The Combinatorial BLAS: design, implementation, and applications
Aydın Buluç, John R Gilbert · The International Journal of High Performance Computing Applications · 2011
This paper presents a scalable high-performance software library to be used for graph analysis and data mining. Large combinatorial graphs appear in many applications of high-performance computing, including computational biology, informatics, analytics, web search, dynamical systems, and sparse matrix methods. Graph computations are difficult to parallelize using traditional approaches due to their irregular nature and low operational intensity. Many graph computations, however, contain sufficient coarse-grained parallelism for thousands of processors, which can be uncovered by using the right primitives. We describe the parallel Combinatorial BLAS, which consists of a small but powerful set of linear algebra primitives specifically targeting graph and data mining applications. We provide an extensible library interface and some guiding principles for future development. The library is evaluated using two important graph algorithms, in terms of both performance and ease-of-use. The scalability and raw performance of the example applications, using the Combinatorial BLAS, are unprecedented on distributed memory clusters.
Cited by 415 works. doi:10.1177/1094342011403516
Authors
References
- MapReduce
- Iterative Methods for Sparse Linear Systems
- Basic Linear Algebra Subprograms for Fortran Usage
- A Set of Measures of Centrality Based on Betweenness
- A Bridging Model for Parallel Computation
- A Multigrid Tutorial, Second Edition
- A faster algorithm for betweenness centrality*
- On understanding types, data abstraction, and polymorphism
- Pregel
- The Landscape of Parallel Computing Research: A View from Berkeley