-
Notifications
You must be signed in to change notification settings - Fork 31
Grid Routing
In this project, you will implement a collection of 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.
You are expected to implement two versions of each grid routing algorithm:
- No intersections are allowed between routed nets.
- Unlimited intersections are allowed between routed nets (although nets may intersect at crosspoints, two nets are not allowed to route on top of one another).
For any given algorithm, the code for both versions should be similar, and maximizing code sharing (within reason) for each version is expected.
All of the algorithms to be implemented in this project route one net at a time. The results obtained are highly sensitive to the order in which nets are routed. Some algorithms attempt to select intelligent orderings of nets; others do not. If the algorithm does not explicitly state how a net ordering is computed, the nets should be routed in the order that they are specified in the input file to the framework.
- Implement the base Lee’s Algorithm [1].
- Implement the 2- and 3-bit route encoding schemes for Lee’s Algorithm described by Akers [2].
- Implement the enhancement described by Ruben [3] to minimize the number of turns in each path.
- Implement Ruben’s strategy to always expand the cell most recently added to the wavefront in regions with no blockages among cells with equal costs [3].
- Implement Ruben’s path-cost function to direct the search [3].
- Implement Korn’s path-cost function [4].
The submitted solution should be parameterizable, so that the user can optionally turn on the enhancements described in Steps 1 and 2, and switch between the Lee, Ruben, and Korn path-cost function. The user should also be able to specify an “overpull” parameter for Korn’s cost function as a double.
Optional: Implement the landmark-based cost function described by Goldberg and Harrison [5], including the landmark selection algorithm.
- Implement Hadlock’s Algorithm [6]
The implementation should include the enhancements from Steps 1 and 2 from Mini-project #2, if at all possible.
Add bi-directional search capabilities (as described by Pohl [7]) to all previously-implemented algorithms.
[1] C.Y. Lee: An Algorithm for Path Connections and its Applications. IRE Transactions on Electronic Computers EC-10: 346-365 (1961)
[2] Sheldon B. Akers Jr.: A Modification of Lee’s Path Connection Algorithm. IEEE Transactions on Electronic Computers EC-16(1): 97-98 (1967)
[3] Frank Rubin: The Lee Path Connection Algorithm. IEEE Transactions on Computers C-23(9): 907-914 (1974)
[4] Robert K. Korn: An efficient variable-cost maze router. DAC 1982: 425-431
[5] Andrew V. Goldberg, Chris Harrelson: Computing the shortest path: A search meets graph theory. SODA 2005: 156-165
[6] F. O. Hadlock: A shortest path algorithm for grid graphs", Networks 7(4): 323-334 (1977)
- This reference does not appear to be available online and is not available in UCR’s library.
[7] Ira Pohl: Bi-directional Search, in Meltzer, Bernard; Michie, Donald, Machine Intelligence 6, Edingburgh University Press: 127-140 (1971)
A website illustrating Lee’s Algorithm: http://workbench.lafayette.edu/~nestorj/cadapplets/MazeRouter.html
A website illustrating Lee’s Algorithm with an A* Cost Function (Ruben’s): http://workbench.lafayette.edu/~nestorj/cadapplets/AStarRouter/AStarRouter.html
A website illustrating Hadlock’s Algorithm: http://workbench.lafayette.edu/~nestorj/cadapplets/HadlockRouter/HadlockRouter.html