Home Publications all years 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 theses techreports presentations edited volumes conferences Awards Research Teaching BLOG Miscellaneous Full CV [pdf]
Events

Past Events
|
Publications of Torsten Hoefler
Copyright Notice:
The documents distributed by this server have been provided by the
contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a noncommercial basis. Copyright and all
rights therein are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by each
author's copyright. These works may not be reposted without the explicit
permission of the copyright holder.
T. Hoefler, C. Siebert and A. Lumsdaine:
| | Scalable Communication Protocols for Dynamic Sparse Data Exchange
(In Proceedings of the 2010 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'10), presented in Bangalore, India, pages 159--168, ACM, ISBN: 978-1-60558-708-0, Jan. 2010)
AbstractMany 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.
ACM Stats
Documentsdownload article:  download slides:  | | BibTeX | @inproceedings{hoefler-dsde, author={T. Hoefler and C. Siebert and A. Lumsdaine}, title={{Scalable Communication Protocols for Dynamic Sparse Data Exchange}}, year={2010}, month={Jan.}, pages={159--168}, booktitle={Proceedings of the 2010 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP'10)}, location={Bangalore, India}, publisher={ACM}, isbn={978-1-60558-708-0}, source={http://www.unixer.de/~htor/publications/}, } |
|
|