圖形處理器上的平行化快速三角形計數之策略

Abstract

三角形計數 (Triangle Counting) 是圖分析領域中的基本問題，在許多應用中扮 演重要角色，包含社交網路分析，異常行為偵測等等。快速執行三角形計數很重 要，近期許多研究使用具有強大平行處理能力的圖形處理器 (GPU) 加速三角形計 數演算法。然後由於圖資料結構的不規則性，如何設計高效平行化三角形計數演 算法是一個巨大挑戰。本研究針對前人所提出的三角形計數演算法進行深入分析， 觀察到了其雖然在理論上可以將工作量平均分配給各執行緒，達到很高的執行效 率，但實際在圖形處理器上卻遇到性能低落問題。我們根據這些觀察，從圖形處 理器硬體特性的角度出發，提出一個不同的方法，改善了原先的問題，並且在多 個真實世界的圖形資料集上都取得了很好的效果。

Triangle counting is one of the most fundamental problems in the field of graph analysis and plays a pivotal role in various applications such as social network analysis and anomaly detection. Efficient execution of triangle counting is crucial, and recently many studies have leveraged the formidable parallel processing capabilities of Graphics Process- ing Units (GPUs) to accelerate triangle counting algorithms. However, due to the inherent irregularity of graph data structures, designing an effective parallel triangle counting algorithm poses a significant challenge. In this study, we conduct an in-depth analysis of a previously proposed triangle counting algorithm. We observe that, although theoretically, it can distribute the workload evenly among threads to achieve high efficiency, it encounters performance issues when implemented on GPUs. Based on these observations and considering the hardware characteristics of GPUs, we propose an alternative method that addresses the original issues. Our method has demonstrated excellent performance on various real-world graph datasets.