在圖形處理器上之並行極大二分團列舉

Abstract

本論文透過圖形處理器優化極大二分團列舉(Maximal Biclique Enumeration)的執行效能。過往最大二分團列舉之演算法皆採用深度優先搜尋技巧，同時需要大量的遞迴呼叫與集合操作。然而，因為圖形處理器在硬體上的限制，使得深度優先搜尋與遞迴呼叫並不可行，並且圖形處理器上的計憶體限制也使得過往的資料結構，會導致計憶體不足的問題。同時，在解決前述之硬體限制之後，也因為圖形處理器本身高平化度的特性，使得如何平均有效率的將工作量分配給每個執行單元，變成影響效能的最大問題之一。 本研究改寫過往之極大二分團列舉演算法，將遞迴呼叫改為迴圈形式，減緩在圖形處理器上呼叫函式所造成的高負擔；同時，也使用新的資料結構，以解決原集合在圖形處理器上不可用之問題，進而減少了宣告集合對記憶體的需求。後續進一步使用了輕量化候選項選擇、工作竊取等技巧，緩解在圖形處理器上執行緒區塊之間工作量不平衡之情形；並使用平行交集計算與雙層平行計算，進一步利用執行緒區塊內之平行度。在提出極大二分團列舉在圖形處理器上之可能性的同時，提高此問題在圖形處理器上之效能。

Maximal biclique is a crucial property in many applications, such as social network analysis and computational biology. By Maximal Biclique Enumeration (MBE), we can list all the maximal biclique in a given graph and thus extract the insight of it. Alone with the growth of graph size, previous studies have introduced different algorithms to solve the MBE problem with parallelism on CPUs to improve the scalability ; however, to the best of author’s knowledge, the problem has not been implemented on Graphic Processing Unit (GPU). In this study, it aims to improve scalability and runtime of MBE through the parallelism provided by GPUs. First, to successfully migrate the MBE algorithm to the GPUs, it proposes a loop-based algorithm to replace the recursion, and then uses a new data structure to solve the memory explosion problem. Lastly, profiting from the parallelism of GPUs, it develops lightweight candidate selection and work-stealing techniques to alleviates the workload imbalance between thread blocks. Furthermore, it leverages parallel intersection computation and two-level parallelism within each thread block to effectively utilize the inherent parallelism of these blocks.