ACER: An Agglomerative Clustering Based Electrode Addressing and Routing Algorithm for Pin-Constrained EWOD Chips
- 18 August 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 33 (9), 1316-1327
- https://doi.org/10.1109/tcad.2014.2329415
Abstract
The problem of pin-constrained electrowetting-ondielectric (EWOD) biochips becomes a serious issue to realize complex bio-chemical operations. Due to limited number of control pins and routing resources, additional Printed Circuit Board (PCB) routing layers may be required which potentially raises the fabrication cost. Previous state-of-the-art work has tried to develop a framework that uses a network-flow-based method for broadcast electrodeaddressing EWOD biochips. Nevertheless, greedily merging of electrical pins in previous works is at high risk of producing unroutable design. Routability should have higher priority than pin reduction. While previous works dedicated their effort on pin reduction, we have addressed our attention on routability of broadcast addressing. Experimental results demonstrate that taking routability into consideration can even have higher pin reduction. Viewed in this light, we present ACER, a routability driven clustering algorithm followed by escape routing using integer linear programming that effectively solves both pin merging and routing in broadcast addressing framework. Our proposed algorithm does not greedily focus on pin-reduction. Instead, routability is taken into consideration through agglomerative clustering. Compared to previous state-of-the-art, our proposed algorithm can further reduce required control pins by an average of 13% and route the design using 68% less wirelength.Keywords
This publication has 17 references indexed in Scilit:
- Voltage-aware chip-level design for reliability-driven pin-constrained EWOD chipsPublished by Association for Computing Machinery (ACM) ,2012
- An ILP-based obstacle-avoiding routing algorithm for pin-constrained EWOD chipsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2012
- Reliability-oriented broadcast electrode-addressing for pin-constrained digital microfluidic biochipsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Broadcast electrode-addressing for pin-constrained multi-functional digital microfluidic biochipsPublished by Association for Computing Machinery (ACM) ,2008
- Direct-Referencing Two-Dimensional-Array Digital Microfluidics Using Multilayer Printed Circuit BoardJournal of Microelectromechanical Systems, 2008
- Hierarchical Clustering via Joint Between-Within Distances: Extending Ward's Minimum Variance MethodJournal of Classification, 2005
- Reducibility among Combinatorial ProblemsPublished by Springer Science and Business Media LLC ,1972
- Hierarchical Grouping to Optimize an Objective FunctionJournal of the American Statistical Association, 1963
- Hierarchical Grouping to Optimize an Objective FunctionJournal of the American Statistical Association, 1963
- An Algorithm for Path Connections and Its ApplicationsIEEE Transactions on Electronic Computers, 1961