A duplication heuristic for static scheduling of tasks on distributed memory multiprocessors

References

• Adam , T.L. , Chandy , K.M. and Dickson , J.R. 1974 . “A Comparison of List Schedules for Parallel Processing Systems,” . Communication of ACM , 17 ( 12 ) : 685 – 690 .
   Web of Science ®Google Scholar
• Al‐Mouhamed , M.A. 1990 . “Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs,” . IEEE Transactions on Software Engineering , 16 ( 12 ) : 1390 – 1401 .
   Web of Science ®Google Scholar
• Baxter , J. and Patel , J.H. “The LAST Algorithm: A Heuristic‐Based Static Task Allocation Algorithm,” . Proceedings of International Conference on parallel Processing . Vol. 2 , pp. 217 – 222 . Chicago, IL
   Google Scholar
• Coffman , E.G. Jr. 1976 . Computer and Job‐Shop Scheduling Theory , New York : Wiley .
   Google Scholar
• Garey , M.R. and Johnson , D.S. 1979 . Computers and Intractability ‐ A Guide to the Theory of NP‐Com‐pleteness , New York : W.H. Freeman .
   Google Scholar
• Graham , R.L. 1969 . “Bounds on Multiprocessor Timing Anomalies,” . SIAM Journal of Applied Mathematics , 17 ( 2 ) : 416 – 429 .
   Web of Science ®Google Scholar
• Hu , T.C. 1961 . “Parallel Sequencing and Assembly Line Problems,” . Operations Research , : 841 – 848 .
   Google Scholar
• Hwang , J.J. , Chow , Y.C. , Anger , F.D. and Lee , C.Y. 1989 . “Scheduling Precedence Graphs in Systems with Interprocessor Communication Times,” . SIAM Journal of Computing , 18 : 244 – 257 .
   Web of Science ®Google Scholar
• Jung , H. , Kirousis , L. and Spirakis , P. “Lower Bounds and Efficient Algorithms for Multiprocessor Scheduling of DAGs with Communication Delay,” . Proceedings of the ACM Symposiums of Parallel Algorithms and Architectures . pp. 254 – 264 .
   Google Scholar
• Kasahara , H. and Narita , S. 1984 . “Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing,” . IEEE Transactions on Computers , 33 ( 11 ) : 1023 – 1029 .
   Web of Science ®Google Scholar
• Kruatrachue , B. 1987 . Static Task Scheduling and Grain Packing in Parallel Processing Systems , Corvallis : Electrical and Computer Engineering Department, Oregon State University . PhD dissertation
   Google Scholar
• Leung , J.Y.T. and Young , G.H. 1989 . “Minimizing Schedule Length Subject to Minimum Flow Time,” . SIAM Journal of Computing , 18 ( 2 ) : 314 – 326 .
   Google Scholar
• Papadimitriou , C.H. and Ullman , J.D. 1987 . “A Communication‐Time Tradeoff,” . SIAM Journal of Computing , 14 ( 4 ) : 639 – 646 .
   Google Scholar
• Shirazi , B. and Wang , M. 1990 . “Analysis and Evaluation of Heuristic Methods for Static Task Scheduling,” . Journal of Parallel and Distributed Computing , 10 : 222 – 232 .
   Web of Science ®Google Scholar
• Sih , G.C. and Lee , E.A. “Scheduling to Account for Interprocessor Communication within Interconnection‐Constrained Processor Networks,” . Proceedings of International Conference on Parallel Processing . Vol. 1 , pp. 9 – 16 . Chicago, IL
   Google Scholar
• Simons , B.B. and Warmuth , M.K. 1989 . “A Fast Algorithm for Multiprocessor Scheduling of Unit‐Time Jobs,” . SIAM Journal of Computing , 18 ( 4 ) : 690 – 710 .
   Google Scholar
• Stone , H. 1987 . High‐Performance Computer Architecture , Reading, Mass. : Addison‐Wesley .
   Google Scholar
• Wu , M.Y. and Gajski , D.D. 1990 . “Hypertool: A Programming Aid for Message‐Passing Systems,” . IEEE Transactions on Parallel and Distributed Systems , 1 ( 3 ) : 330 – 343 .
   Google Scholar
• Correspondence addressee
   Google Scholar