移數(shù)置換和p序置換是芯片設計中的兩種重要置換。移數(shù)置換用于實現(xiàn)處理器中移位功能，是完成地址產(chǎn)生和算術邏輯運算等功能必不可少的部分。p序置換廣泛應用于數(shù)據(jù)加密、圖像處理和數(shù)字信號處理等領域，是完成數(shù)據(jù)擴散的重要方法。隨著微電子技術的不斷進步，特別是芯片可重構技術的興起和發(fā)展^[1]，芯片設計對移數(shù)置換和p序置換功能的并行性、靈活性和可擴展性提出了更高要求。目前，p序置換主要采用基本操作組合和比特置換方式實現(xiàn)，靈活性和可擴展性不強。移數(shù)置換功能實現(xiàn)方式主要有對數(shù)移位器、桶形移位器、基于互連網(wǎng)絡的移位器等[^2-3]。對數(shù)移位器實現(xiàn)單一移位功能時，速度和面積優(yōu)勢較大，但同時支持各類移位操作時，布線資源較大，且電路靈活性不高^[4]；桶形移位器^[5]主要用于實現(xiàn)循環(huán)左移或循環(huán)右移操作，不能很好地支持短字移位操作，電路靈活性不高；基于互連網(wǎng)絡的移位器^[6]對網(wǎng)絡的互連函數(shù)和拓撲結構沒有充分利用，提出的路由算法硬件實現(xiàn)較為復雜，硬件資源消耗和電路延遲較大。

        針對以上問題，本文結合Butterfly網(wǎng)絡互連函數(shù)和拓撲結構特點，將移數(shù)置換和p序置換的架構進行合并，提出了基于Butterfly網(wǎng)絡的移數(shù)p序統(tǒng)一架構，分析并提取出支持該架構的路由算法。

1 基于Butterfly網(wǎng)絡的移數(shù)p序統(tǒng)一架構

        Butterfly網(wǎng)絡是典型的動態(tài)多級阻塞網(wǎng)絡，其并行性好，可拆分性強，支持短字置換和并行操作，能夠滿足移數(shù)置換和p序置換對靈活性、并行性和可擴展性的要求。同時，Butterfly網(wǎng)絡實現(xiàn)移數(shù)置換和p序置換的原理相似，便于兩者架構的合并，因此成為實現(xiàn)移數(shù)p序統(tǒng)一架構的首選。

1.1 Butterfly網(wǎng)絡結構分析

        一個N-N的Butterfly網(wǎng)絡由log2 N個開關級組成，整個網(wǎng)絡的開關量為(N/2)log₂N。每個開關有直通和交叉兩種狀態(tài)，整個網(wǎng)絡有2^k(k=N/2log₂N)種開關狀態(tài)，理論上能實現(xiàn)2^k種置換，每種置換對應的路由信息唯一。

        以8-8 Butterfly為例說明，如圖1所示，左端為源端（輸入端），右端為終端（輸出端），開關級從左到右依次為第1級、第2級、第3級，級與級之間為子蝶式變換。

        本文以Butterfly網(wǎng)絡為基礎，實現(xiàn)移數(shù)p序統(tǒng)一架構，同時提取出適應于該架構的路由算法，支持路由信息實時生成和配置。

1.2 移數(shù)p序統(tǒng)一架構設計

        Butterfly網(wǎng)絡分別實現(xiàn)移數(shù)置換和p序置換時，兩者的數(shù)據(jù)傳輸網(wǎng)絡相同，路由信息生成算法互有交叉，因此兩者可以采用統(tǒng)一的架構來實現(xiàn)。

        如圖2所示，該架構由Butterfly數(shù)據(jù)鏈路和路由算法兩部分組成。其中Butterfly數(shù)據(jù)鏈路用于移數(shù)p序置換的數(shù)據(jù)傳輸；路由算法用于生成移數(shù)p序置換的路由信息。本文的關鍵在于路由算法的實現(xiàn)。

2 路由算法分析、提取與硬件實現(xiàn)

2.1 路由算法分析

        移數(shù)置換和p序置換路由信息生成方式相同，除網(wǎng)絡中第1級開關的路由信息外，其他開關級開關的路由信息都可以由上一級相連開關的路由信息通過對應的布爾運算得到：

        (1)實現(xiàn)移數(shù)置換時，該布爾運算為異或運算。

        (2)實現(xiàn)p序置換時，根據(jù)參數(shù)p的值來決定，若(p-1)/2為偶數(shù)，則該布爾運算為異或運算；若(p-1)/2為奇數(shù)，則該布爾運算為等值運算。

        將第1級開關路由信息稱為初始條件，則只要初始條件確定，后面每一級開關的路由信息都可以由初始條件逐級生成。

2.2 路由算法提取

2.2.1 移數(shù)置換和 p序置換路由算法提取

       為提取出移數(shù)p序統(tǒng)一架構的路由算法，先對移數(shù)置換和p序置換各自的路由算法進行提取。將N-N Butterfly網(wǎng)絡的源端位置信息記為k，相應的終端位置信息記為D(k)，則D(k)可以由k計算得到。

        (1)移數(shù)置換時，D(k)=(k+s) mod N，s為移位位數(shù)；

        (2)p序置換時，D(k)=p·k mod N，p為置換參數(shù)，且p為奇數(shù)。

        將k到D(k)的路由信息記為C(k)，則移數(shù)置換和p序置換中k、D(k)、C(k)三者之間關系相同，為：

        通過對k（k=0，1，2，…，N-1）遍歷取值，就可計算出架構的所有路由信息。取所有路由信息最高比特，得到該架構路由信息的初始條件，再通過相鄰開關級之間的關系，便可逐級完成所有路由信息的適配。

        在此基礎上，本文將移數(shù)置換和p序置換的路由算法進行合并，提取出適用于移數(shù)p序統(tǒng)一架構的路由算法。

2.2.2 移數(shù)p序統(tǒng)一架構路由算法提取

        移數(shù)p序統(tǒng)一架構路由算法的提取過程如下：

        （1）終端位置信息計算表達式為：

其中，N為數(shù)據(jù)位寬，k為比特數(shù)據(jù)在輸入端的位置信息，p為置換參數(shù)，s為移位位數(shù)。

        （2）該數(shù)據(jù)從輸入端到輸出端的路由信息為：

其中，C(k)為 k到D(k)的路由信息。k分別取值0，1，…，N/2-1，得到架構所有的路由信息，然后便可進行路由信息的適配。

        （3）用C0[N/2-1:0]表示路由信息初始條件，取每組路由信息的最高比特，得到路由信息初始條件為：

        初始條件生成后，根據(jù)網(wǎng)絡互連關系，逐級完成第1，2，…，log₂N-1級開關的路由信息的適配。

        該路由算法描述如下：

        算法1：移數(shù)p序統(tǒng)一架構路由算法

        輸入：s&isin;{0，1，&hellip;，N-1}；p(0<p<N，p為奇數(shù))；Mode&isin;{0，1}；

其中，N為Butterfly網(wǎng)絡的數(shù)據(jù)寬度；Mode為置換類型選擇信號；0表示移數(shù)置換；1表示p序置換；s為移位位數(shù)；p為置換參數(shù)；k為Butterfly網(wǎng)絡輸入端的位置信息；C_i(i=0，&hellip;，N/2-1)為Butterfly網(wǎng)絡第i級開關路由信息。

上述路由算法能夠完成基于Butterfly網(wǎng)絡的移數(shù)p序統(tǒng)一架構所需路由信息的生成和適配。根據(jù)算法描述，可以實現(xiàn)其硬件電路。

2.3 路由算法硬件實現(xiàn)

移數(shù)p序統(tǒng)一架構的路由算法硬件電路包括兩部分：初始條件生成電路和路由信息生成適配電路。

（1）初始條件生成電路的硬件實現(xiàn)

初始條件生成電路用于生成路由信息初始條件，移數(shù)p序統(tǒng)一架構路由算法的初始條件生成電路的硬件實現(xiàn)如圖3所示。

圖3中，初始條件生成電路由模加單元、模乘單元、與運算單元、數(shù)據(jù)選擇器、異或網(wǎng)絡和輸出網(wǎng)絡組成，整個系統(tǒng)計算并得到路由信息初始條件C0[N/2-1:0]。

（2）路由信息生成適配電路的硬件實現(xiàn)

路由信息生成適配電路以初始條件為輸入，完成整個Butterfly網(wǎng)絡路由信息的生成和適配。以16-16 Butterfly網(wǎng)絡為例說明，如圖4所示。

移數(shù)p序統(tǒng)一架構的路由信息生成和適配完成后，在路由信息的控制下，數(shù)據(jù)經(jīng)過數(shù)據(jù)鏈路，完成移數(shù)p序統(tǒng)一架構的整體功能。

3 性能分析

3.1 架構性能分析

本設計采用64 bit數(shù)據(jù)位寬，在CMOS 0.065 ?滋m工藝下進行綜合優(yōu)化，得到了本設計的資源消耗和電路延遲，如表1所示。

單獨實現(xiàn)移數(shù)置換和p序置換功能時，p序置換的資源消耗和電路延遲比移數(shù)置換大。實現(xiàn)移數(shù)p序統(tǒng)一架構整體功能時，由于移數(shù)置換和p序置換的硬件電路共用，與兩者單獨實現(xiàn)相比，資源消耗和電路延遲增加都不大。

3.2 架構性能擴展

在CMOS 0.065 ?滋m工藝下，分別對數(shù)據(jù)位寬為8 bit、16 bit、32 bit、64 bit、128 bit、256 bit、512 bit的移數(shù)p序統(tǒng)一架構進行綜合優(yōu)化，得到本架構在不同數(shù)據(jù)位寬下的性能擴展趨勢，如圖5所示。

隨著數(shù)據(jù)位寬的增加，本架構在資源消耗和電路延遲方面都會增加。其中，資源消耗的增長幅度先增大后減小，電路延遲的增長幅度逐漸變小。小位寬時，本架構資源消耗和電路延遲隨數(shù)據(jù)位寬的增加增長較快；在大數(shù)據(jù)位寬下，隨著數(shù)據(jù)位寬的增加，用Butterfly網(wǎng)絡實現(xiàn)移數(shù)和p序置換的方式在資源消耗和電路延遲方面優(yōu)勢明顯，資源消耗和電路延遲的增長幅度逐漸減小。

3.3 架構性能對比

由于目前p序置換主要以基本操作組合的方式或比特置換的方式實現(xiàn)，不便于性能比較，因此，本文重點將本架構的移數(shù)置換功能與對數(shù)移位器、參考文獻[2]和參考文獻[3]中的移位部件進行性能對比。在COMS 0.065 ?滋m工藝下，其對比結果如表2所示，性能對比如圖6所示。

由圖6可知，只實現(xiàn)單向移位（循環(huán)左移）時，對數(shù)移位器面積最小且速度最快，但其靈活性不高，不支持短字移位操作，且當擴展其功能以實現(xiàn)多種類型的移位操作時，資源消耗增長過快。參考文獻[2]中桶形移位器與本設計相比，其電路延遲稍小，但資源消耗較大，且靈活性不高，不支持短字移位，同時，進行功能擴展時，資源消耗和電路延遲都大幅度增加[3]。參考文獻[2]中I-BFLY移位器靈活性較高，功能擴展性較強，且支持短字置換，但其控制信息生成算法較為復雜，資源消耗和電路延遲都較大。本設計在保證較高靈活性、較強功能擴展性、支持短字置換和并行操作的前提下，與I-BFLY移位器[1]相比，面積節(jié)省了30.0%且速度提升了17.6%。此外，本架構不僅支持1組64 bit位寬下移數(shù)和p序置換，同時還支持2組32 bit位寬、4組16 bit位寬的移數(shù)和p序置換。

本文設計并實現(xiàn)了Butterfly網(wǎng)絡下的移數(shù)p序統(tǒng)一架構，分析并提取出相應的路由算法，并對算法進行了硬件實現(xiàn)。通過對該架構進行性能評估，結果表明，本設計靈活性高，功能擴展性強，且支持短字置換和并行操作，和I-BFLY移位器[2]相比，面積節(jié)省了30.0%且速度提升了17.6%。

參考文獻

[1] 于學榮，戴紫彬.可重構移位單元的設計與實現(xiàn)[J].微計

     算機信息，2007，13(6)：22-28.

[2] BURGESS N.Assessment of Butterfly network VLSI shifter 

     circuit[C].IEEE Conference Publications：Signals，Systems 

     and Computers(ASILOMAR)，2010 Conference Record of 

     the Forty Fourth Asilomar Conference on，2010：92-96.

[3] DAS S，KHATRI S P.A timing-driven approach to synthe-

     size fast barrel shifters[J].IEEE Transactions on Circuits 

     and Systems-II：Express Briefs，2008，55(1)：31-35.

[4] Su Yang，Dai Zibin，Li Wei.Research of design technology 

     of reconfigurable shift unit based on multilevel interconnec-

     tion[J].Intelligent System and Applied M-aterial，Advanced 

     Materials Research，2012(2)：1065-1069.

[5] 華校專.定點除法器與向量ALU移位器設計[D].長沙：

     國防科學技術大學，2010.

[6] YEDIDYA H.Advanced bit ma-nipulation instructions：

     architecture，implementation and applications[D].New Jersey，

     Princeton University，2008.