From: ncbi-seminar-admin@ncbi.nlm.nih.gov on behalf of Alejandro
Schaffer [schaffer@ncbi.nlm.nih.gov]
Sent: Friday, December 13, 2002 12:45 PM
To: ncbi-seminar@ncbi.nlm.nih.gov
Subject: Interview lecture 18 December

Physical Design Tools for Field Programmable Gate Arrays
John Karro
Oberlin College

Date: 18 December
Time: 1PM
Location: Bldg. 38A, 5th floor conference room

Field Programmable Gate Arrays (FPGAs) are a user-configurable
computer-chip architecture. In the last decade FPGAs have become extremely
popular due to their flexibility and low design costs, but these advantages
come at a substantial cost in performance when compared to custom-design
chips. To deal with this problem, we proposed the concept of a
three-dimensional FPGA. A study of this new architecture then led us into
an investigation of certain physical design problems, both in relation to
the 3D configuration and to the original structure.

The process of physical design is generally divided into three phases:
placement, global routing, and detailed routing. It is standard practice to
consider each of these phases sequentially, using a generated solution of
one as the fixed input to the next. It has been our goal to develop a
method of performing all three phases simultaneously, thus allowing
constraints relevant to a later phase to affect the computations of an
earlier phase. To date we have had great success integrating these phases
into a single step, producing tools for both standard and 3D-FPGA
architectures that run significantly faster than any tool in the literature
while at the same time leading to state-of-the-art circuit mappings.

In my talk I will discuss the approach we used to integrate these three
steps. First I will overview Spiffy, a tool designed to perform placement
and global routing simultaneously. Following this I will discuss Gambit,
which incorporates detailed routing as well. Using circuit mappings
produced by these tools, I will show that 3D-FPGAs do have the potential to
reduce the performance problems associated with the standard architecture.

References
(Note that the second and third references can be found in pdf format at
http://www.cs.oberlin.edu/~jkarro/

S.D. Brown, J.S. Rose, and Z.G. Varnesic, Field Programmable Gate Arrays
Kluwer Academic Publishers, Boston Massachusetts, 1992

J. Karro and J. Cohoon, ``A Spiffy Tool for the Placement
and Routing of Three-Dimensional Field Programmable Gate Arrays,'' Ninth
Great Lakes Symposium on VLSI, Ann Arbor, Michigan, Mach 1999, pp. 226-227


J. Karro and J. Cohoon, ``Gambit: A Tool for Simultaneous Placement and
Global Routing of Gate Arrays,'' 11th International Conference on Field
Programmable Logic and Applications, Belfast, Northern Ireland, Aug. 2001,
pp. 243-253.