A Place-and-Route Tool for Heterogeneous FPGAs 
Laura Beck (lwb4@cornell.edu) 

 

Contents: 
Project Description: 
2 
Introduction: 
2 
Contributions: 
5 
Experimental Results: 
11 
Possible Future Work: 
18 
Summary: 
19 
References: 
21 

Project Description: 
I have been modifying an FPGA placer/router tool called Versatile Placer/Router (VPR) [1] to 
handle heterogeneous as well as homogeneous FPGA architectures. We want to experiment with 
heterogeneous FPGAs with embedded hard macros such as processors or multipliers to 
determine what FPGA routing channel structure allows for the greatest routability around these 
hard macros. 
 
Introduction: 
A field programmable gate array (FPGA) is a programmable device that can implement many 
different digital circuit designs.  FPGAs contain four types of elements called: logic blocks, 
I
 I
 I
 I
O 
O 
O 
O 
SB 
SB 
SB 
SB 
 IO 
IO 
LB  LB  LB 
SB 
SB 
SB 
SB 
IO 
IO 
LB  LB  LB 
IO 
IO 
 SB 
SB 
 SB 
SB 
LB  LB  LB 
IO 
IO 
SB 
SB 
SB 
SB 
I
 I
 I
 I
O 
O 
O 
O 
 Figure 1. FPGA Structure 
routing channels, switch boxes, and IO pins, arranged as shown in Figure 1. The body of the 
FPGA is a grid of logic blocks, colored green in Figure 1. The grid in Figure 1 is small for 
 
 2 

clarity- the grids in most actual FPGAs contain many more logic blocks. The spaces between the 
logic blocks are called routing channels, marked yellow for horizontal channels and pink for 
vertical channels in Figure 1. Switch boxes appear wherever vertical and horizontal channels 
intersect, and as with other chips, the FPGA is bordered by IO pins (shown in blue) allowing for 
communication with the external world. 
  
The structure and complexity of an FPGA’s logic blocks varies from device to device. However, 
in look-up-table (LUT) based FPGAs, the type we are studying, logic blocks always contain at 
least one LUT - which can be programmed to implement any Boolean function of some small 
number of variables - and one flip-flop [2]. Thus, each logic block can be programmed to either 
perform a small amount of logic, store a small amount of data, or sometimes both. The FPGA’s 
vertical and horizontal routing channels are made up of banks of wires, through which signals 
can travel between the logic blocks and between logic blocks and IO pins. Many vertical and 
horizontal wires go into each of the FPGA’s switch boxes, and these switch boxes are 
programmed to form only some of the many possible connections between these wires, causing 
the signals in the FPGA to be routed to the correct places. 
 
When working with an FPGA, one designs a large digital circuit, and then a software synthesis 
tool breaks it down into pieces small enough to be implemented by single logic blocks. Then a 
second computer-aided design (CAD) tool, called a placer/router, is needed to determine exactly 
where on the FPGA each part of the design should be located. As the name implies, a 
placer/router’s work has two stages: placement and routing. Placement determines exactly which 
FPGA logic blocks should implement which logic-block sized pieces of the circuit design, and 
routing decides how the FPGA’s switch boxes should be configured so that the circuit’s signals 
will travel to the appropriate places through the FPGA’s channels. The placer tries to arrange the 
logic blocks in a way that will minimize the distance signals in the circuit will have to travel. The 
router tries to minimize the amount of wiring needed and the speed the final circuit will run at. 
Routing is generally much more time-consuming than placement. My work involved modifying 
the C-code for a placer/router tool called Versatile Place and Route (VPR) that was developed at 
the University of Toronto [1]. 

 3 

Most FPGAs look somewhat like Figure 1 in that all of their logic blocks have the same 
structure, all of their routing channels are the same size, and basically their entire structure is 
uniform. Such FPGAs are called homogeneous FPGAs.  We are interested in studying 
heterogeneous FPGAs –  those in which some parts of the FPGA are different. Particularly, we 
want to study FPGAs with embedded hard macros: non-reconfigurable hardware such as 
processors and multipliers inserted somewhere in the FPGA [3]. An example of such a device is 
the Xilinx Virtex II Pro FPGA, equipped with embedded memory blocks, a multiplier, and two 
processors. 
 
Our goal is to determine whether non-uniform channel sizes would be useful in FPGAs 
containing hard macros. A study conducted by the makers of VPR showed that for homogeneous 
FPGAs it is optimal for all channels to be the same size [4], however their study did not involve 
any hard macros. We plan to conduct our investigation by using VPR to place and route circuits 
from the twenty-circuit MCNC Benchmark Suite on FPGA architectures containing hard macros 
with several different channel structures. The VPR program was not designed to work with this 
type of heterogeneous FPGA, so I modified VPR to handle these architectures. 
 
Another related study was conducted in 2001 by P. Hallschmid and S. Wilton [5]. Their study 
differs from ours in that it focused on embedded memory blocks whereas we are considering 
general hard macros, and their study used detailed routing, while we are using global routing. 
The difference between detailed and global routing concerns switch boxes. The simplest (and 
most expensive) type of switch box one could build would be capable of making a connection 
between any two of the wires entering it. This requires more hardware than is found in actual 
switch boxes  –  which usually are only able to form some of these connections. In detailed 
routing, one gives specific information about the switch boxes of the FPGA being used to 
produce a route that could be downloaded to an actual FPGA. In global routing, one assumes 
ideal switch boxes that can form any possible connection. Global routing is good for 
experimenting with hypothetical FPGA architectures that do not yet have any specific switch box 
structure.  At this  stage, we are not concerned with switch behavior, so global routing is 
appropriate for our work. 

 4 

Contributions: 
1)  The first modification I made to VPR was to 
allow a user to specify any channel in the FPGA 
and determine what size that channel would be, 
either in absolute units, or relative to the size of 
a typical channel. The relative size is useful 
because the size of a typical channel is not 
usually known before routing takes place. VPR 
performs a binary search to determine the 
smallest size for typical  channels that will not 
make routing impossible. Figure 2 shows VPR’s 
display of an FPGA with some channels wider 
than others. The gray squares represent logic 
Figure 2. VPR Display of an FPGA with 
blocks and the subdivided gray squares along 
Two Very Wide Channels 
the border represent IO pins. 
 
 2)  Next I integrated some code written by a 
former student working with my mentor into 
my modified version of VPR. The MCNC 
Benchmark circuits we are placing and 
routing in our study do not contain any hard 
macros –  when we place and route a circuit, 
we want to select a group of logic blocks 
from that design to model a hard macro in 
our experiment. The former student’s code 
chooses logic blocks to represent the hard 
macro, places them together in a square at 
the FPGA’s center, and colors these blocks 
and wires that connect to them pink in 
Figure 3. VPR Display of an FPGA with 
A Hard Macro at its Center 
VPR’s graphical user interface (GUI) 
display (see Figure 3). His code ensures that 
 
 5 
�2礼�