Abstract
The cost of interprocessor communication has a substantial impact on execution time when implementating parallel algorithms on physical parallel computers. We study these implementation costs, examining the number of inter-processor messages, the cost of routing these messages on various architectures, and the number of communication phases. We provide an improved direct routing algorithm for realizing h-relations on crossbar networks. We also introduce a round-robin message-delivery algorithm which reduces the number of times a communication link is established between a pair of processors (by delivering all messages of that phase for the pair in order without interruption.) We summarize criteria sufficient for a parallel algorithm to be implemented optimally on several common networks. We also describe a log n-phase optimal parallel list-ranking algorithm.
| Original language | English |
|---|---|
| Pages (from-to) | 556-562 |
| Journal | IEEE Symposium on Parallel and Distributed Processing - Proceedings |
| DOIs | |
| Publication status | Published - 1995 |
| Externally published | Yes |
| Event | Proceedings of the IEEE 9th International Parallel Processing Symposium - Santa Barbara, CA, USA Duration: 25 Apr 1995 → 28 Apr 1995 |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Fingerprint
Dive into the research topics of 'Efficient routing and message bounds for optimal parallel algorithms'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver