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
트리 작업 구조는 병렬화가 바람직한 많은 응용 프로그램에서 자주 발생합니다. 우리는 분산 메모리 다중 프로세서에서 비선점형 스케줄링 작업 트리에 대한 형식적인 처리를 제시하고 (i) 고정된 수의 프로세서에서 작업 간 통신이 없는 작업 트리와 (ii) 작업 스케줄링의 근본적인 문제를 보여줍니다. 무제한의 프로세서에서 작업 간 통신이 가능한 트리는 NP-완전입니다. 특정 제약 조건을 만족하는 작업 트리에 대해 최적의 스케줄링 알고리즘을 제시합니다. 알고리즘은 이전 연구보다 더 넓은 작업 트리 세트에 대해 최적으로 표시됩니다.
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.
부
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
부
@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},}
부
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 -