Advanced Grid Routing

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.

Rubin [1] described an algorithmic paradigm for routing multiple nets called iterative congestion (IC). IC repeatedly calls a grid routing algorithm on a weighted graph and allows sharing of grid routing resources between nets. After each iteration completes, all nets are ripped up and the grid weights are increased in congested areas to penalize the use of resources with a history of congestion. A subsequent iteration re-routes all of the nets on a grid graph with updated weights. The algorithm terminates successfully when it finds a routing solution having at most K intersection points; it fails if it is unable to find a solution after a user-specified number of iterations.

Soukup [2] described an algorithm that tries to route using depth-first search, but switches to breadth-first search to get around obstacles. For any given net, Soukup’s routing algorithm is guaranteed to find a path, if one exists, however, it does not guarantee to find the shortest (optimal) path. As Soukup’s algorithm switches between breadth- and depth-first search, dealing with multiple cascading failures of breadth-first searches to escape obstacles can be an formidable challenge.

Project Breakdown

Part #1

Implement Rubin’s iterative congestion algorithm [1].

Part #2

Implement Soukup’s routing algorithm [2].

References

[1] F. Rubin: An iterative technique for printed wire routing. DAC 1974: 308-313

[2] J. Soukup: Fast maze router. DAC 1978: 100-102