Synthesis of Digital Microfluidic Biochips: Modeling, Placement, and Routing
Date Issued
2008
Date
2008
Author(s)
Yuh, Ping-Hung
Abstract
Due to the advances in the microfabrication and microelectromechanical systems, microfluidic technology has gained much attention recently. Droplet-based microfluidic biochips are expected to revolutionize biological laboratory procedures by allowing faster and more error-free assays, where droplets are biological sample carriers. As biochips are adopted for the complex procedures in molecular biology, their complexity is expected to increase due to the need of multiple and concurrent assays on a chip. Therefore, there is a pressing need of CAD support for the biochip design automation.n this dissertation, we handle the placement and routing problems in the synthesis of digital microfluidic biochips.his dissertation is divided into three parts. In the first part, we model each fundamental operation, such as droplet mixing or droplet split, as a 3D box. Therefore, the bioassay execution can be modeled as a 3D floorplan with the X (Y) dimension representing the width (height) of a biochip and the $T$ dimension representing the duration of a bioassay. A key observation, which is one of the key contributions of this dissertation, is that under such a model, the bioassay placement problem is transformed to the temporal floorplanning problem. The advantage of this model is that we can have a high flexibility to optimize both the biochip area and the assay completion time.n the second part, we devise a temporal floorplanning technique to solve the placement problem. We propose the first tree-based representation, called T-tree to solve the temporal floorplanning problem. We present the structure of T-tree and its packing method. We show the advantages of T-tree over other 3D floorplan representations when is is applied to the placement problem of biochips. We also prove the reachability and the solution of T-tree, which presents a solid theoretical foundation of T-tre.ext, we propose the T-tree based temporal floorplanning algorithm for the placement problem of biochips. To ensure the correctness of bioassay execution, we handle the temporal orderings among operations. Moreover, we also handle the storage units that are used to store the intermediate result between two data-dependent operations.o make use of the property of a bioassay, we propose a clustering algorithm to reduce problem size and to obtain better solution. We also handle the defect tolerance issue induced by manufacture.n the third part, we solve droplet routing problem on biochips. The droplet routing problem is to move a droplet from one location to another location for reaction. The main challenge of the droplet routing problem is to ensure the correctness of a bioassay; the fluidic property that avoids unexpected mixing among droplets needs to be satisfied. Unlike traditional VLSI routing, in addition to routing path selection, the droplet routing problem needs to address the issue of scheduling droplets under the practical constraints imposed by the fluidic property and the timing restriction induced by the placement result.wo droplet routing algorithms are proposed for different biochip architectures. For general biochips, we propose a two-stage routing scheme (global routing followed by detailed routing). We propose the first network-flow based routing algorithm to handle the droplet routing problem.n detailed routing, we also present the first polynomial-time algorithm using the global-routing paths.e also develop routing techniques under the more scalable cross-referencing biochip paradigm, which uses row/column addressing scheme to activate electrodes for droplet movement. We propose the first droplet routing algorithm that directly solves the problem of routing in cross-referencing biochips. The main challenge of this type of biochips is the electrode interference which prevents simultaneous movement of multiple droplets. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem.ue to its complexity, we also propose a progressive ILP scheme to determine the locations of droplets at each time step. Therefore, the problem size can be significantly reduced to a manageable size. Experimental result shows that the progressive-ILP based routing scheme can obtain a near-to-optimal solution.
Subjects
Digital microfluidic biochips
cross-referencing biochips
placement
routing
synthesis
temporal floorplanning
T-tree
network-flow
progressive-ILP
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-F91922089-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):7c339ace890bc474d8eaccf1ae0f0b8f