文章编号：1004－5422(2021)03－0256－06                                               DOI:10.3969/j.issn.1004-5422.2021.03.006

覃志东 ¹, 冯  莹¹, 肖芳雄²

（1.东华大学  计算机科学与技术学院，上海  201620；2.金陵科技学院  软件工程学院，江苏 南京  211169）

摘  要：众核软件映射到处理器核心上，形成流水线执行，有利于挖掘软件任务模块的并行性，提高系统吞吐率.提出了一种基于改进的动态规划思路的软件映射算法，算法通过将图划分问题近似分解为多个子问题，通过寻求每个子问题的最优解进而获得全局最优解.动态规划思路的改进主要体现在实时更新可选任务节点和动态调整子图期望负载两方面，这有利于划分后的各子图负载更均衡.实验结果表明，算法在提高系统吞吐率方面均优于现有相关算法.
关键词：软件映射；启发式算法；动态规划
中图分类号：TP301.6;TP311.52            文献标识码：A

A Many-Core Software Mapping Algorithm Based on Dynamic Programming

(1. School of Computer Science and Technology, Donghua University, Shanghai 201620, China; 

2. Software Engineering School of Jinling Institute of Technology, Nanjing, 211169, China)  

Abstract：When many-core software is mapped to the processor cores to form executing pipeline, it is conducive to mining the parallelism of software task modules, and improving the system throughput. A software mapping algorithm based on dynamic programming is proposed in this paper. The algorithm decomposes the graph partition problem into several sub-problems, and seeks the optimal solution to each sub-problem to obtain the global optimal solution. The improvement of dynamic programming is mainly reflected in two aspects: updating the optional task nodes real-timely and adjusting the expected load of subgraphs dynamically. That is conducive to more balanced load of each subgraph after graph partitioning. Experimental results show that the algorithm is superior to the existing algorithms in improving the throughput of systems.
Key words：many-core software mapping; heuristic algorithms; dynamic programming