基于SAT的FPGA布线技术研究

摘要

FPGA作为一种优秀的大规模可编程逻辑器件,在电子设计以及电子产品等方面具有广泛的应用.随着FPGA的不断发展,其中布局布线资源的利用方式是整个系统性能的决定性因素.通过对布局布线算法的改进,将会提高系统的整体性能.本文主要研究利用布尔可满足问题来解决FPGA详细布线问题.采用这种算法,设计实现V-SAT系统,完成把详细布线问题转化为布尔可满足问题,同时集成了两个开源系统,VPR布局布线工具和zChaff可满足求解器.并利用国际通用的MCNC标准电路,分别对VPR和V-SAT进行性能测试.实验表明:在两种主要要素的测试上,V-SAT在整体的性能上优于VPR.V-SAT系统设计中,采用的是布尔可满足算法,通过VPR生成全局布线文件,利用zChaff进行可满足性问题求解.V-SAT系统实现中,主要包括四个功能模块:文件分离器、最少通道求解器、CNF生成器和zChaff格式生成器.通过上述功能模块,完成了两个主要目标:通过左边算法求出了最小通道值、将详细布线问题转换为一个布尔可满足问题.V-SAT系统实现后,利用MCNC电路进行测试,统计系统内部各个部分的耗时,分析出系统的瓶颈所在.提出了库方法,并将其应用于V-SAT系统,优化了系统的存储方式,并缩短了查询时间,提高系统的可重用性.并通过实验表明,系统的整体性能得到很大的提高,表现出更稳定的性能.

目录

文摘

英文文摘

致谢

1 综述

1.1 引言

1.2 课题研究意义

1.2.1 理论意义

1.2.2 应用意义

1.3 国内外研究现状

1.4 论文主要工作及内容安排

2 FPGA基本结构和布线算法

2.1 FPGA基本结构

2.2 布线

2.2.1 布线定义

2.2.2 布线算法

3 VPR系统和zChaff系统的分析与研究

3.1 VPR软件框架

3.1.1 VPR工作流程

3.1.2 VPR布局布线算法分析

3.1.3 VPR安装使用

3.2 zChaff求解器

3.2.1 zChaff求解器架构

3.2.2 zChaff安装使用

4 基于布尔可满足的布线算法研究与分析

4.1 SAT问题

4.2 布尔可满足布线模型

4.3 布尔可满足布线方程转化为CNF

5 基于SAT的FPGA布线系统(V-SAT)实现

5.1 V-SAT系统总体设计框架

5.2 全局布线文件生成

5.3 CNF求解器

5.3.1 文件分离器设计

5.3.2 最少通道求解器设计

5.3.3 CNF生成器设计

5.3.4 zChaff格式生成器设计

6 标准Benchmark电路测试结果及分析

6.1 测试环境和MCNC标准电路

6.2 VPR试验结果

6.3 V-SAT试验结果

6.4 试验结果及分析

7 V-SAT系统改进及优化

7.1 V-SAT系统瓶颈分析

7.2 库方法

7.2.1 库定义

7.2.2 V-SAT系统中库方法的应用

7.3 改进结果及分析

8 总结及展望

8.1 工作总结

8.2 工作展望

参考文献

作者简历

学位论文数据集