Yu-Kwong Kwok
Skip Abstract Section
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.
- ADAM, T. L., CHANDY, K. M., AND DICKSON, J. R. 1974. A comparison of list scheduling for parallel processing systems. Commun. ACM 17, 12 (Dec.), 685-690.]] Google Scholar
Digital Library
- AHMAD, I. AND DHODHI, M. K. 1995. Task assignment using a problem-space genetic algorithm. Concurrency: Pract. Exper. 7, 5 (Aug.), 411-428.]]Google Scholar
- AHMAD, I. AND GHAFOOR, A. 1991. Semi-distributed load balancing for massively parallel multicomputer systems. IEEE Trans. Softw. Eng. 17, 10 (Oct. 1991), 987-1004.]] Google ScholarDigital Library
- AHMAD, I. AND KWOK, Y.-K. 1998a. On exploiting task duplication in parallel program scheduling. IEEE Trans. Parallel Distrib. Syst. 9, 9, 872-892.]] Google ScholarDigital Library
- AHMAD, I. AND KWOK, Y.-K. 1998b. Optimal and near-optimal allocation of precedence-constrained task to parallel processors: Defying the high complexity using effective search technique. In Proceedings of the 1998 International Conference on Parallel Processing (Aug.),]] Google ScholarDigital Library
- AHMAD, I. AND KWOK, Y.-K. 1999. On parallelizing the multiprocessor scheduling problem. IEEE Trans. Parallel Distrib. Syst. 10, 4 (Apr.), 414-432.]] Google ScholarDigital Library
- AHMAD, I., KWOK, Y.-K., AND WU, M.-Y. 1996. Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors. In International Symposium on Parallel Architectures, Algorithms, and Networks (June), 207-213.]] Google ScholarDigital Library
- AHMAD, I., KWOK, Y.-K., WU, M.-Y., AND SHU, W. 1997. Automatic parallelization and scheduling of programs on multiprocessors using CASCH. In Proceedings of the International Conference on Parallel Processing (ICPP, Aug.), 288-291.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- ALI, S., SAIT, S. M., AND BENTEN, M. S.T. 1994. GSA: Scheduling and allocation using genetic algorithm. In Proceedings of the Conference on EURO-DAC'94, 84-89.]] Google ScholarDigital Library
- AL-MOUHAMED, M.A. 1990. Lower bound on the number of processors and time for scheduling precedence graphs with communication costs. IEEE Trans. Softw. Eng. 16, 12 (Dec. 1990), 1390-1401.]] Google ScholarDigital Library
- ALMEIDA, V. A. F., VASCONCELOS, I. M.M., RABE, J. N. C., AND MENASC , D.A. 1992. Using random task graphs to investigate the potential benefits of heterogeneity in parallel systerns. In Proceedings of the 1992 Conference on Supercomputing (Supercomputing '92, Minneapolis, MN, Nov. 16-20), R. Werner, Ed. IEEE Computer Society Press, Los Alamitos, CA, 683-691.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- ANGER, F. D., HWANG, J.-J., AND CHOW, Y.-C. 1990. Scheduling with sufficient loosely coupled processors. J. Parallel Distrib. Comput. 9, 1 (May 1990), 87-92.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- 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.]]Google Scholar
- BECK, M., PINGALI, K., AND NICOLAU, A. 1990. Static scheduling for dynamic dataflow machines. J. Parallel Distrib. Comput. 10, 4 (Dec. 1990), 279-288.]] Google ScholarDigital Library
- BENTEN, M. S. T. AND SAIT, S.M. 1994. Genetic scheduling of task graphs. Int. J. Electron. 77, 4 (Oct.), 401-415.]]Google ScholarCross Ref
- BLAZEWICZ, J., DRABOWSKI, M., AND WEGLARZ, J. 1986. Scheduling multiprocessor tasks to minimize schedule length. IEEE Trans. Comput. C-35, 5 (May 1986), 389-393.]] Google ScholarDigital Library
- BLAZEWICZ, J., WEGLARZ, J., AND DRABOWSKI, M. 1984. Scheduling independent 2-processor tasks to minimize schedule length. Inf. Process. Lett. 18, 5 (June 1984), 267-273.]] Google ScholarDigital Library
- BOKHARI, S.H. 1979. Dual processor scheduling with dynamic reassignment. IEEE Trans. Softw. Eng. SE-5, 4 (July), 341-349.]]Google ScholarDigital Library
- BOKHARI, S.H. 1981. On the mapping problem. IEEE Trans. Comput. C-30, 5, 207-214.]]Google ScholarDigital Library
- BOZOKI, G. AND RICHARD, J.P. 1970. A branchand-bound algorithm for continuous-process task shop scheduling problem. AIIE Trans. 2, 246 -252.]]Google ScholarCross Ref
- BRUNO, J., COFFMAN, E. G., AND SETHI, R. 1974. Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17, 7 (July), 382-387.]] Google ScholarDigital Library
- CASAVANT, T. L. AND KUHL, J.G. 1988. A taxonomy of scheduling in general-purpose distrbuted computing systems. IEEE Trans. Softw. Eng. 14, 2 (Feb.), 141-154.]] Google ScholarDigital Library
- 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.]]Google Scholar
- CHEN, G. AND LAI, T.H. 1988a. Scheduling independent jobs on hypercubes. In Proceedings of the Conference on Theoretical Aspects of Computer Science, 273-280.]] Google ScholarDigital Library
- CHEN, G.-I. AND LAI, T.-H. 1988b. Preemptive scheduling of independent jobs on a hypercube. Inf. Process. Lett. 28, 4 (July 29, 1988), 201- 206.]] Google ScholarDigital Library
- 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.]]Google Scholar
- CHENG, R., GEN, M., AND TSUJIMURA, Y. 1996. A tutorial survey of job-shop scheduling problems using genetic algorithms--I: representation. Comput. Ind. Eng. 30, 4, 983-997.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- 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.]]Google ScholarDigital Library
- CHUNG, Y.-C. AND RANKA, S. 1992. Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors. In Proceedings of the 1992 Conference on Supercomputing (Supercomputing '92, Minneapolis, MN, Nov. 16-20), R. Werner, Ed. IEEE Computer Society Press, Los Alamitos, CA, 512-521.]] Google ScholarDigital Library
- COFFMAN, E.G. 1976. Computer and Job-Shop Scheduling Theory. John Wiley and Sons, Inc., New York, NY.]]Google Scholar
- COFFMAN, E. G. AND GRAHAM, R. L. 1972. Optimal scheduling for two-processor systerns. Acta Inf. 1,200-213.]]Google ScholarDigital Library
- COLIN, J. Y. AND CHRETIENNE, P. 1991. C.P.M. scheduling with small computation delays and task duplication. Oper. Res. 39, 4, 680- 684.]]Google ScholarDigital Library
- COSNARD, M. AND LOI, M. 1995. Automatic task graph generation techniques. Para. Proc. Lett. 5, 4 (Dec.), 527-538.]]Google Scholar
- CRAY RESEARCH, INC. 1991. UNICOS Performance Utilities Reference Manual, SR2040. Cray Supercomputers, Chippewa Falls, MN.]]Google Scholar
- DALLY, W.J. 1992. Virtual-channel flow control. IEEE Trans. Parallel Distrib. Syst. 3, 3 (Mar.), 194-205.]] Google ScholarDigital Library
- DARBHA, S. AND AGARWAL, D. P. 1995. A fast and scalable scheduling algorithm for distrbuted memory systems. In Proceedings of 7th Symposium on Parallel and Distributed Processing (Oct.), 60-63.]] Google ScholarDigital Library
- DAVIS, T., Ed. 1991. The Handbook of Genetic Algorithms. Van Nostrand Reinhold Co., New York, NY.]]Google Scholar
- DE FALCO, I., DEL BALIO, R., AND TARANTINO, E. 1997. An analysis of parallel heuristics for task allocation in multicomputers. Computing 59, 3, 259-275.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- DIGITAL EQUIPMENT CORP. 1992. PARASPHERE User's Guide. Digital Equipment Corp., Maynard, MA.]]Google Scholar
- 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.]]Google Scholar
- Du, g. AND LEUNG, g.Y.-T. 1989. Complexity of scheduling parallel task systems. SIAM J. Discrete Math. 2, 4 (Nov. 1989), 473-487.]] Google ScholarDigital Library
- EL-REWINI, H. AND ALI, H. H. 1995. Static scheduling of conditional branches in parallel programs. J. Parallel Distrib. Comput. 24, 1 (Jan. 1995), 41-54.]] Google ScholarDigital Library
- EL-REWINI, H., ALI, H. H., AND LEWIS, T. G. 1995. Task scheduling in multiprocessor systems. IEEE Computer 28, 12 (Dec.), 27- 37.]] Google ScholarDigital Library
- EL-REWINI, H. AND LEWIS, T. G. 1990. Scheduling parallel program tasks onto arbitrary target machines. J. Parallel Distrib. Comput. 9, 2 (June 1990), 138-153.]] Google ScholarDigital Library
- EL-REWINI, H., LEWIS, T. G., AND ALI, H. H. 1994. Task scheduling in parallel and distributed systems. Prentice-Hall series in innovative technology. Prentice-Hall, Inc., Upper Saddle River, NJ.]] Google ScholarDigital Library
- ERCEGOVAC, M. D. 1988. Heterogeneity in supercomputer architectures. Parallel Comput. 7, 367-372.]]Google ScholarCross Ref
- 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.]]Google ScholarDigital Library
- FERREIRA, A. AND PARDALOS, P., Eds. 1996. Solving Combinatorial Optimization Problems in Parallel: Methods and Techniques. Lecture Notes in Computer Science, vol. 1054.. Springer-Verlag, New York, NY.]] Google ScholarDigital Library
- FILHO, J. L. R., TRELEAVEN, P. C., AND ALIPPI, C. 1994. Genetic-algorithm programming environments. IEEE Computer 27, 6 (June 1994), 28-43.]] Google ScholarDigital Library
- FISHBURN, P. C. 1985. Interval Orders and Interval Graphs. John Wiley and Sons, Inc., New York, NY.]]Google Scholar
- FORREST, S. AND MITCHELL, M. 1993. What makes a problem hard for a genetic algorithm?: some anomalous results and their explanation. Mach. Learn. 13, 2/3 (Nov./Dec. 1993), 285-319.]] Google ScholarDigital Library
- FREUND, R. F. AND SIEGEL, H. J. 1993. Heterogeneous processing. IEEE Computer 26, 6 (June), 13-17.]] Google ScholarDigital Library
- FRIESEN, D. K. 1987. Tighter bounds for LPT scheduling on uniform processors. SIAM J. Comput. 16, 3 (June 1987), 554-560.]] Google ScholarDigital Library
- FuJII, M., KASAMI, T., AND NINOMIYA, K. 1969. Optimal Sequencing of Two Equivalent Processors. SIAM J. Appl. Math. 17, 1.]]Google Scholar
- GABOW, H. 1982. An almost linear algorithm for two-processor scheduling. J. ACM 29, 3 (July), 766-780.]] Google ScholarDigital Library
- GAJSKI, D. D. AND PIER, J. 1985. Essential issues in multiprocessors. IEEE Computer 18, 6 (June).]]Google ScholarDigital Library
- GAREY, M. AND JOHNSON, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., New York, NY.]] Google ScholarDigital Library
- GAREY, M. R., JOHNSON, D., TARJAN, R., AND YAN- NAKAKIS, M. 1983. Scheduling opposing forests. SIAM J. Algebr. Discret. Methods 4, 1, 72-92.]]Google ScholarCross Ref
- 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.]]Google ScholarCross Ref
- GERASOULIS, A. AND YANG, T. 1993. On the granularity and clustering of directed acyclic task graphs. IEEE Trans. Parallel Distrib. Syst. 4, 6 (June), 686-701.]] Google ScholarDigital Library
- GOLDBERG, D. E. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Co., Inc., Redwood City, CA.]] Google ScholarDigital Library
- GONZALEZ, M. J., JR. 1977. Deterministic processor scheduling. ACM Comput. Surv. 9, 3 (Sept.), 173-204.]] Google ScholarDigital Library
- GONZALEZ, T. AND SAHNI, S. 1978. Preemptive scheduling of uniform processor systems. J. ACM 25, 1 (Jan.), 92-101.]] Google ScholarDigital Library
- GRAHAM, R.L. 1966. Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45, 1563-1581.]]Google ScholarCross Ref
- 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.]]Google ScholarCross Ref
- HA, S. AND LEE, E. A. 1991. Compile-time scheduling and assignment of data-flow program graphs with data-dependent iteration. IEEE Trans. Comput. 40, 11 (Nov. 1991), 1225-1238.]] Google ScholarDigital Library
- HANAN, M. AND KURTZBERG, J. 1972. A review of the placement and quadratic assignment problems. SIAM Rev. 14 (Apr.), 324-342.]]Google ScholarDigital Library
- HOCHBAUM, D. S. AND SHMOYS, D. B. 1987. Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 1 (Jan. 1987), 144-162.]] Google ScholarDigital Library
- HOCHBAUM, D. S. AND SHMOYS, D. B. 1988. A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM J. Comput. 17, 3 (June 1988), 539-551.]] Google ScholarDigital Library
- HOLLAND, J. H. 1992. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. 2nd MIT Press, Cambridge, MA.]] Google ScholarDigital Library
- HORVATH, E. C., LAM, S., AND SETHI, R. 1977. A level algorithm for preemptive scheduling. J. ACM 24, 1 (Jan.), 32-43.]] Google ScholarDigital Library
- Hou, E. S. H., ANSARI, N., AND REN, H. 1994. A genetic algorithm for multiprocessor scheduling. IEEE Trans. Parallel Distrib. Syst. 5, 2 (Feb.), 113-120.]] Google ScholarDigital Library
- Hu, T.C. 1961. Parallel sequencing and assembly line problems. Oper. Res. 19, 6 (Nov.), 841-848.]]Google Scholar
- HWANG, K. 1993. Advanced Computer Architecture: Parallelism, Scalability, Programmability. McGraw-Hill, Inc., New York, NY.]] Google ScholarDigital Library
- HWANG, J.-J., CHOW, Y.-C., ANGER, F. D., AND LEE, C.-Y. 1989. Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. 18, 2 (Apr. 1989), 244-257.]] Google ScholarDigital Library
- INTEL SUPERCOMPUTER SYSTEMS DIVISION. 1991. iPSC/2 and iPSC/860 Interactive Parallel Debugger Manual.]]Google Scholar
- JAIN, K. K. AND RAJARMAN, V. 1994. Lower and upper bounds on time for multiprocessor optimal schedules. IEEE Trans. Parallel Distrib. Syst. 5, 8 (Aug.), 879-886.]] Google ScholarDigital Library
- JAIN, K. K. AND RAJARAMAN, V. 1995. Improved lower bounds on time and processors for scheduling precedence graphs on multicomputer systems. J. Parallel Distrib. Comput. 28, 1 (July 1995), 101-108.]] Google ScholarDigital Library
- 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.]]Google Scholar
- JOHNSON, D. S., PAPADIMTRIOU, C. H., AND YANNA- KAKIS, M. 1988. How easy is local search?. J. Comput. Syst. Sci. 37, 1 (Aug. 1988), 79-100.]] Google ScholarDigital Library
- KARP, R.M. 1991. An introduction to randomized algorithms. Discrete Appl. Math. 34, 1-3 (Nov. 1991), 165-201.]] Google ScholarDigital Library
- KASAHARA, H. AND NARITA, S. 1984. Practical multiprocessor scheduling algorithms for efficient parallel processing. IEEE Trans. Comput. C-33, 11 (Nov.), 1023-1029.]]Google ScholarDigital Library
- KAUFMAN, M. 1974. An almost-optimal algorithm for the assembly line scheduling problem. IEEE Trans. Comput. C-23, 11 (Nov.), 1169- 1174.]]Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- 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.]]Google Scholar
- KIM, D. AND YI, B.-G. 1994. A two-pass scheduling algorithm for parallel programs. Parallel Comput. 20, 6 (June 1994), 869-885.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- KOHLER, W. H. AND STEIGLITZ, K. 1974. Characterization and theoretical comparison of branch-and-bound algorithms for permutation problems. J. ACM21, 1 (Jan.), 140-156.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- 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.]]Google Scholar
- KRUATRACHUE, B. AND LEWIS, T.G. 1988. Grain size determination for parallel processing. IEEE Software 5, 1 (Jan.), 23-32.]] Google ScholarDigital Library
- KUMAR, V., GRAMA, A., GUPTA, A., AND KARYPIS, G. 1994. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings, Redwood City, CA.]] Google ScholarDigital Library
- KWOK, Y.-K. 1997. High-performance algorithms for compile-time scheduling of parallel processors. Ph.D. Dissertation. Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong.]] Google ScholarDigital Library
- KWOK, Y.-K. AND AHMAD, I. 1995. Bubble scheduling: A quasi-dynamic algorithm for static allocation of tasks to parallel architectures. In Proceedings of 7th Symposium on Parallel and Distributed Processing (Oct.), 36-43.]] Google ScholarDigital Library
- KWOK, Y.-K. AND AHMAD, I. 1996. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors. IEEE Trans. Parallel Distrib. Syst. 7, 5, 506- 521.]] Google ScholarDigital Library
- KWOK, Y.-K. AND AHMAD, I. 1997. Efficient scheduling of arbitrary task graphs to multiprocessors using a parallel genetic algorithm. J. Parallel Distrib. Comput. 47, 1, 58-77.]] Google ScholarDigital Library
- KWOK, Y.-K. AND AHMAD, I. 1999a. FASTEST: A practical low-complexity algorithm for compile-time assignment of parallel programs to multiprocessors. IEEE Trans. Parallel Distrib. Syst. 10, 2 (Feb.), 147-159.]] Google ScholarDigital Library
- KWOK, Y.-K. AND AHMAD, I. 1999b. Benchmarking and comparison of the task graph scheduling algorithms. J. Parallel Distrib. Comput. 59, 3 (Dec.), 381-422.]] Google ScholarDigital Library
- KWOK, Y.-K., AHMAD, I., AND GU, J. 1996. FAST: A low-complexity algorithm for efficient scheduling of DAGs on parallel processors. In Proceedings of 25th International Conference on Parallel Processing (Aug.), 150-157.]] Google ScholarDigital Library
- LEE, S.-Y. AND AGGARWAL, J. K. 1987. A mapping strategy for parallel processing. IEEE Trans. Comput. C-36, 4 (Apr. 1987), 433-442.]] Google ScholarDigital Library
- LEE, B., HURSON, A. R., AND FENG, T.Y. 1991. A vertically layered allocation scheme for data flow systems. J. Parallel Distrib. Comput. 11, 3 (Mar. 1991), 175-187.]] Google ScholarDigital Library
- LEUNG, J. Y.-T. AND YOUNG, G. H. 1989. Minimizing schedule length subject to minimum flow time. SIAM J. Comput. 18, 2 (Apr. 1989), 314-326.]] Google ScholarDigital Library
- LEWIS, T. G. AND EL-REWINI, H. 1993. Parallax: A tool for parallel program scheduling. IEEE Parallel Distrib. Technol. 1, 2 (May), 64-76.]] Google ScholarDigital Library
- 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,]]Google Scholar
- LIOU, J.-C. AND PALIS, M.A. 1997. A comparison of general approaches to multiprocessor scheduling. In Proceedings of the 11th International Parallel Processing Symposium (Apr.), 152-156.]] Google ScholarDigital Library
- 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.]]Google Scholar
- 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.]]Google ScholarCross Ref
- LORD, R. E., KOWALIK, J. S., AND KUMAR, S. P. 1983. Solving linear algebraic equations on an MIMD computer. J. ACM 30, 1 (Jan.), 103-117.]] Google ScholarDigital Library
- MANOHARAN, S. AND TOPHAM, N. P. 1995. An assessment of assignment schemes for dependency graphs. Parallel Comput. 21, 1 (Jan. 1995), 85-107.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- MASSPAR COMPUTER. 1992. MPPE User's Guide.]]Google Scholar
- MCCREARY, C. AND GILL, H. 1989. Automatic determination of grain size for efficient parallel processing. Commun. ACM 32, 9 (Sept. 1989), 1073-1078.]] Google ScholarDigital Library
- MCCREARY, C., KHAN, A. A., THOMPSON, J. J., AND MCARDLE, M. E. 1994. A comparison of heuristics for scheduling DAG's on multiprocessors. In Proceedings of International Parallel Processing Symposium, 446-451.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- MENASC , D. AND ALMEIDA, V. 1990. Cost-performance analysis of heterogeneity in supercomputer architectures. In Proceedings on Supercomputing '90 (New York, NY, Nov. 12- 16, 1990), J. L. Martin, Ed. IEEE Computer Society Press, Los Alamitos, CA, 169-177.]] Google ScholarDigital Library
- MENASC , D. A. AND PORTO, S. C. 1993. Scheduling on heterogeneous message passing architectures. J. Comput. Softw. Eng. 1, 3.]]Google Scholar
- 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.]]Google Scholar
- MENASC , D. A., PORTO, S. C., AND TRIPATHI, S. K. 1992. Processor assignment in heterogeneous parallel architectures. In Proceedings of International Parallel Processing Symposium.]] Google ScholarDigital Library
- MENASC , D. A., SAHA, D., PORTO, S. C. D. S., ALMEIDA, V. A. F., AND TRIPATHI, S.K. 1995. Static and dynamic processor scheduling disciplines in heterogeneous parallel architectures. J. Parallel Distrib. Comput. 28, 1 (July 1995), 1-18.]] Google ScholarDigital Library
- MOTWANI, R. AND RAGHAVAN, P. 1995. Randomized Algorithms. Cambridge University Press, New York, NY.]] Google ScholarDigital Library
- NORMAN, M. G. AND THANISCH, P. 1993. Models of machines and computation for mapping in multicomputers. ACM Comput. Surv. 25, 3 (Sept. 1993), 263-302.]] Google ScholarDigital Library
- 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.]]Google Scholar
- PALIS, M. A., LIOU, J.-C., AND WEI, D. S. L. 1996. Task clustering and scheduling for distributed memory parallel architectures. IEEE Trans. Parallel Distrib. Syst. 7, 1, 46- 55.]] Google ScholarDigital Library
- PANDE, S. S., AGRAWAL, D. P., AND MAUNEY, J. 1994. A threshold scheduling strategy for Sisal on distributed memory machines. J. Parallel Distrib. Comput. 21, 2 (May 1994), 223-236.]] Google ScholarDigital Library
- PAPADIMITRIOU, C. H. AND STEIGLITZ, K. 1982. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Inc., Upper Saddle River, NJ.]] Google ScholarDigital Library
- PAPADIMITRIOU, C. H. AND ULLMAN, J. D. 1987. A communication-time tradeoff. SIAM J. Comput. 16, 4 (Aug. 1987), 639-646.]] Google ScholarDigital Library
- PAPADIMITRIOU, C. H. AND YANNAKAKIS, M. 1979. Scheduling interval-ordered tasks. SIAM J. Comput. 8, 405-409.]]Google ScholarDigital Library
- PAPADIMITRIOU, C. H. AND YANNAKAKIS, M. 1990. Towards an architecture-independent analysis of parallel algorithms. SIAM J. Comput. 19, 2 (Apr. 1990), 322-328.]] Google ScholarDigital Library
- PEASE, D., GHAFOOR, A., AHMAD, I., ANDREWS, D. L., FOUDIL-BEY, K., KARPINSKI, T. E., MIKKI, M. A., AND ZERROUKI, M. 1991. PAWS: A performance evaluation tool for parallel computing systems. IEEE Computer 24, 1 (Jan. 1991), 18-29.]] Google ScholarDigital Library
- PRAMANICK, I AND KUHL, J. G. 1995. An inherently parallel method for heuristic problemsolving: Part I-General framework. IEEE Trans. Parallel Distrib. Syst. 6, 10 (Oct.), 1006-1015.]] Google ScholarDigital Library
- PRASTEIN, M. 1987. Precedence-constrained scheduling with minimum time and communication. Master's Thesis. University of Illinois at Urbana-Champaign, Champaign, IL.]]Google Scholar
- QUINN, M. J. 1994. Parallel computing (2nd ed.): theory and practice. McGraw-Hill, Inc., New York, NY.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- RAYWARD-SMITH, V.J. 1987a. The complexity of preemptive scheduling given interprocessor communication delays. Inf. Process. Lett. 25, 2 (6 May 1987), 123-125.]] Google ScholarDigital Library
- RAYWARD-SMITH, V. J. 1987b. UET scheduling with unit interprocessor communication delays. Discrete Appl. Math. 18, 1 (Jan. 1987), 55-71.]] Google ScholarDigital Library
- SARKAR, V. 1989. Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press, Cambridge, MA.]] Google ScholarDigital Library
- SCHWEHM, M., WALTER, T., BUCHBERGER, B., AND VOLKERT, J. 1994. Mapping and scheduling by genetic algorithms. In Proceedings of the 3rd Joint International Conference on Vector and Parallel Processing (CONPAR '94), Springer-Verlag, New York, NY, 832- 841.]] Google ScholarDigital Library
- SELVAKUMAR, S. AND MURTHY, C. S. R. 1994. Scheduling precedence constrained task graphs with non-negligible intertask communication onto multiprocessors. IEEE Trans. Parallel Distrib. Syst. 5, 3 (Mar.), 328-336.]] Google ScholarDigital Library
- SETHI, R. 1976. Scheduling graphs on two processors. SIAM J. Comput. 5, 1 (Mar.), 73- 82.]]Google ScholarCross Ref
- 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.]] Google ScholarDigital Library
- SHIRAZI, B., WANG, M., AND PATHAK, G. 1990. Analysis and evaluation of heuristic methods for static task scheduling. J. Parallel Distrib. Comput. 10, 3 (Nov. 1990), 222-232.]] Google ScholarDigital Library
- SIEGEL, H. J., ARMSTRONG, J. B., AND WATSON, D. W. 1992. Mapping computer-vision-related tasks onto reconfigurable parallel-processing systems. IEEE Computer 25, 2 (Feb. 1992), 54-64.]] Google ScholarDigital Library
- SIEGEL, H. J., DIETZ, H. G., AND ANTONIO, J. K. 1996. Software support for heterogeneous computing. ACM Comput. Surv. 28, 1, 237- 239.]] Google ScholarDigital Library
- SIH, G. C. AND LEE, E.A. 1993a. A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures. IEEE Trans. Parallel Distrib. Syst. 4, 2 (Feb.), 75-87.]] Google ScholarDigital Library
- SIH, G. C. AND LEE, E.A. 1993b. Declustering: A new multiprocessor scheduling technique. IEEE Trans. Parallel Distrib. Syst. 4, 6 (June), 625-637.]] Google ScholarDigital Library
- SIMONS, B. B. AND WARMUTH, M.K. 1989. A fast algorithm for multiprocessor scheduling of unit-length jobs. SIAM J. Comput. 18, 4 (Aug. 1989), 690-710.]] Google ScholarDigital Library
- SRINIVAS, M. AND PATNAIK, L.M. 1994. Genetic algorithms: A survey. IEEE Computer 27, 6 (June 1994), 17-26.]] Google ScholarDigital Library
- STONE, H. S. 1977. Multiprocessor scheduling with the aid of network flow algorithms. IEEE Trans. Softw. Eng. SE-3, 1 (Jan.), 85- 93.]]Google ScholarDigital Library
- SUMICHRAST, R. T. 1987. Scheduling parallel processors to minimize setup time. Comput. Oper. Res. 14, 4 (Oct. 1987), 305-313.]] Google ScholarDigital Library
- STORER, R. H., WU, S. D., AND VACCARI, R. 1992. New search spaces for sequencing problems with application to job shop scheduling. Manage. Sci. 38, 10 (Oct. 1992), 1495- 1509.]]Google Scholar
- THINKING MACHINES CORPORATION. 1991. PRISM User's Guide. Thinking Machines Corp., Bedford, MA.]]Google Scholar
- TOWSLEY, D 1986. Allocating programs containing branches and loops within a multiple processor system. IEEE Trans. Softw. Eng. SE- 12, 10 (Oct. 1986), 1018-1024.]] Google ScholarDigital Library
- VARVARIGOU, T. A., ROYCHOWDHURY, V. P., KAILATH, T., AND LAWLER, E. 1996. Scheduling in and out forests in the presence of communication delays. IEEE Trans. Parallel Distrib. Syst. 7, 10, 1065-1074.]] Google ScholarDigital Library
- VELTMAN, B., LAGEWEG, B. J., AND LENSTRA, J. K. 1990. Multiprocessor scheduling with communication delays. Parallel Comput. 16, 173-182.]]Google ScholarCross Ref
- ULLMAN, J. 1975. NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 384-393.]]Google ScholarDigital Library
- WANG, M.-F. 1990. Message routing algorithms for static task scheduling. In Proceedings of the 1990 Symposium on Applied Computing (SAC '90), 276-281.]]Google ScholarCross Ref
- WANG, Q. AND CHENG, K.H. 1991. List scheduling of parallel tasks. Inf. Process. Lett. 37, 5 (Mar. 14, 1991), 291-297.]] Google ScholarDigital Library
- 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.]]Google Scholar
- TONG, W. S. AND MORRIS, R. J.T. 1989. A new approach to choosing initial points in local search. Inf. Process. Lett. 30, 2 (Jan. 1989), 67-72.]] Google ScholarDigital Library
- Wu, M.-Y. AND GAJSKI, D.D. 1990. Hypertool: A programming aid for message-passing systems. IEEE Trans. Parallel Distrib. Syst. 1, 3 (1990), 330-343.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- YANG, T. AND GERASOULIS, A. 1993. List scheduling with and without communication delays. Parallel Comput. 19, 12 (Dec. 1993), 1321- 1344.]] Google ScholarDigital Library
- YANG, T. AND GERASOULIS, A. 1992. PYRROS: Static task scheduling and code generation for message passing multiprocessors. In Proceedings of the 1992 international conference on Supercomputing (ICS '92, Washington, DC, July 19-23, 1992), K. Kennedy and C. D. Polychronopoulos, Eds. ACM Press, New York, NY, 428-437.]] Google ScholarDigital Library
- YANG, T. AND GERASOULIS, A. 1994. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst. 5, 9 (Sept.), 951-967.]] Google ScholarDigital Library
- YANG, J., BIC, L., AND NICOLAU, A. 1993. A mapping strategy for MIMD computers. Int. J. High Speed Comput. 5, 1, 89-103.]]Google ScholarCross Ref
- 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.]]Google ScholarDigital Library
Index Terms
- Static scheduling algorithms for allocating directed task graphs to multiprocessors
Recommendations
Optimal rate-based scheduling on multiprocessors
The PD2 Pfair/ERfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. In this paper, we prove that PD2 is also optimal for scheduling "rate-based" tasks whose processing steps may be ...
Scheduling Aperiodic Tasks Using Total Bandwidth Server on Multiprocessors
EUC '08: Proceedings of the 2008 IEEE/IFIP International Conference on Embedded and Ubiquitous Computing - Volume 01This paper presents real-time scheduling techniques for reducing the response time of aperiodic tasks scheduled with real-time periodic tasks on multiprocessor systems. Two problems are addressed in this paper: (i) the scheduling of aperiodic tasks that ...
The utilization bound of static-priority preemptive partitioned multiprocessor scheduling is 50%
This paper studies static-priority preemptive scheduling on a multiprocessor using partitioned scheduling. We propose a new scheduling algorithm and prove that if the proposed algorithm is used and if less than 50% of the capacity is requested then all ...
Comments