進階搜尋


 
系統識別號 U0026-2301201101300900
論文名稱(中文) 使用遞延決策技術於數位微流體生物晶片之合成及擺置
論文名稱(英文) Synthesis and Placement of Digital Microfluidic Biochips Using Deferred Decision Making Technique
校院名稱 成功大學
系所名稱(中) 電機工程學系碩博士班
系所名稱(英) Department of Electrical Engineering
學年度 99
學期 1
出版年 100
研究生(中文) 鄭為溢
研究生(英文) Wei-Yi Cheng
學號 n2697142
學位類別 碩士
語文別 英文
論文頁數 40頁
口試委員 指導教授-林家民
口試委員-何宗易
口試委員-陳泰蓁
中文關鍵字 微流體生物晶片  三維擺置  泛化分割樹 
英文關鍵字 Microfluidic Biochip  3D Placement  Generalized Slicing Tree 
學科別分類
中文摘要 即使過去有許多的研究投入在微流體生物晶片中,但由於其問題的複雜度,目前關於微流體生物晶片之合成及擺置的相關論文仍相當有限。這個問題中,我們需要最佳化的安排每一個操作步驟的工作時間、決定每一個操作步驟的使用的資源及產生三維固定框架之擺置結果。為了要處理這個問題,我們使用一個形曲線集合來紀錄三維的擺置結果,並解說我們如何合併形兩個曲線集合及使用泛化分割樹列舉所有可能的擺置結果。我們的法方可同時做三維固定框架之擺置及為每一個操作步驟做資源的綁定。除此之外,我們提出一個程序可於合併中檢查是否有違反操作步驟的先後限制,及一個方式去修正這個不合法的結果,如此一來就有較高的機會得到較好的解。最後,我們介紹使用特殊資源之操作步驟的特性及其擺置。此外,我們提出一個方法去解決超出使用資源的問題,且確保最後的結果也要能有足夠空間擺置儲存單元。實驗結果顯示我們的方法比起Unified Synthesis and Placement 和以T-tree 為基礎的方法能得到較好結果且來得較有效率。
英文摘要 Although several researches have been done on droplet-based microfluidic biochips, there exist limited works considering microfluidic module placement problem due to its great complexity. In such problem, we should determine an optimized schedule of bioassay operations, bind assay operations to resources, and create a 3D fixed outline layout. To deal with these issues, we use a shape curve set to record placement results in 3D space and show how to merge two curve sets to enumerate possible placements in a general slicing tree. In our method, the resource binding and 3D placement can be done simultaneously.
Furthermore, we propose a procedure to check violations of precedence constraints while merging, and then present a method to modify violations so that we have a higher probability to get good solutions. Finally, we introduce properties of resource operations and resource operation placement. In addition, we purpose a method to eliminate violation of resource constraints and ensure final result satisfy storage unit constraints. Experimental results demonstrate that our approach is more efficient and effective compared with the unified synthesis and placement framework and T-tree based approach.
論文目次 Chinese Abstract i
Abstract iii
List of Tables vi
List of Figures vii
Chapter 1. Introduction ................. 1
1.1 Previous Work ....................... 3
1.2 Our Contribution .................... 4
Chapter 2. Problem Formulation .......... 6
Chapter 3. Slicing Tree Representation .. 9
3.1 Review of Slicing Tree .............. 9
3.2 3D Generalized Slicing Tree ........ 10
Chapter 4. Overview of Our Algorithm ... 13
Chapter 5. Curve Set Merge ............. 15
5.1 Plane Merge ........................ 16
5.2 Upright Merge ...................... 18
5.3 Bind Curve ......................... 19
5.4 Precedence Constraint .............. 21
Chapter 6. Resource Constraint ......... 24
Chapter 7. Resource Operation Placement 27
7.1 Detection Operation Placement ...... 28
7.2 Source Operation Placement ......... 29
7.3 Check Storage Unit Constraint ...... 30
Chapter 8. Experimental Results ........ 32
Chapter 9. Conclusion .................. 38
Bibliography ........................... 39
參考文獻 [1] Cheng, L., Deng, L., and Wang, M. D. F.."Floorplanning for 3-d VLSI design." In Proc. of ASP-DAC, pages 405-411, 2005.
[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 Proc. IEDM, pages 32.5.1-32.5.4, 2003.
[3] R. B. Fair, "Digital microfluidics: Is a true lab-on-a-chip possible." Microfluidics and Nanofluidics, vol. 3, pages. 245-281, 2007.
[4] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. "Optimization by simulated annealing." Science, 220(4598):671-680, May 1983.
[5] G. Karypis and V. Kumar. "Multilevel K-way Hypergraph Partitioning." In Proc. DAC, pages 343-348, 1999.
[6] E. Maftei, P. Paul, and J. Madsen, "Tabu search-based synthesis of dynamically reconfgurable digital microfluidic biochips," in Proceedings of the Compilers, Architecture, and Synthesis for Embedded Systems Conference, 2009, pages 195-203.
[7] R.H.J.M. Otten. "Automatic floorplan design." In Proc. of DAC, pages 261-267, June 1982.
[8] Ricketts, A. J., Irick, K., Vijaykrishnan, N., and Irwin, M. J. "Priority scheduling in digital microfluidics-based biochips. In Proceedings of Design." Automation and Test in Europe., pages 329-334, 2006.
[9] F. Su and K. Chakrabarty. "Architectural-level synthesis of digital microfluidics-based biochips." In Proc. ICCAD, pages 223-228, Nov. 2004.
[10] V. Srinivasan, V. Pamula, P. Paik, and R. Fair. "Protein stamping for maldi mass spectrometry using an electrowetting-based microfluidic platform." In Proc. SPIE, pages 26-32, 2004.
[11] F. Su and K. Chakrabarty. "Design of fault-tolerant and dynamically-reconfigurable microfluidic biochips." In Proc. DATE, pages 1202-1207, March 2005.
[12] F. Su and K. Chakrabarty. "Unified high-level synthesis and module placement for defect-tolerant microfluidic biochips." In Proc. DAC, pages 825-830, June 2005.
[13] P. Yuh, C. Yang, and Y. 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, article 13, 2007.
[14] Jackey Z. Yan and Chris Chu. "DeFer: Deferred decision making enabled fixed-outline floorplanner." In Proc. of DAC, pages 161-166, June 2008.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2016-01-31起公開。
  • 同意授權校外瀏覽/列印電子全文服務,於2016-01-31起公開。


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