TY - GEN
T1 - Modeling communication in parallel algorithms
T2 - 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
AU - Singh, Jaswinder Pal
AU - Rothberg, Edward
AU - Gupta, Anoop
N1 - Publisher Copyright:
© 1994 ACM.
PY - 1994/8/1
Y1 - 1994/8/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84973240059&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84973240059&partnerID=8YFLogxK
U2 - 10.1145/181014.181329
DO - 10.1145/181014.181329
M3 - Conference contribution
AN - SCOPUS:84973240059
T3 - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
SP - 189
EP - 199
BT - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
PB - Association for Computing Machinery, Inc
Y2 - 27 June 1994 through 29 June 1994
ER -