A DAG scheduling algorithm based on selected duplication of precedent tasks

被引：7

作者：

Meng X. ^{[1
]}

Liu W. ^{[1
]}

机构：

[1] Department of Computer Science and Engineering, Dalian University of Technology

来源：

Jisuanji Fuzhu Sheji Yu Tuxingxue Xuebao/Journal of Computer-Aided Design and Computer Graphics | 2010年 / 22卷 / 06期

关键词：

Directed acyclic graph; Finish time; Heterogeneous computing environment; Task duplication; Task scheduling;

D O I：

10.3724/SP.J.1089.2010.10865

中图分类号：

学科分类号：

摘要：

This paper addresses static scheduling of a directed acyclic graph (DAG) on a heterogeneous, bounded set of distributed processors to minimize the overall run-time of application. By combining list-based scheduling and task duplication, a new static scheduling algorithm, named as selected task-duplication for heterogeneous system (STDH), is proposed, which improves the performance of list-based algorithm with the duplication. By utilizing idle time of the processors, STDH duplicates the parent tasks for advancing the earliest starting time of the current candidate task to reduce the inter-processor communication cost and its waiting time of the processor. By this way, the overall run-time of application is shortened. The experimental results show that STDH outperforms HEFT, HNDP and DDS in terms of finish time. Besides, while the ratio of total communication cost and total computation cost of the task graph becomes larger, STDH's advantage is more distinct.

引用

页码：1056 / 1062

页数：6

共 14 条

[1]

Du X., Jiang C., Xu G., Et al., A grid DAG scheduling algorithm based on fuzzy clustering, Journal of Software, 17, 11, pp. 2277-2288, (2006)

[2]

Kwok Y.K., Ahmad I., Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors, IEEE Transactions on Parallel and Distributed Systems, 7, 5, pp. 506-521, (1996)

[3]

Hou E.S.H., Ansari N., Ren H., A genetic algorithm for multiprocessor scheduling, IEEE Transactions on Parallel and Distributed Systems, 5, 2, pp. 113-120, (1994)

[4]

Maheswaran M., Siegel H.J., A dynamic matching and scheduling algorithm for heterogeneous computing systems, Proceedings of the 7th Heterogeneous Computing Workshop, pp. 57-69, (1998)

[5]

Chung Y.C., Ranka S., Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors, Proceedings of the ACM/IEEE Conference on Supercomputing, pp. 512-521, (1992)

[6]

Ahmad I., Kwok Y.K., On exploiting task duplication in parallel program scheduling, IEEE Transactions on Parallel and Distributed Systems, 9, 9, pp. 872-892, (1998)

[7]

Yang T., Gerasoulis A., DSC: scheduling parallel tasks on an unbounded number of processors, IEEE Transactions on Parallel and Distributed Systems, 5, 9, pp. 951-967, (1994)

[8]

Sih G.C., Lee E.A., A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE Transactions on Parallel and Distributed Systems, 4, 2, pp. 175-187, (1993)

[9]

Adam T.L., Chandy K.M., Dickson J.R., A comparison of list schedules for parallel processing systems, Communications of the ACM, 17, 12, pp. 685-690, (1974)

[10]

Wu M.Y., Gajski D.D., Hypertool: a programming aid for message passing systems, IEEE Transactions on Parallel and Distributed Systems, 1, 3, pp. 330-343, (1990)

← 1 2 →