URBER: Ultrafast Rule-Based Escape Routing Method for Large-Scale Sample Delivery Biochips
Jiayi Weng1 Tsung-Yi Ho2 Weiqing Ji1 Peng Liu1 Mengdi Bao1 Hailong Yao1
1Tsinghua University      2National Tsing Hua University


In high-throughput drug screening applications, as manual drug sample delivery is time-consuming and error-prone, there is an urgent need for accurate and efficient drug sample delivery biochip for large-scale microwell arrays. This paper proposes a new microfluidic biochip architecture, where drugs are automatically prepared with different concentration values, and then delivered into multiple microwells. For the large-scale drug sample delivery biochips, the routing of drug sample delivery channels is a very challenging task without effective routing solutions. This paper proposes an ultrafast rule-based escape routing method, called URBER, to address the large-scale routing of drug sample delivery channels, which scales well in both runtime and memory for large problem size. URBER runs very fast because it routes the channels based on a set of pre-defined rules, which avoids the runtime consumed in solution space exploration. All the benchmarks for 30 ≤ N, M ≤ 100 have been tested, where N and M are the number of columns and rows of the terminal array. Among these benchmarks, about ~91.9% are routed with optimal solutions, and the runtime is order of magnitudes faster than the optimal min-cost flow-based methods (speedup is from ~600 to ~340k). Specifically, for all the benchmarks with 3/4 < M/N < 4/3, optimal routing solutions are always obtained. URBER also shows the promise of routing large-scale designs with up to 500k terminals efficiently.

Online Demonstration

Online demonstration can be found at here.


You can download pdf here.

Bibtex Reference
title={URBER: Ultrafast Rule-Based Escape Routing Method for Large-Scale Sample Delivery Biochips},
author={Weng, Jiayi and Ho, Tsung-Yi and Ji, Weiqing and Liu, Peng and Bao, Mengdi and Yao, Hailong},
journal={IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},

Min-Cost Flow result with benchmark 72x13

Max Flow result with benchmark 72x13

URBER result with benchmark 72x13

Video demos

Here is a zip file including these videos with high quality.

Benchmark 30x30:

Benchmark 40x30:

Benchmark 80x20: