一種數據並行排序方法和系統的製作方法
2023-05-30 00:12:56
一種數據並行排序方法和系統的製作方法
【專利摘要】本發明公開了一種數據並行排序方法和系統。該系統包括數據源、通過網絡連接數據源的多個並行處理單元、以及通信接口。該方法包括將待排序的數據分成多個數據塊，各並行處理單元分別獲取數據塊並進行採樣；第一併行處理單元匯總各並行處理單元的採樣數據並進行排序，根據並行處理單元的數量確定全局排序區間序列，將全局排序區間序列中各數據區間與各並行處理單元依次對應；各並行處理單元判斷本單元獲取的數據塊中每個數據所屬的數據區間並將該數據分發至對應的並行處理單元；各並行處理單元接收數據並進行局部排序；將各並行處理單元的局部排序結果順序組合。本發明提高了大規模數據的排序速度，同時對數據量有較高的擴展性。
【專利說明】一種數據並行排序方法和系統
【技術領域】
[0001]本發明涉及一種數據處理方法和系統，具體涉及一種數據並行排序方法和系統。【背景技術】
[0002]大規模數據處理中進行數據的全局排序是一種常見操作，例如PageRank計算。傳統的排序算法可以分成內排序和外排序兩類。其中，內排序包括插入排序、快速排序等，需要將數據全部加載到內存中進行計算，在需要排序的數據為大規模數據的情況下，單機內存成為瓶頸。外排序主要是基於多路並歸的排序算法，這種方式可以處理大規模數據，但速度較慢。目前在PageRank計算中，需要對最終的計算結果進行一個全局的排序，數據規模在上百GB，從計算規模來考慮，需要引入並行機制。但是，現有的並行排序方法在採樣環節進行串行處理，因此速度和效率仍有待提高。
[0003]消息傳遞接口(Message Passing Interface,簡稱為MPI)是一種應用於並行環境的消息傳遞標準，通過它可以使用多機並行工作，機器之間通過網絡交互數據。因此，為了更好地滿足PageRank計算中大規模數據排序的需求，克服現有的串行採樣的並行排序方法的缺陷，通過MPI開發了排序算法。
【發明內容】
[0004]鑑於上述問題，提出了本發明以便提供一種克服上述問題或者至少部分地解決上述問題的充分利用並行處理及消息傳遞接口實現快速排序的數據並行排序方法和系統。
[0005]根據本發明的一個方面，提供了一種數據並行排序方法。本發明的數據並行排序方法包括:將待排序的數據分成多個數據塊，各並行處理單元分別獲取一數據塊並對數據塊進行採樣；第一併行處理單元匯總各並行處理單元採樣得到的數據並進行排序，根據並行處理單元的數量確定全局排序區間序列，將全局排序區間序列中的各個數據區間與各並行處理單元依次對應；各並行處理單元判斷本單元初始獲取的數據塊中每個數據所屬的數據區間並將該數據分發至對應的並行處理單元；各並行處理單元接收數據並對屬於本單元對應的數據區間的數據進行局部排序；以及將各並行處理單元的局部排序結果順序組合。
[0006]根據本發明的另一方面，提供了一種數據並行排序系統。本發明的數據並行排序系統包括數據源、多個並行處理單元、以及將多個並行處理單元和數據源連接起來的網絡、以及與多個並行處理單元相連的並行處理單元間通信接口。其中，數據源包括數據分塊裝置。各個並行處理單元包括緩存器以及與緩存器相連的採樣裝置、排序裝置和歸屬區間查找裝置。第一併行處理單元還包括與排序裝置相連的分割裝置、以及與分割裝置和緩衝器相連的映射裝置。其中:數據分塊裝置，適於將待排序的數據分成多個數據塊；採樣裝置，適於對來自數據分塊裝置的數據塊進行採樣，並將採樣數據通過並行處理單元間通信接口傳遞至第一併行處理單元供後續匯總排序使用；排序裝置，適於對數據進行排序；分割裝置，適於根據並行處理單元的數量由排序後的採樣數據確定全局排序區間序列；映射裝置，適於將全局排序區間序列中的各數據區間與各並行處理單元依次對應得到映射表，將映射表通過並行處理單元間通信接口傳遞至各個並行處理單元；以及歸屬區間查找裝置，適於根據映射表判斷本單元的數據塊中每個數據所屬的數據區間並進一步找到對應的並行處理單元，將各條數據通過並行處理單元間通信接口發送至對應的並行處理單元進行後續的局部排序。
[0007]根據本發明的技術方案，通過消息傳遞接口實現數據並行排序，與現有的大規模數據排序方法相比，具有涉及環節少、簡單高效的特點，在排序過程中待處理的數據和階段性處理結果可以在多個並行處理單元之間傳遞，因此與現有的大規模數據並行排序方案相t匕，能夠在排序的各個環節充分利用並行處理，不僅在歸屬區間查找階段和局部排序階段採取並行處理，而且在數據取樣階段也採取並行處理，還有可能在並行處理環節進一步並行，大大提高了大規模數據的排序速度，同時本發明的排序方案對數據量有更高的擴展性。
[0008]另外，本發明由於在排序系統中採用消息傳遞接口，保證了並行處理單元間的負載平衡和最小的消息傳遞通信開銷，排序過程能夠全程在並行處理單元上進行，無需客戶端參與，避免了佔用客戶端的工作負載和緩存空間，而且階段性處理結果不需要傳輸到客戶端，只需要在並行處理單元之間傳輸，傳輸距離短，傳輸速度快，不佔用客戶端側的網絡流量。
[0009]上述說明僅是本發明技術方案的概述，為了能夠更清楚了解本發明的技術手段，而可依照說明書的內容予以實施，並且為了讓本發明的上述和其它目的、特徵和優點能夠更明顯易懂，以下特舉本發明的【具體實施方式】。
【專利附圖】
【附圖說明】
[0010]通過閱讀下文優選實施方式的詳細描述，各種其他的優點和益處對於本領域普通技術人員將變得清楚明了。附圖僅用於示出優選實施方式的目的，而並不認為是對本發明的限制。而且在整個附圖中，用相同的參考符號表示相同的部件。在附圖中:
[0011]圖1是根據本發明一個實施例的數據並行排序方法的流程圖；
[0012]圖2是根據本發明一個實施例的數據並行排序系統的組成結構示意圖。
【具體實施方式】
[0013]下面將參照附圖更詳細地描述本公開的示例性實施例。雖然附圖中顯示了本公開的示例性實施例，然而應當理解，可以以各種形式實現本公開而不應被這裡闡述的實施例所限制。相反，提供這些實施例是為了能夠更透徹地理解本公開，並且能夠將本公開的範圍完整的傳達給本領域的技術人員。
[0014]圖1示出根據本發明一個實施例的並行排序方法。該方法基於包括數據源、通過網絡連接數據源的多個並行處理單元、以及使多個並行處理單元能夠互相交換數據的並行單元間通信接口例如MPI的系統，其中，並行處理單元的數量為兩個以上。
[0015]該方法始於步驟101，為了在多個並行處理單元上進行並行排序，在數據源將需要排序的數據分塊。優選地，假設並行處理單元的個數為N，則把需要排序的數據均勻劃分成N塊，每塊數據的數據量為原始數據量的1/N。將待排序的數據均勻分塊可以保證並行處理單元之間的負載平衡。每個並行處理單元從數據源獲得自己的數據塊。
[0016]然後，進入步驟102，每個並行處理單元對從數據源獲得的數據塊進行內部採樣。採樣的數據量越大越能體現出待排序數據的總體情況，由於本發明在數據採樣階段即採用並行處理方式，數據採樣的速度和效率大大提高，所以在同樣的採樣速度的情況下可以從待排序的數據中採樣更多數據，樣本數據的量與原數據量之比提高，樣本數據能夠代替整體數據分布，進而使後續的局部排序過程中各個並行處理單元處理的數據量大致相等，即各個並行處理單元的工作量均衡。
[0017]該方法進入步驟103，第一併行處理單元獲取各個並行處理單元採樣得到的數據，對各個並行處理單元採樣得到的數據進行匯總排序。另外，本領域技術人員容易理解，第一併行處理單元對匯總的採樣數據進行排序可以採用任何一種現有的串行排序方法，例如插入排序、快速排序、歸併排序等等。進入步驟104，根據並行處理單元的數量N由排序後的採樣數據確定全局排序區間序列。優選地，第一併行處理單元從排序後的採樣數據中均勻抽取部分數據作為各個數據區間的邊界，以形成依次包括N個數據區間的全局排序區間序列。為了使後續局部排序時各個並行處理單元之間的工作量均衡，就要儘量保證介於各個數據區間中的數據量大致相等，所以要對排序後的採樣數據進行均勻抽取。然後，進入步驟105，將該全局排序區間序列中的各個數據區間與各個並行處理單元依次對應起來，並將與對應關係有關的信息傳遞給各個並行處理單元。優選地，第一併行處理單元通過映射表將各個數據區間與各個並行處理單元的標識依次對應起來，並將映射表廣播給各個並行處理單元。
[0018]進入步驟106，各個並行處理單元遍曆本單元中的數據塊，根據第一併行處理單元傳遞來的對應關係信息判斷每條數據所屬的數據區間並進一步找到對應的並行處理單元，將各條數據分發至對應的並行處理單元。
[0019]上述步驟102至步驟106是在保證全局有序的前提下為後續的局部排序做準備。其中，第一併行處理單元可以是任意一個並行處理單元。
[0020]進入步驟107，每個並行處理單元接收各個並行處理單元發來的數據，對屬於本單元對應的數據區間的數據進行局部排序。本領域技術人員容易理解，各個並行處理單元對屬於本單元對應的數據區間的數據進行局部排序可以採用任何一種現有的串行排序方法，例如插入排序、快速排序、歸併排序等等。當然，如果並行處理單元進一步包括下一級並行處理單元的話，各個並行處理單元對屬於本單元對應的數據區間的數據進行局部排序也可以採用並行排序方式。
[0021]進入步驟108，將所有並行處理單元的局部排序結果順尋組合即得到最終的排序結果，將結果輸出。實際上，就是按照並行處理單元的標識的順序將所有並行處理單元的排序結果組合起來，得到最終的排序結果。
[0022]根據上述實施例的數據並行排序方法，通過並行單元間通信接口實現數據排序，在排序過程中待處理的數據和階段性處理結果可以在多個並行處理單元之間傳輸，因此與現有的並行排序方法相比，能夠在排序的各個環節充分利用並行處理，不僅在歸屬區間查找階段和局部排序階段採取並行處理而且在數據採樣階段也採取並行處理，大大提高了大規模數據的排序速度，同時這種排序方法對數據量有較高的擴展性。
[0023]圖2示出根據本發明一個實施例的數據並行排序系統。該系統包括多個並行處理單元32、數據源31以及將多個並行處理單元32和數據源31連接起來的網絡、以及與多個並行處理單元相連的並行處理單元間通信接口 33。[0024]其中，數據源31，例如採用HDFS(Hadoop分布式文件系統)，適於存儲大規模數據。數據源31包括數據分塊裝置311，數據分塊裝置311適於對待排序的數據進行分塊，然後各個並行處理單元32分別從數據源31獲取不同的數據塊。假設並行處理單元32的個數為N,則把待排序的數據均勻劃分成N塊，每塊數據的數據量為原始數據量的1/N。
[0025]並行處理單元間通信接口 33，適於在各個並行處理單元32之間傳遞消息。並行處理單元間通信接口 33優選採用MPI，MPI包括MPI廣播模塊和MPI收集模塊，實現集群通信功能，還包括MPI發送模塊和MPI接收模塊，實現點對點通信功能。其中，MPI廣播模塊適於在並行處理單兀32之間一對多廣播同樣的消息,MPI收集模塊適於多對一收集各個並行處理單元32的消息，MPI發送模塊和MPI接收模塊相對應。
[0026]各個並行處理單元32包括緩存器320以及與緩存器320相連的採樣裝置321、排序裝置322和歸屬區間查找裝置325。其中，第一併行處理單元32還包括與排序裝置322相連的分割裝置323、以及與分割裝置323和緩衝器320相連的映射裝置324。
[0027]緩存器320適於對並行處理單元32中待處理的數據或處理結果進行緩存。
[0028]各個並行處理單元32上的採樣裝置321適於對本單元獲取的數據塊進行採樣。
[0029]第一併行處理單元32上的排序裝置322，適於將通過並行處理單元間通信接口 33從各個並行處理單元32獲取的採樣數據匯總後進行排序，將排序後的採樣數據傳輸至分割裝置323。排序裝置322可以是任何一種現有的並行排序裝置，例如插入排序裝置、快速排序裝置、歸併排序裝置等等。如果並行處理單元間通信接口 33是MPI，則第一併行處理單元32通過MPI收集模塊從各個並行處理單元32收集採樣數據提供給排序裝置322進行匯總排序。作為另一選擇，也可以由各個並行處理單元32分別通過MPI發送模塊向第一併行處理單元32發送採樣數據，由第一併行單元32通過MPI接收模塊接收各個並行處理單元32發來的採樣數據。
[0030]第一併行處理單元32上的分割裝置323，適於根據並行處理單元32的數量N由排序後的採樣數據確定全局排序區間序列，將確定的全局排序區間序列傳輸至映射裝置324。分割裝置323的具體功能為從來自排序裝置322的數據中均勻抽取部分數據作為各個數據區間的邊界，以形成依次包括N個數據區間的全局排序區間序列。
[0031]第一併行處理單元32上的映射裝置324，適於將全局排序區間序列中的各個數據區間與各個並行處理單元32依次對應得到映射表。第一併行處理單元32將得到的映射表通過並行處理單元間通信接口 33傳遞給各個並行處理單元32。如果並行處理單元間通信接口 33是MPI，則第一併行處理單元32通過MPI廣播模塊將映射表廣播給其他各個並行處理單元32。
[0032]各個並行處理單元32上的歸屬區間查找裝置325，適於根據通過並行處理單元間通信接口 33傳遞來的映射表判斷本單元的數據塊中每個數據屬於哪個數據區間並進一步找到對應的並行處理單元32。各個並行處理單元32分別通過並行處理單元間通信接口 33將逐條數據分發至對應的並行處理單元32。如果並行處理單元間通信接口 33是MPI，則各個並行處理單元32將歸屬區間查找裝置325找到歸屬區間的數據通過MPI發送模塊發送至對應的並行處理單元32，供對應的並行處理單元32的排序裝置322進行後續的局部排序。
[0033]如果需要在並行處理單元32中對數據塊作進一步分塊，則各個並行處理單元32還包括與採樣裝置321相連的數據分塊裝置。
[0034]根據上述實施例的排序系統由於採用並行處理單元間通信接口 33例如MPI，保證了並行處理單元間的負載平衡和最小的消息傳遞通信開銷，在排序過程中待處理數據和階段性處理結果可以在多個並行處理單元32之間傳輸，因此能夠在排序的各個環節充分利用並行處理，不僅在歸屬區間查找階段和局部排序階段採取並行處理而且在數據取樣階段也採取並行處理，大大提高了大規模數據的排序速度，同時這種排序系統對數據量有較高的擴展性。另外，排序過程由始至終在並行處理單元上進行，無需客戶端參與，避免了佔用客戶端的工作負載和緩存空間，而且階段性處理結果不需要傳輸到客戶端，只需要在並行處理單元之間傳輸，傳輸距離短，傳輸速度快，不佔用客戶端側的網絡流量。
[0035]下面，通過一個簡單的例子對本發明的技術方案做進一步說明。
[0036]數據源31在HDFS (Hadoop分布式文件系統)中，有10億個整數{x0, X1,……J X999999999 I Xi e (0，IO9)}需要排序，具體任務是將這10億個整數從小到大升序排列。多個節點通過HDFS相連，各個節點為具有多核CPU的伺服器，因此既可以以一個節點為一個並行處理單元32，也可以以一個節點上運行的一個線程為一個並行處理單元32。假設有η個節點，節點編號為節點0，節點1，……，節點η-1，每個節點包括24個線程，線程編號為線程0，線程1，……，線程23。並行處理單元間通信接口 33是MPI。
[0037]首先是劃分數據的過程101。根據節點的數量η，分布式文件系統中的數據分塊裝置將待排序的數據均勻劃分成η塊後緩存起來。每個節點從分布式文件系統獲取一個不同的數據塊。節點j的數據為{xk I k%n==j},其中j是k除以η的餘數,從而得到:
[0038]節點O:Χ0，Χη，Χ2η?......[0039]節點I =X1, χη+1, χ2η+1,......[0040]......[0041]節點η-1:Xn-^X2n-!, x3n-1,......[0042]還可以進一步地，每個節點從分布式文件系統獲取一個不同的數據塊之後，對自己獲取的數據塊在節點內再進行分塊，比如Xtl分到節點O的線程0，Xn分到節點O的線程1，X2n分到節點O的線程2,等等；Xi分到節點I的線程O, xn+1分到節點I的線程I, x2n+1分到節點I的線程2，等等。
[0043]然後進入內部採樣的過程102。每個節點的採樣模塊321隨機地從自己獲取的數據塊中抽取1/10000=105個數據。
[0044]節點O採樣得到的數據:xQ，x3n, x7n,......[0045]節點I採樣得到的數據:xn+1, x5n+1, x9n+1,......[0046]......[0047]節點η-1採樣得到的數據X4lri, X10n-!,......[0048]作為另一選擇，如果各個節點將本節點獲取的數據塊進一步分塊後分配給本節點的各個線程，則可以由各個線程對本線程獲取的數據塊進行隨機採樣，然後將各線程採樣得到的數據組合起來，作為節點採樣的結果。
[0049]接著進入節點O對採樣數據進行匯總排序的過程103。節點O通過MPI收集模塊從節點O~η-1收集採樣數據，匯總如下:
[0050]X0, X3n) Χ7η> Χη+1> X5n+1> X9n+1>......Xn_l，X4n_l，X10n-1>......[0051]作為另一選擇，也可以由節點O~η-1分別通過MPI發送模塊向節點O發送採樣數據，節點O通過MPI接收模塊接收各個節點發來的採樣數據。
[0052]節點O的排序模塊322對匯總後的採樣數據進行升序排列:χ3η，χη+1, χ9η+1,……，記為S。對匯總後的採樣數據進行排序可以採用任何一種現有的串行排序方法，例如插入排序、快速排序、歸併排序等等。
[0053]進入由排序後的採樣數據確定全局排序區間序列的過程104。
[0054]在實施例1中，根據節點數η，節點O的分割裝置323從排序後的採樣數據中均勻抽取η-1個點作為全局排序區間序列的分割點，抽取點為split: {Sk I k=105*i/(η-1) , (i=0, I,......，η-2)}。
[0055]在實施例2中，根據節點數η與節點中的線程的數量24得到線程總數24η，因此節點O的分割裝置323從排序後的採樣數據中均勻抽取24η-1個點作為全局排序區間序列的分割點，抽取點為 split:{Sk I k=105*i/ (24n-l)，(i=0，1，……，24n_2)}。
[0056]本發明不限於上述這種確定全局排序區間序列的方式，還可以將排序後的採樣數據均勻劃分成η或24η個數據塊，找到這η或24η個數據塊的數據上限和下限作為全局排序區間序列的分割點。
[0057]接下來進入映射過程105。
[0058]在實施例1中，節點O的映射裝置324將各個數據區間的左邊界與各個節點的編號以數據區間的左邊界為關鍵碼進行哈希(hash)映射，從而使全局排序區間序列中按照邊界數值從小到大排列的數據區間與按照編號順序排列的各節點一一對應。
[0059]在實施例2中，節點O的映射裝置324將各個數據區間的左邊界與各個節點的編號以及節點中各個線程的編號以數據區間的左邊界為關鍵碼進行哈希(hash)映射，從而使全局排序區間序列中按照邊界數值從小到大排列的數據區間與按照編號順序排列的各節點中的各線程對應。
[0060]由各個數據區間的左邊界形成區間邊界數組，將映射表通過MPI廣播模塊廣播給節點O~η-1,其中該映射表包括區間邊界數組。
[0061]本領域技術人員容易理解，上述過程103-105也可以不在節點O上執行，而改由其他任一節點執行。
[0062]進入歸屬區間查找過程106。節點O~η-1每個節點的歸屬區間查找裝置325遍曆本節點中的數據塊，如果在步驟101中，將數據塊進一步分塊後分配給各線程了的話，也可以每個線程遍曆本線程中的數據塊。對於每條數據X，相對於區間邊界數組進行二分查找，即將X與區間邊界數組中的中間結點作比較，如果X等於中間結點，則X屬於以中間結點為左邊界的數據區間；如果X小於中間結點，則X位於區間邊界數組的前半段並在數組前半段中繼續進行二分查找，直到找到X所屬的數據區間，即找到X所屬的數據區間的左邊界；如果X大於中間結點，則X位於區間邊界數組的後半段並在數組後半段中繼續進行二分查找，直到找到X所屬的數據區間，即找到X所屬的數據區間的左邊界。然而，本領域技術人員容易理解，本發明查找歸屬區間的方式可以不採用限於二分查找法，而採用其他查找方法，t匕如順序查找法。
[0063]在實施例1中，假設在split集合中找到一個數據所屬的數據區間的左邊界為t，則目的節點的編號為index (t)，MPI發送模塊通過編號將該數據發送到對應節點。[0064]在實施例2中，假設在split集合中找到一個數據所屬的數據區間的左邊界為t，則目的節點的編號為indeX(t)/24 (算出除數)並且目的線程的編號為index(t)%24 (算出餘數)，MPI發送模塊通過編號將該數據發送到對應節點的對應線程。
[0065]進入局部排序過程107。
[0066]在實施例1中，每個節點通過MPI接收模塊接收節點O?η-1發來的數據,數據接收完成後，每個節點對屬於本節點對應的數據區間的所有數據進行升序排序。
[0067]在實施例2中，每個節點通過MPI接收模塊接收節點O?η-1發來的數據並提供給相應的線程，數據接收完成後，每個線程對屬於本線程對應的數據區間的所有數據進行升序排序。
[0068]對數據進行局部排序可以採用任何一種現有的串行排序方法，例如插入排序、快速排序、歸併排序等等。
[0069]進入最終排序結果輸出過程108。將各個線程的排序結果按照各線程的編號順序通過分布式文件系統向用戶順序輸出，得到最終的排序結果。
[0070]本領域技術人員容易理解，線程的數量也可以不與CPU的核數相同，可以大於或小於CPU的核數。
[0071]根據上述實施例的本發明，由於用於數據排序的並行節點進一步包括多個並行線程，進一步提高了大規模數據的排序速度，同時也進一步提高了對數據量的擴展性。
[0072]在此提供的算法和顯示不與任何特定計算機、虛擬系統或者其它設備固有相關。各種通用系統也可以與基於在此的示教一起使用。根據上面的描述，構造這類系統所要求的結構是顯而易見的。此外，本發明也不針對任何特定程式語言。應當明白，可以利用各種程式語言實現在此描述的本發明的內容，並且上面對特定語言所做的描述是為了披露本發明的最佳實施方式。
[0073]在此處所提供的說明書中，說明了大量具體細節。然而，能夠理解，本發明的實施例可以在沒有這些具體細節的情況下實踐。在一些實例中，並未詳細示出公知的方法、結構和技術，以便不模糊對本說明書的理解。
[0074]類似地，應當理解，為了精簡本公開並幫助理解各個發明方面中的一個或多個，在上面對本發明的示例性實施例的描述中，本發明的各個特徵有時被一起分組到單個實施例、圖、或者對其的描述中。然而，並不應將該公開的方法解釋成反映如下意圖:即所要求保護的本發明要求比在每個權利要求中所明確記載的特徵更多的特徵。更確切地說，如下面的權利要求書所反映的那樣，發明方面在於少於前面公開的單個實施例的所有特徵。因此，遵循【具體實施方式】的權利要求書由此明確地併入該【具體實施方式】，其中每個權利要求本身都作為本發明的單獨實施例。
[0075]本領域那些技術人員可以理解，可以對實施例中的設備中的模塊進行自適應性地改變並且把它們設置在與該實施例不同的一個或多個設備中。可以把實施例中的模塊或單元或組件組合成一個模塊或單元或組件，以及此外可以把它們分成多個子模塊或子單元或子組件。除了這樣的特徵和/或過程或者單元中的至少一些是相互排斥之外，可以採用任何組合對本說明書(包括伴隨的權利要求、摘要和附圖)中公開的所有特徵以及如此公開的任何方法或者設備的所有過程或單元進行組合。除非另外明確陳述，本說明書(包括伴隨的權利要求、摘要和附圖)中公開的每個特徵可以由提供相同、等同或相似目的的替代特徵來代替。
[0076]此外，本領域的技術人員能夠理解，儘管在此所述的一些實施例包括其它實施例中所包括的某些特徵而不是其它特徵，但是不同實施例的特徵的組合意味著處於本發明的範圍之內並且形成不同的實施例。例如，在下面的權利要求書中，所要求保護的實施例的任意之一都可以以任意的組合方式來使用。
[0077]本發明的各個部件實施例可以以硬體實現，或者以在一個或者多個處理器上運行的軟體模塊實現，或者以它們的組合實現。本領域的技術人員應當理解，可以在實踐中使用微處理器或者數位訊號處理器(DSP)來實現根據本發明實施例的消息傳遞接口 MPI中的一些或者全部部件的一些或者全部功能。本發明還可以實現為用於執行這裡所描述的方法的一部分或者全部的設備或者裝置程序(例如，電腦程式和電腦程式產品)。這樣的實現本發明的程序可以存儲在計算機可讀介質上，或者可以具有一個或者多個信號的形式。這樣的信號可以從網際網路網站上下載得到，或者在載體信號上提供，或者以任何其他形式提供。
[0078]應該注意的是上述實施例對本發明進行說明而不是對本發明進行限制，並且本領域技術人員在不脫離所附權利要求的範圍的情況下可設計出替換實施例。在權利要求中，不應將位於括號之間的任何參考符號構造成對權利要求的限制。單詞「包含」不排除存在未列在權利要求中的元件或步驟。位於元件之前的單詞「一」或「一個」不排除存在多個這樣的元件。本發明可以藉助於包括有若干不同元件的硬體以及藉助於適當編程的計算機來實現。在列舉了若干裝置的單元權利要求中，這些裝置中的若干個可以是通過同一個硬體項來具體體現。單詞第一、第二、以及第三等的使用不表示任何順序。可將這些單詞解釋為名稱。
【權利要求】
1.一種數據並行排序方法，包括: 將待排序的數據分成多個數據塊，各並行處理單元分別獲取一數據塊並進行採樣； 第一併行處理單元匯總各並行處理單元採樣得到的數據並進行排序，根據並行處理單元的數量確定全局排序區間序列，將全局排序區間序列中各數據區間與各並行處理單元依次對應； 各並行處理單元判斷本單元獲取的數據塊中每個數據所屬的數據區間並將該數據分發至對應的並行處理單元； 各並行處理單元接收數據並對屬於本單元對應的數據區間的數據進行局部排序； 將各並行處理單元的局部排序結果順序組合。
2.根據權利要求1所述的數據並行排序方法，其中，所述各並行處理單元包括節點和/或節點上的線程。
3.根據權利要求2所述的數據並行排序方法，其中，所述將待排序的數據分成多個數據塊並由各並行處理單元分別獲取進一步包括:根據節點和/或線程的數量將待排序的數據平均分成對應數量的數據塊，各節點和/或線程獲取一數據塊。
4.根據權利要求1所述的數據並行排序方法，其中，所述第一併行處理單元匯總各並行處理單元採樣得到的數據進一步包括:第一併行處理單元從各個並行處理單元收集採樣數據。
5.根據權利要求1所述的數據並行排序方法，其中，所述根據並行處理單元的數量確定全局排序區間序列進一步包括:從排序後的採樣數據中均勻抽取部分數據作為各數據區間的邊界。
6.根據權利要求1所述的數據並行排序方法,其中，所述將全局排序區間序列中的各數據區間與各並行處理單元依次對應進一步包括:通過哈希映射將各個數據區間的左邊界與各個並行處理單元的標識依次對應起來。
7.根據權利要求1所述的數據並行排序方法,其中，所述將全局排序區間序列中的各數據區間與各並行處理單元依次對應進一步包括:第一併行處理單元將所述各數據區間與各並行處理單元之間的對應關係廣播給各個並行處理單元。
8.根據權利要求1所述的數據並行排序方法，其中，所述判斷本單元獲取的數據塊中每個數據所屬的數據區間進一步包括:對於每個數據，相對於各數據區間的邊界進行二分查找，得到該數據所屬的數據區間。
9.根據權利要求1所述的數據並行排序方法，其中，所述每個並行處理單元對屬於本單元對應的數據區間的數據進行局部排序是一種並行排序。
10.一種數據並行排序系統,包括: 數據分塊裝置，適於將待排序的數據分成多個數據塊； 採樣裝置，適於對來自數據分塊裝置的數據塊進行採樣，並將採樣數據通過並行處理單元間的通信接口傳遞至第一併行處理單元供後續匯總排序使用； 排序裝置，適於對數據進行排序； 分割裝置，適於根據並行處理單元的數量由排序後的採樣數據確定全局排序區間序列； 映射裝置，適於將全局排序區間序列中的各數據區間與各並行處理單元依次對應得到映射表，將映射表通過並行處理單元間的通信接口傳遞至各個並行處理單元； 歸屬區間查找裝置，適於根據映射表判斷本單元的數據塊中每個數據所屬的數據區間並進一步找到對應的並行處理單元，將各條數據通過並行處理單元間通信接口發送至對應的並行處理單元進行排序； 排序輸出裝置 ，適於將各並行處理單元進行排序後的結果順序組合後輸出。
【文檔編號】G06F7/24GK103530084SQ201310446658
【公開日】2014年1月22日 申請日期:2013年9月26日 優先權日:2013年9月26日
【發明者】陳建, 唐會軍, 齊路 申請人:北京奇虎科技有限公司, 奇智軟體（北京）有限公司