盲优化软硬件划分技术研究

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 研究背景
• 1.1.1 嵌入式系统的广泛应用及设计需求
• 1.1.2 嵌入式系统设计与软硬件划分
• 1.2 软硬件划分研究现状
• 1.2.1 划分算法
• 1.2.2 应用平台与系统模型
• 1.2.3 任务调度
• 1.2.4 优化目标
• 1.2.5 系统实现
• 1.2.6 动态软硬件划分
• 1.2.7 研究现状总结
• 1.3 本文的应用平台与系统模型
• 1.4 论文的主要贡献
• 1.5 论文的组织结构
• 第二章 盲优化与非盲优化算法及其在软硬件划分中的应用
• 2.1 盲优化
• 2.2 非盲优化算法及其在软硬件划分中的应用
• 2.2.1 贪婪算法
• 2.2.2 一维搜索算法
• 2.3 盲优化算法及其在软硬件划分中的应用
• 2.3.1 遗传算法
• 2.3.2 蚁群算法
• 2.3.3 粒子群优化算法
• 2.3.4 人工蜂群算法
• 2.4 算法分析及总结
• 2.4.1 盲优化算法的基本特征
• 2.4.2 盲优化与非盲优化算法的相互转化
• 2.4.3 优缺点分析及软硬件划分盲优化的必要性
• 2.5 本章小结
• 第三章 基于 IAFSA 的软硬件划分盲优化方法
• 3.1 鱼群行为与 AFSA
• 3.2 基于 AFSA 的软硬件划分盲优化方法
• 3.2.1 软硬件划分问题的特殊性及对算法设计的影响
• 3.2.2 数学描述
• 3.2.3 算法描述
• 3.3 算法分析及改进
• 3.3.1 随机步长
• 3.3.2 邻域搜索
• 3.4 实验结果及对比分析
• 3.5 本章小结
• 第四章 基于 ISFLA 的软硬件划分盲优化方法
• 4.1 分组进化行为与 SFLA
• 4.2 基于 SFLA 的软硬件划分盲优化方法
• 4.2.1 数学描述
• 4.2.2 算法描述
• 4.3 算法分析及改进
• 4.3.1 同优状态复位
• 4.3.2 双层自适应邻域搜索
• 4.4 实验结果及对比分析
• 4.5 本章小结
• 第五章 面向盲优化软硬件划分的任务调度算法
• 5.1 任务调度原理及算法选择
• 5.1.1 任务调度算法原理
• 5.1.2 算法分析与选择
• 5.2 面向盲优化软硬件划分调度长度的调度算法
• 5.2.1 盲优化软硬件划分中任务调度的特殊性
• 5.2.2 面向调度长度的 METF 算法
• 5.3 面向盲优化软硬件划分通信存储能力的调度算法
• 5.3.1 任务调度中的通信存储问题
• 5.3.2 系统模型分析
• 5.3.3 面向通信存储能力的 MDF 和 MRF 算法
• 5.4 实验结果及分析
• 5.5 本章小结
• 第六章 盲优化动态软硬件划分方法
• 6.1 划分方法研究
• 6.1.1 基于统计信息的运行时划分方法
• 6.1.2 基于任务调度的划分方法
• 6.1.3 基于可满足性模理论的划分方法
• 6.1.4 基于盲优化的划分方法
• 6.2 盲优化动态软硬件划分方法
• 6.2.1 三层反馈动态软硬件划分框架
• 6.2.2 基于 IAFSA-METF 算法的软硬件划分与任务调度
• 6.2.3 基于有序周期基的任务预测算法
• 6.3 本章小结
• 第七章 总结与展望
• 7.1 工作总结
• 7.2 工作展望
• 参考文献
• 发表论文和参加科研情况说明
• 附录 缩略词
• 致谢