Information Technology Reference
In-Depth Information
2
Related Works
Numerous scheduling techniques are proposed for architectural level synthesis in
DMFBs using fixed cell locations termed as hard blocks bound for specified droplet
operations. [13] presented modified list scheduling (MLS) and genetic algorithm (GA)
based heuristics, as well as an optimal integer linear programming (ILP) model for
scheduling microfluidic operations onto a DMFB. Although the GA finds optimal or
near-optimal results in much less time than ILP, its iterative nature results in large
computation times. MLS generated schedules with lesser time comparable with GA. In
[14] the algorithm was modified to include droplet-routing aware physical design
decisions. A Tabu search based scheduler proposed in [15] developed an iterative
improvement algorithms for DMFB scheduling where virtual devices were considered
to be movable (can change their placement) during their operation and significant
improvements in scheduling performance were obtained in the process. [16] have
proposed a synthesis and placement algorithm which uses a tree-based topological
representation and is able to improve on the results from [13]. [18] have proposed an
ILP-based architectural-level synthesis and placement approach for DMFBs, which
although has the advantage of producing the optimal solution, is only feasible for
limited problem sizes. A control path based design is recently integrated to the
architectural-level synthesis of DMFBs [19]. In [19], possibilities of errors for each
operation is initially measured using an error propagation based estimation technique,
and then a check point consisting of a storing operation and a error detection is inserted
to the sequencing graph. In [17] a Force-directed List Scheduling
(FDLS)
algorithm for
resource constrained assay compilation targeting
Digital Microfluidic Biochips
(DMFBs) has been proposed. In [17] two methods of FDLS were found to consistently
produce schedules of better or comparable quality to MLS while often approaching the
quality of GA. Several direct-addressing placement and unified scheduling-placement
algorithms [16][20][21][22] using methodologies e.g simulated annealing has been
developed. [23] introduced an online synthesis flow for DMFBs, that enable real-time
response to errors and control flow. The objective of this flow was to facilitate fast assay
synthesis while minimally compromising the quality of results. However it has been
found that only in [24] a routing based scheduling method has been proposed where the
synthesis problem is transformed into a routing problem. Here the concepts of virtual
fixed modules are eliminated and the droplets are allowed to move on the chip on any
route during operation execution. The approach was derived from a Greedy
Randomized Adaptive Search Procedure (GRASP) and it has been shown that
significant improvements can be obtained in the application completion time. In this
paper we have used the same concept as of [24] and used a modified droplet route based
synthesis methodology to perform the necessary placement and routing for optimization
of area and bioassay completion time.
3
Routing in DMFB
The objective of droplet routing is to transmit all the droplets from their respective
sources to targets within a 2D grid array while fulfilling all the constraints imposed
