175.vpr
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
The best two references for VPR:
-
"Architecture and CAD for Deep-Submicron FPGAs," V. Betz, J.
Rose and A. Marquardt, Kluwer Academic Publishers, 1999.
-
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:
-
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.
-
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.
Last Updated: 14 October 1999
