fpga自动布局布线算法

《fpga自动布局布线算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2FPGA自动布局布线算法位置，或人工干预，拆除某些线网、移动某些逻辑单元，重新布线等)，这样的修改可能要反复多次。1．2研究现状随着微孔和单片高密度集成系统等新硬件技术的应用，自由角度布线、自动布局和3D布局布线等新型软件将会成为电路板设计人员必备的设计工具之一。在早期的电路板设计工具中，布局有专门的布局软件，布线也有专门的布线软件，两者之间没什么联系，随着球栅阵列封装的高密度单芯片、高密度连接器、微孔内建技术以及3D板在印刷电路板设计中的应用，布局和布线己越来越一体化，并成为设计过程的重要组成部分。自动布局和自由角度布线等软件技术己渐渐成为解决这类高度一体化问题的重要方法，利

2、用此类软件能在规定时间范围内设计出可制造的电路板。在目前产品上市时间越来越短的情况下，手动布线极为耗时，不合时宜，因此，现在要求布局布线工具具有自动布线功能以快速响应市场对产品设计提出的要求。自动布局布线工具发展要求布局布线算法性能的可靠性，相对于手动布局布线工具，自动布局布线算法引入了人工智能技术，例如用于布局的模拟退火算法及用于布线阶段的迷宫布线算法。其中，迷宫布线算法是广泛应用于FPGA设计流程中的布线算法【5】，它的基本思想是在连线资源平面上，模拟-YU波从线网的一端扩散到线网的另一端以得到实际的布线方案。VPR(VersatilePlaceandRoute)[61，FP

3、R(FPGAplacementandrouting)，SPLACE／SROUTE等都是现有的一些布局布线工具，本文对自动布局布线算法的研究主要基于VPR布局布线工具，‘因为相对于其他工具，VPR在性能及速度方面更加的成熟，比FPR能够节省87％的轨道，在对高扇出网线的处理上要比SPLACE／SROUTE更高效。在最近几年对布线算法的研究上，大部分的研究集中在对布线资源图数据结构的改进上，将布尔可满足、二叉判定图、斯塔纳(STEINER)树等算法引入自动布线中，力图提高当前算法的速度及性能，有的研究则通过定制FPGA的硬件结构数据库的方法来提高布线速度。1．3论文的组织结构本文主要

4、面向孤岛型的FPGA结构，基于VPR针对当前FPGA的详细布线采取的迭代式迷宫搜索算法进行了研究。本文分别从布线的速度及面积耗费上进行改进，并测出最终的试验数据，结果显示本文采取的方法比已有算法的效果更好。本文的章节安排如下：第二章介绍了与布局布线相关的背景知识，如FPGA、第一章绪论FPGA设计流程和常用的自动布线算法及启发式函数，这是以后讨论布局布线算法的基础，第三章首先介绍了VPR布局布线工具的相关参数和术语，然后重点介绍VPR采用的布局布线算法，第四章是本文的重点，从FPGA布线的速度、面积性能方面对当前自动布线算法进行一些理论及实践上的改进。第五章是本文的工作总结和对未

5、来工作的展望。3一第二章布局布线背景知识本章主要介绍布局布线前的准备知识，作者研究的自动布局布线算法面向的是现场可编程门阵列FPGA(FieldProgrammableGateArray)，所以本章首先介绍了FPGA的内部结构及设计流程，布局布线模块是FPGA设计流程中重要的环节之一，然后重点阐述了当前常用的布线算法及布线算法中的启发式函数。2．1FPGA内部结构及设计流程2．1．1FPGA内部结构现场可编程门阵歹lJ(FPGA)是可编程器件【7】，与传统逻辑电路和门阵列(如PAL、GAL及CPLD器件)相比，FPGA具有不同的结构，FPGA利用小型查找表来实现组合逻辑，每个查找

6、表连接到一个D触发器的输入端，触发器再来驱动其他逻辑电路或驱动I／O模块。FPGA的逻辑是通过向内部静态存储器单元加载编程数据来实现的，存储在存储器单元中的值决定了逻辑单元的逻辑功能以及各模块之间或模块与I／O间的连接方式；并最终决定了FPGA所能实现的功能，FPGA允许无限次的编程。FPGA的一个重要特征是可被编程，逻辑单元中的luts一般被用来执行任意的布尔函数，flip．flops被用来实现连续的电路。每个lut和flip．flop对被作为一个逻辑元素即LE，如果有几组LE通过本地的布线交叉连接如下图所示的那样，其工作效率将会更好，这几组LE被称为逻辑簇，有全局时钟来同步电

7、路。FPGA编程与微处理器编程有很大的区别，微处理器是一个可存储程序的计算机，计算机系统包括CPU和存储指令与数据的独立存储器，FPGA编程交织在FPGA的逻辑结构中，FPGA不取指令，FPGA的编程过程直接实现逻辑功能和互联。一般来说，FPGA有三部分构成：组合逻辑、连线和I＼O引脚。这三个部分共同构成FPGA的体系结构，图2．1给出了孤岛型FPGA的体系结构图。CLB是组合逻辑块，是FPGA中的逻辑器件，由查找表和触发器构成，组合逻辑模块通常可以用来构成一些典型的逻辑门函数，