Scheduling DAGs on Message Passing <I>m</I>-Processor Systems

Sanjeev BASKIYAR

Scheduling DAGs on Message Passing m-Processor Systems

Sanjeev BASKIYAR

Full Text Views

0

Cite this

Summary :

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

Cite this

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 -