反熔丝FPGA布局布线算法研究及CAD软件开发

摘要

现场可编程门阵列（Field Programmable Gate Array, FPGA）是一种包含大量可配置的逻辑资源和布线资源、用户可编程的逻辑器件。使用FPGA能够大大缩短ASIC电路的设计周期，同时也降低了设计成本和设计风险。反熔丝FPGA具有抗辐射能力强、耐高低温、功耗低、速度快、安全性高等显著优点，因此在国防军事、卫星通信和航空航天领域存在广泛的应用。然而我国对于反熔丝FPGA的研究处于刚刚起步的阶段，尤其是针对反熔丝FPGA CAD软件的研究更是有待于突破与解决。本文以此为背景，对反熔丝FPGA的相关算法及CAD软件开发做了以下几个方面的工作。
　　（1）提出了一种线长驱动的布局算法。不同于经典的岛型FPGA，反熔丝FPGA的布线资源数目在水平方向和垂直方向存在较大差异，水平布线资源的数目远远多于垂直布线资源的数目。针对上述反熔丝FPGA的结构特点，本文对于VPR中的模拟退火布局算法进行了改进，在线性拥挤成本函数中引入了新的成本因子，从而有效地提高了反熔丝FPGA中垂直布线资源的利用率。实验结果表明，与VPR布局算法相比，该方法不仅优化了线网总长度，使得线网总长度平均减少了12％，同时还减少了编程的水平反熔丝数目。
　　（2）提出了一种提高反熔丝FPGA容错能力的新方法。该方法能够针对反熔丝FPGA中特有的故障类型——反熔丝单元的故障进行容错处理，其基本思想是在FPGA布线时预留下更多的对称互连线资源，当发生反熔丝故障时利用对称互连线资源来形成新的信号通路，从而绕开故障的反熔丝单元。该方法尽管在布线时引入了额外的信号延时，但能够保证容错处理后的电路性能几乎不变。实验结果表明，当FPGA布线资源固定时，该方法在布线阶段有效增加了对称线段的预留量，预留量平均可增加30.4%，最高可达100%；当预留量达到100%时，FPGA的单个反熔丝故障都可以通过容错消除该故障。
　　（3）提出了基于伪布尔可满足性的多层次布线算法。该算法将反熔丝FPGA的通道布线问题转换为伪布尔优化问题，并利用先进的伪布尔求解器进行求解。该算法不仅能够得到较好的布线结果，还可以准确判断电路的可布通性。此外，为了提高算法的性能以及减少运行时间，本文还提出了多层次的布线方法，该方法每次仅对部分线网进行布线并且在布线失败的情况下回溯至上一层次。实验结果表明该布线算法能够在合理的时间范围内提供高质量的布线结果，并且具有最佳的收敛率。
　　（4）设计了一套完整的反熔丝FPGA CAD系统。该CAD系统通过整合成熟的商业软件以及学术界的开源软件，并自主设计了部分软件以完成FPGA的整个设计流程。在工艺映射工具E2fmt中建立了针对ACT2系列反熔丝FPGA的通用库和目标库，并且允许用户通过更新配置文件来生成新的工艺映射库。修改VPR中的布局布线算法，在其中采用了线长驱动的布局算法和基于伪布尔可满足性的多层次布线算法，使得VPR能够支持反熔丝FPGA的布局布线。此外，在位流生成工具Streamline中采用新的位流生成算法，该算法通过将FPGA划分成若干区域来确定每一个反熔丝单元的具体坐标值。用户可以方便地在图形用户界面下完成反熔丝FPGA的设计流程。使用该CAD系统对反熔丝FPGA芯片A1240A进行了编程下载，测试结果验证了CAD系统的有效性和实用性。
　　（5）提出了一种新型的基于栅氧反熔丝的位单元电路。由于栅氧反熔丝存在导通电阻值较大并且分布离散的特点，因此无法直接应用于反熔丝FPGA中。新型位单元电路克服了上述栅氧反熔丝的缺点，它是由两个反熔丝单元、一个选择晶体管和一个高压隔离晶体管所组成，能够输出十分稳定的逻辑电平以控制反熔丝FPGA中各个节点的状态。利用该位单元电路即可将栅氧反熔丝成功地应用于反熔丝FPGA中，设计了反熔丝FPGA电路并采用HHNEC0.18μm CMOS工艺完成了版图设计，样片的测试结果验证了新型位单元电路的可行性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景和意义

1.2 FPGA设计技术

1.3 国内外研究现状

1.4 本文的主要工作和创新

1.5 本论文的内容安排

第二章 反熔丝FPGA基本结构介绍

2.1 反熔丝的分类

2.2 反熔丝的编程方法

2.3 反熔丝FPGA的基本结构

2.4 本章小结

第三章 反熔丝FPGA的布局算法和容错方法研究

3.1 反熔丝FPGA布局算法研究

3.2 反熔丝FPGA容错方法研究

3.3 本章小结

第四章 基于伪布尔可满足性的多层次布线算法研究

4.1 通道布线问题和通道布线模型

4.2 常用的布线算法

4.3 伪布尔可满足性原理

4.4 基于伪布尔可满足性的多层次布线算法

4.5 实验结果及分析

4.6 本章小结

第五章 反熔丝FPGA CAD系统设计研究

5.1 反熔丝FPGA CAD系统设计

5.2 反熔丝FPGA CAD系统验证

5.3 反熔丝FPGA的编程下载

5.4 本章小结

第六章 基于栅氧反熔丝的位单元电路设计研究

6.1 栅氧反熔丝

6.2 已有的位单元电路

6.3 新型的位单元电路

6.4 新型位单元电路在反熔丝FPGA中的应用

6.5 本章小结

第七章 结论

致谢

参考文献

攻读博士学位期间取得的成果