[發(fā)明專利]基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201210510033.1
• 申請(qǐng)日: 2012-12-04
• 公開（公告）號(hào): CN102968496A
• 公開（公告）日: 2013-03-13
• 發(fā)明（設(shè)計(jì)）人: 王效忠;馮柯;蔣志勇;趙殿奎;楊永亮;張巍;關(guān)剛;孟勃榮
• 申請(qǐng)（專利權(quán)）人: 天津神舟通用數(shù)據(jù)技術(shù)有限公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30;G06F9/38
• 代理公司: 天津盛理知識(shí)產(chǎn)權(quán)代理有限公司 12209
• 代理人: 王利文

1.一種基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：包括以下步驟：

步驟1：分塊內(nèi)存排序步驟：將外存文件劃分成一定大小的微小桶并讀入內(nèi)存，每讀入一個(gè)微小桶就對(duì)其進(jìn)行快速排序，當(dāng)沒有更多內(nèi)存可用或者沒有更多數(shù)據(jù)時(shí)，對(duì)所有微小桶進(jìn)行內(nèi)存歸并，然后寫出到外存中，形成一個(gè)有序的桶；

步驟2：外存歸并步驟：對(duì)外存中的桶進(jìn)行歸并，并將歸并結(jié)果輸出到最終有序的文件中，生成有序的排序結(jié)果。

2.根據(jù)權(quán)利要求1所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述步驟1包括的具體步驟為：

⑴根據(jù)文件大小生成一個(gè)磁盤讀任務(wù)，用于讀取一個(gè)微小桶的數(shù)據(jù)到內(nèi)存對(duì)應(yīng)的排序緩沖區(qū)中，將此磁盤讀任務(wù)添加到磁盤讀線程的任務(wù)隊(duì)列的隊(duì)尾；

⑵再生成一個(gè)磁盤讀任務(wù)，添加到磁盤讀線程的任務(wù)隊(duì)列的隊(duì)尾；

⑶等待前一個(gè)磁盤讀任務(wù)的完成；

⑷分析讀入內(nèi)存排序緩沖區(qū)的微小桶的數(shù)據(jù)，生成元組結(jié)構(gòu)和指向元組的指針數(shù)組，產(chǎn)生一個(gè)快速排序任務(wù)，并添加到快速排序線程組任務(wù)隊(duì)列的隊(duì)尾；

⑸循環(huán)執(zhí)行⑵到⑷，直到?jīng)]有更多的磁盤讀任務(wù)或者沒有更多的內(nèi)存；

⑹等待最后一個(gè)磁盤讀任務(wù)的完成，然后分析最后一個(gè)微小桶的數(shù)據(jù)，再產(chǎn)生一個(gè)快速排序任務(wù)，并添加到快速排序線程組任務(wù)隊(duì)列的隊(duì)尾；

⑺等待所有的快速排序任務(wù)完成；

⑻生成一個(gè)內(nèi)存歸并任務(wù)，用于歸并內(nèi)存中所有的微小桶的數(shù)據(jù)到外存的桶中，并添加到快速排序線程組任務(wù)隊(duì)列的隊(duì)尾；

⑼等待內(nèi)存歸并任務(wù)完成；

⑽重復(fù)執(zhí)行⑴到⑼，直到?jīng)]有更多的數(shù)據(jù)。

3.根據(jù)權(quán)利要求2所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述磁盤讀任務(wù)的處理方法為：在指定的文件中，從指定的位置開始讀取指定大小的數(shù)據(jù)塊，存入指定的微小桶緩沖區(qū)中，輸入輸出完成以后給主線程發(fā)送磁盤讀任務(wù)已經(jīng)完成信號(hào)。

4.根據(jù)權(quán)利要求2所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述的快速排序任務(wù)的處理方法為：對(duì)元組指針數(shù)組進(jìn)行快速排序。

5.根據(jù)權(quán)利要求4所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述快速排序任務(wù)采用構(gòu)造等價(jià)排序鍵以及多個(gè)排序鍵合并構(gòu)造等價(jià)排序鍵的方式進(jìn)行。

6.根據(jù)權(quán)利要求5所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述構(gòu)造等價(jià)排序鍵的方法是將字符串等屬性構(gòu)造成能用8字節(jié)整數(shù)進(jìn)行比較的排序鍵的過程。

7.根據(jù)權(quán)利要求6所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述的等價(jià)排序鍵包含排序鍵和該排序鍵在元組指針數(shù)組上的偏移。

8.根據(jù)權(quán)利要求1或2所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述內(nèi)存歸并包括以下步驟：

⑴在每一個(gè)微小桶中順序地讀取等價(jià)排序鍵，插入到最小堆/最大堆中，進(jìn)行堆排序；

⑵將堆頂?shù)挠涗泴懙捷敵鼍彌_區(qū)的工作緩沖區(qū)中，如果工作緩沖區(qū)已經(jīng)被寫滿就執(zhí)行步驟⑶，否則就執(zhí)行步驟⑺；

⑶添加一個(gè)磁盤寫任務(wù)到磁盤寫線程的任務(wù)隊(duì)列的末尾；

⑷等待預(yù)操作緩沖區(qū)的磁盤寫任務(wù)完成；

⑸轉(zhuǎn)換工作緩沖區(qū)為預(yù)操作緩沖區(qū)，預(yù)操作緩沖區(qū)為工作緩沖區(qū)；

⑹將沒有寫入到上一個(gè)工作緩沖區(qū)的數(shù)據(jù)寫出到當(dāng)前工作緩沖區(qū)中；

⑺從剛才寫出的記錄所在的微小桶中繼續(xù)讀取一條記錄插入到堆中，如果此微小桶中沒有更多數(shù)據(jù)，就執(zhí)行⑻，否則就執(zhí)行⑼；

⑻刪除此微小桶，微小桶的個(gè)數(shù)減一；

⑼調(diào)整最小堆；

⑽循環(huán)執(zhí)行步驟⑵到步驟⑼直到微小桶的個(gè)數(shù)減到0為止。

9.根據(jù)權(quán)利要求1或2所述的基于任務(wù)驅(qū)動(dòng)和雙緩沖機(jī)制的并行排序方法，其特征在于：所述外存歸并包括以下步驟：

⑴給每一個(gè)桶都生成一個(gè)磁盤讀任務(wù)，并添加到磁盤讀任務(wù)隊(duì)列的末尾，用于從每個(gè)桶中讀取一小塊有序數(shù)據(jù)到桶的工作緩沖區(qū)；

⑵等待磁盤讀任務(wù)執(zhí)行結(jié)束，生成給該桶的預(yù)操作緩沖區(qū)讀入數(shù)據(jù)的磁盤讀任務(wù)，添加到磁盤讀任務(wù)隊(duì)列末尾；

⑶分析讀入到工作緩沖區(qū)的有序數(shù)據(jù)，生成元組指針數(shù)組，并構(gòu)造等價(jià)排序鍵數(shù)組；

⑷循環(huán)執(zhí)行步驟⑵和步驟⑶，直到每個(gè)桶的工作緩沖區(qū)都讀入了數(shù)據(jù)；

⑸順序的從每一個(gè)桶中讀取一條記錄，插入到最小堆/最大堆中，進(jìn)行堆排序；

⑹將堆頂?shù)挠涗泴懙捷敵鼍彌_區(qū)的工作緩沖區(qū)中，如果工作緩沖區(qū)已經(jīng)被寫滿就執(zhí)行步驟⑺，否則就執(zhí)行步驟⑾；

⑺添加一個(gè)磁盤寫任務(wù)到磁盤寫線程的任務(wù)隊(duì)列的末尾；

⑻等待預(yù)操作緩沖區(qū)的磁盤寫任務(wù)完成；

⑼交換工作緩沖區(qū)和預(yù)操作緩沖區(qū)；

⑽將上一個(gè)工作緩沖區(qū)沒有寫入的數(shù)據(jù)寫到當(dāng)前工作緩沖區(qū)中；

⑾從剛才寫出的記錄所在的桶的內(nèi)存中繼續(xù)讀取一條記錄插入到堆中，如果此桶的內(nèi)存中沒有更多數(shù)據(jù)就執(zhí)行步驟⑿，否則就執(zhí)行⒄；

⑿如果此桶的外存中還有數(shù)據(jù)，就生成磁盤讀任務(wù)，繼續(xù)讀取此桶的下一塊數(shù)據(jù)，否則標(biāo)記此桶沒有更多的數(shù)據(jù)；是否在一個(gè)桶在內(nèi)存中數(shù)據(jù)少于一定數(shù)量就提前進(jìn)行異步輸入輸出，以使磁盤輸入輸出和中央處理器并行;

⒀如果此桶沒有更多數(shù)據(jù)，就執(zhí)行⒁，否則等待此桶的預(yù)操作緩沖區(qū)磁盤讀任務(wù)結(jié)束，執(zhí)行步驟⒂；

⒁刪除此桶，桶的個(gè)數(shù)減一；

⒂分析讀入預(yù)操作緩沖區(qū)的有序數(shù)據(jù)，生成元組指針數(shù)組，并構(gòu)造等價(jià)排序鍵數(shù)組；

⒃交換此桶的預(yù)操作緩沖區(qū)和工作緩沖區(qū)；

⒄調(diào)整最小堆；

⒅循環(huán)執(zhí)行步驟⑹到步驟⒄直到桶的個(gè)數(shù)減到0為止。