@inproceedings{f4fb62394a654fbfaf579286911b1a1f,
title = "Fast PGAS connected components algorithms",
abstract = "Irregular graph algorithms for distributed-memory systems are hard to implement and optimize. Recent developments in PGAS languages make the implementation of irregular algorithms easier. In this paper we present our study of PRAM-based parallel connected components algorithm implemented in UPC for distributed-memory systems, and discuss optimization techniques for such settings. Our optimized version achieved more than 100 times speedup over the straight-forward implementation. Remarkable speedups are also achieved over the best SMP implementation for the same input. As the memory access patterns of these algorithms are representative of those of many other PRAM algorithms, we expect our techniques applicable to optimizing a wide range of PRAM graph algorithms on distributed-memory machines.",
keywords = "Connected components, Distributed-memory, PRAM, Parallel graph algorithms, UPC",
author = "Guojing Cong and Gheorghe Almasi and Vijay Saraswat",
year = "2009",
doi = "10.1145/1809961.1809979",
language = "English",
isbn = "9781605588360",
series = "ACM International Conference Proceeding Series",
booktitle = "Proceedings of the 3rd Conference on Partitioned Global Address Space (PGAS) Programing Models, PGAS '09",
note = "3rd Conference on Partitioned Global Address Space (PGAS) Programing Models, PGAS '09 ; Conference date: 05-10-2009 Through 08-10-2009",
}