A 2-PASS SCHEDULING ALGORITHM FOR PARALLEL PROGRAMS

被引：10

作者：

KIM, DS

YI, BG

机构：

[1] Department of Computer Science, Pohang University of Science and Technology, Pohang, 790-600

[2] B.-G. Yi is currently with POSCON, Pohang

来源：

PARALLEL COMPUTING | 1994年 / 20卷 / 06期

关键词：

PROCESSOR SCHEDULING; NONPREEMPTIVE SCHEDULING; DATA FLOW GRAPH; INTERPROCESSOR COMMUNICATION; COMPILER; PARALLEL COMPUTER;

D O I：

10.1016/0167-8191(94)90121-X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper a fast task scheduling algorithm is proposed. An optimal task scheduling assigns tasks to processors such that the overall completion time (makespan) of a given task is minimized. To find an optimal task scheduling is known NP-complete. The proposed algorithm finds a suboptimal solution in 0(n log n) time, where n is the number of nodes in the task graph. Experimental results reveal the fact that the algorithm produces a good scheduling output several thousand times faster, whose makespan is longer by 5% at worst, than simulated annealing.

引用

页码：869 / 885

页数：17

共 16 条

[1]

BERNSTEIN D, 1989, IEEE T COMPUT SEP

[2]

BIANCHINI RP, 1987, IEEE T COMPUT, V36, P396, DOI 10.1109/TC.1987.1676922

[3]

Chu W. W., 1980, IEEE COMPUT NOV, P57

[4]

CHU WW, 1987, IEEE T COMPUT, V36, P667, DOI 10.1109/TC.1987.1676960

[5]

Coffman E.G., 1976, COMPUTER JOB SHOP SC

[6]

COFFMAN EG, 1972, ACTA INFORM, V1, P200, DOI DOI 10.1007/BF00288685

[7]

GERSOULIS A, 1992, J PARALLEL DISTRIBUT, V16, P276

[8] PARALLEL SEQUENCING AND ASSEMBLY LINE PROBLEMS [J].

HU, TC .

OPERATIONS RESEARCH, 1961, 9 (06) :841-848

[9]

Kasahara H., 1990, Proceedings of Supercomputing '90 (Cat. No.90CH2916-5), P856, DOI 10.1109/SUPERC.1990.130111

[10]

KASAHARA H, 1984, IEEE T COMPUT, V33, P856

← 1 2 →