Steiner Tree Routing

In this project, the student will implement an advanced grid routing algorithm 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.

In this project, the student will implement an algorithm for flow channel routing and layout as described in Ref. [1]. This algorithm will be implemented into a larger physical design flow for continuous fluid flow microfluidics. The architecture of the chip to be laid out will be represented as a graph, similar to the way semiconductor CAD flows represent integrated circuits.

Prior to routing, fluidic components in the circuit will be placed, i.e., their locations in a 2-dimensional plane will be selected. Brian (and others) have already implemented two placement algorithms which the student can use for testing purposes.

After placement, flow channel routing instantiates connections between components, which facilitate the transfer of fluid. These routing instances must also be embedded in the 2D plane; although fluid routing channels may intersect one another, it is generally a good idea to try to minimize the number of intersections (although that is not specifically the goal of the flow channel routing algorithm described in Ref. [1]).

The student will implement the fluid channel routing algorithm described in Ref. [1] in the framework. The algorithm should be compatible with any (correctly implemented) placer, and will be implemented as a standalone software module using the standard interfaces that are already present in the framework. The student should consult with Brian to obtain a copy of the framework software and for instructions regarding the flow channel router interface.

The flow channel routing algorithm is rather complicated, as it makes use of sub-routines that are described in seven other papers (Refs. [2]-[8]). An overview of the complete algorithm (including references to the papers that describe specific steps) is as follows:

Project Breakdown

Flow Channel Routing Algorithm [1]

1. Compute Obstacle-avoiding Voronoi Graph (OAVG) [2] 1.1 Construct Shortest Path Map (SPM) [3] or [4] [3] gives an O(nlogn) algorithm, where n is the number of vertices in the plane [4] gives an O(n + hlogh) algorithm where h is the number of polygons 1.2 Generate vertices [2] 1.3 Edge connection [2]

2. Construct Initial Shortest Path Components (SPCs) [5]

3. Use Kruskals spanning tree algorithm to construct an initial tree to connect pin-vertices. [1]

4. U-shaped pattern refinement [6, Section III.D.3)]

5. H-shaped pattern refinement [2] (with implementation details taken from [7, Section 3.4] and [8])

References:

[1] Chun-Xun Lin, Chih-Hung Liu, I.-Che Chen, D. T. Lee, Tsung-Yi Ho: An Efficient Bi-criteria Flow Channel Routing Algorithm For Flow-based Microfluidic Biochips. DAC 2014: 1-6 [2] Chih-Hung Liu, Shih-Yi Yuan, Sy-Yen Kuo, Jung-Hung Weng: Obstacle-avoiding rectilinear Steiner tree construction based on Steiner point selection. ICCAD 2009: 26-32 [3] Joseph S. B. Mitchell: L_1 Shortest Paths Among Polygonal Obstacles in the Plane. Algorithmica 8(1): 55-88 (1992) [4] Danny Z. Chen, Haitao Wang: L_1 Shortest Path Queries among Polygonal Obstacles in the Plane. STACS 2013: 293-304 [5] K. Mehlhorn, “A faster approximation algorithm for the Steiner problem in Graphs," Inf. Proc Let., vol. 27, pp. 125-128, 1988 [6] Chung-Wei Lin, Szu-Yu Chen, Chi-Feng Li, Yao-Wen Chang, Chia-Lin Yang: Obstacle-Avoiding Rectilinear Steiner Tree Construction Based on Spanning Graphs. IEEE Trans. on CAD of Integrated Circuits and Systems 27(4): 643-653 (2008) [7] Chih-Hung Liu, Shih-Yi Yuan, Sy-Yen Kuo, Yao-Hsin Chou: An O(n log n) path-based obstacle-avoiding algorithm for rectilinear Steiner tree construction. DAC 2009: 314-319 [8] Bernard Chazelle: An Algorithm for Segment-Dragging and Its Implementation. Algorithmica 3: 205-221 (1988)