功率约束下基于ILP和MSH算法的动态线程映射  

Dynamic thread mapping based on ILP and MSH algorithm under power constraint

作　　者：何燕飞[1] 辜寄蓉[2] 汤振华 He Yanfei;Gu Jirong;Tang Zhenhua(Department of Information Technology,Zhejiang Yuying Vocational and Technical College,Hangzhou 310018,China;College of Geography and Resources Science,Sichuan Normal University,Chengdu 610101,China;Center of Radio and TV Media Technology,Zhejiang Radio and TV Group,Hangzhou 310018,China)

机构地区：[1]浙江育英职业技术学院信息技术分院,杭州310018 [2]四川师范大学地理与资源科学学院,成都610101 [3]浙江广播电视集团广播电视融媒体技术中心,杭州310000

出　　处：《国外电子测量技术》2021年第7期30-36,共7页Foreign Electronic Measurement Technology

基　　金：浙江省教育厅科研课题(Y201942750)项目资助。

摘　　要：针对功率约束下异构多核系统中的线程映射进行了研究。将线程映射问题构建为一个在功率约束下的0~1整数线性规划,然后提出了一种基于最大化-交换启发式的有效算法,尝试获得尽可能高的吞吐量而不考虑功率约束,在相邻核类型之间执行虚拟线程交换,以满足功率预算要求。仿真实验结果表明,在给定功率预算约束下,算法不仅能够在总吞吐量方面得到与最优解平均相差不超过0.5%的映射,而且在运行时间开销方面,比商用ILP求解器要快2个数量级以上;同时提出的算法可扩展到在线运行上百个核的异构系统,且其运行时间开销也在ms之内。In this paper, the thread mapping is studied in heterogeneous multicore systems under power constraints.Firstly, the problem of thread mapping is constructed as a 0~1 integer linear programming under power constraints, and then an effective algorithm based on maximization-swapping heuristic is proposed.The proposed algorithm first tries to obtain as high throughput as possible without considering power constraints, and then performs virtual thread swapping between adjacent kernel types to meet the power budget requirements;The simulation results show that under a given the power budget constraint, the proposed algorithm produces mappings less than 0.5% away from the optimal solution on average in terms of total throughput, but also more than 2 orders of magnitude faster than the commercial ILP solver in terms of runtime overheads. At the same time, the proposed algorithm can be extended to heterogeneous systems running hundreds of cores online, and its runtime overhead is also within ms.

关 键 词：异构多核系统 功率约束 线程映射 整数线性规划 最大化-交换启发式算法 吞吐量 运行时间开销 

分 类 号：TP302.7[自动化与计算机技术—计算机系统结构]