SEGA Detailed Routing Software README
SEGA README FILE:
/*
* Copyright 1993 University of Toronto
*
* Permission to use, copy, modify, distribute, and sell this software and its
* documentation for any purpose is hereby granted without fee, provided that
* the above copyright notice appear in all copies and that both that
* copyright notice and this permission notice appear in supporting
* documentation, and that the name of the University of Toronto not be used
* in advertising or publicity pertaining to distribution of the software
* without specific, written prior permission. The University of Toronto
* makes no representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
* THE UNIVERSITY OF TORONTO DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
* SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS,
* IN NO EVENT SHALL THE UNIVERSITY OF TORONTO BE LIABLE FOR ANY SPECIAL,
* INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
* LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
* OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
* PERFORMANCE OF THIS SOFTWARE.
*/
/*
Authors:
Stephen D. Brown, Guy Lemieux, and Muhammad Khellah
Department of Electrical and Computer Engineering
University of Toronto, Toronto M5S 1A4, Canada
e-mail: brown@eecg.toronto.edu
*/
Release 1.0 May 13, 1994
Release 1.1 March 1, 1996
-- updated this README about L block pin placement
-- fixed filename parsing bug, main.c:394
-- change c_block.c, plot.c to reflect actual benchmark pin placements
-- ported to HP700 workstations; X still doesn't work properly on them
-- added experimental Annealing routing algorithm
(similar to PathFinder -- see FPGA'95)
-- added Fs=6 support (just for fun); use it by specifying Fs>3
-- added 'solution checksum' value to summarize the routing solution
(helps to verify that the algorithm is generating the same solution
after src code has been changed during debugging).
------------------------------------------------------------------------------
This README describes the SEGA detailed router for FPGAs.
The subdirectory "./circuits" contains 13 benchmark circuits that
can be used to experiment with SEGA. First the format of the circuit
netlists is described and then instructions are given for compiling
and executing the router.
NOTES:
o SEGA needs no compilation for a SUN-4 with X11 (an optimized and
static-linked binary is provided in bin.sun4 directory)
o Many features/options of this software are not documented, as it is
a research tool. The best source of documentation is the source
code :-)
o The software may be periodically updated. Check on
ftp.eecg.toronto.edu for future updates.
CIRCUIT NETLIST FORMAT
----------------------
Each two-point connection in the circuits has the following format:
NetName NetNumber Xcoord Ycoord 1 PinNumber
Xcoord Ycoord 1
Xcoord Ycoord 1
.
.
.
Xcoord Ycoord 1
Xcoord Ycoord 0 PinNumber
- NetName is a string identifying the net
- NetNumber is an integer. Each net in a circuit has a unique NetNumber, and
multiple two-point connections that are part of the same net will have the
same NetNumber.
- Xcoord,Ycoord are the X,Y coordinates of an L block, C block, or S block.
- PinNumber is the L block pin number, one for each end of the connection.
The circuits in the "./circuits" directory are all built with the L block
shown below:
| |
| |
---+--+---
| 1 4?5?|
---+5?4? 6+---
| |
---+0 2+---
| 3 6 |
|--+--+---
| |
| |
That is, the L blocks have 7 pins, numbered from 0 to 6. Pins 0,1,2,3 are
look-up table inputs, 4 is the clock input the L block's flipflop, 5 is a
tristate enable and 6 is the L block output. None of the circuits use pins
4 or 5, so their exact location is unknown.
Each pin on the L block appears on only one of its sides (except pin 6 which
is on two sides).
NOTE: SEGA assumes the circuit is valid and doesn't check to see if it
conforms to this logic block pinout. It will accept any logic block pinout.
However, as of version 1.1 pins are drawn on the proper sides to correspond
to the correct pattern.
NOTE: the L blocks on the periphery of the FPGA are a special case because
they represent I/O pads. Since they are a special case, there may be pins
that are shared by connections on different nets around the outside of the
chip. This is the only place where such illegal sharing of pins is allowed,
but it must be considered if you are to use these circuits. The reason
that this was done was because real FPGAs have many more I/O pads than would
fit around the periphery of the array of L blocks. Also, pins on the I/O pads
will not follow the same pin arrangement as the L blocks because the I/O pads
are considered 'special cases'.
COMPILING THE SEGA DETAILED ROUTER
---------------------------------
Important Note: you need a fully ANSI-C compatible compiler for this program.
To compile the router, edit the file ./src/plot.c and change "ljC" in the
following line:
#define POSTSCRIPTPRINTER "ljC"
to the name of the default postscript printer that you wish to use with the
router (you don't have to do this if you don't want to be able to print
routing pictures from SEGA).
You can also edit ./src/xsupport.c and change the line:
#define CGELIB "../lib"
to point to a CGE/SEGA library directory (/usr/local/lib/cge is recommended).
If you do this, move the files in ./lib to the directory specified by
CGELIB. Alternatively, you can create an environment variable CGELIB that
points to where the library files reside. (The library files are prologue
and epilogue files for PostScript).
Proceed to the ./src directory and inspect the Makefile. You may wish
to change the compiler and linker used (default is gcc). If you want
to compile with the X11 interface, define the token XSUPPORT (default).
Makefile.hp was used on an HP 735 workstation, but the X11 graphics don't
work properly. Send bug fixes to lemieux@eecg.toronto.edu.
The executable program, called "sega", will be created in the ./src directory.
RUNNING SEGA
-----------
To test SEGA, type
"sega -G -R 1 3 -o1 -w12 -F -X -L ../circuits/Test"
This command causes SEGA to route the circuit called Test, with the following
parameters:
option: "-G -R 1 3 -o1 -w12"
this option sepecifies a group of tracks (-G) with a segmentation
type of "constant length" and a segmentation length of 3 (-R 1 3).
-o1 means that each track's segments will be offset by one L block
from the track above and below it. -w12 means 12 tracks. For this
particular example, only one group of tracks is specified, so there
are 12 tracks per channel in the FPGA.
option: "-F"
this means "produce the result that optimizes the speed-performance
of the final circuit". By constrast, without -F the router will
optimize for area (by concentrating only on achieving 100% routing
of all connections and not worring about routing delays)
option "-X"
turns on the graphical X11 interface
option "-L"
causes SEGA to print statistics about routing delays of final
circuit
SEGA has an interactive graphics interface that is mouse-oriented. To see what
commands are available, put the cursor in the text where SEGA was started and
enter "?". To try out a mouse command, put the cursor in the graphics window
where the routing is displayed and press the appropriate button. For example,
to zoom in on a portion of the FPGA, press the left mouse button when pointing
at some L, C, or S block, then move the mouse to another block (you will see
an elastic box) and then press the left mouse button again. To see the
contents of the FPGA (not just the routing, but also the underlying routing
switches and wires), hold down the SHIFT key and press the right mouse button.
(Note: there is a bug in the way that the program draws the Logic Block pins -
you will see all the pins drawn on all four sides of the block, instead of
the real situation that was described near the beginning of this README file.
The bug affects only what you see on the screen, and is due to the way the
plotting code is written (it doesn't check whether or not a logic block pin
really comes out on each side). The router itself is not affected in any way
by this drawing error; SEGA knows how many sides each L block pins appears on.
To exit from SEGA, type "q" in the text window, or ^C.
To see a list of SEGA's command-line options, use "sega -f".
EDITING SOURCE CODE
-------------------
The source code is best viewed by setting tabstops to 4 in your
favourite editor.
The source code can organized into the following nearly-independant
modules: SUPPORT, FPGA, PATH, ROUTE, and MAIN. Generally speaking,
each module depends only on the previous ones (i.e., PATH never
calls a function found in ROUTE or MAIN, but it does call FPGA and
SUPPORT functions).
Modules and their code:
SUPPORT
mytypes.h /* generic typedefs */
error.h /* general error numbers and messages */
random.h /* prototypes */
random.c /* mother routines (32bit pseudorandom core) */
discrete.c /* discrete random variable generators */
contuous.c /* continous random variable generators */
stack.h /* prototypes */
stack_i.h /* internal details */
stack.c /* special stack data structure used */
FPGA
fpga.h /* header file exporting functions
* to other modules */
fpga_i.h /* detailed internal header file */
fpga.c /* interface code to other modules */
fpgasetget.c /* interface code to other modules */
fpgainit.c /* initialization FPGA instance structures */
fpgadestroy.c /* destroys FPGA instance structures */
c_block.c /* determines C block architecture */
s_block.c /* determines S block architecture */
segment.c /* determines segment length during init */
print.c /* print segment properties (ctl-middle mouse) */
query.c /* ask about C and S block connections */
line.c /* set creation code for connections */
reduce.c /* set reductions for connections */
PATH
path.h /* header file exporting functions to
* to other modules */
path_i.h /* detailed internal header file */
path.c /* interface code to other modules */
pathsetget.c /* interface code to other modules */
pathinit.c /* initializes PATH instance structures */
pathdestroy.c /* destroys PATH instance structures */
demand.c /* computes demand cost */
enum.c /* set enumaration code */
expand.c /* expands a graph into possible connections */
mark.c /* selects a connection, removes others */
net_delay.c /* computes net delays */
path_delay.c /* computes path delays */
pathref.c /* maintains path reference information to
* help detect sharing and competition for
* wire segments */
rdnetlst.c /* reads netlist from file */
sanity.c /* performs sanity check to ensure no bad
* connections were formed (no two different
* nets share a wire segment, and all formed
* connections are permissible by the FPGA
* architecture) */
ROUTE
route.h /* header file exporting functions to
* to other modules */
route_i.h /* detailed internal header file */
route.c /* interface code to other modules */
routecct.c /* router code -- makes routing decisions */
MAIN
main.c /* command-line argument parsing */