Name
Abstract | ||
|---|---|---|
In all-to-all personalized communication (AAPC), every node of a parallel system sends a potentially unique packet to every other node. AAPC is an important primitive operation for modern parallel compilers, since it is used to redistribute data structures during parallel computations. As an extremely dense communication pattern, AAPC causes congestion in many types of networks and therefore executes very poorly on general purpose, asynchronous message passsing routers.We present and evaluate a network architecture that executes all-to-all communication optimally on a two-dimensional torus. The router combines optimal partitions of the AAPC step with a self-synchronizing switching mechanism integrated into a conventional wormhole router. Optimality is achieved by routing along shortest paths while fully utilizing all links. A simple hardware addition for synchronized message switching can guarantee optimal AAPC routing in many existing network architectures.The flexible communication agent of the iWarp VLSI component allowed us to implement an efficient prototype for the evaluation of the hardware complexity as well as possible software overheads. The measured performance on an 8 × 8 torus exceeded 2 GigaBytes/sec or 80% of the limit set by the raw speed of the interconnects. We make a quantitative comparison of the AAPC router with a conventional message passing system. The potential gain of such a router for larger parallel programs is illustrated with the example of a two-dimensional Fast Fourier Transform. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1145/181014.181427 | SPAA |
Keywords | Field | DocType |
modern parallel compiler,larger parallel program,conventional wormhole router,flexible communication agent,all-to-all personalized communication,all-to-all communication optimally,optimal all-to-all personalized communication,aapc step,optimal aapc routing,dense communication pattern,aapc router,fast fourier transform,data bases,parallel systems,gain,computer networks,computations,newton iteration,switching,data structure,network architecture,limit set,two dimensional,efficiency,lu factorization,shortest path,computer architecture,parallel algorithms,sparse matrices,parallel computer,prototypes,patterns,linear systems,fast fourier transforms,compilers | Asynchronous communication,Parallel algorithm,Computer science,Network packet,Parallel computing,Computer network,Network architecture,Router,iWarp,Very-large-scale integration,Message switching,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-89791-671-9 | 45 | 10.07 |
References | Authors | |
17 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Susan Hinrichs | 1 | 72 | 14.65 |
| Corey Kosak | 2 | 186 | 25.74 |
| David R. O'hallaron | 3 | 1243 | 126.28 |
| Thomas Stricker | 4 | 126 | 20.89 |
| Riichiro Take | 5 | 49 | 12.64 |