ACER: An agglomerative clustering based electrode addressing and routing algorithm for pin-constrained EWOD chips

Sean Shih Ying Liu, Chung Hung Chang, Hung-Ming Chen, Tsung Yi Ho

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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.

Original languageEnglish
Article number6879599
Pages (from-to)1316-1327
Number of pages12
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
StatePublished - 1 Jan 2014


  • Agglomerative clustering
  • broadcast addressing
  • electrowetting-on-dielectric
  • pin-constrained.

Fingerprint Dive into the research topics of 'ACER: An agglomerative clustering based electrode addressing and routing algorithm for pin-constrained EWOD chips'. Together they form a unique fingerprint.

Cite this