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
Struktur tugas pokok kerap berlaku dalam banyak aplikasi di mana penyelarasan mungkin diingini. Kami membentangkan rawatan formal penjadualan bukan penjadualan pepohon tugas pada multipemproses memori teragih dan menunjukkan bahawa masalah asas penjadualan (i) pepohon tugas tanpa sebarang komunikasi antara tugas pada bilangan pemproses tetap dan (ii) tugasan pokok dengan komunikasi antara tugas pada bilangan pemproses yang tidak terhad adalah NP-lengkap. Untuk pepohon tugas yang memenuhi kekangan tertentu, kami membentangkan algoritma penjadualan yang optimum. Algoritma ditunjukkan secara optimum pada set pepohon tugas yang lebih luas daripada kerja sebelumnya.
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.
Salinan
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
Salinan
@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},}
Salinan
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 -