Speedup Graph Processing by Graph Ordering
Speedup Graph Processing by Graph Ordering
复制标题
DOI：
10.1145/2882903.2915220
复制
发表时间：
2016-06
期刊：
影响因子：
--
通讯作者：
Hao Wei;J. Yu;Can Lu;Xuemin Lin
中科院分区：
文献类型：
--
作者：
Hao Wei;J. Yu;Can Lu;Xuemin Lin
CPU缓存性能是影响数据库系统效率的关键问题之一。据报道，在数据库系统中，缓存未命中延迟占执行时间的一半。为了提高CPU缓存性能，有一些研究支持搜索，包括缓存无关树和缓存感知树。在本文中，我们关注的是通过降低不同图算法的CPU缓存未命中率来提高图计算的CPU加速比。处理树的方法不适用于性质复杂的图。在本文中，我们探索了一种通用的加速CPU计算的方法，以便在不改变图算法(实现)和使用的数据结构的情况下，进一步提高图算法的效率。也就是说，我们的目标是设计一个通用的解决方案，而不是针对特定的图算法，也不是针对特定的数据结构。本文研究的方法是图排序，即通过将频繁访问的节点保持在一起来寻找给定图中所有节点之间的最优排列，以最小化CPU缓存未命中率。我们证明了该图排序问题是NP难的，并给出了一个有界逼近的基本算法。为了提高基本算法的时间复杂度，我们进一步提出了一种新的算法，基于一种新的数据结构，采用新的优化技术来降低时间复杂度，提高效率。我们使用8个大型实图和9个有代表性的图算法对我们的方法进行了广泛的实验，并与其他9种可能的图排序(例如由METIS获得的图排序)进行了比较。我们确认，我们的方法可以通过降低CPU缓存未命中率来实现高性能。
The CPU cache performance is one of the key issues to efficiency in database systems. It is reported that cache miss latency takes a half of the execution time in database systems. To improve the CPU cache performance, there are studies to support searching including cache-oblivious, and cache-conscious trees. In this paper, we focus on CPU speedup for graph computing in general by reducing the CPU cache miss ratio for different graph algorithms. The approaches dealing with trees are not applicable to graphs which are complex in nature. In this paper, we explore a general approach to speed up CPU computing, in order to further enhance the efficiency of the graph algorithms without changing the graph algorithms (implementations) and the data structures used. That is, we aim at designing a general solution that is not for a specific graph algorithm, neither for a specific data structure. The approach studied in this work is graph ordering, which is to find the optimal permutation among all nodes in a given graph by keeping nodes that will be frequently accessed together locally, to minimize the CPU cache miss ratio. We prove the graph ordering problem is NP-hard, and give a basic algorithm with a bounded approximation. To improve the time complexity of the basic algorithm, we further propose a new algorithm to reduce the time complexity and improve the efficiency with new optimization techniques based on a new data structure. We conducted extensive experiments to evaluate our approach in comparison with other 9 possible graph orderings (such as the one obtained by METIS) using 8 large real graphs and 9 representative graph algorithms. We confirm that our approach can achieve high performance by reducing the CPU cache miss ratios.