一种基于线网关键性判别的FPGA总体布线算法

论文摘要

随着千差万别的系统用户提出不同的设计要求,出现了一种新的可以由用户自行定义配置的高容量密度的ASIC——用户现场可编程门阵列器件（FPGA）,FPGA以其高密度、高速率、系列化、标准化、小型化、多功能、低功耗、低成本,设计灵活方便,可无限次反复编程,并可现场模拟调试验证等特点,在国内外得到了飞速发展 当前集成电路产业向深亚微米工艺不断推进,FPGA芯片布线时的面积约束便成为了影响整个芯片性能的最重要的因素之一,尤其是其关键线网布线时的布通率和面积约束是一对矛盾体。本文充分利用FPGA芯片本身具有的固定的规则的布线资源这一特点,提出在对每一个线网布线之前将待布的线网进行关键性分析,再根据关键性大小对关键性相对大的线网进行布线,即NCJ（Net Criticality Judge）算法;此算法有效地在保证芯片性能的同时,提高了布线资源的利用率,同时考虑到深亚微米时布线时延是影响芯片性能的一个重要因素,因此充分利用芯片的中长线布线资源以减少通过编程开关的几率。 本文建立了NCJ算法的布线模型,用C++语言实现了基于NCJ算法的总体布线和SEGA详细布线的FPGA布线器,并与目前经典的基于LocusRout的总体布线算法和SEGA详细布线算法的结果进行比较,结果证明了基于NCJ的布线算法在提高布线资源的利用率方面是非常有效的。 高密度器件的另一个重要问题是相邻线间的串扰影响,论文还对串扰进行了定性分析,提出了改进措施。

论文目录

• 第1章 绪论
• 1.1 课题的背景、意义和目标
• 1.1.1 大规模集成电路设计与EDA工具
• 1.1.2 FPGA新技术使EDA工具面临的挑战
• 1.2 课题完成的工作
• 1.3 论文的组织结构
• 第2章 FPGA结构FPGA布线的影响
• 2.1 对称型FPGA
• 2.2 行排列FPGA
• 2.3 小结
• 第3章 对称型FPGA结构布线算法介绍
• 3.1 LocusRoute总体布线算法介绍
• 3.1.1 LocusRoute布线方法
• 3.1.2 LocusRoute算法的特点
• 3.1.3 LocusRoute算法实现
• 3.2 详细布线算法介绍
• 3.2.1 考虑开关模块容量的布线算法
• 3.2.2 考虑不同的布线段选取方案在FPGA布线中的意义
• 3.3 SEGA算法
• 3.3.1 SEGA算法模型
• 3.3.2 SEGA算法思想
• 3.3.2.1 列举布线方案
• 3.3.2.2 连接实现
• 3.4 小结
• 第4章 线网关键性判别算法
• 4.1 线网关键性判别算法的意义
• 4.2 XILINX XC4000布线通道模型
• 4.2.1 CLB内部结构
• 4.2.2 布线资源
• 4.2.3 IO单元
• 4.3 相关数学理论介绍
• 4.3.1 马尔可夫过程
• 4.3.2 状态转移概率
• 4.3.3 曼哈顿距离
• 4.4 NCJ算法
• 4.4.1 两端线网对布线资源的占有情况分析
• 4.4.2 两端线网布线的通道密度分析
• 4.4.3 多个线网关键性大小判断
• 4.5 小结
• 第5章 FPGA中不同长度的布线资源在布线中的作用
• 5.1 双长线与单长线在布线时的优势对比
• 5.2 FPGA中合理利用单长线与双长线的算法
• 5.2.1 统计布线资源中双长线的使用情况
• 5.2.2 两端线网的双长线优选布线方案
• 5.3 小结
• 第6章 算法实现及结果分析
• 6.1 布线算法模型及参数说明
• 6.2 基于NCJ的布线算法流程
• 6.3 算法中使用的相关函数说明
• 6.3.1 布线输入
• 6.3.2 多端线网拆分为两端线网
• 6.3.3 两端线网的关键性分析
• 6.3.4 生成两端线网的布线通道图
• 6.3.5 两端线网布线路径选择
• 6.3.5.1 总体布线
• 6.3.5.2 详细布线
• 6.3.6 布线资源合并
• 6.4 实验结果
• 6.5 小结
• 第7章 考虑串扰影响因素对布线算法的优化
• 7.1 FPGA串扰形成的原因
• 7.2 几种克服FPGA串扰问题的方法介绍
• 7.2.1 增大线间距离
• 7.2.2 屏蔽技术
• 7.2.3 改变缓冲器的尺寸
• 7.2.4 改变开关模块的连接形式
• 7.3 布线算法中关于减小串扰所采取的措施
• 结论
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文及科研成果
• 附录1 一个与门布局网表文件
• 附录2 五个实验的线网相关参数
• 附录3 8个多端线网的布线输出