An efficient message-passing scheduler based on guided self scheduling

ABSTRACT

While much work has been done to date on the study of task-scheduling schemes for shared memory machines, little of the knowledge gained has been transferred to distributed memory systems. In this paper we discuss the implementation and performance evaluation of various scheduling schemes (which have been widely used on shared memory systems) on the Intel iPSC/2 hypercube. Two benchmarks representing the two ends of the spectrum with respect to task sizes were used to carry out the experiments. The primary goal of this work was to test the performance of guided self-scheduling (GSS) [PoKu87] against other commonly used schemes, and implement an efficient dynamic loop scheduling mechanism on a hypercube. The results suggest that GSS would be a far more efficient and consistent scheduling mechanism for hypercube architectures, and across the range of applications.

REFERENCES

• Alli85: Alliant Computer Systems Corporation. FX/Series Architecture Manual. Acton, MA, 1985.
• Bane88: Utpal K. Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Norwell, MA, 1988
• Brad88: Bradley, D. K. First and Second Generation Hypercube Performance. Master's Thesis, University of Illinois, September 1988.
• CaKe88: Callahan, D. and K. Kennedy. Compiling Programs for Distributed-memory Muttiprocessors. Tech. Report/tRice COMP TR88-74, Rice University, August 1988.
• Cray85: Cray Computer Systems. Multitasking User Guide. Technical Note #SN-0222, January 1985.
• GuMB88: Gustafson, J. L., G. R. Montry, and R. E. Benner. "Development of Parallel Methods for a 1024- Processor Hypercube." SIAM Journal on Scientific and Statistical Computing. July 1988, pp. 609-638.
• Inte88a: Intel Scientific Computers. iPSC/2 C Programmer's Reference Manual. Beaverton, OR, 1988.
• Pier88: P. Pierce, The NX/2 operating system, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.384-390, January 19-20, 1988, Pasadena, California, United States [doi>10.1145/62297.62341]
• Poly88: Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Norwell, MA, 1988
• PoKu87: 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
• Rudo89: Rudolph, D. C. Performance Instrumentation for the Intel iPSCI2. Master's Thesis, University of illinois, May 1989.
• RuRe89: Rudolph, D. C. and D. A. Reed. "CRYSTAL: Operating System Instrumentation for the Intel iPSC/2." Proceedings of the Fourth Conference on Hypercubes, Concurrent Computers, and Applications. Monterey, CA, March 1989.
• Sark87: Sarkar, V. Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors. Tech. report #CSL-DR-87-328, Computer Systems Lab, Stanford University, April 1987.
• Smit81: Smith, B. "Architecture and Applications of the HEP Multiprocessor Computer System." Real Time Processing IV, Proc. of SPIE. 1981, pp. 241-248.
• TaYe86: Tang, P. and P. C. Yew. "Processor Self- Scheduling for Multiple-Nested Parallel Loops." Proceedings of the I986 International Conference on Parallel Processing. August 1986.
• Wolf89: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

  D. Software
  D.3 PROGRAMMING LANGUAGES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Benchmarks

General Terms:
Design, Experimentation, Management, Measurement, Performance, Standardization, Theory