[發(fā)明專利]并行合并有效
| 申請?zhí)枺?/td> | 201580056152.6 | 申請日： | 2015-10-06 |
| 公開（公告）號： | CN107077488B | 公開（公告）日： | 2020-12-04 |
| 發(fā)明（設(shè)計）人： | 張浩煒;沈小瑛 | 申請（專利權(quán)）人： | 甲骨文國際公司 |
| 主分類號： | G06F16/27 | 分類號： | G06F16/27;G06F9/50 |
| 代理公司： | 中國貿(mào)促會專利商標(biāo)事務(wù)所有限公司 11038 | 代理人： | 邊海梅 |
| 地址： | 美國加*** | 國省代碼： | 暫無信息 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 并行 合并 | ||
1.一種用于高性能并行數(shù)據(jù)排序的方法，包括：
接收K個有序列表，其中，M表示所述K個有序列表中的每一個有序列表中的元素數(shù)量，其中，K超出1并且M超出1；
為N個均衡的工作負荷定義目標(biāo)大小范圍，所述目標(biāo)大小范圍背離目標(biāo)大小KM/N不超出預(yù)定閾值，其中N超出1；
為所述N個均衡的工作負荷中的每個特定工作負荷執(zhí)行多次迭代，以使所述每個特定工作負荷的大小朝目標(biāo)大小范圍收斂，其中對于所述多次迭代中的每次迭代：
確定所述每個特定工作負荷包括來自所述K個有序列表中的每一個有序列表的相應(yīng)的子集，所述相應(yīng)的子集由相應(yīng)的索引范圍界定，其中所述多次迭代中的每次迭代選擇所述K個有序列表中的特定的有序列表，其中當(dāng)所述每次迭代具有前一次迭代時，所述確定包括：
基于所述前一次迭代期間的所述K個有序列表中的所述相應(yīng)的子集的大小，選擇所述K個有序列表中的特定的有序列表，其中所述每次迭代的所述特定的有序列表可以與所述前一次迭代的特定的有序列表不同，以及
基于所述前一次迭代期間的所述特定的有序列表的所述相應(yīng)的子集的大小，調(diào)整用于所述特定的有序列表的所述相應(yīng)的子集的所述相應(yīng)的索引范圍；
并行地對所述N個均衡的工作負荷中的每一個進行排序；及
組合所述N個均衡的工作負荷，以輸出經(jīng)排序的結(jié)果；
其中所述方法由一個或多個計算設(shè)備執(zhí)行。
2.如權(quán)利要求1所述的方法，還包括在接收所述K個有序列表之前：
接收對多個無序數(shù)據(jù)元素進行排序的請求；
將所述多個無序數(shù)據(jù)元素近似均勻地劃分為K個無序列表；及
并行地對所述K個無序列表中的每一個進行排序，以提供所述K個有序列表。
3.如權(quán)利要求2所述的方法，其中通過快速排序?qū)λ鯧個無序列表中的每一個無序列表進行排序。
4.如權(quán)利要求1所述的方法，其中通過K路合并排序或者2路合并排序?qū)λ鯪個均衡的工作負荷中的每一個工作負荷進行排序。
5.如權(quán)利要求1所述的方法，其中并行地對所述N個均衡的工作負荷中的每一個進行排序是通過將所述N個均衡的工作負荷中的每一個指派給多個線程中的相應(yīng)的線程來執(zhí)行的，并且所述多個線程中的每個線程在多個處理核心中的相應(yīng)的處理核心上執(zhí)行。
6.如權(quán)利要求1所述的方法，其中所述確定包括：
對于所述N個均衡的工作負荷中的特定工作負荷執(zhí)行：
對于收斂過程中的每次迭代：
如果所述每次迭代是第一次迭代，則從所述K個有序列表中選擇特定列表并且將所述特定列表中的候選拆分點選擇為第一索引M/N；
如果所述每次迭代是在所述第一次迭代之后，則：
如果所述特定工作負荷的大小小于所述目標(biāo)大小，則從所述K個有序列表中選擇具有作為所述K個有序列表中的最小拆分點的第一拆分點的特定列表，或者，如果所述特定工作負荷的大小大于所述目標(biāo)大小，則從所述K個有序列表中選擇具有作為所述K個有序列表中的最大拆分點的第二拆分點的特定列表；并且
將所述特定列表中的所述候選拆分點選擇為對應(yīng)于(i+M/N)/2的向上取整的第二索引，其中i是用于前一次迭代的所述特定列表中的拆分點的第三索引；
找到用于所述K個有序列表中除所述特定列表之外的每個列表的拆分點，其中在每個所述拆分點之前的索引處的值不超出在所述候選拆分點處的候選值；
對在有序列表中的每一個有序列表的拆分點之前的元素數(shù)量求和，以確定所述特定工作負荷的大小；
如果所述特定工作負荷的大小在所述目標(biāo)大小范圍內(nèi)，則結(jié)束所述收斂過程；
如果達到最大迭代次數(shù)，則結(jié)束所述收斂過程；
將用于所述特定工作負荷的每個所述子集的特定索引范圍定義為從起始偏移量開始并且不超出有序列表中的每一個有序列表的拆分點；
對于有序列表中的每一個有序列表，將起始偏移量移動到拆分點。
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于甲骨文國際公司，未經(jīng)甲骨文國際公司許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.17sss.com.cn/pat/books/201580056152.6/1.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
