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

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

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

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

1.1 Butterfly網(wǎng)絡(luò)結(jié)構(gòu)分析

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

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

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

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

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

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

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

2.1 路由算法分析

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

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

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

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

2.2 路由算法提取

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

       為提取出移數(shù)p序統(tǒng)一架構(gòu)的路由算法，先對移數(shù)置換和p序置換各自的路由算法進(jìn)行提取,。將N-N Butterfly網(wǎng)絡(luò)的源端位置信息記為k,，相應(yīng)的終端位置信息記為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)三者之間關(guān)系相同，為：

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

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

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

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

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

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

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

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

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

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

        該路由算法描述如下：

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

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

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

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

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

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

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

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

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

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

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

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

3 性能分析

3.1 架構(gòu)性能分析

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

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

3.2 架構(gòu)性能擴(kuò)展

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

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

3.3 架構(gòu)性能對比

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

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

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

參考文獻(xiàn)

[1] 于學(xué)榮,，戴紫彬.可重構(gòu)移位單元的設(shè)計與實現(xiàn)[J].微計

     算機(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移位器設(shè)計[D].長沙：

     國防科學(xué)技術(shù)大學(xué),，2010.

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

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

     Princeton University,，2008.