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

有效

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

1.一種歸并樹形排序裝置，其特征在于，包括：至少兩種輸出數據數量不同的雙調半排序模塊和緩存模塊；

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

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

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

2.如權利要求1所述的歸并樹形排序裝置，其特征在于，

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

各層雙調半排序模塊的輸出數據數量為：p取2的冪次的值，其中，p表示最頂層的雙調半排序模塊的輸出數據數量，表示向上取整。

3.如權利要求1或2所述的歸并樹形排序裝置，其特征在于，所述緩存模塊為FIFO模塊。

4.一種排序系統，其特征在于，包括至少一個歸并樹組，每個歸并樹組包括用于流水化數據排序的多個如權利要求1至3任一項所述的歸并樹形排序裝置。

5.如權利要求4所述的排序系統，其特征在于，在排序系統包括多個歸并樹組的情況下，各所述歸并樹組的內部結構相同。

6.如權利要求4所述的排序系統，其特征在于，還包括：預排序模塊；

所述預排序模塊，用于對外部輸入多個序列分別按目標排序方式進行預排序并將多個預排序后的序列存儲至內存模塊；

所述歸并樹組，用于從內存模塊中獲取多個預排序后的序列，對獲取的多個預排序后的序列中的數據進行排序，并將排序后輸出的有序序列存儲至內存模塊。

7.如權利要求6所述的排序系統，其特征在于，還包括：額外的如權利要求1至3任一項所述的歸并樹形排序裝置，用于對從內存模塊轉存至存儲模塊的多個排序后輸出的有序序列進行排序。

8.如權利要求7所述的排序系統，其特征在于，所述內存模塊為DRAM，和/或所述存儲模塊為SSD或Flash。

9.如權利要求6至8任一項所述的排序系統，其特征在于，所述預排序模塊，用于通過錦標賽排序方式對外部輸入多個序列進行預排序。

10.一種排序方法，其特征在于，適用于如權利要求1至3任一項所述的歸并樹形排序裝置，所述排序方法包括：

利用歸并樹形排序裝置的各輸入端口從相應有序序列獲取相應數量的數據；

利用歸并樹形排序裝置對獲取的所有數據進行排序處理，并輸出獲取的所有數據中部分數據的有序序列；

在歸并樹形排序裝置的輸入端口對應的有序序列中仍存在待獲取數據的情況下，利用歸并樹形排序裝置中未被數據阻塞的輸入端口從相應有序序列繼續獲取相應數量的數據；

利用歸并樹形排序裝置對其中阻塞的數據和繼續獲取的所有數據繼續進行排序處理，并輸出阻塞的數據和繼續獲取的所有數據中部分數據的有序序列；

在歸并樹形排序裝置的所有輸入端口對應的有序序列中均不存在待獲取數據的情況下，確定歸并樹形排序裝置的所有輸入端口對應的有序序列中的所有數據完成排序。