A performance evaluation of a general parallel processing model

ABSTRACT

In this paper we analyze a model of a parallel processing system. In our model there is a single queue which is K ≥ 1 identical processors. Jobs are assumed to consist of a sequence of barrier synchronizations where, at each step, the number of tasks that must be synchronized is random with a known distribution. An exact analysis of the model is derived. The model leads to a rich set of results characterizing the performance of parallel processing systems. We show that the number of jobs concurrently in execution, as well as the number of synchronization variables, grows linearly with the load of the system and strongly depends on the average number of parallel tasks found in the workload. Properties of expected response time or such systems are extensively analyzed and, in particular, we report on some non-obvious response time behavior that arises as a function of the variance of parallelism found in the workload. Based on exact response time analysis, we propose a simple calculation that can be used as a rule of thumb to predict speedups. This can be viewed as a generalization of Amdahl's law that includes queueing effects. This generalization is reformulated when precise workloads cannot be characterized, but rather when only the fraction or sequential work and the average number of parallel tasks arc assumed to be known.

REFERENCES

• 1: Virgilio A. F. Almeida , Lawrence W. Dowdy, Performance analysis of a scheme for concurrency/synchronization using queueing network models, International Journal of Parallel Programming, v.15 n.6, p.529-550, December 1, 1986 [doi>10.1007/BF01407412]
• 2: G.M. Amdahl, "Validity of the Siilgle Processor Approach to Achieving |,arge Scale Computing Capabilities", A FII'S Conf. Prec., Vol. 30, Thompson, Washington I).C., pp..t83-,185, 1967.
• 3: F. Baccelli, A.M. Makowski, A. Shwartz, "The Fork-Join queue related systems with synchronization constraints: Stocllastic ordering at~d computable bounds",to appear in Advances in A pplied Probability.
• 4: François Baccelli , William A. Massey , Don Towsley, Acyclic fork-join queuing networks, Journal of the ACM (JACM), v.36 n.3, p.615-642, July 1989 [doi>10.1145/65950.65957]
• 5: F. Baccelli and A. Makowskl, "Q,,e,,eing Modcls {or Systcms with Synchronization Constraints", Proceedings of the I EEE, Vol. 77, No. 1, January 1989.
• 6: lJ. Brocllard, "Scalability, Granularity and Parallelism of Numerical Algorithms", 1BM Research Report RC 14786, June 89.
• 7: F. Darerna-R.ogers, G.F. Pfister and K. So, "Memory Access Patterns of Parallel Scientific Programs", IBM Research Report RC 12086, July 1986.
• 8: D. L. Eager , J. Zahorjan , E. D. Lozowska, Speedup Versus Efficiency in Parallel Systems, IEEE Transactions on Computers, v.38 n.3, p.408-423, March 1989 [doi>10.1109/12.21127]
• 9: John L. Gustafson, Reevaluating Amdahl's law, Communications of the ACM, v.31 n.5, p.532-533, May 1988 [doi>10.1145/42411.42415]
• 10: J. Ilack, "On the Promise of General Purpose Parallel Computing",Parallel Compuling, 10, pp.261-275, 1989.
• 11: I,. Jamieson, Purdue University, personal cornnlunication.
• 12: C. Kim , A. K. Agrawala, Analysis of the Fork-Join Queue, IEEE Transactions on Computers, v.38 n.2, p.250-255, February 1989 [doi>10.1109/12.16501]
• 13: {,. Kleinrock. Queueing Systems, Volume {: Theory, John Wiley, 1976.
• 14: J.D.C. Little, "A Proof of the Queueing Formula L = A t'V", Operations Research, pp. 383- 387, 1961.
• 15: O.M. Lubeck and V. Faber, "Modeling the Performance of l lypercubes: A Case Study using the Particle-ln-Cell Application", Los Alamos National Lab Research Report.
• 16: V.K. Naik and M.L. Patrick, "Data Traffic Reduction Schemes for Cholesky Factorization on Asynchronous Multiprocessor Systems", IBM Research Report RC 14500, March 1989.
• 17: Randolph Nelson , Don Towsley , Asser N. Tantawi, Performance Analysis of Parallel Processing Systems, IEEE Transactions on Software Engineering, v.14 n.4, p.532-540, April 1988 [doi>10.1109/32.4676]
• 18: R. Nelson , A. N. Tantawi, Approximate Analysis of Fork/Join Synchronization in Parallel Queues, IEEE Transactions on Computers, v.37 n.6, p.739-743, June 1988 [doi>10.1109/12.2213]
• 19: M. Neuts, "Matrix Geometric Solutions in Stochastic Models", The Johns Hopkins Press, 198i.
• 20: G.F. Pfistcr and V.A. Norton, "Ilot Spot Contention and Combining in Multistage Interconnectlon Networks", IEEE Trans. on Computers, Vol. C-34, No 10, pp.943-948, Oct. 1985.
• 21: 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
• 22: Harold S. Stone, High-performance computer architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987
• 23: C. G. Rommel , D. Towsley , J. A. Stankovic, Analysis of Fork-Join Jobs Using Processor-Sharing, University of Massachusetts, Amherst, MA, 1987
• 24: Don Towsley , Shou Yu, Bounds for Two Server Fork-Join Queueing Systems, University of Massachusetts, Amherst, MA, 1987

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Parallel processors**
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes; Modeling techniques

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

General Terms:
Performance, Theory