數位微流體晶片上高可繞性與高效能之液珠繞線模擬方法

A Routability-and Performance-Driven Droplet Routing Simulator for Digital Microfluidic Biochips

黃琮蔚 ； 林俊賢 ； 蔡季紘 ； 何宗易

《國家奈米元件實驗室奈米通訊》 17卷1期 (2010/03) Pp. 57-64

https://doi.org/10.29913/NDLC.201003.0009

摘要

隨著微流體科技的進步，數位微流體生物晶片(Digital Microfluidic Biochips, DMFB)的發展已被預期在短期內會有顯著的突破。在這顯著的突破中，其中一個關鍵的挑戰是使用時間多工的方法(Time-Multiplexedmanner)安排各個液珠(Droplet)在生物晶片上的繞線問題(Droplet Routing Problem)。基於此關鍵性的問題，我們提出一個擁有高度可繞性(Routability)與效能(Performance)的液珠繞線模擬方法，其主要貢獻如下3點：1.利用全域的(Global)液珠移動向量來建構優先繞線路徑(Preferred Routing Tracks)以減少晶片單元(Cell)的使用數量。2.利用液珠的繞線資源，決定液珠的繞線順序(Routing Order)，以得到較佳的繞線結果。3.利用動態程式規畫(Dynamic Programming)的方式模擬液珠繞線路徑壓縮(Routing Compaction)的技術以減少整體的繞線執行時間。

關鍵字

生物晶片 ； 微流體 ； 繞線 ； 動態程式規劃

並列摘要

As the microfluidic technology advances, digital microfluidic biochips (DMFB) have recently gained much attention and are expected to revolutionize the biological laboratory procedure. One of the most critical challenges for DMFB design is the droplet routing problem, which schedules the movement of each droplet in a time-multiplexed manner. Therefore, we propose a fast routability-and performance-driven droplet routing algorithm for digital microfluidic biochips design. To reduce the routing complexities and the used cells, we first construct preferred routing tracks by analyzing the global moving vector of droplets to guide the droplet routing. Then, using an entropy-based equation determines the routing order of droplets for better routability. Finally, a routing compaction technique by dynamic programming to minimize the latest arrival time of droplets.

並列關鍵字

Biochip ； Microfluidic ； Routing ； Dynamic Programming