Note: This tool is no longer being maintained. If you find any problems, I may be able to help you out, but can’t guarantee anything. It’s been a long time since I’ve looked at this code. I would be happy to post any bug fixes or other comments that may help other people using this tool.
The global router is based on maze routing. It was created by Ryan Kastner many years ago as part of his Master’s Thesis reseach. Labyrinth was developed to evaluate placement results in terms of congestion and wirelength at the global bin level. Also, it was used implement some new routing algorithms (see references). It uses a grid graph as the underlying data structure. For detailed routing, each global bin – sometime referred to as tiles – can be feed to an area router.
Routing development tool
Labyrinth is also a good development tool for evaluating and implementing routing algorithms. The source code is object oriented and has algorithms for maze routing (global or detailed), L and Z shaped two terminal routing and coupling-free routing among other things. There are C++ libraries for specifing points, segments, nets, pins and other data structures used in global routing.
- Extensive rip up and reroute phase
- Online documentation for the source code
- Support for coupling-free routing algorithms
- Support for L and Z shaped routing
- Input files for the MCNC benchmarks and ISPD98/IBM benchmarks
- Java based congestion display (no documentation, sorry)
Labyrinth is “copylefted” under the GNU Free Software license.
Download Labyrinth 1.1 source files. There were some problems with old source when running on gcc newer versions. These source files should compile with g++ 3.2.2 and g++ 2.96. Many thanks to Jurjen Westra for fixes these bugs and providing the new source code.
Download Labyrinth 1.0 source files. Known to work with g++ versions 2.8.1. The classes use the standard c libaries as well as the STL. A compiler that supports both of these should work, but nothing is guaranteed or tested.
Download Labyrinth 1.0 executable files. Platform requirement: Sun SPARC Workstation, Solaris 2.5.1 or later.
Download source documentation in html format.
- Nets are not directional i.e. source and sink pins are not specified.
- The grid graph must be uniform.
- Edge capacity is restricted to a single horizontal value and a single vertical value.
- There is no layer assignment of nets.
Ryan Kastner, Elaheh Bozorgzadeh and Majid Sarrafzadeh, “Pattern Routing: Use and Theory for Increasing Predictability and Avoiding Coupling“, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, July 2002 (pdf)
Elaheh Bozorgzadeh, Ryan Kastner and Majid Sarrafzadeh, “Creating and Exploiting Flexibility in Steiner Trees“,IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, May 2003 (pdf)
Ryan Kastner, “Methods and Algorithms for Coupling Reduction“, MS Thesis, Department of Electrical and Computer Engineering, Northwestern University, Evanston, IL, August 2000 (pdf)