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

        針對以上問題，本文結(jié)合Butterfly網(wǎng)絡(luò)互連函數(shù)和拓?fù)浣Y(jié)構(gòu)特點(diǎn)，將移數(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ò)實(shí)現(xiàn)移數(shù)置換和p序置換的原理相似，便于兩者架構(gòu)的合并，因此成為實(shí)現(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)，理論上能實(shí)現(xiàn)2^k種置換，每種置換對應(yīng)的路由信息唯一。

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

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

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

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

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

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

2.1 路由算法分析

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

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

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

        將第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ù)算法描述，可以實(shí)現(xiàn)其硬件電路。

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

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

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

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

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

（2）路由信息生成適配電路的硬件實(shí)現(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所示。

單獨(dú)實(shí)現(xiàn)移數(shù)置換和p序置換功能時，p序置換的資源消耗和電路延遲比移數(shù)置換大。實(shí)現(xiàn)移數(shù)p序統(tǒng)一架構(gòu)整體功能時，由于移數(shù)置換和p序置換的硬件電路共用，與兩者單獨(dú)實(shí)現(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ò)實(shí)現(xiàn)移數(shù)和p序置換的方式在資源消耗和電路延遲方面優(yōu)勢明顯，資源消耗和電路延遲的增長幅度逐漸減小。

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

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

由圖6可知，只實(shí)現(xiàn)單向移位（循環(huán)左移）時，對數(shù)移位器面積最小且速度最快，但其靈活性不高，不支持短字移位操作，且當(dāng)擴(kuò)展其功能以實(shí)現(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è)計并實(shí)現(xiàn)了Butterfly網(wǎng)絡(luò)下的移數(shù)p序統(tǒng)一架構(gòu)，分析并提取出相應(yīng)的路由算法，并對算法進(jìn)行了硬件實(shí)現(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è)計與實(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] 華校專.定點(diǎn)除法器與向量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.