Design of Topologies for Interpreting Assays on Digital Microfluidic Biochips

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