Labyrinth
A global router and routing development tool
Ryan Kastner Majid Sarrafzadeh
Introduction
Global router:
The global router is based on maze routing. It was created by Ryan Kastner 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.
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.
Features
- 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)
Documentation
Errata
pop_front dynamic memory bug,
abs-stdlib bug - thanks to William Hung for
pointing these out
Known Limitations
- 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.
Download Labyrinth
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.
Related links
References
[1] 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)
[2] 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)
[3] Ryan Kastner, Elaheh
Bozorgzadeh and Majid Sarrafzadeh, "Coupling Aware Routing",
International
ASIC/SOC Conference, September 2000 (pdf,
slides)
[4] Ryan Kastner, Elaheh
Bozorgzadeh and Majid Sarrafzadeh, "Predictable Routing", International
Conference on Computer-Aided Design (ICCAD), November 2000 (pdf,
slides)
[5] Ryan Kastner, Elaheh
Bozorgzadeh and Majid Sarrafzadeh, "An Exact Algorithm for
Coupling-Free Routing",
International Symposium on Physical Design (ISPD), April 2001 (pdf,
slides)
[6] Ryan
Kastner, “Methods and Algorithms for Coupling
Reduction", MS Thesis, Department
of Electrical and Computer Engineering, Northwestern University,
Evanston, IL,
August 2000 (pdf)<>