[發明專利]歸并樹形排序裝置、排序系統及排序方法

有效

• 申請號: 202110264743.X
• 申請日: 2021-03-11
• 公開（公告）號: CN113076312B
• 公開（公告）日: 2022-11-18
• 發明（設計）人: 鄢貴海;盧文巖;孔浩
• 申請（專利權）人: 中科馭數（北京）科技有限公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F5/06
• 代理公司: 北京金咨知識產權代理有限公司 11612
• 代理人: 秦景芳

本發明提供了一種歸并樹形排序裝置、排序系統及排序方法，其中，該排序裝置包括：至少兩種輸出數據數量不同的雙調半排序模塊和緩存模塊；輸出數據數量不同的雙調半排序模塊按輸出數據數量從小到大的順序從底層到頂層連接形成歸并樹形結構，且相鄰的兩個輸出數據數量不同的雙調半排序模塊之間連接有緩存模塊；緩存模塊用于緩存累積前一層雙調半排序模塊輸出的數據以滿足后一層雙調半排序模塊的輸入數據數量的要求；每個雙調半排序模塊用于對兩個有序序列進行雙調排序，并在雙調排序過程中完成升序序列和降序序列中的一種序列的排序及輸出且阻塞另一種序列的排序及輸出。通過上述方案能夠實現在一個時鐘周期輸出多個數據，能夠提高排序效率。

技術領域

本發明涉及數據處理技術領域，尤其涉及一種歸并樹形排序裝置、排序系統及排序方法。

背景技術

排序在很多應用場景中發揮關鍵性作用，如數據挖掘、模式識別等。隨著數據量的爆炸式增長，在大規模數據的排序過程中，減小排序延時、增大排序吞吐量顯得越來越重要。考慮到FPGA(Field Programmable Gate Array，現場可編程門陣列)自身具備的并行性、可重配置等特性，將排序算法使用FPGA實現是一個不錯的選擇。

在FPGA上部署排序算法時，為實現任意數據規模的排序，通常會選擇使用歸并排序算法。但是常見的歸并算法一個時鐘周期只能輸出一個數據，極大地限制了排序算法的吞吐量，進而增大了延時。

發明內容

有鑒于此，本發明提供了一種歸并樹形排序裝置、排序系統及排序方法，以實現一個時鐘周期輸出多個數據，以降低延時，實現高效排序。

為了達到上述目的，本發明采用以下方案實現：

根據本發明實施例的一個方面，提供了一種歸并樹形排序裝置，包括：至少兩種輸出數據數量不同的雙調半排序模塊和緩存模塊；

其中，輸出數據數量不同的雙調半排序模塊按輸出數據數量從小到大的順序從底層到頂層連接形成歸并樹形結構，且相鄰的兩個輸出數據數量不同的雙調半排序模塊之間連接有緩存模塊，以及歸并樹形結構中的靠近底層的雙調半排序模塊的輸出端連接與其緊鄰的靠近頂層的雙調半排序模塊的輸入端；緩存模塊用于緩存累積前一層雙調半排序模塊輸出的數據以滿足后一層雙調半排序模塊的輸入數據數量的要求；

每個雙調半排序模塊用于對兩個有序序列進行雙調排序，并在雙調排序過程中完成升序序列和降序序列中的一種序列的排序及輸出且阻塞另一種序列的排序及輸出；各輸出數據數量為多個的雙調半排序模塊用于輸出的序列的排列方式均與目標排序方式一致；

歸并樹形結構中的最底層的雙調半排序模塊用于接收外部輸入的兩個有序序列的數據，最頂層的雙調半排序模塊用于輸出在歸并樹形排序裝置的一次排序中參與排序的所有數據中最靠近目標排序結果頭部的相應數量的數據。

在一些實施例中，歸并樹形結構的層數為：log₂l，l取2的冪次的值，其中，l為所述歸并樹形排序裝置的用于接收外部輸入的有序序列的端口的數量；

各層雙調半排序模塊的輸出數據數量為：i＝0,1,2...(log₂l-1)，p取2的冪次的值，其中，p表示最頂層的雙調半排序模塊的輸出數據數量，表示向上取整。

在一些實施例中，所述緩存模塊為FIFO模塊。

根據本發明實施例的另一個方面，提供了一種排序系統，包括至少一個歸并樹組，每個歸并樹組包括用于流水化數據排序的多個如上述任一實施例所述的歸并樹形排序裝置。

作為本發明實施例一種可選的實施方式，在排序系統包括多個歸并樹組的情況下，各所述歸并樹組的內部結構相同。

作為本發明實施例一種可選的實施方式，所述的排序系統，還包括：預排序模塊；