Partitioning programs for parallel execution

ABSTRACT

The ability of parallel computers to execute multiple instruction streams (tasks) simultaneously gives rise to the problem of partitioning a program into a set of tasks that can be assigned to different processors. The degree to which parallelism can be exploited, the amount of overhead involved during parallel execution of a program and a number of other factors depend directly on partitioning. A good partitioning scheme must take into account all these factors. In this paper we present algorithms to compute optimal partitions in diverse models of the problem. Both directed and undirected graph representations of a parallel program are considered. For some instances of the problem where practical optimal schemes are not possible we suggest simple and efficient heuristics. Finally, a polynomial time algorithm to compute optimal partitions for chains is given.

REFERENCES

• Bokh88: S. H. Bokhari, Partitioning Problems in Parallel, Pipeline, and Distributed Computing, IEEE Transactions on Computers, v.37 n.1, p.48-57, January 1988 [doi>10.1109/12.75137]
• Coff72: Coffman E. G. Jr., R. L. Graham. Optimal Scheduling on Two Processor Systems, A cta Informat|ca, Vol. 1, No. 3~ 1972.
• Coff78: Coffmaxt E. G. Jr., M. R. Garey, D. S. Johnson. An Application of Bin. Packing to Multiprocessor Scheduling, SIAM J. of Computing, Vol. 7, No. 1, February 78.
• GaJo79: 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
• Grah69: Graham R. L. Bounds on Multiprocessing Timing Anomalies, SIAM J. Appl. Math., Vol. 17, 1969, pp. 263- 269.
• InSC86: B Indurkhya , H S Stone , L Xi-cheng, Optimal partitioning of randomly generated distributed programs, IEEE Transactions on Software Engineering, v.12 n.3, p.483-495, March 1986
• Iqba86: Iqbal M. A. Approximate Algorithms for Partitioning and Assignment Problems ICASE Rap. 86-40, NASA Contractor Rap. 178130
• Nico86: Nicol D. M. Analysis of Optimal Random Program Partitions, ICASE Report No. 86-53, NASA Langley Research Center, August 1086.
• Peir86: J K Peir, Program partitioning and synchronization on multiprocessor systems, University of Illinois, Department of Computer Science, Urbana, IL, 1986
• Poly86: Polychronopoulos C. D. On Program Restructuring, Scheduling and Communication for Parallel Processor Systems, Center for Supercomputing Research and Development Research and Development, Rep. No. 595, August 1986.
• 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 [doi>10.1109/TC.1987.5009495]
• Sark87: Sarkar V. Partitioning and Scheduling Parallel Programs for Ezecution on Multiprocessors, Technical Report No. CSL-TR-87-328, Computer Systems Laboratory, Department of Electrical Engineering and Computer Science, Stan~ord University, April 1987.
• Ston77: Stone H. Multiprocessor Scheduling with the Aid of Network Flow Algorithms, IEEE Transactions on Software Engineering, Vol. SE-3, No. 1, January 77, pp. 85-93.

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:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures

General Terms:
Algorithms, Design