An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes
Summary :
This paper deals with two-processor nonpreemptive scheduling problem for acyclic SWITCH-less program nets including two types of nodes: AND-node and OR-node. Compared with task graphs that are a special case of acyclic SWITCH-less program nets and include only AND-nodes, the multiprocessor scheduling problem of general acyclic SWITCH-less program nets is more complicated. Since multiprocessor scheduling problem for general task graphs is NP-hard, so is for acyclic SWITCH-less program nets generally. In this paper, we suppose the acyclic SWITCH-less program nets satisfy: (i) each AND-node and OR-node have 1 and 0 node firing time, respectively; (ii) each AND-node possesses single input edge. For such a class of acyclic SWITCH-less program nets, we first propose a hybrid priority list L that consists of both dynamic and static sub-lists. Then we prove that, for a given acyclic SWITCH-less program net to be executed by two identical processors, the schedule generated by L is optimal.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.6 pp.1274-1280
- Publication Date
- 2002/06/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Papers Selected from 2001 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2001))
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Qi-Wei GE, "An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 6, pp. 1274-1280, June 2002, doi: .
Abstract: This paper deals with two-processor nonpreemptive scheduling problem for acyclic SWITCH-less program nets including two types of nodes: AND-node and OR-node. Compared with task graphs that are a special case of acyclic SWITCH-less program nets and include only AND-nodes, the multiprocessor scheduling problem of general acyclic SWITCH-less program nets is more complicated. Since multiprocessor scheduling problem for general task graphs is NP-hard, so is for acyclic SWITCH-less program nets generally. In this paper, we suppose the acyclic SWITCH-less program nets satisfy: (i) each AND-node and OR-node have 1 and 0 node firing time, respectively; (ii) each AND-node possesses single input edge. For such a class of acyclic SWITCH-less program nets, we first propose a hybrid priority list L that consists of both dynamic and static sub-lists. Then we prove that, for a given acyclic SWITCH-less program net to be executed by two identical processors, the schedule generated by L is optimal.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_6_1274/_p
Copy
@ARTICLE{e85-a_6_1274,
author={Qi-Wei GE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes},
year={2002},
volume={E85-A},
number={6},
pages={1274-1280},
abstract={This paper deals with two-processor nonpreemptive scheduling problem for acyclic SWITCH-less program nets including two types of nodes: AND-node and OR-node. Compared with task graphs that are a special case of acyclic SWITCH-less program nets and include only AND-nodes, the multiprocessor scheduling problem of general acyclic SWITCH-less program nets is more complicated. Since multiprocessor scheduling problem for general task graphs is NP-hard, so is for acyclic SWITCH-less program nets generally. In this paper, we suppose the acyclic SWITCH-less program nets satisfy: (i) each AND-node and OR-node have 1 and 0 node firing time, respectively; (ii) each AND-node possesses single input edge. For such a class of acyclic SWITCH-less program nets, we first propose a hybrid priority list L that consists of both dynamic and static sub-lists. Then we prove that, for a given acyclic SWITCH-less program net to be executed by two identical processors, the schedule generated by L is optimal.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1274
EP - 1280
AU - Qi-Wei GE
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2002
AB - This paper deals with two-processor nonpreemptive scheduling problem for acyclic SWITCH-less program nets including two types of nodes: AND-node and OR-node. Compared with task graphs that are a special case of acyclic SWITCH-less program nets and include only AND-nodes, the multiprocessor scheduling problem of general acyclic SWITCH-less program nets is more complicated. Since multiprocessor scheduling problem for general task graphs is NP-hard, so is for acyclic SWITCH-less program nets generally. In this paper, we suppose the acyclic SWITCH-less program nets satisfy: (i) each AND-node and OR-node have 1 and 0 node firing time, respectively; (ii) each AND-node possesses single input edge. For such a class of acyclic SWITCH-less program nets, we first propose a hybrid priority list L that consists of both dynamic and static sub-lists. Then we prove that, for a given acyclic SWITCH-less program net to be executed by two identical processors, the schedule generated by L is optimal.
ER -
English
