Scalable communication protocols for dynamic sparse data exchange. Hoefler, T., Siebert, C., & Lumsdaine, A. In Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP, volume 45, pages 159-168, 2010.
Scalable communication protocols for dynamic sparse data exchange [link]Website  doi  abstract   bibtex   
Many large-scale parallel programs follow a bulk synchronous parallel (BSP) structure with distinct computation and communication phases. Although the communication phase in such programs may involve all (or large numbers) of the participating processes, the actual communication operations are usually sparse in nature. As a result, communication phases are typically expressed explicitly using point-to-point communication operations or collective operations. We define the dynamic sparse data-exchange (DSDE) problem and derive bounds in the well known LogGP model. While current approaches work well with static applications, they run into limitations as modern applications grow in scale, and as the problems that are being solved become increasingly irregular and dynamic. To enable the compact and efficient expression of the communication phase, we develop suitable sparse communication protocols for irregular applications at large scale. We discuss different irregular applications and show the sparsity in the communication for real-world input data. We discuss the time and memory complexity of commonly used protocols for the DSDE problem and develop NBX - a novel fast algorithm with constant memory overhead for solving it. Algorithm NBX improves the runtime of a sparse data-exchange among 8,192 processors on BlueGene/P by a factor of 5.6. In an application study, we show improvements of up to a factor of 28.9 for a parallel breadth first search on 8,192 BlueGene/P processors. Copyright © 2010 ACM.
@inproceedings{
 title = {Scalable communication protocols for dynamic sparse data exchange},
 type = {inproceedings},
 year = {2010},
 keywords = {Algorithms,Alltoall,Block codes,Collective operations,Communication,Computati,Computational efficiency,Distributed termi,Distributed termination,Irregular algorithms,Non-blocking,Parallel architectures,Parallel programming,Sparse data},
 pages = {159-168},
 volume = {45},
 issue = {5},
 websites = {https://www.scopus.com/inward/record.uri?eid=2-s2.0-77957567653&doi=10.1145%2F1837853.1693476&partnerID=40&md5=74c0e0b5d4abcbee288a068dc53dbdad,https://www.scopus.com/inward/record.uri?eid=2-s2.0-77749280365&doi=10.1145%2F1693453.1693476&partnerID=40&md5=},
 city = {Bangalore},
 id = {c2a8bd90-406d-3bf4-ad90-335ae55ccbdb},
 created = {2018-01-19T07:02:32.081Z},
 file_attached = {false},
 profile_id = {42d295c0-0737-38d6-8b43-508cab6ea85d},
 last_modified = {2018-03-12T19:03:13.640Z},
 read = {false},
 starred = {false},
 authored = {true},
 confirmed = {true},
 hidden = {false},
 citation_key = {Hoefler2010159},
 source_type = {conference},
 notes = {<b>From Duplicate 1 (<i>Scalable communication protocols for dynamic sparse data exchange</i> - Hoefler, T; Siebert, C; Lumsdaine, A)<br/></b><br/><b>From Duplicate 1 (<i>Scalable communication protocols for dynamic sparse data exchange</i> - Hoefler, T; Siebert, C; Lumsdaine, A)<br/></b><br/>cited By 16<br/><br/><b>From Duplicate 2 (<i>Scalable communication protocols for dynamic sparse data exchange</i> - Hoefler, T; Siebert, C; Lumsdaine, A)<br/></b><br/>cited By 14; Conference of 2010 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'10 ; Conference Date: 9 January 2010 Through 14 January 2010; Conference Code:79501<br/><br/><b>From Duplicate 2 (<i>Scalable communication protocols for dynamic sparse data exchange</i> - Hoefler, T; Siebert, C; Lumsdaine, A)<br/></b><br/>cited By 14; Conference of 2010 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP'10 ; Conference Date: 9 January 2010 Through 14 January 2010; Conference Code:79501},
 folder_uuids = {2aba6c14-9027-4f47-8627-0902e1e2342b},
 private_publication = {false},
 abstract = {Many large-scale parallel programs follow a bulk synchronous parallel (BSP) structure with distinct computation and communication phases. Although the communication phase in such programs may involve all (or large numbers) of the participating processes, the actual communication operations are usually sparse in nature. As a result, communication phases are typically expressed explicitly using point-to-point communication operations or collective operations. We define the dynamic sparse data-exchange (DSDE) problem and derive bounds in the well known LogGP model. While current approaches work well with static applications, they run into limitations as modern applications grow in scale, and as the problems that are being solved become increasingly irregular and dynamic. To enable the compact and efficient expression of the communication phase, we develop suitable sparse communication protocols for irregular applications at large scale. We discuss different irregular applications and show the sparsity in the communication for real-world input data. We discuss the time and memory complexity of commonly used protocols for the DSDE problem and develop NBX - a novel fast algorithm with constant memory overhead for solving it. Algorithm NBX improves the runtime of a sparse data-exchange among 8,192 processors on BlueGene/P by a factor of 5.6. In an application study, we show improvements of up to a factor of 28.9 for a parallel breadth first search on 8,192 BlueGene/P processors. Copyright © 2010 ACM.},
 bibtype = {inproceedings},
 author = {Hoefler, T and Siebert, C and Lumsdaine, A},
 doi = {10.1145/1693453.1693476},
 booktitle = {Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP}
}
Downloads: 0
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021