本站原创
文章编号:10019081(2013)07189805
doi:10.11772/j.issn.10019081.201
软硬件划分是嵌入式系统设计过程中一个关键环节，已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛，且找到的全局最优解的质量不佳等问题，提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的01背包问题，在求解背包问题的算法基础上用贪心算法构造出初始划分解；然后，对代价函数的解空间进行合理的区域划分，并基于划分的区间设计新的代价函数，采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明，与目前已有的类似改进算法相比，新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右，具有高效性和实用性。
关键词：软硬件划分；启发式算法；01背包问题；模拟退火；代价函数
:A
英文标题
Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm
英文作者名
ZHANG Liang*, XU Cheng, TIAN Zheng, LI Tao
英文地址(
College of Information Science and Engineering, Hunan University, Changsha Hunan 410082, China英文摘要)
Abstract：
Hardware/Software (HW/SW) partitioning is one of the crucial steps in the codesign of embedded system, and it has been proven to be a NP problem. Considering that the latest work has slow convergence speed and poor solution quality, the authors proposed a HW/SW partitioning method based on greedy algorithm and Simulated Annealing (SA) algorithm. This method reduced the HW/SW partitioning problem to the extended 01 knapsack problem, and used the greedy algorithm to do the initial rapid partition; then divided the solution space reasonably and designed a new cost function and used the improved SA algorithm to search for the global optimal solution. Compared to the existing improved algorithms, the experimental results show that the new algorithm is more effective and practical in terms of the quality of partitioning and the running time, and the promotion proportions are 8% and 17% respectively.
Hardware/software (HW/SW) partitioning is one of the crucial steps in the codesign of embedded system, and it has been proven to be a NP problem. Considering that the latest work has slow convergence speed and poor solution quality, the authors proposed a HW/SW partitioning method based on greedy algorit
英文关键词Key words:
Hardware/Software (HW/SW) partitioning; heuristic algorithm; 01 knapsack problem; Simulated Annealing (SA); cost function
0 引言
随着半导体工艺的发展，由通用微处理器和硬件处理单元组成的新型嵌入式系统的应用越来越广泛。软硬件协同设计已成为嵌入式领域的主流技术。众所周知，硬件的执行速度快，但往往资源有限，且成本较高；而软件的执行速度较慢，但操作灵活，成本较低。因此，能否合理地把任务划分到软硬件执行，将对整个嵌入式系统的性能有着重要的影响［1］。
软硬件划分是软硬件协同设计过程中的一个关键问题，该问题已经被证明是一个典型的多目标优化问题［2］。关于软硬件划分的问题目前国内外已经有了大量的研究，主要集中在利用启发式算法寻求近似全局最优解。主流的算法有贪心算法［3］、遗传算法［4-5］和模拟退火算法［6-9］。
doi:10.11772/j.issn.1001908
1.2013.07.1898
摘 要：
软硬件划分是嵌入式系统设计过程中一个关键环节，已经被证明是一个NP问题。针对目前算法在进行大任务集下的软硬件划分时计算复杂度高、不能快速收敛，且找到的全局最优解的质量不佳等问题，提出一种基于贪心算法和模拟退火算法相融合的软硬件划分方法。首先将软硬件划分问题规约为变异的01背包问题，在求解背包问题的算法基础上用贪心算法构造出初始划分解；然后，对代价函数的解空间进行合理的区域划分，并基于划分的区间设计新的代价函数，采用改进的模拟退火算法对初始划分进行全局寻优。实验结果表明，与目前已有的类似改进算法相比，新算法在任务划分质量和算法运行时间两个方面的提升率最大可达到8%和17%左右，具有高效性和实用性。关键词：软硬件划分；启发式算法；01背包问题；模拟退火；代价函数
:A
英文标题
Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm
英文作者名
ZHANG Liang*, XU Cheng, TIAN Zheng, LI Tao
英文地址(
College of Information Science and Engineering, Hunan University, Changsha Hunan 410082, China英文摘要)
Abstract：
Hardware/Software (HW/SW) partitioning is one of the crucial steps in the codesign of embedded system, and it has been proven to be a NP problem. Considering that the latest work has slow convergence speed and poor solution quality, the authors proposed a HW/SW partitioning method based on greedy algorithm and Simulated Annealing (SA) algorithm. This method reduced the HW/SW partitioning problem to the extended 01 knapsack problem, and used the greedy algorithm to do the initial rapid partition; then divided the solution space reasonably and designed a new cost function and used the improved SA algorithm to search for the global optimal solution. Compared to the existing improved algorithms, the experimental results show that the new algorithm is more effective and practical in terms of the quality of partitioning and the running time, and the promotion proportions are 8% and 17% respectively.
Hardware/software (HW/SW) partitioning is one of the crucial steps in the codesign of embedded system, and it has been proven to be a NP problem. Considering that the latest work has slow convergence speed and poor solution quality, the authors proposed a HW/SW partitioning method based on greedy algorit
源于：如何写论文www.udooo.com
hm and Simulated Annealing (SA) algorithm. This method reduced the HW/SW partitioning problem to the extended 01 knapsack problem, and used the greedy algorithms to do the initial rapid partition; then divided the solution space reasonably and designed a new cost function and used the improved SA algorithm to search the global optimal solution. Compared to the existing improved algorithms, the experimental results show that the new algorithm is more effective and practical in the aspects of the quality of partitioning and the running time, and the promotion rate are 8% and 17%.英文关键词Key words:
Hardware/Software (HW/SW) partitioning; heuristic algorithm; 01 knapsack problem; Simulated Annealing (SA); cost function
0 引言
随着半导体工艺的发展，由通用微处理器和硬件处理单元组成的新型嵌入式系统的应用越来越广泛。软硬件协同设计已成为嵌入式领域的主流技术。众所周知，硬件的执行速度快，但往往资源有限，且成本较高；而软件的执行速度较慢，但操作灵活，成本较低。因此，能否合理地把任务划分到软硬件执行，将对整个嵌入式系统的性能有着重要的影响［1］。
软硬件划分是软硬件协同设计过程中的一个关键问题，该问题已经被证明是一个典型的多目标优化问题［2］。关于软硬件划分的问题目前国内外已经有了大量的研究，主要集中在利用启发式算法寻求近似全局最优解。主流的算法有贪心算法［3］、遗传算法［4-5］和模拟退火算法［6-9］。