ACER: An Agglomerative Clustering Based Electrode Addressing and Routing Algorithm for Pin-Constrained EWOD Chips

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.