[發(fā)明專利]一種基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202210556207.1
• 申請(qǐng)日: 2022-05-20
• 公開（公告）號(hào): CN114780151A
• 公開（公告）日: 2022-07-22
• 發(fā)明（設(shè)計(jì)）人: 張多利;葛虎;孫賀云;聶言碩;宋宇鯤;倪偉
• 申請(qǐng)（專利權(quán)）人: 合肥工業(yè)大學(xué)
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38;G06F9/30
• 代理公司: 北京律譜知識(shí)產(chǎn)權(quán)代理有限公司 11457
• 代理人: 孟德洲

1.一種基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，所述數(shù)據(jù)排序系統(tǒng)用于對(duì)外部存儲(chǔ)模塊中的原始數(shù)據(jù)進(jìn)行歸并排序，其特征在于，所述系統(tǒng)包括：加速模塊(40)，歸并模塊(20)以及數(shù)據(jù)輸出模塊(50)；

所述加速模塊(40)用于采用數(shù)據(jù)比較的方式，將獲取到的所述原始數(shù)據(jù)進(jìn)行分組排序，記作有序子序列數(shù)據(jù)；

所述數(shù)據(jù)輸出模塊(50)用于將所述有序子序列數(shù)據(jù)輸出至所述外部存儲(chǔ)模塊；

所述歸并模塊(20)用于獲取所述外部存儲(chǔ)模塊中的有序子序列數(shù)據(jù)，并采用循環(huán)的方式，對(duì)獲取到的有序子序列數(shù)據(jù)進(jìn)行歸并運(yùn)算，將歸并后的數(shù)據(jù)記作歸并排序數(shù)據(jù)；

所述數(shù)據(jù)輸出模塊(50)還用于將所述歸并排序數(shù)據(jù)輸出至所述外部存儲(chǔ)模塊。

2.如權(quán)利要求1所述的基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，其特征在于，所述系統(tǒng)還包括：控制模塊(10)以及緩存模塊(30)；

所述控制模塊(10)用于根據(jù)接收到的配置信息，確定讀寫數(shù)據(jù)的起始地址、結(jié)束地址以及歸并層數(shù)；

所述緩存模塊(30)用于根據(jù)所述起始地址、所述結(jié)束地址，從所述外部存儲(chǔ)模塊中獲取所述原始數(shù)據(jù)，并將所述原始數(shù)據(jù)發(fā)送至所述加速模塊(40)。

3.如權(quán)利要求1所述的基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，其特征在于，所述加速模塊(40)包括：RAM陣列，流水線模塊以及歸并樹模塊；

所述流水線模塊的兩側(cè)分別設(shè)置有一個(gè)RAM陣列，所述流水線模塊中設(shè)置有十級(jí)流水，所述流水線模塊用于采用數(shù)據(jù)比較以及查找表的編碼排序的方式，對(duì)獲取到的所述原始數(shù)據(jù)進(jìn)行分組排序；

所述歸并樹模塊用于對(duì)分組排序后的數(shù)據(jù)進(jìn)行歸并，得到所述有序子序列數(shù)據(jù)。

4.如權(quán)利要求3所述的基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，其特征在于，所述加速模塊(40)還用于根據(jù)所述RAM陣列的緩沖大小，獲取所述原始數(shù)據(jù)。

5.如權(quán)利要求3所述的基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，其特征在于，所述RAM陣列包括第一RAM以及第二RAM，所述第一RAM以及所述第二RAM中含8位寄存器，所述流水線模塊被配置為：

步驟11，按先后順序，將從所述第一RAM中獲取到的數(shù)據(jù)進(jìn)行兩兩分組，并比較每一組內(nèi)數(shù)據(jù)的大小，按照各組的順序，依次將組內(nèi)數(shù)值大的數(shù)據(jù)存儲(chǔ)在第二RAM的奇數(shù)位寄存器內(nèi)，將組內(nèi)數(shù)值小的數(shù)據(jù)存儲(chǔ)在第二RAM的偶數(shù)位寄存器內(nèi)，其中，所述第一RAM以及所述第二RAM中寄存器的位數(shù)從0開始依次編號(hào)；

步驟12，分別將所述第二RAM的奇數(shù)位寄存器、偶數(shù)位寄存器內(nèi)的數(shù)據(jù)進(jìn)行兩兩分組，并比較分組后各組數(shù)據(jù)的大小，對(duì)所述第一RAM進(jìn)行復(fù)用，將組內(nèi)數(shù)值大的數(shù)據(jù)存儲(chǔ)在所述第一RAM的第一寄存器內(nèi)，將組內(nèi)數(shù)值小的數(shù)據(jù)存儲(chǔ)在所述第一RAM的第二寄存器內(nèi)，其中，所述第一寄存器為第一、第二、第五、第六位寄存器，所述第二寄存器為第三、第四、第七第八位寄存器；

步驟13，對(duì)所述第二RAM進(jìn)行復(fù)用，分別比較所述第一RAM中第二、第三位寄存器以及第六、第七位寄存器中數(shù)據(jù)的大小，將數(shù)值大的數(shù)據(jù)存儲(chǔ)在所述第二RAM的第二、第六位寄存器，將數(shù)值小的數(shù)據(jù)存儲(chǔ)在所述第二RAM的第三、第七位寄存器，并將所述第一RAM中第一、第四、第五、第八位寄存器中的數(shù)據(jù)依次寫入所述第二RAM的第一、第四、第五、第八位寄存器；

步驟14，采用查找表的編碼排序的方式，對(duì)所述第二RAM中的數(shù)據(jù)依次進(jìn)行編碼、查找和譯碼，生成分組排序后的數(shù)據(jù)。

6.如權(quán)利要求2所述的基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，其特征在于，

所述控制模塊(10)還用于采用循環(huán)的方式，按順序從所述外部存儲(chǔ)模塊中讀取任一長度的有序子序列數(shù)據(jù)，并將獲取到的任一長度的有序子序列數(shù)據(jù)發(fā)送至所述緩存模塊(30)，其中，下一次獲取的數(shù)據(jù)長度為上一次獲取的數(shù)據(jù)長度的兩倍；

所述緩存模塊(30)還用于所述控制模塊(10)獲取到的任一長度的有序子序列數(shù)據(jù)發(fā)送至所述歸并模塊(20)。

7.如權(quán)利要求6所述的基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，其特征在于，所述控制模塊(10)第一次讀取所述有序子序列數(shù)據(jù)的長度小于有序子序列數(shù)據(jù)的總長度，

所述控制模塊(10)還被配置為：

當(dāng)判定所述數(shù)據(jù)輸出模塊(50)輸出的所述歸并排序數(shù)據(jù)的總長度等于所述有序子序列數(shù)據(jù)的總長度時(shí)，確定數(shù)據(jù)寫回起始地址，

其中，所述數(shù)據(jù)寫回起始地址用于確定所述歸并排序數(shù)據(jù)在所述外部存儲(chǔ)模塊中的存儲(chǔ)位置。