文獻標識碼： A
文章編號： 0258-7998(2014)07-0065-04
移數置換和p序置換是芯片設計中的兩種重要置換。移數置換用于實現處理器中移位功能，是完成地址產生和算術邏輯運算等功能必不可少的部分。p序置換廣泛應用于數據加密、圖像處理和數字信號處理等領域，是完成數據擴散的重要方法。隨著微電子技術的不斷進步，特別是芯片可重構技術的興起和發(fā)展[1]，芯片設計對移數置換和p序置換功能的并行性、靈活性和可擴展性提出了更高要求。目前，p序置換主要采用基本操作組合和比特置換方式實現，靈活性和可擴展性不強。移數置換功能實現方式主要有對數移位器、桶形移位器、基于互連網絡的移位器等[2-3]。對數移位器實現單一移位功能時，速度和面積優(yōu)勢較大，但同時支持各類移位操作時，布線資源較大，且電路靈活性不高[4]；桶形移位器[5]主要用于實現循環(huán)左移或循環(huán)右移操作，不能很好地支持短字移位操作，電路靈活性不高；基于互連網絡的移位器[6]對網絡的互連函數和拓撲結構沒有充分利用，提出的路由算法硬件實現較為復雜，硬件資源消耗和電路延遲較大。
針對以上問題，本文結合Butterfly網絡互連函數和拓撲結構特點，將移數置換和p序置換的架構進行合并，提出了基于Butterfly網絡的移數p序統(tǒng)一架構，分析并提取出支持該架構的路由算法。
1 基于Butterfly網絡的移數p序統(tǒng)一架構
Butterfly網絡是典型的動態(tài)多級阻塞網絡，其并行性好，可拆分性強，支持短字置換和并行操作，能夠滿足移數置換和p序置換對靈活性、并行性和可擴展性的要求。同時，Butterfly網絡實現移數置換和p序置換的原理相似，便于兩者架構的合并，因此成為實現移數p序統(tǒng)一架構的首選。
1.1 Butterfly網絡結構分析
一個N-N的Butterfly網絡由log2 N個開關級組成，整個網絡的開關量為(N/2)log2N。每個開關有直通和交叉兩種狀態(tài)，整個網絡有2k(k=N/2log2N)種開關狀態(tài)，理論上能實現2k種置換，每種置換對應的路由信息唯一。
以8-8 Butterfly為例說明，如圖1所示，左端為源端（輸入端），右端為終端（輸出端），開關級從左到右依次為第1級、第2級、第3級，級與級之間為子蝶式變換。
本文以Butterfly網絡為基礎，實現移數p序統(tǒng)一架構，同時提取出適應于該架構的路由算法，支持路由信息實時生成和配置。
1.2 移數p序統(tǒng)一架構設計
Butterfly網絡分別實現移數置換和p序置換時，兩者的數據傳輸網絡相同，路由信息生成算法互有交叉，因此兩者可以采用統(tǒng)一的架構來實現。
如圖2所示，該架構由Butterfly數據鏈路和路由算法兩部分組成。其中Butterfly數據鏈路用于移數p序置換的數據傳輸；路由算法用于生成移數p序置換的路由信息。本文的關鍵在于路由算法的實現。
2 路由算法分析、提取與硬件實現
2.1 路由算法分析
移數置換和p序置換路由信息生成方式相同，除網絡中第1級開關的路由信息外，其他開關級開關的路由信息都可以由上一級相連開關的路由信息通過對應的布爾運算得到：
(1)實現移數置換時，該布爾運算為異或運算。
(2)實現p序置換時，根據參數p的值來決定，若(p-1)/2為偶數，則該布爾運算為異或運算；若(p-1)/2為奇數，則該布爾運算為等值運算。
將第1級開關路由信息稱為初始條件，則只要初始條件確定，后面每一級開關的路由信息都可以由初始條件逐級生成。
2.2 路由算法提取
2.2.1 移數置換和 p序置換路由算法提取
為提取出移數p序統(tǒng)一架構的路由算法，先對移數置換和p序置換各自的路由算法進行提取。將N-N Butterfly網絡的源端位置信息記為k，相應的終端位置信息記為D(k)，則D(k)可以由k計算得到。
(1)移數置換時，D(k)=(k+s) mod N，s為移位位數；
(2)p序置換時，D(k)=p·k mod N，p為置換參數，且p為奇數。
將k到D(k)的路由信息記為C(k)，則移數置換和p序置換中k、D(k)、C(k)三者之間關系相同，為：
通過對k（k=0，1，2，…，N-1）遍歷取值，就可計算出架構的所有路由信息。取所有路由信息最高比特，得到該架構路由信息的初始條件，再通過相鄰開關級之間的關系，便可逐級完成所有路由信息的適配。
在此基礎上，本文將移數置換和p序置換的路由算法進行合并，提取出適用于移數p序統(tǒng)一架構的路由算法。
2.2.2 移數p序統(tǒng)一架構路由算法提取
移數p序統(tǒng)一架構路由算法的提取過程如下：
（1）終端位置信息計算表達式為：
其中，N為數據位寬，k為比特數據在輸入端的位置信息，p為置換參數，s為移位位數。
（2）該數據從輸入端到輸出端的路由信息為：
其中，C(k)為 k到D(k)的路由信息。k分別取值0，1，…，N/2-1，得到架構所有的路由信息，然后便可進行路由信息的適配。
（3）用C0[N/2-1:0]表示路由信息初始條件，取每組路由信息的最高比特，得到路由信息初始條件為：
初始條件生成后，根據網絡互連關系，逐級完成第1，2，…，log2N-1級開關的路由信息的適配。
該路由算法描述如下：
算法1：移數p序統(tǒng)一架構路由算法
輸入：s∈{0，1，…，N-1}；p(0<p<N，p為奇數)；Mode∈{0，1}；
其中，N為Butterfly網絡的數據寬度；Mode為置換類型選擇信號；0表示移數置換；1表示p序置換；s為移位位數；p為置換參數；k為Butterfly網絡輸入端的位置信息；Ci(i=0，…，N/2-1)為Butterfly網絡第i級開關路由信息。
上述路由算法能夠完成基于Butterfly網絡的移數p序統(tǒng)一架構所需路由信息的生成和適配。根據算法描述，可以實現其硬件電路。
2.3 路由算法硬件實現
移數p序統(tǒng)一架構的路由算法硬件電路包括兩部分：初始條件生成電路和路由信息生成適配電路。
（1）初始條件生成電路的硬件實現
初始條件生成電路用于生成路由信息初始條件，移數p序統(tǒng)一架構路由算法的初始條件生成電路的硬件實現如圖3所示。
圖3中，初始條件生成電路由模加單元、模乘單元、與運算單元、數據選擇器、異或網絡和輸出網絡組成，整個系統(tǒng)計算并得到路由信息初始條件C0[N/2-1:0]。
（2）路由信息生成適配電路的硬件實現
路由信息生成適配電路以初始條件為輸入，完成整個Butterfly網絡路由信息的生成和適配。以16-16 Butterfly網絡為例說明，如圖4所示。
移數p序統(tǒng)一架構的路由信息生成和適配完成后，在路由信息的控制下，數據經過數據鏈路，完成移數p序統(tǒng)一架構的整體功能。
3 性能分析
3.1 架構性能分析
本設計采用64 bit數據位寬，在CMOS 0.065 ?滋m工藝下進行綜合優(yōu)化，得到了本設計的資源消耗和電路延遲，如表1所示。
單獨實現移數置換和p序置換功能時，p序置換的資源消耗和電路延遲比移數置換大。實現移數p序統(tǒng)一架構整體功能時，由于移數置換和p序置換的硬件電路共用，與兩者單獨實現相比，資源消耗和電路延遲增加都不大。
3.2 架構性能擴展
在CMOS 0.065 ?滋m工藝下，分別對數據位寬為8 bit、16 bit、32 bit、64 bit、128 bit、256 bit、512 bit的移數p序統(tǒng)一架構進行綜合優(yōu)化，得到本架構在不同數據位寬下的性能擴展趨勢，如圖5所示。
隨著數據位寬的增加，本架構在資源消耗和電路延遲方面都會增加。其中，資源消耗的增長幅度先增大后減小，電路延遲的增長幅度逐漸變小。小位寬時，本架構資源消耗和電路延遲隨數據位寬的增加增長較快；在大數據位寬下，隨著數據位寬的增加，用Butterfly網絡實現移數和p序置換的方式在資源消耗和電路延遲方面優(yōu)勢明顯，資源消耗和電路延遲的增長幅度逐漸減小。
3.3 架構性能對比
由于目前p序置換主要以基本操作組合的方式或比特置換的方式實現，不便于性能比較，因此，本文重點將本架構的移數置換功能與對數移位器、參考文獻[2]和參考文獻[3]中的移位部件進行性能對比。在COMS 0.065 ?滋m工藝下，其對比結果如表2所示，性能對比如圖6所示。
由圖6可知，只實現單向移位（循環(huán)左移）時，對數移位器面積最小且速度最快，但其靈活性不高，不支持短字移位操作，且當擴展其功能以實現多種類型的移位操作時，資源消耗增長過快。參考文獻[2]中桶形移位器與本設計相比，其電路延遲稍小，但資源消耗較大，且靈活性不高，不支持短字移位，同時，進行功能擴展時，資源消耗和電路延遲都大幅度增加[3]。參考文獻[2]中I-BFLY移位器靈活性較高，功能擴展性較強，且支持短字置換，但其控制信息生成算法較為復雜，資源消耗和電路延遲都較大。本設計在保證較高靈活性、較強功能擴展性、支持短字置換和并行操作的前提下，與I-BFLY移位器[1]相比，面積節(jié)省了30.0%且速度提升了17.6%。此外，本架構不僅支持1組64 bit位寬下移數和p序置換，同時還支持2組32 bit位寬、4組16 bit位寬的移數和p序置換。
本文設計并實現了Butterfly網絡下的移數p序統(tǒng)一架構，分析并提取出相應的路由算法，并對算法進行了硬件實現。通過對該架構進行性能評估，結果表明，本設計靈活性高，功能擴展性強，且支持短字置換和并行操作，和I-BFLY移位器[2]相比，面積節(jié)省了30.0%且速度提升了17.6%。
參考文獻
[1] 于學榮，戴紫彬.可重構移位單元的設計與實現[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.