SEGA Detailed Routing Software
Last modified September 26, 1997.
Many links are broken...will fix later (sorry)
News: ISPD'97 has come and gone! Check out the ISPD'97 paper in the Publications
section.
Info: The ISPD'97 paper says that the results and benchmarks are available
on the web. I still haven't had time to put them up properly yet. My work
on this so far is
here.
UPDATE: Release 1.1 on March 1, 1996.
NEW TOOLS: Translators from VPR to SEGA formats on June 21, 1996.
Tools updated on February 24, 1997.
SEGA, the successor to CGE, was developed as a tool to evaluate
routing algorithms and architectures for array-based Field-Progammable
Gate Arrays (see also
FPGA Research at UofT
). SEGA was written in a modular fashion to permit flexibility
between modifying the routing algorithm and representing the routing
architecture.
SEGA and CGE both solve the detailed routing resource allocation problem
for array-based FPGAs. An
array-based FPGA consists of horizontal and vertical routing channels.
Each channel is composed of many `wires' of varying lengths (wire segments),
as well as routing switches which permit the wires to be interconnected.
Connections between various `gridpoints', indicated by a series of
coordinates, are given as input data to the router. These were produced
by another router, the global router, whose goal was to evenly distribute
connections amongst the channels as well as reduce the number of turns
each connection made. A detailed router must assign connections to routing
wires and switches from the FPGA interconnect. Since the number of
connections can be quite high, competition for resources can occur.
Because the entire circuit must be routed to be useful, the router must
try as hard as it can to produce a conflict-free solution.
SEGA improves upon CGE in that it considers the speed-performance of the
routed circuit an important goal (instead of just routability). To
achieve good speed-performance, it must consider wire segment length as
part of the problem -- longer wire segments imply fewer routing switches
are needed, and each routing switch imposes considerable signal delay.
Source Code
Click
here
to ftp the source code. Input netlists of some circuits are also included
to provide a basis for experimental research.
Click
here
to see the README included in the source code.
Click
here to get the
SEGA to BLIF conversion utility source code.
Click
here to get the
VPR to SEGA netlist conversion utility source code. You will also need to
use an architecture file similar to
cge.arch.2
with VPR to target a SEGA-compatible FPGA.
Benchmark Circuits
Click
here
to get the CBL
LGSynth93
circuits that have been mapped into 4-LUTs.
These circuits are in BLIF format. (Thanks go to Mike Hutton
for this work.)
Click
here
to get the SEGA circuits that have input-pin and output-pin doglegs. These
circuits are in SEGA-input format.
Click
here
to get the SEGA circuits that have only output-pin doglegs
(i.e., NO input-pin doglegs). These circuits are in SEGA-input
format.
Click
here to get a fixed
version of k2 which can be translated into BLIF for use by VPR.
(VPR complains about the k2 circuit included with SEGA because
there are some nets in it that don't make practical sense.)
Routed Circuits
See a
simple
(60 kB PostScript) and a
complex
(1.9 MB PostScript) circuit that was routed with SEGA.
Publications
About SEGA
-
-
G. Lemieux,
``Design and Implementation of Detailed Router Software for
Segmented-Architecture Field-Programmable Gate Arrays''
(PDF),
B.A.Sc. Thesis, University of Toronto, April 1993.
-
-
G. Lemieux
and
S. Brown,
``A Detailed Router for Allocating Wire Segments in FPGAs''
(PDF),
ACM Physical Design Workshop, Lake Arrowhead, California,
pp. 215 - 226, April 1993.
-
-
M. Khellah,
S. Brown,
and
Z. Vranesic,
``Modelling Routing Delays in SRAM-based FPGAs''
(PDF),
Proc. 1993 CCVLSI, Banff, Canada, pp. 6B.13 - 6B.18,
November 1993.
-
-
M. Khellah,
S. Brown,
and
Z. Vranesic,
``Minimizing Interconnection Delays in Array-based FPGAs'',
Proc. 1994 Custom Integrated Circuits Conference, San Diego, CA,
May 1994.
-
-
S. Brown,
G. Lemieux,
and M. Khellah,
``Segmented Routing for Speed-Performance and Routability in Field-Programmable
Gate Arrays''
(PDF),
Journal of VLSI Design, 4(4), pp. 275 - 291, 1996.
-
-
G. Lemieux,
S. Brown,
D. Vranesic,
``On Two-Step Routing for FPGAs'', International
Symposium on Physical Design
(PDF),
Napa, CA, pp. 60 - 66, April 1997.
Other FPGA-related
-
-
Z. Zilic,
G. Lemieux,
K. Loveless,
S. Brown,
and
Z. Vranesic
``Designing for High Speed-Performance in CPLDs and FPGAs''
(PDF),
Proc. 3rd Canadian Workshop on Field-Programable
Devices (FPD'95): Technology, Tools, and Applications,
Montreal, Canada, pp. 108 - 113, May 1995.
-
-
Stephen D. Brown
Robert J. Francis,
Jonathan Rose,
and
Zvonko G. Vranesic,
``Field-Programmable Gate Arrays'', Kluwer Academic Publishers, 222 pages,
1992.
-
-
Jonathan Rose
and
Stephen D. Brown,
``The Effect of Switch Box Flexibility on Routability of Field-Programmable
Gate Arrays'', Proc. 1990 Custom Integrated Circuits Conference,
pp. 27.5.1 - 27.5.4, May 1990.
-
-
Jonathan Rose
and
Stephen D. Brown,
``Flexibility of Interconnection Structures in Field-Programmable Gate
Arrays'', IEEE Journal of Solid State Circuits, Vol. 26 No. 3,
pp. 277-282, March 1991.
-
-
B. Tseng,
Jonathan Rose
and
Stephen D. Brown,
``Using Architectural and CAD Interactions to Improve FPGA Routing
Architectures'', First International ACM/SIGDA Workshop on Field-
Programmable Gate Arrays, pp. 3-8, February 1992.
-
-
Stephen D. Brown,
Jonathan Rose
and
Zvonko G. Vranesic,
``A Detailed Router for Field-Programmable Gate Arrays'',
Proc. IEEE International Conference on Computer Aided Design,
pp. 382-385, November 1992.
-
-
Stephen D. Brown,
Jonathan Rose
and
Zvonko G. Vranesic,
``A Detailed Router for Field-Programmable Gate Arrays'',
IEEE Transactions on Computer Aided Design of Integrated Circuits
and Systems,
Vol. 11 No. 5, pp. 620-628, May 1992.
-
-
R. Francis,
Jonathan Rose
and
Zvonko G. Vranesic,
``Chortle-crf: Fast Technology Mapping for Lookup Table-Based FPGAs'',
Proc. 28th DAC, pp. 227-223, June 1991.
-
-
Jonathan Rose
``Parallel Global Routing for Standard Cells'',
IEEE Transactions on Computer Aided Design of Integrated Circuits
and Systems, Vol. 9 No. 10, pp. 1085 - 1095, Oct. 1990.
The web counter says you're visitor
.