-------------------------------------------------
Qrouter version 1.4
Detail netlist router for ASICs
(c) 2017 by Tim Edwards
Released under Gnu Public License
----------------------------------------------

----------------------------------------------
Release notes:
----------------------------------------------

Version 1.4
------------
Branch created April 25, 2017 mainly for
the purpose of making the existing version 1.3
the stable branch, particularly as version 1.3
is required for qflow.

Version 1.3
------------
Branch created September 16, 2014 and slowly
developed for more robust and DRC-clean output,
along with numerous bugfixes.  The underlying
algorithm is essentially unchanged from version
1.2.

Version 1.2
------------
Branch of 1.1 that puts qrouter in a Tcl/Tk
environment and includes routines to generate
and draw into a graphics window.  Code
reorganized into three main sections that are
called from the Tcl command line as "stage1",
"stage2", and "write_def".  The front-end
process of reading in the LEF and DEF files
and configuring the routing environment will
be added to the command set, eventually.

Based on analysis from the visualization of
the router, the code has been rewritten to
speed up the routing during multi-tap (more
than 2 connections) nets, so that previous
search results remain in place after each
route, avoiding redundant searching.  This
speeds up qrouter by a factor of about 2x.
A masking function that limits routes
to a specific defined portion of the layout
speeds up qrouter by a factor of about 30x.

Version 1.1
------------
Second major release.  Revised the "proute"
structure so that its position information
refers to the position of the structure itself
and not of the predecessor.  This requires
setting up proute structures for every point on
the source net, but makes it possible to specify
one or more alternate predecessors for each
potential route position.

Added handling of routes with larger size and
pitch on the higher layers.  Added handling
of technologies that do not allow contacts
to be stacked arbitrarily.  Some preliminary
work in search optimization.  Finding a viable
route (any viable route) quickly is the key to 
setting a bound on cost early and prevent
multiple passes over many points.

Added code for detailed analysis of port
geometry and taking steps necessary to avoid
generating DRC errors.

Redesigned internal structures so that nodes
are not in an independent list, but only listed
under their assigned net.  Routes are assigned
to nets, not to nodes.  Added the ability to read
in existing route geometry and add it to the
database.

Version 1.0
------------
First release.  This is work in progess on a
professional-grade multi-layer maze router.
First release implements the standard Lee
algorithm.  However, a modified Lee algorithm
is used that presents all nodes of the network
(other than the source node) as targets.  As
each target node is reached, in order of lowest
cost, the target node and its route to the
source are added to the source node, and the
process repeated until there are no more target
nodes.

The implementation is geometry-aware, to the
extent that all node and obstruction geometry
is present in the LEF file used to define the
standard cell macros.

The implementation uses the open standard
LEF and DEF formats.  Standard cell definitions
and routing layer definitions are read in from
the LEF file, and cell placement information
and an unrouted network are read from the DEF
file.  Output is a copy of the original input
DEF file, annotated with the physical routes.

----------------------------------------------
Compilation & installation:
----------------------------------------------

The system runs under autoconf, and so has
the standard compile and install sequence:

	./configure
	make
	make install

For FreeBSD, use 'gmake' instead of 'make'.

Options to configure:

	--prefix=<prefix>
		overrides the standard install
		location of /usr/local

	--with-libdir=<path>
		overrides the standard search
		location for configuration
		files, /usr/local/share/qrouter

	--with-tcl=<path>
		path to tclConfig.sh file.

	--with-tk=<path>
		path to tkConfig.sh file.

----------------------------------------------
Usage:
----------------------------------------------

   qrouter [-noc] [-s <script_name>]

     This is the normal invocation, where a
     Tcl-script specified by <script_name>
     contains all of the configuration information,
     specifies where to read LEF and DEF files,
     how to perform the routing, and where to
     write the output DEF file.  All commands
     in the script can alternatively be entered
     on the Tcl command line after starting
     qrouter.  The "-noc" option does not invoke
     the Tk console on startup, which is best
     for batch operation, as text output to the
     console can slow down the routing process.

   qrouter [-c <config_name>] [options] <basename>

     where <basename> is without an extension.
     File <basename>.def is assumed to exist
     and to define cell placement and netlist
     information.  File <config_name> is
     assumed to exist and contains basic
     routing parameters, or points to a LEF
     file containing detailed routing parameters.
     If this option is not specified, then the
     default configuration file name of "route.cfg"
     is used.

----------------------------------------------
Completed development tasks:
----------------------------------------------

1. New algorithm for routing nodes of a network,
   in which route_segs calculates costs out from
   source to any node in the network, settling
   on the minimum, and this continues until there
   are no nodes left to route.

2. Need to compute obstruction areas around nodes
   and mark them (e.g., with a flag) so that they
   can interpreted as obstructions when routing a
   different net, and available space when routing
   the node's net.

3. Rework the crossover cost method.  Currently
   it does not account for the vertical layer, and
   so gives a high crossover cost to layers that
   are more than one route level above a node and
   would not block it.

4. Stub routing to nodes from unobstructed positions
   smaller than the route pitch but outside of the
   tap geometry.

5. Crossover costing removed for all terminals on
   completed routes.

6. Replace linked list code with simpler linked
   lists, no dependency on non-open-source
   linked-list code.

7. Added the ability to specify additional
   obstruction areas in the route.cfg file.

8. Increased the route width to the width of a
   via where the distance between a via and a
   terminal is less than the route metal's
   spacing rule.  This cannot be done with
   normal routes in a DEF file, so it is added
   on as a "specialnets" section.

9. Collect all unroutable nets and route them
   with other nets marked as high-cost instead
   of obstructions.  Analyze all the resultant
   collisions between nets, and proceed with an
   iterative rip-up and reroute algorithm.

10. When a net is ripped up to remove it from
   the path of a net being routed in the 2nd
   stage, the ripped-up net is added to a list
   in the routed net so that it will not be
   ripped up to make way for that net again.
   This prevents infinite looping in the 2nd
   stage.

11. Clean up the DEF file reader with a proper
   parser ported from magic, like the LEF file
   reader was.

12. Add a Tcl/Tk command-line interface for
   interactive routing and display.

13. Recast the config file as a set of Tcl
   command-line commands to execute.  All
   original setup options have corresponding
   commands in the Tcl interpreter.  The
   config file and its parsing is retained
   for backwards compatibility.

14. Vias can be larger than metal routes.  Need
   to identify positions as obstructions to
   vias only.

15. Make Euclidean geometry checks instead of
   Manhattan geometry checks.

----------------------------------------------
Development to do:
----------------------------------------------

1. Handle nets in the input DEF file that are
   already routed by adding them as obstructions
   to the route grid.

2. Final stage should rip up and reroute each
   network in turn, with all crossover costing
   removed, so that each route will be cleaner
   (to be done by Tcl commands acting on
   individual routes.  Can be run as a simple
   Tcl script).

3. Need to normalize the segment and jog costs to
   the track pitch, so that costs do not give
   preference to the route layers with the widest
   track pitch.

4. Need a command-line switch (and/or Tcl
   command) to disable the specialnets section.

5. Sort trunk lines so no trunk lines overlap
   prior to routing.

6. Apply costing to terminals, giving higher cost
   to terminals with offsets and the lowest cost
   to simple on-grid contacts.

-------------------------------------------------