论文部分内容阅读
FPGA是目前广泛使用的一种可编程器件,随着半导体工艺的迅速发展,FPGA芯片的结构越来越复杂、规模越来越大,使得用户在应用FPGA设计电路时对计算机辅助设计工具的依赖越来越大,因此需要不断对相应的计算机辅助设计流程、算法及相关工具进行改进。当前FPGA结构不断改进及规模不断扩大,使得FPGA计算机辅助设计面临许多新的挑战,本文着重研究与FPGA结构及规模紧密相关的FPGA设计后端算法,分析当前流行后端算法的研究状况,概况其优缺点并针对当前各个后端算法面临的困难,提出相应的改进算法。随着可编程逻辑块结构越来越复杂,FPGA装箱算法中用户电路包含的可配置子电路种类越来越多,如何开发出适应不同的、复杂的可编程逻辑块结构的装箱算法成为当前的难点。针对上述困难本文提出了一种基于CSP图匹配的装箱算法,该算法能根据描述文件匹配出用户电路中符合条件的可配置子电路,并能根据描述文件中的相应指令对用户电路进行改写,实现对用户电路的装箱。实验表明该算法能灵活对复杂可编程逻辑块结构进行装箱,且通过指定相应电路优化规则,用户电路的逻辑块数目减少了1.4%,布局布线后关键路径延迟减少了6.1%传统的FPGA布局算法在处理不同粒度逻辑块布局时尤显不足,针对该情况本文提出了一种基于CSP问题的布局算法,该算法将布局问题映射到CSP问题进行求解,利用CSP问题的求解方法能方便处理不同粒度逻辑块的布局问题,通过添加开放式的成本函数及时序分析等手段,该算法能够获得质量较高的初始布局,之后利用低温退火布局算法优化布局结果,得到与VPR布局算法质量相当的布局结果,且降低了原有退火算法的运行时间。FPGA布线随着FPGA规模的增大其运行时间在FPGA设计中占越来越大的比重,因此提高布线速度显得越来越重要。本文提出了一种基于紧凑布线资源图的布线算法,通过在紧凑布线资源图上进行路径搜索,算法有效降低了布线的搜索空间,从而大大提高了布线的运行速度。实验表明,对于XC4000系列芯片,该算法的执行速度比VPR布线算法平均提高了40.39%。