Efficient implementation of scatter-gather operations for large scale graph analytics
Efficient implementation of scatter-gather operations for large scale graph analytics
复制标题
高效实施大规模图形分析的分散-聚集操作
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ilie Gabriel Tanase
中科院分区：
文献类型：
--
作者：
Manoj Kumar;M. Serrano;J. Moreira;P. Pattnaik;William P. Horn;Joefon Jann;Ilie Gabriel Tanase
我们开发了一种方法来改善图分析中使用的稀疏线性代数内核的该高速缓存行为和整体性能。大规模图形处理通常具有低性能，因为它不能有效地使用处理器缓存，导致存储器访问的高延迟。这在图算法的稀疏线性代数公式中尤其如此，其使用众所周知的内核，例如稀疏矩阵向量乘法和稀疏矩阵转置。所提出的方法划分线性代数内核的内部循环，并执行这些分区的迭代在一个独立的顺序的方式。这会产生更友好的缓存访问模式，从而减少缓存未命中并提高性能。我们首先通过一个例子来说明该技术，然后将其推广到多个场景。我们的评估表明，关键计算内核的执行时间减少了2至5倍，当被认为是大型图形。执行时间的大部分改进来自于每指令周期数（CPI）的显著减少，即使执行代码的路径长度增加。
We developed a methodology to improve the cache behavior and overall performance of sparse linear algebra kernels used in graph analytics. Large scale graph processing typically has low performance because it cannot effectively use processor caches, resulting in high-latency for memory accesses. This is particularly true in a sparse linear algebra formulations of graph algorithms, which use well known kernels such as sparse-matrix vector multiply and sparse-matrix transposition. The proposed methodology partitions the inner loops of linear algebra kernels, and executes the iterations over these partitions in an independently ordered manner. This produces more cache-friendly access patterns, which reduce cache misses and improve performance. We first illustrate the technique through an example and then generalize it to multiple scenarios. Our evaluation shows that execution time of key computational kernels is reduced by 2- to 5-fold, when large graphs are considered. Most of the improvement in execution time comes from a significant reduction in cycles-per-instruction (CPI), even as the path length of the executed code increases.