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.
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.
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.
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.
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.
The system runs under autoconf, and so has the standard compile and install sequence:
./configure
make
make installFor 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.qrouter [-noc] [-s
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
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.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.
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.
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.
Stub routing to nodes from unobstructed positions smaller than the route pitch but outside of the tap geometry.
Crossover costing removed for all terminals on completed routes.
Replace linked list code with simpler linked lists, no dependency on non-open-source linked-list code.
Added the ability to specify additional obstruction areas in the route.cfg file.
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.
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.
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.
Clean up the DEF file reader with a proper parser ported from magic, like the LEF file reader was.
Add a Tcl/Tk command-line interface for interactive routing and display.
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.
Vias can be larger than metal routes. Need to identify positions as obstructions to vias only.
Make Euclidean geometry checks instead of Manhattan geometry checks.
Handle nets in the input DEF file that are already routed by adding them as obstructions to the route grid.
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).
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.
Need a command-line switch (and/or Tcl command) to disable the specialnets section.
Sort trunk lines so no trunk lines overlap prior to routing.
Apply costing to terminals, giving higher cost to terminals with offsets and the lowest cost to simple on-grid contacts.