A Edge-Centered High Energy-Efficient Mapping Algorithm for Cipher Logic Array
-
摘要: 为解决密码算法在粗粒度可重构密码逻辑阵列(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.
-
Key words:
- Cryptographic algorithm /
- Array /
- Mapping /
- Edge centered /
- Energy-efficient
-
表 1 ECLMap算法描述
输入:G={V,E},C={P,L} 输出: Map (1) FT←Initialize_FT(); //初始化回溯表 (2) Map←Initialize_MP(); // 初始化映射 (3) repeat (4) Vroot←Choose_Root_Node(V); //起始节点的选取 (5) SE←Sort_Edge(Vroot); //构建搜索步 (6) PEroot←Map_Root(Vroot); //起始节点的映射 (7) for each edge e in SE do (8) RM←Search_Road(e); //路径搜索 (9) M←Choose_Road_by_Affinity(R`M,PE); //亲和度函数 进一步路径选择 (10) R`M←Choose_Min_Road(RM,PE); //选择最小的路径 (11) if M≠$\emptyset $ then (12) RoadM←M(0); (13) VM←Get_Destination(RoadM); //路径终点即为节点 的映射 (14) Upadate_mapping(RoadM, VM, Map); (15) FT←Updata_FT(VM,FT,M,M(0)); //回溯表的确定 (16) else (17) RBK←Edge_To_Backtrack(e,FT); //M为空则进行回溯 (18) end if (19) if RBK==NULL then (20) break; (21) else (22) Modify_FT(RBK, FT); //修改回溯表 (23) Delete_MP(RBK,Map); //删除映射失败的路径 (24) end if (25) end for (26) Until all nodes and edge in SE are mapped; (27) return Map 表 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 表 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 -
[1] 杜怡然, 李伟, 戴紫彬. PVHArray: 一种流水可伸缩的层次化可重构密码逻辑阵列结构[J]. 电子学报, 2020, 48(4): 781–789. doi: 10.3969/j.issn.0372-2112.2020.04.020DU 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.011DU 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.068HAN 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.001XING 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/JEIT170748ZHANG 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/JEIT200079LI 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.032CHEN 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.010YIN 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.