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

论文摘要

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

论文目录

• 摘要
• Abstract
• 插图索引
• 插表索引
• 第1章 绪论
• 1.1 研究背景及意义
• 1.1.1 嵌入式系统发展趋势
• 1.1.2 软硬件协同设计
• 1.1.3 研究意义
• 1.2 课题来源
• 1.3 研究目标
• 1.4 主要工作
• 1.5 本文的组织结构
• 第2章 可重构计算系统中软硬件划分相关研究
• 2.1 可重构计算系统
• 2.1.1 可重构计算系统概述
• 2.1.2 可重构计算系统分类
• 2.1.3 可重构计算系统耦合方式
• 2.2 软硬件划分问题
• 2.2.1 软硬件划分概述
• 2.2.2 系统描述
• 2.2.3 粒度选择
• 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 小结
• 第3章 基于改进模拟退火算法的软硬件划分
• 3.1 引言
• 3.2 软硬件划分系统抽象模型
• 3.2.1 系统体系结构抽象
• 3.2.2 系统建模
• 3.3 改进的软硬件划分算法
• 3.3.1 模拟退火算法分析
• 3.3.2 模拟退火算法改进
• 3.4 算法评价
• 3.4.1 评价指标
• 3.4.2 仿真系统设计与实现
• 3.4.3 实验结果分析
• 3.5 小结
• 第4章 面向大任务集的软硬件划分
• 4.1 引言
• 4.2 大任务集下初始化划分
• 4.2.1 基于 0-1 背包的软硬件划分模型
• 4.2.2 基于贪心算法的初始化策略
• 4.3 改进的软硬件划分算法
• 4.4 实验结果分析
• 4.5 小结
• 总结
• 参考文献
• 致谢
• 附录 A 攻读学位期间发表的学术论文及参与的科研项目