基于可分负载理论的多核密码处理器调度研究

doi:10.19678/j.issn.1000-3428.0066383

摘要/Abstract

摘要：

针对多核密码处理器高能效负载调度问题，基于可分负载理论提出多轮与单轮混合负载调度机制，在不增加功耗前提下缩短密码任务完成时间，提升处理器能效。利用可分负载理论分析方法重点划分计算、负载传输时间，建立单轮调度、多轮与单轮混合调度方式，得到数学解析解以指导负载调度高能效设计，同时考虑计算通信占比、结果输出等因素以精确模型。分析模型并设计负载调度机制，在多核密码处理器芯片上实现并验证。MATLAB仿真结果表明，混合调度方式具有更好的性能表现，密码任务传输与计算时间比越大，负载完成时间的下限值越大，当处理器核数、调度轮数取中间值时，达到最优的负载完成时间和能效值，当结果输出时间小于任务传输时间时，影响较小。芯片实测结果表明，对于不同密码算法，提出的多轮与单轮混合调度方式能缩短10.1%~48.2%的负载任务完成时间，相应的多核密码处理器能效值提升9.8%~48.1%。

关键词: 密码处理器, 多核处理器, 可分负载理论, 负载调度, 高能效

Abstract:

Based on the divisible load theory, a mixed load scheduling mechanism with multi-round and single-round is proposed to solve the high energy-efficient load scheduling problem for multicore cryptoprocessors. This method can reduce the time taken to complete a cryptographic task without increasing the power consumption and can improve the energy-efficiency. First, the Divisible Load Theory(DLT) analysis is used to divide the computation and loads transfer time, and mathematical models have been constructed for single-round scheduling as well as multi- and single-round mixed scheduling. Mathematically, closed-form solutions are obtained to guide the design of high energy-efficiency for load scheduling. Moreover, the computing/communication ratio and resulting output are considered. After analyzing the model, a load scheduling mechanism is designed, which is implemented and validated on a multicore cryptographic processor chip. MATLAB simulations show that hybrid scheduling performs better. The larger the ratio of the transmission/computation time for cryptographic tasks, the higher the lower bound on the load completion time. The optimal load completion time and energy efficiency are achieved when the number of processor cores and scheduling rounds are taken as intermediate values. The effect is negligible when the output time is shorter than the task transmission time. The experimental results show that for different cipher algorithms, the proposed multi-and single-round mixed scheduling can shorten the completion time by 10.1 to 48.2 percent and increase the energy-efficiency of the corresponding multicore cryptographic processors by 9.8 to 48.1 percent.

Key words: cryptoprocessor, multi-core processor, Divisible Load Theory(DLT), load scheduling, high energy-efficiency

郎俊豪, 李伟, 陈韬, 南龙梅. 基于可分负载理论的多核密码处理器调度研究[J]. 计算机工程, 2023, 49(10): 255-263.

Junhao LANG, Wei LI, Tao CHEN, Longmei NAN. Research on Scheduling for Multi-core Cryptoprocessors Based on Divisible Load Theory[J]. Computer Engineering, 2023, 49(10): 255-263.

http://www.ecice06.com/CN/Y2023/V49/I10/255

图/表 15

图1 多核密码处理器的单层树状拓扑结构

Fig.1 Single layer tree topology structure of multi-core cryptographic processors

图2 单轮可分负载任务调度

Fig.2 Single-round divisible load tasks scheduling

图3 多轮加单轮混合调度

Fig.3 Multi-round and single-round mixed scheduling

图4 处理器核数与完成时间之间的关系

Fig.4 The relationship between processor cores and completion time

图5 固定轮次条件下混合调度完成时间的变化趋势

Fig.5 Changing trend of completion time of mixed scheduling under fixed turns condition

图6 固定处理器数条件下混合调度完成时间的变化趋势

Fig.6 Changing trend of completion time of mixed scheduling under fixed number of processors condition

图7 固定参数r条件下混合调度完成时间的变化趋势

Fig.7 Changing trend of completion time of mixed scheduling under fixed parameter r condition

图8 处理器核数与混合调度完成时间的关系

Fig.8 Relationshtp between the number of processor cores and completion time of mixed scheduling

图9 多核密码处理器芯片的结构

Fig.9 Structure of multi-core cryptoprocessor chip

图10 多核密码处理器芯片板级测试平台

Fig.10 Chip board testing platform for multi-core cryptoprocessor chips

图11 不同调度方式下完成时间的对比

Fig.11 Comparison of completion time under different scheduling patterns

图12 算法2在不同轮次条件下的吞吐率

Fig.12 Throughput rate of algorithm 2 under different turns condition

参考文献 25

1	亓晋, 王微, 陈孟玺, 等. 工业互联网的概念、体系架构及关键技术. 物联网学报, 2022, 6 (2): 38- 49. URL
	QI J , WANG W , CHEN M X , et al. Concept, architecture and key technologies of industrial Internet. Chinese Journal on Internet of Things, 2022, 6 (2): 38- 49. URL
2	ROBERTAZZI T G . Ten reasons to use divisible load theory. Computer, 2003, 36 (5): 63- 68. doi: 10.1109/MC.2003.1198238
3	陈剑骏, 陈耀武. 基于功能和数据划分的H.264并行解码算法. 计算机工程, 2012, 38 (12): 214- 217. doi: 10.3969/j.issn.1000-3428.2012.12.064
	CHEN J J , CHEN Y W . H.264 parallel decoding algorithm based on function and data partition. Computer Engineering, 2012, 38 (12): 214- 217. doi: 10.3969/j.issn.1000-3428.2012.12.064
4	王晓峰, 于卓, 赵健, 等. 大规模图例的最大团问题算法分析. 计算机工程, 2022, 48 (6): 182-192, 199. URL
	WANG X F , YU Z , ZHAO J , et al. Algorithm analysis for solving maximum clique problems of large-scale graphs. Computer Engineering, 2022, 48 (6): 182-192, 199. URL
5	CHRONAKI K , RICO A , CASAS M , et al. Task scheduling techniques for asymmetric multi-core systems. IEEE Transactions on Parallel and Distributed Systems, 2017, 28 (7): 2074- 2087. doi: 10.1109/TPDS.2016.2633347
6	TOPCUOGLU H , HARIRI S , WU M Y . Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 2002, 13 (3): 260- 274. doi: 10.1109/71.993206
7	CHENG H. A high efficient task scheduling algorithm based on heterogeneous multi-core processor[C]//Proceedings of the 2nd International Workshop on Database Technology and Applications. Washington D.C., USA: IEEE Press, 2010: 1-4.
8	CHENG X H, TAN C P, ZHANG Y. Research on optimization of DAG task scheduling model based on heterogeneous multicore processor[C]//Proceedings of the 3rd Advanced Information Technology, Electronic and Automation Control Conference. Washington D.C., USA: IEEE Press, 2018: 1393-1396.
9	GHANBARI S , OTHMAN M . Comprehensive review on divisible load theory: concepts, strategies, and approaches. Mathematical Problems in Engineering, 2014, 14, 1- 13.
10	BŁAŻEWICZ J , DROZDOWSKI M . The performance limits of a two dimensional network of load-sharing processors. Foundations of Computing and Decision Sciences, 1996, 21 (1): 3- 15.
11	CHENG Y C , ROBERTAZZI T G . Distributed computation for a tree network with communication delays. IEEE Transactions on Aerospace and Electronic Systems, 1990, 26 (3): 511- 516.
12	ROBERTAZZI T G . Processor equivalence for daisy chain load sharing processors. IEEE Transactions on Aerospace and Electronic Systems, 1993, 29 (4): 1216- 1221.
13	BATAINEH S , HSIUNG T Y , ROBERTAZZI T G . Closed form solutions for bus and tree networks of processors load sharing a divisible job. IEEE Transactions on Computers, 1994, 43 (10): 1184- 1196.
14	LI P , VEERAVALLI B , KASSIM A A . Design and implementation of parallel video encoding strategies using divisible load analysis. IEEE Transactions on Circuits and Systems for Video Technology, 2005, 15 (9): 1098- 1112.
15	GHOSE D , KIM H J , KIM T H . Adaptive divisible load scheduling strategies for workstation clusters with unknown network resources. IEEE Transactions on Parallel and Distributed Systems, 2005, 16 (10): 897- 907.
16	MOGES M A . Grid scheduling divisible loads from two sources. Computers & Mathematics with Applications, 2009, 58 (6): 1081- 1092.
17	YANG Y , VAN DER RAADT K , CASANOVA H . Multiround algorithms for scheduling divisible loads. IEEE Transactions on Parallel and Distributed Systems, 2005, 16 (11): 1092- 1102.
18	CHUPRAT S. Divisible load scheduling of real-time task on heterogeneous clusters[C]//Proceedings of 2010 International Symposium on Information Technology. Washington D.C., USA: IEEE Press, 2010: 721-726.
19	CHEN C Y , CHU C P . A novel computational model for non-linear divisible loads on a linear network. IEEE Transactions on Computers, 2016, 65 (1): 53- 65.
20	AALI S N, SHAHHOSSEINI H S, BAGHERZADEH N. Divisible load scheduling of image processing applications on the heterogeneous star network using a new genetic algorithm[C]//Proceedings of the 26th Euromicro International Conference on Parallel, Distributed and Network-based Processing. Washington D.C., USA: IEEE Press, 2018: 77-84.
21	CHINNAPPAN G M, VEERAVALLI B. Handling large-scale SAR image data on network-based compute systems using divisible load paradigm[C]//Proceedings of the 22nd International Conference on High Performance Computing and Communications. Washington D.C., USA: IEEE Press, 2021: 231-238.
22	YANG Y, CASANOVA H, DROZDOWSKI M. et al, On the complexity of multi-round divisible load scheduling. [EB/OL]. [2022-10-07] https://www.researchgate.net/publication/240775896_On_the_Complexity_of_Multi-Round_Divisible_Load_Scheduling.
23	BERLINSKA J , DROZDOWSKI M . Heuristics for multi-round divisible loads scheduling with limited memory. Parallel Computing, 2010, 36 (4): 199- 211.
24	MOGES M A . Divisible load scheduling and Markov chain models. Computers & Mathematics with Applications, 2006, 52 (10/11): 1529- 1542.
25	戴紫彬, 尹安琪, 曲彤洲, 等. 面向众核密码处理器的高效负载均衡技术. 电子与信息学报, 2019, 41 (2): 369- 376. URL
	DAI Z B , YIN A Q , QU T Z , et al. Efficient workload balance technology on many-core crypto processor. Journal of Electronics & Information Technology, 2019, 41 (2): 369- 376. URL

[1]	高秀武, 姜军, 白书敬, 黄亮明. 一种加速访存地址计算的编译优化[J]. 计算机工程, 2023, 49(1): 173-180.
[2]	周雍浩, 徐金龙, 李斌, 钱宏, 聂凯. 面向神威高性能多核处理器的并行编译优化方法[J]. 计算机工程, 2022, 48(9): 130-138.
[3]	焦童, 陈玲玲, 安鑫, 李建华. 基于重用信息的非易失性缓存动态旁路策略[J]. 计算机工程, 2021, 47(4): 158-165.
[4]	冯国富, 舒玉娟, 陈明, 董立夫. 基于big.LITTLE架构的多目标功耗自适应控制方法[J]. 计算机工程, 2019, 45(7): 60-65.
[5]	赵瑞姣,朱怡安,李联. 基于异构多核系统的混合关键任务调度算法[J]. 计算机工程, 2018, 44(2): 51-55.
[6]	陆思羽,王宏伟,张悠慧,杨广文,郑纬民. 面向MPI集合操作的定制化片上网络[J]. 计算机工程, 2017, 43(6): 1-10,18.
[7]	张晶,孙少杰,范洪博,付鑫,张果. 高实时性异构多核处理器任务调度算法[J]. 计算机工程, 2017, 43(5): 55-59.
[8]	朱怡安,黄林林,李联,罗殊彦. 多核平台下分区操作系统的安全关键任务调度方法[J]. 计算机工程, 2017, 43(12): 38-44.
[9]	金星,荆明娥,曾晓洋. 基于异构通信机制的任务映射算法[J]. 计算机工程, 2017, 43(12): 51-54,59.
[10]	彭毅,安虹,金旭,程亦超,迟孟贤,孙荪. 基于分布式模拟机制的片上网络硬件模拟系统[J]. 计算机工程, 2016, 42(5): 71-79.
[11]	冯杰,荆明娥,虞志益. 基于双层片上网络的路由算法[J]. 计算机工程, 2016, 42(4): 83-87.
[12]	田进华,魏长宝. 多核处理器中改进的动态缓存优化技术[J]. 计算机工程, 2015, 41(8): 46-51.
[13]	徐卫,刘端阳,暴占兵. 基于剩余能量的可分负载WSN 能耗均衡研究[J]. 计算机工程, 2015, 41(6): 66-70.
[14]	俞剑明,周炜,虞志益. 基于多层网络的片上网络可靠测试结构[J]. 计算机工程, 2015, 41(1): 275-278.
[15]	吴建宇,彭蔓蔓. 面向多线程应用的片上多核处理器私有LLC优化[J]. 计算机工程, 2015, 41(1): 316-321.

选择文件类型/文献管理软件名称

选择包含的内容