[發明專利]一種提高計算機運算速度的并發篩選排序方法

有效

• 申請號: 201810522983.3
• 申請日: 2018-05-28
• 公開（公告）號: CN108762718B
• 公開（公告）日: 2022-03-04
• 發明（設計）人: 卜浩
• 申請（專利權）人: 武漢大學
• 主分類號: G06F7/24
• 分類號: G06F7/24
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 魏波

本發明提供一種提高計算機運算速度的并發篩選排序方法，假設對n個元素的數組A＝[a₁，…，a_i，…，a_n]進行排序，在計算機系統中，構造大小為n×(n+1)的并行處理邏輯矩陣M，矩陣M分為兩部分，矩陣第一列為最左邊一列M₁，M₁按行順序存儲了數組A，剩下方陣為處理邏輯矩陣M₂。M₂中每個元素都稱為篩孔。M₂中第i列存儲的每個元素為數組A中第i個元素。M₁中每行元素即數組A中每個元素并發的發送到處理邏輯矩陣M₂中對應行的每個元素進行篩選，然后將篩選后的結果累加，累加后的結果就是該篩孔所代表的元素在數組中的位置。本發明在資源充足，并發率100％的條件下，可達到排序效率的極限；這對現代計算機系統及今后量子計算機系統的運算速度有極大的影響。

技術領域

本發明屬于計算機技術領域，涉及一種提高計算機運算速度的方法，具體涉及一種提高計算機運算速度的并發篩選排序方法。

背景技術

一般排序算法有兩種分類形式，按算法執行的步驟來分，可以分為串行排序和并發排序。按照元素存儲的方式分，可分為基于鏈表式存儲元素的排序和基于索引式存儲元素的排序。經典排序一般都是基于索引式存儲的串行或并發排序。

串行排序相對比較成熟，比較經典的串行排序算法主要有冒泡排序，選擇排序，插入排序，希爾排序，堆排序，歸并排序以及快速排序等。其中快速排序和歸并排序是經典排序中效率最高的兩種排序方法，其時間復雜度可達到O(nlogn)，在系統中運用十分廣泛。

串行排序算法一般應用在單處理器的環境中。在按一定拓撲結構連接起來的多核多處理器的計算機環境中，為了充分利用計算資源，可以采用并行排序算法來提高排序速度。并行排序算法可以由串行排序算法得來，比如說，快速排序和歸并排序，其中就存在有些步驟可以并發執行。

現在的并行排序算法主要是基于專門的硬件結構來進行設計的，這種專用的硬件排序結構被稱之為排序網絡。

比較經典的排序網絡是Bacther在上世紀60年代在歸并排序的基礎上提出了奇偶歸并網絡和雙調歸并網絡，其排序網絡時間復雜度達到了o(log²n)。Dei Lei Lee和KennthE.Batcher提出了LB網絡，Bruce Parker和Ian Parberry提出了PP排序網絡，這兩種都是基于多路歸并的排序網絡，這兩種排序網絡(假設是k路歸并)時間復雜度達到了O(log_k²n)，并且這兩種排序網絡還需要某些特定歸并硬件器材的支持。

1975年，Murller和Preparata使用更靈活的網絡元件構造了枚舉排序網絡，其時間復雜度為O(logn)，比Bateher排序網絡加速了(logn)倍。可從實用性的角度來看，Bathcer的排序網絡更加簡單易行。

1983年，Ajtai，Komlos和Szemeredi基于擴展圖構造了AKS排序網絡。其時間復雜度為O(logn)。由于無實用的擴展圖結構，因此AKS排序網絡的實現還有一定的難度。并且AKS排序網絡中存在的較大常數也限制了該排序網絡的具體應用。

1994年，Minze.V.Chien和A.Yavuz，ourc提出了適應排序網絡，該排序網絡的時間復雜度與Batcher排序網絡是一樣的，但降低了成本。

計算機系統中除了時間以外，任何資源都可以通過更新換代的方式進行擴容和升級，在宏觀世界中唯獨時間是均勻流逝的。實質上，時間是一種剛性的不可再生的最為稀缺的資源。現代的計算機系統經常會出現在計算資源還存在大量盈余的情況下，程序本身的運行速度已經達到了無法提升的極限。

無論從系統高層還是底層來看，排序操作都是計算機系統中最基本并且使用最頻繁的操作之一，如果能利用計算機并發的特性來提高排序的速度，將極大的提升計算機系統總體的運算速度。