Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, 2010, p.1-11
2010

Details

Autor(en) / Beteiligte
Titel
Fast PGAS Implementation of Distributed Graph Algorithms
Ist Teil von
  • 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis, 2010, p.1-11
Ort / Verlag
IEEE Computer Society
Erscheinungsjahr
2010
Link zum Volltext
Quelle
IEEE Electronic Library (IEL)
Beschreibungen/Notizen
  • Due to the memory intensive workload and the erratic access pattern, irregular graph algorithms are notoriously hard to implement and optimize for high performance on distributed-memory systems. Although the PGAS paradigm proposed recently improves ease of programming, no high performance PGAS implementation of large-scale graph analysis is known. We present the first fast PGAS implementation of graph algorithms for the connected components and minimum spanning tree problems. By improving memory access locality, compared with the naive implementation, our implementation exhibits much better communication efficiency and cache performance on a cluster of SMPs. With additional algorithmic and PGASspecific optimizations, our implementation achieves significant speedups over both the best sequential implementation and the best single-node SMP implementation for large, sparse graphs with more than a billion edges.
Sprache
Englisch
Identifikatoren
ISBN: 9781424475599, 1424475597, 9781424475575, 1424475570
ISSN: 2167-4329
DOI: 10.1109/SC.2010.26
Titel-ID: cdi_acm_primary_1884669

Weiterführende Literatur

Empfehlungen zum selben Thema automatisch vorgeschlagen von bX