IBPU:一种面向通用处理器架构的比特置换功能单元

doi:10.3969/j.issn.0372-2112.2018.08.022

电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1960-1968.DOI: 10.3969/j.issn.0372-2112.2018.08.022

IBPU:一种面向通用处理器架构的比特置换功能单元

马超¹, 南龙梅², 潘达杉¹, 李伟³, 戴紫彬³

1. 国家高性能集成电路(上海)设计中心, 上海 201204;
2. 复旦大学集成电路国家重点实验室, 上海 200433;
3. 信息工程大学, 河南郑州 450000

收稿日期:2016-07-21 修回日期:2017-11-14 出版日期:2018-08-25
- 通讯作者:
- 南龙梅
- 作者简介:
- 马超男,1988年生于陕西西安.国家高性能集成电路(上海)设计中心,博士.研究方向为专用处理器设计,多级动态互连网络,ASIC专用芯片设计.
- 基金资助:
- 国家自然科学基金 (No.61404175）

IBPU:A Bit Permutation Functional Unit for General-Purpose Processors

MA Chao¹, NAN Long-mei², PAN Da-shan¹, LI Wei³, DAI Zi-bin³

1. National High Performance Integrated Circuit Design Center, Shanghai 201204, China;
2. State Key Lab of ASIC and System, Fudan University, Shanghai 200433, China;
3. Information Engineering University, Zhengzhou, Henan 450000, China

Received:2016-07-21 Revised:2017-11-14 Online:2018-08-25 Published:2018-08-25
- Corresponding author:
- NAN Long-mei
- Supported by:
- National Natural Science Foundation of China (No.61404175)

摘要/Abstract

摘要： 本文利用Inverse Butterfly网络拓扑结构的自路由特性，并结合分治策略，提出了一种能够硬件高速实现任意比特置的换选路算法.利用该算法能够在O（lgN）条指令内完成N-bit任意静态置换操作，在O（lg²N）条指令内完成N-bit任意动态置换操作.在此基础上，本文构造了一种新型比特置换单元-Permutation Unit based on Inverse Butterfly，IBPU.并将它在SMIC 65nm工艺下进行了逻辑综合，结果表明：与以往研究成果相比，本文提出的IBPU资源消耗降低了约32%，延迟降低了近30%.当完成静态置换操作时，其功能单元所消耗的代价最小，不超过以往设计的60%；当完成动态置换操作时，虽然消耗的代价较大，但其随置换位宽N的增加涨幅较小，因此具有较高的稳定性，其综合性能优势明显.

关键词: Inverse Butterfly网络, 分治策略, 置换选路算法, 硬件实现

Abstract: In this paper,a new routing algorithm for arbitrary bit permutation operations is proposed combining with the divide and conquer strategy.The algorithm utilizes self-routing characteristics of the Inverse Butterfly Network.It can complete any N-bit fixed permutation in no more than O(lgN) instructions,and also can complete any N-bit dynamic permutation in no more than O(lg^<i>2N) instructions.On this basis,a new bit-permutation unit based on Inverse Butterfly,IBPU is developed and synthesized in SMIC 65-nm process.The results show that our IBPU has less resource consumption which decreased by about 32%,and lower latency which reduced by nearly 30% compared with the similar designs.Moreover,when it performs fixed permutation,the cost of the functional unit is minimal,which is not more than 60% of what was previously designed.When it performs dynamic permutation,though its cost is greater,the cost has smaller increase accompanying with the increase of permutation width N,so it has higher stability and its comprehensive performance advantages are obvious.

Key words: Inverse Butterfly Network, divide and conquer, permutation routing algorithm, hardware implementation

中图分类号:

TP393.3

马超, 南龙梅, 潘达杉, 等. IBPU:一种面向通用处理器架构的比特置换功能单元[J]. 电子学报, 2018, 46(8): 1960-1968.

MA Chao, NAN Long-mei, PAN Da-shan, et al. IBPU:A Bit Permutation Functional Unit for General-Purpose Processors[J]. Acta Electronica Sinica, 2018, 46(8): 1960-1968.

参考文献

[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] 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.
[3] Ao T,He Z,Dai K.Low-cost bit permutation circuit with concise configuration rule[A].Proceedings of the International Multi Conference of Engineers and Computer Scientists[C].Hong Kong:International Association of Engineers,2015.158-160.
[4] Kolay S,Khurana S.PERMS:a bit permutation instruction for accelerating software cryptography[A].16th Euromicro Conference on Digital System Design[C].Spain:IEEE,2013.963-968.
[5] Dimitrakopoulos G,Mavrokefalidis C,Galanopoulos K,et al.Fast bit permutation unit for media enhanced microprocessors[A].2006 IEEE International Symposium on Circuits and Systems(ISCAS 2006)[C].Greece:IEEE,2006.49-52.
[6] 陈国良,韩雅华.Benes网络的半自动选路法[J].计算机学报,1990,3(3):161-173. Chen Guo Liang,Han Ya Hua.The semi-self-routing algorithms for Benes network[J].Chinese Journal of Computers,1990,3(3):161-173.(in Chinese)
[7] Shan W,Chen X,et al.A novel combinatorics-based reconfigurable bit permutation network and its circuit implementation[J].Chinese Journal of Electronics,2015,24(3):513-523.
[8] 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.
[9] 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):145-169.
[10] Chang Zhongxiang,Hu Jinshan,MA Chao.Research on shifter based on ibutterfly network[A].17th China Computer Federation[C].Xi Ning,China:2013.92-100.
[11] 常忠祥,戴紫彬,李伟,等.高速比特置换实现技术研究[J].小型微型计算机系统,2015,36(3):627-630. Chang Zhong Xiang,Dai Zi Bin,Li Wei,et al.High-speed bit permutation implementation technology[J].Journal of Chinese Computer Systems,2015,36(3):627-630.(in Chinese)
[12] Rajkumar S,Goyal N K.Design of 4-disjoint gamma interconnection network layouts and reliability analysis of gamma interconnection Networks[J].Journal of Supercomputing,2014,69(1):468-491.
[13] Bistouni F,Jahanshahi M.Pars network:A multistage interconnection network with fault-tolerance capability[J].Journal of Parallel & Distributed Computing,2015,75:168-183.
[14] 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.
[15] Intel Corporation,Intel 64 and IA-32 Architectures Software Developer's Manual[S].2015
[16] Semiconductor Manufacturing International Corporation.SMIC 65nm Logic Process Standard Cell Library Databook[S].2012.
[17] LIU B,BAAS BM.Parallel AES encryption engines for many-core processor arrays[J].IEEE Transactions on Computers,2013,62(3):536-547.

IBPU:一种面向通用处理器架构的比特置换功能单元

IBPU:A Bit Permutation Functional Unit for General-Purpose Processors

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

[1]	高振国;蔡绍滨;李香;赵蕴龙;王慧强. 非完全无线报文重传分析研究及其分治策略[J]. 电子学报, 2011, 39(7): 1683-1688.
[2]	周旭;李肯立;乐光学;杨志邦. 一种基于分治的三维匹配问题DNA计算算法[J]. 电子学报, 2010, 38(8): 1831-1836.