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