动态可重构FPGA布局算法的研究与改进

论文摘要

随着嵌入式系统复杂度的不断提高,以FPGA(Field Programmable Gate Array)为代表的可编程逻辑器件得到了广泛的应用。FPGA为开发者提供了便捷的硬件电路设计方案,通过FPGA辅助设计软件可以在线的完成硬件电路设计的整个过程,大大缩短了嵌入式系统的开发周期。在FPGA硬件电路的设计流程中,布局是最耗时的一个阶段,也是对最终生成的硬件电路质量影响较大的一个阶段,提高布局阶段的效率往往能够较大程度的缩短FPGA的设计周期,因而关于FPGA布局问题的研究一直是近年来的热点。FPGA布局需要解决两个主要问题,布局评价方法的确定和布局算法的设计。布局评价方法决定了布局的优化方向。现有的布局软件通常以连接各个逻辑块的布线长度来作为布局优劣的评价标准,随着动态可重构FPGA的发展,单纯考虑布线长度的布局评价方法体现出一定的局限性。本文对此问题进行了研究,并在对原有方法局限性进行分析的基础上提出了综合考虑布线长度,面积代价布局评价方法。实验表明,新的布局评价方法能够有效的较少布局面积。FPGA布局算法关系到布局求解的效率和最终布局的质量。FPGA布局是一个NP难问题,通常需要采用启发式算法对布局进行迭代求解,目前已有一些布局工具如VPR采用模拟退火算法来进行求解。本文研究了FPGA布局问题的模拟退火解决方案,并对其局限性进行了分析,在此基础上提出了遗传算法解决方案和自动控温的改进模拟退火算法解决方案,通过实验对三者的性能进行了对比,分析了算法的效率和扩展性问题。最后利用自动控温的模拟退火算法对VPR布局工具进行了改进。测试结果显示,改进后的VPR布局工具能够在不牺牲布局质量的情况下,高效率的完成布局,并且很好的解决了原布局算法所存在退火进度控制问题,建立起退火进度和布局优化速度的联系,具有良好的扩展性和可用性。

论文目录

• 中文摘要
• ABSTRACT
• 第1章 引言
• 1.1 论文研究背景
• 1.2 FPGA布局问题研究现状
• 1.3 论文研究内容及组织结构
• 第2章 FPGA基本结构和设计流程
• 2.1 FPGA的基本结构
• 2.2 FPGA的设计流程
• 2.2.1 逻辑综合
• 2.2.2 工艺映射
• 2.2.3 布局
• 2.2.4 布线
• 2.2.5 比特流的生成
• 2.3 FPGA布局原理
• 2.4 本章小结
• 第3章 FPGA布局评价方法的研究
• 3.1 FPGA布局的基本目标
• 3.2 FPGA布局中的线长估计
• 3.2.1 常用的线长估计法
• 3.2.2 线长估计法的选择
• 3.3 基于线网半周长的布局评价方法
• 3.3.1 线网半周长的基本概念
• 3.3.2 线长代价函数
• 3.3.3 布局评价法的局限性
• 3.4 考虑面积代价的布局评价方法
• 3.4.1 面积代价函数
• 3.4.2 计算面积代价的算法
• 3.5 布局评价方法的扩展
• 3.6 本章小结
• 第4章 FPGA布局算法的研究与改进
• 4.1 布局算法概述
• 4.2 传统的模拟退火算法解决方案
• 4.2.1 模拟退火算法原理
• 4.2.2 解空间编码
• 4.2.3 解调整策略
• 4.2.4 能量函数和新解接受策略
• 4.2.5 初始温度的选取和降温策略
• 4.2.6 基于模拟退火的布局算法
• 4.2.7 实验结果及算法局限性分析
• 4.3 基于遗传算法的改进方案
• 4.3.1 解空间编码
• 4.3.2 选择操作
• 4.3.3 交叉操作
• 4.3.4 变异操作
• 4.3.5 控制参数的选取
• 4.3.6 算法流程
• 4.4 基于自动控温退火算法的改进方案
• 4.4.1 新解接受策略的设计
• 4.4.2 布局质量调整系数k的确定
• 4.4.3 退火进度表的设计
• 4.4.4 算法流程
• 4.5 实验结果对比
• 4.5.1 算法时间性能对比
• 4.5.2 算法可扩展性对比
• 4.5.3 结果分析
• 4.6 本章小结
• 第5章 改进算法在VPR布局工具中的实现
• 5.1 VPR布局工具简介
• 5.2 VPR布局算法分析
• 5.3 对VPR布局工具的改进
• 5.3.1 布局工具基本结构
• 5.3.2 符号表生成模块的设计
• 5.3.3 布局模块的设计
• 5.4 系统调试与测试
• 5.4.1 输入文件格式
• 5.4.2 运行结果
• 5.4.3 结果分析与对比
• 5.5 本章小结
• 第6章 总结和展望
• 6.1 论文工作总结
• 6.2 未来工作及展望
• 参考文献
• 致谢
• 科研项目和论文发表情况