Labyrinth

A global router and routing development tool
Ryan Kastner Majid Sarrafzadeh

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)
  

• Input format
• Box
• CoupleFree
• Maze
• Net
• Pin
• Point
• PrimMST
• RouteEdge
• RouteTracks
• Segment

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

• GSRC bookshelf Grid-Based Global and Detailed Routing slot
• ER group - Majid Sarrafzadeh's research group at UCLA
• ExPRESS group - Ryan Kastner's reseach group at UCSB
  

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)<>