Qrouter 1.3 (Stable) and 1.4 (Development)

Table of Contents

Revision information on Qrouter 1.4
Revision information on Qrouter 1.3
Revision information on Qrouter 1.2
Revision information on Qrouter 1.1
Revision information on Qrouter 1.0

Revision information on Qrouter 1.4 (development):

Revision information on Qrouter 1.3 (stable):

Revision information on Qrouter 1.2:

  1. Thursday, November 14, 2013
    This is a first draft.
  2. November 15, 2013 at 3:00am
    Several corrections for errors found when the system was run from the standard install location.
    Also: Made a correction to the backward-compatibility of version 1.2, in particular to restore the use of "-c" and "-i" switches.
    Also: A few more changes, allowing the "-c" option to operate in a completely backward-compatibility mode by running a simple script roughly equivalent to qrouter version 1.1 (but a lot faster).
  3. November 16, 2013 at 3:00am
    Added some more commands to the qrouter command set to complete the overlap with OS command-line switches and statements in the configuration file. Everything can now be done from the interpreter prompt.
    Also: Update at Fri Nov 15 11:24:23 EST 2013 by tim
    Also: Merge branch 'master' into work
    Also: Corrected handling of the script file switch, some DEF read modifications for reading pre-routed nets (not completed).
    Also: Cleaned up the problems with reinitialization; qrouter can now re-read a DEF file or read a routed DEF file and proceed normally.
    Also: Cleaned up the use of "verbose", so that "verbose 0" is truly quiet (only reports failed routes at the end of each stage, and other major errors). "verbose 3" is the level of the original output, and is the default. "verbose 0" will significantly speed up the routing process, as there is a rather large overhead associated with flushing output to the tkcon console window.
    Also: Thought better of the catch-all "config" command, and broke it up into individual commands like "verbose", "layers", etc. Otherwise the distinction between commands and sub-commands of "config" is pretty arbitrary.
    Also: Modified the configuration file reader to accept the new Tcl command syntax as well as the older syntax.
    Also: Modified routines dofirststage and dosecondstage so that they return the number of failed routes. The Tcl commands "stage1" and "stage2" then return the number of failed routes to the interpreter. This allows for a simple test of success on the command line or in the route script. The default route script has been updated to take advantage of this feature.
  4. November 23, 2013 at 3:00am
    Renamed "config.h" to "qconfig.h" to prevent confusion with all the "config" files used by autoconf.
    Also: Update at Fri Nov 22 11:35:36 EST 2013 by tim
    Also: Merge branch 'master' into work
    Also: Added INC_SPECS to Makefile.in so that Tcl/Tk header files in places other than /usr/include/ will be handled properly. Corrected a typo for the redefinition of "Flush" for the non-Tcl compile, as kindly pointed out by Stefan Thiede.
    Also: Fixed a crash condition that occurs when a pin extends outside of the defined track area, potentially giving it a track position of -1, which was not handled one place in the DEF read routine.
  5. November 24, 2013 at 3:00am
    Changed the behavior of "qrouter -h" when querying the version number such that (1) "qrouter -v 0 -h" prints only the version information, and (2) the Tcl/Tk version prints ".T" at the end of the version string so that querying tools (like qflow) can determine the capabilities of qrouter and can be made aware when scripting is and is not available.
    Also: Update at Sat Nov 23 10:10:38 EST 2013 by tim
    Also: Merge branch 'master' into work
    Also: Modification to the qrouter.tcl script so that having a local "route.cfg" file is equivalent to having "-c " on the command line, in making qrouter run the "autoroute" script. This adds a little more consistency to the different ways qrouter runs, depending on the setup.
    Also: Added a line to the top of the output file when using "qrouter -i" to query LEF files for information; this line includes version information about qrouter.
    Also: Removed the compiled "qrouter" from the distribution (should not have been there), and changed Makefile.in to fix a few errors in the "make clean" sequence.
  6. November 27, 2013 at 3:00am
    Correction of the code supporting output of congestion analysis; corrected a few other errors, and greatly increased the vector used as a temporary hold space for net names read from files, which at 64 bytes was far too short for some names generated by yosys.
    Also: Update at Tue Nov 26 19:20:56 EST 2013 by tim
    Also: Merge branch 'master' into work
  7. November 28, 2013 at 3:00am
    Corrected an error in counting when writing back the order in which to route nets; count was off by one and the last net to be routed would be pushed up to the front. Also, got rid of the pointless output statement about "TotalRoutes", which is meaningless, and instead replaced it with "Nets remaining", which is a metric of interest. Arguably the most important metric of interest.
    Also: Update at Wed Nov 27 20:35:43 EST 2013 by tim
    Also: Merge branch 'master' into work
  8. November 29, 2013 at 3:00am
    Changed the output of "congested" so that the values are normalized to the number of routing layers. A value of 1 would indicate full occupation of all routing grids covering a cell.
    Also: Update at Thu Nov 28 12:00:44 EST 2013 by tim
    Also: Merge branch 'master' into work
  9. December 2, 2013 at 3:00am
    Modified the SPECIALNETS section on advice from Stefan Thiede to use the net name for the stub routes instead of making a new, fake net name. Otherwise some tools treat the stubs as different nets and complain about the nets overlapping. Removed most instances where empty stub routes were being written to the output. Also, modified the NETS structure from a linked list to an array. The array is passed directly to qsort() for sorting, and then the nets are in order of route priority. The qsort compare routines were modified to include handling critical nets, instead of having them sorted separately. The getnettoroute() routine then just retrieves the indexed net, and doesn't have to go searching for it.
    Also: Update at Sun Dec 1 17:13:56 EST 2013 by tim
    Also: Merge branch 'master' into work
    Also: Made several key modifications; changed instance record to have a pointer to the macro record instead of having a copy of the macro name, avoiding having to search over the macro list. But mainly, for the Tcl version, the instance records are hashed in addition to the linked list, greatly improving the time to read in a DEF file with many nets.
  10. December 4, 2013 at 3:00am
    Corrected an error where a net with no routable terminal points would cause a crash when computing a route mask area.
    Also: Update at Tue Dec 3 15:37:36 EST 2013 by tim
    Also: Merge branch 'master' into work
    Also: Some corrections to allow compiling without Tcl support.
  11. December 6, 2013 at 3:00am
    Cleaned up the stupidity with regard to the use of Nlnets[0]. The net numbers are ordered from 1, not the array. The netorder record is unnecessary, since nets are ordered by qsort(), but the record is kept for the convenience of marking critical nets and having them handled by qsort(). There are no longer any NULL records in Nlnets[]. There is still some ambiguity when SPECIALNETS are declared in the DEF file, especially if the nets are partially routed with fixed routes. This needs to be dealt with properly.
    Also: Update at Thu Dec 5 15:43:47 EST 2013 by tim
    Also: Merge branch 'master' into work
    Also: Restored the "failing all" command, which had not been rewritten for the revised Nlnets array.
  12. December 21, 2013 at 3:00am
    A few changes to deal with problems stemming from lower-case in either macro names or the tech directory name.
    Also: Update at Fri Dec 20 13:04:37 EST 2013 by tim
    Also: Merge branch 'master' into work
    Also: Corrected an error where non-square vias caused the wrong dimension to be used when drawing a stem from the last via to the terminal.
  13. January 8, 2014 at 3:00am
    Corrected an error in which a position marked as a stub route to a terminal would be missed when checking for net collisions on the second stage, resulting in a shorted net in the output.
    Also: Update at Tue Jan 7 15:57:14 EST 2014 by tim
    Also: Merge branch 'master' into work
  14. January 12, 2014 at 3:00am
    A number of corrections to the code determining how to make the final connections to a terminal without generating DRC errors. Also tracked down and corrected an error that allowed routes with collisions to route on positions that are too close to other terminal positions to be allowed; sometimes this error would show up as a missing final connection to a terminal.
    Also: Update at Sat Jan 11 20:56:53 EST 2014 by tim
    Also: Merge branch 'master' into work
  15. January 19, 2014 at 3:00am
    Removed temporary files. Corrected an error in the "expand taps" subroutine that was improperly ignoring what layer geometry was on, and thereby growing tap geometry into areas where the tap did not exist.
    Also: Update at Sat Jan 18 14:46:58 EST 2014 by tim
    Also: Merge branch 'master' into work
    Also: Modified the handling of route layers with pitches too narrow and vias too wide to be placed in adjacent tracks. Handling is not ideal, yet, but this fix reduces the majority of errors coming from routes on these kind of layers. More fixes to come.
    Also: Corrected an error with route writeback that would fail to preserve the stub routing information if it was on the "wrong" layer of a via.
  16. January 20, 2014 at 3:00am
    Added code to deal with DRC spacing violations between a via on an offset terminal position and a neighboring via or bend in a metal route. Discovered that offset measurements were being double-counted, so fixed that.
    Also: Update at Sun Jan 19 13:04:02 EST 2014 by tim
    Also: Merge branch 'master' into work
    Also: Removed some diagnostic print statements.
  17. January 23, 2014 at 3:00am
    Several enhancements to take care of route layers with vias that are large enough to cause DRC spacing violations with vias on adjacent tracks.
    Also: Update at Wed Jan 22 09:55:30 EST 2014 by tim
    Also: Merge branch 'master' into work
    Also: Corrected an error which was calculating the wrong edge of non-square vias and therefore could determine that track spacing was too small for placing vias, force the track spacing to double, and thereby make the layout mostly unroutable.
    Also: Fixed an incorrect handling of roundoff error for negative values. This can happen on the left and bottom edge of a layout if the routing area extends beyond the layout zero coordinate axes in X or Y. The old problem that (int)(x + 1/2) does not work when x < 0!
  18. February 4, 2014 at 3:00am
    Corrected one error with oversized route layers that can allow a placement of a via in the track next to a route where such an arrangement will cause a DRC error. Relaxed the constraint on taps with nearby obstructions such that the tap position will be allowed for routing using a tap position offset, if and only if the next track over in the direction of the offset is empty. This helps to prevent having a tap be unroutable because there is too much nearby obstruction geometry, without resorting to a full geometry search that would require a lot of additional coding.
    Also: Update at Mon Feb 3 14:00:13 EST 2014 by tim
    Also: Merge branch 'master' into work
  19. February 6, 2014 at 3:00am
    Corrected two errors---one is a small change to the stub adjustment routine, requiring the error box to not only touch the neighboring geometry but to touch it in a non-trivial way (not just corner points touching). The other is a more serious error that can reassign a tap position as an available route position where one tap crosses over another tap.
    Also: Update at Wed Feb 5 10:11:37 EST 2014 by tim
    Also: Merge branch 'master' into work
    Also: Corrected a secondary problem caused by allowing additional offset taps. Solution is to block positions around an offset tap if an offset tap is placed, and to block the position at an offset tap if a route is placed in front of the offset. These are temporary blocks that could prevent routing to the tap on the first pass but will not interfere with the second stage rip-up and reroute.
  20. February 8, 2014 at 3:00am
    Update of config files and Makefile that really should have been in gitignore. . . this is a nonfunctional update. . .
    Also: Update at Fri Feb 7 12:37:16 EST 2014 by tim
    Also: Merge branch 'master' into work
  21. February 9, 2014 at 3:00am
    Implemented a workaround for nodes that are boxed in by obstruction layers which are spaced properly for euclidean distance measurement but not for manhattan distance measurement. Any tap for which the metal area completely covers a via centered on the route grid point will be made unconditionally routable. It may be necessary to flag such an unconditionally routable point to make sure that it does not get removed by the tap_to_tap interaction routine. Also removed an improper check for VDD and GND nets left over from much earlier code; it was causing power and ground nets to be invisible to the router under some circumstances.
    Also: Update at Sat Feb 8 21:07:22 EST 2014 by tim
    Also: Merge branch 'master' into work
  22. February 10, 2014 at 3:00am
    Modifications to the LEF reader to allow metal layers that are not numeric (like "topmet" instead of "met4") to be parsed. They are *assumed* to be in order from bottom to top, such that "topmet" followed by "met2" would cause a real screw-up. But it's doubtful that there's any better way to parse a LEF file, unless it's to look at all the via layers and arrange them accordingly. If any LEF file is so badly written that it comes to that, then I'll revisit the code then. And not until.
    Also: Update at Sun Feb 9 15:04:20 EST 2014 by tim
    Also: Merge branch 'master' into work
    Also: Correction to cleanup_net; can only do a simple rerouting of a segment end if the two neighboring contacts are the same type. This fix removes a potential to create shorted nets, but also allows the DRC error that the cleanup_net code was trying to eliminate. The DRC errors will have to be handled elsewhere by generating specialnets to connect across the two vias.
    Also: Corrected an error with cleanup_net (another one)---forgot to ignore route endpoints that are taps to cell ports; otherwise removing the via and connecting the route somewhere else will disconnect the net from the port, and can also screw up the route layers in the output.
  23. April 8, 2014 at 3:00am
    Prevented a segfault when a pin in the DEF file is not attached to anything else in the netlist.
    Also: Update at Mon Apr 7 15:40:02 EDT 2014 by tim
    Also: Merge branch 'master' into work
  24. May 27, 2014 at 3:00am
    Update at Mon May 26 09:55:11 EDT 2014 by tim
  25. May 28, 2014 at 3:00am
    Update at Tue May 27 19:10:20 EDT 2014 by tim
  26. May 30, 2014 at 3:00am
    Update at Thu May 29 10:52:51 EDT 2014 by tim
  27. May 31, 2014 at 3:00am
    Update at Fri May 30 14:41:25 EDT 2014 by tim
  28. June 1, 2014 at 3:00am
    Update at Sat May 31 14:50:58 EDT 2014 by tim
  29. July 13, 2014 at 3:00am
    Changed the handling of route area masks, moving the position of net trunks into the net record and branch positions into the node records. This will facilitate the initial determination of best potential net placement.
    Also: Update at Sat Jul 12 14:17:42 EDT 2014 by tim
    Also: Merge branch 'master' into work
  30. July 18, 2014 at 3:00am
    Added a catch-all routine for "node has no taps" message. This makes it easier to debug common problems by allowing a single entry point for declaring breaks.
    Also: Update at Thu Jul 17 08:32:38 EDT 2014 by tim
    Also: Merge branch 'master' into work
    Also: Removed files from the build that were not supposed to have been added to the repository.
    Also: Modified the gitignore file so that no extraneous files from the build will end up in the repository.
  31. September 8, 2014 at 3:00am
    Ran "git rm --cached" to prevent config.log and config.status from being tracked in spite of being in the .gitignore file.
    Also: Update at Sun Sep 7 10:16:02 EDT 2014 by tim
    Also: Merge branch 'master' into work
    Also: Applied patches from Ruben Undheim needed for a clean build of the debian package.
  32. September 10, 2014 at 3:00am
    Modified some headers to make them more purely GPL, with authorization from Steve Beccue, whose copyright line was being removed.
    Also: Update at Tue Sep 9 16:21:56 EDT 2014 by tim
    Also: Merge branch 'master' into work
  33. September 13, 2014 at 3:00am
    Applied two patches for things that should have been corrected in the Makefile long ago for portability. Thanks to Ruben Undheim for forwarding the patch files to me.
    Also: Update at Fri Sep 12 17:02:47 EDT 2014 by tim
    Also: Merge branch 'master' into work

Revision information on Qrouter 1.1:

  1. December 24, 2012 at 2:45pm
    First commit of development version 1.1
  2. December 29, 2012 at 3:00am
    Rewrote the stack-contact removal algorithm. New method is not elegant but does the job, more or less. Does not look further than one step away from the solution, so is unable to find solutions requiring additional rerouting.
    Also: Update at Fri Dec 28 11:47:24 EST 2012 by tim
    Also: Merge branch 'master' into work
  3. December 31, 2012 at 3:00am
    Increased PRindMAX, which is now large enough to handle designs that are 8192 x 8192 tracks x 4 layers, although I may try to change this to a type long, move the flags elsewhere, and avoid all potential size limitations.
    Also: Update at Sun Dec 30 12:34:18 EST 2012 by tim
    Also: Merge branch 'master' into work
  4. January 19, 2013 at 3:00am
    Corrected an error where a copy was copying flag bits for the Obs[] vector into the Obs2[] vector, where overlapping bit fields were making the router confuse pin obstructions with source nodes.
    Also: Update at Fri Jan 18 11:27:13 EST 2013 by tim
    Also: Merge branch 'master' into work
  5. March 30, 2013 at 3:00am
    Added the capability to handle upper-level metals with larger spacing and pitch requirements. Added the capability to handle technologies that don't allow arbitrary via stacking. Some preliminary work in route search optimization.
    Also: Update at Fri Mar 29 17:41:50 EDT 2013 by tim
    Also: Merge branch 'master' into work
  6. March 31, 2013 at 3:00am
    Corrected an error with the search order optimization, although it doesn't make a lot of difference because the route order optimization does not speed things up noticeably in this simple form.
    Also: Update at Sat Mar 30 09:24:44 EDT 2013 by tim
    Also: Merge branch 'master' into work
  7. April 9, 2013 at 3:00am
    Reworked the DEF file read-in using a proper parser pulled from magic, which significantly improves the ability of qrouter to read DEF files generated by tools other than the place2def2 tool from the digital flow toolchain on opencircuitdesign.
    Also: Update at Mon Apr 8 09:58:12 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: One correction to replace a cleanup routine that was improperly carried over from magic, which has a different memory allocation scheme (one-delayed).
  8. April 11, 2013 at 3:00am
    Corrected a typo that prevents qrouter from expanding the number of route layers if the input contains more layers than are declared for routing in the config file.
    Also: Update at Wed Apr 10 10:45:21 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Corrected correctly, this time.
    Also: Removed deprecated routines for DEF file reading from qrouter.c. These are superceded by the routines in def.c.
  9. April 12, 2013 at 3:00am
    Corrected output for different scalefactors in the DEF file. Originally it was assumed that the DEF file was written by the open-source digital flow, and was always in centimicrons. Now the UNITS line is parsed for the correct scaling.
    Also: Update at Thu Apr 11 15:22:56 EDT 2013 by tim
    Also: Merge branch 'master' into work
  10. April 13, 2013 at 3:00am
    Corrected an error in stubroute generation that caused some stubroutes to be improperly connected in the DEF file to the previous stubroute.
    Also: Update at Fri Apr 12 17:10:19 EDT 2013 by tim
    Also: Merge branch 'master' into work
  11. April 16, 2013 at 3:00am
    Changed the static allocation of Pr[] into a dynamic one. This prevents all sorts of trouble with the linker and execution on various platforms. Also, put the whole system under autoconf.
    Also: Update at Mon Apr 15 09:40:06 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Changed the README file to give instructions for the autconf compile and install.
  12. April 17, 2013 at 3:00am
    A major code overhaul. Even though dynamic allocation of the Pr[] array fixed compile-time problems, the array is so huge that systems without enough memory just keel over when it runs. Given that earlier changes made the Pr[] array contents reflect the array position of that route point, the only useful information kept in Pr[] was the cost, plus a few flags. So the code was modified to make Obs2[] an array of structures holding a cost (u_int) and flags (u_char), that is, five bytes per point, and it is allocated per layer, not all at once, so unlikely to cause paging errors. Also removed a few unnecessary references to global variables.
    Also: Update at Tue Apr 16 19:12:11 EDT 2013 by tim
    Also: Merge branch 'master' into work
  13. April 18, 2013 at 3:00am
    Corrected an error in the second-stage rip-up and reroute.
    Also: Update at Wed Apr 17 10:00:53 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Another correction to the rip-up and re-route stage. Areas around the perimeter of a port were being ignored during the re-routing stage, leading to a low incidence of successful re-routes.
  14. April 19, 2013 at 3:00am
    Added some additional handling of off-grid terminals, so now most terminals can be reached no matter how badly the placement is aligned to the routing grid.
    Also: Update at Thu Apr 18 19:14:10 EDT 2013 by tim
    Also: Merge branch 'master' into work
  15. April 20, 2013 at 3:00am
    Update for handling terminals that are offset from the route grid.
    Also: Update at Fri Apr 19 13:24:17 EDT 2013 by tim
    Also: Merge branch 'master' into work
  16. April 23, 2013 at 3:00am
    Qrouter additions for handling offset port positions; these are not yet working and were not meant to be checked in, although the new code should not cause any additional problems with the router.
    Also: Update at Mon Apr 22 09:12:33 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Some backtracking on the last set of changes. Reverting to the most recent code that produces correct routes, even if there are a few DRC errors. Will make a second attempt to identify route position offsets at off-grid pins.
  17. April 24, 2013 at 3:00am
    This version eliminates the majority of DRC errors. Still working on an assortment of additional DRC violations.
    Also: Update at Tue Apr 23 12:20:59 EDT 2013 by tim
    Also: Merge branch 'master' into work
  18. April 27, 2013 at 3:00am
    More detailed analysis of port geometry added, to eliminate DRC errors at port connections. Not quite finished yet, but resolves many more DRC errors than before.
    Also: Update at Fri Apr 26 09:32:46 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: More corrections/additions for finding and eliminating DRC errors at terminal points. The list of DRC errors is getting very small. . .
  19. April 30, 2013 at 3:00am
    Latest changes to the router to handle various geometries at a port connection. This set of changes eliminates nearly all DRC errors produced by the detailed route.
    Also: Update at Mon Apr 29 17:45:00 EDT 2013 by tim
    Also: Merge branch 'master' into work
  20. May 1, 2013 at 3:00am
    Added another bit of code to avoid DRC errors generated when two routes on the same net approach to within a short distance of each other from different directions.
    Also: Update at Tue Apr 30 17:51:47 EDT 2013 by tim
    Also: Merge branch 'master' into work
  21. May 2, 2013 at 3:00am
    Continuing to solve all DRC issues; test case is now down to 3 errors in 10000+ routes, all errors of the same type. Last error requires a bit more coding than the others, so I am checking in now before tackling it.
    Also: Update at Wed May 1 15:35:21 EDT 2013 by tim
    Also: Merge branch 'master' into work
  22. May 3, 2013 at 3:00am
    First version of qrouter to finish routing the 3000+ gate, 10000+ routes test circuit with no route errors, no DRC errors, and no stacked contact errors.
    Also: Update at Thu May 2 15:51:08 EDT 2013 by tim
    Also: Merge branch 'master' into work
  23. May 4, 2013 at 3:00am
    Corrected a minor but fatal error in which the routine that sets a node and all its connected routes to "source" or "target" does not process the point of the top connection of a via. This is a rare occurrence, but can happen if a pin or port is declared on a layer above metal1, and there is room on the metal1 route layer below it to connect to the pin by a via down, putting the route endpoint at the top of the via.
    Also: Update at Fri May 3 12:25:10 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Correction to minor typo in last update.
  24. May 8, 2013 at 3:00am
    Major code overhaul: simplified internal structures, putting the route information under the net instead of the node, and removing the independent list of nodes in favor of having nodes listed only under their assigned nets. Added code to read in the geometry of existing routed nets from a DEF file, so that qrouter can start from a partially-routed solution. "Fixed" or "cover" nets, as well as nets in the "specialnets" section, are treated as obstructions.
    Also: Update at Tue May 7 16:17:34 EDT 2013 by tim
    Also: Merge branch 'master' into work
  25. May 9, 2013 at 3:00am
    Additional code to handle routing of pins directly to power and ground. Note that this does not connect together rows of power busses; it just finds the nearest bus and connects to it from any pin that is marked as connecting to power or ground.
    Also: Update at Wed May 8 19:44:21 EDT 2013 by tim
    Also: Merge branch 'master' into work
  26. May 10, 2013 at 3:00am
    Corrected an error that would overwrite array bounds if the physical Y lower bound of the array was less than zero.
    Also: Update at Thu May 9 15:44:57 EDT 2013 by tim
    Also: Merge branch 'master' into work
  27. May 11, 2013 at 3:00am
    Corrected an error in the recently added power/ground route handling, that fails to route the last connection.
    Also: Update at Fri May 10 14:05:57 EDT 2013 by tim
    Also: Merge branch 'master' into work
  28. May 17, 2013 at 3:00am
    Correction of a bug referencing an uninitialized variable.
    Also: Update at Thu May 16 10:52:54 EDT 2013 by tim
    Also: Merge branch 'master' into work
  29. May 25, 2013 at 3:00am
    Corrected an error in which obstructions from a single direction would be specified by a tap position offset but fail to mark the point with the node number, making the tap point unroutable. Corrected another error in which the track offset was incorrectly read from the DIEAREA lower corner rather than from the TRACKS statement.
    Also: Update at Fri May 24 11:04:53 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Corrected another error that would prevent qrouter from seeing that it had already completed a route, if that route was forced to connect to the tap to avoid an irrational blocking obstruction.
  30. May 29, 2013 at 3:00am
    Corrected another couple of places where set_node_to_net would succeed on an unroutable terminal and cause an infinite loop.
    Also: Update at Tue May 28 14:24:50 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Changed a diagnostic message to be printed only if "verbose" mode is set.
  31. May 30, 2013 at 3:00am
    Corrected yet another instance where an obstructed tap would put qrouter into an infinite loop.
    Also: Update at Wed May 29 18:04:29 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Fixed an issue with qrouter where it would always pick up spacing from a RANGE statement if it came last, and therefore assume worst-case spacing always. The fix reverts to the intended behavior of ignoring worst-case spacing, which is a limitation that will one day need to be addressed.
  32. May 31, 2013 at 3:00am
    Correction to yesterday's update; improper to call LefEndStatement() if the semicolon ending the statement has already been read. LEF parser had been fixed for SPACING statements with a RANGE component but became broken for plain SPACING statements. Fixed now.
    Also: Update at Thu May 30 17:54:19 EDT 2013 by tim
    Also: Merge branch 'master' into work
  33. June 1, 2013 at 3:00am
    Found that the last patch showed up a previously hidden DRC violating condition where an offset on one tap to avoid an obstruction creates a spacing violation with a tap on the other side. Added a completely new set of checks for this one condition, because it is difficult to integrate into create_obstructions_from_nodes(). Also, found an incorrect calculation for how much a via should be offset in addition to the calculated offset, to prevent a DRC error. The original caculation was 2x too large, sometimes leading to a DRC spacing violation on the other side.
    Also: Update at Fri May 31 17:26:45 EDT 2013 by tim
    Also: Merge branch 'master' into work
  34. July 31, 2013 at 3:00am
    Corrected an issue where power net positions would be ignored unless they were routable with no offsets or other hazards.
    Also: Update at Tue Jul 30 10:11:12 EDT 2013 by tim
    Also: Merge branch 'master' into work
  35. August 21, 2013 at 3:00am
    Modified handling of stacked contacts to fail a route rather than accept it if a solution cannot be found that avoids stacking contacts beyond what is specified as allowable. In stage 2, a stacked contact solution will always be found, by overrouting existing nets and moving those nets to the rip-up list.
    Also: Update at Tue Aug 20 17:46:26 EDT 2013 by tim
    Also: Merge branch 'master' into work
  36. August 22, 2013 at 3:00am
    Corrected a segfault error in the second stage routing, and relaxed the conditions for abandoning the second stage routing, which were too restrictive (and still may need to be revisited).
    Also: Update at Wed Aug 21 09:34:16 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Corrected an error in which a rare set of conditions involving a via as the initial route segment connecting to a pin by only a stub route would not output the stub route, causing the pin to be disconnected in the final output.
  37. August 26, 2013 at 3:00am
    Small change to ensure that the "-i " result does not print null lines, if the number of layers defined in the .cfg file is erroneously larger than the number of layers defined by the LEF file.
    Also: Update at Sun Aug 25 14:16:50 EDT 2013 by tim
    Also: Merge branch 'master' into work
  38. August 30, 2013 at 3:00am
    A number of modifications and updates, dealing with round-off errors and handling more geometry cases for checking DRC interactions.
    Also: Update at Thu Aug 29 13:41:40 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Correction for cases involving (in particular) terminals on metal2, where the obstruction generator looks at a point over a terminal, and seeing that it has a valid node, decides not to block it, ignoring the fact that it is the same node, not a different one.
  39. August 31, 2013 at 3:00am
    Finished corrections and additions to DRC error detection and handling, especially for terminals on metals above the lowest layer.
    Also: Update at Fri Aug 30 17:34:04 EDT 2013 by tim
    Also: Merge branch 'master' into work
  40. September 2, 2013 at 3:00am
    Some experimenting with ways to get around problems caused by failure to avoid a stacked via. There is something wrong here, and I have not found it yet.
    Also: Update at Sun Sep 1 19:52:50 EDT 2013 by tim
    Also: Merge branch 'master' into work
  41. September 8, 2013 at 3:00am
    Added a switch to prevent qrouter from giving up. . . qrouter is abandoning routing attempts too early, and it needs a better metric for determining when it is stuck.
    Also: Update at Sat Sep 7 14:37:01 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Changed the output of "qrouter -h" to provide the entire x.y.z version number; this will allow qflow to detect the version number and file a complaint if it needs a qrouter version number higher than the one installed.
    Also: Correction to the LEF read routine to properly parse quoted material.
  42. September 10, 2013 at 3:00am
    Added code that adjusts via position by an offset if vias on adjacent routing tracks are close enough together to cause a DRC spacing rule violation. This also covers via-to-metal spacing violations.
    Also: Update at Mon Sep 9 16:29:57 EDT 2013 by tim
    Also: Merge branch 'master' into work
  43. September 11, 2013 at 3:00am
    Corrected an error where an unroutable tap position under a metal layer would remain unmarked as source or dest, causing qrouter to infinite loop trying to route to it.
    Also: Update at Tue Sep 10 16:18:32 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Corrected an error that can prevent a local power supply network (e.g., vdd or gnd) from being connected to the global power supply, if all the local pins get connected together first.
    Also: A correction to the correction for power and ground connections to buses. The original correction simply didn't work right. This commit has been tested and confirmed working.
    Also: Corrected a coding error in maze.c; variable "i" copied up from another section and not replaced, so it was being used uninitialized.
  44. September 12, 2013 at 3:00am
    Corrected an error in reading pre-routed layers that would crash on and invalid pointer.
    Also: Update at Wed Sep 11 08:09:44 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Added additional handling to parse SPACING ... RANGE lines from a technology LEF file, and handle the extra wide-spacing requirements. This is not thorough, because it only looks at one obstruction rectangle at a time, so can miss additional widths caused by concatenating geometry.
  45. September 13, 2013 at 3:00am
    Corrected an error in which, where the last change introduced via offsets to avoid via-to-via DRC errors, the code reacts to points on double-spaced tracks (e.g., metal4 on osu035) that have been dynamically obstructed by setting NO_NET along with ROUTED_NET. Also: Introduced a command-line switch "-r " that sets the resolution of the output. "-r 1" is default, and routed points are always integer (scale is always centimicrons). "-r 2" yields twice the resolution, so output may be in units of 5 nanometers (scale is still in centimicrons, so values are 1/2-integer).
    Also: Update at Thu Sep 12 13:14:42 EDT 2013 by tim
    Also: Merge branch 'master' into work
  46. September 14, 2013 at 3:00am
    Added an experimental switch to force a route point on a node that fails due to having no valid tap points.
    Also: Update at Fri Sep 13 20:43:46 EDT 2013 by tim
    Also: Merge branch 'master' into work
  47. September 16, 2013 at 3:00am
    Modified via placement so that it follows a checkerboard pattern of X, Y when the metal rectangles forming the via are not square. This appears to be the way to deal with tight pitches in some processes with metal overhang requirements on vias.
    Also: Update at Sun Sep 15 16:25:35 EDT 2013 by tim
    Also: Merge branch 'master' into work
    Also: Slight change to the previous addition, to require a line in the config file before using the patterned vias.
  48. September 17, 2013 at 3:00am
    Fixed a couple of minor format errors in config.c
    Also: Update at Mon Sep 16 20:29:45 EDT 2013 by tim
    Also: Merge branch 'master' into work
  49. September 24, 2013 at 3:00am
    Update at Mon Sep 23 22:18:33 EDT 2013 by tim
  50. November 7, 2013 at 3:00am
    Corrected missing initialization values for the LEF macro read-in. Likely to cause crashes on systems that do not explicitly zero memory on malloc().
    Also: Update at Wed Nov 6 14:25:49 EST 2013 by tim
    Also: Merge branch 'master' into work
  51. May 27, 2014 at 3:00am
    Update at Mon May 26 09:55:10 EDT 2014 by tim
  52. May 28, 2014 at 3:00am
    Update at Tue May 27 19:10:20 EDT 2014 by tim
  53. May 30, 2014 at 3:00am
    Update at Thu May 29 10:52:50 EDT 2014 by tim
  54. May 31, 2014 at 3:00am
    Update at Fri May 30 14:41:24 EDT 2014 by tim
  55. June 1, 2014 at 3:00am
    Update at Sat May 31 14:50:57 EDT 2014 by tim

Revision information on Qrouter 1.0:

  1. Thursday, June 16, 2011
    This is a first draft.
  2. June 17, 2011 at 6:14am
    Added "make distclean" to the makefile.
  3. June 18, 2011 at 2:40am
    Corrected the stub routing, which was being applied only to the start of a route but not the end.
    Also: Added the .gitignore file to avoid committing modifications to object and executable files.
    Also: Corrected the configuration file so that the LEF filename is case-sensitive. Also modified the parser so that initial whitespace is ignored.
  4. June 20, 2011 at 2:40am
    Added the ability to specify extra obstruction areas in the configuration file.
    Also: Update at Sun Jun 19 10:32:07 PDT 2011 by tim
    Also: Merge branch 'master' into work
  5. June 21, 2011 at 2:40am
    Corrected stub routing, which was missing a terminating path point.
    Also: Update at Mon Jun 20 07:47:13 PDT 2011 by tim
    Also: Merge branch 'master' into work
    Also: Changed the code so that no warning is generated on any power/ ground node following the convention "vdd*", "gnd*", or "vss*".
    Also: Update at Mon Jun 20 12:55:01 PDT 2011 by tim
    Also: Merge branch 'master' into work
    Also: Corrected a few segfaults related to having bad route tracks that completely disallow access to one or more nodes.
    Also: Made a alternate invocation of "qrouter -i " that will read the configuration file, print information about the route layers to the given filename, then exit. This is useful for preprocessing scripts to get the route layer information without having to parse the LEF file themselves.
  6. June 22, 2011 at 2:40am
    Modified qrouter to reduce the maximum cost for the first pass to be much lower than before. Otherwise, very large designs take forever to route.
    Also: Update at Tue Jun 21 06:46:10 PDT 2011 by tim
    Also: Merge branch 'master' into work
    Also: Trivial change to prevent the config file reader from claiming, incorrectly, that it has not understood the "obstruction" lines.
  7. June 23, 2011 at 2:40am
    Corrected the loop over maxcost. The algorithm now shuffles points that exceed the maximum cost onto a separate stack, so that if no route is found less than the first maximum cost setpoint, the algorithm can pick up on the next pass from where it left off, with no overhead. Algorithm just successfully routed the vast majority of a large design with > 3000 components and > 3000 nets, and is now ready for implementation of a rip-up and re-route algorithm.
    Also: Update at Wed Jun 22 11:56:46 PDT 2011 by tim
    Also: Merge branch 'master' into work
    Also: Fixed on segfault on verbose output, and one potential infinite loop situation. Still there is an infinite loop situation in the code, which should be fixed in the next update.
  8. June 24, 2011 at 2:40am
    Found and fixed an error where a grid location close to a pin could overwrite an existing node location of another pin on another cell, not only erasing that pin, but causing the nets of the two pins to become confused, ending up with a infinite loop situation.
    Also: Update at Thu Jun 23 07:15:35 PDT 2011 by tim
    Also: Merge branch 'master' into work
    Also: Corrected a few more errors related to pins on higher-level metals whose extended pin positions were allowed to exist over top, and to block, other nearby pins on lower metal layers.
    Also: More corrections to the same problem.
    Also: Corrected an error that was causing all stub route paths to be eliminated from the routing. Current version draws stub routes but the code to write the stub routes again as specialnets using a wider route width needs fixing.
    Also: And, as promised, corrections to the specialnets section for wide stub routes. Result now routes well on all examples, with no crashes or hangs.
  9. July 5, 2011 at 2:40am
    Completed the second-stage routing algorithm for rip-up and re-route of nets that were not routed in the first stage.
    Also: Update at Mon Jul 4 06:32:49 PDT 2011 by tim
    Also: Merge branch 'master' into work
    Also: Correction to a bad typo in the code.
    Also: And this time, fixing it the right way. . .
  10. July 6, 2011 at 2:40am
    Corrected a badly-thought-out procedure that bypasses the anti-looping check and therefore allows infinite loops.
    Also: Update at Tue Jul 5 13:53:50 PDT 2011 by tim
    Also: Merge branch 'master' into work
  11. October 21, 2011 at 3:00am
    Minor fix to the header file submitted by Niels Moseley.
    Also: Update at Thu Oct 20 12:58:10 PDT 2011 by tim
    Also: Merge branch 'master' into work
  12. September 10, 2012 at 3:00am
    Update at Sun Sep 9 15:44:11 EDT 2012 by tim
  13. November 16, 2012 at 3:00am
    Update at Tue Mar 6 12:30:35 PST 2012 by tim
    Also: Merge branch 'master' into work
    Also: Corrected an error which allowed vias defined with MASTERSLICE layers to issue a warning but then default to a layer number of zero, effectively making them metal1 contacts. Now, the warning is issued but the contact geometry is kept, along with the negative layer number, preventing it from being incorrectly parsed later on.
    Also: Update at Thu Nov 15 12:32:30 EST 2012 by tim
    Also: Merge branch 'master' into work
    Also: Another correction for the same purpose of correcting via read-in from a LEF file.
    Also: More corrections, with incorrect offset calculations when cells have a non-zero origin, and offset needed to be added to all of the layer geometry.
    Also: More fixes, these to account for pins that are between two route grid lines such that routes can only reach the pin from an "extended" area grid point (from which a stub route takes it to the pin).
  14. December 7, 2012 at 3:00am
    Added track offset to the information dumped by qrouter for use by the placement-to-DEF file conversion. The track offset gives the distance from a cell origin to the first routing track. Previously, an offset of 1/2 pitch was used. This is still the default value.
    Also: Update at Thu Dec 6 11:12:38 EST 2012 by tim
    Also: Merge branch 'master' into work
    Also: Also added route width to the mixture, so as not to force it to be the same as route pitch.
  15. December 21, 2012 at 3:00am
    An edit for testing caused the file to be marked as changed, but no changes were made.
    Also: Update at Thu Dec 20 17:14:33 EST 2012 by tim
    Also: Merge branch 'master' into work
  16. December 22, 2012 at 3:00am
    Implemented a configuration option "no stacked contacts" that will prevent the router from generating paths with stacked contacts. This is a very simple implementation that merely prevents moving between three layers at the same grid point. It does not consider the possibility that contacts can be staggered by placing them between grid points. There should be more refined options. . .
    Also: Update at Fri Dec 21 10:04:07 EST 2012 by tim
    Also: Merge branch 'master' into work
  17. December 24, 2012 at 3:00am
    Changes reverted, no significant code changes in this revision.
    Also: Update at Sun Dec 23 17:08:38 EST 2012 by tim
    Also: Merge branch 'master' into work
  18. April 9, 2013 at 3:00am
    Corrected an error that caused some stubroutes to write the first path as "NEW ..." rather than "+ ROUTED ...", resulting in illegal syntax in the DEF output file.
    Also: Update at Mon Apr 8 09:55:32 EDT 2013 by tim
    Also: Merge branch 'master' into work
  19. May 4, 2013 at 3:00am
    Correction to minor typo in last update.
    Also: Update at Fri May 3 12:36:04 EDT 2013 by tim
    Also: Merge branch 'master' into work
  20. September 24, 2013 at 3:00am
    Update at Mon Sep 23 22:18:33 EDT 2013 by tim

email:

Last updated: July 13, 2017 at 3:00am