A SAT-based routing algorithm for cross-referencing biochips

Ping Hung Yuh, Cliff Chiung Yu Lin, Tsung Wei Huang, Tsung Yi Ho, Chia Lin Yang, Yao Wen Chang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

CAD problems for microfluidic biochips have recently gained much attention. One critical issue is the droplet routing problem. On cross-referencing biochips, the routing problem requires an efficient way to tackle the complexity of simultaneous droplet routing, scheduling and voltage assignment. In this paper, we present the first SAT based routing algorithm for droplet routing on cross-referencing biochips. The SAT-based technique solves a large problem size much more efficiently than a generic ILP formulation. We adopt a two-stage technique of global routing followed by detailed routing. In global routing, we iteratively route a set of nets that heavily interfere with each other. In detailed routing, we adopt a negotiation based routing algorithm and the droplet routing information obtained in the global routing stage is utilized for routing decision. The experimental results demonstrate the efficiency and effectiveness of the proposed SAT-based routing algorithm on a set of practical bioassays.

Original languageEnglish (US)
Title of host publication2011 13th International Workshop on System Level Interconnect Prediction, SLIP 2011
DOIs
StatePublished - Dec 1 2011
Externally publishedYes
Event2011 13th International Workshop on System Level Interconnect Prediction, SLIP 2011 - San Diego, CA, United States
Duration: Jun 5 2011Jun 5 2011

Publication series

NameInternational Workshop on System Level Interconnect Prediction, SLIP

Other

Other2011 13th International Workshop on System Level Interconnect Prediction, SLIP 2011
Country/TerritoryUnited States
CitySan Diego, CA
Period6/5/116/5/11

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A SAT-based routing algorithm for cross-referencing biochips'. Together they form a unique fingerprint.

Cite this