An ILP-based obstacle-avoiding routing algorithm for pin-constrained EWOD chips

Jia Wen Chang, Tsung Wei Huang, Tsung Yi Ho

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

Abstract

Electrowetting-on-dielectric (EWOD) chips have become the most popular actuator particularly for droplet-based digital microfluidic (DMF) systems. In order to enable the electrical manipulations, wire routing is a key problem in designing EWOD chips. Unlike traditional very-large-scale-integration (VLSI) routing problems, in addition to routing-path establishment on signal pins, the EWOD-chip routing problem needs to address the issue of signal sharing for pin-count reduction under a practical constraint posed by limited pin-count supply. Moreover, EWOD-chip designs might incur several obstacles in the routing region due to embedded devices for specific fluidic protocols. However, no existing works consider the EWOD-chip routing with obstacles. To remedy this insufficiency, we propose in this paper the first obstacle-avoiding routing algorithm for pin-constrained EWOD chips. Our algorithm, based on effective integer-linear-programming (ILP) formulation as well as efficient routing framework, can achieve high routability with a low design complexity. Experimental results based on real-life chips with obstacles demonstrate the high routability of our obstacle-avoiding routing algorithm for pin-constrained EWOD chips.

Original languageEnglish (US)
Title of host publicationASP-DAC 2012 - 17th Asia and South Pacific Design Automation Conference
Pages67-72
Number of pages6
DOIs
StatePublished - Apr 26 2012
Externally publishedYes
Event17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012 - Sydney, NSW, Australia
Duration: Jan 30 2012Feb 2 2012

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Other

Other17th Asia and South Pacific Design Automation Conference, ASP-DAC 2012
CountryAustralia
CitySydney, NSW
Period1/30/122/2/12

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'An ILP-based obstacle-avoiding routing algorithm for pin-constrained EWOD chips'. Together they form a unique fingerprint.

Cite this