Dynamic partitioning in a transputer environment

ABSTRACT

Parallel programs are characterized by their speedup behavior. As more processors are allocated to a particular parallel program, the program (potentially) executes faster. However, there is often a point of diminishing returns, beyond which extra allocated processors cannot be used effectively. Extra processors would be better utilized by allocating them to another program. Thus, given a set of processors in a multiprocessor system, and a set of parallel programs, a partitioning problem naturally arises which seeks to allocate processors to programs optimally. The problem addressed in this paper is dynamic partitioning. When the number of executable parallel programs changes, the optimal partition sizes also change. To realize the new partition settings, a dynamic repartitioning of all processors is triggered. When extra processors suddenly become available to a running program due to a program departure, or when processors suddenly are taken away from a running program due to a program arrival, a nontrivial repartitioning overhead occurs. Depending upon the specific environment, this overhead cost may negate any potential repartitioning benefit. To gain insight into this dynamic partitioning problem, a specific system, a specific workload, and a specific analytical model are studied. The specific system is an INMOS transputer system consisting of an IIP Vectra front-end, an INMOS B004 evaluation board with a single T414 transputer, and an EB8-10 board with eight T800 transputers. The specific workload consists of parallel versions of a classical N-body problem and a classical search problem. The specific analytical model is a Markov model which is parameterized using the concept of program execution signatures. The sensitivity analysis experiments both validate the model and indicate the characteristics of those workloads which benefit from dynamic partitioning.

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 ]
• Coff76: E.G. Coffman Jr., Ed., Computer and Job- Shop Sehedullng Theory, John Wiley & Sons, New York, 1976.
• DeJo75: K.A. DeJong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Ph.D. Thesis, Department of Computer and Communication Sciences, University of Michigan, 1975.
• Dowd88: L.W. Dowdy, "On the partitioning of multiprocessor systems." Dept. of Computer Sci. Tech. Rep. 88-06, Vanderbilt Univ., Nashville, TN 37035 (Juiy, 19ss).
• Klei75: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• Mill77: F. Miller, Jr., College Physics~ 4th ed., Harcourt, Brace and Janovich Inc., 1977.
• Nico89: David M. Nicol, Optimal Partitioning of Random Programs Across Two Processors, IEEE Transactions on Software Engineering, v.15 n.2, p.134-141, February 1989 [doi>10.1109/32.21740 ]
• NS88: D. M. Nicol , Joel H. Saltz, Dynamic Remapping of Parallel Computations with Varying Resource Demands, IEEE Transactions on Computers, v.37 n.9, p.1073-1087, September 1988 [doi>10.1109/12.2258 ]
• PD89: Kee-Hyun Park , L. Dowdy, Dynamic partitioning of multiprocessor systems, International Journal of Parallel Programming, v.18 n.2, p.91-120, Apr. 1990 [doi>10.1007/BF01491212]
• Seit85: Charles L. Seitz, The cosmic cube, Communications of the ACM, v.28 n.1, p.22-33, Jan. 1985 [doi>10.1145/2465.2467]
• Sevc89: K. C. Sevcik, Characterizations of parallelism in applications and their use in scheduling, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.171-180, May 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.1 PROGRAMMING TECHNIQUES

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