去中心化前沿佇列提升廣度優先搜尋在圖形處理器上的可擴展性

Abstract

圖（Graph）是一種常見的資料結構，在導航、語音辨識和推薦系統等方面具有廣泛的應用。其中，廣度優先搜索（BFS）是探索圖中節點的基本算法，在獲取各種graph性質的方面起著至關重要的作用。圖形處理器（GPU）為常用的硬體加速器，具備卓越的計算能力和存儲容量。現在已有許多BFS演算法被移植到GPU上以提高效能，例如並行BFS（PBFS）演算法。 本研究主要為一種改進傳統PBFS演算法的可擴展性之方法。採用了去中心化前沿佇列（Decentralized Frontier Queue）、即時佇列排空（Real-time Queue Draining）、兩級鄰居訪問（Two-level Neighbor Visiting）及狀態陣列原子掃描（Atomic Status Array Scanning）等設計。這些機制成功緩解GPU上的爭用（Contension）、降低記憶體消耗、解決負載不平衡問題，在實現了具競爭力的運行速度的同時，改進了PBFS演算法在GPU上的可擴展性。本論文介紹了此方法的設計、評估，以及未來改進的方向。

Graph is a common data structure widely used in navigation, speech recognition, and recommendation systems. Breadth-First Search (BFS) is a fundamental algorithm for graph traversal and plays a crucial role in obtaining various graph properties. Graphic Processing Unit (GPU) is a commonly used hardware accelerators with remarkable computing power and storage capacity. Many BFS algorithms have been ported to GPUs to improve performance, such as the Parallel BFS (PBFS) algorithm. This study proposes some approach to improve the scalability of the traditional PBFS algorithm, includes Decentralized Frontier Queue, Real-time Queue Draining, Two-level Neighbor Visiting, and Atomic Status Array Scanning. These mechanism successfully alleviate contention on GPUs, reduce memory consumption, and solve load imbalance issues. We achieved competitive executing speeds and improved the scalability of the PBFS algorithm on GPUs. This thesis shows the design, evaluation, and future works.