[發(fā)明專利]一種歸并排序結構

無效

• 申請?zhí)枺?/td>: 201310106487.7
• 申請日: 2013-03-29
• 公開（公告）號: CN103226464A
• 公開（公告）日: 2013-07-31
• 發(fā)明（設計）人: 柴志雷
• 申請（專利權）人: 江蘇復芯物聯(lián)網科技有限公司
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 無錫盛陽專利商標事務所(普通合伙) 32227
• 代理人: 顧吉云

技術領域

本發(fā)明涉及排序算法領域，具體為一種歸并排序結構。

背景技術

排序算法在科學技術領域已經有了極其詳盡的研究，已有許多成熟的排序算法，近年來，在不同的應用下也提出了多種基于FPGA的排序方法，根據(jù)應用的不同，基于FPGA的排序一般分為兩類：基于網絡的排序和基于線性數(shù)組的排序。

基于網絡的排序一般使用兩輸入的交換比較器來排序，Zhang,?Y.采用了固定大小的排序網絡，分為輸入隊列，乒乓排序網絡，和輸出檢測模塊。Martinez?et?al.?提出了應用在塊排序壓縮上的網絡排序算法，采用了乒乓操作，實現(xiàn)數(shù)據(jù)循環(huán)處理，排序單元處理128個字符，最終的結果顯示可達到的最大時鐘頻率為50MHZ左右。基于線性數(shù)組的排序基于可擴展的線性數(shù)組，Paraham,Kwai采用比較/插入單元，每個單元包含比較器，乘法器和控制單元，可擴展線性數(shù)組包含一系列的單元。K.?Ratnayake?和A.?Amer提出了計數(shù)排序算法，不過他們是在BRAMS上實現(xiàn)排序算法，較為復雜，M.?Edahiro在EDK的開發(fā)環(huán)境下實現(xiàn)了并行的排序算法。

縱觀以上排序算法，有的是針對特殊應用的排序，有的在對有限的數(shù)據(jù)排序的時候，資源利用率較高的同時，最大時鐘頻率很低，無法滿足對于高清實時圖片的特征點排序的要求。

歸并排序是建立在歸并操作上的一種有效排序算法，歸并操作是將兩個或兩個以上有序隊列合并成一組新的有序表，舉例如下，若已知兩組有序隊列分別為1,3,5和2,4,6，見圖1所示，兩路歸并操作，A，B分別為排完序的有序隊列，C為A，B的歸并結果，其歸并步驟如下：

1、分別取A，B的隊頭，設a，b，比較a，b兩者的大小；（比較操作）

2、a，b中較大者出隊，放入緩存tmp中；（出隊操作）

3、tmp壓入C的隊尾；（入隊操作）

重復步驟1-3直到A，B中一個為空，執(zhí)行步驟4；

4、A/B為空，將B/A隊頭放入tmp中；（出隊操作）

5、將tmp壓入C的隊尾；（入隊操作）

重復步驟5-6，直到A，B兩者都為空。

一種基于歸并操作的歸并排序，設待排序的數(shù)列為D[n]，數(shù)列的長度為N，其歸并步驟如下所述：將D[n]分為N個已排完序的長度為1的隊列，兩兩之間運行用歸并操作，合并成floor[n/2]個兩兩有序的隊列，循環(huán)進行之，兩兩之間進行歸并操作，直到最后合并成一個N有序的隊列，舉例見圖2所示，數(shù)列為1，3，5，2，4，6，對其進行歸并排序，步驟如下

1、將隊列中1和3,5和2,4和6進行歸并操作得到3個隊列3,1和5,2及6,4；

2、將隊列3,1和5,2記性歸并操作得到隊列5,3,2,1；

3、將隊列5,3,2,1與隊列6,4進行歸并操作得到有序隊列6,5,4,3,2,1。

以上歸并排序的是基于PC操作，其算法比較簡單，適用于多種隊列的排序，歸并排序效率高且穩(wěn)定，但是比較占用內存，其時間復雜度為O（Nlog（N）），空間負責度是O（N）。

發(fā)明內容

為了解決上述問題，本發(fā)明提供了一種歸并排序結構，其利用FPGA結構實現(xiàn)歸并排序的操作，實現(xiàn)資源和效率的最大化，能夠完全滿足對于高清實時圖片的特征點排序的要求，且時間復雜度優(yōu)于基于PC操作的歸并排序。

其技術方案是這樣的：一種歸并排序結構，其特征在于，其包括歸并組件，所述歸并組件包括存儲的隊列，所述隊列連接比較器和輔助控制器，所述輔助控制器上設置有計數(shù)所述隊列出隊或入隊操作的計數(shù)器。

其進一步特征在于，所述存儲的隊列包括兩個隊列寄存器，兩個所述隊列寄存器連接所述比較器，兩個所述隊列寄存器分別連接所述輔助控制器；所述比較器采用上升沿觸發(fā)；所述輔助控制器設置有計數(shù)每個所述隊列寄存器的出隊或入隊的計數(shù)器。

其進一步特征在于，所述存儲的隊列包括兩個FIFO，所述輔助控制器包括時序邏輯輔助控制器和組合邏輯輔助控制器，所述時序邏輯輔助控制器和所述組合邏輯輔助控制器分別連接所述FIFO，所述FIFO分別設置有FIFOIN和FIFOOUT端口，所述其中一個FIFO的FIFOOUT端口連接所述另一個FIFO的FIFOIN端口，讀信號口、寫信號口分別連接所述FIFO；所述FIFO的FIFOOUT端口分別連接比較器，所述時序邏輯輔助控制器設置有計數(shù)所述每個所述FIFO出隊或入隊操作的計數(shù)器；