Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (18 results)

  • Thesis
  • Peer Reviewed
UC Riverside Electronic Theses and Dissertations (2014)

In the last decade, digital microfluidic biochips have emerged as a viable candidate for the automation and miniaturization of biochemistry; however, digital microfluidic designs in previous works typically suffer from two short-comings: 1.) they are unable to respond to live feedback and errors; 2.) they are application-specific, rather than programmable. In the early years of digital microfluidic research, the synthesis problems of scheduling, placement and routing were performed offline (before runtime) due to their algorithmic complexity, typically yielding application-specific devices that could perform only one type of biochemical reaction and could not respond to live feedback in a timely manner, due to the complexity of their algorithms.

This dissertation offers topological solutions toward realizing digital microfluidic biochips that are both dynamic and programmable in nature. We begin by presenting interpretation, which is a form of dynamic synthesis. Instead of static compilation which generates a deterministic electrode activation sequence, interpretation acts like an operating system that manages resources as an assay is being executed, allowing for resources to be allocated and dispatched dynamically in response to live feedback from integrated sensors and video monitoring. We also present new language constructs necessary to incorporate control flow into digital microfluidic biochips (DMFBs). We then introduce virtual topologies, a virtual organization of electrodes into "city streets and blocks," which help simplify dynamic synthesis flow algorithms; we show two new virtual topologies and describe scheduling, placement and routing algorithms to accompany them, yielding fast, reliable, dynamic, programmable DMFBs. Finally, we present a field-programmable, pin-constrained (FPPC), topology which, for the first time, offers a solution to reduce the cost of a DMFB while maintaining programmability. We include results which show our FPPC design to be the least expensive when compared to prior pin-constrained and direct addressing DMFBs, while offering unmatched flexibility next to its closest competitors in price. We conclude with the first detailed cost analysis and shed light on the relationship between PCB layer count, pin count and cost. Our results reveal that the minimization of pin-count, if not done carefully, can necessitate additional PCB layers and yield a more expensive DMFB.

    Cover page: Design of Topologies for Interpreting Assays on Digital Microfluidic Biochips
    • Article
    • Peer Reviewed
    UC Riverside Previously Published Works (2013)
    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. Copyright © 2013 ACM.
      • Article
      • Peer Reviewed
      UC Riverside Previously Published Works (2014)
      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. © 2013 IEEE.
        • Article
        • Peer Reviewed
        UC Riverside Previously Published Works (2015)
        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.
          • Article
          • Peer Reviewed
          UC Riverside Previously Published Works (2014)
          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.
            • Article
            • Peer Reviewed
            UC Riverside Previously Published Works (2018)
            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.
              Cover page: Resource-Constrained Scheduling for Digital Microfluidic Biochips
              • Article
              • Peer Reviewed
              UC Riverside Previously Published Works (2014)
              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. © 2014 ACM.
                • Article
                • Peer Reviewed
                UC Riverside Previously Published Works (2014)
                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. © 2014 IEEE.
                  • Article
                  • Peer Reviewed
                  UC Riverside Previously Published Works (2014)
                  Virtual topologies simply the process of compiling assays to execute on digital microfluidic biochips (DMFBs). This paper evaluates the performance and cost of a virtual topology inspired by networks-on-chip (NoCs). The throughput of several deadlock-free droplet routing protocols is compared on synthetic traffic patterns that are widely used to evaluate semiconductor NoCs. The cost is the number of control pins required for actuation and the number of PCB layers required to route the chip; by eliminating unused pins, the virtual topology is cheaper than a direct-addressing DMFB, especially as chip size increases.
                    • Article
                    • Peer Reviewed
                    UC Riverside Previously Published Works (2014)
                    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.
                      Top