research-article

A novel droplet routing algorithm for digital microfluidic biochips

Authors:

Hafizur Rahaman,

Parthasarathi DasguptaAuthors Info & Claims

GLSVLSI '10: Proceedings of the 20th symposium on Great lakes symposium on VLSI

Pages 441 - 446

https://doi.org/10.1145/1785481.1785583

Published: 16 May 2010 Publication History

Abstract

One of the recent areas of research interest is the use of microfluidics for building up biochips, the digital microfluidic biochips (DMFB). This paper deals with a challenging problem related to the design of DMFB. Specifically the design problem considered is related to high performance droplet routing, where each droplet has single source location and single target location. The objectives are (i) minimizing the number of electrodes used in the DMFB, and (ii) minimizing the total routing time of all the droplets or arrival time of a droplet that is the last to arrive at its target(latest arrival time). We propose a simple algorithm for concurrent path allocation to multiple droplets, based on the Soukup's routing algorithm [22], together with the use of stalling, and possible detouring of droplets in cases of contentions. Selection of the droplets is based on their respective source to target Manhattan paths. The empirical results are quite encouraging.

References

[1]

Boahringer. K. F. "Modeling and controlling parallel tasks in droplet based microfluidic systems". IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 25(2):334 -- 344, February 2006.

Digital Library

[2]

Cho Minsik and Pan. David Z. "A high-performance droplet routing algorithm for digital microfluidic biochips." IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 27(10):406--419, October 2008.

Digital Library

[3]

Akella S. Griffith E. J. and Goldberg. M. K. "Performance characterization of a reconfigurable planar-array digital microfluidic system." IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, 25(10):340--352,February 2006.

Digital Library

[4]

Hwang William, Su Fei and Chakrabarty K. "Droplet routing in the synthesis of digital microfluidic biochips." In Proceedings of Design Automation and Test in Europe, 2006.

Digital Library

[5]

Zeng X., Liu L.Wu, J,Yue. R. "Droplets Actuating Chip Based On EWOD". Springer-Verlag, 2007.

[6]

Mukherjee. T. "Design automation issues for biofluidic microchips." In Proceedings of International Conference on Computer Aided Design, page 463 -- 470, November 2005.

Digital Library

[7]

Pollack M.G, Paik P, Pamula V.K and Chakrabarty K. "Coplanar digital microfluidics using standard printed circuit board Processes". In Proceedings of in MicroTAS, 2005.

[8]

Yang C.L, Yuh P.H. and Chang. Y.W. "Bioroute: A network flow based routing algorithm for digital microfluidic biochips." In Proceedings of IEEE/ACM International Conference of Computer Aided Design, pages 752--757, 2007.

Digital Library

[9]

Yang Chia-Lin,Chang Yao-Wen,Yuh Ping-Hung, Sapatnekar S. "A progressive-ilp based routing algorithm for Cross referencing biochips." In Proceedings of Design Automation Conference, pages 284 -- 289, June 2008.

Digital Library

[10]

Ren H., Paik P, Pamula V. K, Fair R. B., Srinivasan V. and Pollack. M.G. "Electrowetting-based on-chip sample processing for integrated microfluidics." In Proceedings of IEEE International Electron Devices Meeting (IEDM), pages 32.5.1--32.5.4, 2003.

[11]

Tailor T.D., Ivan V., Evans R. D., Griffin P. B., Srinivasan,V.Pamula V. K., Pollack M. G. Fair R. B., Khlystov A. and Zhou J. "Chemical and biological applications of digital- microfluidic devices." IEEE Design and Test for Computers, 24:10--24, 2007.

Digital Library

[12]

Sarrafzadeh M. and Wong. C. K. "An Introduction to VLSI Physical Design". McGraw Hill, 1996.

Digital Library

[13]

Sherwani. Naveed A. "Algorithm for VLSI Physical Design Automation."Kluwer Academic Publishers, Boston, 1999.

Digital Library

[14]

Stallings William "Data and Computer Communication"- Prentice Hall of India Pvt. Ltd, New Delhi,India,2004.

Digital Library

[15]

Su Fei and Chakrabarty K. "Architectural-Level synthesis of digital microfluidics-based biochips". In Proceedings of IEEE International Conference on CAD, pages 223--228,2004

Digital Library

[16]

Su F, Xu T., Hwang W. and Chakrabarty. K. "Automated design of pin-constrained digital microfluidic biochips under droplet-interference constraints." ACM Journal on Emerging Technologies in Computing Systems, 3(14), 2007.

Digital Library

[17]

Rivest Robert L., Cormen Thomas H, Leiserson. Charles E. "Introduction to Algorithms". MIT, 1990.

Digital Library

[18]

Xu T. and Chakrabarty. K. "Droplet-trace-based array partitioning and a pin assignment algorithm for the automated design of digital microfluidic biochips." In Proceedings of IEEE/ACM International Conference on Hardware/Software Codesign and System Synthesis, pages 112--117, 2006.

Digital Library

[19]

Xu T. and Chakrabarty. K. "A cross-referencing-based droplet manipulation method for high-throughput and pinconstrained digital microfluidic arrays." In Proceedings of Design Automation and Test in Europe, pages 552 -- 557, April 2007.

Digital Library

[20]

Xu T. and Chakrabarty. K. "Integrated droplet routing in the synthesis of microfluidic biochips." In Proceedings of Design Automation Conference, pages 948 -- 953, 2007.

Digital Library

[21]

Paik Philip. Y., Pamula Vamsee K. and Chakrabarty K., "Adaptive Cooling of Integrated Circuits Using Digital Microfluidics" IEEE Transactions on Very Large Scale Integration(VLSI) Systems, vol. 16, no. 4, April 2008.

Digital Library

[22]

Soukup J, "Fast Maze Router" Proceedings of the 15th ACM IEEE Design Automation Conference, Pages 100--102,1978

Digital Library

Cited By

Loveless TBrisk PDubach CBruening DHardekopf B(2023)Compiling Functions onto Digital MicrofluidicsProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580023(136-148)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580023
Swain JPyne S(2023)A Flooding-Based Droplet Routing Protocol for Digital Microfluidic BiochipJournal of Circuits, Systems and Computers10.1142/S021812662350302432:17Online publication date: 30-May-2023
https://doi.org/10.1142/S0218126623503024
Swain JPyne S(2023)A bidirectional droplet routing in digital microfluidics biochipMicroprocessors & Microsystems10.1016/j.micpro.2023.10477498:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.micpro.2023.104774
Show More Cited By

Index Terms

Recommendations

Flexible Droplet Routing in Active Matrix–Based Digital Microfluidic Biochips

The active matrix (AM)-based architecture offers many advantages over conventional digital electrowetting-on-dielectric (EWOD) microfluidic biochips, such as the capability of handling variable-size droplets, more flexible droplet movement, and precise ...
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,...
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

GLSVLSI '10: Proceedings of the 20th symposium on Great lakes symposium on VLSI

May 2010

502 pages

ISBN:9781450300124

DOI:10.1145/1785481

General Chairs:
R. Iris Bahar
Brown University, USA
,
Fabrizio Lombardi
Northeastern University, USA
,
Program Chairs:
David Atienza
EPFL, Switzerland
,
Erik Brunvand
University of Utah, USA

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

In-Cooperation

IEEE CEDA
IEEE CASS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 May 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GLSVLSI '10

Sponsor:

SIGDA

GLSVLSI '10: Great Lakes Symposium on VLSI 2010

May 16 - 18, 2010

Rhode Island, Providence, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
316
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Loveless TBrisk PDubach CBruening DHardekopf B(2023)Compiling Functions onto Digital MicrofluidicsProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580023(136-148)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580023
Swain JPyne S(2023)A Flooding-Based Droplet Routing Protocol for Digital Microfluidic BiochipJournal of Circuits, Systems and Computers10.1142/S021812662350302432:17Online publication date: 30-May-2023
https://doi.org/10.1142/S0218126623503024
Swain JPyne S(2023)A bidirectional droplet routing in digital microfluidics biochipMicroprocessors & Microsystems10.1016/j.micpro.2023.10477498:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.micpro.2023.104774
Rajesh KPyne S(2022)Droplet Routing Based on Double Deep Q-Network Algorithm for Digital Microfluidic BiochipsJournal of Circuits, Systems and Computers10.1142/S021812662250299131:17Online publication date: 23-Jul-2022
https://doi.org/10.1142/S0218126622502991
Jiang CYang RYuan B(2022)An evolutionary algorithm with indirect representation for droplet routing in digital microfluidic biochipsEngineering Applications of Artificial Intelligence10.1016/j.engappai.2022.105305115:COnline publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1016/j.engappai.2022.105305
Loveless TOtt JBrisk PMars JTang LXue JWu P(2020)A performance-optimizing compiler for cyber-physical digital microfluidic biochipsProceedings of the 18th ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3368826.3377925(171-184)Online publication date: 22-Feb-2020
https://dl.acm.org/doi/10.1145/3368826.3377925
Rajesh KTirkey ASarkar APyne S(2020)Reinforcement Learning based Droplet Routing Algorithm for Digital Microfluidic Biochips2020 24th International Symposium on VLSI Design and Test (VDAT)10.1109/VDAT50263.2020.9190306(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/VDAT50263.2020.9190306
Jaluka VRajesh KPyne S(2020)Virtual Droplet Routing Algorithm for Digital Microfluidic Biochips2020 24th International Symposium on VLSI Design and Test (VDAT)10.1109/VDAT50263.2020.9190214(1-6)Online publication date: Jul-2020
https://doi.org/10.1109/VDAT50263.2020.9190214
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
Swain JRajesh KPyne S(2019)A Space Efficient Greedy Droplet Routing for Digital Microfluidics BiochipVLSI Design and Test10.1007/978-981-32-9767-8_9(102-114)Online publication date: 18-Aug-2019
https://doi.org/10.1007/978-981-32-9767-8_9
Show More Cited By

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