文献标识码： A
文章编号： 0258-7998(2014)07-0065-04
移数置换和p序置换是芯片设计中的两种重要置换。移数置换用于实现处理器中移位功能，是完成地址产生和算术逻辑运算等功能必不可少的部分。p序置换广泛应用于数据加密、图像处理和数字信号处理等领域，是完成数据扩散的重要方法。随着微电子技术的不断进步，特别是芯片可重构技术的兴起和发展[1]，芯片设计对移数置换和p序置换功能的并行性、灵活性和可扩展性提出了更高要求。目前，p序置换主要采用基本操作组合和比特置换方式实现，灵活性和可扩展性不强。移数置换功能实现方式主要有对数移位器、桶形移位器、基于互连网络的移位器等[2-3]。对数移位器实现单一移位功能时，速度和面积优势较大，但同时支持各类移位操作时，布线资源较大，且电路灵活性不高[4]；桶形移位器[5]主要用于实现循环左移或循环右移操作，不能很好地支持短字移位操作，电路灵活性不高；基于互连网络的移位器[6]对网络的互连函数和拓扑结构没有充分利用，提出的路由算法硬件实现较为复杂，硬件资源消耗和电路延迟较大。
针对以上问题，本文结合Butterfly网络互连函数和拓扑结构特点，将移数置换和p序置换的架构进行合并，提出了基于Butterfly网络的移数p序统一架构，分析并提取出支持该架构的路由算法。
1 基于Butterfly网络的移数p序统一架构
Butterfly网络是典型的动态多级阻塞网络，其并行性好，可拆分性强，支持短字置换和并行操作，能够满足移数置换和p序置换对灵活性、并行性和可扩展性的要求。同时，Butterfly网络实现移数置换和p序置换的原理相似，便于两者架构的合并，因此成为实现移数p序统一架构的首选。
1.1 Butterfly网络结构分析
一个N-N的Butterfly网络由log2 N个开关级组成，整个网络的开关量为(N/2)log2N。每个开关有直通和交叉两种状态，整个网络有2k(k=N/2log2N)种开关状态，理论上能实现2k种置换，每种置换对应的路由信息唯一。
以8-8 Butterfly为例说明，如图1所示，左端为源端（输入端），右端为终端（输出端），开关级从左到右依次为第1级、第2级、第3级，级与级之间为子蝶式变换。
本文以Butterfly网络为基础，实现移数p序统一架构，同时提取出适应于该架构的路由算法，支持路由信息实时生成和配置。
1.2 移数p序统一架构设计
Butterfly网络分别实现移数置换和p序置换时，两者的数据传输网络相同，路由信息生成算法互有交叉，因此两者可以采用统一的架构来实现。
如图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序统一架构的路由算法，先对移数置换和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序统一架构的路由算法。
2.2.2 移数p序统一架构路由算法提取
移数p序统一架构路由算法的提取过程如下：
（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序统一架构路由算法
输入：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序统一架构所需路由信息的生成和适配。根据算法描述，可以实现其硬件电路。
2.3 路由算法硬件实现
移数p序统一架构的路由算法硬件电路包括两部分：初始条件生成电路和路由信息生成适配电路。
（1）初始条件生成电路的硬件实现
初始条件生成电路用于生成路由信息初始条件，移数p序统一架构路由算法的初始条件生成电路的硬件实现如图3所示。
图3中，初始条件生成电路由模加单元、模乘单元、与运算单元、数据选择器、异或网络和输出网络组成，整个系统计算并得到路由信息初始条件C0[N/2-1:0]。
（2）路由信息生成适配电路的硬件实现
路由信息生成适配电路以初始条件为输入，完成整个Butterfly网络路由信息的生成和适配。以16-16 Butterfly网络为例说明，如图4所示。
移数p序统一架构的路由信息生成和适配完成后，在路由信息的控制下，数据经过数据链路，完成移数p序统一架构的整体功能。
3 性能分析
3.1 架构性能分析
本设计采用64 bit数据位宽，在CMOS 0.065 ?滋m工艺下进行综合优化，得到了本设计的资源消耗和电路延迟，如表1所示。
单独实现移数置换和p序置换功能时，p序置换的资源消耗和电路延迟比移数置换大。实现移数p序统一架构整体功能时，由于移数置换和p序置换的硬件电路共用，与两者单独实现相比，资源消耗和电路延迟增加都不大。
3.2 架构性能扩展
在CMOS 0.065 ?滋m工艺下，分别对数据位宽为8 bit、16 bit、32 bit、64 bit、128 bit、256 bit、512 bit的移数p序统一架构进行综合优化，得到本架构在不同数据位宽下的性能扩展趋势，如图5所示。
随着数据位宽的增加，本架构在资源消耗和电路延迟方面都会增加。其中，资源消耗的增长幅度先增大后减小，电路延迟的增长幅度逐渐变小。小位宽时，本架构资源消耗和电路延迟随数据位宽的增加增长较快；在大数据位宽下，随着数据位宽的增加，用Butterfly网络实现移数和p序置换的方式在资源消耗和电路延迟方面优势明显，资源消耗和电路延迟的增长幅度逐渐减小。
3.3 架构性能对比
由于目前p序置换主要以基本操作组合的方式或比特置换的方式实现，不便于性能比较，因此，本文重点将本架构的移数置换功能与对数移位器、参考文献[2]和参考文献[3]中的移位部件进行性能对比。在COMS 0.065 ?滋m工艺下，其对比结果如表2所示，性能对比如图6所示。
由图6可知，只实现单向移位（循环左移）时，对数移位器面积最小且速度最快，但其灵活性不高，不支持短字移位操作，且当扩展其功能以实现多种类型的移位操作时，资源消耗增长过快。参考文献[2]中桶形移位器与本设计相比，其电路延迟稍小，但资源消耗较大，且灵活性不高，不支持短字移位，同时，进行功能扩展时，资源消耗和电路延迟都大幅度增加[3]。参考文献[2]中I-BFLY移位器灵活性较高，功能扩展性较强，且支持短字置换，但其控制信息生成算法较为复杂，资源消耗和电路延迟都较大。本设计在保证较高灵活性、较强功能扩展性、支持短字置换和并行操作的前提下，与I-BFLY移位器[1]相比，面积节省了30.0%且速度提升了17.6%。此外，本架构不仅支持1组64 bit位宽下移数和p序置换，同时还支持2组32 bit位宽、4组16 bit位宽的移数和p序置换。
本文设计并实现了Butterfly网络下的移数p序统一架构，分析并提取出相应的路由算法，并对算法进行了硬件实现。通过对该架构进行性能评估，结果表明，本设计灵活性高，功能扩展性强，且支持短字置换和并行操作，和I-BFLY移位器[2]相比，面积节省了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.