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 .