Title | ||
---|---|---|
URBER: Ultrafast Rule-Based Escape Routing Method for Large-Scale Sample Delivery Biochips |
Abstract | ||
---|---|---|
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 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 even for a very large problem size. URBER runs very fast because it routes channels based on a set of predefined rules, which avoids runtime consumed in solution space exploration. All benchmarks for 30
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\le }~{N}$ </tex-math></inline-formula>
,
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${M} {\le }~100$ </tex-math></inline-formula>
have been tested, where
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${N}$ </tex-math></inline-formula>
and
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${M}$ </tex-math></inline-formula>
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 optimal min-cost flow-based methods (speedup is from ~600 to ~340 k). Specifically, for all benchmarks with (
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${M}/{N}$ </tex-math></inline-formula>
)
<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\in }$ </tex-math></inline-formula>
((3/4), (4/3)), optimal routing solutions are always obtained. URBER also shows promise of routing large-scale designs with up to 500 k terminals efficiently. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1109/TCAD.2018.2883908 | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |
Keywords | Field | DocType |
Routing,Drugs,Generators,Computer architecture,Runtime,Benchmark testing | Row,Rule-based system,Biochip,Computer science,Microfluidics,Communication channel,Real-time computing,Drug Sample,Ultrashort pulse,Distributed computing,Speedup | Journal |
Volume | Issue | ISSN |
39 | 1 | 0278-0070 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jiayi Weng | 1 | 0 | 0.34 |
Tsung-Yi Ho | 2 | 59 | 21.63 |
Weiqing Ji | 3 | 0 | 2.03 |
Peng Liu | 4 | 0 | 0.34 |
Mengdi Bao | 5 | 0 | 0.34 |
Hailong Yao | 6 | 267 | 39.56 |