基于雙ibutterfly網絡的插入排序算法

陳 帆，徐金甫，常忠祥

（信息工程大學 密碼工程學院，河南 鄭州450001）

0 引 言

插入排序操作可以將一個序列轉化成任意的指定序列，在密碼算法中有著廣泛的應用，尤其是硬件級的可重構密碼算法的實現方面應用普遍［1］。然而插入排序算法的硬件實現過程比較復雜，如何高效、快速的實現成為密碼算法硬件實現技術的研究熱點之一。

目前主流的方法一般基于ibutterfly （inverse butterfly）網絡來實現插入排序算法，這其中的典型代表有Kolay S等結合歸并算法的思想，利用雙ibutterfly 網絡設計實現的GRP算法［2，3］，其能夠快速實現序列的插入排序操作，提高插入排序操作的實現速度。然而該GRP算法實現過程沒有考慮到序列的自身特點，過多的使用網絡導致序列實現過于復雜。據此，本文針對該算法進行了研究與并提出了改進方案。

文中首先對ibutterfly網絡的置換原理與特性進行了分析，提出了一種利用單個ibutterfly網絡實現插入排序操作復雜度評估的方法，其次基于該評估方法搜尋優選方案，對GRP算法進行了改進，提出一種能夠根據目標序列特點選用不同工作模式的算法，最后給出了改進后方案的實現效率和性能指標。

1 ibutterfly網絡與GRP算法

1.1 butterfly/ibutterfly網絡分析

ibutterfly網絡是實現輸入數據與輸出數據一一對應的排序的較好選擇［4，5］。圖1表示一個n－bit的ibutterfly網絡（n＝8），該網絡有lg（n）級，從左到右依次為第一級、第二級、第三級 （最右邊），每一級由n/2 個2 輸入開關構成，而每一個2輸入開關由兩個二選一數據選擇器組成。

圖1 8－8ibutterfly網絡

數據A、B在開關控制信息Sel的控制下選擇交叉或者直通。n－bit的數據在進入ibutterfly網絡各級時以位置間距為2i－1（i為級數）的行兩兩分組。如第一級ibutterfly網絡中位置7的數據與位置6的數據就組成了一個數據組，第二級中位置7的數據與位置5的數據就組成了一個數據組。然后將分組后的數據輸入到2輸入開關中，在控制信息sel的作用下 “路由”出相應結果。Butterfly網絡是ibutterfly網絡的逆結構［6］，其數據間距為2lg（n）－i。

該網絡具有很好的可拆分性和迭代性，將n—n的ibutterfly網絡的最外層去掉，可以看作兩個 （n/2）— （n/2）的子網絡［7］。如果實現位寬為n/2的操作，只需將網絡最外一層開關置為直通，剩余的控制信息正常配置即可。輸入數據在各級移位的規律性較強，對于不同類型的置換操作，控制信息便于實時生成［8］。

通過對ibutterfly網絡的分析與研究，總結出如圖2所示的排序方式。數據進入ibutterfly網絡后，網絡能夠實現數據按照控制序列中 “0”、 “1”指示排序序列。即將控制序列中為 “1”的控制位對應的原數據依次排在新序列右側，將控制序列中為 “0”的控制位對應的原數據依次逆序排在新序列的左側。

圖2 ibutterfly網絡排序方式

由ibutterfly網絡分析得出的這一排序功能可知：由于控制位列中 “0”所對應的原數據在進入到新序列后順序顛倒了，所以這種實現方式是從右側開始先將與目的序列同序的數據放置后，再將剩余與目的序列順序不同的序列顛倒；如此重復進行，直至完成目的序列順序調整。從上述分析發現，目的序列中數據的排列順序對于插入排序的影響是很大的，因此對于序列數據排列順序的研究是很有必要的。

1.2 GRP算法分析

GRP算法是一種快速高效排序算法，它利用歸并的思想將一個大的排序任務分割成若干個子排序任務，再將子排序任務兩兩組合，并通過指令完成各組合子排序任務，重復此操作直至完成最終排序任務［9，10］。完成全部排序任務所需的指令條數為lg（n）條，很好地限制了指令周期數，即提高了排序操作的運行速度。

GRP算法在實現時是由兩個ibutterfly網絡并行連接而成，通過源序列多次通過ibutterfly網絡實現序列的插入排序［11］。

如圖3所示，GRP算法的運算實現過程共分為3個步驟：①根據歸并算法得到控制信息，將控制信息和控制信息的逆分別同源序列相與得到兩個互補序列。②將兩個互補序列分別送入各自對應的ibutterfly網絡，使得兩個互補序列其中一個序列中數據按指定順序序列排列在輸出序列的左側，同時另一個序列中數據按指定順序序列排列在輸出序列的右側。③將兩個網絡的輸出序列相或，合并為一個序列作為輸出，即可得到目的序列。

圖3 GRP算法硬件實現電路

忽略GRP實現細節，GRP算法的實現則簡化成根據控制序列中 “0”、 “1”指示排列序列。即將控制序列中為“1”的控制位對應的原數據依次排在新序列右側，將控制序列中為 “0”的控制位對應的原數據依次排在新序列左側，以此實現序列的插入排序。

GRP算法結合了ibutterfly網絡與歸并算法的優勢，能夠快速而簡便地實現插入排序操作。但由于GRP算法沒有考慮不同序列的特點，在針對某些特殊序列時，存在嚴重不足。

例如實現8bit序列 （0，1，2，3，4，5，6，7）排序成 （7，6，5，4，3，2，0，1）。對于GRP 網絡，根據排序原則，第一條控制序列為 （0，0，1，0，1，0，1，0），將源序列排列成 （0，1，3，5，7，2，4，6）；第二條控制序列為 （1，1，0，1，0，0，1，0），將序列排列成 （3，7，2，6，0，1，5，4）；第三條控制序列為 （1，0，1，0，1，1，0，0），得到目的序列 （7，6，5，4，3，2，0，1）。實現該操作共需3條指令。如果使用單個ibutterfly網絡，則只需執行1 條控制序列，即 （1，1，0，0，0，0，0，0）。之所以如此，是因為GRP算法只是針對普遍序列的一個算法，沒有考慮不同序列的特點。

2 GRP算法的改進

2.1 插入排序算法復雜度評估算法

定義1 正序列：在一個給定整數序列A1，A2，……Ai，……Aj，……An中，若子序列Ai，……Aj滿足以下條件：i＜i＋1＜i＋2＜……＜j－1＜j，i－1＞i或者i＝1，j＋1＜j或者j＝n，則該子序列為正序列。

例如：對于源序列為 ｛0，1，2，3，4，5，6，7｝，給定的一個序列 ｛1，2，5，7，0，3，6，4｝，其正序列為｛（1，2，5，7），（0，3，6），（4）｝。

定義2 逆序列：在一個給定整數序列A1，A2，……Ai，……Aj，……An，如子序列Ai，……Aj滿足以下條件：i＞i＋1＞i＋2＞……＞j－1＞j，i－1＜i或者i＝1，j＋1＞j或者j＝n，則該子序列為正序列。

例如：對于源序列為 ｛0，1，2，3，4，5，6，7｝，給定的一個序列 ｛1，2，5，4，7，3，6，0｝，其逆序列為｛（1），（2），（5，4），（7，3），（6，0）｝。

用Numh來表示目的序列中正序列個數。用Numd來表示目的序列中降序序列個數。例如：對于源序列為 ｛0，1，2，3，4，5，6，7｝，An＝ ｛1，2，5，7，0，3，6，4｝，Bn＝ ｛1，2，5，4，7，3，6，0｝則Numh（An）＝2，Numd（Bn）＝5。

基于ibutterfly網絡的插入排序算法指令條數的判決值用Num 來表示。（通過Num 能夠成為插入排序算法復雜度評估值）在檢測目的序列開始前，Num＝ “0”。檢測目的序列開始后，按照規定方向輪流檢測正向序列和逆向序列，每檢測出一個單向序列則使Num 加 “1”。

例如：對于源序列為 ｛0，1，2，3，4，5，6，7｝，目的序列為 ｛1，2，5，7，0，3，6，4｝，檢測規則定位為從左往右。

插入算法指令條數判決值的計算步驟為：

（1）檢測得出第一組正向序列為 （1，2，5，7），則Num＝1；

（2）繼續檢測逆向序列為 （0），則Num＝2；

（3）繼續檢測正向序列為 （3，6），則Num＝3；

（4）繼續檢測逆向序列為 （4），則Num＝4，檢測完畢。

所以該例中判決值Num 最終為4。

2.2 單個ibutterfly網絡插入排序算法研究

利用單獨一個ibutterfly網絡，讓數據多次通過網絡實現插入排序。假設存在一個n－bit的整數序列An，要求通過比特置換得到指定序列Bn。An為源序列，Bn為目的序列。按照ibutterfly網絡的排序方式實現排序時，實現排序所需指令條數的判斷方法為：對序列Bn按照從右向左的規則計算插入指令條數判決值；對序列Bn檢測完畢后得出判決值為Num；則從源序列向目的序列轉換所需要的指令個數為 （Num－1）條。

例：源序列為 ｛7，6，5，4，3，2，1，0｝，目的序列為 ｛3，4，2，5，1，6，0，7｝。因此由定義可知，在本次排序中，阿拉伯數字從高到低為正序列，從低到高為逆序列。以此來檢測目的序列。從右向左進行檢測指令個數判決值，檢測結果為： ｛7｝， ｛0｝， ｛6｝， ｛1｝， ｛5｝， ｛2｝，｛4｝，｛3｝。所以Num＝8，指令條數即為n＝Num－1＝7。

假設源序列為 ｛7，6，5，4，3，2，1，0｝，目的序列為 ｛2，7，4，3，5，1，0，6｝。同理檢測，檢測結果為：｛6｝，｛0｝，｛5，1｝，｛3｝，｛7，4｝，｛2｝。所以指令條數為n＝5。

通過實驗可知，多次通過ibutterfly網絡可以實現任意目的序列的插入排序操作，且根據目的序列不同特點，實現排序操作時所需指令條數差異較大。利用ibutterfly 網絡，由源序列 （0，1，2，3，4，5，6，7）通過y條指令實現向任意排列方式的目的序列排序，指令條數y的值在0～7之間。通過matlab仿真，對8bit數據的排序操作進行統計，使用y條指令能夠實現插入排序的目的序列個數及占任意排序組合序列總數的比例結果見表1。

表1 8比特排序指令個數

通過統計可知，8bit序列的不同排布方式共有40320種，且實現排序操作占用不超過3條指令 （包含3條指令）的序列個數共占總序列數的19.37%。

因為通過單一的ibutterfly網絡來實現排序時，使用1條、2條、3條指令的序列所需指令條數與GRP 算法是不一樣的，且只用到一個ibutterfly網絡。所以將改進的GRP算法針對這些特殊序列進行特殊操作，能有效提升GRP算法的速度和效率。

2.3 GRP算法的改進

由2.2節可知，在8bit序列排序過程中，在全部目的序列中有19%左右的序列在由源序列排序過程中只需要3條以下的指令個數 （包括3條）。將這些序列定義為特殊序列。對于這些特殊的序列而言，可通過單個ibutterfly網絡很方便的就能實現，而GRP算法中依然需要兩個ibutterfly網絡配合完成。不能發揮出GRP算法的優勢，反而增加了實現的復雜程度。

基于以上分析，本文提出GRP算法的改進算法，改進后實現電路結構如圖4所示。

圖4 GRP改進算法的電路結構

在改進的GRP算法中，通過模式選擇信號控制兩個二選一數據選擇器。當模式為單個ibutterfly網絡工作時，則通過模式選擇信號控制數據選擇器選擇全 “1”序列進入電路，與源序列相與，同時在輸出時選擇單個ibutterfly輸出的結果作為最終輸出。當模式為GRP操作時，則通過模式選擇信號控制數據選擇器選擇控制序列進入電路，與源序列相與，同時在輸出時將兩個ibutterfly網絡結果相或后作為最終輸出。

改進后GRP算法執行時，在開始排序操作前，首先通過對目的序列特點的分析，先利用2.1節提出的評估算法判斷序列通過單個ibutterfly網絡所需指令個數。如果通過單個ibutterfly網絡所需的指令個數已經小于lg（n）條指令了。則發出模式選擇信號，啟動單個ibutterfly網絡來實現插入排序操作。

如果通過2.1節評估算法得出通過單個ibutterfly網絡所需的指令個數大于lg（n）條指令，則發出模式選擇信號，啟動全部網絡共同工作，完成插入排序操作。

3 性能評估

以8bit位寬序列為例，在實現排序過程中，特殊序列占整體序列的比重由表1可知，其中有19.37%數量的序列為特殊序列，不需使用GRP網絡，而只需開啟一個ibutterfly網絡，用與GRP相同的指令數即可實現排序操作。如圖5所示，特殊序列的數量會隨數據位寬的增加而顯著增加。所以隨著位寬的增加，GRP算法改進的效果會更加明顯。

硬件實現前后硬件開銷對比見表2。

圖5 特殊序列數量隨數據位寬變化趨勢

表2 硬件實現前后硬件開銷對比

綜合分析，在針對一些特殊插入排序操作時，例如DES加密運算中的P序操作，恰好使用的就是這些特殊序列。因此本文設計雖然略微增加了GRP硬件實現資源，但彌補了其應用的靈活性。

本文提出結合序列自身特點對GRP算法進行改進，改進后的GRP 算法針對不同的序列特點選擇相應的工作模式，有效地增強了GRP算法的速度和效率。

4 結束語

由于GRP算法具有自身不足，即實現特殊序列的插入排序時效率不高。因此本文針對GRP算法的不足，提出了GRP算法的改進的算法。通過加入序列自身特點的分析和歸納，提出了一種基于ibutterfly網絡下的簡便插入排序操作復雜度評估規律。通過分析比較，通過評估規律對序列進行分析后，在改進后的GRP 算法中選擇合適的工作模式，能夠高效地實現插入排序操作。

［1］Nan Longmei，Dai Zhibin.Design and implementation of configurable extract instructions targeted at stream cipher processing ［C］//Sth International Conference on ASIC，2009.

［2］Yedidya Hilewitz.A new basis for shifters in general－purpose processors or exiting and advanced bit manipulations［J］.IEEE Transactions on Computers，2009，58 （8）：1035－1048.

［3］Kolay S，Khurana S，Sadhukhan A，et al.Bit permutation instructions for accelerating software cryptography ［C］//IEEE Conference Publications，2013：963－968.

［4］Li Hongyan，Gao Fei.Design and implementation of reconfigurable bit permutation system based on Waksman network［C］//IEEE Conference Publications，2010：113－116.

［5］Su Yang.Research of design technology of reconfigurable shift unit based on multilevel interconnection ［J］.Intelligent System and Applied Material，Advanced Materials Research，Advanced Materials Research，2012，466：1065－1069.

［6］Hilewitz Yedidya.Advanced bit manipulation instructions：Architecture，implementation and applications［D］.New Jersey：Princeton University，2008.

［7］Azaria Paz.A theory of decomposition into prime factors of layered interconnection networks ［J］.Discrete Applied Mathematics，2011，159 （7）：628－649

［8］John Garoflakis，Eleftherios Stergiou.An analytical model for the performance evaluation of multistage interconnection networks with two class priorities ［J］.Future Generation Computer Systems，2013，29 （1）：114－129.

［9］David Arroyo，JesusDiaz FB Rodriguez.Cryptanalysis of a one round chaos－based substitution permutation network ［J］.Signal Processing，2013，93 （5）：1358－1364.

［10］Hilewitz Y，Ruby B Lee.Fast bit gather，bit scatter and bit permutation instructions for commodity microprocessors ［J］.J Signal Processing Systems，2008，53 （1－2）：145－169.

［11］John Garofalakis，Eleftherios Stergiou.Analytical model for the performance evaluation of multilayer multistage interconnection networks servicing unicast and multicast traffic by partial multicast operation ［J］.Performance Evaluation，2010，67 （10）：959－976.