基于双ibutterfly网络的插入排序算法

陈 帆，徐金甫，常忠祥

（信息工程大学 密码工程学院，河南 郑州450001）

0 引 言

插入排序操作可以将一个序列转化成任意的指定序列，在密码算法中有着广泛的应用，尤其是硬件级的可重构密码算法的实现方面应用普遍［1］。然而插入排序算法的硬件实现过程比较复杂，如何高效、快速的实现成为密码算法硬件实现技术的研究热点之一。

目前主流的方法一般基于ibutterfly （inverse butterfly）网络来实现插入排序算法，这其中的典型代表有Kolay S等结合归并算法的思想，利用双ibutterfly 网络设计实现的GRP算法［2，3］，其能够快速实现序列的插入排序操作，提高插入排序操作的实现速度。然而该GRP算法实现过程没有考虑到序列的自身特点，过多的使用网络导致序列实现过于复杂。据此，本文针对该算法进行了研究与并提出了改进方案。

文中首先对ibutterfly网络的置换原理与特性进行了分析，提出了一种利用单个ibutterfly网络实现插入排序操作复杂度评估的方法，其次基于该评估方法搜寻优选方案，对GRP算法进行了改进，提出一种能够根据目标序列特点选用不同工作模式的算法，最后给出了改进后方案的实现效率和性能指标。

1 ibutterfly网络与GRP算法

1.1 butterfly/ibutterfly网络分析

ibutterfly网络是实现输入数据与输出数据一一对应的排序的较好选择［4，5］。图1表示一个n－bit的ibutterfly网络（n＝8），该网络有lg（n）级，从左到右依次为第一级、第二级、第三级 （最右边），每一级由n/2 个2 输入开关构成，而每一个2输入开关由两个二选一数据选择器组成。

图1 8－8ibutterfly网络

数据A、B在开关控制信息Sel的控制下选择交叉或者直通。n－bit的数据在进入ibutterfly网络各级时以位置间距为2i－1（i为级数）的行两两分组。如第一级ibutterfly网络中位置7的数据与位置6的数据就组成了一个数据组，第二级中位置7的数据与位置5的数据就组成了一个数据组。然后将分组后的数据输入到2输入开关中，在控制信息sel的作用下 “路由”出相应结果。Butterfly网络是ibutterfly网络的逆结构［6］，其数据间距为2lg（n）－i。

该网络具有很好的可拆分性和迭代性，将n—n的ibutterfly网络的最外层去掉，可以看作两个 （n/2）— （n/2）的子网络［7］。如果实现位宽为n/2的操作，只需将网络最外一层开关置为直通，剩余的控制信息正常配置即可。输入数据在各级移位的规律性较强，对于不同类型的置换操作，控制信息便于实时生成［8］。

通过对ibutterfly网络的分析与研究，总结出如图2所示的排序方式。数据进入ibutterfly网络后，网络能够实现数据按照控制序列中 “0”、 “1”指示排序序列。即将控制序列中为 “1”的控制位对应的原数据依次排在新序列右侧，将控制序列中为 “0”的控制位对应的原数据依次逆序排在新序列的左侧。

图2 ibutterfly网络排序方式

由ibutterfly网络分析得出的这一排序功能可知：由于控制位列中 “0”所对应的原数据在进入到新序列后顺序颠倒了，所以这种实现方式是从右侧开始先将与目的序列同序的数据放置后，再将剩余与目的序列顺序不同的序列颠倒；如此重复进行，直至完成目的序列顺序调整。从上述分析发现，目的序列中数据的排列顺序对于插入排序的影响是很大的，因此对于序列数据排列顺序的研究是很有必要的。

1.2 GRP算法分析

GRP算法是一种快速高效排序算法，它利用归并的思想将一个大的排序任务分割成若干个子排序任务，再将子排序任务两两组合，并通过指令完成各组合子排序任务，重复此操作直至完成最终排序任务［9，10］。完成全部排序任务所需的指令条数为lg（n）条，很好地限制了指令周期数，即提高了排序操作的运行速度。

GRP算法在实现时是由两个ibutterfly网络并行连接而成，通过源序列多次通过ibutterfly网络实现序列的插入排序［11］。

如图3所示，GRP算法的运算实现过程共分为3个步骤：①根据归并算法得到控制信息，将控制信息和控制信息的逆分别同源序列相与得到两个互补序列。②将两个互补序列分别送入各自对应的ibutterfly网络，使得两个互补序列其中一个序列中数据按指定顺序序列排列在输出序列的左侧，同时另一个序列中数据按指定顺序序列排列在输出序列的右侧。③将两个网络的输出序列相或，合并为一个序列作为输出，即可得到目的序列。

图3 GRP算法硬件实现电路

忽略GRP实现细节，GRP算法的实现则简化成根据控制序列中 “0”、 “1”指示排列序列。即将控制序列中为“1”的控制位对应的原数据依次排在新序列右侧，将控制序列中为 “0”的控制位对应的原数据依次排在新序列左侧，以此实现序列的插入排序。

GRP算法结合了ibutterfly网络与归并算法的优势，能够快速而简便地实现插入排序操作。但由于GRP算法没有考虑不同序列的特点，在针对某些特殊序列时，存在严重不足。

例如实现8bit序列 （0，1，2，3，4，5，6，7）排序成 （7，6，5，4，3，2，0，1）。对于GRP 网络，根据排序原则，第一条控制序列为 （0，0，1，0，1，0，1，0），将源序列排列成 （0，1，3，5，7，2，4，6）；第二条控制序列为 （1，1，0，1，0，0，1，0），将序列排列成 （3，7，2，6，0，1，5，4）；第三条控制序列为 （1，0，1，0，1，1，0，0），得到目的序列 （7，6，5，4，3，2，0，1）。实现该操作共需3条指令。如果使用单个ibutterfly网络，则只需执行1 条控制序列，即 （1，1，0，0，0，0，0，0）。之所以如此，是因为GRP算法只是针对普遍序列的一个算法，没有考虑不同序列的特点。

2 GRP算法的改进

2.1 插入排序算法复杂度评估算法

定义1 正序列：在一个给定整数序列A1，A2，……Ai，……Aj，……An中，若子序列Ai，……Aj满足以下条件：i＜i＋1＜i＋2＜……＜j－1＜j，i－1＞i或者i＝1，j＋1＜j或者j＝n，则该子序列为正序列。

例如：对于源序列为 ｛0，1，2，3，4，5，6，7｝，给定的一个序列 ｛1，2，5，7，0，3，6，4｝，其正序列为｛（1，2，5，7），（0，3，6），（4）｝。

定义2 逆序列：在一个给定整数序列A1，A2，……Ai，……Aj，……An，如子序列Ai，……Aj满足以下条件：i＞i＋1＞i＋2＞……＞j－1＞j，i－1＜i或者i＝1，j＋1＞j或者j＝n，则该子序列为正序列。

例如：对于源序列为 ｛0，1，2，3，4，5，6，7｝，给定的一个序列 ｛1，2，5，4，7，3，6，0｝，其逆序列为｛（1），（2），（5，4），（7，3），（6，0）｝。

用Numh来表示目的序列中正序列个数。用Numd来表示目的序列中降序序列个数。例如：对于源序列为 ｛0，1，2，3，4，5，6，7｝，An＝ ｛1，2，5，7，0，3，6，4｝，Bn＝ ｛1，2，5，4，7，3，6，0｝则Numh（An）＝2，Numd（Bn）＝5。

基于ibutterfly网络的插入排序算法指令条数的判决值用Num 来表示。（通过Num 能够成为插入排序算法复杂度评估值）在检测目的序列开始前，Num＝ “0”。检测目的序列开始后，按照规定方向轮流检测正向序列和逆向序列，每检测出一个单向序列则使Num 加 “1”。

例如：对于源序列为 ｛0，1，2，3，4，5，6，7｝，目的序列为 ｛1，2，5，7，0，3，6，4｝，检测规则定位为从左往右。

插入算法指令条数判决值的计算步骤为：

（1）检测得出第一组正向序列为 （1，2，5，7），则Num＝1；

（2）继续检测逆向序列为 （0），则Num＝2；

（3）继续检测正向序列为 （3，6），则Num＝3；

（4）继续检测逆向序列为 （4），则Num＝4，检测完毕。

所以该例中判决值Num 最终为4。

2.2 单个ibutterfly网络插入排序算法研究

利用单独一个ibutterfly网络，让数据多次通过网络实现插入排序。假设存在一个n－bit的整数序列An，要求通过比特置换得到指定序列Bn。An为源序列，Bn为目的序列。按照ibutterfly网络的排序方式实现排序时，实现排序所需指令条数的判断方法为：对序列Bn按照从右向左的规则计算插入指令条数判决值；对序列Bn检测完毕后得出判决值为Num；则从源序列向目的序列转换所需要的指令个数为 （Num－1）条。

例：源序列为 ｛7，6，5，4，3，2，1，0｝，目的序列为 ｛3，4，2，5，1，6，0，7｝。因此由定义可知，在本次排序中，阿拉伯数字从高到低为正序列，从低到高为逆序列。以此来检测目的序列。从右向左进行检测指令个数判决值，检测结果为： ｛7｝， ｛0｝， ｛6｝， ｛1｝， ｛5｝， ｛2｝，｛4｝，｛3｝。所以Num＝8，指令条数即为n＝Num－1＝7。

假设源序列为 ｛7，6，5，4，3，2，1，0｝，目的序列为 ｛2，7，4，3，5，1，0，6｝。同理检测，检测结果为：｛6｝，｛0｝，｛5，1｝，｛3｝，｛7，4｝，｛2｝。所以指令条数为n＝5。

通过实验可知，多次通过ibutterfly网络可以实现任意目的序列的插入排序操作，且根据目的序列不同特点，实现排序操作时所需指令条数差异较大。利用ibutterfly 网络，由源序列 （0，1，2，3，4，5，6，7）通过y条指令实现向任意排列方式的目的序列排序，指令条数y的值在0～7之间。通过matlab仿真，对8bit数据的排序操作进行统计，使用y条指令能够实现插入排序的目的序列个数及占任意排序组合序列总数的比例结果见表1。

表1 8比特排序指令个数

通过统计可知，8bit序列的不同排布方式共有40320种，且实现排序操作占用不超过3条指令 （包含3条指令）的序列个数共占总序列数的19.37%。

因为通过单一的ibutterfly网络来实现排序时，使用1条、2条、3条指令的序列所需指令条数与GRP 算法是不一样的，且只用到一个ibutterfly网络。所以将改进的GRP算法针对这些特殊序列进行特殊操作，能有效提升GRP算法的速度和效率。

2.3 GRP算法的改进

由2.2节可知，在8bit序列排序过程中，在全部目的序列中有19%左右的序列在由源序列排序过程中只需要3条以下的指令个数 （包括3条）。将这些序列定义为特殊序列。对于这些特殊的序列而言，可通过单个ibutterfly网络很方便的就能实现，而GRP算法中依然需要两个ibutterfly网络配合完成。不能发挥出GRP算法的优势，反而增加了实现的复杂程度。

基于以上分析，本文提出GRP算法的改进算法，改进后实现电路结构如图4所示。

图4 GRP改进算法的电路结构

在改进的GRP算法中，通过模式选择信号控制两个二选一数据选择器。当模式为单个ibutterfly网络工作时，则通过模式选择信号控制数据选择器选择全 “1”序列进入电路，与源序列相与，同时在输出时选择单个ibutterfly输出的结果作为最终输出。当模式为GRP操作时，则通过模式选择信号控制数据选择器选择控制序列进入电路，与源序列相与，同时在输出时将两个ibutterfly网络结果相或后作为最终输出。

改进后GRP算法执行时，在开始排序操作前，首先通过对目的序列特点的分析，先利用2.1节提出的评估算法判断序列通过单个ibutterfly网络所需指令个数。如果通过单个ibutterfly网络所需的指令个数已经小于lg（n）条指令了。则发出模式选择信号，启动单个ibutterfly网络来实现插入排序操作。

如果通过2.1节评估算法得出通过单个ibutterfly网络所需的指令个数大于lg（n）条指令，则发出模式选择信号，启动全部网络共同工作，完成插入排序操作。

3 性能评估

以8bit位宽序列为例，在实现排序过程中，特殊序列占整体序列的比重由表1可知，其中有19.37%数量的序列为特殊序列，不需使用GRP网络，而只需开启一个ibutterfly网络，用与GRP相同的指令数即可实现排序操作。如图5所示，特殊序列的数量会随数据位宽的增加而显著增加。所以随着位宽的增加，GRP算法改进的效果会更加明显。

硬件实现前后硬件开销对比见表2。

图5 特殊序列数量随数据位宽变化趋势

表2 硬件实现前后硬件开销对比

综合分析，在针对一些特殊插入排序操作时，例如DES加密运算中的P序操作，恰好使用的就是这些特殊序列。因此本文设计虽然略微增加了GRP硬件实现资源，但弥补了其应用的灵活性。

本文提出结合序列自身特点对GRP算法进行改进，改进后的GRP 算法针对不同的序列特点选择相应的工作模式，有效地增强了GRP算法的速度和效率。

4 结束语

由于GRP算法具有自身不足，即实现特殊序列的插入排序时效率不高。因此本文针对GRP算法的不足，提出了GRP算法的改进的算法。通过加入序列自身特点的分析和归纳，提出了一种基于ibutterfly网络下的简便插入排序操作复杂度评估规律。通过分析比较，通过评估规律对序列进行分析后，在改进后的GRP 算法中选择合适的工作模式，能够高效地实现插入排序操作。

［1］Nan Longmei，Dai Zhibin.Design and implementation of configurable extract instructions targeted at stream cipher processing ［C］//Sth International Conference on ASIC，2009.

［2］Yedidya Hilewitz.A new basis for shifters in general－purpose processors or exiting and advanced bit manipulations［J］.IEEE Transactions on Computers，2009，58 （8）：1035－1048.

［3］Kolay S，Khurana S，Sadhukhan A，et al.Bit permutation instructions for accelerating software cryptography ［C］//IEEE Conference Publications，2013：963－968.

［4］Li Hongyan，Gao Fei.Design and implementation of reconfigurable bit permutation system based on Waksman network［C］//IEEE Conference Publications，2010：113－116.

［5］Su Yang.Research of design technology of reconfigurable shift unit based on multilevel interconnection ［J］.Intelligent System and Applied Material，Advanced Materials Research，Advanced Materials Research，2012，466：1065－1069.

［6］Hilewitz Yedidya.Advanced bit manipulation instructions：Architecture，implementation and applications［D］.New Jersey：Princeton University，2008.

［7］Azaria Paz.A theory of decomposition into prime factors of layered interconnection networks ［J］.Discrete Applied Mathematics，2011，159 （7）：628－649

［8］John Garoflakis，Eleftherios Stergiou.An analytical model for the performance evaluation of multistage interconnection networks with two class priorities ［J］.Future Generation Computer Systems，2013，29 （1）：114－129.

［9］David Arroyo，JesusDiaz FB Rodriguez.Cryptanalysis of a one round chaos－based substitution permutation network ［J］.Signal Processing，2013，93 （5）：1358－1364.

［10］Hilewitz Y，Ruby B Lee.Fast bit gather，bit scatter and bit permutation instructions for commodity microprocessors ［J］.J Signal Processing Systems，2008，53 （1－2）：145－169.

［11］John Garofalakis，Eleftherios Stergiou.Analytical model for the performance evaluation of multilayer multistage interconnection networks servicing unicast and multicast traffic by partial multicast operation ［J］.Performance Evaluation，2010，67 （10）：959－976.