Programmable microfluidic laboratories-on-a-chip (LoCs) offer the benefits of automation and miniaturization to the life sciences. This paper presents an updated version of the BioCoder language and a fully static (offline) compiler that can target an emerging class of LoCs called Digital Microfluidic Biochips (DMFBs), which manipulate discrete droplets of liquid on a 2D electrode grid. The BioCoder language and runtime execution engine leverage advances in sensor integration to enable specification, compilation, and execution of assays (bio-chemical procedures) that feature online decision-making based on sensory data acquired during assay execution. The compiler features a novel hybrid intermediate representation (IR) that interleaves fluidic operations with computations performed on sensor data. The IR extends the traditional notions of liveness and interference to fluidic variables and operations, as needed to target the DMFB, which itself can be viewed as a spatially reconfigurable array. The code generator converts the IR into the following: (1) a set of electrode activation sequences for each basic block in the control flow graph (CFG); (2) a set of computations performed on sensor data, which dynamically determine the result of each control flow operation; and (3) a set of electrode activation sequences for each control flow transfer operation (CFG edge). The compiler is validated using a software simulator which produces animated videos of realistic bioassay execution on a DMFB.

Digital microfluidics based on electrowetting-on-dielectric technology is poised to revolutionize many aspects of chemistry and biochemistry through miniaturization, automation, and software programmability. Digital microfluidic biochips (DMFBs) offer ample spatial parallelism, which is then exposed to the compiler. The first problem that a DMFB compiler must solve is resource-constrained scheduling, which is NP-complete. If the compiler is applied off-line, then long-running algorithms that produce solutions of high quality, such as iterative improvement or branch-and-bound search, can be applied; in an online context, where a biochemical reaction is to be executed as soon as it is specified by the programmer, heuristics that sacrifice solution quality to attain a fast runtime are used. This article describes in detail the algorithms and heuristics that have been proposed for resource-constrained scheduling, focusing on several recent contributions: path scheduling and force-directed list scheduling. It also discusses shortcomings and limitations of existing optimal scheduling problem formulations based on Integer Linear Programming and presents an updated formulation that addresses these issues. The algorithms are compared and evaluated on an extensive benchmark suite of biochemical assays used for applications, such as in vitro diagnostics, protein crystallization, and automated sample preparation.

This paper introduces a multiterminal escape routing algorithm for the design of printed circuit boards (PCBs) that control digital microfluidic biochips (DMFBs). The new algorithm extends a negotiated congestion-based single-terminal escape router that has been shown to be superior to previous methods. It relaxes the pin assignment to allow pin groups to be broken up when doing so can reduce the number of PCB layers. Experimental results indicate that the improved method can reduce both the number of PCB layers and average wirelength compared to existing DMFB escape routers.

Routing-based synthesis for digital microfluidic biochips yields faster assay execution times compared to module-based synthesis. We show that routing-based synthesis can lead to deadlocks and livelocks in specific cases, and that dynamically detecting them and adjusting the probabilities associated with different droplet movements can alleviate the situation. We also introduce methods to improve the efficiency of wash droplet routing during routing-based synthesis, and to support nonreconfigurable modules, such as integrated heaters and detectors. We obtain increases in success rates when dealing with resource-constrained chips and reductions in average assay execution time.

Microfluidic technologies offer benefits to the biological sciences by miniaturizing and automating chemical reactions. Software-controlled laboratories-on-a-chip (LoCs) execute biological protocols (assays) specified using high-level languages. Integrated sensors and video monitoring provide a closed feedback loop between the LoC and its control software, which provide timely information about the progress of an ongoing assay and the overall health of the LoC. This paper introduces a cyber-physical control algorithm that rectifies hard and soft faults that are detected dynamically while executing an assay on a digital microfluidic biochip (DMFB), one specific LoC technology. The approach is scalable (i.e., there is no fixed limit on the number of faults that may occur), and runs efficiently in practice, thereby limiting the performance overhead incurred when a hard or soft fault occurs during assay execution.

This paper transforms the problem of droplet routing for digital microfluidic biochips (DMFBs) from the discrete into the continuous domain, based on the observation that droplet transport velocity is a function of the actuation voltage applied to electrodes that control the devices. A new formulation of the DMFB droplet routing problem is introduced for the continuous domain, which attempts to minimize total energy consumption while meeting a timing constraint. Henceforth, DMFBs should be viewed as continuous, highly integrated cyber-physical systems that interact with and manipulate physical quantities, as opposed to inherently discrete and fully synchronized devices.

This paper introduces a multi-terminal escape routing algorithm for the design of Printed Circuit Boards (PCBs) that control Digital Microfluidic Biochips (DMFBs). The new algorithm is based on the principle of negotiated congestion, which has been applied in the past to problems including FPGA routing and PCB escape routing for single-terminal nets. PCBs designed for Pin-constrained DMFBs, in which one control pin may drive multiple electrodes, require multi-terminal escape routing solutions. Experimental results indicate that negotiated congestion is more effective for multi-terminal escape routing than existing techniques, which are based on maze routing coupled with rip-up and re-route, yielding an overall reduction in the number of PCB layers in most the test cases that were tried.

BioCoder is a C++ library developed at Microsoft Research, India, for the unambiguous specification of biochemical assays. This article describes language extensions to BioCoder along with a compiler and runtime system that translate and execute assays specified using BioCoder on a software simulator. The simulator mimics the behavior of laboratories-on-a-chip (LoCs) based on a droplet actuation technology called electrowetting on dielectric (EWoD). To date, prior compilers targeting similar EWoD devices are limited to assays specified as directed acyclic graphs (DAGs) and cannot handle arbitrary control flow or feedback from the LoC. The framework presented herein addresses these challenges through dynamic interpretation, thereby enlarging the space of assays that can be compiled onto EWoD devices.

We introduce an online synthesis flow, focusing primarily on the virtual topology and operation binder, for digital microfluidic biochips, which will enable real-time response to errors and control flow. The objective of this flow is to facilitate fast assay synthesis while minimally compromising the quality of results. In particular, we show that a virtual topology, which constrains the allowable locations of assay operations such as mixing, dilution, sensing, etc., in lieu of traditional placement, can significantly speed up the synthesis process without significantly lengthening assay execution time. We present a base virtual topology and show how it can be leveraged to reduce algorithmic runtimes and guarantee rout ability. We later present several variations of the virtual topology and present experimental results demonstrating best-design practices. We present two binding solutions. The first is a left-edge binding algorithm, while the second is a more intelligent path-based binding algorithm that leverages spatial and temporal locality to produce superior results.

This paper introduces a field-programmable pin-constrained digital microfluidic biochip (FPPC-DMFB), which offers general-purpose assay execution at a lower cost than general-purpose direct addressing DMFBs and highly optimized application-specific pin-constrained DMFBs. One of the key cost drivers for DMFBs is the number of printed circuit board (PCB) layers, onto which the device is mounted. We demonstrate a scalable single-layer PCB wiring scheme for several FPPC-DMFB variations, for PCB technology with orthogonal routing capacity of at least three; for PCB technology with orthogonal capacity of two, more PCB layers are required, but the FPPC-DMFB retains its cost advantage. These results offer new insights on the relationship between PCB layer count, pin count, and cost. Additionally, to reduce the execution time of assays on the FPPC-DMFB, we present efficient algorithms for droplet routing, with and without contamination removal via wash droplets.

As digital microfluidic biochips (DMFBs) have matured over the last decade, efforts have been made to 1.) reduce the cost, and 2.) produce general-purpose chips. While work done to generalize DMFBs typically depends on the flexibility of individually controlled electrodes, such devices have high wiring complexity, which requires costly multi-layer printed circuit boards (PCBs). In contrast, pin-constrained DMFBs reduce the wiring complexity, but reduce the flexibility of droplet coordination. We present a field-programmable pin-constrained DMFB that leverages the cost-savings of pin-constrained designs, but is general-purpose, rather than assay-specific. We show that with just a few more pins than the state-of-the-art pin-constrained designs, we can execute arbitrary assays almost as fast as the most recent general-purpose DMFB designs.

Since the inception of digital microfluidics, the synthesis problems of scheduling, placement and routing have been performed offline (before runtime) due to their algorithmic complexity. However, with the increasing maturity of digital microfluidic research, online synthesis is becoming a realistic possibility that can bring new benefits in the areas of dynamic scheduling, control-flow, fault-tolerance and live-feedback. This paper contributes to the digital microfluidic synthesis process by introducing a fast, novel path-based scheduling algorithm that produces better schedules than list scheduler for assays with high fan-out; path scheduler computes schedules in milliseconds, making it suitable for both offline and online synthesis.

We introduce an online interpreter to execute biochemical assays on droplet-based digital microfluidic biochips (DMFBs). Online interpretation enables adaptivity, e.g., response to faults during assay execution, variable-latency assay operations, and concurrent workloads whose composition is not known statically. Our online method routes droplets dynamically, making decisions in milliseconds while running on a low-cost Intel Atom" processor.

Synthesis of digital microfluidic biochips (DMFBs) is a crucial to the advancement and realization of miniaturized, automated, programmable biochemistry solutions; synthesis is performed in three steps: scheduling, placement and routing. In principle, algorithms for specific steps should be interchangeable with one another; however, different research groups typically develop algorithms for each step in isolation from one another. Thus, it is difficult to compare algorithms against one another, or to determine which algorithms for different steps share synergies. We introduce an open source DMFB synthesis framework to encourage collaboration between researchers working in the area. We introduce a common interface and describe the internal data structures that must be updated to ensure that the interfaces are adhered to. We also present and describe a number of high-quality 2D and 3D debugging tools that provide graphical output for each stage of synthesis. © 2012 IEEE.

We introduce a Force-directed List Scheduling (FDLS) algorithm for resource-constrained assay compilation targeting Digital Microfluidic Biochips (DMFBs). This algorithm has been used in the past for high-level synthesis of digital signal processing systems, and is now applied to DMFB synthesis. The results show improvements compared to List Scheduling (LS) and Path Scheduling (PS), the most efficient heuristics that have been proposed, to date, for DMFBs. FDLS was also competitive with longer-running iterative improvement DMFB scheduling algorithms based on genetic algorithms. © 2012 IEEE.