Multiprocessor scheduling in a genetic paradigm

被引:47
作者
Ahmad, I
Dhodhi, MK
机构
[1] Dept. of Elec. and Comp. Engineering, Kuwait University, Safat 13060, P.O. Box
关键词
graph theory; scheduling problem; multiprocessor system; genetic algorithm;
D O I
10.1016/0167-8191(95)00068-2
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper, we present a technique based on the problem-space genetic algorithm (PSGA) for the static scheduling of directed acyclic graphs onto homogeneous multiprocessor systems to reduce the response-time. The PSGA based approach combines genetic algorithms with a list scheduling heuristic to search a large solution space efficiently and effectively to find the best possible solution in an acceptable cpu time. Comparison of results with the genetic algorithm (GA) based scheduling technique for the Stanford manipulator and the Elbow manipulator examples shows a significant improvement in the response-time. We also demonstrate the effectiveness of our algorithm by comparing it with the Critical Path/Maximum Immediate Successor First (CP/MISF) list scheduling technique for randomly generated graphs. The proposed scheme offers on the average a 3.6% improvement in the response-time as compared to the CP/MISF technique for all the random graphs.
引用
收藏
页码:395 / 406
页数:12
相关论文
共 14 条
[1]   COMPARISON OF LIST SCHEDULES FOR PARALLEL PROCESSING SYSTEMS [J].
ADAM, TL ;
CHANDY, KM ;
DICKSON, JR .
COMMUNICATIONS OF THE ACM, 1974, 17 (12) :685-690
[2]   TASK ASSIGNMENT USING A PROBLEM-SPACE GENETIC ALGORITHM [J].
AHMAD, I ;
DHODHI, MK .
CONCURRENCY-PRACTICE AND EXPERIENCE, 1995, 7 (05) :411-428
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]  
Coffman E. G. Jr., 1972, Acta Informatica, V1, P200, DOI 10.1007/BF00288685
[5]   DATAPATH SYNTHESIS USING A PROBLEM-SPACE GENETIC ALGORITHM [J].
DHODHI, MK ;
HIELSCHER, FH ;
STORER, RH .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1995, 14 (08) :934-944
[6]  
Goldberg DE, 1989, GENETIC ALGORITHMS S
[7]   BOUNDS ON MULTIPROCESSING TIMING ANOMALIES [J].
GRAHAM, RL .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (02) :416-&
[8]   A GENETIC ALGORITHM FOR MULTIPROCESSOR SCHEDULING [J].
HOU, ESH ;
ANSARI, N ;
REN, H .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (02) :113-120
[9]  
KASAHARA H, 1984, IEEE T COMPUT, V33, P1023, DOI 10.1109/TC.1984.1676376
[10]  
Kasahara H., 1985, IEEE Journal of Robotics and Automation, VRA-1, P104, DOI 10.1109/JRA.1985.1087004