基于Inverse Butterfly/Butterfly网络的置换-逆序与置换-移位选路算法

doi:10.3969/j.issn.0372-2112.2017.11.016

电子学报 ›› 2017, Vol. 45 ›› Issue (11): 2685-2694.DOI: 10.3969/j.issn.0372-2112.2017.11.016

基于Inverse Butterfly/Butterfly网络的置换-逆序与置换-移位选路算法

马超¹, 戴紫彬¹, 李伟², 南龙梅²

1. 解放军信息工程大学, 河南郑州 450000;
2. 复旦大学集成电路国家重点实验室, 上海 200433

收稿日期:2016-06-23 修回日期:2016-09-28 出版日期:2017-11-25
- 通讯作者:
- 李伟
- 作者简介:
- 马超,男,1988年生于陕西西安.解放军信息工程大学博士研究生.研究方向为专用处理器设计,多级动态互连网络路由算法,ASIC专用芯片设计.E-mail:wenlu_ma@163.com;戴紫彬,男,1966年出生于河南商丘.解放军信息工程大学专用芯片设计教研室主任,博士生导师.研究方向为密码处理器设计,VLSI设计.
- 基金资助:
- 国家自然科学基金 (No.61404175）

Permutation-Reverse and Permutation-Rotation Routing Algorithms Based on Inverse Butterfly/Butterfly Network

MA Chao¹, DAI Zi-bin¹, LI Wei², NAN Long-mei²

1. The PLA Information Engineering University, Zhengzhou, Henan 450000, China;
2. State Key Lab of ASIC and System, Fudan University, Shanghai 200433, China

Received:2016-06-23 Revised:2016-09-28 Online:2017-11-25 Published:2017-11-25

摘要/Abstract

摘要： 本文利用Inverse Butterfly/Butterfly多级动态互连网络的自路由和可重排特性，提出了基于该网络的置换-逆序和置换-移位选路算法.它们都能够对所有一次通过该网络的任意置换结果动态地完成逆序和移位操作，且算法复杂度低，硬件实现简洁.进一步，将本文提出的算法对基于该网络设计的置换操作进行了功能扩展，分别构建了置换-逆序、置换-移位以及置换-逆序-移位硬件单元.并将它们在SMIC 65nm工艺下进行了综合，结果表明：当在以往研究成果上扩展逆序操作时，硬件电路面积仅增加约6%且几乎不影响原架构的延迟；当在以往研究成果上扩展移位和逆序-移位操作时，原架构以18%和21%的面积增加值和30%的延迟增加值，实现了功能性2倍的提升.

关键词: Inverse Butterfly/Butterfly网络, 自路由, 置换-逆序算法, 置换-移位算法

Abstract: In this paper,we propose routing algorithms for permutation-reverse and permutation-rotation operations based on Inverse Butterfly and Butterfly Networks respectively.The algorithms utilize self-routing and self-reconfigurable characteristics of the networks,and are capable of completing all reverse and rotation operations of arbitrary permutation-P.Their computational complexities are low and the hardware implementations are simple.Following this,we extend the functions of the previous permutation operations based on the networks with our proposed algorithms.And then,permutation-reverse,permutation-rotation and permutation-reverse-rotation hardware units are developed and synthesized in SMIC 65-nm process.The results show that when the reverse operations are extended in previous designs,the area of the original circuits is only increased by 6%,and the latency of original circuits is almost not affected.In addition,when the rotation and reverse-rotation operations are extended in previous designs,the area of the original circuits is increased by 18% and 21%,and the latency of them is increased by 30%,while the functions of original circuits are expanded 2 times.

Key words: Inverse Butterfly/Butterfly Network, self-routing, permutation-reverse algorithms, permutation-rotation algorithm

中图分类号:

TP331.2

马超, 戴紫彬, 李伟, 南龙梅. 基于Inverse Butterfly/Butterfly网络的置换-逆序与置换-移位选路算法[J]. 电子学报, 2017, 45(11): 2685-2694.

MA Chao, DAI Zi-bin, LI Wei, NAN Long-mei. Permutation-Reverse and Permutation-Rotation Routing Algorithms Based on Inverse Butterfly/Butterfly Network[J]. Acta Electronica Sinica, 2017, 45(11): 2685-2694.

参考文献

[1] Shan W,Fu X,Xu Z.A secure reconfigurable crypto IC with countermeasures against SPA,DPA and EMA[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2015,34(7):1201-1205.
[2] Yin S Y,Ouyang P,Chen T,et al.A configurable parallel hardware architecture for efficient integral histogram image computing[J].IEEE Transactions on Very Large Scale Integration (VLSI) Systems,2016,24(4):1305-1318.
[3] Liu R.Chaos-based fingerprint images encryption using symmetric cryptography[A].Proc of 9th IEEE International Conference on Fuzzy Systems and Knowledge Discovery[C].Sichuan,China:IEEE,2012.2153-2156.
[4] Shan W,Zhang X,Fu X Y,et al.VLSI design of a reconfigurable S-box based on memory sharing method[J].IEICE Electronics Express,2014,11(1):1-6.
[5] Shan W,Chen X,Li B,Cao P,et al.Evaluation of correlation power analysis resistance and its application on asymmetric mask protected data encryption standard hardware[J].IEEE Transaction on Instrumentation and Measurement,2013,62(10):2716-2724.
[6] Shan W,Chen X,Lu Y C,et al.A novel combinatorics-based reconfigurable bit permutation network and its circuit implementation[J].Chinese Journal of Electronics,2015,24(3):513-517.
[7] Bansod G,Raval N,Pisharoty N.Implementation of a new lightweight encryption design for embedded security[J].IEEE Transactions on Information Forensics and Security,2015,10(1):142-151.
[8] Nassimi D,Sahni S A.Self_routing benes network and parallel permutation algorithm[J].IEEE Transaction on Computers,1981,30(5):332-340.
[9] Yin S Y,Ouyang P,Liu L B,et al.A fast and power-efficient memory-centric architecture for affine computation[J].IEEE Transactions on Circuits and Systems-Ⅱ:Express Brief,2016,63(7):.668-672.
[10] Yin S Y,Gu J Y,Liu D J,et al.Joint modulo scheduling and vdd assignment for loop mapping on dual-vdd CGRAs[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2016,35(9):1475-1488.
[11] Hilewitz Y,Lee R B.Fast bit gather,bit scatter and bit permutation instructions for commodity microprocessors[J].Journal of Signal Processing Systems,2008,53(1-2):145-169.
[12] Shi Z,Yang X,Lee R B.Arbitrary bit permutations in one or two cycles[A].14th IEEE International Conference on Application-Specific Systems,Architectures and Processors[C].Netherlands:IEEE,2003.237-237.
[13] Hilewitz Y,Shi Z J,Lee R B.Comparing fast implementations of bit permutation instructions[A].38th IEEE Annual Asilomar Conference on Signals,Systems,and Computers[C].United State:IEEE,2004.1856-1863.
[14] Bansod G,Gupta A,Ghosh A,et al.Experimental analysis and implementation of bit level permutation instructions for embedded security[J].Wseas Transactions on Information Science & Applications,2013,10(9):303-312.
[15] Hilewitz Y,Lee R B.A new basis for shifters in general-purpose processors for existing and advanced bit manipulations[J].IEEE Transactions on Computers,2009,58(8):1035-1048.
[16] Vidhya S P,Venkatesulu M.A block cipher based on boolean matrices using bit level operations[A].13th IEEE International Conference on Computer and Information Science (ICIS)[C].Tai Yuan:IEEE,2014.59-63.
[17] Intel Corporation,Intel® 64 and IA-32 Architectures Software Developer's Manual[S].2015.
[18] 杭州中天微系统有限公司,CK-Core用户手册[S].2007.
[19] Chang Zhongxiang,Hu Jinshan,Ma Chao.Research on shifter based on ibutterfly network[A].17th China Computer Federation[C].Xi Ning,China:Springer-Verlag,2013.92-100.
[20] Hilewitz Y.Advanced bit manipulation instructions:Architecture,implementation and applications[D].Princeton:Princeton University,2008.
[21] Filer E P,Getzinger T W.Dynamic endian switching[P].US Paten:7139905,2006.
[22] Chen J,Wang Q,Guo Z,et al.A Circuit Design of SMS4 against Chosen Plaintext Attack[A].17th International Conference on Computational Intelligence and Security[C].Paris,France:IEEE,2015.371-374.
[23] Neki K.Digital data processing circuit equipped with full bit string reverse control circuit and shifter to perform full or partial bit string reverse operation and data shift operation[P].US Patent:4984189,1991.
[24] Semiconductor Manufacturing International Corporation.SMIC 65nm Logic Process Standard Cell Library Databook[S].2012.

基于Inverse Butterfly/Butterfly网络的置换-逆序与置换-移位选路算法

Permutation-Reverse and Permutation-Rotation Routing Algorithms Based on Inverse Butterfly/Butterfly Network

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

编辑推荐

Metrics

[1]	马超, 李伟, 戴紫彬, 冯晓. 新型可重构移位-置换单元研究与设计[J]. 电子学报, 2017, 45(5): 1025-1034.
[2]	李挥;林良敏;黄佳庆;王蔚;安辉耀;伊鹏;汪斌强. 具有最小缓存复杂度的负载均衡交换方法[J]. 电子学报, 2009, 37(11): 2367-2372.
[3]	李挥, 何伟, 伊鹏, 王秉睿, 雷凯, 安辉耀, 汪斌强. 排序集线器多级互连交换结构的多路径自路由模型[J]. 电子学报, 2008, 36(1): 1-8.