LoGPC: modeling network contention in message-passing programs

ABSTRACT

In many real applications, for example those with frequent and irregular communication patterns or those using large messages, network contention and contention for message processing resources can be a significant part of the total execution time. This paper presents a new cost model, called LoGPC, that extends the LogP [9] and LogGP [4] models to account for the impact of network contention and network interface DMA behavior on the performance of message-passing programs.We validate LoGPC by analyzing three applications implemented with Active Messages [11, 18] on the MIT Alewife multiprocessor. Our analysis shows that network contention accounts for up to 50% of the total execution time. In addition, we show that the impact of communication locality on the communication costs is at most a factor of two on Alewife. Finally, we use the model to identify tradeoffs between synchronous and asynchronous message passing styles.

REFERENCES

• 1: A. Agarwal, Limits on Interconnection Network Performance, IEEE Transactions on Parallel and Distributed Systems, v.2 n.4, p.398-412, October 1991 [doi>10.1109/71.97897]
• 2: Anant Agarwal , Ricardo Bianchini , David Chaiken , Kirk L. Johnson , David Kranz , John Kubiatowicz , Beng-Hong Lim , Kenneth Mackenzie , Donald Yeung, The MIT Alewife machine: architecture and performance, Proceedings of the 22nd annual international symposium on Computer architecture, p.2-13, June 22-24, 1995, S. Margherita Ligure, Italy
• 3: 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]
• 4: 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]
• 5: C. Andras Moritz, K. AI-Tawit, B. Fraguela Rodriguez, "MPI performance comparison on M PP and workstation clusters," appears in l'twc, of the l Oth Int. Conf on Parallel and Distributed Computing, New Orleans, October 1997.
• 6: G. Chochia, C. Boeres, E Thanisch, "Analysis of Multicotnputer Schedules in Cost and Latency Model of Communication", Abstract Machine Workshop, 1996.
• 7: F. Chong , R. Barua , F. Dahlgren , J. Kubiatowicz , A. Agarwal, The Sensitivity of Communication Mechanisms to Bandwidth and Latency, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.37, January 31-February 04, 1998
• 8: A. Krishnamurthy , D. E. Culler , A. Dusseau , S. C. Goldstein , S. Lumetta , T. von Eicken , K. Yelick, Parallel programming in Split-C, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.262-273, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169724]
• 9: 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
• 10: D. Culler, L. Liu, R. Martin, and C. Yoshikawa, "LogP Performance Assessment of Fast Network Interfaces," Technical Report, Computer Science Division, university of California, Berkeley, November 1995, (available on the Web.)
• 11: 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
• 12: Albert G. Greenberg, On the time complexity of broadcast communication schemes (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.354-364, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802211]
• 13: Chris Holt , Mark Heinrich , Jaswinder P Singh , Edward Rothberg , John Hennessy, The Effects of Latency, Occupancy, and Bandwidth in Distributed Shared Memory Multiprocessors, Stanford University, Stanford, CA, 1995
• 14: Matthew I. Frank , Anant Agarwal , Mary K. Vernon, LoPC: modeling contention in parallel algorithms, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.276-287, June 18-21, 1997, Las Vegas, Nevada, United States
• 15: K. Keeton, T. Anderson, and D. Patterson, "LogP Quantified: The Case for Low-Overhead Local Area Networks," Hot Interconnects 111: A Syrup. on High Performance Interconnects, Stanford University, Stanford, CA, Aug. I 0-12, 1995.
• 16: Vijay Karamcheti , Andrew A. Chien, A comparison of architectural support for messaging in the TMC CM-5 and the Cray T3D, Proceedings of the 22nd annual international symposium on Computer architecture, p.298-307, June 22-24, 1995, S. Margherita Ligure, Italy
• 17: C. E Kruskal and M. Snir, "The performance of multistage interconnection networks for multiprocessors," IEEE Trans. Comput., Vol. 37, pp. 1091-1098, Dec 1983.
• 18: K. Mackenzie , J. Kubiatowicz , M. Frank , W Lee , V Lee , A. Agarwal , M. Kaashoek, Exploiting Two-Case Delivery for Fast Protected Messaging, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.231, January 31-February 04, 1998
• 19: N.K. Madsen. "Divergence preserving discrete surface integral methods for Maxwell's curl equations using nonorthogonal unstructured grids", Technical Report 92.04, RIACS, Februaxy 1992.
• 20: Richard P. Martin , Amin M. Vahdat , David E. Culler , Thomas E. Anderson, Effects of communication latency, overhead, and bandwidth in a cluster architecture, Proceedings of the 24th annual international symposium on Computer architecture, p.85-97, June 01-04, 1997, Denver, Colorado, United States
• 21: Christos H. Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, SIAM Journal on Computing, v.19 n.2, p.322-328, April 1990 [doi>10.1137/0219021]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Performance