基于改进模拟退火的RISP软硬件划分

Hardware/Software Partitioning of RISP Based on Improved Simulated Annealing Algorithm

摘要:

软硬件划分是可重构指令集处理器在软硬件协同设计中的关键问题,已经被证明是一个NP难问题；模拟退火在解决该类问题的算法中较为常用,但在任务数变大时,其收敛速度过慢且不一定能找到有效近似最优解,通过将Cauchy分布引入扰动模型同时将其距离参数Δy乘上一个系数,然后在已有代价函数的基础上提出一个更加有效的边界条件,最后将冷却进度表的算式乘上一个权值,以此加快算法的收敛速度；实验结果表明,和经典模拟退火算法相比,新算法的收敛速度明显提高,同时得到的解更接近最优解,其性能优势在任务数增大时尤为明显。

Abstract:

Hardware/software partitioning is the key issue of Reconfigurable Instruction Sets Processor (RISP) in hardware/software co-design, what has been proved to be a NP problem. Simulated annealing algorithm (SA) is always the useful method to solve this kind of problems. However, the convergence speed for finding the approximately optimal solution will be slow when the count of tasks become larger. By improving the distance parameter of the perturb model using Cauchy distributing and the annealing schedule, then proposing a more effective boundary condition on the basis of the existing cost function, the speed of convergence will be accelerated. Compared to the classical simulated annealing algorithm, the final experiments indicate that using improved algorithm can significantly accelerate the convergence speed meanwhile increase the ability of finding an approximately optimal solution. 