Version 1.4 (Development) Release Notes
Version 1.3 (Stable) Release Notes
Version 1.2 Release Notes
Version 1.1 Release Notes
Version 1.0 Release Notes
Things To Do
Version 1.4 is the development branch of qrouter, started on April 25, 2017.
Version 1.3 is the distribution branch of qrouter, started as a development version on September 16, 2014, and upgraded to stable on April 25, 2017.
There were no major changes to the underlying algorithm in version 1.3 development, but mostly a series of changes to decrease the number of DRC errors generated in the layout, reduce memory overhead, and some code refactoring for efficiency.
Version 1.2 Version 1.2 is the development branch of qrouter, started on November 14, 2013. This version represents a major overhaul of the source code. Version 1.2 was upgraded from development to stable in September 2014.
List of completed tasks
- Added a Tcl interpreter option to the compile. This is intended to be the default compile option, although the original non-Tcl version is available and is backwardly compatible. The routing process is broken into stages which are relatively independent and can be called individually from the Tcl command line.
- Added graphics visualization of the routing process. This allows one to see the routing progress without appreciable slow-down of the routing process. A "debug" mode shows the search progress as well as the routing progress, which does slow down the process considerably. It is intended for diagnostic purposes only.
- Improved the routing performance by restructuring the routing of multi-terminal (more than two terminal) nets such that each terminal route works from the search solution of the previously routed terminal without starting the search over. This improves routing performance by a factor of about 2X without any impact on the routing solution.
- Improved the routing performance by implementing area masking. Before each net is routed, a mask is generated that is based on a simple model of the route, either an L-shaped route for two terminals, or a trunk-and-branches route for nets with more than two terminals. An "ideal" route is selected, and a mask is generated that covers the ideal route plus an additional area of "slack". The routing proceeds as before, but with searches stopped whenever the cost of the searched route exceeds the current maximum limit, or the position searched is outside of the mask. At the end of each pass, if any search position stopped because the maximum cost limit was reached, then the cost limit is doubled for the next pass. If all positions were stopped due to the masking, then the mask area is increased by one route track on all sides for the next pass. This method retains the essential benefits of the standard search algorithm but speeds up the routing time by a factor of around 20X to 30X. There is a minor impact to the routing solution (more routes fail on the first stage).
- Added Tcl command-line commands to allow individual nets to be routed.
- Added a Tcl command-line command to return a list of failing nets, with an option to put all nets in the design onto the failing list. This latter option enables an alternative routing procedure in which only the stage2 routing (allowing collisions and ripping up colliding nets) is performed.
Version 1.1 Version 1.1 was replaced by 1.2 as the stable branch of qrouter in September 2014. The initial version changes the structure of a potential route to point to its own location, rather than that of the preceeding position, so that the structure may conveniently hold pointers to one or more alternative routes. The first use of this modified structure is to avoid creating stacked contacts.
Version 1.1 was upgraded from the development version to the stable version on November 14, 2013.
List of completed tasks
- Redesigned the primary structure holding costing information so that it does not require allocating a single massive block of memory. Previous versions were having difficulty linking, and running with low memory overhead.
- Added a large amount of code designed to analyze the geometry around each port connection, and specify offsets or stub (stem) routes from the nearest grid point to the port that does not produce DRC errors.
- Added code to read existing net routes from the input DEF file, and add them to the database, so that qrouter can work from a partially-routed solution. "Fixed" or "cover" type nets, as well as nets in the "specialnets" section, are treated as obstructions to be routed around.
Version 1.0 Version 1.0 is an initial offering of an open-source, professional-grade, over-the-cell maze router. It is designed to be used with the all open-source digital design flow offered by OpenCircuitDesign, using user-supplied verilog source and the tools VIS, SIS, TimberWolf, and Magic. The detail router completes the open-source design flow.
List of completed tasks (from May/July 2011)
- 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.
- 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.
- Reworked the crossover cost method. The previous version did not account for the vertical layer, and so gave 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.
- Replaced linked list code with simpler linked lists, no dependency on non-open-source 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 was done in the output DEF file by declaring these stub routes in the "specialnets" section.
- Added a second-stage routing when the completed first-stage routing finishes with one or more routing failures. In the second stage, 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.
- Added a method to avoid looping in the second stage. This simply collects lists of nets that were ripped up to make way for another net, and prohibits the same sequence of rip-up and re-route again. It works well and is simpler than creating and analyzing a directed graph.
- Need method to sort the trunk-and-branch structures to maximize success on 1st stage routing. Probably best approach is an annealing process to swap tracks until collisions are minimized or eliminated.
- After each routing stage, trunk-and-branch structures should be renegotiated.
- Any dynamic changing of the trunk-and-branch structures should at least take into account major obstructions such as the power and ground posts.
- Reverse net number lookup table needed for speedup
- Net name hash table needed for speedup
- Need alternative version where multiple collisions can be made, and routing attempts to minimize collisions rather than make all routes collision-free.
Each revision has substantial bug fixes. See the code history for details.
Last updated: June 14, 2017 at 10:05pm