Performance prediction of parallel processing systems: the PAMELA methodology

ABSTRACT

In this paper we present a new methodology for the performance prediction of parallel programs on parallel platforms ranging from shared-memory to distributed-memory (vector) machines. The methodology comprises a procedural program and machine specification paradigm based on PAMELA (PerformAnce ModEling LAnguage), along with a performance calculus, called “serialization analysis”. This calculus extends conventional parallel program analysis technology by explicitly accounting for resource contention, yet at the low evaluation cost typical for static techniques. It is shown that, where conventional techniques introduce fundamental errors, predictions from serialization analysis remain realistic. Apart from the merits of the methodology itself, this high reliability/cost ratio makes PAMELA an attractive candidate for compile-time application within the performance prediction hierarchy often found in parallel programming environments.

REFERENCES

• 1: W. Abu-Sufah and A.D. Malony, "Vector processing on the Alliant FX/8 multiprocessor," in Proc. Int. Conf. Parallel Proc., Aug. 1986, pp. 559-566.
• 2: F. Allen , M. Burke , P. Charles , R. Cytron , J. Ferrante, An overview of the PTRAN analysis system for multiprocessing, Proceedings of the 1st International Conference on Supercomputing, p.194-211, March 1988, Athens, Greece
• 3: F. Allen , M. Burke , R. Cytron , J. Ferrante , W. Hsieh, A framework for determining useful parallelism, Proceedings of the 2nd international conference on Supercomputing, p.207-215, June 1988, St. Malo, France [doi>10.1145/55364.55385]
• 4: G.R. Andrews and F.B. Schneider, "Concepts and notations for concurrent programming," Computing Surveys, vol. 266, no. 24, 1987, pp. 132-145.
• 5: M. Annaratone , C. Pommerell , R. Rühl, Interprocessor communication speed and performance in distributed-memory parallel processors, Proceedings of the 16th annual international symposium on Computer architecture, p.315-324, April 1989, Jerusalem, Israel
• 6: Vasanth Balasundaram , Geoffrey Fox , Ken Kennedy , Ulrich Kremer, A static performance estimator to guide data partitioning decisions, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.213-223, April 21-24, 1991, Williamsburg, Virginia, United States
• 7: L. Bomans and D. Roose, "Benchmarking the iPSC/2 hypercube multiprocessor," Concurrency-Practice and Experience, vol. 1, Sept. 1989, pp. 3-18.
• 8: Ingrid Y. Bucher , Margaret L. Simmons, A close look at vector performance of register-to-register vector computers and a new model, ACM SIGMETRICS Performance Evaluation Review, v.15 n.1, p.39-45, May 1987
• 9: D. Calahan, K.D. Cooper, R.T. Hood, K. Kennedy, and L. Torczon, "ParaScope: A parallel programming environment," Int. Journ. of Supercomp. Applic., vol. 4, no. 2, 1988, pp. 84-99.
• 10: Tony Cheung , James E. Smith, A simulation study of the CRAY X-MP memory system, IEEE Transactions on Computers, v.35 n.7, p.613-622, July 1986 [doi>10.1109/TC.1986.1676802]
• 11: O.J. Dahl and K. Nygaard, Simula: A Language for Programming and Description of Discrete Event Systems. Norwegian Computing Center, Oslo, 1967.
• 12: F. Darema, D.A. George, V.A. Norton, and G.F. Pfister, "A single-program-multiple-data computation model for EPEX/FORTRAN," Parallel Computing, vol. 7, 1988, pp. 11-24.
• 13: W. Ewinger, O. Haan, E. Haupenthal, and C. Siemers, "Modelling and measurement of memory access in SIEMENS VP supercomputers," Parallel Computing, vol. 11, 1989, pp. 361-365.
• 14: Kyle Gallivan , William Jalby , Allen Maloney , Harry Wijshoff, Performance prediction of loop constructs on multiprocessor hierarchical-memory systems, Proceedings of the 3rd international conference on Supercomputing, p.433-442, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318891]
• 15: N H Gehani , W D Roome, Concurrent C, Software—Practice & Experience, v.16 n.9, p.821-844, Sept. 1986
• 16: A.J.C. van Gemund, "Performance modeling with PAMELA: An introduction," Tech. Rep. 1-68340- 44(1992)01, Delft University of Technology, Dec. 1992.
• 17: Vincent A. Guarna, Jr. , Dennis Gannon , David Jablonowski , Allen D. Maloney , Yogesh Gaur, Faust: An Integrated Environment for Parallel Programming, IEEE Software, v.6 n.4, p.20-27, July 1989 [doi>10.1109/52.31649]
• 18: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 19: R.W. Hockney and I.J. Curington, "(f1/2): A parameter to characterize memory and communication bottlenecks," Parallel Computing, vol. 10, 1989, pp. 277-286.
• 20: H. Jonkers, "Introduction to probabilistic performance modelling of parallel applications," Tech. Rep. 1-68340- 44(1993)04, Delft University of Technology, Apr. 1993.
• 21: H.F. Jordan, "The Force," in The Characteristics of Parallel Algorithms (L.H. Jamieson, D. Gannon, and R.J. Douglas, eds.), MIT Press, 1987, pp. 395-436.
• 22: Alan H. Karp, Programming for parallelism, Computer, v.20 n.5, p.43-57, May 1987 [doi>10.1109/MC.1987.1663563]
• 23: Alan H. Karp , Robert G. Babb II, A Comparison of 12 Parallel FORTRAN Dialects, IEEE Software, v.5 n.5, p.52-67, September 1988 [doi>10.1109/52.7943]
• 24: C. Koelbel , P. Mehrotra, Compiling Global Name-Space Parallel Loops for Distributed Execution, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.440-451, October 1991 [doi>10.1109/71.97901]
• 25: O. Kolp and H. Mierendorff, "Performance estimations for SUPRENUM systems," Parallel Computing, vol. 7, 1988, pp. 357-366.
• 26: Wolfgang Kreutzer, System simulation programming styles and languages, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 27: B.P. Lester, "A system for computing the speedup of parallel programs," in Proc. Int. Conf. Parallel Proc., Aug. 1986, pp. 145-152.
• 28: Mamoru Maekawa , Arthur E Oldehoeft , Rodney R Oldehoeft, Operation systems: advanced concepts, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1986
• 29: V. W. Mak , S. F. Lundstrom, Predicting Performance of Parallel Computations, IEEE Transactions on Parallel and Distributed Systems, v.1 n.3, p.257-270, July 1990 [doi>10.1109/71.80155]
• 30: Hermann Mierendorff , R. Schwarzwald, LAPAS: A Performance Evaluation Tool for Large Parallel Systems, Architektur von Rechensystemen, Tagungsband, 11. ITG/GI-Fachtagung, p.245-253, March 07-09, 1990
• 31: David A Mundie , David A Fisher, Parallel processing in Ada, Computer, v.19 n.8, p.20-25, Aug. 1986 [doi>10.1109/MC.1986.1663304]
• 32: W Oed , O Lange, Modelling, measurement, and simulation of memory interference in the CRAY X-MP, Parallel Computing, v.3 n.4, p.343-358, Oct. 1986 [doi>10.1016/0167-8191(86)90015-3]
• 33: Edwin M. Paalvast , Arjan J. van Gemund , Henk J. Sips, A method for parallel program generation with an application to the Booster language, Proceedings of the 4th international conference on Supercomputing, p.457-469, June 11-15, 1990, Amsterdam, The Netherlands
• 34: ParaSoft Corporation, EXPRESS user's manual, 1989.
• 35: C.D. Polychronopoulos and U. Banerjee, "Speedup bounds and processor allocation for parallel programs on multiprocessors," in Proc. Int. Conf. Parallel Proc., Aug. 1986, pp. 961-968.
• 36: C.D. Polychronopoulos, M. Girkar, M.R. Haghighat, C.L. Lee, B. Leung, and D. Schouten, "Parafrase-2: An environment for parallelizing, partitioning, synchronizing, and scheduling programs on multiprocessors," in Proc. Int. Conf. Parallel Proc., Aug. 1989, vol. II, pp. 39-48.
• 37: Bin Qin , Howard A. Sholl , Reda A. Ammar, Micro Time Cost Analysis of Parallel Computations, IEEE Transactions on Computers, v.40 n.5, p.613-628, May 1991 [doi>10.1109/12.88485]
• 38: Vivek Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors, MIT Press, Cambridge, MA, 1989
• 39: Herb Schwetman, CSIM: a C-based process-oriented simulation language, Proceedings of the 18th conference on Winter simulation, p.387-396, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318464]
• 40: K. So and V.A. Norton, "A speedup analyzer for parallel programs," in Proc. int. Conf. Parallel Proc., Aug. 1987, pp. 653-661.
• 41: B. Stramm and F. Berman, "Predicting the performance of large programs on scalable multicomputers," in Scalable HPC Conference, Apr. 1992, pp. 22-29.
• 42: D. F. Vrsalovic , D. P. Siewiorek , Z. Z. Segall , E. F. Gehringer, Performance Prediction and Calibration for a Class of Multiprocessors, IEEE Transactions on Computers, v.37 n.11, p.1353-1365, November 1988 [doi>10.1109/12.8701]
• 43: K-Y. Wang, "Intelligent program optimization and parallelization for parallel computers," Tech. Rep. CSD- TR 91-030, Purdue University, Apr. 1991.

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES

General Terms:
Algorithms, Design, Languages, Performance