论文部分内容阅读
异构MPSoC集成了不同类型的处理器内核的优点,被认为是高性能嵌入式计算平台未来的发展趋势。此种架构的嵌入式系统的设计包含了硬件设计和软件设计两个方面的内容,当前比较流行的设计方法是对软件和硬件同时进行设计,即软硬件协同设计。相关研究表明,任务的软硬件划分是软硬件协同设计过程中最为关键的步,对软硬件划分问题的研究已成为国内外研究的热点。因此,如何设计高性能的软硬件划分算法受到了研究者的广泛关注。在软硬件划分算法的研究中,常用贪心算法和模拟退火算法来对解空间进行寻优。贪心算法具有较低的计算复杂度,但只能获得局部最优解。模拟退火算法在理论上可以搜索到全局最优解,但算法的收敛速度相对较慢。本文针对双路软硬件划分系统模型的特点,借鉴求解0-1背包问题的相关算法思想,基于模拟退火算法的全局寻优特性,研究种融合贪心算法和模拟退火算法的软硬件划分方法,用以提高在硬件资源约束下的算法收敛速度和解质量。具体工作如下:针对传统的基于贪心算法的预划分算法忽略通信代价,导致预划分后得到的解的质量不高的问题,本文在分析了通信代价对软硬件划分结果的影响的基础上,结合0-1背包问题的解决方法,提出了种改进的基于贪心算法的预划分算法。首先基于传统预划分算法得到个初始解;然后把通信代价引入软硬件划分系统模型中,在此初始解的基础上,利用价值变化量与空间变化量的比值,对背包内外的物品再次进行取舍。对算法复杂度的分析表明,该算法在不提高计算复杂度的情况下,得到了更好的预划分效果。针对模拟退火算法在进行全局寻优时收敛速度较慢的问题,本文对模拟退火算法的算法收敛条件进行分析,并结合模拟退火算法计算复杂度主要由内外两层循环构成的特点,提出了种基于改进的模拟退火算法的全局寻优算法。首先对算法的扰动模型进行改进,改进后的模型增大了扰动距离取2和3的概率,减少了内层循环的计算复杂度;然后设计了种新的代价函数,提高了算法对解空间的搜索效率,使得算法可以尽快找到最优解,有效减少了外层循环次数。为了验证上述算法,本文基于TGFF工具和C++程序描述语言,分别实现了本文算法和对比算法,并以硬件面积作为约束条件,以算法运行时间和划分后系统时间作为性能指标,对算法进行对比分析。实验结果表明本文算法在算法收敛速度和解的质量方面都优于对比算法;同时,硬件资源条件越苛刻,本文算法的优势越明显。