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
Estruturas de tarefas em árvore ocorrem frequentemente em muitas aplicações onde a paralelização pode ser desejável. Apresentamos um tratamento formal do escalonamento não preemptivo de árvores de tarefas em multiprocessadores de memória distribuída e mostramos que os problemas fundamentais do escalonamento (i) de uma árvore de tarefas na ausência de qualquer comunicação entre tarefas em um número fixo de processadores e (ii) uma tarefa árvore com comunicação entre tarefas em um número ilimitado de processadores são NP-completas. Para árvores de tarefas que satisfazem certas restrições, apresentamos um algoritmo de escalonamento ideal. O algoritmo se mostra ideal em um conjunto mais amplo de árvores de tarefas do que trabalhos anteriores.
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 Task In-Trees on Distributed Memory Systems" in IEICE TRANSACTIONS on Information,
vol. E84-D, no. 6, pp. 685-691, June 2001, doi: .
Abstract: Tree task structures occur frequently in many applications where parallelization may be desirable. We present a formal treatment of non-preemptively scheduling task trees on distributed memory multiprocessors and show that the fundamental problems of scheduling (i) a task tree in absence of any inter-task communication on a fixed number of processors and (ii) a task tree with inter-task communication on an unbounded number of processors are NP-complete. For task trees that satisfy certain constraints, we present an optimal scheduling algorithm. The algorithm is shown optimal over a wider set of task trees than previous works.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_6_685/_p
Copiar
@ARTICLE{e84-d_6_685,
author={Sanjeev BASKIYAR, },
journal={IEICE TRANSACTIONS on Information},
title={Scheduling Task In-Trees on Distributed Memory Systems},
year={2001},
volume={E84-D},
number={6},
pages={685-691},
abstract={Tree task structures occur frequently in many applications where parallelization may be desirable. We present a formal treatment of non-preemptively scheduling task trees on distributed memory multiprocessors and show that the fundamental problems of scheduling (i) a task tree in absence of any inter-task communication on a fixed number of processors and (ii) a task tree with inter-task communication on an unbounded number of processors are NP-complete. For task trees that satisfy certain constraints, we present an optimal scheduling algorithm. The algorithm is shown optimal over a wider set of task trees than previous works.},
keywords={},
doi={},
ISSN={},
month={June},}
Copiar
TY - JOUR
TI - Scheduling Task In-Trees on Distributed Memory Systems
T2 - IEICE TRANSACTIONS on Information
SP - 685
EP - 691
AU - Sanjeev BASKIYAR
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2001
AB - Tree task structures occur frequently in many applications where parallelization may be desirable. We present a formal treatment of non-preemptively scheduling task trees on distributed memory multiprocessors and show that the fundamental problems of scheduling (i) a task tree in absence of any inter-task communication on a fixed number of processors and (ii) a task tree with inter-task communication on an unbounded number of processors are NP-complete. For task trees that satisfy certain constraints, we present an optimal scheduling algorithm. The algorithm is shown optimal over a wider set of task trees than previous works.
ER -