基于遗传和禁忌搜索混合的SoC软硬件划分方法研究

摘要

微电子工艺的快速发展促使集成电路进入SoC时代，但是随着设计复杂度的提高，传统的设计方法已经无法满足片上系统设计的需要。因此软硬件协同设计方法学应运而生，而软硬件划分技术又是软硬件协同设计技术中的关键技术之一。因此，研究SoC设计中的软硬件划分方法，构建一种合理的系统描述模型，提出划分算法并对其进行优化改进，将有十分重要的理论及应用价值。 本文介绍了软硬件协同设计的研究领域以及国内外的发展现状，重点研究了在解决软硬件划分问题所使采用的数学模型，同时分析了目前划分技术中普遍存在的问题。比较遗传算法（Genetic Algorithm，GA）和禁忌搜索（Tabu Search，TS）各自优缺点的基础上，面向嵌入式系统和SoC软硬件双路划分问题，本文创新性地提出了提出遗传禁忌搜索混合算法（Genetic Algorithm and Tabu Search，GATS）的策略，采用免费任务图（Task Graph for Free，TGFF）工具生成的有向无环图作为软硬件双路划分的数学模型，用GA提供并行搜索的主框架，TS作为GA的变异算子，GA中变异过程解空间的搜索由TS实现。 最后，将GA、TS算法与GATS算法分别使用由TGFF工具生成的真实数据进行编程，对比验证，验证结果表明GATS算法能够克服GA爬山能力差、TS单点出发的弱点，从而得到更优秀，精度更高的划分结果。

目录

文摘

英文文摘

声明

第1章 绪论

1.1 课题研究背景及意义

1.2 软硬件协同设计研究领域

1.2.1 系统任务描述

1.2.2 软硬件划分

1.2.3 软硬件并行综合

1.2.4 软硬件协同模拟和仿真

1.3 软硬件协同设计的国内外研究现状

1.3.1 国外研究现状

1.3.2 国内研究现状

1.3.3 研究不足

1.4 课题的来源及研究内容

1.4.1 课题来源

1.4.2 课题的主要研究内容

第2章 软硬件划分的相关理论

2.1 概述

2.1.1 系统结构

2.1.2 软硬件划分种类

2.2 系统模型的建立方法

2.2.1 有限状态机建模

2.2.2 数据流图建模

2.2.3 Petri网建模

2.2.4 数据/控制流图

2.2.5 任务流图

2.3 软硬件划分技术中存在问题的分析

2.3.1 说明抽象的层次

2.3.2 划分粒度的问题

2.3.3 系统中元件的分配

2.3.4 指标和评估问题

2.3.5 划分算法问题

2.3.6 可重配置计算

2.4 本章小结

第3章 遗传和禁忌搜索算法研究与分析

3.1 引言

3.2 遗传算法

3.2.1 遗传算法的特点

3.2.2 遗传算法基本原理

3.2.3 遗传算法的应用领域

3.2.4 遗传算法的编码方式

3.2.5 适应度函数

3.2.6 遗传操作算子

3.2.7 遗传算法的实现步骤

3.3 禁忌搜索算法

3.3.1 禁忌搜索算法基本思想

3.3.2 初始解

3.3.3 邻域结构与候选解

3.3.4 禁忌对象和禁忌长度

3.3.5 特赦准则

3.3.6 终止准则

3.3.7 禁忌搜索算法的流程

3.4 遗传和禁忌搜索混合算法

3.5 本章小结

第4章 GATS软硬件划分方法实现

4.1 引言

4.2 遗传和禁忌搜索算法对比分析

4.2.1 遗传算法GA优缺点

4.2.2 禁忌搜索TS算法优缺点

4.3 算法实现

4.3.1 软硬件划分模型

4.3.2 软硬件划分功能描述

4.3.3 目标系统结构

4.3.4 GATS问题描述

4.3.5 适应度函数

4.3.6 算法实现过程

4.4 本章小结

第5章 算法验证及结果分析

5.1 引言

5.2 算法验证及分析

5.2.1 30个节点的GA，TS和GATS运行结果比较

5.2.2 90个节点的GA，TS和GATS运行结果比较

5.3 本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢