跳到主要內容

臺灣博碩士論文加值系統

(44.221.70.232) 您好!臺灣時間:2024/05/29 10:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:張嘉文
研究生(外文):Jia-WenChang
論文名稱:針對腳位限制介電潤濕晶片之整數線性規劃之障礙物避除繞線演算法
論文名稱(外文):An ILP-based Obstacle-Avoiding Routing Algorithm for Pin-Constrained EWOD chips
指導教授:何宗易
指導教授(外文):Tsung-Yi Ho
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:47
中文關鍵詞:介電潤濕數位微流體繞線障礙物
外文關鍵詞:EWODdigital microfluidicroutingobstacle
相關次數:
  • 被引用被引用:0
  • 點閱點閱:157
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
介電潤濕晶片已成為數位微流體系統中廣為被使用的技術,為了能正確操控晶片,底層繞線是一個相當重要的問題。與傳統超大型積體電路的繞線問題不相同的是,在此晶片中,腳位數是被限制的,因此如何做節省腳位數並且連接訊號源到外部的控制器為一個重要的課題。此外,因為嵌入裝置的使用,在介電潤濕晶片的繞線問題中還面臨到障礙物阻擋問題。然而,現今仍沒有相關研究探討此類問題。因此,我們在這篇論文中提出了相當有效的演算法來解決此問題。我們的方法是基於整數線性規劃以及有效的繞線架構來達成節省腳位數的目的以及尋找可行的繞線結果。此外,針對多層繞線的晶片設計,我們也提出相對應的處理方法。在實驗結果中,我們模擬了數個含有障礙物之實際晶片,並且以我們的方法、文獻的方法、以及一個直覺的方法做比較,我們的演算法展現了高度的可繞性。
Electrowetting-on-dielectric (EWOD) chips have become the most popular actuators, particularly for droplet-based digital microfluidic (DMF) systems. In order to enable the electrical manipulations, wire routing is a key problem in designing EWOD chips. Unlike traditional very-large-scale-integration (VLSI) routing problems, in addition to routing-path establishment on signal pins, the pin-constrained EWOD-chip routing problem must address the issue of signal sharing for pin-count reduction under the practical constraint posed by a limited pin-count supply. Moreover, EWOD-chip designs might incur several obstacles in the routing region due to embedded devices for specific fluidic protocols. However, no existing work considers the EWOD-chip routing with obstacles and therefore lots of manual design efforts are involved. To remedy this insufficiency, we propose in this thesis the first routing algorithm for pin-constrained EWOD chips with obstacle avoidance. The proposed algorithm, based on effective integer-linear-programming (ILP) formulation as well as efficient routing framework, can achieve high routability with a low design complexity. Experimental results based on real-life chips with obstacles demonstrate the high routability of proposed routing algorithm for pin-constrained EWOD chips with obstacle avoidance.
List of Tables vi
List of Figures vii
Chapter 1. Introduction 1
1.1 Previous Work 4
1.2 Our Contributions 5
Chapter 2. Pin-Constrained EWOD-Chip Designs 7
2.1 Broadcast Addressing 7
2.2 Obstacle-Avoiding EWOD-Chip Routing 9
2.3 Problem Formulation 11
Chapter 3. ILP-based Obstacle-Avoiding Routing Algorithm 12
3.1 ILP-Based Routability-Driven Electrode Grouping 13
3.1.1 ILP formulatioin 16
3.1.2 ILP reduction 19
3.2 Wire Routing 20
3.3 Trial Routing 23
3.4 Exemplification 25
3.5 Partial Trial-Routing 27
Chapter 4. Algorithm for Multilayer Designs 30
4.1 Problem Formulation 30
4.2 Algorithm Flow 31
4.3 Nets Redistribution 33
Chapter 5. Experimental Results 36
5.1 Multilayer EWOD chips 39
5.2 Runtime Analysis 39
Chapter 6. Conclusions 44
Bibliography 45
[1] http://www.liquid-logic.com/
[2] http://microfluidics.ee.duke.edu/
[3] http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/
[4] C. J. Alpert, D. P. Mehta, S. S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, CRC Press, 2009.
[5] K. Chakrabarty, Towards fault-tolerant digital microfluidic lab-on-chip: defects, fault modeling, testing, and reconfiguration, Proc. IEEE ICBCS, pp. 329-332, 2008.
[6] R. B. Fair, Digital microfluidics: Is a true lab-on-a-chip possible?,Microfluidics and Nanofluidics, vol. 3, pp. 245-281, 2007.
[7] R. B. Fair, A. Khlystov, T. D. Tailor, V. Ivanov, R. D. Evans, P. B. Griffin, S. Vijay, V. K. Pamula, M. G. Pollack, and J. Zhou, Chemical and Biological Applications of Digital-Microfluidic Devices, IEEE Design and Test, vol. 24, pp. 20-24, 2007.
[8] J.-W. Fang, I.-J. Lin, Y.-W. Chang, and J.-H. Wang, A network-flow-based RDL routing algorithm for flip-chip design, IEEE Trans. Computer-Aided Design, 26(8), Aug, 2007.
[9] C. M. Fiduccia and R.M. Mattheyses, A linear-time heuristic for improving network partitions, Proc. ACM/IEEE DAC, pp. 175-181, 1982.
[10] J. Gong and C. J. Kim, Direct-referencing two-dimensional-array digital microfluidics using multilayer printed circuit board, IEEE J. MEMS, no. 2, pp. 257-264, 2008.
[11] T.-Y. Ho, J. Zeng, and K. Chakrabarty, Digital microfluidic biochips: A vision for functional diversity and more than Moore, Proc. IEEE/ACM ICCAD, pp. 578-585, 2010.
[12] 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, Proc. ACM ISPD, pp. 201-208, 2010.
[13] T.-W. Huang and T.-Y. Ho, A two-stage ILP-based droplet routing algorithm for pin-constrained digital microfluidic biochips, Proc. IEEE/ACM ICCAD, pp. 425-431, 2010.
[14] C. C.-Y. Lin and Y.-W. Chang, ILP-based pin-count aware design methodology for microfluidic biochips, Proc. ACM/IEEE DAC, pp. 258-263, 2009.
[15] 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 MultiLayer Insulators., Sensors and Actuators B: Chemical, pp. 465-470, 2010.
[16] M. G. Pollack, A. D. Shenderov, and R. B. Fair, Electrowetting-based actuation of droplets for integrated microfluidics, LOC, pp. 96-101, 2002.
[17] 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.
[18] F. Su, K. Chakrabarty, and R. B. Fair, Microfluidics based biochips: Technology issues, implementation platforms, and design-automation challenges, IEEE Trans. on CAD, pp. 211-223, 2006.
[19] T. Xu and K. Chakrabarty, Broadcast electrode-addressing for pin-constrained multi-functional digital microfluidic biochips, Proc. ACM/IEEE DAC, pp. 173-178, 2008.
[20] T. Yan and M. D. F. Wong, A correct network flow model for escape routing, Proc. ACM/IEEE DAC, pp. 332-335, 2009.
[21] T. Yan and M. D. F. Wong, Optimal simultaneous pin assignment and escape routing for dense PCBs, Proc. ACM/IEEE ASP-DAC, pp. 275-280, 2010.
[22] Y. Zhao and K. Chakrabarty, Co-optimization of droplet routing and pin assignment in disposable digital microfluidic biochips, Proc. ACM ISPD, pp. 69-76, 2011.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊