[發明專利]一種GPU上的基于warp重用與著色分區的強連通圖檢測方法

有效

• 申請號: 202010403115.0
• 申請日: 2020-05-13
• 公開（公告）號: CN111754383B
• 公開（公告）日: 2023-03-10
• 發明（設計）人: 侯駿騰;吳廣君;王樹鵬;王振宇;賈思宇
• 申請（專利權）人: 中國科學院信息工程研究所
• 主分類號: G06T1/20
• 分類號: G06T1/20;G06F9/48;G06F9/50
• 代理公司: 北京君尚知識產權代理有限公司 11200
• 代理人: 陳艷

1.一種GPU上的基于warp重用與著色分區的強連通圖檢測方法，其特征在于，包括以下步驟：

加載圖數據并統一存儲格式，步驟包括：使用壓縮矩陣行的格式存儲數據，根據圖數據的大小為數組C和數組R申請主機內存，將圖數據保存到數組C和數組R中；調換邊的起點和終點，使用上述步驟得到反向的CSR格式圖數據存儲，并保存到數組C’和數組R’中；在GPU設備上申請與主機內存相同的內存空間，并將上述全部數組復制到設備上，在設備內存中申請用于表示頂點狀態的數組M；

對圖數據進行第一類剪枝操作，檢測出只由一個頂點組成的強連通圖1-SCC；

進行第一類中心點選取操作，使用入度和出度的積最大的頂點做為中心點；

使用warp重用方法從中心點開始并行地前向和后向遍歷，步驟包括：按照預設的參數kw將GPU中的每個warp分成若干個等大的虛擬warp，每個虛擬warp包含kw個線程；順次將所有的頂點任務分配給虛擬warp，其中每個虛擬warp分配kv個頂點任務；從中心點開始，并行地在數組R和數據C上進行前向廣度優先遍歷，在數組R’和數據C’上進行后向廣度優先遍歷；在每個虛擬warp中，對于所分配的頂點中需要處理的頂點，所有線程同時并行檢測所分配的頂點中某個需要處理的頂點的鄰接頂點是否已經完成檢測，并將結果標記到數組M中；經過前述的遍歷得到強連通圖和三個分區，其中強連通圖為前向和后向均遍歷到的頂點與中心點形成的連通圖，三個分區為前向遍歷到后向未遍歷到的頂點，前向未遍歷到后向遍歷到的頂點，以及前向和后向均未遍歷到的頂點所形成的分區；每個分區獨立包含其中的所有強連通圖，可相互并行的完成強連通圖檢測；強連通圖和可并行檢測的分區中的頂點在數組M中進行相應標；

判斷是否需要進行第二類剪枝操作，步驟包括：根據預設kt決定是否執行剪枝操作，每進行kt次強連通圖檢測進行一次著色分區；如果kt為0，則不需要進行剪枝操作；如果kt大于0，則需要進行剪枝操作；若需要，則進行第二類剪枝操作，檢測出由一個頂點組成的強連通圖1-SCC和由兩個頂點組成的強連通圖2-SCC；第二類剪枝操作的步驟包括：首先進行多次1-SCC的檢測至無1-SCC產生，然后進行一次2-SCC的檢測，最后進行多次1-SCC的檢測至無1-SCC產生，其中1-SCC的檢測方法與第一類剪枝操作的步驟相同，2-SCC的檢測的步驟包括：并行檢測每一個未被檢測的頂點的鄰接頂點，如果鄰接頂點上存在有向邊連接到當前頂點，并且這兩個點除相互的連接外出度為零或入度為零，則這兩個頂點會組成一個強連通圖，在數組M中對這些頂點進行標記；

使用著色分區方法對所述三個分區進行進一步分區，得到更多更小的分區；

在所形成的小分區中進行第二類中心點選取操作，選取每個分區中初始顏色值與分區顏色值相同的頂點做為中心點，從中心點開始前向遍歷，將遍歷到的頂點與中心點組成一個強連通圖，未被遍歷到的頂點形成新的分區；

進行第三類中心點選取操作，直接在每個分區中隨機選取一個頂點做為中心點，從中心點開始并行地前向和后向遍歷；

再次進行第一類剪枝操作，并更新強連通圖和分區；

判斷是否有新的強連通圖產生，如果沒有新的強連通圖產生，則結束，如果有新的強連通圖產生，則判斷迭代次數是否超過閾值k_t，如果已超過閾值，則使用著色分區方法進行著色分區操作，否則進行第三類中心點選取操作；該著色分區方法的步驟包括：將每個頂點的ID視為該頂點的顏色值，檢測所有未形成強連通圖的頂點的鄰接頂點顏色，如果鄰接頂點顏色小于當前頂點顏色，則修改當前頂點顏色為鄰接頂點顏色，重復以上過程直到所有頂點的顏色值不再變化，根據不同的顏色值將所有未形成強連通圖的頂點分成若干個分區，每個分區獨立包含其中的所有強連通圖。

2.如權利要求1所述的方法，其特征在于，第一類剪枝操作的步驟包括：在GPU上并行檢測每一個頂點的入度和出度，如果頂點的入度為零或出度為零，則該點單獨形成一個1-SCC，在數組M中將該頂點狀態標記為中心點且已完成檢測。

3.如權利要求1所述的方法，其特征在于，第一類中心點選取的步驟包括：在GPU上申請一個用于保存中心點的變量并賦值為0，并行計算中心點和每一個頂點的入度和出度的積，如果當前頂點的入度和出度積大于中心點的入度和出度積，則使用該頂點替換中心點，重復以上過程直到中心點的值不再變化。

4.如權利要求1所述的方法，其特征在于，k_t包括取2。