論文題目：Segmented Merge: A New Primitive for Parallel Sparse Matrix Computations

發表會議：The 17th Annual IFIP International Conference on Network and Parallel Computing (CCF C類會議)

作者列表

1) 戢昊男 中國石油大學(北京) 信息科學與工程學院 計算機科學與技術專業 研20級

2) 盧世博 中國石油大學(北京) 信息科學與工程學院 計算機科學與技術專業 本16級

3) 侯凱希 美國弗吉尼亞理工大學

4) 汪 浩 美國俄亥俄州立大學

5) 劉偉峰 中國石油大學(北京) 信息科學與工程學院 計算機科學與技術系

6) Brian Vinter 丹麥奧胡斯大學

文章摘要

本文提出了一個被稱為分段合并的新的并行原語，實現了從q個有序子段到p個主段的并行合并。這q個子段的長度和主段中包含子段的數目都可以是不同的。我們的主要思想是確定一個線程所處理的元素數目，并以二叉樹的形式將同一段中的子段合并，直到每個段內只剩一個子段。這種操作可以被廣泛的應用于稀疏矩陣的處理中，以解決其中非規則性導致的負載不均衡問題。在兩個NVIDIA Turing GPU(RTX 2080和Titan RTX)上進行測試的表明，與NVIDIA cuSPARSE庫相比，我們的算法使稀疏矩陣轉置(SpTRANS)和稀疏矩陣乘法(SpGEMM)運算的性能分別提高了3.94和2.89倍。

背景與動機

隨著分段排序、分段掃描、分段求和等并行分段原語的提出和這些分段原語在并行不規則稀疏矩陣算法上帶來的良好性能改進，分段操作受到了研究人員的廣泛關注。然而盡管合并算法是計算機科學重要的基礎算法之一，分段合并卻還沒有受到人們的關注。基于我們對稀疏矩陣操作的觀察，分段合并原語可能在稀疏矩陣轉置(SpTRANS)和稀疏矩陣乘法(SpGEMM)等操作中很有價值。因此，我們在本工作中提出了分段合并原語，并解決了實現并行分段合并操作的兩大挑戰：一是段的長度和子段的長度不均勻導致的負載均衡問題；二是在超大規模并行的圖形處理器(GPU)上向量化問題。

設計與實現

在本文中，我們定義了分段合并原語。

假定我們有一個鍵值對數組S，包含p個段，

(1)

每個段包含q_i 個子段，

(2)

我們可以得到

(3)

每個子段S_i,j 有n_i,j 個已經根據關鍵字排序的鍵值對。我們的分段合并操作就是讓每個段內的所有鍵值對按關鍵字有序排列。

基于這個定義，我們提出了一個并行分段合并算法，其主要思想是通過固定線程處理的元素數量解決負載均衡的問題，并以二叉樹的形式將同一段中的子段兩兩合并，直到所有子段合并完成。該算法包括三個步驟：

(1)數據預處理(4-15行)：首先記錄段和子段的位置，然后為每個線程固定工作量，最后通過運行標準合并路徑算法的分區策略為每個線程收集所處理數據的信息；

(2)使用合并路徑合并每個線程的兩個子序列(16-18行)；單個線程已經包含執行合并操作所需的所有信息，可以有效地合并兩個有序的子段。而子段的合并操作通常由多個線程完成，這些線程通過合并路徑算法進行合并子段。首先，將與線程對應的子段中的數據進行多次比較，以生成用于分割兩個子段的邊界，然后根據目標矩陣，將兩個子段中的數據按照路徑放入輸出序列中，完成合并操作。算法圖中粉紅色虛線框顯示了兩組子段合并的例子。

(3)迭代合并二叉樹上的子段(3-21行)：同一段的每一個子段可視為二叉樹的一個葉節點進行合并，可能需要多次迭代。當段內只有一個子段時，迭代結束，分段合并完成。

下圖展示了使用分段合并算法將八個子段合并為三個有序段的一個例子。

分段合并實例圖

實驗結果

本文在兩個NVIDIA Turning GPU(RTX 2080和Titan RTX)上對SpTRANS和SpGEMM進行了測試，并將它們與NVIDIA 的cuSPARSE v10.2庫中的相應函數進行了比較，數據集從SuiteSparse Matrix Collection中進行選擇。

我們的SpTRANS算法是將CSR格式的矩陣轉置成CSR格式的矩陣。經測試，我們的算法在兩個GPU上對于cuSPARSE算法平均加速比分別達到3.55倍(最高9.64倍)和3.94倍(最高13.09倍)。

SpTRANS實驗： cuSPARSE方法和使用分段合并原語方法在兩個NVIDIA GPU上的比較。x軸表示被測矩陣的密度(非零元數與行數和列數之積的比率)。

SpGEMM算法計算C=AB，其中A、B和C三個矩陣都是稀疏的。我們使用行-行方法，每個處理單元遍歷A行中的非零元，并使用這些值乘以B對應行的所有元素，然后將乘后的元素合并到C的行中。經測試，我們的算法在RTX 2080上，對于cuSPARSE和bhSPARSE算法平均加速比分別達到了2.89x(最高109.15x)和1.26x(最高7.5x)；在Titan RTX上，平均加速分別為2.53倍(高達81.85倍)和1.22倍(最高17.38倍)。

SpGEMM實驗： cuSPARSE方法，bhSPARSE方法和采用分段合并方法在兩個NVIDIA GPU上的比較。x軸是壓縮率，即結果矩陣中中間非零元與非零元的數量之比。

關于作者：

劉偉峰，博士，中國石油大學(北京)信息科學與工程學院教授，院長，歐盟瑪麗居里學者。2002年和2006年于中國石油大學(北京)計算機系獲學士與碩士學位，2006年至2012年在中國石化石油勘探開發研究院歷任助理工程師、工程師和高級研究師，其間主要研究領域為石油地球物理勘探的高性能算法。2016年于丹麥哥本哈根大學獲計算科學博士學位，主要研究方向為高性能稀疏線性代數子程序。他的主要研究興趣為數值線性代數和并行計算，其中尤其關注稀疏矩陣的數據結構、并行算法和軟件。 他的研究工作發表于SC、ICS、PPoPP、ASPLOS、IPDPS、JPDC、FGCS和Parco等重要國際會議和期刊。他還是TPDS、SISC和TKDE等多個重要國際期刊審稿人，也是SC、ICS和ICPP等多個重要國際會議的程序委員會委員。他是IEEE和CCF高級會員以及ACM和SIAM會員。聯系方式：weifeng.liu@cup.edu.cn

99亚洲综合精品