【正文】 routing found thus far. After k1 invocations of the maze router all k terminals of the will be connected. Unfortunately， this approach requires considerable CPU time for highfanout s usually span most or all of the FPGA. Therefore， in the latter invocations of the maze router the partial routing used as the source will be very large， and it will take a long time to expand the maze router 17 wavefront out to the next there is a more efficient method. When a sink is reached， add all the routing resource segments required to connect the sink and the current partial routing to the wavefront (. the expansion list) with a cost of 0. Do not empty the current maze routing wavefront。 this buffer also means that input pin doglegs can not be used. Therefore， while we allow input pin doglegs in this section in order to make a fair parison with past results， it would be best if in the future FPGA routers were tested without input pin doglegs. In this section we pare the minimum number of tracks per channel required for a successful routing by various CAD tools on a set of 9 benchmark All the results in Table 2 are obtained by routing a placement produced by Altor [16]， a mincut based placement tool. Three of the columns consist of twostep (global then detailed) routing， while the other routers perform bined global and detailed requires 10% fewer tracks than the second best router， and the third best router consists of VPR’s global route phase plus SEGA for detailed routing. Table 3 lists the number of tracks required to implement these benchmarks when new CAD tools are allowed to both place and route the circuits. The size column lists the number of logic blocks in each circuit. VPR uses 13% fewer tracks when it performs bined global and detailed routing than it does when SEGA is used to perform detailed routing on a a VPRgenerated global route. FPR， which performs placement and global routing simultaneously in an attempt to improve routability，requires 87% more total tracks than VPR. Finally， allowing VPR to place the circuits 19 instead of forcing it to use the Altor placements reduces the number of tracks VPR requires to route them by 40%， indicating that VPR’s simulated annealing based placer is considerably better than the Altor mincut placer. Experimental Results Without Input Pin Doglegs Table 4 pares the performance of VPR with that of the SPLACE/SROUTE toolset，which does not allow input pin doglegs. When both tools are only allowed to route an Altorgenerated placement VPR requires 13% fewer tracks than SROUTE. When the tools are allowed to both place and route the circuits， VPR requires 29% fewer tracks than the SPLACE/SROUTE bination. Both VPR and SPLACE are based on simulated annealing. We believe the VPR placer outperforms SPLACE partially because it handles highfanout s more efficiently， allowing more moves to be evaluated in a given time， and partially because of its more efficient annealing schedule. Experimental Results on Large Circuits The benchmarks used in Sections and range in size from 54 to 358 logic blocks， and accordingly are too small to be very representative of today’s ， in this section we present experimental results for the 20 largest MCNC benchmark circuits [27]， which range in size from 1047 to 8383 logic blocks. We use Flowmap [28] to technology map each circuit to 4LUTs and flip flops， and VPACK tobine flip flops and LUTs into our basic logic block. The number of I/O pads that fit per row or column is set to 2， in line with current mercial FPGAs. Each circuit is placed and routed in the smallest square FPGA which can contain it. Input pin doglegs are not allowed. Note that three of the benchmarks， bigkey， des， and dsip， are padlimited in the FPGA architecture 5 pares the number of tracks required to place and pletely route circuits with VPR with the number required to place and globally route the circuits with VPR and then perform detailed routing with SEGA [23]. Table 5 also gives the size of each circuit， in terms of the number of logic blocks. The entries in the SEGA column with a 179。 T Inc.， ORCA Datasheet， 1994. [4] Actel Inc.， FPGA Data Book， 1994. [5] Altera Inc.， Data Book， 1996. [6] V. Betz and J. Rose， “ClusterBased Logic Blocks for FPGAs: AreaEfficiency vs. Input Sharing and Size， ” CICC， 1997， pp. 551 554. [7] S. Kirkpatrick， C. D. Gelatt， Jr.， and M. P. Vecchi， “Optimization by Simulated Annealing， ” Science， May 13， 1983， pp. 671 680. [8] V. Betz and J. Rose， “Directional Bias and NonUniformity in FPGA Global Routing Architectures， ” ICCAD， 1996， pp. 652 659. [9] V. Betz and J. Rose， “On Biased and NonUniform Global Routing Architectures and CAD Tools for FPGAs， ” CSRI Tech. Rep. 358， Dept. of ECE， University of Toronto， 1996. [10] C. E. Cheng， “RISA: Accurate and Efficient Placement Routability Modeling， ” DAC， 1994， pp. 690 695. [11] M. Huang， F. Romeo， and A. SangiovanniVincentelli， “An Efficient General Cooling Schedule for Simulated Annealing， ” ICCAD， 1986， pp. 381 384. [12] W. Swartz and C. Sechen， “New Algorithms for the Placement and Routing of Macro Cells， ” ICCAD， 1990， pp. 336 339. [13] J. Lam and J. Delosme， “Performance of a New Annealing Schedule， ” DAC， 1988， pp. 306 311. [14] C. Ebeling， L. McMurchie， S. A. Hauck and S. Burns， “Placement and Routing Tools for the Triptych FPGA， ” IEEE Trans. on VLSI， Dec. 1995， pp. 473 482. [15] C. Y. Lee， “An Algorithm for Path Connections and its Applications， “IRE Trans. 22 Electron. Comput.， Vol. EC=10， 1961， pp. 346 365. [16] J. S. Rose， W. M. Snelgrove， Z. G. Vranesic， “ALTOR: An Automatic Standard Cell Layout Program， ” Canadian Conf. on VLSI， 1985， pp. 169 173. [17] J. S. Rose， “Parallel Gl