Soukup's Global Router

In this project, the student will implement two advanced grid routing algorithms in C++. These algorithms will be integrated into a framework for the design of microfluidic chips based on integrated microvalve technology that is under development in Dr. Brisk’s laboratory. Grid routing is implemented as a standalone module within the framework.

The microfluidic chip architecture is represented as a graph called a netlist. Vertices correspond to components (valves, mixers, etc.) and edges (called “nets”) correspond to fluid channels between components. Prior to routing, the microfluidic chip is placed (either algorithmically or by hand). Placement determines the location of each component and each component’s I/O interface ports in the 2D plane. Grid routing is then invoked to establish connections between components, allowing for the transfer of fluid.

This project will focus on advanced planar routing algorithms that include features more complicated than the straightforward breadth/depth first searches that derived from Lee’s algorithm.

Soukup [1] described two global routing algorithms (GR1 and GR2) that try to route all nets at the same time, rather than one-at-a-time. Nets may compete for cells, and even steal cells away from one another during the search process. These algorithms are very creative and competition-oriented, borrowing some concepts and ideas from game theory.

Project Breakdown

In this project, you will implement the GR1 and GR2 algorithms, as described in Ref. [1], using the code and interface provided by Brian Crites. As Ref. [1] is ambiguous in many key respects, especially in terms of how it describes when to switch from GR2 back to GR1, the students are encouraged to use their own intuition and ingenuity to make appropriate implementation decisions.

References

[1] J. Soukup: Global router. DAC 1979: 481-484