Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach

被引:221
作者
Wang, L [1 ]
Siegel, HJ
Roychowdhury, VP
Maciejewski, AA
机构
[1] Purdue Univ, Sch Elect & Comp Engn, Parallel Proc Lab, W Lafayette, IN 47907 USA
[2] Univ Calif Los Angeles, Dept Elect Engn, Los Angeles, CA 90095 USA
关键词
D O I
10.1006/jpdc.1997.1392
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
To exploit a heterogeneous computing (HC) environment, an application task may be decomposed into subtasks that have data dependencies. Subtask matching and scheduling consists of assigning subtasks to machines, ordering subtask execution for each machine, and ordering intermachine data transfers. The goal is to achieve the minimal completion time for the task. A heuristic approach based on a genetic algorithm is developed to do matching and scheduling in HC environments. It is assumed that the matcher/scheduler is in control of a dedicated HC suite of machines. The characteristics of this genetic-algorithm-based approach include: separation of the matching and the scheduling representations, independence of the chromosome structure from the details of the communication subsystem, and consideration of overlap among all computations and communications that obey subtask precedence constraints. It is applicable to the static scheduling of production jobs and can be readily used to collectively schedule a set of tasks that are decomposed into subtasks. Some parameters and the selection scheme of the genetic algorithm were chosen experimentally to achieve the best performance. Extensive simulation tests were conducted. For small-sized problems (e.g., a small number of subtasks and a small number of machines), exhaustive searches were used to verify that this genetic-algorithm-based approach found the optimal solutions. Simulation results for larger-sized problems showed that this genetic-algorithm-based approach outperformed two nonevolutionary heuristics and a random search. (C) 1997 Academic Press.
引用
收藏
页码:8 / 22
页数:15
相关论文
共 35 条
[1]   Multiprocessor scheduling in a genetic paradigm [J].
Ahmad, I ;
Dhodhi, MK .
PARALLEL COMPUTING, 1996, 22 (03) :395-406
[2]  
[Anonymous], 5 HET COMP WORKSH
[3]   GENETIC SCHEDULING OF TASK GRAPHS [J].
BENTEN, MST ;
SAIT, SM .
INTERNATIONAL JOURNAL OF ELECTRONICS, 1994, 77 (04) :401-415
[4]  
BUDENSKE JR, 1997, P 1997 HET COMP WORK, P96
[5]   EFFICIENT SCHEDULING ALGORITHMS FOR ROBOT INVERSE DYNAMICS COMPUTATION ON A MULTIPROCESSOR SYSTEM [J].
CHEN, CL ;
LEE, CSG ;
HOU, ESH .
IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1988, 18 (05) :729-743
[6]  
CORMEN TH, 1992, INTRO ALGORITHMS
[7]  
DAVIS L, 1991, HDB GENTIC ALGORITHM
[8]  
Eshaghian M. M., 1994, International Journal of High Speed Computing, V6, P287, DOI 10.1142/S0129053394000147
[9]   ALLOCATING MODULES TO PROCESSORS IN A DISTRIBUTED SYSTEM [J].
FERNANDEZBACA, D .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1989, 15 (11) :1427-1436
[10]  
FREUND RF, 1993, COMPUTER, V26, P13