research-article

Open access

Directed Placement for mVLSI Devices

Authors:

Philip BriskAuthors Info & Claims

ACM Journal on Emerging Technologies in Computing Systems (JETC), Volume 16, Issue 2

Article No.: 14, Pages 1 - 26

https://doi.org/10.1145/3369585

Published: 12 December 2019 Publication History

All formats PDF

Abstract

Continuous-flow microfluidic devices based on integrated channel networks are becoming increasingly prevalent in research in the biological sciences. At present, these devices are physically laid out by hand by domain experts who understand both the underlying technology and the biological functions that will execute on fabricated devices. The lack of a design science that is specific to microfluidic technology creates a substantial barrier to entry. To address this concern, this article introduces Directed Placement, a physical design algorithm that leverages the natural “directedness” in most modern microfluidic designs: fluid enters at designated inputs, flows through a linear or tree-based network of channels and fluidic components, and exits the device at dedicated outputs. Directed placement creates physical layouts that share many principle similarities to those created by domain experts. Directed placement allows components to be placed closer to their neighbors compared to existing layout algorithms based on planar graph embedding or simulated annealing, leading to an average reduction in laid-out fluid channel length of 91% while improving area utilization by 8% on average. Directed placement is compatible with both passive and active microfluidic devices and is compatible with a variety of mainstream manufacturing technologies.

References

[1]

[n.d.]. Design Your Own Device: Basic Design Rules. Retrieved May 30, 2019, from https://web.stanford.edu/group/foundry/.

[2]

Nada Amin, William Thies, and Saman P. Amarasinghe. 2009. Computer-aided design for microfluidic chips based on multilayer soft lithography. In 27th International Conference on Computer Design (ICCD’09) 2--9.

[3]

Ismail Emre Araci and Stephen R. Quake. 2012. Microfluidic very large scale integration (mVLSI) with integrated micromechanical valves. Lab-on-a-Chip 12, 16 (Aug. 2012), 2803--2806.

[4]

Frederick K. Balagaddé, Lingchong You, Carl L. Hansen, Frances H. Arnold, and Stephen R. Quake. 2005. Long-term monitoring of bacteria undergoing programmed population control in a microchemostat. Science (New York, N.Y.) 309, 5731 (July 2005), 137--40.

[5]

H. Nelson Brady. 1984. An approach to topological pin assignment. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 3, 3 (1984), 250--255.

Digital Library

[6]

Brian Crites, Karen Kong, and Philip Brisk. 2017. Diagonal component expansion for flow-layer placement of flow-based microfluidic biochips. ACM Transactions on Embedded Computing Systems (TECS) 16, 5s (2017), 126.

Digital Library

[7]

Dino Di Carlo, Nima Aghdam, and Luke P. Lee. 2006. Single-cell enzyme concentrations, kinetics, and inhibition analysis using high-density hydrodynamic cell isolation arrays. Analytical Chemistry 78, 14 (2006), 4925--4930.

[8]

Jamil El-Ali, Peter K. Sorger, and Klavs F. Jensen. 2006. Cells on chips. Nature 442, 7101 (2006), 403--411.

[9]

Luis M. Fidalgo and Sebastian J. Maerkl. 2011. A software-programmable microfluidic device for automated biology. Lab Chip 11, 9 (2011), 1612--1619.

[10]

Hua Gong, Adam T. Woolley, and Gregory P. Nordin. 2016. High density 3D printed microfluidic valves, pumps, and multiplexers. Lab Chip 16, 13 (2016), 2450--2458.

[11]

Andreas Grimmer, Philipp Frank, Philipp Ebner, Sebastian Häfner, Andreas Richter, and Robert Wille. 2018. Meander designer: Automatically generating meander channel designs. Micromachines 9, 12 (2018), 625.

[12]

Andreas Grimmer, Qin Wang, Hailong Yao, Tsung-Yi Ho, and Robert Wille. 2017. Close-to-optimal placement and routing for continuous-flow microfluidic biochips. In 22nd Asia and South Pacific Design Automation Conference (ASP-DAC’17). 530--535.

[13]

William H. Grover, Alison M. Skelley, Chung N. Liu, Eric T. Lagally, and Richard A. Mathies. 2003. Monolithic membrane valves and diaphragm pumps for practical large-scale integration into glass microfluidic devices. Sensors and Actuators B: Chemical 89, 3 (2003), 315--323.

[14]

Jong Wook Hong and Stephen R. Quake. 2003. Integrated nanoliter systems. Nature Biotechnology 21, 10 (Oct. 2003), 1179--1183.

[15]

Jong Wook Hong, Vincent Studer, Giao Hang, W. French Anderson, and Stephen R. Quake. 2004. A nanoliter-scale nucleic acid processor with parallel architecture. Nature Biotechnology 22 (March 2004), 435--439. https://doi.org/10.1038/nbt951

[16]

Yi-Ling Hsieh and Tsung-Yi Ho. 2011. Automated physical design of microchip-based capillary electrophoresis systems. In VLSI Design 2011: 24th International Conference on VLSI Design, IIT. 165--170.

[17]

Kai Hu, Trung Anh Dinh, Tsung-Yi Ho, and Krishnendu Chakrabarty. 2017. Control-layer routing and control-pin minimization for flow-based microfluidic biochips. IEEE Transactions on CAD of Integrated Circuits and Systems 36, 1 (2017), 55--68.

Digital Library

[18]

Bo Huang, Hongkai Wu, Samuel Kim, and Richard N. Zare. 2005. Coating of poly(dimethylsiloxane) with n-dodecyl-Î²-d-maltoside to minimize nonspecific protein adsorption. Lab Chip 5, 10 (2005), 1005--1007.

[19]

Paul J. Hung, Philip J. Lee, Poorya Sabounchi, Robert Lin, and Luke P. Lee. 2005. Continuous perfusion microfluidic cell culture array for high-throughput cell-based assays. Biotechnology and Bioengineering 89, 1 (2005), 1--8.

[20]

E. C. Jensen, W. H. Grover, and R. A. Mathies. 2007. Micropneumatic digital logic structures for integrated microdevice computation and control. Journal of Microelectromechanical Systems 16, 6 (Dec. 2007), 1378--1385.

[21]

Xiran Jiang, Ning Shao, Wenwen Jing, Shengce Tao, Sixiu Liu, and Guodong Sui. 2014. Microfluidic chip integrating high throughput continuous-flow PCR and DNA hybridization for bacteria analysis. Talanta 122 (2014), 246--250.

[22]

Casimir Kuratowski. 1930. Sur le problème des courbes gauches en Topologie. Fundamenta Mathematicae 15, 1 (1930), 271--283.

[23]

Ali Lashkaripour, Christopher Rodriguez, Luis Ortiz, and Douglas Densmore. 2019. Performance tuning of microfluidic flow-focusing droplet generators. Lab Chip 19, 6 (2019), 1041--1053.

[24]

Ali Lashkaripour, Ryan Silva, and Douglas Densmore. 2018. Desktop micromilled microfluidics. Microfluidics and Nanofluidics 22, 3 (Feb. 2018), 31.

[25]

C. Y. Lee. 1959. An algorithm for path connections and its applications. IRE Transactions on Electronic Computers 30 (1959), 1389--1401.

[26]

Baichen Li, Lin Li, Allan Guan, Quan Dong, Kangcheng Ruan, Ronggui Hu, and Zhenyu Li. 2014. A smartphone controlled handheld microfluidic liquid handling system. Lab-on-a-Chip 14, 20 (2014), 4085--4092.

[27]

Chun-Xun Lin, Chih-Hung Liu, I-Che Chen, D. T. Lee, and Tsung-Yi Ho. 2014. An efficient bi-criteria flow channel routing algorithm for flow-based microfluidic biochips. In Proceedings of the the 51st Annual Design Automation (DAC’14). 141:1--141:6.

[28]

Chunfeng Liu, Bing Li, Tsung-Yi Ho, Krishnendu Chakrabarty, and Ulf Schlichtmann. 2018. Design-for-testability for continuous-flow microfluidic biochips. In Proceedings of the 55th Annual Design Automation Conference (DAC’18). 164:1--164:6.

Digital Library

[29]

Jeffrey McDaniel, Auralila Baez, Brian Crites, Aditya Tammewar, and Philip Brisk. 2013. Design and verification tools for continuous fluid flow-based microfluidic devices. In Asia and South Pacific Design Automation Conference (ASPDAC’13).

[30]

Jeffrey McDaniel, Brian Crites, Philip Brisk, and William H. Grover. 2015. Flow-layer physical design for microchips based on monolithic membrane valves. IEEE Design 8 Test 32, 6 (2015), 51--59.

[31]

Jeffrey McDaniel, Christopher Curtis, and Philip Brisk. 2013. Automatic synthesis of microfluidic large scale integration chips from a domain-specific language. In Proceedings of the IEEE Biomedical Circuits and Systems Conference (BioCAS’13). 101--104.

[32]

Jeffrey McDaniel, Brendon Parker, and Philip Brisk. 2014. Simulated annealing-based placement for microfluidic large scale integration (mLSI) chips. In Proceedings of the 22nd IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC’14). 213--218.

[33]

Carver Mead and Lynn Conway. 1980. Introduction to VLSI Systems. Addison-Wesley.

Digital Library

[34]

Jessica Melin and Stephen R. Quake. 2007. Microfluidic large-scale integration: The evolution of design rules for biological automation. Annual Review of Biophysics and Biomolecular Structure 36 (Jan. 2007), 213--231.

[35]

Wajid Hassan Minhass, Paul Pop, Jan Madsen, and Felician Stefan Blaga. 2012. Architectural synthesis of flow-based microfluidic large-scale integration biochips. In Proceedings of the International Conference on Compilers, Architectures and Synthesis of Embedded Systems (CASES’12). 181--190.

Digital Library

[36]

Wajid Hassan Minhass, Paul Pop, Jan Madsen, and Tsung-yi Ho. 2013. Control synthesis for the flow-based microfluidic large-scale integration biochips. In Asia and South Pacific Design Automation Conference (ASPDAC’13).

[37]

Shirin Mesbah Oskui, Graciel Diamante, Chunyang Liao, Wei Shi, Jay Gan, Daniel Schlenk, and William H. Grover. 2016. Assessing and reducing the toxicity of 3D-printed parts. Environmental Science 8 Technology Letters 3, 1 (2016), 1--6.

[38]

Nicole Pamme. 2007. Continuous flow separations in microfluidic devices. Lab on a Chip 7, 12 (2007), 1644--1659.

[39]

Anton J. Pfeiffer, Tamal Mukherjee, and Steinar Hauan. 2006. Synthesis of multiplexed biofluidic microchips. IEEE Transactions on CAD of Integrated Circuits and Systems 25, 2 (2006), 321--333.

Digital Library

[40]

Seetal Potluri, Paul Pop, and Jan Madsen. 2019. Design-for-testability of on-chip control in mVLSI biochips. IEEE Design 8 Test 36, 1 (2019), 48--56.

[41]

Seetal Potluri, Alexander Schneider, Martin Horslev-Petersen, Paul Pop, and Jan Madsen. 2017. Synthesis of on-chip control circuits for mVLSI biochips. In Design, Automation 8 Test in Europe Conference 8 Exhibition (DATE’17). 1799--1804.

[42]

Minsoung Rhee and Mark A. Burns. 2008. Microfluidic assembly blocks. Lab-on-a-Chip 8, 8 (2008), 1365--1373.

[43]

Chad I. Rogers, Kamran Qaderi, Adam T. Woolley, and Gregory P. Nordin. 2015. 3D printed microfluidic devices with integrated valves. Biomicrofluidics 9, 1 (2015), 016501.

[44]

C. Sechen and A. Sangiovanni-Vincentelli. 1985. The TimberWolf placement and routing package. IEEE Journal of Solid-State Circuits 20, 2 (April 1985), 510--522.

[45]

Carl Sechen and Alberto L. Sangiovanni-Vincentelli. 1986. TimberWolf3.2: A new standard cell placement and global routing package. In Proceedings of the 23rd ACM/IEEE Design Automation Conference. 432--439.

[46]

Jayna J. Shah, Jon Geist, Laurie E. Locascio, Michael Gaitan, Mulpuri V. Rao, and Wyatt N. Vreeland. 2006. Surface modification of poly(methyl methacrylate) for improved adsorption of wall coating polymers for microchip electrophoresis. ELECTROPHORESIS 27, 19 (2006), 3788--3796.

[47]

Taraneh Taghavi, Xiaojian Yang, Bo-Kyung Choi, Maogang Wang, and Majid Sarrafzadeh. 2006. Dragon2006: Blockage-aware congestion-controlling mixed-size placer. In Proceedings of the 2006 International Symposium on Physical Design (ISPD’06). 209--211.

Digital Library

[48]

S. C. Terry, J. H. Jerman, and J. B. Angell. 1979. A gas chromatographic air analyzer fabricated on a silicon wafer. IEEE Transactions on Electron Devices 26, 12 (Dec. 1979), 1880--1886.

[49]

Todd Thorsen, Sebastian J. Maerkl, and Stephen R. Quake. 2002. Microfluidic large-scale integration. Science 298, 5593 (2002), 580--584.

[50]

Kai-Han Tseng, Sheng-Chi You, Jhe-Yu Liou, and Tsung-Yi Ho. 2013. A top-down synthesis methodology for flow-based microfluidic biochips considering valve-switching minimization. In Proceedings of the International Symposium on Physical Design (ISPD’13). 123--129.

Digital Library

[51]

Tsun-Ming Tseng, Mengchu Li, Daniel Nestor Freitas, Travis McAuley, Bing Li, Tsung-Yi Ho, Ismail Emre Araci, and Ulf Schlichtmann. 2018. Columba 2.0: A co-layout synthesis tool for continuous-flow microfluidic biochips. IEEE Transactions on CAD of Integrated Circuits and Systems 37, 8 (2018), 1588--1601.

[52]

Tsun-Ming Tseng, Mengchu Li, Daniel Nestor Freitas, Amy Mongersun, Ismail Emre Araci, Tsung-Yi Ho, and Ulf Schlichtmann. 2018. Columba S: A scalable co-layout design automation tool for microfluidic large-scale integration. In Proceedings of the 55th Annual Design Automation Conference (DAC’18). 163:1--163:6.

Digital Library

[53]

Tsun-Ming Tseng, Mengchu Li, Bing Li, Tsung-Yi Ho, and Ulf Schlichtmann. 2016. Columba: Co-layout synthesis for continuous-flow microfluidic biochips. In Proceedings of the 53rd Annual Design Automation Conference (DAC’16). 147:1--147:6.

Digital Library

[54]

Marc Alexander Unger, Hou-Pu Chou, Todd Thorsen, Axel Scherer, and Stephen R. Quake. 2000. Monolithic microfabricated valves and pumps by multilayer soft lithography. Science 288, 5463 (April 2000), 113--116.

[55]

John Paul Urbanski, William Thies, Christopher Rhodes, Saman Amarasinghe, and Todd Thorsen. 2006. Digital microfluidics using soft lithography. Lab-on-a-Chip 6, 1 (2006), 96--104.

[56]

Sidra Waheed, Joan M. Cabot, Niall P. Macdonald, Trevor Lewis, Rosanne M. Guijt, Brett Paull, and Michael C. Breadmore. 2016. 3D printed microfluidic devices: Enablers and barriers. Lab Chip 16, 11 (2016), 1993--2013.

[57]

Junchao Wang, Philip Brisk, and William H. Grover. 2016. Random design of microfluidics. Lab on a Chip 16, 21 (2016), 4212--4219.

[58]

Qin Wang, Hao Zou, Hailong Yao, Tsung-Yi Ho, Robert Wille, and Yici Cai. 2018. Physical co-design of flow and control layers for flow-based microfluidic biochips. IEEE Transactions on CAD of Integrated Circuits and Systems 37, 6 (2018), 1157--1170.

[59]

Richard A. White, Paul C. Blainey, H. Christina Fan, and Stephen R. Quake. 2009. Digital PCR provides sensitive and absolute calibration for high throughput sequencing. BMC Genomics 10, 1 (March 2009), 116.

[60]

Angela R. Wu, Tiara L. A. Kawahara, Nicole A. Rapicavoli, Jan van Riggelen, Emelyn H. Shroff, Liwen Xu, Dean W. Felsher, Howard Y. Chang, and Stephen R. Quake. 2012. High throughput automated chromatin immunoprecipitation as a platform for drug screening and antibody validation. Lab on a Chip 12, 12 (June 2012), 2190--2198.

[61]

Younan Xia and George M. Whitesides. 1998. Soft lithography. Annual Review of Materials Science 28, 1 (1998), 153--184.

[62]

Hailong Yao, Tsung-Yi Ho, and Yici Cai. 2015. PACOR: Practical control-layer routing flow with length-matching constraint for flow-based microfluidic biochips. In Proceedings of the 52nd Annual Design Automation Conference. 142:1--142:6.

Digital Library

[63]

Hailong Yao, Qin Wang, Yizhong Ru, Yici Cai, and Tsung-Yi Ho. 2015. Integrated flow-control codesign methodology for flow-based microfluidic biochips. IEEE Design 8 Test 32, 6 (2015), 60--68.

[64]

Ying Zhu, Bing Li, Tsung-Yi Ho, Qin Wang, Hailong Yao, Robert Wille, and Ulf Schlichtmann. 2018. Multi-channel and fault-tolerant control multiplexing for flow-based microfluidic biochips. In Proceedings of the International Conference on Computer-Aided Design (ICCAD’18). 123.

Digital Library

Cited By

Lashkaripour ARodriguez CMehdipour NMardian RMcIntyre DOrtiz LCampbell JDensmore D(2021)Machine learning enables design automation of microfluidic flow-focusing droplet generationNature Communications10.1038/s41467-020-20284-z12:1Online publication date: 4-Jan-2021
https://doi.org/10.1038/s41467-020-20284-z

Index Terms

Directed Placement for mVLSI Devices

Recommendations

Diagonal Component Expansion for Flow-Layer Placement of Flow-Based Microfluidic Biochips
Special Issue ESWEEK 2017, CASES 2017, CODES + ISSS 2017 and EMSOFT 2017

Continuous flow-based microfluidic devices have seen a huge increase in interest because of their ability to automate and miniaturize biochemistry and biological processes, as well as their promise of creating a programmable platform for chemical and ...
Droplet-routing-aware module placement for cross-referencing biochips
ISPD '10: Proceedings of the 19th international symposium on Physical design

Digital Microfluidic Biochip (DMFB) is a revolutionary technology for performing lab-on-a-chip experiments. Comparing to traditional direct-addressing design of DMFB, Cross-Referencing Biochip is a flexible design which not only helps to reduce pin ...
Seamless joining of porous membrane with thermoplastic microfluidic devices

This paper introduces a novel fabrication method for integrating commercially available porous membranes onto thermoplastic microfluidics devices. This method involves a two-step bonding process that creates a sturdy fusion between the membrane and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal on Emerging Technologies in Computing Systems

ACM Journal on Emerging Technologies in Computing Systems Volume 16, Issue 2

April 2020

261 pages

ISSN:1550-4832

EISSN:1550-4840

DOI:10.1145/3375712

Editor:
Zhaojun Bai
University of California at Davis, USA

Issue’s Table of Contents

Copyright © 2019 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 the author(s) 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 12 December 2019

Accepted: 01 October 2019

Revised: 01 September 2019

Received: 01 July 2018

Published in JETC Volume 16, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

National Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
666
Total Downloads

Downloads (Last 12 months)114
Downloads (Last 6 weeks)29

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lashkaripour ARodriguez CMehdipour NMardian RMcIntyre DOrtiz LCampbell JDensmore D(2021)Machine learning enables design automation of microfluidic flow-focusing droplet generationNature Communications10.1038/s41467-020-20284-z12:1Online publication date: 4-Jan-2021
https://doi.org/10.1038/s41467-020-20284-z

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents