Escape Routing Algorithms
Escape Routing Algorithms
This page summarizes the escape algorithms that have been implemented and integrated into the framework, and cites the papers that describe them in detail. Escape routing is an integral part of Printed Circuit Board (PCB) design. Underneath the DMFB, the escape router determines the path of the wire that delivers electrical signals from each control pins to all of the electrodes that it drives. As control pins have not yet been placed, it suffices for the route to "escape" to any position on the perimeter of the chip.
Examples of 1- and 2-layer escape routing solutions are shown below.
The process of escape routing for a single pin group proceeds iteratively; an example is shown below. The first step is to find a route from any point on the perimeter of the DMFB to an electrode that is part of the group. From there, the search proceeds from the current route, until one-by-one, electrodes belonging to that pin group are discovered.
Lee's Algorithm with Rip-up and Re-Route
A simple and straightforward escape router can be build using Lee's Algorithm, which can be viewed as a breadth-first search on a 2D grid. The solution can be improved by a Rip-up and Re-route post-processing step.
We used this approach as a baseline for comparison in the following two papers:
J. McDaniel, Z. Zimmerman, D. Grissom, and P. Brisk
PCB Escape Routing and Layer Minimization for Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
36(1):69-82, January, 2017
Paper
J. McDaniel, D. Grissom, and P. Brisk
Multi-terminal PCB Escape Routing for Digital Microfluidic Biochips using Negotiated Congestion
22nd IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)
Playa Del Carmen, Mexico, October 6-8, 2014, pp. 219-224
Paper Slides
We adapted our implementation from the following paper, which limited the escape route to a single PCB layer; our implementation, in contrast, allows multi-layer PCB designs with the objective of minimizing the number of PCB layers.
S-H. Yeh, J-W. Chang, T-W. Huang, S-T. Yu, and T-Y. Ho,
Voltage-aware Chip-level Design for Reliability-driven Pin-constrained EWOD Chips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
33(9):1302-1315, September, 2014
Lee's Algorithm was introduced in the following paper:
C. Y. Lee
An Algorithm for Path Connections and Its Applications
IRE Transactions on Electronic Computers
EC-10(2):346-365, 1961.
Layer Negotiated Congestion (LNC)
Negotiated Congestion is an iterative routing technique that has achieved particular notable success in routing for FPGAs. Layer Negotiated Congestion (LNC) is an adaptation which partitions the nets to be routed across multiple PCB layers, and then routes each layer using negotiated congestion.
We introduced and evaluated LNC in the following papers:
J. McDaniel, Z. Zimmerman, D. Grissom, and P. Brisk
PCB Escape Routing and Layer Minimization for Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
36(1):69-82, January, 2017
Paper
J. McDaniel, D. Grissom, and P. Brisk
Multi-terminal PCB Escape Routing for Digital Microfluidic Biochips using Negotiated Congestion
22nd IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)
Playa Del Carmen, Mexico, October 6-8, 2014, pp. 219-224
Paper Slides
Negotiated congestion was introduced, modified, and applied to the FPGA domain in the following papers:
L. McMurchie and C. Ebeling
PathFinder: A Negotiation-based Performance-driver Router for FPGAs
International Symposium on Field Programmable Gate Arrays (FPGA)
Monterey, CA, USA, February 12-14, 1995, pp. 111-117
R. Nair
A Simple Yet Effective Technique for Global Wiring
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
6(2):165-172, February, 2017
F. Rubin
The Lee Path Connection Algorithm
IEEE Transactions on Computers
C-23(9):907-914, September, 1974
Layer Minimized Negotiated Congestion (LMNC)
Layer Minimized Negotiated Congestion (LMNC) is an enhancement to LNC that relaxes the pin groupings, thereby increasing the number of control pins, when doing so is likely to reduce the total number of PCB layers.
We introduced and evaluated LMNC in the following papers:
J. McDaniel, Z. Zimmerman, D. Grissom, and P. Brisk
PCB Escape Routing and Layer Minimization for Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
36(1):69-82, January, 2017
Paper
J. McDaniel, D. Grissom, and P. Brisk
Multi-terminal PCB Escape Routing for Digital Microfluidic Biochips using Negotiated Congestion
22nd IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)
Playa Del Carmen, Mexico, October 6-8, 2014, pp. 219-224
Paper Slides
Integrating Pin Mapping with Escape Routing
Several papers in recent years have co-optimized DMFB pin mapping with escape routing, effectively calling the escape router as a sub-routine.These algorithms are distinct from those that perform pin mapping upfront, followed by escape routing as a post-processing step. We implemented one of these algorithms in our framework and generalized it to be compatible with multi-layer escape routing, and to be able to call any of the three escape routers described above as a sub-routine.
These integrated pin mapper and escape router is summarized in the following papers:
J. McDaniel, Z. Zimmerman, D. Grissom, and P. Brisk
PCB Escape Routing and Layer Minimization for Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
36(1):69-82, January, 2017
Paper
J. McDaniel, D. Grissom, and P. Brisk
Multi-terminal PCB Escape Routing for Digital Microfluidic Biochips using Negotiated Congestion
22nd IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)
Playa Del Carmen, Mexico, October 6-8, 2014, pp. 219-224
Paper Slides
The following paper describes the integrated pin mapper and escape router which forms the basis of our implementation.
S-T. Yu, S-H. Yeh, and T-Y. Ho
Reliability-driven Chip-level Design for High Frequency Digital Microfluidic Biochips
International Symposium on Physical Design (ISPD)
Petaluma, CA, USA, March 30 - April 2, 2014, pp. 133-140
Contact
Please direct any questions, comments, or other inquiries to the following e-mail address: microfluidics@cs.ucr.edu
Acknowledgment
This material is based upon work supported by the National Science Foundation under Grant Numbers 1035603, 1536026, and 1545097. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.