research-article

BioRoute: a network-flow based routing algorithm for digital microfluidic biochips

Authors:

Ping-Hung Yuh,

Chia-Lin Yang,

Yao-Wen ChangAuthors Info & Claims

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

Pages 752 - 757

Published: 05 November 2007 Publication History

Get Access

Abstract

Due to the recent advances in microfluidics, digital microfluidic biochips are expected to revolutionize laboratory procedures. One critical problem for biochip synthesis is the droplet routing problem. Unlike traditional VLSI routing problems, in addition to routing path selection, the biochip routing problem needs to address the issue of scheduling droplets under the practical constraints imposed by the fluidic property and the timing restriction of the synthesis result. In this paper, we present the first network-flow based routing algorithm that can concurrently route a set of non-interfering nets for the droplet routing problem on biochips. We adopt a two-stage technique of global routing followed by detailed routing. In global routing, we first identify a set of non-interfering nets and then adopt the network-flow approach to generate optimal global-routing paths for the nets. In detailed routing, we present the first polynomial-time algorithm for simultaneous routing and scheduling using the global-routing paths with a negotiation-based routing scheme. The experimental results show the robustness and efficiency of our algorithm.

References

[1]

F. Su, K. Chakrabarty, and R. B. Fair, "Micrpfluidic-based biochips: Technology issues, implementation platforms, and design-automation challenges," TCAD, 2006.

Digital Library

Google Scholar

[2]

R. B. Fair, V. Srinivasan, H. Ren, P. Paik, V. Pamula, and M. Pollack, "Electrowetting-based on-chip sample processing for integrated microfluidics," in IEDM, 2003.

Google Scholar

[3]

K. F. Böhringer, "Modeling and controlling parallel tasks in droplet-based microfluidic systems," TCAD, 2006.

Google Scholar

[4]

E. J. Griffith, S. Akella, and M. K. Goldberg, "Performance characterization of a reconfigurable planar-array digital microfluidic system," TCAD, 2006.

Digital Library

Google Scholar

[5]

F. Su, W. Hwang, and K. Chakrabarty, "Droplet routing in the synthesis of digital microfluidic biochips," in DATE, 2006.

Digital Library

Google Scholar

[6]

P.-H. Yuh, C.-L. Yang, and Y.-W. Chang, "Placement of digital microfluidic biochips using the t-tree formulation," in DAC, 2006.

Digital Library

Google Scholar

[7]

F. Su and K. Chakrabarty, "Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips," in DAC, 2005.

Digital Library

Google Scholar

[8]

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, 1993.

Digital Library

Google Scholar

[9]

R. D. Mohring, Graphs and Orders: the rosl of graphs in the theory of ordered sets and its application. D. Reidel Publishing Company, 1984.

Google Scholar

[10]

L. McMurchie and C. Ebeling, "Pathfinder: a negotiation-based performance-driven router for fpgas," in FPGA, 1995.

Digital Library

Google Scholar

[11]

K. Mehlhorn and S. Näher, The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999.

Digital Library

Google Scholar

Cited By

View all

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
Keszocze OWille RDrechsler RChang Y(2014)Exact routing for digital microfluidic biochips with temporary blockagesProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691447(405-410)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691447
Roy PBhattacharjee RSohid MChakraborty SRahaman HDasgupta PJerraya ACarloni LChang NFummi F(2012)An intelligent compaction technique for pin constrained routing in cross referencing digital microfluidic biochipsProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2380445.2380511(423-432)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380445.2380511
Show More Cited By

Recommendations

BioRoute: A Network-Flow-Based Routing Algorithm for the Synthesis of Digital Microfluidic Biochips

Due to recent advances in microfluidics, digital microfluidic biochips are expected to revolutionize laboratory procedures. One critical problem for biochip synthesis is the droplet routing problem. Unlike traditional very large scale integration ...
MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
MP-trees: a packing-based macro placement algorithm for mixed-size designs
DAC '07: Proceedings of the 44th annual Design Automation Conference

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various ...

Comments

Information & Contributors

Information

Published In

ICCAD '07: Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design

November 2007

933 pages

ISBN:1424413826

General Chair:
Georges Gielen
ESAT-MICAS, Katholieke Univ. Leuven, Leuven, Belgium

Publisher

IEEE Press

Publication History

Published: 05 November 2007

Check for updates

Qualifiers

Research-article

Conference

ICCAD07

Sponsor:

CEDA
SIGDA
IEEE-CS\DATC

ICCAD07: The International Conference on Computer-Aided Design 2007

November 5 - 8, 2007

California, San Jose

Acceptance Rates

ICCAD '07 Paper Acceptance Rate 139 of 510 submissions, 27%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
298
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Keszocze OWille RDrechsler RChang Y(2014)Exact routing for digital microfluidic biochips with temporary blockagesProceedings of the 2014 IEEE/ACM International Conference on Computer-Aided Design10.5555/2691365.2691447(405-410)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.5555/2691365.2691447
Roy PBhattacharjee RSohid MChakraborty SRahaman HDasgupta PJerraya ACarloni LChang NFummi F(2012)An intelligent compaction technique for pin constrained routing in cross referencing digital microfluidic biochipsProceedings of the eighth IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis10.1145/2380445.2380511(423-432)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.1145/2380445.2380511
Yuh PLin CHuang THo TYang CChang Y(2011)A SAT-based routing algorithm for cross-referencing biochipsProceedings of the System Level Interconnect Prediction Workshop10.5555/2134224.2134233(1-7)Online publication date: 5-Jun-2011
https://dl.acm.org/doi/10.5555/2134224.2134233
Roy PRahaman HDasgupta PAtienza DXie YAyala JStevens K(2011)Fast high-performance algorithms for multi-pin droplet routing in digital microfluidic biochipsProceedings of the 21st edition of the great lakes symposium on Great lakes symposium on VLSI10.1145/1973009.1973055(229-234)Online publication date: 2-May-2011
https://dl.acm.org/doi/10.1145/1973009.1973055
Zhao YChakrabarty KChang YHu J(2011)Co-optimization of droplet routing and pin assignment in disposable digital microfluidic biochipsProceedings of the 2011 international symposium on Physical design10.1145/1960397.1960413(69-76)Online publication date: 27-Mar-2011
https://dl.acm.org/doi/10.1145/1960397.1960413
Xiao ZYoung ELin Y(2010)CrossRouterProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899780(269-274)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.5555/1899721.1899780
Maftei EPop PMadsen JKathail VTatge RBarua R(2010)Routing-based synthesis of digital microfluidic biochipsProceedings of the 2010 international conference on Compilers, architectures and synthesis for embedded systems10.1145/1878921.1878928(41-50)Online publication date: 24-Oct-2010
https://dl.acm.org/doi/10.1145/1878921.1878928
Lin CChang YSapatnekar S(2010)Cross-contamination aware design methodology for pin-constrained digital microfluidic biochipsProceedings of the 47th Design Automation Conference10.1145/1837274.1837438(641-646)Online publication date: 13-Jun-2010
https://dl.acm.org/doi/10.1145/1837274.1837438
Roy PRahaman HDasgupta PBahar RLombardi FAtienza DBrunvand E(2010)A novel droplet routing algorithm for digital microfluidic biochipsProceedings of the 20th symposium on Great lakes symposium on VLSI10.1145/1785481.1785583(441-446)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.1145/1785481.1785583
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.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Recommendations

BioRoute: A Network-Flow-Based Routing Algorithm for the Synthesis of Digital Microfluidic Biochips

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

MP-trees: a packing-based macro placement algorithm for mixed-size designs

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations