多选择软硬件划分问题的算法研究

摘要

软硬件划分是软硬件协同设计的关键环节，划分的结果直接影响目标系统的设计质量。由于单个任务具有多种不同的硬件实现方式，与传统的单一硬件实现方式的软硬件划分问题相比，多选择的软硬件划分更能客观地反映现实应用。这导致问题的求解更具挑战性，它们已被证明是NP完全问题。本文对于两种不同任务图模型上的多选择软硬件划分问题分别做了算法方面的研究。
　　对于简单任务图模型上的多选择软硬件划分问题，分别使用模拟退火算法和遗传算法，提出了可行性的解决方案。并与禁忌搜索算法进行比较，寻找多选择软硬件划分问题的相对较好的启发式算法。实验结果表明，在求得的解的质量方面，禁忌搜索算法相比于其他两种算法而言是最好的;在获得较好解的速度方面，模拟退火算法和遗传算法要比禁忌搜索算法快的多。
　　针对多核处理器片上系统上的多选择软硬件划分问题，建立了任务图为二叉树的多选择软硬件划分问题的计算模型，并分别提出了启发式算法、禁忌搜索算法以及动态规划算法来解决该问题。实验结果表明，当问题规模较小时，所提动态规划算法能够获得多选择软硬件划分问题的精确解;当问题规模和硬件面积限制都较大时，启发式算法可以快速有效地得到一个非常接近于精确解的优质近似解;当问题规模较大、硬件面积限制较小时，启发式算法先快速产生一个初始解，然后禁忌搜索算法对这个初始解进行优化，从而得到一个较好的近似解。

目录

声明

摘要

第一章 前言

1．1 研究背景

1．2 研究现状

1．3 存在的问题

1．4 研究内容和目标

1．5 论文组织结构

第二章 智能优化算法

2．1 智能优化算法概述

2．2 遗传算法

2．3 模拟退火算法

2．4 禁忌搜索算法

2．5 本章小结

第三章 简单模型上的多选择软硬件划分

3．1 多选择软硬件划分问题

3．2 计算模型及问题描述

3．3 模拟退火算法

3．4 遗传算法

3．5 实验结果及分析

3．5．1 实验参数的设置

3．5．2 三种算法的比较和分析

3．5．3 实验结论

3．6 本章小结

第四章 树型任务图上的多选择软硬件划分

4．1 计算模型及问题描述

4．1．1 MPSoC的体系结构模型

4．1．2 CFG模型

4．1．3 二叉树上的多选择软硬件划分

4．2 启发式算法

4．3 禁忌搜索算法

4．4 动态规划算法

4．5 实验结果与分析

4．5．1 实验参数的设置

4．5．2 三种算法的比较与分析

4．5．3 实验结论

4．6 本章小结

第五章 总结与展望

5．1 回顾与总结

5．2 未来工作展望

参考文献

发表论文和参加科研情况说明

致谢