考慮可繞線度之數位微流體生物晶片叢集演算法

Abstract

在此篇論文中，我們主要針對微流體生物晶片做一個探討。在晶片設計越來 越複雜的狀況下，如何有效的在微流體生物晶片上減少針腳的使用量，以減少製 作的成本已經變成一個重要的議題。在此篇論文中，我們提出了一個考慮可繞線 度的叢集演算法，在叢集的過程中，我們會針對每個針腳做有效的估計，決定出 一組最適合的繞線順序。並且我們在繞線過程中，會考慮到每一條路徑的擁擠程 度。試著將比較擁擠的地方給予一些空間，使的後面的繞線路徑更為順暢。最後 我們提出了一個線性規畫的逃脫繞線演算法，我們的演算法同時可以實現在有障 礙物的晶片上。在我們的演算法中平均可以減少11%針腳的使用量，同時繞線長 度也有151%的降幅。

With the increasing design complexities, the design of pin-constrained electrowetting-on-dielectric (EWOD) biochips is of practical importance for the emerging market-place. However, as the system complexity increases, the number of control pads also rapidly increases that may necessitate multiple PCB layers, which potentially raise the price of fabrication cost. To tackle this problem, we present ACER, an agglomerative clustering-based electrode addressing and routing algorithm for pin-constrained EWOD chip that solves both pin merging and routing effectively. An agglomerative clustering technique is applied to determine merging priority of electrical pins. Furthermore, in consideration of routability, we propose an effective estimation method to incorporate routability to our objective during clustering. At routing stage, we formulate the consequent multi-source multi-sink escape routing problem using a set of integer linear constraints. Our algorithm can handle designs with and without obstacles. Compared to work [8] without considering presence of obstacles, ACER can further reduce activation sequences by 11% with 151% reduction in routed wirelength within comparable execution time. In comparison with obstacle aware algorithm proposed in [3], our algorithm can achieve equivalent reduction using 25% less routed wirelength.