Combining static and dynamic scheduling on distributed-memory multiprocessors

ABSTRACT

Loops are a large source of parallelism for many numerical applications. An important issue in the parallel execution of loops is how to schedule them so that the workload is well balanced among the processors. Most existing loop scheduling algorithms were designed for shared-memory multiprocessors, with uniform memory access costs. These approaches are not suitable for distributed-memory multiprocessors where data locality is a major concern and communication costs are high. This paper presents a new scheduling algorithm in which data locality is taken into account. Our approach combines both worlds, static and dynamic scheduling, in a two-level (overlapped) fashion. This way data locality is considered and communication costs are limited. The performance of the new algorithm is evaluated on a CM-5 message-passing distributed-memory multiprocessor.

REFERENCES

• BB91: Belkhale, K. P. and Banerjee, P.," A Scheduling Algorithm for Parallelizable Dependent Tasks", in 5th IEEE Int. Parallel Processing Symp., Apr. 1991, pp. 500-506.
• HP93: Mohammad R. Haghighat , Constantine D. Polychronopoulos, Symbolic Analysis: A Basis for Parallelization, Optimization, and Scheduling of Programs, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.567-585, August 12-14, 1993
• HSF92: Susan Flynn Hummel , Edith Schonberg , Lawrence E. Flynn, Factoring: a method for scheduling parallel loops, Communications of the ACM, v.35 n.8, p.90-101, Aug. 1992 [doi>10.1145/135226.135232]
• KW85: Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
• LS93: J. Liu , V. A. Saletore, Self-scheduling on distributed-memory machines, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.814-823, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169841]
• LSL92: Liu, J., Saletore, V. A. and Lewis, T. G., "Scheduling Parallel Loops with Variable Length Iteration Execution Times on Parallel Computers", in ISMM Int. Conf. on Parallel and Distributed Computing Systems, Oct. 1992.
• LTSS93: Li, H., Tandri, S., Stummu, M. and Sevcik, K., "Locality and Loop Scheduling on NUMA Multiprocessors", in IEEE Int. Conf. on Parallel Processing, Aug. 1993, pp. 140-147.
• Luc92: Steven Lucco, A dynamic scheduling method for irregular parallel programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.200-211, June 15-19, 1992, San Francisco, California, United States
• ML94: E. P. Markatos , T. J. LeBlanc, Using Processor Affinity in Loop Scheduling on Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.5 n.4, p.379-400, April 1994 [doi>10.1109/71.273046]
• PK87: C. D. Polychronopoulos , D. J. Kuck, Guided self-scheduling: A practical scheduling scheme for parallel supercomputers, IEEE Transactions on Computers, v.36 n.12, p.1425-1439, Dec. 1987 [doi>10.1109/TC.1987.5009495]
• PKP89: C. D. Polychronopoulos , David J. Kuck , David A. Padua, Utilizing Multidimensional Loop Parallelism on Large Scale Parallel Processor Systems, IEEE Transactions on Computers, v.38 n.9, p.1285-1296, September 1989 [doi>10.1109/12.29467]
• Pol88: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• RP89: David C. Rudolph , Constantine D. Polychronopoulos, An efficient message-passing scheduler based on guided self scheduling, Proceedings of the 3rd international conference on Supercomputing, p.50-61, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318796]
• SH86: Vivek Sarkar , John Hennessy, Compile-time partitioning and scheduling of parallel programs, ACM SIGPLAN Notices, v.21 n.7, p.17-26, July 1986
• SLL93: Saletore, V. A., Liu, J. and Lam, B. Y., "Scheduling Non-Uniform Parallel Loops on Distributed Memory Machines", in IEEE Int. Conf. on System Sciences, Jan. 1993, pp. 516-525.
• TF92: Nadia Tawbi , Paul Feautrier, Processor allocation and loop scheduling on multiprocessor computers, Proceedings of the 6th international conference on Supercomputing, p.63-71, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143387]
• Thi91: Thinking Machines Corporation, Cambridge, MA. The Connection Machine CM-5 Technical Summary, 1991.
• TN93: T. H. Tzen , L. M. Ni, Trapezoid Self-Scheduling: A Practical Scheduling Scheme for Parallel Compilers, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.87-98, January 1993 [doi>10.1109/71.205655]
• TY86: Tang, P. and Yew, P.C., "Processor Self- Scheduling for Multiple Nested Parallel Loops", in IEEE Int. Conf. on Parallel Processing, Aug. 1986, pp. 528-535.
• Zha91: Xiaodong Zhang, Dynamic and static load scheduling performance on a NUMA shared memory multiprocessor, Proceedings of the 5th international conference on Supercomputing, p.128-135, June 17-21, 1991, Cologne, West Germany [doi>10.1145/109025.109062]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Measurement, Performance, Theory

Keywords:
distributed-memory multiprocessors, dynamic and static scheduling, load balancing, loop scheduling, message-passing