介電潤濕晶片已成為數位微流體系統中廣為被使用的技術，為了能正確操控晶片，底層繞線是一個相當重要的問題。與傳統超大型積體電路的繞線問題不相同的是，在此晶片中，腳位數是被限制的，因此如何做節省腳位數並且連接訊號源到外部的控制器為一個重要的課題。此外，因為嵌入裝置的使用，在介電潤濕晶片的繞線問題中還面臨到障礙物阻擋問題。然而，現今仍沒有相關研究探討此類問題。因此，我們在這篇論文中提出了相當有效的演算法來解決此問題。我們的方法是基於整數線性規劃以及有效的繞線架構來達成節省腳位數的目的以及尋找可行的繞線結果。此外，針對多層繞線的晶片設計，我們也提出相對應的處理方法。在實驗結果中，我們模擬了數個含有障礙物之實際晶片，並且以我們的方法、文獻的方法、以及一個直覺的方法做比較，我們的演算法展現了高度的可繞性。

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.

[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.