提供了用于改進(jìn)的高性能并行數(shù)據(jù)排序的方法、裝置和系統(tǒng)。在第一階段，要排序的多個(gè)無(wú)序數(shù)據(jù)元素被劃分為K個(gè)無(wú)序列表，這K個(gè)無(wú)序列表優(yōu)選地各自具有大約M個(gè)元素。這K個(gè)無(wú)序列表中的每一個(gè)可以使用任何算法(諸如快速排序)來(lái)并行排序，以生成K個(gè)有序列表。在第二階段，通過(guò)使用由最大迭代次數(shù)限制的迭代收斂過(guò)程，從K個(gè)有序列表中確定N個(gè)均衡的工作負(fù)荷。因此，任何非均勻或偏斜的數(shù)據(jù)分布都可以以最少的處理時(shí)間得以負(fù)荷均衡。一旦確定了N個(gè)均衡的工作負(fù)荷，它們就可以例如通過(guò)使用合并排序被并行地獨(dú)立排序，并且然后利用快速級(jí)聯(lián)組合，以提供最終的經(jīng)排序的結(jié)果。因此，排序操作完全并行化，同時(shí)避免了任何昂貴的數(shù)據(jù)掃描步驟。

技術(shù)領(lǐng)域

本公開(kāi)內(nèi)容涉及數(shù)據(jù)排序，并且更具體而言，涉及適于多線程和多節(jié)點(diǎn)環(huán)境的改進(jìn)的高性能并行數(shù)據(jù)排序。

背景技術(shù)

對(duì)數(shù)據(jù)排序是具有在各種學(xué)術(shù)領(lǐng)域和工業(yè)領(lǐng)域中的實(shí)際應(yīng)用的經(jīng)典優(yōu)化問(wèn)題。計(jì)算機(jī)應(yīng)用可能需要高性能的排序方法來(lái)進(jìn)行業(yè)務(wù)智能分析、提供演示渲染、對(duì)來(lái)自用戶和應(yīng)用的外部請(qǐng)求做出響應(yīng)、以及用于其它任務(wù)。例如，可以為了根據(jù)用戶或應(yīng)用所定義的標(biāo)準(zhǔn)排序的記錄列表而查詢數(shù)據(jù)庫(kù)。由于回應(yīng)這些查詢的整體處理時(shí)間直接受排序執(zhí)行時(shí)間的影響，所以需要高性能排序以及時(shí)提供結(jié)果。排序性能對(duì)于針對(duì)大數(shù)據(jù)集工作的應(yīng)用(諸如用于大型企業(yè)或高性能計(jì)算(HPC)的數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS))尤其重要，因?yàn)榇罅繑?shù)據(jù)記錄可能會(huì)放大任何排序操作的執(zhí)行時(shí)間。

可以利用多線程處理為這些數(shù)據(jù)密集型應(yīng)用提供合適的響應(yīng)時(shí)間，其中根據(jù)數(shù)據(jù)處理工作負(fù)荷添加諸如處理器核心和/或處理節(jié)點(diǎn)之類的資源。通過(guò)高度可并行化的工作負(fù)荷，多線程處理具有以成本高效和實(shí)用的方式提供優(yōu)化的性能縮放的潛力。由于排序可能會(huì)貢獻(xiàn)數(shù)據(jù)處理工作負(fù)荷的大部分，所以排序成為并行化的主要目標(biāo)，以減少查詢延遲時(shí)間以及提高多線程環(huán)境中的數(shù)據(jù)處理吞吐量。

諸如快速排序(quicksort)的串行排序技術(shù)是容易獲得的，從而為具有低至中等數(shù)據(jù)處理需求的應(yīng)用提供足夠的性能。然而，這些串行排序方法不太適用于具有高數(shù)據(jù)處理需求的多線程應(yīng)用。雖然已經(jīng)提議了用于并行化串行排序方法的各種做法，但是當(dāng)嘗試在數(shù)據(jù)密集型應(yīng)用中處理需要排序的大量元素(其數(shù)量可以是數(shù)十億或更多)時(shí)，或者當(dāng)嘗試在高度多線程的環(huán)境中將工作負(fù)荷分布到大量并行處理線程(其數(shù)量可以是數(shù)百個(gè)或更多)時(shí)，這些做法可能崩潰。

此外，要分析的給定數(shù)據(jù)集可以包括任何種類的數(shù)據(jù)分布，因此排序必須能夠處理數(shù)據(jù)集而不管數(shù)據(jù)集的特定數(shù)據(jù)分布是怎樣的。為了應(yīng)付非均勻的數(shù)據(jù)分布而需要冗長(zhǎng)的預(yù)處理或后處理步驟的任何并行化做法都可能由于減少或否定從并行化獲得的性能增益而強(qiáng)加不可接受的性能損失。例如，雖然由于每個(gè)分區(qū)可以被獨(dú)立排序而使得基數(shù)排序(radix-sort)可以適于(amenable to)并行化，但是根據(jù)最高有效位對(duì)數(shù)據(jù)進(jìn)行分區(qū)為非均勻的數(shù)據(jù)分布或偏斜(skewed)的數(shù)據(jù)分布提供了差的工作負(fù)荷均衡。因此，對(duì)于基數(shù)排序而言，需要在計(jì)算上昂貴的預(yù)處理步驟以應(yīng)付非均勻的數(shù)據(jù)分布，例如通過(guò)進(jìn)行串行數(shù)據(jù)掃描來(lái)確定均衡的工作負(fù)荷分區(qū)。雖然并行數(shù)據(jù)掃描也是可能的，但是由于解決寫入爭(zhēng)用(write contention)所需的進(jìn)程間通信，并行數(shù)據(jù)掃描將強(qiáng)加顯著的處理開(kāi)銷，這隨著線程數(shù)量的增加只會(huì)變差。在任一情況下，由于預(yù)處理步驟而產(chǎn)生的性能損失可能超出由于并行化基數(shù)排序而產(chǎn)生的任何性能增益。

基于前述，存在對(duì)于提供適于多線程和多節(jié)點(diǎn)環(huán)境的高性能并行數(shù)據(jù)排序的方法的需求。

本節(jié)中描述的做法是可以推行的做法，但不一定是先前已經(jīng)設(shè)想或推行的做法。因此，除非另有指示，否則不應(yīng)當(dāng)假設(shè)本節(jié)中描述的任何做法僅僅因?yàn)樗鼈儼诒竟?jié)中就成為現(xiàn)有技術(shù)。

附圖說(shuō)明

在附圖中以示例而非限制的方式示出了本發(fā)明，附圖中相同的參考標(biāo)號(hào)指代相似的要素，并且其中：

圖1是繪出根據(jù)實(shí)施例的用于改進(jìn)的并行數(shù)據(jù)排序的示例系統(tǒng)的框圖；

圖2A是繪出根據(jù)實(shí)施例的用于改進(jìn)的并行數(shù)據(jù)排序的過(guò)程的框圖；