research-article

SVM-Based Routability-Driven Chip-Level Design for Voltage-Aware Pin-Constrained EWOD Chips

Authors:

Yici CaiAuthors Info & Claims

ISPD '15: Proceedings of the 2015 Symposium on International Symposium on Physical Design

Pages 49 - 56

https://doi.org/10.1145/2717764.2717777

Published: 29 March 2015 Publication History

Abstract

The chip-level design problem is critical in pin-constrained electrowetting-on-dielectric (EWOD) biochips, which not only affects the number of control pins and PCB routing layers from the manufacturing cost point of view, but also determines the functional reliability induced by excessive applied voltage. Existing works either greedily minimize the number of control pins with degraded routability, or disregard the differences in driving voltages on the electrodes, where the trapped charge due to excessive applied voltage causes significant reliability issue. This paper presents the first SVM-based classifier for electrode addressing in chip-level design stage, which simultaneously optimizes the number of control pins, routability, as well as reliability. Experimental results on both real-life chips and synthesized benchmarks show that, compared with the state-of-the-art method, the SVM-based electrode addressing method obtains significant improvements in both routability and reliability.

References

[1]

F. K. Balagadde, L. You, C. L. Hansen, F. H. Arnold, and S. R. Quake, "Long-Term Monitoring of Bacteria Undergoing Programmed Population Control in a Microchemostat," Science, vol. 309, no. 5731, pp. 137--140, 2005.

[2]

K. Chakrabarty and F. Su, "Digital Microfluidic Biochips," CRC Press, 2006.

[3]

G. M. Whitesides, "The Origins and the Future of Microfluidics," Nature, vol. 442, no. 7101, pp. 368--373, 2006.

[4]

P. Yager, T. Edwards, E. Fu, K. Helton, K. Nelson, M. R. Tam, and B. H. Weigl, "Microfluidic Diagnostic Technologies for Global Public Health," Nature, vol. 442, no. 7101, pp. 412--418, 2006.

[5]

R. B. Fair, A. Khlystov, T. D. Tailor, V. Ivanov, R. D. Evans, P. B. Griffin, V. "Chemical and Biological Applications of Digital-Microfluidic Devices," IEEE Design and Test of Computers, vol. 24, no. 1, pp. 10--24, 2007.

Digital Library

[6]

T. Thorsen, S. J. Maerkl, and S. R. Quake, "Microfluidic Large-Scale Integration," Science, vol. 298, no. 5593, pp. 580--584, 2002.

[7]

D. Mark, S. Haeberle, G. Roth, F. von Stetten, and R. Zengerle, "Microfluidic Lab-on-a-Chip Platforms: Requirements, Characteristics and Applications," Chemical Society Reviews, vol. 39, no. 3, pp. 1153--1182, 2010.

[8]

M. G. Pollack, A. D. Shenderov, and R. B. Fair, "Electrowetting-Based Actuation of Droplets for Integrated Microfluidics," Lab Chip, vol. 2, no. 2, pp. 96--101, 2002.

[9]

V. Srinivasan, V. K. Pamula, and R. B. Fair, "An Integrated Digital Microfluidic Lab-on-a-Chip for Clinical Diagnostics on Human Physiological Fluids," Lab Chip, pp. 310--315, 2004.

[10]

F. SU, K. Chakrabarty, and R. B. Fair, "Microfluidics-Based Biochips: Technology Issues, Implementation Platforms, and Design-Automation Challenges," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 2, pp. 211--223, 2006.

Digital Library

[11]

I. Barbulovic-Nad, H. Yang, P. S. Park et al., "Digital Microfluidics for Cell-based Assays," Lab Chip, pp. 519--526, 2008.

[12]

V. Srinivasan, V. K. Pamula, P. Paik et al., "Protein Stamping for MALDI Mass Spectrometry Using an Electrowetting-based Microfluidic Platform," Optics East, 2004, vol. 5591, pp. 26--32.

[13]

T.-Y. Ho, J. Zeng, and K. Chakrabarty, "Digital Microfluidic Biochips: A Vision for Functional Diversity and More Than Moore," Prof. IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2010, pp. 578--585.

Digital Library

[14]

T.-W. Huang, S.-Y. Yeh, and T.-Y. Ho, "A Network-Flow Based Pin-Count Aware Routing Algorithm for Broadcast-Addressing EWOD Chips," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 12, pp. 1786--1799, 2011.

Digital Library

[15]

T.-W. Huang, T.-Y. Ho, and K. Chakrabarty, "Reliability-Oriented Broadcast Electrode-Addressing for Pin-Constrained Digital Microfluidic Biochips," Proc. of IEEE/ACM International Conference on Computer-Aided Design, 2011, pp. 448--455.

Digital Library

[16]

T.-Y. Ho, K. Chakrabarty, and P. Pop, "Digital Microfluidic Biochips: Recent Research and Emerging Challenges," Proc. of International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), 2011, pp. 335--343.

Digital Library

[17]

F. SU and K. Chakrabarty, "Architectural-Level Synthesis of Digital Microfluidics-Based Biochips," IEEE/ACM International Conference on Computer Aided Design, 2004, pp. 223--228.

Digital Library

[18]

D. Grissom, K. O'Neal, B. Preciado, H. Patel, R. Doherty, N. Liao, and P. Brisk, "A Digital Microfluidic Biochip Synthesis Framework," Proc. of IEEE/IFIP International Conference on VLSI and System-on-Chip (VLSI-SoC), 2012, pp. 177--182.

[19]

M. Cho and D. Z. Pan, "A High-Performance Droplet Routing Algorithm for Digital Microfluidic Biochips," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 10, pp. 1714--1724, 2008.

Digital Library

[20]

M. Cho and D. Z. Pan, "A High-Performance Droplet Router for Digital Microfluidic Biochips," Proc. of International Symposium on Physical Design, 2008, pp. 200--206.

Digital Library

[21]

F. SU and K. Chakrabarty, "Unified High-Level Synthesis and Module Placement for Defect-Tolerant Microfluidic Biochips," Proc. of Design Automation Conference, 2005, pp. 825--830.

Digital Library

[22]

F. SU, W. Hwang, and K. Chakrabarty, "Droplet Routing in the Synthesis of Digital Microfluidic Biochips," Proc. of Design, Automation and Test in Europe, 2006, vol. 1, pp. 1--6.

Digital Library

[23]

T. Xu and K. Chakrabarty, "Integrated Droplet Routing in the Synthesis of Microfluidic Biochips," Proc. of Design Automation Conference, 2007, pp. 948--953.

Digital Library

[24]

P.-H. Yuh, C.-L. Yang, and Y.-W. Chang, "Placement of Defect-Tolerant Digital Microfluidic Biochips Using the T-Tree Formulation," ACM Journal on Emerging Technologies in Computing Systems (JETC), vol. 3, no. 3, Artical No. 13, 2007.

Digital Library

[25]

P.-H. Yuh, C.-L. Yang, and Y.-W. Chang, "BioRoute: A Network-Flow-Based Routing Algorithm for the Synthesis of Digital Microfluidic Biochips," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 11, pp. 1928--1941, 2008.

Digital Library

[26]

T.-W. Huang and T.-Y. Ho, "A Two-Stage Integer Linear Programming-Based Droplet Routing Algorithm for Pin-Constrained Digital Microfluidic Biochips," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 2, pp. 215--228, 2011.

Digital Library

[27]

P.-H. Yuh, S. S. Sapatnekar, C.-L. Yang, and Y.-W. Chang, "A Progressive-ILP-Based Routing Algorithm for the Synthesis of Cross-Referencing Biochips," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, no. 9, pp. 1295--1306, 2009.

Digital Library

[28]

Z. Xiao and E. F. Y. Young, "CrossRouter: A Droplet Router for Cross-Referencing Digital Microfluidic Biochips," Proc. of Asia and South Pacific Design Automation Conference (ASP-DAC), 2010, pp. 269--274.

Digital Library

[29]

M. Campàs and I. Katakis, "DNA Biochip Arraying, Detection and Amplification Strategies," TrAC Trends in Analytical Chemistry, vol. 23, no. 1, pp. 49--62, 2004.

[30]

Y. Zhao and K. Chakrabarty, "Cross-contamination Avoidance for Droplet Routing in Digital Microfluidic Biochips," Proc. Design, Automation and Test in Europe (DATE), 2009, pp. 1290--1295.

Digital Library

[31]

T.-W. Huang, C.-H. Lin, and T.-Y. Ho, "A Contamination Aware Droplet Routing Algorithm for the Synthesis of Digital Microfluidic Biochips," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 11, pp. 1682--1695, 2010.

Digital Library

[32]

Y. Zhao and K. Chakrabarty, "Synchronization of Washing Operations with Droplet Routing for Cross-contamination Avoidance in Digital Microfluidic Biochips," Proc. of Design Automation Conference, 2010, pp. 635--640.

Digital Library

[33]

C. C. Y. Lin and Y.-W. Chang, "Cross-Contamination Aware Design Methodology for Pin-Constrained Digital Microfluidic Biochips," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, no. 6, pp. 817--828, 2011.

Digital Library

[34]

D. Mitra, S. Ghoshal, H. Rahaman, K. Chakrabarty, B. B. Bhattacharya, K. Chakrabarty, and B. B. Bhattacharya, "On Residue Removal in Digital Microfluidic Biochips," Proc. of the Great Lakes Symposium on VLSI, pp. 1--4, 2011.

Digital Library

[35]

Q. Wang, Y. Shen, H. Yao, T.-Y. Ho, and Y. Cai, "Practical Functional and Washing Droplet Routing for Cross-Contamination Avoidance in Digital Microfluidic Biochips," Proc. of Design Automation Conference (DAC), 2014, pp. 1--6.

Digital Library

[36]

T. Xu and K. Chakrabarty, "Broadcast Electrode-Addressing for Pin-Constrained Multi-Functional Digital Microfluidic Biochips," Proc. of IEEE/ACM Design Automation Conference, 2008, pp. 173--178.

Digital Library

[37]

H. J. J. Verheijen and M. W. J. Prins, "Reversible Electrowetting and Trapping of Charge: Model and Experiments," Langmuir, vol. 15, no. 20, pp. 6616--6620, 1999.

[38]

A. I. Drygiannakis, A. G. Papathanasiou, and A. G. Boudouvis, "On the Connection Between Dielectric Breakdown Strength, Trapping of Charge, and Contact Angle Saturation in Electrowetting," Langmuir, vol. 25, no. 1, pp. 147--152, 2009.

[39]

S.-H. Yeh, J.-W. Chang, T.-W. Huang, and T.-Y. Ho, "Voltage-Aware Chip-Level Design for Reliability-Driven Pin-Constrained EWOD Chips," Proc. of IEEE/ACM International Conference on Computer-Aided Design, 2012, pp. 353--360.

Digital Library

[40]

R. Fair, "Digital Microfluidics: Is a True Lab-on-a-Chip Possible?" Microfluid Nanofluidics, vol. 3, no. 3, pp. 245--281, 2007.

[41]

K. Chakrabarty, "Towards Fault-Tolerant Digital Microfluidic Lab-on-Chip: Defects, Fault Modeling, Testing, and Reconfiguration," Transactions of the IRE Professional Group on Audio, pp. 329--332, 2008.

[42]

S. S.-Y. Liu, C.-H. Chang, H.-M. Chen, and T.-Y. Ho, "ACER: An Agglomerative Clustering Based Electrode Addressing and Routing Algorithm for Pin-Constrained EWOD Chips," IEEE Trans. on CAD, vol. 33, no. 9, pp. 1316--1327, 2014.

[43]

J.-W. Chang, T.-W. Huang, and T.-Y. Ho, "An ILP-Based Obstacle-Avoiding Routing Algorithm for Pin-Constrained EWOD Chips," Proc. of Asia and South Pacific Design Automation Conference (ASP-DAC), 2012, pp. 67--72.

[44]

N. Cristianini and J. Shawe-Taylor, An Introduction to Support Vector Machines, Cambridge University Press, 2000.

Digital Library

[45]

T. Joachims, "Making Large-Scale SVM Learning Practical," B. Scholkopf and C. Burges, and A. Smola, Advances in Kernel Methods - Support Vector Learning, MIT-Press, 1999.

Digital Library

[46]

P. E. Hart, N. J. Nilsson, and B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100--107, 1968.

Cited By

Li KWu FLi JWang S(2024)Reinforcement Learning Double DQN for Chip-Level Synthesis of Paper-Based Digital Microfluidic BiochipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337065243:8(2465-2478)Online publication date: Aug-2024
https://doi.org/10.1109/TCAD.2024.3370652
Majumdar RDatta PChowdhury SPal R(2024)Advancement with digital microfluidic biochips towards sustainability and secured outcome: a comprehensive survey on specific design metricsDiscover Electronics10.1007/s44291-024-00018-x1:1Online publication date: 5-Aug-2024
https://doi.org/10.1007/s44291-024-00018-x
Wang QJi WLi ZCheong HKwon OYao HHo TShin KLi BSchlichtmann UCai Y(2020)Integrated Control-Fluidic Codesign Methodology for Paper-Based Digital Microfluidic BiochipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.289482039:3(613-625)Online publication date: Mar-2020
https://doi.org/10.1109/TCAD.2019.2894820
Show More Cited By

Index Terms

SVM-Based Routability-Driven Chip-Level Design for Voltage-Aware Pin-Constrained EWOD Chips
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Voltage-aware chip-level design for reliability-driven pin-constrained EWOD chips
ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

Electrowetting-on-dielectric (EWOD) chips have become the most promising technology to realize pin-constrained digital microfluidic biochips (PDMFBs). In the design flow of EWOD chips, reliability is a critical challenge as it directly affects execution ...
Routability-Driven Blockage-Aware Macro Placement
DAC '14: Proceedings of the 51st Annual Design Automation Conference

We present a new floorplan representation, called circular-packing trees (CP-trees), for the problem of macro placement. Our CP-trees can flexibly pack movable macros toward corners or pre-placed macros along chip boundaries circularly to optimize macro ...
Design of pin-constrained general-purpose digital microfluidic biochips
DAC '12: Proceedings of the 49th Annual Design Automation Conference

Digital microfluidic biochips are being increasingly used for biotechnology applications. The number of control pins used to drive electrodes is a major contributor to fabrication cost for disposable biochips in a highly cost-sensitive market. Most ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '15: Proceedings of the 2015 Symposium on International Symposium on Physical Design

March 2015

204 pages

ISBN:9781450333993

DOI:10.1145/2717764

General Chair:
Azadeh Davoodi
University of Wisconsin - Madison
,
Program Chair:
Evangeline Young
The Chinese University of Hong Kong

Copyright © 2015 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Tsinghua University Initiative Scientific Research Program
Ministry of Science and Technology, Taiwan
Doctoral Fund of Ministry of Education of China
National Natural Science Foundation of China

Conference

ISPD'15

Sponsor:

SIGDA

ISPD'15: International Symposium on Physical Design

March 29 - April 1, 2015

California, Monterey, USA

Acceptance Rates

ISPD '15 Paper Acceptance Rate 14 of 37 submissions, 38%;

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
202
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li KWu FLi JWang S(2024)Reinforcement Learning Double DQN for Chip-Level Synthesis of Paper-Based Digital Microfluidic BiochipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337065243:8(2465-2478)Online publication date: Aug-2024
https://doi.org/10.1109/TCAD.2024.3370652
Majumdar RDatta PChowdhury SPal R(2024)Advancement with digital microfluidic biochips towards sustainability and secured outcome: a comprehensive survey on specific design metricsDiscover Electronics10.1007/s44291-024-00018-x1:1Online publication date: 5-Aug-2024
https://doi.org/10.1007/s44291-024-00018-x
Wang QJi WLi ZCheong HKwon OYao HHo TShin KLi BSchlichtmann UCai Y(2020)Integrated Control-Fluidic Codesign Methodology for Paper-Based Digital Microfluidic BiochipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.289482039:3(613-625)Online publication date: Mar-2020
https://doi.org/10.1109/TCAD.2019.2894820
Shi JFu PZheng W(2020)Pin Addressing Method Based on an SVM With a Reliability Constraint in Digital Microfluidic BiochipsIEEE Access10.1109/ACCESS.2020.30349458(199792-199802)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3034945
Wang QZou HYao HHo TWille RCai Y(2018)Physical Co-Design of Flow and Control Layers for Flow-Based Microfluidic BiochipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2017.274800337:6(1157-1170)Online publication date: Jun-2018
https://doi.org/10.1109/TCAD.2017.2748003
McDaniel JZimmerman ZGrissom DBrisk P(2017)PCB Escape Routing and Layer Minimization for Digital Microfluidic BiochipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2016.256819936:1(69-82)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1109/TCAD.2016.2568199
Wang QZuo SYao HHo TLi BSchlichtmann UCai Y(2017)Hamming-distance-based valve-switching optimization for control-layer multiplexing in flow-based microfluidic biochips2017 22nd Asia and South Pacific Design Automation Conference (ASP-DAC)10.1109/ASPDAC.2017.7858376(524-529)Online publication date: Jan-2017
https://doi.org/10.1109/ASPDAC.2017.7858376
Yao HWang QHo T(2017)Smart Microfluidic Biochips: Cyberphysical Sensor Integration for Dynamic Error RecoverySmart Sensors at the IoT Frontier10.1007/978-3-319-55345-0_3(23-71)Online publication date: 31-May-2017
https://doi.org/10.1007/978-3-319-55345-0_3
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