【作者】 全浩军；

【导师】 郭继昌； 张涛；

【作者基本信息】 天津大学 ， 信息与通信工程， 2013， 博士

【摘要】 在软硬件结合的嵌入式系统设计中，往往采用软硬件协同设计方法以缩短系统的研发周期，同时降低系统在成本、功耗等多方面的需求，而软硬件划分是软硬件协同设计中的重点和难点。现有的静态软硬件划分算法存在通用性差、对参数设置敏感、计算复杂等问题，而对动态软硬件划分的研究成果较少。本文以盲优化为主线对软硬件划分中划分与调度技术进行了深入研究，完成了以下工作：分析并指出了非盲优化软硬件划分中一维搜索算法存在的局限性，提出了基于贪婪规则的描述方法，该方法及相关定理的引入明确了一维搜索可以找到最优解的前提条件，保证了原理和算法的一致性。将人工鱼群算法引入到软硬件划分领域，从而提出一种新的软硬件划分盲优化方法。针对其应用于离散型问题时普遍存在的最优解出现概率低、收敛速度慢等问题，提出了基于随机步长和邻域搜索的改进方法。实验结果表明，改进后算法在寻优能力和收敛速度上优于原始算法，可更高效地完成软硬件划分任务。针对大规模系统的软硬件划分问题，提出了基于混合蛙跳算法的软硬件划分盲优化方法，并针对其存在的全局寻优能力差、收敛效率低等问题，提出了基于同优状态复位和双层自适应邻域搜索的改进方法。实验结果表明，在平均执行时间小于原算法的前提下，改进后算法的最优解等于或优于原算法，且最优解出现的次数等于或高于原算法。因此，改进后算法具有更强的全局寻优能力和更高的收敛效率。针对盲优化软硬件划分中的任务调度问题，提出了面向任务调度长度的METF算法和面向通信存储能力的MDF、MRF算法，并通过随机DAG图调度实验证明了以上三种算法的有效性。针对盲优化动态软硬件划分中的任务预测问题，提出了基于有序周期基的任务预测算法。对所选任务序列的预测实验表明，该算法具有一定的任务预测能力，可完成动态软硬件划分系统的预测任务。更多还原

【Abstract】 The method of hardware software co-design is always used in embedded systemdesign to shorten the development cycle of the system, while reducing system cost,power consumption, and many other requirements. And the emphasis and difficulty ofhardware software co-design is HW/SW partitioning. The existing algorithms forstatic HW/SW partitioning have sensitive parameter settings, high computationalcomplexity or other problems, while there is less study for dynamic HW/SWpartitioning. So, in the paper, the partitioning and scheduling technologies in HW/SWpartitioning are in-depth studied with the main clue of blind optimization, and thefollowing work is completed.The limitation of1DS algorithm in HW/SW partitioning is analyzed and pointedout, and then a description method based on greedy rule is proposed. The introducedmethod and related theorem make clear the precondition of finding optimumsolutions, and ensure the consistency of the theory and algorithm.The AFSA is introduced to HW/SW partitioning and a novel blind optimizationmethod for HW/SW partitioning is proposed. When AFSA is applied to solve discreteproblems, the optimum solution occurrence probability and the convergence speed arelow. So the improved methods based on random step and neighborhood searching areproposed. Experimental results show that the improved AFSA can achieve results insearch ability and convergence speed superior to original algorithm. Thus theimproved AFSA can execute HW/SW partitioning much more efficiently.The blind optimization method based on SFLA is introduced to HW/SWpartitioning for large-scale systems, and the improved methods based on same stateresetting and double-layer adaptive neighborhood searching are adopted to solve theproblems of poor global searching ability and low convergence efficiency.Experimental results show that, within a shorter run time, the optimum solution ofimproved SFLA is equal to or better than that of the original algorithm, and theoptimum solution occurrence probability is equal to or higher than that of the originalalgorithm. Thus the improved SFLA has better global searching ability and higherconvergence efficiency. Aiming at the task scheduling problem of blind-optimization-based HW/SWpartitioning, the METF algorithm oriented to scheduling length and the MDF, MRFalgorithm oriented to communication storage ability are proposed. Finally, theefficiency of the three algorithms is proved through scheduling experiments withrandom DAGs.Aiming at the task prediction problem of blind-optimization-based dynamicHW/SW partitioning, a task prediction algorithm based on ordered periodic base isproposed. The experiments of task scheduling prediction for selected task sequencesshow that the algorithm has the ability of task prediction and can complete predictiontasks for dynamic HW/SW partitioning.更多还原