The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
O agendamento de gráficos de tarefas acíclicas direcionadas (DAGs) em multiprocessadores é conhecido por ser um problema intratável. Embora existam vários algoritmos heurísticos para escalonamento de DAGs em multiprocessadores, poucos abordam o mapeamento em um determinado número de processadores completamente conectados com o objetivo de minimizar o tempo de término. Apresentamos um algoritmo eficiente chamado ClusterMerge agendar estaticamente gráficos de tarefas acíclicas direcionadas em um sistema MIMD homogêneo completamente conectado com um determinado número de processadores. O algoritmo agrupa tarefas em um DAG usando uma heurística de caminho mais longo e então mescla iterativamente esses clusters para fornecer um número de clusters idêntico ao número de processadores disponíveis. Cada um desses clusters é então agendado em um processador separado. Usando simulações, demonstramos que ClusterMerge agenda gráficos de tarefas produzindo tempos de execução iguais ou inferiores aos de outros pesquisadores, mas usando menos processadores. Também discutimos as armadilhas nas várias abordagens para definir o caminho mais longo em um gráfico de tarefa acíclica direcionada.
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.
Copiar
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
Copiar
@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},}
Copiar
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 -