LogGPS: a parallel computational model for synchronization analysis

ABSTRACT

We present a new parallel computational model, named LogGPS, which captures synchronization.The LogGPS model is an extension of the LogGP model, which abstracts communication on parallel platforms. Although the LogGP model captures long messages with one bandwidth parameter (G), it does not capture synchronization that is needed before sending a long message by high-level communication libraries. Our model has one additional parameter, S, defined as the threshold for message length, above which synchronous messages are sent.We also present some experimental results using both models. The results include (1) a verification of the LogGPS model, (2) an example of synchronization analysis using an MPI program and (3) a comparison of the models. The results indicate that the LogGPS model is more accurate than the LogGP model, and analyzing synchronization costs is important when improving parallel program performance.

REFERENCES

• 1: K. Al-Tawil and C. A. Moritz. LogGP Quantified: The Case for MPI. In Proc. 7th IEEE International Symp. on High Performance Distributed Computing (HPDC-7), Chicago, IL, August 1998.
• 2: Albert Alexandrov , Mihai F. Ionescu , Klaus E. Schauser , Chris Scheiman, LogGP: incorporating long messages into the LogP model—one step closer towards a realistic model for parallel computation, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.95-105, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215427]
• 3: Nanette J. Boden , Danny Cohen , Robert E. Felderman , Alan E. Kulawik , Charles L. Seitz , Jakov N. Seizovic , Wen-King Su, Myrinet: A Gigabit-per-Second Local Area Network, IEEE Micro, v.15 n.1, p.29-36, February 1995 [doi>10.1109/40.342015]
• 4: G. Burns, R. Daoud, and J. Vaigl. LAM: An Open Cluster Environment for MPI. In In Proc. of Supercomputing Symposium '94 (SS'94), pages 379-386, Toronto, June 1994. available from http://www.mpi.nd.edu/lam/.
• 5: David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
• 6: Andrea C. Dusseau , David E. Culler , Klaus Erik Schauser , Richard P. Martin, Fast Parallel Sorting Under LogP: Experience with the CM-5, IEEE Transactions on Parallel and Distributed Systems, v.7 n.8, p.791-805, August 1996 [doi>10.1109/71.532111]
• 7: William Gropp , Ewing Lusk , Nathan Doss , Anthony Skjellum, A high-performance, portable implementation of the MPI message passing interface standard, Parallel Computing, v.22 n.6, p.789-828, Sept. 1996 [doi>10.1016/0167-8191(96)00024-5]
• 8: M. Homewood and M. McLaren. Meiko CS-2 interconnect elan - elite design. In Proc. IEEE Hot Interconnects '93 Symp., pages 95-105, August 1993.
• 9: IBM Corp. IBM Parallel Enviroment for AIX, MPL Programming and Subroutine Reference, Document Number GC23-3893-00, 1995.
• 10: IBM Corp. IBM Parallel Enviroment (PE), http://www.rs6000.ibm.com/software/sp products/ pe.html, 2000.
• 11: Y. Kanoh, M. Nakamura, T. Hirose, T. Hosomi, and T. Nakata. User-level Network Interface for a Parallel Computer Cenju-4. Trans. of Information Processing Society of Japan, 41(5):1379-1389, 1999.
• 12: Thilo Kielmann , Henri E. Bal , Kees Verstoep, Fast Measurement of LogP Parameters for Message Passing Platforms, Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, p.1176-1183, May 01-05, 2000
• 13: Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. International Journal of Supercomputing Applications, 8(3/4), 1994.
• 14: C. A. Moritz. Cost Modeling and Analysis: Towards Optimal Resource Utilization in Parallel Compuer Systems. PhD thesis, Royal Institute of Technology, Stockholm, 1998.
• 15: Francis O'Carroll , Hiroshi Tezuka , Atsushi Hori , Yutaka Ishikawa, The design and implementation of zero copy MPI using commodity hardware with a high performance network, Proceedings of the 12th international conference on Supercomputing, p.243-250, July 1998, Melbourne, Australia [doi>10.1145/277830.277883]
• 16: Parallel Software Contest (PSC95). http://www.info.waseda.ac.jp/muraoka/project/ psc95/, 1995.
• 17: David Sundaram-Stukel , Mary K. Vernon, Predictive analysis of a wavefront application using LogGP, Proceedings of the seventh ACM SIGPLAN symposium on Principles and practice of parallel programming, p.141-150, May 04-06, 1999, Atlanta, Georgia, United States
• 18: O. Tatebe. Software, http://phase.etl.go.jp/ %7etatebe/software/index-j.html, 2000.
• 19: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia

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.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Synchronization

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

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