The Combinatorial BLAS: design, implementation, and applications
The Combinatorial BLAS: design, implementation, and applications
复制标题
DOI：
10.1177/1094342011403516
复制
发表时间：
2011-11-01
影响因子：
3.1
通讯作者：
Gilbert, John R.
中科院分区：
文献类型：
--
作者：
Buluc, Aydin;Gilbert, John R.
本文提出了一个用于图形分析和数据挖掘的可扩展的高性能软件库。大型组合图出现在高性能计算的许多应用中，包括计算生物学、信息学、分析、网络搜索、动力系统和稀疏矩阵方法。由于图计算的不规则性和运算强度低，传统的图计算方法很难实现并行化。然而，许多图计算包含足够的粗粒度并行性，可以用于数千个处理器，这可以通过使用正确的原语来发现。我们描述了并行组合BLAS，它由一组很小但功能强大的线性代数原语组成，专门针对图形和数据挖掘应用。我们提供了可扩展的库接口，并为未来的开发提供了一些指导原则。该库使用两种重要的图形算法进行评估，分别是性能和易用性。使用组合BLAS的示例应用程序的可伸缩性和原始性能在分布式内存集群上是前所未有的。
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.