【正文】 10 外文原文 VPR: A New Packing， Placement and Routing Tool for FPGA Research1 Vaughn Betz and Jonathan Rose Department of Electrical and Computer Engineering， University of Toronto Toronto， ON， Canada M5S 3G4 {vaughn， 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 the algorithms used are based on previously known approaches， we present several enhancements that improve runtime and quality. We present placement and routing results on a new set of large circuits to allow future benchmark parisons of FPGA place and route tools on circuit sizes more typical of today’s industrial is capable of targeting a broad range of FPGA architectures， and the source code is publicly available. It and the associated list 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 architecture’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 parisons of the paper describes the Versatile Place and Route (VPR) tool， which has been designed to be flexible enough to allow parison of many different FPGA can perform placement and either global routing or bined global anddetailed routing. It is publicly available from 11 In order to make meaningful FPGA architecture parisons， 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 bination of VPR’s placer and router outperforms all published binations of FPGA placement and routing 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 pare 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 list and a text file describing the FPGA architecture. VPR can place the circuit， or a preexisting placement can be read in. VPR can then perform either a global route or a bined global/detailed route of the placement. VPR’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 of the architectural parameters that can be specified in the architecture description file are: ? the number of logic block inputs and outputs， ? the side(s) of the logic block from which each input and output is accessible， ? the logical equivalence between various input and output pins (. all LUT inputs are functionally equivalent)， ? the number of I/O pads that fit into one row or one column of the FPGA， and ? the dimensions of the logic block array (. 23 x 30 logic blocks). In addition， if global routing is to be performed， one can also specify: ? the relative widths of horizontal and vertical channels， and ? the relative widths of the channels in different regions of the FPGA. Finally， if bined global and detailed routing is to be performed， one also specifies: ? the switch block [1] architecture (. how the routing tracks are interconnected)， ? the number of tracks to which each logic block input pin connects (Fc [1])， ? the Fc value for logic block outputs， and ? the Fc value for I/O pads. The current architecture description format does not allow segments that span more 12 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 routing track and every pin in the architecture bees a node in this graph， and the graph edges represent the allowable connections. The router， graphics visualization and statistics putation routines all work only with this routing resource graph， so adding new routing architecture features only involves changing the subroutines that build this VPR was initially developed for islandstyle FPGAs [2， 3]， it can also be used with rowbased 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 ， VPR’s builtin graphics allow interactive visualization of the placement， the routing， the available routing resources and the possible ways of interconnecting the routing resources. The VPACK Logic Block Packer / Netlist Translator VPACK reads in a blif format list of a circuit that has been technologymapped to LUTs and flipflops， packs the LUTs and flip flops into the desired FPGA logic block， and outputs a list in VPR’s list format. VPACK can target a logic block consisting of one 13 LUT and one FF， as shown in Figure 2， a