GPU上具擴充性的三角形計數演算法

A Scalable Triangle Counting Algorithm on GPU

鄭雅如(Cheng, Ya Ju)

指導教授 ： 李哲榮

國立清華大學/電機資訊學院/資訊工程學系/碩士(2015年)

摘要

計算一個圖中的三角形個數在社會網路和網路科學中扮演了重要的角色，例如計算集聚係數。因此，一個快速的三角形計數演算法及其實作是網路分析的關鍵。然而不同的三角形計數演算法只在具有某些特定性質(例如密度)的圖中有較好的表現，沒有任何一種演算法及實作方法能夠迅速處理各種不同性質的圖。
在本篇論文中，我們將介紹一個具有可擴充性的GPU三角形計數演算法及其實作方法。這個演算法可以大略分成三個步驟。首先將原圖重新排序，將圖中密度較高和較低的部分區隔開。重新排序不只能讓我們更容易將不同的演算法應用在圖中具有不同特性的部分，也能使各個計算節點達到較平均的負載。再來將排序後的圖分成數個子圖以便平行化及增加演算法的可擴展性。最後在不同的計算節點上解決各個子問題。
我們使用SNAP和DIMACS 10th Graph Challenge內的圖做實驗以評估我們的實作成果。其結果顯示我們的實作方式比直接使用同一種演算法解出整個圖的三角形還要快超過20%。

關鍵字

GPU ； 三角形計數

並列摘要

Triangle counting of a graph plays an important role in social network and network science, such as finding the clustering coefficients. Hence, a fast triangle counting algorithm and imple-mentation is critical for network analysis. However, different triangle counting algorithms only work well on some particular graphs with specific properties, such as density. No single algorithm and implementation can satisfy all kinds of graph.
In this thesis, we introduce a scalable triangle counting algorithm and its implementation on GPU. This algorithm has three steps. First, it reorders the origin graph based on the degree of vertices. Reordering not only makes it easier to apply different algorithms on graphs with dif-ferent properties, but also achieves load balance between the computing nodes. Second, it parti-tions the graph into several sub-graphs for parallelization and scalability. Last, each sub-problem is solved on different computing nodes and the results are merged.
We evaluated our implementation using the graphs from SNAP and DIMACS 10th Graph Challenge. Experimental results show that our implementation is over 20% faster than solving the whole graph with single algorithm.

並列關鍵字

GPU ； triangle counting

參考文獻

[1] T. Schank and D. Wagner, “Finding, Counting and Listing All Triangles in Large Graphs, an Experimental Study,” Experimental and Efficient Algorithms. Springer, 2005, pp. 606–609.

[2] R. D. Luce and A. D. Perry, “A method of matrix analysis of group structure,” in Psychometrika, vol. 14, issue 2, pp. 95-116, 1949

[4] D. J. Watts and S. H. Strogatz, “Collective Dynamics of “Small-World” Networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998

[6] N. Alon, R. Yuster, and U. Zwick, “Finding and counting given length cycles,” Algorithmica, vol. 17, issue 3, pp.209-223, 1997.

[10] C. E. Tsourakakis, “Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws,” In Proceedings of the 2008 Eighth IEEE International Conference on Data Mining (ICDM '08). IEEE Computer Society, 2008