An ILP-Based Routing Algorithm for Pin-Constrained EWOD Chips With Obstacle Avoidance
| Autor: | Sheng-Han Yeh, Tsung-Wei Huang, Tsung-Yi Ho, Jia-Wen Chang |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Very-large-scale integration
Engineering Linear programming business.industry Hardware_PERFORMANCEANDRELIABILITY Computer Graphics and Computer-Aided Design Reduction (complexity) Embedded system Obstacle avoidance Hardware_INTEGRATEDCIRCUITS Key (cryptography) Electrical and Electronic Engineering Routing (electronic design automation) business Biochip Integer programming Software |
| Zdroj: | IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 32:1655-1667 |
| ISSN: | 1937-4151 0278-0070 |
| DOI: | 10.1109/tcad.2013.2269767 |
| Popis: | Electrowetting-on-dielectric (EWOD) chips have become the most popular actuators, particularly for droplet-based digital microfluidic biochip (DMFB) 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 a 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 paper 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 algorithm for pin-constrained EWOD chips with obstacle avoidance. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|