【正文】 sign could not be successfully routed because SEGA ran out of SEGA to perform detailed routing on a global route generated by VPR increases the total number of tracks required to route the circuits by over 68% vs. having VPR perform the routing pletely. Clearly SEGA has difficulty routing large circuits when input pin doglegs are not encourage other FPGA researchers to publish routing results using these larger benchmarks， we issue the following “FPGA challenge.” Each time verified results which beat the previously best verified results on these benchmarks are announced， we will pay the authors $1 (sorry， $1 Cdn.， not $1 .) for each track by which they reduce the total number of tracks required from that of the previously best results. The 20 technologymapped lists， the placements generated by VPR and the currently best routing track total are available at 6 Conclusions and Future Work We have presented a new FPGA placement and routing tool that outperforms all such tools to which we can make direct parisons. In addition we have presented benchmark results on much larger circuits than have typically been used to characterize academic FPGA place and route tools. We hope the next generation of FPGA CAD tools will be pared on the basis of these larger benchmarks， as they are a closer approximation of the kind of problems being mapped into today’s of the main design goals for VPR was to keep the tool flexible enough to allow its use in many FPGA architectural studies. We are currently working on several improvements to VPR to further increase its utility in FPGA architecture research. In the near future VPR will support buffered and segmented routing structures， and soon after that we plan to add a timing analyzer and timingdriven routing. 21 References [1] S. Brown， R. Francis， J. Rose， and Z. Vranesic， FieldProgrammable Gate Arrays， Kluwer Academic Publishers， 1992. [2] Xilinx Inc.， The Programmable Logic Data Book， 1994. [3] AT amp。 just continue expanding normally. Since the new path added to the partial routing has a cost of zero， the maze router will expand around it at this new path is typically fairly small， it will take relatively little time to add this new wavefront， and the next sink will be reached much more quickly than if the entire wavefront expansion had been started from scratch. Figure 3 illustrates the difference graphically. 5 Experimental Results The various FPGA parameters used in this section were always chosen to allow a direct parison with previously published results. All the results in this section were obtained with a logic block consisting of a 4input LUT plus a flip flop， as shown in Figure 2. The clock was not routed in sequential circuits， as it is usually routed via a dedicated routing work in mercial FPGAs. Each LUT input appears on one side of the logic block， while the logic block output is accessible from both the bottom and right sides， as shown in Figure 4. Each logic block input or output can connect to any track in the adjacent channel(s) (. Fc = W). Each wire segment can connect to three other wiring segments at channel intersections ( Fs = 3) and the switch box topology is “disjoint” that is， a wiring segment in track 0 connects only to other wiring segments in track 0 and so on. Experimental Results with Input Pin Doglegs 18 Most previous FPGA routing results have assumed that “input pin doglegs” are possible. If the connection box between an input pin and the tracks to which it connects consists of Fc independent pass transistors controlled by Fc SRAM bits， it is possible to turn on two of these switches in order to electrically connect two tracks via the input pin. We will refer to this as an input pin dogleg. Commercial FPGAs， however， implement the connection box from an input pin to a channel via a multiplexer， so only one track may be connected to the input pin. Using a multiplexer rather than independent pass transistors saves considerable area in the FPGA layout. As well， normally there is a buffer between a track and the connection block multiplexers to which it connects in order to improve speed。maximum FPGA dimension. This results in Dlimit being the size of the entire chip for the first part of the anneal， shrinking gradually during the middle stages of the anneal， and being 1 for the lowtemperature part of the ， the anneal is terminated when T * Cost / Ns. The movement of a logic block will always affect at least one . When the temperature is less than a small fraction of the average cost of a ， it is unlikely that any move that results in a cost increase will be accepted， so we terminate the anneal. 3 Routing Algorithm VPR’s router is based on the Pathfinder negotiated congestion algorithm [14， 8].Basically， this algorithm initially routes each by the shortest path it can find，regardless of any overuse of wiring segments or logic block pins that may result. One iteration of the router consists of sequentially rippingup and rerouting (by the lowest cost path found) every in the circuit. The cost of using a routing resource is a function of the current overuse of that resource and any overuse that occurred in prior routing iterations. By 16 gradually increasing the cost of oversubscribed routing resources， the algorithm forces s with alternative routes to avoid using oversubscribed resources， leaving only the that most needs a given resource the experimental results in this paper we set the maximum number of router iterations to 45。 q is 1 for s with 3 or fewer terminals， and slowly increases to for s with 50 ， x(n) and Cav， y(n) are the average channel capacities (in tracks) in the x and y directions， respectively， over the bounding box of cost function penali