VPR: A New Packing， Placement and Routing Tool for
FPGA Research
Vaughn Betz and Jonathan Rose
Department of Electrical and Computer Engineering， University of Toronto
Toronto， ON， Canada M5S 3G4 {vaughn， jayar}@eecg.toronto.edu
Abstract
We describe the capabilities of and algorithms used in a new FPGA CAD tool，Versatile Place and Route (VPR). In terms of minimizing routing area， VPR outperforms all published FPGA place and route tools to which we can compare.Although the algorithms used are based on previously known approaches， we present several enhancements that improve run-time and quality. We present placement and routing results on a new set of large circuits to allow future benchmark comparisons of FPGA place and route tools on circuit sizes more typical of todayrsquo;s industrial designs.VPR is capable of targeting a broad range of FPGA architectures， and the source code is publicly available. It and the associated netlist translation /clustering tool VPACK have already been used in a number of research projects worldwide， and should be useful in many areas of FPGA architecture research.
1 Introduction
In FPGA research， one must typically evaluate the utility of new architectural features experimentally. That is， benchmark circuits are technology mapped， placed and routed onto the FPGA architectures of interest， and measures of the architecturersquo;s quality， such as speed or area， can then readily be extracted. Accordingly， there is considerable need for flexible CAD tools that can target a wide variety of FPGA architectures efficiently， and hence allow fair comparisons of the architectures.This paper describes the Versatile Place and Route (VPR) tool， which has been designed to be flexible enough to allow comparison of many different FPGA architectures.VPR can perform placement and either global routing or combined global anddetailed routing. It is publicly available from http://www.eecg.toronto.edu/~jayar/software.html.
In order to make meaningful FPGA architecture comparisons， it is essential that the CAD tools used to map circuits into each architecture are of high quality. The routing phase of VPR outperforms all previously published FPGA routers for which standard benchmarks results are available， and that the combination of VPRrsquo;s placer and router outperforms all published combinations of FPGA placement and routing tools.2 The organization of this paper is as follows. In Section 2 we describe some of the features of VPR and the range of FPGA architectures with which it may be used. In Sections 3 and 4 we describe the placement and routing algorithms. In Section 5， we compare the number of tracks required by VPR to successfully route circuits with that required by other published tools. In Section 6 we conclude and outline some future enhancements which will be made to VPR.
2 Overview of VPR
Figure 1 outlines the VPR CAD flow. The inputs to VPR consist of a technologymapped netlist and a text file describing the FPGA architecture. VPR can place the circuit， or a pre-existing placement can be read in. VPR can then perform either a global route or a combined global/detailed route of the placement. VPRrsquo;s output consists of the placement and routing， as well as statistics useful in assessing the utility of an FPGA architecture， such as routed wirelength， track count， and maximum net length.Some of the architectural parameters that can be specified in the architecture description file are:
bull; the number of logic block inputs and outputs，
bull; the side(s) of the logic block from which each input and output is accessible，
bull; the logical equivalence between various input and output pins (e.g. all LUT
inputs are functionally equivalent)，
bull; the number of I/O pads that fit into one row or one column of the FPGA， and
bull; the dimensions of the logic block array (e.g. 23 x 30 logic blocks).
In addition， if global routing is to be performed， one can also specify:
bull; the relative widths of horizontal and vertical channels， and
bull; the relative widths of the channels in different regions of the FPGA.
Finally， if combined global and detailed routing is to be performed， one also specifies:
bull; the switch block [1] architecture (i.e. how the routing tracks are interconnected)，
bull; the number of tracks to which each logic block input pin connects (Fc [1])，
bull; the Fc value for logic block outputs， and
bull; the Fc value for I/O pads.
The current architecture description format does not allow segments that span more than one logic block to be included in the routing architecture， but we are presently adding this feature. Adding new routing architecture features to VPR is relatively easy， since VPR uses the architecture description to create a routing resource graph.Every routing track and every pin in the architecture becomes a node in this graph， and the graph edges represent the allowable connections. The router， graphics visualiza-tion and statistics computation routines all work only with this routing resource graph，so adding new routing architecture features only involves changing the subroutines that build this graph.Although VPR was initially developed for island-style FPGAs [2， 3]， it can also be used with row-based FPGAs [4]. VPR is not currently capable of targeting hierarchical FPGAs [5]， although adding an appropriate placement cost function and the required routing resource graph building routines would allow it to target them.Finally， VPRrsquo;s built-in graphics allow interactive visualization of the placement，the routing， the available routing resources and the possible ways of interconnecting the routing resources.
2.1 The VPACK Logic Block Packer / Netlist Translator
VPACK
VPR：一种新的包装，布局和布线工具的FPGA研究
沃恩贝茨和乔纳森罗斯
电气系和计算机系，多伦多大学
多伦多，加拿大M5S 3G4 {vaughn， jayar}@eecg.toronto.edu
摘 要
我们描述了一个基于FPGA新的功能和CAD工具使用的算法，各种途径和方（VPR）。在减少路由面积计算方面，VPR优于所有的FPGA布局布线工具，我们可以比较。虽然常用的算法是基于已知的方法，是我们目前而言改善运行时间和质量的几个有效方法。我们目前的版图和路由上的大型电路的一套新的结果，让未来的基准电路尺寸上的设计方法更多，用于今天的典型的FPGA布局布线工具工业品外观设计。VPR是针对一个范围广泛的FPGA架构的能力，并且源代码是公开的。它和相关的网表翻译/群集工具VPACK已经被用在世界各地的一些研究项目，并且是有用的FPGA体系结构的研究。
1 简介
在FPGA的研究中，人们通常必须评估新结构特色的实用工具而做评估实验。也就是说评估基准电路技术映射，放置和FPGA的布线结构上的关系和措施的架构质量，如运算速度或区域，然后可以很容易地提取出来。因此，有相当大的对于灵活CAD工具的需求，这样才可以针对各种架构的FPGA做高效的设计，从而便于比较均匀的设计架构。本文介绍了通用的地点和路线（VPR）工具，设计很灵活，足够让许多FPGA架构的比较VPR可以执行的位置，要么全球路由或合并后的全球详细路由。这是公开的来自http://www.eecg.toronto.edu/~jayar/software.html。
为了使FPGA体系结构的比较有意义，它是至关重要的CAD工具用于将每个电路架构，以地图的高品质展现。路由相优于所有的VPR在查看FPGA的路由器方面，任何标准基准测试的结果都可用，并且指出VPR的砂矿和路由器的组合胜过所有出版的FPGA布局和布线工具。本文结构如下：
在第2节我们描述了一些VPR功能的FPGA架构和范围与它可能被使用的地方。在第3和第4节，我们描述了布局布线法。在第5节讲述了比较有必要的VPR曲目数量和该电路成功的布线所要求的其他已发表的工具。在第6节得出了我们的结论，并提出一些VPR将来的升级。
2 概述VPR
图1概括了VPR 的CAD流程。VPR投入到由一个technologymapped 网表和一个文本文件描述了的FPGA架构中。VPR可以放置电路，或一个预先存在的位置，可以读入VPR可以执行或者是全局的路线或合并后的全球/详细的安置途径。VPR的输出由布局、布线和统计组成，评估一项有用的工具FPGA架构，如路由线长，跟踪计数最大净长度。给出一些可指定的建筑结构参数描述文件：
bull;逻辑块输入和输出的数量，
bull;对每个逻辑块的输入和输出端访问（S）之和
bull;逻辑等价性不同的输入和输出引脚（例如，所有对照表输入功能当量），
bull;对I /成一行或一列的FPGA适合O引脚数，
bull;逻辑块阵列的尺寸（如23 times; 30的逻辑块）。此外，如果全球路由要执行，你也可以指定：
bull;横向和纵向通道的相对宽度之和
bull;在不同区域的FPGA的渠道相对宽度。最后，如果合并后的全球和详细的路由被执行，一个也会进行求值：
bull;开关块[1]架构（即为何路由曲目是相互关联的），
bull;曲目号码，每个逻辑块的输入引脚连接（ [1]），
bull;为逻辑块输出FC值，
bull;对I / O口FC值。
当前的体系结构描述格式不允许跨越多个领域和多个逻辑块和被列入路由体系结构，但我们目前加入此功能。添加新的路由架构的功能VPR相对容易，因为VPR使用体系结构描述来创建路由资源图。每个路由跟踪和建设中的每一个脚成为在这个图中的节点，图边表示为允许的连接。路由器，图形可视化和统计计算程序都与此路由资源图的工作相关，所以添加新的路由架构功能仅涉及更改的子程序来建设这个图。虽然VPR最初是岛式FPGA的开发[2，3]，它也可以和以行为为基础的FPGA应用[4]。 VPR目前没有能力为目标的层次FPGA的[5]，显然增加一个适当的位置和成本函数设计所需的布线资源图形程序将使其能够解决这些问题。最后，VPR的内置图形允许交互式可视化的布局，路由可用资源和互连的可能途径路由资源。
VPACK逻辑块包装程序/网络表翻译
VPACK读取一个已经技术映射电路网表格式blif 到LUT和触发器，包装成所需的FPGA逻辑LUT和触发器块，并输出在VPR的网表。 VPACK可以针对逻辑块组成一个LUT，如图2所示，因为这是一种常见的FPGA逻辑元件。 VPACK也针对逻辑块包含几个有用的LUT和几个拖动程序，有或没有共享LUT的输入[6]。这些“clusterbased”逻辑块类似于最近由Altera FPGA开发的工具类型。
3布局算法
VPR采用模拟退火算法[7]。我们已经尝试与几个不同的成本函数联系，发现我们称之为线性挤塞的成本函数提供了一个合理的计算时间，最好的结果[8]。此成本函数的函数形式就是对所有的求和电路中的网进行计算。对于每一个网，北方新宇和bby指出在其边界框的水平和垂直跨度分别为Q（n）的因数补偿。边界线长度模型中的实际低估所需的布线，就可以看成超过三个终端网，作为建议[10]。它的价值取决于净N两端号码; Q是对总体1有3个或更少的终端，并慢慢增加了50台网逻辑与上2.79。贾夫常数x（n）、Yuml;（n）为平均信道容量（在首部）在X和Y方向，分别比较全净边框和成本函数的余量，需要更多的调配路由的领域，FPGA具有窄渠道。本文中的所有结果的得到，是利用FPGA中的所有通道都有相同的原则。在这种情况下，贾夫是一个常数，函数的线性阻塞耗费降低到一个包围盒的成本函数。一个良好的退火算法的必要条件是时间表取得一个合理的高品质的解决方案与模拟退火的计算时间相关联。我们已经开发出一种新的退火附表，导致非常高品质的展示位置，并在其中给出退火参数的自动调节功能，不同的成本和电路尺寸。我们计算在初始温度相同的方式为[11]。让Nblocks是总数逻辑块加的I / O口电路中的数量。我们首先创建一个随机安置的电路。接下来，我们执行Nblocks移动（成对掉期）的逻辑块或I / O口，并计算出不同的成本，这些Nblocks标准偏差配置。初始温度设定为20倍标准差，确保最初几乎所有的行动是在退火算法范围内被系统接受。正如在[12]，默认号码的行为在每个温度都有评价。这个默认的数字可以在命令行被取代，从而让不同的CPU时间和填筑质量权衡。减少温度每秒移动数的10倍，例如，加快安置到10倍，并降低了大约只有10％的最终填筑质量。当温度是如此之高，几乎任何举动都可以被接受时，我们基本上从一个位置随机移动到另一个位置所改善获得的成本都是小成本。相反，如果动作是很少被接受（因温度当前正处于低位，安置相当高的品质），也有不少改善成本。有了这个动机，我们提出了一个新的温度更新附表，在温度增加的时间花费在一个重要的小区域上，但不是全部动作都被接受。如表1：
最后，它表明在[12，13]，这是可取的Raccept保证作为近似0.44的量有可能被取值。为此，就需要利用Raccept值来控制这个范围限制器。块是小于或等于交汇处的值，Dlimit单位除了在X和Y方向尝试。一个小的Dlimit增加值由Raccept确保这仅仅是块进行交换考虑。而这些“本地交换“往往导致安置成本相对较小的变化，越来越多被接受的可能性增加。最初，Dlimit设置为整个芯片。每当温度降低，Dlimit整个芯片的尺寸为这个结果退火的第一部分，逐渐萎缩退火过程中的中间阶段，并正在为退火低温第1部分最后设计余量，当T退火终止“0.005*成本/ Nnets。该运动的逻辑块总是至少影响到一个网。当温度高于平均净成本的一个单位时，它是不可能接受任何成本增加的调配结果的，所以我们终止了退火。
4路由算法
VPR的路由器是基于试探谈判的拥塞算法[14，8]。 基本上该算法由最初各条线路的最短路径找到网， 无论任何接线段或逻辑块管脚，都可能会导致过度使用。路由器的迭代过程包含顺序抓取行动和重新路由（由最低成本路径中找到）中的每个电路网。对使用路由资源成本的函数，其对资源的任何过度使用都会让当前路由发生事先迭代。通过逐渐增加的多余认购路由资源成本，该算法势力替代路线网，以避免使用超额认购资源，只剩下网最需要一个给定的资源。对于本文的实验结果，我们设置路由器的最大数量迭代为45，如果电路中路由没有成功，一定数目的目录中45迭代就被假定为不可路由通道的宽度。为了避免过于迂回路线以节省CPU时间，我们让一个去净路由最外的3个通道的净终端边界框。一个重要的执行细节值得一提。无论是原探路者算法和Vpr路由器使用的Dijkstra算法（即一个迷宫路由器[15]），以每个网络连接和AK用线网为依据，路由器调用通道的k - 1次执行所有需要的连接。在第一次调用迷宫路由波从净源扩大，直到它到达任何的K – 1值之后。路径从源到接收器作为现在这个网的路由的第一部分。波前的迷宫路由被清空，新波前扩展是从整个网络布线开始发出的。之后的K - 1路由器的迷宫调用净终端将所有k值连接。不幸的是，这种方法需要高扇出网络相当多的CPU时间。高扇出网络通常跨越大部分或所有的FPGA。因此，后者调用迷宫路由器的路由部分作为净源会非常大，它将需要相当长的时间以扩大迷宫路由器波前部分到下一个接收器。幸好，有一个更有效的方法。当达到净水槽值时，加入所有路由资源分部需要连接水槽和目前的局部路由成本为0的波前（即扩展列表）。当前不要空迷宫路由波前，只要保证继续扩大正常。由于增加新的路径路由的部分有一个零成本，由于这项新路径通常相当小迷宫路由器将首先扩大它范围，也需要相对较少的时间来添加此新波，如果整个波前扩展了能实现那么下一个接收器将达到的速度远远超过现在。图3说明了差异图形。
5实验结果
各种FPGA在本节中使用的参数，总是选择与先前参数有明显对比的那些参数。所得结果在本节获得了逻辑的4输入LUT加上一个触发器组成的块，如图所示在图2。时钟网和时序电路没有递交，因为它通常是路由通过专用FPGA的商业网络中的路由。每个LUT的输入出现在一个逻辑块的一面，而逻辑块输出一般访问底部和右侧，如图4。每个逻辑块的输入或输出连接任何相邻通道（s）（即Fc的=宽）。每根电线段和其他布线连接到三段，而在通道交叉口（即值= 3）和开关箱拓扑是“不相交” 这是因为在0磁道接线段只连接在0磁道的其他布线段。
5.1实验结果与输入引脚Doglegs
以往大多数FPGA布线结果认为“输入引脚doglegs”是可能。如果输入引脚之间的音轨和它连接接线盒的Fc通过独立的SRAM位控制晶体所组成，为了验证两条轨道上的这些开关通过电气连接的可能性。我们将把这个作为一个输入管脚doglegs。作为商业化的FPGA，实现从一个输入引脚接线盒到多路通道，只有一个轨道可以连接到输入引脚，使用多路复用器而不是独立通过在FPGA中的晶体管布局来保存相当的面积。另外，通常有一个缓冲轨道之间的连接块和它连接多路复用这样做的目的是为了提高速度，同时这也意味着缓冲输入引脚doglegs不能被使用。因此，如果在未来FPGA的路由器测试时没有输入引脚doglegs那么我们必须让输入引脚doglegs和过去的结果公平的比较这样是最好的。在本节中我们比较了所需的最低数目，每一条成功的路径和CAD工具的路由设置。所有的基准circuits.1在表2给出结果，得到了路由Altor [16]，制作了一个基于位置的工具min。列出三两步（全球和详细）路由与其它路由器进行合并后的全球和详细的路由。
VPR要求比第二，第三最佳路由器降低10％的资源数目，表3列出了音轨需要执行这些标准时数新的CAD工具，同时允许地方和路线的电路的连接。列出所有电路逻辑快的消息清单。 VPR使用少于13％资源数目的同时，它将执行合并后的全球和详细的路由，世嘉比用于执行详细路由对AA VPR生成全版图走线。执行安置和全局路由，在试图改善绕线同时需要超过87％以上VPR总资源数目。最后，让VPR配置电路而不是强迫它使用Altor内存来减少资源数目的40％，这表明VPR的模拟退火算法单元远较Altor最小单元更好。
5.2不输入引脚的Doglegs实验
比较了VPR与SPLACE / SROUTE工具，不允许输入引脚doglegs的性能。当这两个工具都只能使用路线一，比起SROUTE轨道Altor产生的安置需求VPR减少13％，。当然这些工具都支持允许布局和布线的电路，对于SPLACE / SROUTE组合VPR还需要少29％资源数目。无论是基于VPR和SPLACE只要是使用模拟退火算法，我们相信VPR单元在一方面优于SPLACE是因为它处理高扇出网络更有效率，让更多的动作进行评估，另一方面是因为它更有效的退火时间表给定的时间。
朗显示对应的拉丁字符的拼音
5.3实验结果
在第5.1和5.2的54至358的逻辑基准块范围内使用面积计算显然太小，因为这是特殊的FPGA。因此在本节中我们目前的实验结果，20个最大的MCNC基准电路[27]，它的大小范围从1047到8383逻辑块。我们使用Flowmap [28]以技术图每4个LUT和拖动块并为VPACK tocombine拖动块，进入我们的基本逻辑电路块LUT。I / O引脚数每行或列适合设置为2，符合目前的商业化FPGA。每个电路被放置在最小的正方形
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
