Design Methodology for Digital Microfluidic Biochips Considering Pin-Count Reduction and Cross-Contamination Avoidance
Date Issued
2009
Date
2009
Author(s)
Lin, Cliff Chiung-Yu
Abstract
Digital microfluidic biochips have emerged as a popular alternative for laboratory experiments. Pin-count reduction and cross-contamination avoidance are key design considerations for practical applications with different droplets being transported and manipulated on highly integrated biochips.or pin-count reduction, most previous works approach the problem by postprocessing 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 thesis a comprehensive pinconstrained 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, exact ILP formulations and effective solution-space reduction schemes are proposed to minimize the assay time and pin count. Experimental results show the efficiency of our algorithms/flow and a 55–57% pin-count reduction over the state-of-the-art algorithms/flow.or cross-contamination avoidance, we also present in this thesis the first design automation flow that considers the cross-contamination problem on pinconstrained biochips. We recognize the desirable properties for cross-contamination avoidance and classify the cross contaminations that can happen with the properties. To cope with these cross contaminations, we propose (1) placement and routing algorithms that minimize the number of crossings among routing paths, and (2) wash droplet scheduling and routing methods that require only one extra control pin and zero assay completion time overhead for general bioassays. Experimental results show the effectiveness and scalability of our algorithms for practical bioassays.
Subjects
design automation
digital microfluidic biochip
pin-constrained
crosscontamination
algorithm
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R96943165-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):72cb62bf48a2f56a90aef7ecde75220e