TY - GEN
T1 - A SAT-based routing algorithm for cross-referencing biochips
AU - Yuh, Ping Hung
AU - Lin, Cliff Chiung Yu
AU - Huang, Tsung Wei
AU - Ho, Tsung Yi
AU - Yang, Chia Lin
AU - Chang, Yao Wen
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84863152988&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84863152988&partnerID=8YFLogxK
U2 - 10.1109/SLIP.2011.6135436
DO - 10.1109/SLIP.2011.6135436
M3 - Conference contribution
AN - SCOPUS:84863152988
SN - 9781457712401
T3 - International Workshop on System Level Interconnect Prediction, SLIP
BT - 2011 13th International Workshop on System Level Interconnect Prediction, SLIP 2011
T2 - 2011 13th International Workshop on System Level Interconnect Prediction, SLIP 2011
Y2 - 5 June 2011 through 5 June 2011
ER -