以边为中心的密码逻辑阵列高能效映射算法

徐金甫; 章宇雷; 李伟; 陈韬

doi:10.11999/JEIT210008

以边为中心的密码逻辑阵列高能效映射算法

doi: 10.11999/JEIT210008

战略支援部队信息工程大学郑州 450001

详细信息

作者简介:
徐金甫：男，1965年生，教授，博士生导师，研究方向为专用集成电路设计技术

章宇雷：男，1996年生，硕士生，研究方向为可重构逻辑电路设计

李伟：男，1983年生，副教授，博士生导师，研究方向为密码处理器设计、ASIC专用芯片设计

陈韬：男，1979年生，副教授，硕士生导师，研究方向为安全专用芯片设计

通讯作者:
章宇雷　462960074@qq.com

中图分类号: TN918.2
计量
- 文章访问数: 676
- HTML全文浏览量: 209
- PDF下载量: 46
- 被引次数: 0
出版历程
- 收稿日期: 2021-01-04
- 修回日期: 2021-03-05
- 网络出版日期: 2021-03-27
- 刊出日期: 2021-06-18

A Edge-Centered High Energy-Efficient Mapping Algorithm for Cipher Logic Array

Strtegic Support Force Information Engineering University, Zhengzhou 450001, China

摘要

摘要: 为解决密码算法在粗粒度可重构密码逻辑阵列(CRCLA)上映射性能不高及编译时间长的问题，该文提出一种密码算法和硬件资源的描述形式，在映射过程中能够更加直观地显示各个资源的占用情况；并通过分析密码算法运算特征与粗粒度可重构密码逻辑阵列硬件结构的内在关联，以减少关键路径延时为目标，提出了一种以边为中心的密码逻辑阵列高能效映射算法(ECLMap)。通过边映射来指导节点映射，结合相关映射策略，引入回溯机制来提高映射成功率。在仿真平台下对多种密码算法进行实验，相比于其他通用的映射算法，结果表明该文提出的算法映射性能最佳，在算法能效上平均提升了约20%，同时在编译时间上平均提升了约25%。实现了算法的高能效映射。
- 密码算法 /
- 阵列 /
- 映射 /
- 以边为中心 /
- 能效
Abstract: In order to solve the problem of low mapping performance and long compilation time of cipher algorithms on Coarse-grained Reconfigurable Cipher Logic Arrays (CRCLA), a description of cryptographic algorithms and hardware resources is proposed, which can display the occupancy of each resource more intuitively during the mapping process. Then by analyzing the inherent relationship between the cryptographic algorithm operation characteristics and the coarse-grained reconfigurable cipher logic array hardware structure, with the goal of reducing the critical path delay, an Edge - centric Cipher Logical array Mapping (ECLMap) algorithm is proposed. Using edge mappings to guide the mapping of nodes, combined with relevant mapping strategy, the backtracking mechanism is introduced to improve the success rate of mapping. Compared with other common mapping algorithms, the results show that the algorithm proposed in this paper has the best mapping performance, with an average increase of about 20% in the algorithm energy efficiency and about 25% in the compilation time. The high-efficiency mapping of the algorithm is realized.
- Cryptographic algorithm /
- Array /
- Mapping /
- Edge centered /
- Energy-efficient

HTML全文

图 1 CRCLA整体硬件结构

下载: 全尺寸图片幻灯片

图 2 数据流图的矩阵表示过程

下载: 全尺寸图片幻灯片

图 3 PE资源占用情况表示

下载: 全尺寸图片幻灯片

图 4 一个包含互连及运算单元的集合及其表示方式

下载: 全尺寸图片幻灯片

图 5 数据流图拆分映射过程

下载: 全尺寸图片幻灯片

图 6 ECLMap算法映射成功率对比

下载: 全尺寸图片幻灯片

图 7 CRCLA密码算法映射编译时间对比结果

下载: 全尺寸图片幻灯片

图 8 CRCLA密码算法映射能效对比结果

下载: 全尺寸图片幻灯片

表 1 ECLMap算法描述

输入：G={V,E},C={P,L}
输出： Map
(1) FT←Initialize_FT(); //初始化回溯表
(2) Map←Initialize_MP(); // 初始化映射
(3) repeat
(4) V_root←Choose_Root_Node(V); //起始节点的选取
(5) SE←Sort_Edge(V_root);　//构建搜索步
(6) PE_root←Map_Root(V_root);　//起始节点的映射
(7) for each edge e in SE do
(8)　R_M←Search_Road(e); //路径搜索
(9)　M←Choose_Road_by_Affinity(R^`_M,PE);　//亲和度函数　　　进一步路径选择
(10) R^`_M←Choose_Min_Road(R_M,PE);　//选择最小的路径
(11)　if M≠$\emptyset $ then
(12)　　Road_M←M(0);
(13)　　V_M←Get_Destination(Road_M);　//路径终点即为节点　　　的映射
(14)　　Upadate_mapping(Road_M, V_M, Map);
(15)　　FT←Updata_FT(V_M,FT,M,M(0)); //回溯表的确定
(16)　else
(17) 　 R_BK←Edge_To_Backtrack(e,FT); //M为空则进行回溯
(18)　end if
(19)　if R_BK==NULL then
(20) 　break;
(21) 　else
(22)　　Modify_FT(R_BK, FT); //修改回溯表
(23)　　Delete_MP(R_BK,Map);　//删除映射失败的路径
(24)　end if
(25) end for
(26) Until all nodes and edge in SE are mapped;
(27) return Map

下载: 导出CSV

表 2 不同映射算法下的密码算法映射性能(Mbps)

密码算法	SPKM	EPIMap	2-StepACO	SA	本文
AES	410	420	446	440	450
DES	247	225	219	256	269
A5-1	115	110	112	120	128
ZUC	160	156	150	168	175
SM3	228	217	219	235	256

下载: 导出CSV

表 3 不同映射算法下的密码算法映射功耗(mW)

密码算法	电压(V)	SPKM	EPIMap	2-StepACO	SA	本文
AES	1.2	273	280	265	260	250
DES	1.2	256	267	252	248	241
A5-1	1.2	278	286	272	266	245
ZUC	1.2	285	291	280	273	258
SM3	1.2	293	296	283	275	264

下载: 导出CSV

参考文献(16)

[1]	杜怡然, 李伟, 戴紫彬. PVHArray: 一种流水可伸缩的层次化可重构密码逻辑阵列结构[J]. 电子学报, 2020, 48(4): 781–789. doi: 10.3969/j.issn.0372-2112.2020.04.020 DU Yiran, LI Wei, and DAI Zibin. PVHArray: A pipeline variable hierarchical reconfigurable cryptographic logic array structure[J]. Acta Electronica Sinica, 2020, 48(4): 781–789. doi: 10.3969/j.issn.0372-2112.2020.04.020
[2]	杜怡然, 南龙梅, 戴紫彬, 等. 可重构分组密码逻辑阵列加权度量模型及高能效映射算法[J]. 电子学报, 2019, 47(1): 82–91. doi: 10.3969/j.issn.0372-2112.2019.01.011 DU Yiran, NAN Longmei, DAI Zibin, et al. Reconfigurable block cryptographic logic array weighted metric model and high energy-efficient mapping algorithm[J]. Acta Electronica Sinica, 2019, 47(1): 82–91. doi: 10.3969/j.issn.0372-2112.2019.01.011
[3]	韩国栋, 肖庆辉, 张帆. 可重构系统中硬件任务布局布线算法研究[J]. 计算机科学, 2011, 38(11): 291–295. doi: 10.3969/j.issn.1002-137X.2011.11.068 HAN Guodong, XIAO Qinghui, and ZHANG Fan. Algorithms of placing and routing hardware task in reconfigurable system[J]. Computer Science, 2011, 38(11): 291–295. doi: 10.3969/j.issn.1002-137X.2011.11.068
[4]	行华彧, 景乃锋. 一种基于多阶段模拟退火的异构可重构阵列布局算法[J]. 微电子学与计算机, 2020, 37(6): 1–5. doi: 10.19304/j.cnki.issn1000-7180.2020.06.001 XING Huayu and JING Naifeng. A placement algorithm for HGRA based on multi-stage simulated anneal[J]. Microelectronics &Computer, 2020, 37(6): 1–5. doi: 10.19304/j.cnki.issn1000-7180.2020.06.001
[5]	YOON J W, SHRIVASTAVA A, PARK S, et al. SPKM: A novel graph drawing based algorithm for application mapping onto coarse-grained reconfigurable architectures[C]. The 2008 Asia and South Pacific Design Automation Conference, Seoul, Korea, 2008: 776-782. doi: 10.1109/ASPDAC.2008.4484056.
[6]	DAVE S, BALASUBRAMANIAN M, and SHRIVASTAVA A. RAMP: Resource-aware mapping for CGRAs[C]. The 55th Annual Design Automation Conference, San Francisco, USA, 2018: 1–6. doi: 10.1145/3195970.3196101.
[7]	KOU Mingyang, GU Jiangyuan, WEI Shaojun, et al. TAEM: Fast transfer-aware effective loop mapping for heterogeneous resources on CGRA[C]. The 57th ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2020: 1–6. doi: 10.1109/DAC18072.2020.9218668.
[8]	张兴明, 袁开坚, 高彦钊. 基于存储划分和路径重用的粗粒度可重构结构循环映射算法[J]. 电子与信息学报, 2018, 40(6): 1520–1524. doi: 10.11999/JEIT170748 ZHANG Xingming, YUAN Kaijian, and GAO Yanzhao. Coarse grained reconfigurable architecture loop mapping algorithm based on memory partitioning and path reuse[J]. Journal of Electronics &Information Technology, 2018, 40(6): 1520–1524. doi: 10.11999/JEIT170748
[9]	PARK H, FAN K, MAHLKE S, et al. Edge-centric modulo scheduling for coarse-grained reconfigurable architectures[C]. The 17th International Conference on Parallel Architectures and Compilation Techniques, Toronto, Canada, 2008: 166–176. doi: 10.1145/1454115.1454140.
[10]	明畅. 面向密码算法的可重构自动映射方法的设计与实现[D]. [硕士论文], 东南大学, 2018. MING Chang. Design and implementation of a reconfigurable automatic mapping method for cipher algorithms[D]. [Master dissertation], Dongnan University, 2018.
[11]	李伟, 高嘉浩, 杜怡然, 等. 一种密码专用可编程逻辑阵列的分组密码能效模型及其映射算法[J]. 电子与信息学报, 2021, 43(5): 1372–1380. doi: 10.11999/JEIT200079 LI Wei, GAO Jiahao, DU Yiran, et al. Energy efficiency model and mapping algorithm of block cipher for cipher specific programmable logic array[J]. Journal of Electronics &Information Technology, 2021, 43(5): 1372–1380. doi: 10.11999/JEIT200079
[12]	LIU Min, YAN Yinjian, LI Wei, et al. A dependence-first clustering based partitioning algorithm for coarse-grained reconfigurable cipher logic array[C]. 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference, Chongqing, China, 2018: 88–92. doi: 10.1109/IAEAC.2018.8577573.
[13]	陈乃金, 江建慧, 陈昕, 等. 一种考虑执行延迟最小化和资源约束的改进层划分算法[J]. 电子学报, 2012, 40(5): 1055–1066. doi: 10.3969/j.issn.0372-2112.2012.05.032 CHEN Naijin, JIANG Jianhui, CHEN Xin, et al. An improved level partitioning algorithm considering minimum execution delay and resource restraints[J]. Acta Electronica Sinica, 2012, 40(5): 1055–1066. doi: 10.3969/j.issn.0372-2112.2012.05.032
[14]	尹文志, 赵仲元, 毛志刚, 等. 一种快速高效的粗粒度可重构架构编译框架[J]. 微电子学与计算机, 2019, 36(8): 45–48, 53. doi: 10.19304/j.cnki.issn1000-7180.2019.08.010 YIN Wenzhi, ZHAO Zhongyuan, MAO Zhigang, et al. A fast and efficient compiler framework for CGRAs[J]. Microelectronics &Computer, 2019, 36(8): 45–48, 53. doi: 10.19304/j.cnki.issn1000-7180.2019.08.010
[15]	HAMZEH M, SHRIVASTAVA A, and VRUDHULA S. EPIMap: Using Epimorphism to map applications on CGRAs[C]. The DAC Design Automation Conference 2012, San Francisco, USA, 2012: 1280–1287. doi: 10.1145/2228360.2228600.
[16]	ZHOU Li, ZHANG Jianfeng, and LIU Hengzhu. Ant colony algorithm for Steiner tree problem in CGRA mapping[C]. The 4th International Conference on Information Science and Control Engineering, Changsha, China, 2017: 198-202. doi: 10.1109/ICISCE.2017.51.