A fast Routability- And performance-driven droplet routing algorithm for digital microfluidic biochips

Tsung Wei Huang, Tsung Yi Ho

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

Abstract

As the microfluidic technology advances, the design complexity of digital microfluidic biochips (DMEB) are expected to explode in the near future. One of the most critical challenges for DMFB design is the droplet routing problem, which schedules the movement of each droplet in a time-multiplexed manner. In this paper, we propose a fast routability- and performancedriven droplet router for DMFBs. The main contributions of our work are: (1) a global moving vector analysis for constructing preferred routing tracks to minimize the number of used unit cells; (2) an entropy-based equation to determine the routing order of droplets for better routability; (3) a routing compaction technique by dynamic programming to minimize the latest arrival time of droplets. Experimental results show that our algorithm achieves 100% routing completion for all test cases on three Benchmark Suites while the previous algorithms are not. In addition to routability, compared with the state-of-theart high-performance routing on the Benchmark Suite I [3], the experimental results still show that our algorithm performed better in runtime by 40%, reduced the latest arrival time by 21%, reduced the used unit cells by 10%. Furthermore, experiment results on Benchmark Suite II and III are also very promising. Based on the evaluation of three Benchmark Suites, our algorithm demonstrates the efficiency and robustness of handling complex droplet routing problem over the existing algorithms.

Original languageEnglish (US)
Title of host publication2009 IEEE International Conference on Computer Design, ICCD 2009
Pages445-450
Number of pages6
DOIs
StatePublished - 2009
Event2009 IEEE International Conference on Computer Design, ICCD 2009 - Lake Tahoe, CA, United States
Duration: Oct 4 2009Oct 7 2009

Publication series

NameProceedings - IEEE International Conference on Computer Design: VLSI in Computers and Processors
ISSN (Print)1063-6404

Other

Other2009 IEEE International Conference on Computer Design, ICCD 2009
CountryUnited States
CityLake Tahoe, CA
Period10/4/0910/7/09

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A fast Routability- And performance-driven droplet routing algorithm for digital microfluidic biochips'. Together they form a unique fingerprint.

Cite this