ILP-Based Pin-Count Aware Design Methodology for Microfluidic Biochips

Digital microfluidic biochips have emerged as a popular alternative for laboratory experiments. To make the biochip feasible for practical applications, pin-count reduction is a key problem to higher-level integration of reactions on a biochip. Most previous works approach the problem by post-processing the placement and routing solutions to share compatible control signals; however, the quality of such sharing algorithms is inevitably limited by the placement and routing solutions. We present in this paper a comprehensive pin-constrained biochip design flow that addresses the pin-count issue at all design stages. The proposed flow consists of three major stages: 1) pin-count aware stage assignment that partitions the reactions in the given bioassay into execution stages; 2) pin-count aware device assignment that determines a specific device used for each reaction; and 3) guided placement, routing, and pin assignment that utilize the pin-count saving properties from the stage and device assignments to optimize the assay time and pin-count. For both the stage and device assignments, basic integer linear programming formulations and effective solution-space reduction schemes are proposed to minimize the assay time and pin-count. Experimental results show the efficiency of our methods and a 55-57% pin-count reduction over the state-of-the-art algorithms/flow.