The search functionality is under construction.

The search functionality is under construction.

Scheduling directed a-cyclic task graphs (DAGs) onto multiprocessors is known to be an intractable problem. Although there have been several heuristic algorithms for scheduling DAGs onto multiprocessors, few address the mapping onto a given number of completely connected processors with an objective of minimizing the finish time. We present an efficient algorithm called *ClusterMerge* to statically schedule directed a-cyclic task graphs onto a homogeneous completely connected MIMD system with a given number of processors. The algorithm clusters tasks in a DAG using a longest path heuristic and then iteratively merges these clusters to give a number of clusters identical to the number of available processors. Each of these clusters is then scheduled on a separate processor. Using simulations, we demonstrate that *ClusterMerge* schedules task graphs yielding the same or lower execution times than those of other researchers, but using fewer processors. We also discuss pitfalls in the various approaches to defining the longest path in a directed a-cyclic task graph.

- Publication
- IEICE TRANSACTIONS on Information Vol.E83-D No.7 pp.1497-1507

- Publication Date
- 2000/07/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Computer Systems

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.

Copy

Sanjeev BASKIYAR, "Scheduling DAGs on Message Passing m-Processor Systems" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 7, pp. 1497-1507, July 2000, doi: .

Abstract: Scheduling directed a-cyclic task graphs (DAGs) onto multiprocessors is known to be an intractable problem. Although there have been several heuristic algorithms for scheduling DAGs onto multiprocessors, few address the mapping onto a given number of completely connected processors with an objective of minimizing the finish time. We present an efficient algorithm called *ClusterMerge* to statically schedule directed a-cyclic task graphs onto a homogeneous completely connected MIMD system with a given number of processors. The algorithm clusters tasks in a DAG using a longest path heuristic and then iteratively merges these clusters to give a number of clusters identical to the number of available processors. Each of these clusters is then scheduled on a separate processor. Using simulations, we demonstrate that *ClusterMerge* schedules task graphs yielding the same or lower execution times than those of other researchers, but using fewer processors. We also discuss pitfalls in the various approaches to defining the longest path in a directed a-cyclic task graph.

URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_7_1497/_p

Copy

@ARTICLE{e83-d_7_1497,

author={Sanjeev BASKIYAR, },

journal={IEICE TRANSACTIONS on Information},

title={Scheduling DAGs on Message Passing m-Processor Systems},

year={2000},

volume={E83-D},

number={7},

pages={1497-1507},

abstract={Scheduling directed a-cyclic task graphs (DAGs) onto multiprocessors is known to be an intractable problem. Although there have been several heuristic algorithms for scheduling DAGs onto multiprocessors, few address the mapping onto a given number of completely connected processors with an objective of minimizing the finish time. We present an efficient algorithm called *ClusterMerge* to statically schedule directed a-cyclic task graphs onto a homogeneous completely connected MIMD system with a given number of processors. The algorithm clusters tasks in a DAG using a longest path heuristic and then iteratively merges these clusters to give a number of clusters identical to the number of available processors. Each of these clusters is then scheduled on a separate processor. Using simulations, we demonstrate that *ClusterMerge* schedules task graphs yielding the same or lower execution times than those of other researchers, but using fewer processors. We also discuss pitfalls in the various approaches to defining the longest path in a directed a-cyclic task graph.},

keywords={},

doi={},

ISSN={},

month={July},}

Copy

TY - JOUR

TI - Scheduling DAGs on Message Passing m-Processor Systems

T2 - IEICE TRANSACTIONS on Information

SP - 1497

EP - 1507

AU - Sanjeev BASKIYAR

PY - 2000

DO -

JO - IEICE TRANSACTIONS on Information

SN -

VL - E83-D

IS - 7

JA - IEICE TRANSACTIONS on Information

Y1 - July 2000

AB - Scheduling directed a-cyclic task graphs (DAGs) onto multiprocessors is known to be an intractable problem. Although there have been several heuristic algorithms for scheduling DAGs onto multiprocessors, few address the mapping onto a given number of completely connected processors with an objective of minimizing the finish time. We present an efficient algorithm called *ClusterMerge* to statically schedule directed a-cyclic task graphs onto a homogeneous completely connected MIMD system with a given number of processors. The algorithm clusters tasks in a DAG using a longest path heuristic and then iteratively merges these clusters to give a number of clusters identical to the number of available processors. Each of these clusters is then scheduled on a separate processor. Using simulations, we demonstrate that *ClusterMerge* schedules task graphs yielding the same or lower execution times than those of other researchers, but using fewer processors. We also discuss pitfalls in the various approaches to defining the longest path in a directed a-cyclic task graph.

ER -