------------------------------------------------------------------------- SPEC CPU2000 Benchmark Description File Benchmark Name: VPR (Versatile Place and Route) Benchmark Author: Vaughn Betz Benchmark Program General Category: Integrated Circuit Computer-Aided Design Program (More specifically, performs placement and routing in Field-Programmable Gate Arrays) Benchmark Description: VPR is a placement and routing program; it automatically implements a technology-mapped circuit (i.e. a netlist, or hypergraph, composed of FPGA logic blocks and I/O pads and their required connections) in a Field-Programmable Gate Array (FPGA) chip. VPR is an example of an integrated circuit computer-aided design program, and algorithmically it belongs to the combinatorial optimization class of programs. Placement consists of determining which logic block and which I/O pad within the FPGA should implement each of the functions required by the circuit. The goal is to place pieces of logic which are connected (i.e. must communicate) close together in order to minimize the amount of wiring required and to maximize the circuit speed. This is basically a slot assignment problem -- assign every logic block function required by the circuit and every I/O function required by the circuit to a logic block or I/O pad in the FPGA, such that speed and wire-minimization goals are met. VPR uses simulated annealing to place the circuit. An initial random placement is repeatedly modified through local perturbations in order to increase the quality of the placement, in a method similar to the way metals are slowly cooled to produce strong objects. Routing (in an FPGA) consists of determining which programmable switches should be turned on in order to connect the pre-fabricated wires in the FPGA to the logic block inputs and outputs, and to other wires, such that all the connections required by the circuit are completed and such that the circuit speed is maximized. The connections required by the circuit are represented as a hypergraph, and the possible connections of wire segments to other wires and to logic block inputs and outputs are represented by (a different) directed graph, which is often called a "routing-resource" graph. VPR uses a variation of Dijkstra's algorithm in its innermost routing loop in order to connect the terminals of a net (signal) together. Congestion detection and avoidance features run "on top" of this innermost algorithm to resolve contention between different circuit signals over the limited interconnect resources in the FPGA. Input Description: The net.in file provides the netlist (hypergraph) of the circuit to be placed and routed in an FPGA. The net.in file for the reference run contains the netlist of the "clma" benchmark circuit. This benchmark circuit comes from the Microelectronics Center of North Carolina (MCNC) circuit benchmark suite. (See S. Yang, "Logic Synthesis and Optimization Benchmarks, Version 3.0," Tech. Report, Microelectronics Center of North Carolina, 1991, for a description of this benchmark suite). clma is a sequential circuit consisting of approximately 8300 4-input look-up tables, several hundred registers and several hundred IO pads. As such it is a fairly large benchmark circuit. The arch.in file describes the FPGA architecture in which this circuit is to be implemented. The target architecture in this case is an "island-style" FPGA that is reasonably similar to the commercial Xilinx 4000 series of FPGAs. The place.in file provides a circuit placement (assignment of positions to each circuit element in the netlist) which is used when VPR performs a routing. This file is ignored when VPR is invoked in order to produce a placement. Output Description: place_log.out: The statistics and validity check results output by VPR as it places a circuit into the target FPGA. route_log.out: The statistics and validity check results output by VPR as it routes a circuit in the target FPGA. route.out: The final circuit routing. This file gives a list of which wires and input and output pins on the FPGA logic blocks must be connected together in order to route each net in the input circuit. A fourth file (place.out) is also generated by VPR's execution, but this file is not diffed in the final validity tests. This file contains the circuit placement output by VPR (assignment of circuit elements to locations). It is not diffed by the final SPEC validity tests because round-off error can result in different final placements. VPR is invoked twice in the SPEC benchmark suite. In the first invocation, it performs a placement, using the net.in and arch.in files as inputs, and creating the place_log.out and place.out files as outputs. In the second invocation, VPR performs a routing, using the net.in, arch.in and place.in files as inputs, and creating the route_log.out and route.out files as outputs. Programming Language: ANSI C Known portability issues: Use -DSPEC_CPU2000. No known portability problems. References: VPR home page: http://www.eecg.toronto.edu/~vaughn/vpr/vpr.html The best two references for VPR are: "Architecture and CAD for Deep-Submicron FPGAs," V. Betz, J. Rose and A. Marquardt, Kluwer Academic Publishers, 1999. and V. Betz, "Architecture and CAD for the Speed and Area Optimization of FPGAs," Ph.D. Dissertation, University of Toronto, 1998. Other useful (but less complete) references are: V. Betz and J. Rose, "VPR: A New Packing, Placement and Routing Tool for FPGA Research," Seventh International Workshop on Field-Programmable Logic and Applications, 1997, pp. 213 - 222. and V. Betz and J. Rose, "Directional Bias and Non-Uniformity in FPGA Global Routing Architectures," IEEE/ACM International Conference on Computer-Aided Design, 1996, pp. 652 - 659.