一種面向gpu的雙調歸併排序方法

2023-11-02 22:52:42 1

專利名稱：一種面向gpu的雙調歸併排序方法
—種面向GPU的雙調歸併排序方法本發明涉及一種數據排序方法，特別是一種面向GPU的基於OpenCL規範的雙調歸併排序方法。
背景技術：
排序是計算機應用中最常見的操作之一，隨著並行處理技術的進一步發展，並行排序已經成為一個非常重要的研究領域。通常將並行排序分為兩類一類是直接排序，能夠直接實現序列的排序；另一類是歸併排序，即可以將多個有序列快速合併為一個有序列。在現有技術中，大部分的排序方法都需要開闢新的內存空間來存儲排序中間步驟的結果，例如常見的快速排序、基數排序和並行排序算法中的桶排序等。雙調歸併排序方法 能夠直接在待排序列的存儲空間進行數據交換，有效節省了內存開銷。目前AMD的OpenCL軟體開發套件(SDK)中包含了 OpenCL版本的雙調排序方法在GTO上的實現。其雙調排序程序能夠充分利用GPU的流處理器，但是排序中的同步工作完全由CPU部分完成，工作組間的線程同步需要進行上下文的切換，從而影響計算效率。因此，在節省存儲空間的基礎上，如何有效減少CPU和GPU之間的同步次數、減少執行指令的總量和延時、增加GPU計算單元的利用率等是本發明要解決的技術問題。

發明內容
本發明的目的是為了有效減少CPU和GPU之間的同步次數、減少執行指令的總量和延時、增加GPU計算單元的利用率。為了實現上述目的，本發明提供了一種面向GPU的雙調歸併排序方法，包括如下步驟(I)將共享內存中的待排序列數據拷貝到GPU設備局部內存中；(2)判斷是否需要進行向量內排序，若需要則由一個線程操作向量模擬L個比較器，多個線程並行執行歸併排序；(3)將排序結果由GPU設備局部內存拷貝到共享內存中。本發明還提供了一種面向GPU的雙調歸併排序系統，包括如下模塊用於將共享內存中的待排序列數據拷貝到GPU設備局部內存中的模塊；用於判斷是否需要進行向量內排序，若需要則由一個線程操作向量模擬L個比較器，多個線程並行執行歸併排序的模塊；用於將排序結果由GPU設備局部內存拷貝到共享內存中的模塊。本發明的一種優選方案為多個線程並行執行歸併排序時，對於同一個工作組內的線程同步使用同步函數來完成，對於不同工作組內的線程間同步通過CPU完成。本發明的另一優選方案為當一個工作組內的比較器本次和下次操作數都存在於該工作組的局部內存時，使用同步函數同步工作組內線程；當一個工作組內的比較器本次和下次操作數存放在不同的工作組局部內存時，由CPU參與線程的同步。本發明的另一優選方案為由一個線程來模擬LXM個比較器，操作2XM個向量進行比較交換操作，每個線程內向量運算指令順序執行。本發明的另一優選方案為在排序過程中，改變比較器操作數的寫回地址，以使局部內存讀操作的地址連續，同時為防止線程間數據讀寫衝突，設置每個線程將需要操作的數據讀入寄存器再進行比較交換操作。本發明的另一優選方案為在排序一組向量時，若該組向量的前半部分向量不連續，則將該前半部分向量中的後半部與該後半部分向量中的後半部交換位置後，再執行寫回共享內存的操作。本發明的另一優選方案為在排序一組向量時，若該組向量的前半部分向量不連續，後半部分向量連續，則將該前半部分向量中的前半部與該後半部分向量中的前半部交換位置後，再執行寫回共享內存的操作。



圖I為雙調歸併排序網絡的原理圖；圖2為本發明的由CPU端執行的主機程序流程；圖3為本發明的GPU雙調歸併排序方法執行過程。
具體實施例方式下面通過附圖和實施例，對本發明的技術方案做進一步的詳細描述。本發明主要通過以下幾種方式，對現有技術中GPU雙調歸併排序方法做出改進一、使用向量模擬多個比較器在傳統的GPU雙調歸併排序方法中，一條線程作為一個比較器(compare andconditionally interchange),待排序列長度為比較器數的2倍。可以將比較器第一次分組，通過組號即可確定所排列的數據段是按升序還是降序排列，同時可以將比較器二次分組，通過組號能夠得到該比較器操作的序列元素的位置，圖I是擁有4個比較器的雙調歸併排序網絡的簡單原理示意。而在實際應用的測試中發現，僅使用單數據項進行比較的傳統雙調排序方法在運行中算術邏輯單元(ALU)的使用率偏低，為解決該技術問題，本發明提出一種引入向量計算的雙調歸併排序方法，以提高算術邏輯單元的利用率。對2N個數字進行基於標量的雙調歸併排序，需要N個比較器，同步次數為(IgN/lg2+2)*(lgN/lg2+l)/2-l。而使用長度為L的向量，使得一個線程由模擬一個比較器變為模擬L個比較器，在進行雙調歸併排序時，同步次數減少為(2+lgN/lg2-2*lgL/lg2)*(lgN/lg2-2*lgL/lg2+l)/2-l。同時使用向量可以減少線程數，即減少需要執行的指令數。排序同等規模數據時，使用長度為L的向量的指令數為基於標量的指令數的1/L，從而將大大減少計算的時間，提高排序計算的效率。二、向量同步操作優化在GPU運算中線程同步是高開銷的操作，不同的同步方法產生的開銷差別很大。在OpenCL規範中，一個工作組(work-group)內的線程(work_item)同步可以使用同步函數完成，同步過程不需要CPU參與，不涉及上下文(context)切換，因而該同步方法開銷低。而工作組間的線程同步必須通過切換上下文到CPU設備來完成，該同步方法開銷高。若GPU—個工作組內可包含的線程數為ITEMS，使用長度為L的向量進行排序操作，當(N/L>lgITEMS/lg2)時，需要CPU同步的次數為(l+lgN/lg2-2*lgL/lg2-lgITEMS/lg2)*(lgN/lg2-2*lgL/lg2_lgITEMS/lg2)/2 ；而當(N/L〈=lgITEMS/lg2)時，需要CPU同步的次數為0，即完全使用同步函數來進行線程內同步。基於上述分析，為了將同步開銷降到最低，本實施例的方案中混合使用兩種同步方法，當一個工作組內的比較器本次和下次操作數都存在於該工作組的局部內存時，使用同步函數同步工作組內線程；當一個工作組內的比較器本次和下次操作數存放在不同的工作組局部內存時，CPU參與所有線程的同步。三、使用多個向量模擬更大長度向量 由於在GPU運算中，向量指令允許的向量長度有限制，為使單個線程模擬超過最大向量長度數的比較器，可以使用單線程操作2組多個向量實現。使用標量的情況下，一個線程模擬一個比較器操作2個標量進行比較交換；使用L長度的向量情況下，一個線程模擬L個比較器操作2個向量進行比較交換。為使單個線程模擬超過向量指令允許的最大向量長度數的比較器，本實施例的方案中，使用單線程操作2組向量，每組向量中包含多個向量。即L長度向量情況下一個線程模擬L*M個比較器操作2*M個向量進行比較交換。單線程操作2組M個L長度向量，即相當於使用M個L長度向量模擬M*L長度向量，從而增加單個工作組內處理的數據量。對於排序2N個元素，使用M個L長度向量模擬M*L長度向量，與實施例一、二中使用L長度向量相比，在執行相同數量向量運算指令下將(l+2*lgN/lg2-2*lgITEMS/lg2-2*lgM*lg2)*lgM/lg2條需CPU參與的同步轉換為單線程內向量運算指令順序執行所蘊含的隱式同步或同步函數同步，隱式同步的開銷要小於CPU參與的同步和OpenCL同步函數的同步。四、基於向量的局部內存讀操作優化傳統的雙調歸併排序方法中，一組線程進行內存讀操作的地址在大多數情況下是不連續的，當局部內存讀操作的內存地址不連續時將降低緩存命中率、產生額外的bank衝關。由於下次操作的數據位置在本次操作中是能夠計算的，可以通過改變數據寫回地址實現下次局部內存讀操作的地址連續。改變後由於比較器讀操作的內存地址和寫操作的內存地址不一致，為了防止線程間數據讀寫衝突，設置每個線程將需要操作的數據讀入寄存器再進行比較交換操作，在寫回操作前設置同步操作確保所有數據已經被處理。通過對雙調歸併排序的推導，得到如下數據寫回地址換算規則，對CPU和GPU構架均適用。a)設本次數據操作是將兩組m個元素的單調序列歸併為一個2*m個元素的單調序列的一系列操作中的一步，下次數據操作仍然屬於這一系列操作，轉換公式為(僅適用於包含8個元素的向量)idl=((Id>>jg_3)<<jg_3)+Id-g21_setoff;id2=idl+(l jg_3);
idl= (idl》(jg_3-l)) %2==0 idl-( (idl》(jg_3_l)) >>1) * (1 (jg_3_l)) : idl+ (((1 (10_jg_3)) - (idl》(jg_3-l))) >>1) * (1 (jg_3-l));id2= (id2 (jg_3-l)) %2==0 id2-((id2 (jg_3_l)) >>1) * (1 (jg_3_l)) : id2+ (((1 (10_jg_3)) - (id2 (jg_3-l))) >>1) * (1 (jg_3-l));其中idl、id2為比較器操作的兩個數的寫回下標，Id為線程的全局編號，jg_3為將兩個m個元素的單調序列歸併為一個2*m個元素的單調序列的一系列操作中「總步數和現步驟編號的差」，g21_setoff為「兩倍的工作組內線程數乘以工作組編號」。b)設本次數據操作是將兩個m個元素的單調序列歸併為一個2*m個元素的單調序列的一系列操作中的一步，但下次數據操作是將兩個2*m個元素的單調序列歸 並為一個2*2*m個元素的單調序列的一系列操作中的一步，同時下一次數據操作所隸屬的一系列操作完成後不需要CPU參與同步，轉換公式為(僅適用於包含8個元素的向量)idl=((Id>>jg_3)<>1) * (1 (ig_3+l));id2= (id2 (ig_3+l)) %2==0 id2-((id2 (ig_3+l)) >>1) * (1 (ig_3+l)) : id2+ (((1 (8_ig_3)) - (id2 (ig_3+l))) >>1) * (1 (ig_3+l));b條的規則設置是為了將不需要CPU同步的幾組系列操作通過同步函數聯繫起來。c)類似於上述b條情況，但下一次數據操作所隸屬的一系列操作完成後需CPU參與同步，轉換公式為(僅適用於包含8個元素的向量)idl=((Id>>jg_3)<<jg_3)+Id-g21_setoff;id2=idl+(1<1所以必然存在bank衝突」。普適的向量寫操作bank衝突優化方法為「排序一組連續向量，前半部向量不連續時，將前半部的後半部(或前半部)向量和後半部的後半部(或前半部)向量交換位置後再執行寫回設備全局內存的操作將使bank衝突降至最低」。鑑於一次寫操作的向量地址必然等間隔，一組比較器執行一次比較操作的兩次寫操作的向量地址必然連續的特點，可保證上述方法的正確性。如附圖2所示，本發明的面向GPU的雙調歸併排序方法中，由CPU端執行的主機程序流程為步驟I :查找OpenCL支持的計算平臺，選擇相應的計算平臺後創建支持特定特備的上下文(Context)；步驟2 :查找上下文支持的計算設備，並關聯上下文和計算設備；步驟3 :查詢計算設備的屬性，創建待排序隊列並關聯到上下文和具體設備；步驟4 :創建Kernel程序並關聯到上下文後，編譯具體設備上運行的Kernel程序; 步驟5 :選擇Kernel程序中一個能夠在設備上運行的函數作為Kernel函數；步驟6 :創建設備內存和主機內存間的緩衝區；步驟7 :對Kernel函數的參數賦值,初次啟動Kernel函數；步驟8 :判斷待排序隊列的排序是否已完成，若完成則導出設備內存數據至主機內存；步驟9 :若未完成,繼續判斷是否更新Kernel函數參數,若不需更新則啟動Kernel函數後跳轉到步驟8繼續執行，若需要更新則重新對Kernel函數參數賦值並啟動Kernel函數後跳轉到步驟8繼續執行。如附圖3所示，為由Kernel函數執行的本發明的GPU雙調歸併排序方法執行過程步驟I :讀取Kernel函數參數，若為GPU線程需要多次局部同步(工作組內同步)截止到需要全局同步(情況3)，則執行步驟3 ;若為GPU線程進行一次比較操作後需要全局同步(情況2)，則執行步驟4後強制返回至步驟I ;若為排序起始到首次GPU線程需要全局同步截止(情況I )，則執行步驟2 ；步驟2 :將設備共享內存數據拷貝到設備局部內存，進行向量內排序；步驟3 :執行數據讀合併操作；步驟4:向量比較交換數據，判斷是否需要進行向量內排序，若是則進行向量內排序，若否則繼續執行步驟5;步驟5 :判斷是否需要降低bank衝突操作，若是則執行半數線程交換操作，若否則繼續執行步驟6 ；
步驟6 :判斷是否終止排序，若是則將設備局部內存數據拷貝到設備共享內存，若否則返回至步驟I。通過本發明的技術方案，可以實現在節省存儲空間的基礎上，有效減少CPU和GPU之間的同步次數、減少執行指令的總量和延時、增加GPU計算單元的利用率。以上所述的具體實施方式
，對本發明的目的、技術方案和有益效果進行了進一步詳細說明，所應理解的是，以上所述僅為本發明的具體實施方式
而已，並不用於限定本發明 的保護範圍，凡在本發明的精神和原則之內，所做的任何修改、等同替換、改進等，均應包含在本發明的保護範圍之內。
權利要求
1.一種面向GPU的雙調歸併排序方法，其特徵在於包括如下步驟 (1)將共享內存中的待排序列數據拷貝到GPU設備局部內存中； (2)判斷是否需要進行向量內排序，若需要則由一個線程操作向量模擬L個比較器，多個線程並行執行歸併排序； (3)將排序結果由GPU設備局部內存拷貝到共享內存中。
2.如權利要求I所述的方法，其特徵在於 步驟(2)中多個線程並行執行歸併排序時，對於同一個工作組內的線程同步使用同步函數來完成，對於不同工作組內的線程間同步通過CPU完成。
3.如權利要求2所述的方法，其特徵在於 當一個工作組內的比較器本次和下次操作數都存在於該工作組的局部內存時，使用同步函數同步工作組內線程；當一個工作組內的比較器本次和下次操作數存放在不同的工作組局部內存時，由CPU參與線程的同步。
4.如權利要求1-3之一所述的方法，其特徵在於 由一個線程來模擬L X M個比較器，操作2 X M個向量進行比較交換操作，每個線程內向量運算指令順序執行。
5.如權利要求4所述的方法，其特徵在於 在排序過程中，改變比較器操作數的寫回地址，以使局部內存讀操作的地址連續，同時為防止線程間數據讀寫衝突，設置每個線程將需要操作的數據讀入寄存器再進行比較交換操作。
6.如權利要求5所述的方法，其特徵在於 在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中的後半部與該後半部分向量中的後半部交換位置後，再執行寫回共享內存的操作。
7.如權利要求5所述的方法，其特徵在於 在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中的前半部與該後半部分向量中的前半部交換位置後，再執行寫回共享內存的操作。
8.一種面向GPU的雙調歸併排序系統，其特徵在於包括如下模塊 用於將共享內存中的待排序列數據拷貝到GPU設備局部內存中的模塊； 用於判斷是否需要進行向量內排序，若需要則由一個線程操作向量模擬L個比較器，多個線程並行執行歸併排序的模塊； 用於將排序結果由GPU設備局部內存拷貝到共享內存中的模塊。
9.如權利要求8所述的系統，其特徵在於 多個線程並行執行歸併排序時，對於同一個工作組內的線程同步使用同步函數來完成，對於不同工作組內的線程間同步通過CPU完成。
10.如權利要求9所述的系統，其特徵在於 當一個工作組內的比較器本次和下次操作數都存在於該工作組的局部內存時，使用同步函數同步工作組內線程；當一個工作組內的比較器本次和下次操作數存放在不同的工作組局部內存時，由CPU參與線程的同步。
11.如權利要求8-10之一所述的系統,其特徵在於 由一個線程來模擬L X M個比較器，操作2 X M個向量進行比較交換操作，每個線程內向量運算指令順序執行。
12.如權利要求11所述的系統，其特徵在於 在排序過程中，改變比較器操作數的寫回地址，以使局部內存讀操作的地址連續，同時為防止線程間數據讀寫衝突，設置每個線程將需要操作的數據讀入寄存器再進行比較交換操作。
13.如權利要求12所述的系統，其特徵在於 在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中的後半部與該後半部分向量中的後半部交換位置後，再執行寫回共享內存的操作。
14.如權利要求12所述的系統，其特徵在於 在排序一組向量時，若該組向量的前半部分向量地址不連續，則將該前半部分向量中 的前半部與該後半部分向量中的前半部交換位置後，再執行寫回共享內存的操作。
全文摘要
本發明公開了一種面向GPU的雙調排序方法和系統，通過一個線程操作向量來模擬多個比較器，多個線程並行執行歸併排序，其中對同一個工作組內的線程同步使用同步函數來完成，對不同工作組內的線程同步通過CPU完成，進一步的可以使用多個向量來模擬更大長度向量，在排序過程中改變比較器操作數的寫回地址，對內存讀寫進行優化。本發明在節省存儲空間的基礎上，有效地減少CPU和GPU之間的同步次數、減少執行指令的總量和延時、增加GPU計算單元的利用率。
文檔編號G06F9/38GK102750131SQ20121018738
公開日2012年10月24日 申請日期2012年6月7日 優先權日2012年6月7日
發明者王珏, 聶寧明, 遲學斌, 郎顯宇, 闞聖哲 申請人:中國科學院計算機網絡信息中心