tutorial

A General and Exact Routing Methodology for Digital Microfluidic Biochips

Authors:

Oliver Keszocze,

Krishnendu Chakrabarty,

Rolf DrechslerAuthors Info & Claims

ICCAD '15: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design

Pages 874 - 881

Published: 02 November 2015 Publication History

Abstract

Advances in microfluidic technologies have led to the emergence of Digital Microfluidic Biochips (DMFBs), which are capable of automating laboratory procedures in biochemistry and molecular biology. During the design and use of these devices, droplet routing represents a particularly critical challenge. Here, various design tasks have to be addressed for which, depending on the corresponding scenario, different solutions are available. However, all these developments eventually result in an "inflation" of different design approaches for routing of DMFBs -- many of them addressing a very dedicated routing task only. In this work, we propose a comprehensive routing methodology which (1) provides one (generic) solution capable of addressing a variety of different design tasks, (2) employs a "push-button"-scheme that requires no (manual) composition of partial results, and (3) guarantees minimality e.g., with respect to the number of timesteps or the number of required control pins. Experimental evaluations demonstrate the benefits of the solution, i.e., the applicability for a wide range of design tasks as well as improvements compared to specialized solutions presented in the past.

References

[1]

Tsung-Yi Ho, Jun Zeng, and Krishnendu Chakrabarty. Digital microfluidic biochips: A vision for functional diversity and more than Moore. In Int'l Conf. on CAD, pages 578--585. IEEE Press, 2010.

[2]

MG Pollack, AD Shenderov, and RB Fair. Electrowetting-based actuation of droplets for integrated microfluidics. Lab on a Chip, 2(2):96--101, 2002.

[3]

Cliff Chiung-Yu Lin and Yao-Wen Chang. ILP-Based Pin-Count Aware Design Methodology for Microfluidic Biochips. IEEE Trans. on CAD, 29(9):1315--1327, 2010.

Digital Library

[4]

Tsung-Wei Huang, Jia-Wen Chang, and Tsung-Yi Ho. Integrated Fluidic-Chip Co-Design Methodology for Digital Microfluidic Biochips. In International Symposium on Physical Design, pages 49--56. ACM, 2012.

Digital Library

[5]

Fei Su, William Hwang, and Krishnendu Chakrabarty. Droplet routing in the synthesis of digital microfluidic biochips. In Design, Automation and Test in Europe, volume 1, pages 1--6. IEEE, 2006.

Digital Library

[6]

Ying-Han Chen, Chung-Lun Hsu, Li-Chen Tsai, Tsung-Wei Huang, and Tsung-Yi Ho. A reliability-oriented placement algorithm for reconfigurable digital microfluidic biochips using 3D deferred decision making technique. IEEE TCAD, 32(8):1151--1162, 2013.

Digital Library

[7]

Andrew J Ricketts, Kevin Irick, Narayanan Vijaykrishnan, and Mary Jane Irwin. Priority scheduling in digital microfluidics-based biochips. In DATE, pages 329--334, 2006.

Digital Library

[8]

Oliver Keszocze, Robert Wille, Tsung-Yi Ho, and Rolf Drechsler. Exact One-pass Synthesis of Digital Microfluidic Biochips. In Design Automation Conf., 2014.

Digital Library

[9]

Ping-Hung Yuh, Chia-Lin Yang, and Yao-Wen Chang. BioRoute: A network-flow based routing algorithm for digital microfluidic biochips. In Int'l Conf. on CAD, pages 752--757. IEEE Press, 2007.

[10]

Minsik Cho and David Z Pan. A high-performance droplet routing algorithm for digital microfluidic biochips. IEEE Trans. on CAD, 27(10):1714--1724, 2008.

Digital Library

[11]

Tao Xu and Krishnendu Chakrabarty. Droplet-Trace-Based Array Partitioning and a Pin Assignment Algorithm for the Automated Design of Digital Microfluidic Biochips. In Conference on Hardware/Software Codesign and System Synthesis, pages 112--117. ACM, 2006.

Digital Library

[12]

Tao Xu and Krishnendu Chakrabarty. Broadcast Electrode-Addressing for Pin-Constrained Multi-Functional Digital Microfluidic Biochips. In Design Automation Conf., pages 173--178. ACM, 2008.

Digital Library

[13]

Yang Zhao and Krishnendu Chakrabarty. Simultaneous Optimization of Droplet Routing and Control-Pin Mapping to Electrodes in Digital Microfluidic Biochips. IEEE Trans. on CAD, 31(2):242--254, 2012.

Digital Library

[14]

Tsung-Wei Huang and Tsung-Yi Ho. A Two-Stage ILP-Based Droplet Routing Algorithm for Pin-Constrained Digital Microfluidic Biochips. In International Symposium on Physical Design, pages 201--208. ACM, 2010.

Digital Library

[15]

Zhishan Hua, Jeremy L. Rouse, Allen E. Eckhardt, Vijay Srinivasan, Vamsee K. Pamula, Wiley A. Schell, Jonathan L. Benton, Thomas G. Mitchell, and Michael G. Pollack. Multiplexed Real-Time Polymerase Chain Reaction on a Digital Microfluidic Platform. Analytical Chemistry, 82(6):2310--2316, 2010. 20151681.

[16]

Ramakrishna Sista, Zhishan Hua, Prasanna Thwar, Arjun Sudarsan, Vijay Srinivasan, Allen Eckhardt, Michael Pollack, and Vamsee Pamula. Development of a digital microfluidic platform for point of care testing. Lab on a Chip, 8(12):2091--2104, 2008.

[17]

Tsung-Wei Huang and Tsung-Yi Ho. A fast routability- and performance-driven droplet routing algorithm for digital microfluidic biochips. In Int'l Conf. on Comp. Design, pages 445--450. IEEE, 2009.

Digital Library

[18]

Ping-Hung Yuh, Sachin Sapatnekar, Chia-Lin Yang, and Yao-Wen Chang. A progressive-ilp based routing algorithm for cross-referencing biochips. In Design Automation Conf., pages 284--289. ACM, 2008.

Digital Library

[19]

Ping-Hung Yuh, Cliff Chiung-Yu Lin, Tsung-Wei Huang, Tsung-Yi Ho, Chia-Lin Yang, and Yao-Wen Chang. A SAT-based routing algorithm for cross-referencing biochips. In System Level Interconnect Prediction Workshop, pages 6:1--6:7. IEEE Press, 2011.

Digital Library

[20]

Oliver Keszocze, Robert Wille, and Rolf Drechsler. Exact routing for digital microfluidic biochips with temporary blockages. In Int'l Conf. on CAD, pages 405--410. IEEE Press, 2014.

[21]

Daniel Grissom and Philip Brisk. Fast online synthesis of generally programmable digital microfluidic biochips. In International Conference on Hardware/Software Codesign and System Synthesis, pages 413--422. ACM, 2012.

Digital Library

[22]

Kai Hu, Bang-Ning Hsu, Andrew Madison, Krishnendu Chakrabarty, and Richard Fair. Fault detection, real-time error recovery, and experimental demonstration for digital microfluidic biochips. In Design Automation Conf., pages 559--564. EDA Consortium, 2013.

Digital Library

[23]

Leonardo De Moura and Nikolaj Bjørner. Z3: An efficient SMT solver. In Tools and Algorithms for the Construction and Analysis of Systems, pages 337--340. Springer, 2008. Z3 is available at http://z3.codeplex.com/.

Digital Library

[24]

Advanced liquid logic, inc. http://www.liquid-logic.com.

Cited By

Roy PBanerjee AWille RBhattacharya B(2019)Harnessing the Granularity of Micro-Electrode-Dot-Array Architectures for Optimizing Droplet Routing in BiochipsACM Transactions on Design Automation of Electronic Systems10.1145/336599325:1(1-37)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1145/3365993
Willsey MStephenson ATakahashi CVaid PNguyen BPiszczek MBetts CNewman SJoshi SStrauss KCeze LBahar IHerlihy MWitchel ELebeck A(2019)PuddleProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304027(183-197)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304027
Zhong ZWille RChakrabarty KShibuya T(2019)Robust sample preparation on digital microfluidic biochipsProceedings of the 24th Asia and South Pacific Design Automation Conference10.1145/3287624.3287709(474-480)Online publication date: 21-Jan-2019
https://dl.acm.org/doi/10.1145/3287624.3287709
Show More Cited By

Index Terms

A General and Exact Routing Methodology for Digital Microfluidic Biochips
1. Applied computing
  1. Arts and humanities
    1. Architecture (buildings)
      1. Computer-aided design
  2. Physical sciences and engineering
    1. Engineering
      1. Computer-aided design
2. Hardware
  1. Electronic design automation
    1. Physical design (EDA)
      1. Placement
      2. Wire routing
  2. Emerging technologies

Recommendations

Digital microfluidic biochips: recent research and emerging challenges
CODES+ISSS '11: Proceedings of the seventh IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis

Microfluidic biochips are replacing the conventional biochemical analyzers, and are able to integrate on-chip all the basic functions for biochemical analysis. The "digital" microfluidic biochips (DMFBs) are manipulating liquids not as a continuous flow,...
A general and exact routing methodology for Digital Microfluidic Biochips
2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)
Advances in microfluidic technologies have led to the emergence of Digital Microfluidic Biochips (DMFBs), which are capable of automating laboratory procedures in biochemistry and molecular biology. During the design and use of these devices, droplet ...
Routing-based synthesis of digital microfluidic biochips

Microfluidic biochips are replacing the conventional biochemical analyzers, and are able to integrate on-chip all the necessary functions for biochemical analysis. The "digital" biochips are manipulating liquids as discrete droplets on a two-dimensional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '15: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design

November 2015

955 pages

ISBN:9781467383899

General Chair:
Diana Marculescu
Carnegie Mellon Univ., Dept. of Electrical and Computer Engineering, 5000 Forbes Ave., Pittsburgh, PA 15213, 412-268-1167
,
Program Chair:
Frank Liu
IBM Corp., IBM Austin Research Lab, 11501 Burnet Rd., MS 904-6G017, Austin, TX 78758, 512-286-7267

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Press

Publication History

Published: 02 November 2015

Check for updates

Qualifiers

Tutorial
Research
Refereed limited

Conference

ICCAD '15

Sponsor:

SIGDA

ICCAD '15: IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN

November 2 - 6, 2015

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
85
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Roy PBanerjee AWille RBhattacharya B(2019)Harnessing the Granularity of Micro-Electrode-Dot-Array Architectures for Optimizing Droplet Routing in BiochipsACM Transactions on Design Automation of Electronic Systems10.1145/336599325:1(1-37)Online publication date: 4-Dec-2019
https://dl.acm.org/doi/10.1145/3365993
Willsey MStephenson ATakahashi CVaid PNguyen BPiszczek MBetts CNewman SJoshi SStrauss KCeze LBahar IHerlihy MWitchel ELebeck A(2019)PuddleProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304027(183-197)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304027
Zhong ZWille RChakrabarty KShibuya T(2019)Robust sample preparation on digital microfluidic biochipsProceedings of the 24th Asia and South Pacific Design Automation Conference10.1145/3287624.3287709(474-480)Online publication date: 21-Jan-2019
https://dl.acm.org/doi/10.1145/3287624.3287709
Grimmer AKlepic BHo TWille RShin Y(2018)Sound valve-control for programmable microfluidic devicesProceedings of the 23rd Asia and South Pacific Design Automation Conference10.5555/3201607.3201617(40-45)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.5555/3201607.3201617
Ott JLoveless TCurtis CLesani MBrisk P(2018)BioScript: programming safe chemistry on laboratories-on-a-chipProceedings of the ACM on Programming Languages10.1145/32764982:OOPSLA(1-31)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276498
Curtis CGrissom DBrisk PKnoop JSchordan MJohnson TO'Boyle M(2018)A compiler for cyber-physical digital microfluidic biochipsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168826(365-377)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168826
Roy PSaha SRahaman HDasgupta P(2016)Novel Wire Planning Schemes for Pin Minimization in Digital Microfluidic BiochipsIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2016.254167124:11(3345-3358)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1109/TVLSI.2016.2541671

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents