An Optimal Two-Processor Scheduling for a Class of Program Nets via a Hybrid Priority List (特集 並列処理)
スポンサーリンク
概要
- 論文の詳細を見る
This paper deals with two-processor scheduling for acyclic SWITCH-less program nets that is a graph representation of data-flow programs. A task graph is a special case of acyclic SWITCH-less program net and the important difference between a program net and a task graph is that a program net allows the nodes to fire more than once while a task graph require each of its nodes to fire exactly once. Hence the multiprocessor scheduling problem for general acyclic SWITCH-less program nets is NP-hard in a strong sense. In this paper, we require the program nets to satisfy: (i) all the nodes have the same firing time and (ii) all the AND-nodes possess single input edge. For such a class of program nets, we first propose a scheduling method using hybrid priority list that consists of both dynamic and static lists, and then prove optimality of the schedules generated by the hybrid priority list.
- 一般社団法人情報処理学会の論文
- 1999-05-15
著者
-
Ge Q‐w
Yamaguchi Univ. Yamaguchi‐shi Jpn
-
Ge Qi-wei
Faculty Of Education Yamaguchi University
-
YOSHIOKA NAOMI
Fujitsu Ten Limited
-
Ge Qi‐wei
Faculty Of Education Yamaguchi University
関連論文
- An Optimal Two-Processor Scheduling for a Class of Program Nets via a Hybrid Priority List (特集 並列処理)
- Modelling and simulation of signal transductions in an apoptosis pathway by using timed Petri nets
- A Flexible and Efficient Workflow Change Type : Selective Shift(Papers Selected from ITC-CSCC 2004)
- Modeling and Performance Evaluation on Change Time for Migrate Dynamic Workflow Changes(Special Section on Papers Selected from ITC-CSCC 2002)
- WF-Net Based Modeling and Soundness Verification of Interworkflows(Selected Papers from the 19th Workshop on Circuits and Systems in Karuizawa)
- Complexity and a Heuristic Algorithm of Computing Parallel Degree for Program Nets with SWITCH-Nodes(Concurrent Systems,Concurrent/Hybrid Systems: Theory and Applications)
- Performance Evaluation on Worst Change Time of Flush and SCO Dynamic Changes for State Machine WF-Nets(Papers Selected from 2005 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2005))
- Dead Problem of Program Nets(Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
- Computation Methods of Maximum Throughput for MG/SMWF-Nets with Conflict-Free Resources(Concurrent Systems)(Concurrent Systems and Hybrid Systems)
- Performance Evaluation on Transient Time of Dynamic Workflow Changes(Special Section on Concurrent Systems Technology)
- Performance Evaluation on Change Time of Dynamic Workflow Changes (Special Section on Concurrent Systems Technology)
- Parallel Degree of Well-Structured Workflow Nets
- Delay Time Determination for the Timed Petri Net Model of a Signaling Pathway Based on Its Structural Information
- On Verification of Token Self-Cleanness of Data-Flow Program Nets (Special Section of Papers Selected from JTC-CSCC'95)
- Performance Evaluation of a Two-Processor Scheduling Method for Acyclic SWITCH-less Program Nets(Papers Selected from ITC-CSCC 2004)
- A New Proposal to Two-Processor Scheduling Problem for SWITCH-less Program Nets(Concurrent Systems)(Concurrent Systems and Hybrid Systems)
- An Optimal Two-Processor Scheduling for a Class of SWITCH-less Program Nets with Combined OR-nodes(Special Section on Papers Selected from ITC-CSCC 2001)
- A Two-Processor Scheduling Method for a Class of Program Nets with Unity Node Firing Time (Special Section on Concurrent Systems Technology)
- A Method of Finding Legal Sequence Number for a Class of Extended Series-Parallel Digraphs (Special Section on Discrete Mathematics and Its Applications)
- An Effective Dynamic Priority List for 2-Processor Scheduling of Program Nets(Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
- Incorporation of Cycles and Inhibitory Arcs into the Timed Petri Net Model of Signaling Pathway