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

在審

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

本申請(qǐng)公開(kāi)了一種基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，該數(shù)據(jù)排序系統(tǒng)用于對(duì)外部存儲(chǔ)模塊中的原始數(shù)據(jù)進(jìn)行歸并排序，系統(tǒng)中的加速模塊用于采用數(shù)據(jù)比較的方式，將獲取到的原始數(shù)據(jù)進(jìn)行分組排序，記作有序子序列數(shù)據(jù)；數(shù)據(jù)輸出模塊用于將有序子序列數(shù)據(jù)輸出至外部存儲(chǔ)模塊；歸并模塊用于獲取外部存儲(chǔ)模塊中的有序子序列數(shù)據(jù)，并采用循環(huán)的方式，對(duì)獲取到的有序子序列數(shù)據(jù)進(jìn)行歸并運(yùn)算，將歸并后的數(shù)據(jù)記作歸并排序數(shù)據(jù)；數(shù)據(jù)輸出模塊還用于將歸并排序數(shù)據(jù)輸出至外部存儲(chǔ)模塊。通過(guò)本申請(qǐng)中的技術(shù)方案，實(shí)現(xiàn)了對(duì)大批量的數(shù)據(jù)在有限的本地存儲(chǔ)空間下進(jìn)行快速排序，并降低資源消耗、提高數(shù)據(jù)排序速度。

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

本申請(qǐng)涉及數(shù)據(jù)處理的技術(shù)領(lǐng)域，具體而言，涉及一種基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)。

背景技術(shù)

在數(shù)據(jù)處理、圖像處理、機(jī)器學(xué)習(xí)等場(chǎng)景中，數(shù)據(jù)排序都是基本的數(shù)據(jù)處理問(wèn)題。據(jù)統(tǒng)計(jì)，在計(jì)算機(jī)完成的所有工作中，有25％～50％的工作內(nèi)容涉及到數(shù)據(jù)排序。除此之外，隨著機(jī)器學(xué)習(xí)、人工智能等技術(shù)的發(fā)展，對(duì)數(shù)據(jù)排序速度以及排序數(shù)量的要求越來(lái)越高。

相比于軟件，利用FPGA進(jìn)行硬件加速可以顯著提升數(shù)據(jù)排序速度，但是常規(guī)的FPGA硬件電路(如FPGA排序器)對(duì)大批量且無(wú)序的原始數(shù)據(jù)進(jìn)行排序時(shí)，由于芯片內(nèi)無(wú)法分出大量存儲(chǔ)空間用于存儲(chǔ)這些數(shù)據(jù)，因此，在對(duì)待排序的數(shù)據(jù)進(jìn)行比較時(shí)，通常用RAM或者FIFO做暫存。

而在這種FPGA硬件電路進(jìn)行數(shù)據(jù)比較的模式下，就會(huì)涉及到對(duì)存儲(chǔ)模塊的持續(xù)讀寫(xiě)控制，不僅增加了FPGA硬件電路數(shù)據(jù)排序?qū)崿F(xiàn)的控制邏輯復(fù)雜性，而且在持續(xù)讀寫(xiě)數(shù)據(jù)的過(guò)程中還需要花費(fèi)額外的時(shí)間，降低了數(shù)據(jù)排序的效率。

發(fā)明內(nèi)容

本申請(qǐng)的目的在于：如何利用FPGA硬件電路以及數(shù)據(jù)讀寫(xiě)控制方法，對(duì)大批量的數(shù)據(jù)在有限的本地存儲(chǔ)空間下進(jìn)行快速排序，并降低資源消耗、提高數(shù)據(jù)排序速度。

本申請(qǐng)的技術(shù)方案是：提供了一種基于歸并排序算法實(shí)現(xiàn)可變規(guī)模數(shù)量的數(shù)據(jù)排序系統(tǒng)，該數(shù)據(jù)排序系統(tǒng)用于對(duì)外部存儲(chǔ)模塊中的原始數(shù)據(jù)進(jìn)行歸并排序，系統(tǒng)包括：加速模塊，歸并模塊以及數(shù)據(jù)輸出模塊；加速模塊用于采用數(shù)據(jù)比較的方式，將獲取到的原始數(shù)據(jù)進(jìn)行分組排序，記作有序子序列數(shù)據(jù)；數(shù)據(jù)輸出模塊用于將有序子序列數(shù)據(jù)輸出至外部存儲(chǔ)模塊；歸并模塊用于獲取外部存儲(chǔ)模塊中的有序子序列數(shù)據(jù)，并采用循環(huán)的方式，對(duì)獲取到的有序子序列數(shù)據(jù)進(jìn)行歸并運(yùn)算，將歸并后的數(shù)據(jù)記作歸并排序數(shù)據(jù)；數(shù)據(jù)輸出模塊還用于將歸并排序數(shù)據(jù)輸出至外部存儲(chǔ)模塊。

上述任一項(xiàng)技術(shù)方案中，進(jìn)一步地，系統(tǒng)還包括：控制模塊以及緩存模塊；控制模塊用于根據(jù)接收到的配置信息，確定讀寫(xiě)數(shù)據(jù)的起始地址、結(jié)束地址以及歸并層數(shù)；緩存模塊用于根據(jù)起始地址、結(jié)束地址，從外部存儲(chǔ)模塊中獲取原始數(shù)據(jù)，并將原始數(shù)據(jù)發(fā)送至加速模塊。

上述任一項(xiàng)技術(shù)方案中，進(jìn)一步地，加速模塊包括：RAM陣列，流水線(xiàn)模塊以及歸并樹(shù)模塊；流水線(xiàn)模塊的兩側(cè)分別設(shè)置有一個(gè)RAM陣列，流水線(xiàn)模塊中設(shè)置有十級(jí)流水，流水線(xiàn)模塊用于采用數(shù)據(jù)比較以及查找表的編碼排序的方式，對(duì)獲取到的原始數(shù)據(jù)進(jìn)行分組排序；歸并樹(shù)模塊用于對(duì)分組排序后的數(shù)據(jù)進(jìn)行歸并，得到有序子序列數(shù)據(jù)。

上述任一項(xiàng)技術(shù)方案中，進(jìn)一步地，加速模塊還用于根據(jù)RAM陣列的緩沖大小，獲取原始數(shù)據(jù)。