双目标的软硬件划分算法研究

《双目标的软硬件划分算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第一章引言面的优化，实现整个应用程序的目的晴1。面向软件的设计方法，首先假定所有组件在软件上实现，逐个将组件块转移到硬件上，以加速整个应用程序的速度¨1。相应的编译技术也被研制出来，通过使用一个程序探测器来追踪每个指令块的被执行频率阳儿引，并把执行频率高的指令块优先分派给硬件实现．这种程序探测器的代表为SUIF编译器n0。，它还可以分辨出循环体内可并行执行的指令块。许多现代的智能优化方法也被广泛地研究并应用于求解软硬件划分问题，[11]构造了可行的遗传算法，[7]、[12]、[13]使用了模拟退火算法，[14]、[15]完成了对遗传算法、模拟退火算法、和禁忌搜索

2、算法的比较，得出禁忌搜索在求解软硬件的粗粒度划分问题上优于其他两种算法。一种被称作蚂蚁系统的搜索算法也被应用到求解软硬件划分的问题上n⋯，全局最优与局部最优策略被综合应用到该搜索过程中。随着小体积电子产品的市场需求不断增加，高速并且低功耗的目标系统的研制备受关注，在以低功耗为目标的软硬件划分问题上也有相应的研究“7¨”m1。在近期的研究成果中，文献[20]将应用程序对应于一个有向任务图，图的顶点代表相应的子过程或函数，顶点间的边对应过程或函数间的控制关系。在此基础上从理论的角度对软硬件划分问题进行了分类，一类为多项式可解的，另一类为NP难解的，并给出了求解此类难

3、解问题的近似算法。文献[21]相继对这类难解问题给出了多项式近似算法，对不同约束条件下的软硬件划分问题给出了问题复杂度的下界。文献[22]将任务的硬件实现设定在可塑性较强的FPGA(Field-programmableGateArray)上，进而将软硬件划分问题视作广义的作业调度问题来进行启发式算法求解。借助可满足性(SAT)问题的求解方案，建立了求解软硬件划分问题的一个计算模型。文献[23]在部分可重构的硬件环境下的软硬件划分和调度问题，如FPGA。文献[24]研究了在动态可重构环境下，在合成和编译阶段，基于时间的划分。文献[25]设计了一个基于动态可重构环境

4、下的框架，考虑了重构时需要的代价。文献[26]提出了在可重构环境下的任务划分和调度的一个启发式算法。尽管如此，现有的研究工作对软硬件划分问题的探讨是基于特定的硬件环境，目前缺乏公认的性能评价体系，很难通过对比来确定哪一种方法具有明显的优势心71。国内学者也在软硬件划分问题上做了相应研究，有些成果不局限于只考虑软件和硬件两种实现方式的传统划分。例如，文献[28]在软硬件划分和任务调度之间加入了筛选步骤，同时对软硬件划分后的结果的硬件面积进行预先估计，依据预先估计的结果进行筛选，择优调度，加速系统的运行。部分学者对不同条件或者环境下的软硬件划分问题进行了探究。在算法

5、层面上，人们对混沌优化方法髓⋯，蚂蚁寻优策略鼬㈨3进行了尝试，以求有效避免搜索过程陷入局部最优。同时对传统的分枝界限算法口引、遗传算法口朝等也有讨论，并将软硬件划分映射和任务调度天津工业大学硕士学位论文合二为一，从而在调度过程中同时完成软硬件的映射，充分地发挥了任务调度的作用[33]o我导师的课题组近年来一直在软硬件协同设计的核心算法领域上做相应的研究。主要成果概述如下。粗粒度层面上，对于给定的作业(对应于任务图)，提出了一个高效的启发式划分算法m1，该算法迭代地选择性能价格比最优的任务优先安排在硬件上实现，同时动态更新性价比，此算法为高质量的划分结果提供了保障

6、。与此同时，基于动态关键路径的任务调度策略进一步提高了目标系统的执行速度。细粒度层面上，对动态规划策略进行了改进b51，使软硬件划分问题的复杂度从平方量级降到线性量级。进而对计算模型又进行了细化，新的计算模型，拓宽了原来计算模型的表达能力，使得相邻模块间各种可能的通讯开销在目标函数中得以体现口引。我们对功耗以及硬件使用面积的最小化等方面的研究也有突破性的进展，将求解0-1背包问题的策略扩展并成功应用到软硬件划分问题的数学建模与算法求解上b7H3引。文献[39]则是将快速启发式算法与禁忌搜索算法成功的混成使用，产生了几乎最优的近似解。并且将搜索空间从原来的2维归约

7、成1维，在不降低解的质量的同时，大大提高了软硬件划分的速度H⋯。对于同一个组件，在不同的硬件下实现的速度、功耗、面积都不一样，这又增加了解的空间，加大了问题求解难度。最近的研究成果，文献[41]在考虑通讯的同时也考虑了硬件实施的多样性，采用了基于多选择背包问题的启发式求解算法、禁忌搜索算法优化启发解取得了很好的效果。1．3存在的问题和发展趋势通过总结国内外的研究现状可知，软硬件划分的相关技术正处在孕育发展阶段。虽然学术界已经有很多理论成果与求解算法，但很多技术仍未成熟，用于片上系统的商用自动设计工具尚在研发阶段。前人的理论研究，大多是单目标的即在一定的代价下，优

8、化运行时间或者功耗；或者