Scheduling Algorithms
Scheduling Algorithms
This page summarizes the DMFB Scheduling algorithms that have been implemented and integrated into the framework, and cites the papers that describe them in detail. Scheduling determines the times at which each assay operation starts and finishes, while adhering to precedence constraints (from the DAG) and resource constraints from the target device.
Scheduling is a NP-complete problem and it is not possible to guarantee legal schedules in all instances. Situations may exist where the demand of an assay for resources may exceed the availability of resources on-chip. Both of the following situations may occur:
♦ No legal solution exists; or
♦ A legal solution exists, but the heuristics below cannot find it; in principle, Integer Linear Programming (ILP) should be able to find a legal solution if one exists, however, convergence in tractable time is not guaranteed, presuming that P != NP.
List Scheduling
List Scheduling is a greedy heuristic that schedules vertices one-by-one in priority order. A vertex is ready to be scheduled at time-step t if all of its predecessors have completed their operations. List Scheduling maintains a priority queue of ready vertices. The priority of each vertex is the length of the longest path in the DAG from that vertex to a primary output node. List scheduling will always schedule an operation if a resource is available; the drawback (as shown in detail below) is that this can increase demand for on-chip storage during future time-steps.
Our implementation of List Scheduling is described in the following papers:
D. Grissom and P. Brisk
Fast Online Synthesis of Digital Microfluidic Biochips
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)
33(3):356-369, February, 2014
Paper
D. Grissom and P. Brisk
Fast Online Synthesis of Generally Programmable Digital Microfluidic Biochips
10th IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (CODES-ISSS)
Tampere, Finland, October 7-12, 2012, pp. 413-422
Paper Slides
The following paper (which preceding our work) introduced an algorithm called Modified List Scheduling (MLS). MLS includes a rescheduling step that may be invoked if the scheduler fails at a given time-step. Our implementation of List Scheduling does not include the rescheduling step.
F. Su and K. Chakrabarty
High-Level Synthesis of Digital Microfluidic Biochips
ACM Journal on Emerging Technologies in Computing (JETC)
3(4): article #16, January 2008
Force-directed List Scheduling
Force-directed List Scheduling replaces List Scheduling's priority function with a physical model that estimates the criticality of each operation based on the number of time-steps at which it can be scheduled on an infinitely large DMFB without resource constraints. Other than the change in priority function, the underlying structure of the List Scheduling heuristic remains unchanged.
Our implementation of Force-directed List Scheduling is described in the following paper:
K. O'Neal, D. Grissom, and P. Brisk
Force-directed List Scheduling for Digital Microfluidic Biochips
20th IFIP/IEEE International Conference on Very Large Scale Integration (VLSI-SoC)
Santa Cruz, CA, USA, October 7-12, 2012, pp. 7-12
Paper Slides
Path Scheduling
Path Scheduling starts by decomposing a DAG into paths, as shown below.
The schedule is computed on the granularity of paths: all operations on a path are scheduled contiguously, which eliminates intermediate storage, except for dependencies between paths This approach is fast and is more likely than List Scheduling or Force-directed List Scheduling to find legal solutions when a relatively large assay is scheduled onto a relatively small DMFB.
Our implementation of Path Scheduling is described in the following paper:
D. Grissom and P. Brisk
Path Scheduling on Digital Microfluidic Biochips
49th Design Automation Conference (DAC)
San Francisco, CA, USA, June 3-7, 2012, pp. 26-35
Paper Slides Poster
Genetic List Scheduling
Genetic Algorithms are a class of long-running iterative improvement heuristics that tend to converge to locally optimal solutions. Two Genetic Schedulers have been proposed (with subtle differences between them). Both repeatedly call List Scheduling to produce legal solutions, while randomly varying operation priorities.
Our implementation of the two Genetic List Schedulers are based on the following papers:
A. J. Ricketts, K. Irick, N. Vijaykrishnan, and M. J. Irwin
Priority Scheduling of Microfluidics-Based Biochips
Design Automation and Test in Europe (DATE)
Munich, Germany, March 6-10, 2006, pp. 329-334
F. Su and K. Chakrabarty
High-Level Synthesis of Digital Microfluidic Biochips
ACM Journal on Emerging Technologies in Computing (JETC)
3(4): article #16, January 2008
Integer Linear Programming (ILP)
Coming soon.
Implementation Details
One of the keys to obtaining a good quality schedule is to minimize storage requirements. The example below illustrates a situation where delaying an input operation until immediately before the time-step the droplet is used can free up space on the chip. In principle, this space could be used to schedule another assay operation. (List Scheduling and Force-directed List Scheduling would schedule the operation early, while Path Scheduling would delay it to reduce the storage requirement).
Greedily scheduling vertices without accounting for storage demand can limit the available on-chip parallelism. In the example below, a DMFB has been partitioned into four Work Modules which may perform an operation (such as mix) or store up to 4 droplets. On the left, List Scheduling has injected 8 droplets into the chip; only two Work Modules are available for processing, as the other two must store the remaining 6 droplets. Path Scheduling, which is more conservative, stores just two droplets, freeing up three Work Modules for Processing, therefore making better use of on-chip resources.
Out scheduling framework represents storage by inserting storage nodes (shown below in black) for each time-step where an droplet is stored. This offers two key benefits:
♦ Visual inspection enables a quick and intuitive comparison between scheduling algorithms in terms of their ability to manage on-chip storage.
♦ It provides leeway to the placer, downstream, to easily move droplets from one storage location to another.
The example below compares List Scheduling to Path Scheduling. On the left, inverting List Scheduling's priority function (a bad idea, in principle, but shown here for illustrative purposes) introduces a large number of storage node. In the middle, List Scheduling's regular priority function introduces 119 storage nodes, while on the right, Path Scheduling introduces just 54 storage nodes.
Contact
Please direct any questions, comments, or other inquiries to the following e-mail address: microfluidics@cs.ucr.edu
Acknowledgment
This material is based upon work supported by the National Science Foundation under Grant Numbers 1035603, 1536026, and 1545097. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.