Title: ACER: An Agglomerative Clustering Based Electrode Addressing and Routing Algorithm for Pin-Constrained EWOD Chips
Authors: Liu, Sean Shih-Ying
Chang, Chung-Hung
Chen, Hung-Ming
Ho, Tsung-Yi
電子工程學系及電子研究所
Department of Electronics Engineering and Institute of Electronics
Keywords: Agglomerative clustering;broadcast addressing;electrowetting-on-dielectric;pin-constrained
Issue Date: 1-Sep-2014
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.
URI: http://dx.doi.org/10.1109/TCAD.2014.2329415
http://hdl.handle.net/11536/123988
ISSN: 0278-0070
DOI: 10.1109/TCAD.2014.2329415
Journal: IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS
Volume: 33
Begin Page: 1316
End Page: 1327
Appears in Collections:Articles


Files in This Item:

  1. 000344528500004.pdf