FPGA自动布局布线算法

论文摘要

微电子技术的发展,特别是可编程逻辑器件的产生加速了电子设计技术的发展,现代电子设计技术的核心日趋转向基于计算机的电子设计自动化技术,即EDA技术。EDA技术采用的自顶向下设计流程代替了原有的自下而上设计流程,缩短了集成电路的开发周期,节省了开发费用,促进了集成电路的发展。布局布线是计算机设计自动化的一个重要环节,也是计算机辅助设计的一个重要课题,其性能的好坏直接影响到电子设计自动化技术的可靠性。本文首先介绍了布局布线前的背景知识,然后对学术上成熟的VPR布局布线工具所采用的算法进行了阐述,分别介绍用于布局的模拟退火算法和布线的A*迭代式迷宫搜索算法,最后重点研究了自动布线算法,并作出了以下改进:根据FPGA布线算法的需要对双向启发式搜索算法进行了相应的理论分析及改进;基于VPR实现了网线递增排序方法,并与网线递减排序进行了比较;在原有的时序驱动布线启发式函数中引入了面积约束条件以节约FPGA布线的面积。通过对测试数据的分析比较,发现:引入双向启发式搜索算法能大大增加布线拆线的速度;递增有序比递减有序布线减少了运行时间;时序驱动布线算法中引入面积约束后,大大减少了布线面积。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 引言
• 1.2 研究现状
• 1.3 论文的组织结构
• 第二章 布局布线背景知识
• 2.1 FPGA内部结构及设计流程
• 2.1.1 FPGA内部结构
• 2.1.2 FPGA设计流程
• 2.2 自动布线算法回顾
• 2.2.1 自动布线常用算法
• 2.2.2 自动布线启发式函数
• 2.3 本章小结
• 第三章 VPR自动布局布线算法
• 3.1 VPR布局布线工具
• 3.1.1 通道宽度描述
• 3.1.2 逻辑块描述
• 3.1.3 详细布线结构描述
• 3.1.4 时序分析参数
• 3.2 VPR采取的自动布局布线算法
• 3.2.1 自动布局算法
• 3.2.2 自动布线算法
• 3.3 本章小结
• 第四章 自动布线算法的改进
• 4.1 布线加速算法
• 4.1.1 双向搜索算法原理
• 4.1.2 消除双向启发式搜索算法缺陷
• 4.1.3 双向启发式搜索算法的优势
• 4.2 时序驱动布线算法的改进
• 4.2.1 Net Order方法
• 4.2.2 实验结果和总结
• 4.3 布线启发式函数的改进
• 4.3.1 带有面积约束的布线启发式函数
• 4.3.2 实验结果和总结
• 4.4 本章小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 未来工作展望
• 致谢
• 参考文献
• 作者在读期间研究成果