基于模拟退火算法的可重构计算系统软硬件划分方法研究

摘要

可重构计算系统通常由通用处理器和可编程器件组成，同时拥有受限的硬件资源和软件资源。任务可以被划分到软件或者硬件上执行，但两者将在任务执行时间、功耗等方面产生显著的差别。为了充分利用硬件资源并使系统满足应用场景需求，需要对任务进行有效的软硬件划分。软硬件划分是当前可重构计算系统设计中的关键步骤和研究热点。
　　 软硬件划分为组合优化问题，已经被证明为NP问题，目前的研究主要是基于启发式算法来解决此类问题，研究的重点在于提高算法的收敛速度和解的质量。因此本文在两种任务集规模下，提出改进的启发式划分算法来提高算法收敛速度和解质量。
　　 在中小规模任务集的情况下，使用改进的模拟退火算法进行软硬件划分。模拟退火算法是解决软硬件划分问题常用的启发式算法，但是其收敛速度过慢且解的质量有待提高。本文通过改进算法的扰动模型和退火进度来改进其收敛速度慢的问题。针对算法存在解质量较差的问题，本文在总结现有代价函数的基础上提出一种新的代价函数计算方法。该方法对算法在解空间上的搜索方向进行引导，避免了搜索的盲目性，从而使算法能快速搜索到近似最优解，提高划分质量。
　　 在大规模任务集的情况下，结合改进的贪心算法和模拟退火算法对软硬件划分进行了研究。在大任务集下，单纯使用一种启发式算法会导致算法运行时间增加及划分质量下降。针对存在的上述问题，在文中首先使用改进的贪心算法对任务集进行初始化。贪心算法时间复杂度较低且容易实现，输出的解能接近全局近似最优解所在区域。然后使用改进的模拟退火算法，在初始化的基础上继续进行搜索。模拟退火算法全局搜索能力较强，能最终获得全局近似最优解。
　　 为验证本文算法，使用通用的TGFF工具生成随机的测试任务集，在同一平台上实现了本文算法和对比算法。实验分析表明，本文的算法在中小任务规模下，运行时间较对比的算法减少，同时解的质量有所提高。在大任务集下，本文算法的运行时间虽较贪心算法要长，但解得质量要高；同时本文算法在运行时间和解的质量上都较对比的模拟退火算法要优。