進階搜尋


下載電子全文  
系統識別號 U0026-1107201111421600
論文名稱(中文) 數位微流體生物晶片之繞線方法:流體層級導向晶片層級
論文名稱(英文) Routing for Digital Microfluidic Biochips:From Fluidic-Level toward Chip-Level
校院名稱 成功大學
系所名稱(中) 資訊工程學系碩博士班
系所名稱(英) Institute of Computer Science and Information Engineering
學年度 99
學期 2
出版年 100
研究生(中文) 黃琮蔚
研究生(英文) Tsung-Wei Huang
電子信箱 twhuang@eda.csie.ncku.edu.tw
學號 p76994034
學位類別 碩士
語文別 英文
論文頁數 128頁
口試委員 指導教授-何宗易
口試委員-Krishnendu Chakrabarty
口試委員-曾新穆
口試委員-張耀文
中文關鍵字 數位微流體生物晶片  繞線  電腦輔助設計 
英文關鍵字 Digital microfluidic biochip  Routing  Computer-aided design 
學科別分類
中文摘要 數位微流體生物晶片已經為近代生物科技帶來革命性的發展,其為許多實驗程序提供了一個高效能、自動化的操控平台。數位微流體生物晶片能夠精準地操控微米或奈米尺度體積的微流體,也就是所謂的液珠,來攜帶生化樣本或試劑進行反應。其應用囊括分子生物學、分析化學、生物測定以及樣品的製備等等。與日俱增的應用急遽地提高了晶片的設計複雜度,迫使傳統勞力密集的設計方法面臨到嚴重的低效率開發問題;因此,電腦輔助設計儼然成為不可或缺的元素。數位微流體生物晶片的電腦輔助設計流程主要分為流體層級的液珠行為合成以及晶片層級的電訊號規劃兩大步驟。其中,流體層級的液珠繞線以及晶片層級的訊號線繞線分別為兩大關鍵性的設計考量。液珠繞線主要在決定液珠的行為去實現給定的反應程序,其主導了整個晶片運作效能;訊號線繞線則是探討晶片底層控制電極的訊號連接以及傳輸,對於製程複雜度以及生產成本有巨大的影響。然而,此二繞線問題已被證明為計算機理論中最困難的問題,也就是所謂NP 等級的問題;再者,諸多複雜的設計限制加上橫跨流體和晶片範疇的考量,更是為此二繞線問題增加更進一步的困難度。因此,解決此二繞線問題必須仰賴特殊且有效的電腦輔助設計演算法。在本篇論文中,我們提出了以網路流為基礎的演算法,先後對流體層級的液珠繞線以及晶片層級的訊號線繞線提出了電腦輔助設計的解決方法。實驗結果展示了我們所提出的液珠繞線演算法能夠精準無誤地操控液珠完成所有生化反應,達成檢測最佳化,提高晶片檢測運作效能;實驗結果也展示了我們所提出的訊號線繞線演算法能夠快速地對控制電極建立正確的訊號傳遞,同時降低訊號線連接所產生的製程複雜度,大幅降低晶片生產成本。這些結果展示了我們所提出的演算法能夠有效地解決此兩大關鍵性的繞線問題。我們相信我們所提出的電腦輔助設計演算法,除了能大幅度地改善傳統勞力密集設計下所產生的耗時、費力、高成本、低效能的問題之外,更加速了數位微流體晶片從實驗室研發到成功商品化的運行時間。
英文摘要 Advances in droplet-based digital microfluidic biochips (DMFBs) have led to the emergence of biochips for automating laboratory procedures in biochemistry and molecular biology. These devices enable the precise control of micro-liter or nano-liter volumes of biochemical samples and reagents. They combine electronics with biology, and integrate various bioassay operations, such as sample preparation, analysis, separation, and detection. To meet the challenges of increasing design complexity, computer-aided-design (CAD) tools have been involved to build DMFBs efficiently, where a two-stage design methodology of fluidic-level synthesis followed by chip-level design are generally applied. Along with the CAD methodology, droplet routing in fluidic level and wire routing in chip level are two fairly critical design problems. Droplet routing, dealing with the fluidic behaviors on a DMFB, has great impact on the entire assay performance. Wire routing, establishing electrical connections of signal wires among the underlying electrodes, primarily dominates the manufacturing complexity and fabrication cost. However, solving these two routing problems is non-trivial due to the NP-complete property involved and thus is computationally expensive. Complex objectives and constraints that span fluidic domain and electrical domain impose significant difficulties on solving the two routing problems. Due to the distinctive nature of DMFB technology, the two routing problems are quite different from traditional VLSI counterparts. Specialized and dedicated CAD tools are thus necessary to be developed. In this thesis, we propose two CAD algorithms which are based on effective flow network to solve the droplet routing and wire routing problems. Experimental results demonstrate that our droplet routing algorithm can achieve 100% routing completion with maximized assay performance. Also, our wire routing algorithm can correctly establish the signal connections among electrodes while maintaining a minimum manufacturing complexity thereby a low-cost fabrication. Furthermore, our CAD algorithms can complete each routing benchmark by less than 1 minute, which are very efficient. The authors believe that the proposed CAD algorithms can significantly remove the design burden incurred from time-consuming and high-cost manual design manners, accordingly establishing an efficient development pathway from technology to commercialization.
論文目次 List of Tables viii
List of Figures ix
Chapter 1. Introduction 1
1.1 Continuous-Flow Microfluidic Biochip 3
1.2 Digital Microfluidic Biochip 4
1.3 Computer-Aided Design 13
1.4 Design Problems and Challenges 17
Chapter 2. Thesis Contributions 21
Chapter 3. Fluidic-Level Routing 29
3.1 Droplet Routing 29
3.2 Cross-Contamination Avoidance 33
3.3 Problem Formulation 36
3.4 Related Works 36
3.5 Algorithm 38
3.5.1 Preprocessing Stage 40
3.5.2 Intra-Contamination Aware Routing Stage 47
3.5.3 Inter-Contamination Aware Routing Stage 62
3.6 Experimental Results 66
Chapter 4. Chip-Level Routing 70
4.1 EWOD-Chip Routing 70
4.2 Previous Works 74
4.3 Preliminaries 75
4.3.1 Digital Microfluidics and EWOD Chips 75
4.3.2 Broadcast Addressing 76
4.4 Design Challenges 78
4.4.1 Broadcast Constraints 80
4.4.2 Routing Constraints 81
4.5 Problem Formulation 82
4.6 Algorithm 83
4.6.1 Electrode Grouping Method 84
4.6.2 Pin-Count Aware Global Routing 84
4.6.3 Progressive Routing Scheme 92
4.6.4 Readdressing and Rerouting Refinement 102
4.7 Experimental Results 105
Chapter 5. Conclusions 110
Bibliography 114
Appendix 123
Appendix A. Biography 124
參考文獻 [1] Advanced Liquid Logic, http://www.liquid-logic.com
[2] Nanotechnology News, http://www.nanotech-now.com/
[3] Ultimate Printed Circuit Design, http://www.ultimatepcb.com/
[4] Printed Circuit Design Magazine, http://pcdandf.com/cms/home
[5] Silicon Bioaystems, http://www.siliconbiosystems.com/
[6] International Technology Roadmap for Semiconductors (ITRS), http://public.itrs.net/Files/2003ITRS/Home2003.htm
[7] C. J. Alpert, D. P. Mehta, S. S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, CRC Press, 2009.
[8] R. Bellman, “Dynamic programming treatment of the travelling salesman problem,”Journal of ACM, pp. 61--63, 1962.
[9] K. F. Bohringer, “Modeling and controlling parallel tasks in droplet based microfluidic systems,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, pp. 334--344, 2006.
[10] M. A. Burns, B. N. Johnson, S. N. Brahmasandra, K. Handique, J. R. Webster, M. Krishnan, T. S. Sammarco, P. M. Man, D. Jones, D. Heldsinger, C. H. Mastrangelo, and D. T. Burke, “An integrated nanoliter DNA analysis device,” Science, vol. 282, no. 5388, pp. 484--487, 1998.
[11] K. Chakrabarty, “Towards fault-tolerant digital microfluidic lab-on-chip: defects,
fault modeling, testing, and reconfiguration,” Proceedings of IEEE International Conference on Biomedical Circuits and Systems, pp. 329--332, 2008.
[12] K. Chakrabarty, “Design automation and test solutions for digital microfluidic biochips,” IEEE Transactions on Circuits and Systems I, vol. 57, pp. 4--17, 2010.
[13] M. Cho and D. Z. Pan, “BoxRouter: a new global router based on box expansion and progressive ILP,”Proceedings of ACM/IEEE Design Automation Conference, pp. 373--378, 2006.
[14] 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, pp. 1714--1724, 2008.
[15] S. K. Cho, S.-K. Fan, H. Moon, and C. J. Kim, “Towards digital microfluidic circuits: Creating, transporting, cutting and merging liquid droplets by electrowetting-based actuation,” Proceedings of IEEE Microelectromechanical Systems, pp. 32--35, 2002.
[16] 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,” ACS Journal of Langmuir, no. 25, pp. 147--152, 2009.
[17] D. Eppstein, “Finding the k shortest paths,” Proceedings of IEEE Symposium on Foundations of Computer Science, pp. 154--165, 1994.
[18] B. S. Gallardo, V. K. Gupta, F. D. Eagerton, L. I. Jong, V. S. Craig, R. R. Shah, and N. L. Abbott, “Electrochemical principles for active control of liquids on submillimeter scales,” Science, vol. 27, no. 5398, pp. 57--60, 1999.
[19] A. V. Goldberg and R. E. Tarjan, “Finding minimum cost circulations by canceling negative cycles,” Journal of ACM , pp. 873--886, 1989.
[20] J. Gong and C. J. Kim, “Two-dimensional digital microfluidic system by multi-layer printed circuit board,” Proceedings of IEEE Microelectromechanical Systems, pp. 726--729, 2005.
[21] J. Gong and C. J. Kim, “Direct-referencing two-dimensional-array digital microfluidics using multilayer printed circuit board,” IEEE Journal of Microelectromechanical Systems, no. 2, pp. 257--264, 2008.
[22] E. J. Griffith, S. Akella, and M. K. Goldberg, “Performance characterization of a reconfigurable planar-array digital microfluidic system,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, pp. 345--357, 2006.
[23] J. L. Gross, and J. Yellen, Graph Theory and Its Application, CRC Press, FL, 1999.
[24] T.-Y. Ho, J. Zeng, and K. Chakrabarty, “Digital microfluidic biochips: A vision for functional diversity and more than Moore,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 578--585, 2010.
[25] T.-W. Huang and T.-Y. Ho, “A fast routability- and performance-driven droplet routing algorithm for digital microfluidic biochips,” Proceedings of IEEE International Conference on Computer Design, pp. 445--450, 2009.
[26] T.-W. Huang, C.-H. Lin, and T.-Y. Ho, “A contamination-aware droplet routing algorithm for digital microfluidic biochips,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 151--156, 2009.
[27] T.-W. Huang and T.-Y. Ho, “A two-stage ILP-based droplet routing algorithm for pin-constrained digital microfluidic biochips,” Proceedings of ACM International Symposium on Physical Design, pp. 201--208, 2010.
[28] T.-W. Huang, S.-Y. Yeh, and T.-Y. Ho, “A network-flow based pin-count aware routing algorithm for broadcast electrode-addressing EWOD chips,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 425--431, 2010.
[29] 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, pp. 1682--1695, 2010.
[30] T.-W. Huang and T.-Y. Ho, “A two-stage ILP-based droplet routing algorithm for pin-constrained digital microfluidic biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 30, pp. 215--228, 2011.
[31] 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, to be appeared.
[32] T.-W. Huang, H.-Y. Su, and T.-Y. Ho, “Progressive network-flow based power-aware broadcast addressing for pin-constrained digital microfluidic biochips,” Proceedings of ACM/IEEE Design Automation Conference, pp. 741--746, 2011.
[33] T.-W. Huang, Y.-Y. Lin, J.-W. Chang, and T.-Y. Ho, “Chip-level design and optimization for digital microfluidic biochips,” Proceedings of IEEE International Midwest Symposium on Circuits and Systems, 2011.
[34] T.-W. Huang, Y.-Y. Lin, J.-W. Chang, and T.-Y. Ho, “Recent Research and Emerging Challenges in Design and Optimization for Digital Microfluidic Biochips,” Proceedings of IEEE International System-on-Chip Conference, 2011.
[35] T.-W. Huang, T.-Y. Ho, and K. Chakrabarty, “Reliability-oriented broadcast addressing for pin-constrained digital microfluidic biochips,”Proceedings of IEEE/ACM International Conference on Computer-Aided Design, 2011.
[36] H. F. Hull, R. Danila, and K. Ehresmann, “Smallpox and bioterrorism: Public-health responses,” Journal of Laboratory and Clinical Medicine, vol. 142, no. 4, pp. 221--228,
2003.
[37] D. S. Johnson, “Approximation algorithms for combinatorial problems,” Journal of Computer and System Sciences, pp. 256--278, 1974.
[38] T. B. Jones, M. Gunji, M. Washizu, and M. J. Feldman, “Dielectrophoretic liquid actuation and nanodroplet formation,” Journal of Applied Physics, pp. 1441--1448, 2001.
[39] A. Kerber, F. Cartier, R. Degraeve, P. J. Roussel, L. Pantisano, T. Kauerauf, G. Groeseneken, H. E. Maes, and U. Schwalke, “Charge trapping and dielectric reliability of SiO2-Al2O3 gate stacks with TiN electrodes,” IEEE Transactions on Electron Devices, no. 50, pp. 1261--1269, 2003.
[40] R.-W. Liao and T.-H. Yang, “Design and fabrication of biochip for in-situ protein synthesis,” Master Thesis, Department of Optics and Photonics, National Central University, Taiwan, 2008.
[41] C. C.-Y. Lin and Y.-W. Chang, “ILP-based pin-count aware design methodology for microfluidic biochips,” Proceedings of ACM/IEEE Design Automation Conference, pp. 258--263, 2009.
[42] Y.-Y. Lin, R. D. Evans, E. Welch, B.N. Hsu, A. C. Madison, and R. B. Fair, “Low voltage electrowetting-on-dielectric platform using multi-layer insulators,”Sensors and Actuators B: Chemical, pp. 465--470, 2010.
[43] E. Maftei, P. Paul, and J. Madsen, “Tabu search-based synthesis of dynamically reconfigurable digital microfluidic biochips,” Proceedings of ACM International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, pp. 195--203, 2009.
[44] H. Moon, A. R. Wheeler, R. L. Garrell, J.A. Loo, and C. J. Kim, “An integrated digital microfluidic chip for multiplexed proteomic sample preparation and analysis by MALDI-MS,” Lab on Chip, vol. 6, pp. 1213--1219, 2006.
[45] M. G. Pollack, Electrowetting-based microactuation of droplets for digital microfluidics, Ph.D. thesis, Department of Electrical and Computer Engineering, Duke University, Durham, NC, 2001.
[46] M. G. Pollack, A. D. Shenderov, and R. B. Fair, “Electrowetting-based actuation of droplets for integrated microfluidics,” Lab on Chip, vol. 2, pp. 96--101, 2002.
[47] T. S. Sammarco and M. A. Burns, “Thermocapillary pumping of discrete droplets in microfabricated analysis devices,” AIChe Journal, pp. 350--366, 1999.
[48] T. H. Schulte, R. L. Bardell, and B. H. Weigl, “Microfluidic technologies in clinical diagnostics,” Journal of Clinical Chemistry, vol. 321, no. 1, pp. 1--10, Jul. 2002.
[49] R. Sista, Z. Hua, P. Thwar, A. Sudarsan, V. Srinivasan, A. E. Eckhardt, M. Pollack, and V. Pamula, “Development of a digital microfluidic platform for point of care testing,” Lab on Chip, no. 8, pp. 2091--2104, 2008.
[50] J. H. Song, R. Evans, Y. Y. Lin, B. N. Hsu, and R. B. Fair, “A scaling model for electrowetting-on-dielectric microfluidic actuators,” Microfluidics and Nanofluidics, pp. 75--89, 2009.
[51] V. Srinivasan, V. K. Pamula, M. G. Pollack, and R. B. Fair, “A digital microfluidic biosensor for multianalyte detection,” Proceedings of IEEE Microelectromechanical Systems, pp. 327--330, 2003.
[52] 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 on Chip, vol. 4, no. 4, pp. 310-–315, 2004.
[53] F. Su and K. Chakrabarty, “Architectural-level synthesis of digital microfluidics-based biochips,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 223--228, 2004.
[54] F. Su and K. Chakrabarty, “Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips,” Proceedings of ACM/IEEE Design Automation Conference, pp. 825--830, June 2005.
[55] F. Su and K. Chakrabarty, “Design of fault-tolerant and dynamically reconfigurable microfluidic biochips,” Proceedings of IEEE/ACM Design, Automation, and Test in Europe, pp. 223--228, 2005.
[56] 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, pp. 211--223, 2006.
[57] F. Su, W. Hwang, and K. Chakrabarty, “Droplet routing in the synthesis of digital microfluidic biochips,” Proceedings of IEEE/ACM Design, Automation, and Test in Europe, pp. 1--6, 2006.
[58] F. Su and K. Chakrabarty, “Module placement for fault-tolerant microfluidics-based biochips,” ACM Transactions on Design Automation of Electronic Systems, vol. 11, pp. 682--710, 2006.
[59] T. Thorsen, S. Maerkl, and S. Quake, “Microfluidic large-scale integration,” Science, vol. 298, no. 5593, pp. 580--584, 2002.
[60] J. Y. Toon and R. L. Garrell, “Preventing biomolecular adsorption in electrowetting-based biofluidic chips,” Analytical Chemistry, vol. 75, pp. 5097--5102, 2003.
[61] S. Venkatesh and Z. A. Memish, “Bioterrorism: A new challenge for public health,” Journal of Antimicrobial Agents, vol. 21, no. 2, pp. 200--206, 2003.
[62] H. J. J. Verheijen and M. W. J. Prins, “Reversible electrowetting and trapping of charge: model and experiments,” ACS Journal of Langmuir, no. 15, pp. 6616--6620, 1999.
[63] E. Verpoorte and N. F. De Rooij, “Microfluidics meets MEMS,” Proceedings of IEEE, vol. 91, no. 6, pp. 930--953, 2003.
[64] T. Xu and K. Chakrabarty, “Droplet-trace-based array partitioning and a pin assignment algorithm for the automated design of digital microfluidic biochips,” Proceedings of International Conference on Hardware/Software Codesign and System Synthesis, pp. 112--117, 2006.
[65] T. Xu and K. Chakrabarty, “Broadcast electrode-addressing for pin-constrained multi-functional digital microfluidic biochips,” Proceedings of ACM/IEEE Design Automation Conference, pp. 173--178, 2008.
[66] T. Xu, K. Chakrabarty and V. K. Pamula, “Design and optimization of a digital microfluidic biochip for protein crystallization,” Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pp. 297--301, 2008.
[67] T. Xu and K. Chakrabarty, “A droplet-manipulation method for achieving high-throughput in cross-referencing-based digital microfluidic biochips,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, pp. 1905--1917, 2008.
[68] T. Xu and K. Chakrabarty, “Automated design of digital microfluidic lab-on-chip under pin-count constraints,” Proceedings of ACM International Symposium on Physical Design, pp. 90--98, 2008.
[69] T. Xu, K. Chakrabarty and V. K. Pamula, “Defect-tolerant design and optimization of a digital microfluidic biochip for protein crystallization,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2010.
[70] P.-H. Yuh, C.-L. Yang, and Y.-W. Chang, “Placement of defect-tolerant digital microfluidic biochips using the T-tree formulation,” ACM Journal of Emerging Technology, vol. 3, 2007.
[71] 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, pp. 1928--1941, 2008.
[72] T. Zhang, K. Chakrabarty, and R. B. Fair, Microelectrofluidic Systems: Modeling and Simulation, Boca Raton, FL, CRC Press, 2002.
[73] Y. Zhao and K. Chakrabarty, “Cross-contamination avoidance for droplet routing in digital microfluidic biochips,” Proceedings of IEEE/ACM Design, Automation, and Test in Europe, pp. 1290--1295, 2009.
[74] Y. Zhao, R. Sturmer, K. Chakrabarty and V. K. Pamula, “Optimization of droplet routing for an n-plex bioassay on a digital microfluidic lab-on-chip,” Proceedings of IEEE International Conference on Biomedical Circuits and Systems, pp. 241--244, 2009.
[75] Y. Zhao, R. Sturmer, K. Chakrabarty and V. K. Pamula, “Synchronization of concurrently-implemented fluidic operations in pin-constrained digital microfluidic biochips,” IEEE International Conference on VLSI Design, pp. 69--74, 2010.
[76] Y. Zhao and K. Chakrabarty, “Co-optimization of droplet routing and pin assignment in disposable digital microfluidic biochips,” Proceedings of ACM International Symposium on Physical Design, pp. 69--76, 2011.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2012-07-22起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2012-07-22起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw