Static scheduling algorithms for allocating directed task graphs to multiprocessors

ABSTRACT

Static scheduling of a program represented by a directed task graph on a multiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP-complete problem in general, researchers have resorted to devising efficient heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, searching, graph-theory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categories. We consider 27 scheduling algorithms, with each algorithm explained through an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promising optimization approaches and current research trends in the area. Finally, we give an overview of the software tools that provide scheduling/mapping functionalities.

REFERENCES

• 1: Thomas L. Adam , K. M. Chandy , J. R. Dickson, A comparison of list schedules for parallel processing systems, Communications of the ACM, v.17 n.12, p.685-690, Dec 1974 [doi>10.1145/361604.361619]
• 2: AHMAD, I. AND DHODHI, M. K. 1995. Task assignment using a problem-space genetic algorithm. Concurrency: Pract. Exper. 7, 5 (Aug.), 411-428.
• 3: Ishfaq Ahmad , Arif Ghafoor, Semi-Distributed Load Balancing for Massively Parallel Multicomputer Systems, IEEE Transactions on Software Engineering, v.17 n.10, p.987-1004, October 1991 [doi>10.1109/32.99188]
• 4: Ishfaq Ahmad , Yu-Kwong Kwok, On Exploiting Task Duplication in Parallel Program Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.9 n.9, p.872-892, September 1998 [doi>10.1109/71.722221]
• 5: Ishfaq Ahmad , Yu-Kwong Kwok, Optimal and Near-Optimal Allocation of Precedence-Constrained Tasks to Parallel Processors: Defying the High Complexity Using Effective Search Techniques, Proceedings of the 1998 International Conference on Parallel Processing, p.424-431, August 10-14, 1998
• 6: Ishfaq Ahmad , Yu-Kwong Kwok, On Parallelizing the Multiprocessor Scheduling Problem, IEEE Transactions on Parallel and Distributed Systems, v.10 n.4, p.414-432, April 1999 [doi>10.1109/71.762819]
• 7: Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors, Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms and Networks, p.207, June 12-14, 1996
• 8: Ishfaq Ahmad , Yu-Kwong Kwok , Min-You Wu , Wei Shu, Automatic Parallelization and Scheduling of Programs on Multiprocessors using CASCH, Proceedings of the international Conference on Parallel Processing, p.288-291, August 11-15, 1997
• 9: ALI, H. H. AND EL-REWINI, H. 1993. The time complexity of scheduling interval orders with communication is polynomial. Para. Proc. Lett. 3, 1, 53-58.
• 10: Ali Shahid , Muhammed S. T. Benten , Sadiq M. Sait, GSA: scheduling and allocation using genetic algorithm, Proceedings of the conference on European design automation, p.84-89, September 19-23, 1994, Grenoble, France
• 11: Mayez A. Al-Mouhamed, Lower Bound on the Number of Processors and Time for Scheduling Precedence Graphs with Communication Costs, IEEE Transactions on Software Engineering, v.16 n.12, p.1390-1401, December 1990 [doi>10.1109/32.62447]
• 12: V. A. F. Almeida , I. M. M. Vasconcelos , J. N. C. Árabe , D. A. Menascé, Using random task graphs to investigate the potential benefits of heterogeneity in parallel systems, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.683-691, November 16-20, 1992, Minneapolis, Minnesota, United States
• 13: AMDAHL, G. 1967. Validity of the single processor approach to achieving large scale computing capability. In Proceedings of the on AFIPS Spring Joint Computer Conference (Reston, Va.), AFIPS Press, Arlington, VA, 483-485.
• 14: Frank D. Anger , Jing-Jang Hwang , Yuan-Chieh Chow, Scheduling with sufficient loosely coupled processors, Journal of Parallel and Distributed Computing, v.9 n.1, p.87-92, May 1990 [doi>10.1016/0743-7315(90)90116-7]
• 15: BASHIR, A. F., SUSARLA, V., AND VAIRAVAN, K. 1983. A statistical study of the performance of a task scheduling algorithm. IEEE Trans. Comput. C-32, 8 (Aug.), 774-777.
• 16: BAXTER, J. AND PATEL, J. H. 1989. The LAST algorithm: A heuristic-based static task allocation algorithm. In Proceedings of the International Conference on Parallel Processing (ICPP '89, Aug.), Pennsylvania State University, University Park, PA, 217-222.
• 17: Micah Beck , Keshav Pingali , Alexandru Nicolau, Static scheduling for dynamic dataflow machines, Journal of Parallel and Distributed Computing, v.10 n.4, p.279-288, Dec. 1990 [doi>10.1016/0743-7315(90)90030-S]
• 18: BENTEN, M. S. T. AND SAIT, S.M. 1994. Genetic scheduling of task graphs. Int. J. Electron. 77, 4 (Oct.), 401-415.
• 19: J Blazewicz , M Drabowski , J Weglarz, Scheduling multiprocessor tasks to minimize schedule length, IEEE Transactions on Computers, v.35 n.5, p.389-393, May 1986 [doi>10.1109/TC.1986.1676781]
• 20: J Blazewicz , J Weglarz , M Drabowski, Scheduling independent 2-processor tasks to minimize schedule length, Information Processing Letters, v.18 n.5, p.267-273, June 1984 [doi>10.1016/0020-0190(84)90006-1]
• 21: BOKHARI, S.H. 1979. Dual processor scheduling with dynamic reassignment. IEEE Trans. Softw. Eng. SE-5, 4 (July), 341-349.
• 22: BOKHARI, S.H. 1981. On the mapping problem. IEEE Trans. Comput. C-30, 5, 207-214.
• 23: BOZOKI, G. AND RICHARD, J.P. 1970. A branchand-bound algorithm for continuous-process task shop scheduling problem. AIIE Trans. 2, 246 -252.
• 24: J. Bruno , E. G. Coffman, Jr. , R. Sethi, Scheduling independent tasks to reduce mean finishing time, Communications of the ACM, v.17 n.7, p.382-387, July 1974 [doi>10.1145/361011.361064]
• 25: T. L. Casavant , J. G. Kuhl, A taxonomy of scheduling in general-purpose distributed computing systems, IEEE Transactions on Software Engineering, v.14 n.2, p.141-154, February 1988 [doi>10.1109/32.4634]
• 26: CHANDRASEKHARAM, R., SUBHRAMANIAN, S., AND CHAUDHURY, S. 1993. Genetic algorithm for node partitioning problem and applications in VLSI design. IEE Proc. Comput. Digit. Tech. 140, 5 (Sept.), 255-260.
• 27: Guan-Ing Chen , Ten-Hwang Lai, Scheduling Independent Jobs on Hypercubes, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.273-280, February 11-13, 1988
• 28: Guan-Ing Chen , Ten-Hwang Lai, Preemptive scheduling of independent jobs on a hypercube, Information Processing Letters, v.28 n.4, p.201-206, July 29, 1988 [doi>10.1016/0020-0190(88)90209-8]
• 29: CHEN, H., SHIRAZI, B., AND MARQUIS, J. 1993. Performance evaluation of a novel scheduling method: Linear clustering with task duplication. In Proceedings of the 2nd International Conference on Parallel and Distributed Systerns (Dec.), 270-275.
• 30: Runwei Cheng , Mitsuo Gen , Yasuhiro Tsujimura, A tutorial survey of job-shop scheduling problems using genetic algorithms—I: representation, Computers and Industrial Engineering, v.30 n.4, p.983-997, Sept. 1996 [doi>10.1016/0360-8352(96)00047-2]
• 31: CHRETIENNE, P. 1989. A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints. Europ. J. Oper. Res. 43, 225- 230.
• 32: CHU, W. W., LAN, M.-T., AND HELLERSTEIN, J. 1984. Estimation of intermodule communication (IMC) and its applications in distributed processing systems. IEEE Trans. Comput. C-33, 8 (Aug.), 691-699.
• 33: Y.-C. Chung , S. Ranka, Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.512-521, November 16-20, 1992, Minneapolis, Minnesota, United States
• 34: COFFMAN, E.G. 1976. Computer and Job-Shop Scheduling Theory. John Wiley and Sons, Inc., New York, NY.
• 35: COFFMAN, E. G. AND GRAHAM, R. L. 1972. Optimal scheduling for two-processor systerns. Acta Inf. 1,200-213.
• 36: COLIN, J. Y. AND CHRETIENNE, P. 1991. C.P.M. scheduling with small computation delays and task duplication. Oper. Res. 39, 4, 680- 684.
• 37: COSNARD, M. AND LOI, M. 1995. Automatic task graph generation techniques. Para. Proc. Lett. 5, 4 (Dec.), 527-538.
• 38: CRAY RESEARCH, INC. 1991. UNICOS Performance Utilities Reference Manual, SR2040. Cray Supercomputers, Chippewa Falls, MN.
• 39: W. J. Dally, Virtual-Channel Flow Control, IEEE Transactions on Parallel and Distributed Systems, v.3 n.2, p.194-205, March 1992 [doi>10.1109/71.127260]
• 40: S. Darbha , D. P. Agrawal, A fast and scalable scheduling algorithm for distributed memory systems, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.60, October 25-28, 1995
• 41: DAVIS, T., Ed. 1991. The Handbook of Genetic Algorithms. Van Nostrand Reinhold Co., New York, NY.
• 42: I. De Falco , R. Del Balio , E. Tarantino, An analysis of parallel heuristics for task allocation in multicomputers, Computing, v.59 n.3, p.259-275, 1997 [doi>10.1007/BF02684444]
• 43: DHODI, M. K., AHMAD, I., AND AHMAD, I. 1995. A multiprocessor scheduling scheme using problem-space genetic algorithms. In Proceedings of the IEEE International Conference on Evolutionary Computation, IEEE Computer Society Press, Los Alamitos, CA, 214-219.
• 44: DIGITAL EQUIPMENT CORP. 1992. PARASPHERE User's Guide. Digital Equipment Corp., Maynard, MA.
• 45: DIXIT-RADYA, V. A. AND PANDA, D. K. 1993. Task assignment on distrbuted-memory systerns with adaptive wormhole routing. In Proceedings of the 2nd International Conference on Parallel and Distributed Systems (Dec.), 674-681.
• 46: J. Du , J. Y.-T. Leung, Complexity of scheduling parallel task systems, SIAM Journal on Discrete Mathematics, v.2 n.4, p.473-487, Nov. 1989 [doi>10.1137/0402042]
• 47: Hesham El-Rewini , Hesham H. Ali, Static scheduling of conditional branches in parallel programs, Journal of Parallel and Distributed Computing, v.24 n.1, p.41-54, Jan. 1995 [doi>10.1006/jpdc.1995.1005]
• 48: Hesham El-Rewini , Hesham H. Ali , Ted Lewis, Task Scheduling in Multiprocessing Systems, Computer, v.28 n.12, p.27-37, December 1995 [doi>10.1109/2.476197]
• 49: Hesham El-Rewini , T. G. Lewis, Scheduling parallel program tasks onto arbitrary target machines, Journal of Parallel and Distributed Computing, v.9 n.2, p.138-153, June 1990 [doi>10.1016/0743-7315(90)90042-N]
• 50: Hesham El-Rewini , Theodore G. Lewis , Hesham H. Ali, Task scheduling in parallel and distributed systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1994
• 51: ERCEGOVAC, M. D. 1988. Heterogeneity in supercomputer architectures. Parallel Comput. 7, 367-372.
• 52: FERNANDEZ, E. B. AND BUSSELL, B. 1973. Bounds on the number of processors and time for multiprocessor optimal schedules. IEEE Trans. Comput. C-22, 8 (Aug.), 745-751.
• 53: Solving Combinatorial Optimization Problems in Parallel - Methods and Techniques, January 1996
• 54: José L. Ribeiro Filho , Philip C. Treleaven , Cesare Alippi, Genetic-Algorithm Programming Environments, Computer, v.27 n.6, p.28-43, June 1994 [doi>10.1109/2.294850]
• 55: FISHBURN, P. C. 1985. Interval Orders and Interval Graphs. John Wiley and Sons, Inc., New York, NY.
• 56: Stephanie Forrest , Melanie Mitchell, What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation, Machine Learning, v.13 n.2-3, p.285-319, Nov./Dec. 1993 [doi>10.1007/BF00993046]
• 57: Richard F. Freund , Howard Jay Siegel, Guest Editor's Introduction: Heterogeneous Processing, Computer, v.26 n.6, p.13-17, June 1993
• 58: Donald K. Friesen, Tighter bounds for LPT scheduling on uniform processors, SIAM Journal on Computing, v.16 n.3, p.554-560, June 1987 [doi>10.1137/0216037]
• 59: FuJII, M., KASAMI, T., AND NINOMIYA, K. 1969. Optimal Sequencing of Two Equivalent Processors. SIAM J. Appl. Math. 17, 1.
• 60: Harold N. Gabow, An Almost-Linear Algorithm for Two-Processor Scheduling, Journal of the ACM (JACM), v.29 n.3, p.766-780, July 1982 [doi>10.1145/322326.322335]
• 61: GAJSKI, D. D. AND PIER, J. 1985. Essential issues in multiprocessors. IEEE Computer 18, 6 (June).
• 62: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 63: GAREY, M. R., JOHNSON, D., TARJAN, R., AND YAN- NAKAKIS, M. 1983. Scheduling opposing forests. SIAM J. Algebr. Discret. Methods 4, 1, 72-92.
• 64: GERASOULIS, A. AND YANG, T. 1992. A comparison of clustering heuristics for scheduling DAG's on multiprocessors. J. Parallel Distrib. Comput. 16, 4 (Dec.), 276-291.
• 65: A. Gerasoulis , T. Yang, On the Granularity and Clustering of Directed Acyclic Task Graphs, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.686-701, June 1993 [doi>10.1109/71.242154]
• 66: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 67: Mario J. Gonzalez, Jr., Deterministic Processor Scheduling, ACM Computing Surveys (CSUR), v.9 n.3, p.173-204, Sept. 1977 [doi>10.1145/356698.356700]
• 68: Teofilo Gonzalez , Sartaj Sahni, Preemptive Scheduling of Uniform Processor Systems, Journal of the ACM (JACM), v.25 n.1, p.92-101, Jan. 1978 [doi>10.1145/322047.322055]
• 69: GRAHAM, R.L. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.
• 70: GRAHAM, R. L., LAWLER, E. L., LENSTRA, J. K., AND RINNOY KAN, A. H. G. 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. 5, 287-326.
• 71: Soonhoi Ha , Edward A. Lee, Compile-Time Scheduling and Assignment of Data-Flow Program Graphs with Data-Dependent Iteration, IEEE Transactions on Computers, v.40 n.11, p.1225-1238, November 1991 [doi>10.1109/12.102826]
• 72: HANAN, M. AND KURTZBERG, J. 1972. A review of the placement and quadratic assignment problems. SIAM Rev. 14 (Apr.), 324-342.
• 73: Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
• 74: Dorit s. Hochbaum , David B. Shmoys, A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach, SIAM Journal on Computing, v.17 n.3, p.539-551, June 1988 [doi>10.1137/0217033]
• 75: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 76: Edward C. Horvath , Shui Lam , Ravi Sethi, A Level Algorithm for Preemptive Scheduling, Journal of the ACM (JACM), v.24 n.1, p.32-43, Jan. 1977 [doi>10.1145/321992.321995]
• 77: E. S. H. Hou , N. Ansari , H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.113-120, February 1994 [doi>10.1109/71.265940]
• 78: Hu, T.C. 1961. Parallel sequencing and assembly line problems. Oper. Res. 19, 6 (Nov.), 841-848.
• 79: Kai Hwang, Advanced Computer Architecture: Parallelism,Scalability,Programmability, McGraw-Hill Higher Education, 1992
• 80: Jing-Jang Hwang , Yuan-Chieh Chow , Frank D. Anger , Chung-Yee Lee, Scheduling precedence graphs in systems with interprocessor communication times, SIAM Journal on Computing, v.18 n.2, p.244-257, April 1989 [doi>10.1137/0218016]
• 81: INTEL SUPERCOMPUTER SYSTEMS DIVISION. 1991. iPSC/2 and iPSC/860 Interactive Parallel Debugger Manual.
• 82: K. K. Jain , V. Rajaraman, Lower and Upper Bounds on Time for Multiprocessor Optimal Schedules, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.879-886, August 1994 [doi>10.1109/71.298216]
• 83: Kamal Kumar Jain , V. Rajaraman, Improved lower bounds on time and processors for scheduling precedence graphs on multicomputer systems, Journal of Parallel and Distributed Computing, v.28 n.1, p.101-108, July 1995 [doi>10.1006/jpdc.1995.1092]
• 84: JIANG, H., BHUYAN, L. N., AND GHOSAL, D. 1990. Approximate analysis of multiprocessing task graphs. In Proceedings of the International Conference on Parallel Processing (Aug.), 228-235.
• 85: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 86: Richard M. Karp, An introduction to randomized algorithms, Discrete Applied Mathematics, v.34 n.1-3, p.165-201, Nov. 1991 [doi>10.1016/0166-218X(91)90086-C]
• 87: KASAHARA, H. AND NARITA, S. 1984. Practical multiprocessor scheduling algorithms for efficient parallel processing. IEEE Trans. Comput. C-33, 11 (Nov.), 1023-1029.
• 88: KAUFMAN, M. 1974. An almost-optimal algorithm for the assembly line scheduling problem. IEEE Trans. Comput. C-23, 11 (Nov.), 1169- 1174.
• 89: KHAN, A., MCCREARY, C. L., AND JONES, M. S. 1994. A comparison of multiprocessor scheduling heuristics. In Proceedings of the 1994 International Conference on Parallel Processing, CRC Press, Inc., Boca Raton, FL, 243- 250.
• 90: KIM, S. J. AND BROWNE, J. C. 1988. A general approach to mapping of parallel computation upon multiprocessor architectures. In Proceedings of International Conference on Parallel Processing (Aug.), 1-8.
• 91: Dongseung Kim , Byung-Guoen Yi, A two-pass scheduling algorithm for parallel programs, Parallel Computing, v.20 n.6, p.869-885, June 1994 [doi>10.1016/0167-8191(94)90121-X]
• 92: KOHLER, W.H. 1975. A preliminary evaluation of the critical path method for scheduling tasks on multiprocessor systems. IEEE Trans. Comput. C-24, 12 (Dec.), 1235-1238.
• 93: Walter H. Kohler , Kenneth Steiglitz, Characterization and Theoretical Comparison of Branch-and-Bound Algorithms for Permutation Problems, Journal of the ACM (JACM), v.21 n.1, p.140-156, Jan. 1974 [doi>10.1145/321796.321808]
• 94: KON'YA, S. AND SATOH, T. 1993. Task scheduling on a hypercube with link contentions. In Proceedings of International Parallel Processing Symposium (Apr.), 363-368.
• 95: KRUATRACHUE, B. AND LEWIS, T. G. 1987. Duplication Scheduling Heuristics (DSH): A New Precedence Task Scheduler for Parallel Processor Systems. Oregon State University, Corvallis, OR.
• 96: Boontee Kruatrachue , Ted Lewis, Grain Size Determination for Parallel Processing, IEEE Software, v.5 n.1, p.23-32, January 1988 [doi>10.1109/52.1991]
• 97: Vipin Kumar , Ananth Grama , Anshul Gupta , George Karypis, Introduction to parallel computing: design and analysis of algorithms, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1994
• 98: Yu-Kwong Kwok , Ishfaq Ahmad, High-performance algorithms of compile-time scheduling of parallel processors, 1997
• 99: Yu-Kwong Kwok , I. Ahmad, Bubble scheduling: A quasi dynamic algorithm for static allocation of tasks to parallel architectures, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.36, October 25-28, 1995
• 100: Yu-Kwong Kwok , Ishfaq Ahmad, Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.506-521, May 1996 [doi>10.1109/71.503776]
• 101: Yu-Kwong Kwok , Ishfaq Ahmad, Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm, Journal of Parallel and Distributed Computing, v.47 n.1, p.58-77, Nov. 25, 1997 [doi>10.1006/jpdc.1997.1395]
• 102: Yu-Kwong Kwok , Ishfaq Ahmad, FASTEST: A Practical Low-Complexity Algorithm for Compile-Time Assignment of Parallel Programs to Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.147-159, February 1999 [doi>10.1109/71.752781]
• 103: Yu-Kwong Kwok , Ishfaq Ahmad, Benchmarking and comparison of the task graph scheduling algorithms, Journal of Parallel and Distributed Computing, v.59 n.3, p.381-422, Dec. 1999 [doi>10.1006/jpdc.1999.1578]
• 104: (R) FAST: A Low-Complexity Algorithm for Efficient Scheduling of DAGs on Parallel Processors, Proceedings of the Proceedings of the 1996 International Conference on Parallel Processing, p.150, August 12-16, 1996
• 105: S.-Y. Lee , J. K. Aggarwal, A mapping strategy for parallel processing, IEEE Transactions on Computers, v.36 n.4, p.433-442, April 1987 [doi>10.1109/TC.1987.1676925]
• 106: B. Lee , A. R. Hurson , T. Y. Feng, A vertically layered allocation scheme for data flow systems, Journal of Parallel and Distributed Computing, v.11 n.3, p.175-187, March 1991 [doi>10.1016/0743-7315(91)90042-8]
• 107: Joseph Y.-T. Leung , Gilbert H. Young, Minimizing schedule length subject to minimum flow time, SIAM Journal on Computing, v.18 n.2, p.314-326, April 1989 [doi>10.1137/0218022]
• 108: Ted Lewis , Hesham El-Rewini, Parallax: A Tool for Parallel Program Scheduling, IEEE Parallel & Distributed Technology: Systems & Technology, v.1 n.2, p.62-72, May 1993 [doi>10.1109/88.218176]
• 109: LIOU, J.-C. AND PALIS, M.A. 1996. An efficient task clustering heuristic for scheduling DAGs on multiprocessors. In Workshop on Resource Management, Symposium on Parallel and Distributed Processing,
• 110: Jing-Chiou Liou , Michael A. Palis, A Comparison of General Approaches to Multiprocessor Scheduling, Proceedings of the 11th International Symposium on Parallel Processing, p.152-156, April 01-05, 1997
• 111: Lo, V. M. 1992. Temporal communication graphs: Lamport's process-time graphs augmented for the purpose of mapping and scheduling. J. Parallel Distrib. Comput. 16, 4 (Dec.), 378-384.
• 112: Lo, V. M., RAJOPADHYE, S., GUPTA, S., KELDSEN, D., MOHAMED, M. A., NITZBERG, B., TELLE, J. A., AND ZHONG, X. 1991. OREGAMI: Tools for mapping parallel computations to parallel architectures. Int. J. Parallel Program. 20, 3, 237-270.
• 113: R. E. Lord , J. S. Kowalik , S. P. Kumar, Solving Linear Algebraic Equations on an MIMD Computer, Journal of the ACM (JACM), v.30 n.1, p.103-117, Jan. 1983 [doi>10.1145/322358.322366]
• 114: Sathiamoorthy Manoharan , Nigel P. Topham, An assessment of assignment schemes for dependency graphs, Parallel Computing, v.21 n.1, p.85-107, Jan. 1995 [doi>10.1016/0167-8191(94)00066-J]
• 115: MARKENSCOFF, P. AND LI, Y. Y. 1993. Scheduling a computational DAG on a parallel system with communication delays and replication of node execution. In Proceedings of International Parallel Processing Symposium (Apr.), 113-117.
• 116: MASSPAR COMPUTER. 1992. MPPE User's Guide.
• 117: Carolyn McCreary , Helen Gill, Automatic determination of grain size for efficient parallel processing, Communications of the ACM, v.32 n.9, p.1073-1078, Sept. 1989 [doi>10.1145/66451.66454]
• 118: Carolyn McCreary , A. A. Khan , J. J. Thompson , M. E. McArdle, A Comparison of Heuristics for Scheduling DAGs on Multiprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.446-451, April 01, 1994
• 119: MEHDIRATTA, N. AND GHOSE, K. 1994. A bottom-up approach to task scheduling on distributed memory multiprocessor. In Proceedings of the 1994 International Conference on Parallel Processing, CRC Press, Inc., Boca Raton, FL, 151-154.
• 120: Daniel Menascé , Virgílio Almeida, Cost-performance analysis of heterogeneity in supercomputer architectures, Proceedings of the 1990 conference on Supercomputing, p.169-177, October 1990, New York, New York, United States
• 121: MENASC , D. A. AND PORTO, S. C. 1993. Scheduling on heterogeneous message passing architectures. J. Comput. Softw. Eng. 1, 3.
• 122: MENASC , D. A., PORTO, S. C., AND TRIPATHI, S. K. 1994. Static heuristic processor assignment in heterogeneous message passing architectures. Int. J. High Speed Comput. 6, 1 (Mar.), 115-137.
• 123: Daniel A. Menascé , Stella C. S. Porto , Satish K. Tripathi, Processor Assignment in Heterogeneous Parallel Architectures, Proceedings of the 6th International Parallel Processing Symposium, p.186-191, March 01, 1992
• 124: Daniel A. Menascé , Debanjan Saha , Stella C. da Silva Porto , Virgilio A. F. Almeida , Satish K. Tripathi, Static and dynamic processor scheduling disciplines in heterogeneous parallel architectures, Journal of Parallel and Distributed Computing, v.28 n.1, p.1-18, July 1995 [doi>10.1006/jpdc.1995.1085]
• 125: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 126: Michael G. Norman , Peter Thanisch, Models of machines and computation for mapping in multicomputers, ACM Computing Surveys (CSUR), v.25 n.3, p.263-302, Sept. 1993 [doi>10.1145/158439.158908]
• 127: PALIS, M. A., LIOU, J.-C., RAJASEKARAN, S., SHENDE, S., AND WEI, D. S.L. 1995. Online scheduling of dynamic trees. Para. Proc. Lett. 5, 4 (Dec.), 635-646.
• 128: Michael A. Palis , Jing-Chiou Liou , David S. L. Wei, Task Clustering and Scheduling for Distributed Memory Parallel Architectures, IEEE Transactions on Parallel and Distributed Systems, v.7 n.1, p.46-55, January 1996 [doi>10.1109/71.481597]
• 129: Santoshkumar S. Pande , Dharma P. Agrawal , Jon Mauney, A threshold scheduling strategy for Sisal on distributed memory machines, Journal of Parallel and Distributed Computing, v.21 n.2, p.223-236, May 1994 [doi>10.1006/jpdc.1994.1054]
• 130: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 131: Christos H. Papadimitriou , Jeffrey D. Ullman, A communication-time tradeoff, SIAM Journal on Computing, v.16 n.4, p.639-646, Aug. 1987 [doi>10.1137/0216044]
• 132: PAPADIMITRIOU, C. H. AND YANNAKAKIS, M. 1979. Scheduling interval-ordered tasks. SIAM J. Comput. 8, 405-409.
• 133: Christos H. Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, SIAM Journal on Computing, v.19 n.2, p.322-328, April 1990 [doi>10.1137/0219021]
• 134: Daniel Pease , Arif Ghafoor , Ishfaq Ahmad , David L. Andrews , Kamal Foudil-Bey , Thomas E. Karpinski , Mohammad A. Mikki , Mohamed Zerrouki, PAWS: A Performance Evaluation Tool for Parallel Computing Systems, Computer, v.24 n.1, p.18-29, January 1991 [doi>10.1109/2.67190]
• 135: Ira Pramanick , Jon G. Kuhl, An Inherently Parallel Method for Heuristic Problem-Solving: Part I-General Framework, IEEE Transactions on Parallel and Distributed Systems, v.6 n.10, p.1006-1015, October 1995 [doi>10.1109/71.473511]
• 136: PRASTEIN, M. 1987. Precedence-constrained scheduling with minimum time and communication. Master's Thesis. University of Illinois at Urbana-Champaign, Champaign, IL.
• 137: Michael J. Quinn, Parallel computing (2nd ed.): theory and practice, McGraw-Hill, Inc., New York, NY, 1994
• 138: RAMAMOORTHY, C. V., CHANDY, K. M., AND GONZA- LEZ, M.J. 1972. Optimal scheduling strategies in a multiprocessor system. IEEE Trans. Comput. C-21, 2 (Feb.), 137-146.
• 139: V. J. Rayward-Smith, The complexity of preemptive scheduling given interprocessor communication delays, Information Processing Letters, v.25 n.2, p.123-125, 6 May 1987 [doi>10.1016/0020-0190(87)90231-6]
• 140: V. J. Rayward-Smith, UET scheduling with unit interprocessor communication delays, Discrete Applied Mathematics, v.18 n.1, p.55-71, Nov. 1987 [doi>10.1016/0166-218X(87)90042-4]
• 141: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 142: Markus Schwehm , Thomas Walter, Mapping and Scheduling by Genetic Algorithms, Proceedings of the Third Joint International Conference on Vector and Parallel Processing: Parallel Processing, p.832-841, September 06-08, 1994
• 143: C. Selvakumar , C. Siva Ram Murthy, Scheduling Precedence Constrained Task Graphs with Non-Negligible Intertask Communication onto Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.3, p.328-336, March 1994 [doi>10.1109/71.277783]
• 144: SETHI, R. 1976. Scheduling graphs on two processors. SIAM J. Comput. 5, 1 (Mar.), 73- 82.
• 145: SHIRAZI, B., KAVI, K., HURSON, A. R., AND BISWAS, P. 1993. PARSA: A parallel program scheduling and assessment environment. In Proceedings of the International Conference on Parallel Processing, CRC Press, Inc., Boca Raton, FL, 68-72.
• 146: Behrooz Shirazi , Mingfang Wang , Girish Pathak, Analysis and evaluation of heuristic methods for static task scheduling, Journal of Parallel and Distributed Computing, v.10 n.3, p.222-2232, Nov. 1990 [doi>10.1016/0743-7315(90)90014-G]
• 147: Howard Jay Siegel , James B. Armstrong , Daniel W. Watson, Mapping Computer-Vision-Related Tasks onto Reconfigurable Parallel-Processing Systems, Computer, v.25 n.2, p.54-63, February 1992 [doi>10.1109/2.121475]
• 148: Howard Jay Siegel , Henry G. Dietz , John K. Antonio, Software support for heterogeneous computing, ACM Computing Surveys (CSUR), v.28 n.1, p.237-239, March 1996 [doi>10.1145/234313.234411]
• 149: G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993 [doi>10.1109/71.207593]
• 150: G. C. Sih , E. A. Lee, Declustering: A New Multiprocessor Scheduling Technique, IEEE Transactions on Parallel and Distributed Systems, v.4 n.6, p.625-637, June 1993 [doi>10.1109/71.242160]
• 151: Barbara B. Simons , Manfred K. Warmuth, A fast algorithm for multiprocessor scheduling of unit-length jobs, SIAM Journal on Computing, v.18 n.4, p.690-710, Aug. 1989 [doi>10.1137/0218048]
• 152: M. Srinivas , Lalit M. Patnaik, Genetic algorithms: A Survey, Computer, v.27 n.6, p.17-26, June 1994 [doi>10.1109/2.294849]
• 153: STONE, H. S. 1977. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans. Softw. Eng. SE-3, 1 (Jan.), 85- 93.
• 154: Robert T. Sumichrast, Scheduling parallel processors to minimize setup time, Computers and Operations Research, v.14 n.4, p.305-313, Oct. 1987 [doi>10.1016/0305-0548(87)90068-2]
• 155: Robert H. Storer , S. David Wu , Renzo Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Management Science, v.38 n.10, p.1495-1509, Oct. 1992 [doi>10.1287/mnsc.38.10.1495]
• 156: THINKING MACHINES CORPORATION. 1991. PRISM User's Guide. Thinking Machines Corp., Bedford, MA.
• 157: D Towsley, Allocating programs containing branches and loops within a multiple processor system, IEEE Transactions on Software Engineering, v.12 n.10, p.1018-1024, Oct. 1986
• 158: Theodora A. Varvarigou , Vwani P. Roychowdhury , Thomas Kailath , Eugene Lawler, Scheduling In and Out Forests in the Presence of Communication Delays, IEEE Transactions on Parallel and Distributed Systems, v.7 n.10, p.1065-1074, October 1996 [doi>10.1109/71.539738]
• 159: VELTMAN, B., LAGEWEG, B. J., AND LENSTRA, J. K. 1990. Multiprocessor scheduling with communication delays. Parallel Comput. 16, 173-182.
• 160: ULLMAN, J. 1975. NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 384-393.
• 161: WANG, M.-F. 1990. Message routing algorithms for static task scheduling. In Proceedings of the 1990 Symposium on Applied Computing (SAC '90), 276-281.
• 162: Qingzhou Wang , Kam Hoi Cheng, List scheduling of parallel tasks, Information Processing Letters, v.37 n.5, p.291-297, March 14, 1991 [doi>10.1016/0020-0190(91)90222-4]
• 163: WANG, L., SIEGEL, H. J., AND ROYCHOWDHURY, V. P. 1996. A genetic-algorithm-based approach for task matching and scheduling in heterogeneous computing environments. In Proceedings of the '96 Workshop on Heterogeneous Computing, IEEE Computer Society Press, Los Alamitos, CA, 72-85.
• 164: Wing Shing Wong , Robert J. T. Morris, A new approach to choosing initial points in local search, Information Processing Letters, v.30 n.2, p.67-72, January 1989 [doi>10.1016/0020-0190(89)90111-7]
• 165: M. Y. Wu , D. D. Gajski, Hypertool: A Programming Aid for Message-Passing Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.330-343, July 1990 [doi>10.1109/71.80160]
• 166: YANG, C.-Q. AND MILLER, B. P. 1988. Critical path analysis for the execution of parallel and distributed programs. In Proceedings of the 8th International Conference on Distributed Computing Systems (ICDCS '88, Washington, D. C., June), IEEE Computer Society Press, Los Alamitos, CA, 366-373.
• 167: Tao Yang , Apostolos Gerasoulis, List scheduling with and without communication delays, Parallel Computing, v.19 n.12, p.1321-1344, Dec. 1993 [doi>10.1016/0167-8191(93)90079-Z]
• 168: Tao Yang , Apostolos Gerasoulis, PYRROS: static task scheduling and code generation for message passing multiprocessors, Proceedings of the 6th international conference on Supercomputing, p.428-437, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143446]
• 169: T. Yang , A. Gerasoulis, DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.951-967, September 1994 [doi>10.1109/71.308533]
• 170: YANG, J., BIC, L., AND NICOLAU, A. 1993. A mapping strategy for MIMD computers. Int. J. High Speed Comput. 5, 1, 89-103.
• 171: ZHU, Y. AND MCCREARY, C. L. 1992. Optimal and near optimal tree scheduling for parallel systems. In Proceedings of Symposium on Parallel and Distributed Processing, IEEE Computer Society Press, Los Alamitos, CA, 112-119.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking; Scheduling

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
DAG, automatic parallelization, multiprocessors, parallel processing, software tools, static scheduling, task graphs