Modeling communication in parallel algorithms: A fruitful interaction between theory and systems?

Jaswinder Pal Singh, Edward Rothberg, Anoop Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

Recently, several theoretical models of parallel architectures have been proposed to replace the PRAM as the model that is presented to an algorithm designer. A primary focus of the new models is to include the cost of interprocessor communication, which is increasingly important in modern parallel architectures. We argue that modeling the communication costs in the architecture or system is only one part of the problem, The other, and usually much more difficult, part is modeling the communication properties of the algorithm itself, which provides necessary inputs into the architectural model to determine overall complexity. In this context, we make three main points in this paper: (i) It is incomplete to describe communication without regard to its relationship with replication. We propose a description of the communication-replication relationship in terms of the working set hierarchy of an algorithm, (ii) Both inherent communication and the communication- replication relationship can be very difficult to model in irregular, dynamic computations that are crucial in many real-world applications. We present some examples that demonstrate this difficulty, (iii) We believe that substantial leverage can be obtained in this effort from the computer systems community, which can provide a hierarchy of simulation and profiling tools-from abstract to detailed-tailored to the needs of the algorithm designers. We propose an initial set of simulation tools, and we discuss possible future refinements to this set.

Original languageEnglish (US)
Title of host publicationProceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
PublisherAssociation for Computing Machinery, Inc
Pages189-199
Number of pages11
ISBN (Electronic)0897916719, 9780897916714
DOIs
StatePublished - Aug 1 1994
Externally publishedYes
Event6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 - Cape May, United States
Duration: Jun 27 1994Jun 29 1994

Publication series

NameProceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

Other

Other6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
CountryUnited States
CityCape May
Period6/27/946/29/94

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Modeling communication in parallel algorithms: A fruitful interaction between theory and systems?'. Together they form a unique fingerprint.

  • Cite this

    Singh, J. P., Rothberg, E., & Gupta, A. (1994). Modeling communication in parallel algorithms: A fruitful interaction between theory and systems? In Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 (pp. 189-199). (Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994). Association for Computing Machinery, Inc. https://doi.org/10.1145/181014.181329