An optimal upper bound on the minimal completion time in distributed supercomputing

ABSTRACT

We first consider an MIMD multiprocessor configuration with n processors. A parallel program, consisting of n processes, is executed on this system—one process per processor. The program terminates when all processes are completed. Due to synchronizations, processes may be blocked waiting for events in other processes. Associated with the program is a parallel profile vector v¯, index i (1≤i≤n) in this vector indicates the percentage of the total execution time when i processes are executing. We then consider a distributed MIMD supercomputer with k clusters, containing u processors each. The same parallel program, consisting of n processes, is executed on this system. Each process can only be executed by processors in the same cluster. Finding a schedule with minimal completion time in this case is NP-hard. We are interested in the gain of using n processors compared to using k clusters containing u processors each. The gain is defined by the ratio between the minimal completion time using processor clusters and the completion time using a schedule with one process per processor. We present the optimal upper bound for this ratio in the form of an analytical expression in n, v¯, k and u. We also demonstrate how this result can be used when evaluating heuristic scheduling algorithms.

REFERENCES

• 1: G. Anderson, An Ada multitasking solution for the sieve of Eratosthenes, ACM SIGAda Ada Letters, v.VIII n.5, p.71-74, Sept./Oct. 1988 [doi>10.1145/51624.51628]
• 2: 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]
• 3: E.G. Coffman Jr., M. R. Garey and D. S. Johnson, An Application of Bin Packing to Multiprocessor Scheduling, SIAM Journal of Computing, Vol. 7, No. 1, February 1978, pp. 1-17.
• 4: R.L. Graham, Bounds on Multiprocessor Timing Anomalies, SIAM Journal of Applied Mathematics, 17, 2 (1969), pp 416-429.
• 5: D.K. Friesen, Tighter bounds for the multifit processor scheduling algorithm, SIAM Journal of Computing, 13 (1984), pp. 170-181.
• 6: M. Garey and D. Johnson, Computers and Intractability, W.H. Freeman and Company, 1979.
• 7: Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
• 8: Michael Allen Langston, Processor scheduling with improved heuristic algorithms, 1981
• 9: Hakan Lennerstad , Lars Lundberg, An Optimal Execution Time Estimate of Static versus Dynamic Allocation in Multiprocessor Systems, SIAM Journal on Computing, v.24 n.4, p.751-764, Aug. 1995 [doi>10.1137/S0097539792240571]
• 10: Lars Lundberg, Predicting the speedup of parallel Ada programs, Proceedings of the 11th Ada-Europe international conference on Ada: moving towards 2000, p.257-274, January 1992, Zandvoort, The Netherlands
• 11: H.S. Stone, Multiprocessor Scheduling with the Aid of Network Flow Algorithms, IEEE Transactions on Software Engineering, Vol. SE-3, No. 1. January 1977, pp. 85-93.
• 12: P. Tang , P.-C. Yew , C.-Q. Zhu, Impact of self-scheduling order on performance on multiprocessor systems, Proceedings of the 2nd international conference on Supercomputing, p.593-603, June 1988, St. Malo, France [doi>10.1145/55364.55422]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.1 Large and Medium ("Mainframe") Computers
          Subjects: Super (very large) computers

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Design, Measurement, Performance, Theory