System Support for Generally Programmable for Digital Microfluidic Biochip Devices
Abstract
We have developed a compiler and runtime system to translate assays specified using a high-level language into an executable form appropriate for an LoC called a Digital Microfluidic BioChip (DMFB) that manipulates discrete droplets on a 2-dimensional array through an enabling technology called >electrowetting on dielectric (EWoD). Assays are specified using BioCoder, a C++ library for biological protocol specification developed at Microsoft Research, India. Language extensions to BioCoder are introduced that facilitate user-specified control-flow operations (e.g., conditionals and loops). The interpreter can execute assays with control flow and can use feedback from the DMFB to make control flow decisions, and does not rely on complex re-synthesis methods that dynamically recompile the assay when control flow become unpredictable. This represents a significant improvement over existing DMFB compilation techniques, as it enables the execution of a much wider range of assays compared to what has been supported previously.
Historically, assays have been specified as DAGs, without control flow. The DAG is first scheduled; dimensions for each operational module are selected; scheduled operations are then placed onto the 2D grid, ensuring that no concurrently executing operations overlap to prevent interference; and, lastly, non-interfering droplet routes are computed to deliver droplets to the appropriate DMFB locations at appropriate times. The control program generated by the assay compiler is a linear state machine. Each state specifies a subset of electrodes that are will be activated; it typically takes 1ms to transport a droplet to an adjacent cell, and mixing/dilution times during assay execution are on the order of seconds or tens-of-seconds.
The linear state machine control model is wholly deterministic, which is acceptable for a scheduled DAG with no operation variability. To cope with bounded variability, it is possible to enumerate schedules for all possible combinations of operation times, which is exponential in the general case. An alternative approach, which can accommodate assay operations that fail and require partial recomputation, is to pause assay execution temporarily and recompile the assay on-the-fly. Although this overall approach results in the execution of a non-linear state machine, it essentially uses dynamic recompilation to replace one linear state machine with another.
The system under development in this project takes a different approach, wherein the assay is interpreted dynamically, rather than compiled statically and then (possibly) recompiled dynamically. The approach taken here imposes a virtual architecture on the DMFB that restricts the functions that different cells can perform. The virtual architecture organizes the DMFB like a well-planned city, with blocks (where all non-transport operations occur), one-way streets (which facilitate droplet transport) and rotaries (where in-flight droplets may change direction). Although the virtual architecture limits DMFB reconfigurability, these restrictions actually simplify the design and implementation of the interpreter.
We refer to a city block as a work chamber. The virtual architecture organizes the DMFB as a 2D-mesh network of work chambers, where the rotaries play a role akin to network routers. One contribution of this paper is to adapt deadlock-free 2D- mesh routing algorithms to DMFBs using this virtual architecture. The ability to perform deadlock-free droplet routing enables abstraction layers that share some principle similarities with the TCP/IP stack used in computer networks. This, in turn, facilitates an intermediate bytecode format (motivated by virtual machines), which simplifies the design of the interpreter. Without loss of generality, suppose that we want to dynamically issue the command: “Mix droplets x and y.” Under the recompilation paradigm described previously, the placement must be updated to make room for the new mixing operation (which, literally, could be anywhere on the chip, especially if other ongoing operations need to be moved), and then routes to deliver the two droplets must be computed algorithmically on-the-fly. In contrast, our interpreter could select any available work chamber, knowing that the droplet transportation protocol will deliver the two droplets (unless the device physically fails). Similarly, this capability facilitates the interpretation of assays that feature control flow operations, as runtime decisions (i.e., which chamber executes each assay operation) can be made dynamically with minimal overhead.
The poster describes the droplet transportation protocol in detail, as it is the key enabling technology for the interpreter. The current implementation effort is to build the interpreter on top of the droplet transportation protocol. The interpreter will seamlessly address the challenges of operation variability, unpredictable control flow, and the ability to execute multiple assays concurrently without knowing the precise mix of assays to execute at compile-time.
Award ID: 1035603