Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2016 | Book

Introduction Read chapter Read first chapter

Fault-Tolerant Digital Microfluidic Biochips

Compilation and Synthesis

Authors: Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen

Publisher: Springer International Publishing

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik"

Login to get access
insite
SEARCH

About this book

This book describes for researchers in the fields of compiler technology, design and test, and electronic design automation the new area of digital microfluidic biochips (DMBs), and thus offers a new application area for their methods. The authors present a routing-based model of operation execution, along with several associated compilation approaches, which progressively relax the assumption that operations execute inside fixed rectangular modules. Since operations can experience transient faults during the execution of a bioassay, the authors show how to use both offline (design time) and online (runtime) recovery strategies. The book also presents methods for the synthesis of fault-tolerant application-specific DMB architectures.

· Presents the current models used for the research on compilation and synthesis techniques of DMBs in a tutorial fashion;

· Includes a set of “benchmarks”, which are presented in great detail and includes the source code of most of the techniques presented, including solutions to the basic compilation and synthesis problems;

· Discusses several new research problems in detail, using numerous examples.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
This chapter presents an introduction to the microfluidics field and microfluidic biochips. We discuss the main fluid propulsion principles used by modern microfluidic platforms, with a focus on “digital” microfluidic biochips, which are the topic of this book. Digital microfluidic biochips manipulate the fluids as small “droplets” using electrokinetics, i.e., electrowetting-on-dielectric. Several application areas for biochips are discussed, and the motivation behind the work presented in this book is introduced. At the end of the chapter, we outline the structure of the book and an overview of the topics covered.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen

Preliminaries

Frontmatter
Chapter 2. Design Methodology for Digital Microfluidic Biochips
Abstract
This chapter presents an overview of the digital biochip design process, highlighting the main design tasks, with a focus on fault-tolerant biochips. The purpose is to explain how the methods presented in this book are used within a design methodology and to define the main design tasks. We highlight the difference between the “compilation” and “synthesis” terms used throughout the book. We discuss in more detail the compilation task, which is covered by Parts II and III, and its constituent subtasks. The architecture synthesis tasks are covered in Part IV. This chapter is intended to help in understanding how the methods presented in the book interact with each other. This chapter also presents the related work in the area of compilation and architecture synthesis approaches for digital microfluidic biochips.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 3. Biochip Architecture Model
Abstract
This chapter presents in detail how digital microfluidic biochips work, and introduces the architecture model we use in the book. Digital microfluidic biochips are organized as an array of electrodes, each of which can hold one droplet, and move the droplets of fluid using electrokinetics. We present the key ideas behind electrowetting-on-dielectric, the fluid propulsion method used in these biochips. We discuss the basic microfluidic operations, such as transport, splitting, dispensing, mixing, and detection, focusing on the reconfigurable operations, which are characteristic to droplet-based biochips. The reconfigurable operations are typically performed inside “virtual modules”, which are created by grouping adjacent cells. During module-based operation execution, all cells inside the module are considered occupied, although the droplet uses only one cell at a time, which is inefficient. Therefore, we introduce a new, “routing-based”, model of operation execution and propose an analytical method for determining the completion time of an operation on any given route. The chapter also presents the typical faults affecting digital microfluidic biochips and the fault models considered in this book, as well as a detailed discussion of how these faults can affect the operation execution.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 4. Biochemical Application Model
Abstract
Biochemical applications (also called in this book “protocols” or “assays”) are typically written in natural language, which is imprecise and cannot be used for automation purposes. We first present the state-of-the-art in biochemical language modeling, and highlight the new high-level languages recently proposed. Then, we present the “graph model” used in the book to capture the behaviour of a biochemical application; several examples of real-life applications are also presented. This graph model is used in Part II of the book, where we do not consider fault-tolerance and variability aspects. To capture these aspects in the application model, we introduce later in the chapter a “fault-tolerant biochemical application model” that captures the operations needed for error recovery. This extended model is used in Part III of the book. Finally, the fault models considered are presented and several related fault-tolerant techniques are discussed.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen

Compilation

Frontmatter
Chapter 5. The Compilation Problem
Abstract
This chapter presents in detail the compilation task, which, given the biochemical application and biochip architecture models as inputs, produces the electrode actuation sequence required to run the application on the given biochip. Each of the compilation subtasks, such as, allocation, binding, placement, scheduling and routing are discussed in a corresponding subsection. These subtasks have a high computational complexity, and we have used a heuristic algorithm called “List Scheduling” as a starting point for providing solutions to them. Hence, this chapter also covers the “List Scheduling” heuristic. The compilation task also takes as input a “library of modules” on which the operations on the biochemical applications have to execute. We present a method to determine a library of “circular-route modules”, which will be used in Part IV of the book, to support application-specific architectures. To simplify the presentation, this chapter presents the compilation task assuming that an operation executes on a static rectangular “module”. However, as discussed in Chap. 3, we also consider other operation execution models in the book; these will be covered in the next chapters related to the compilation task.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 6. Module-Based Compilation
Abstract
In this chapter we propose a solution to the compilation of biochemical applications on a given biochip model. The assumptions are as follows: We consider that the reconfigurable operations are executed on rectangular modules, which group adjacent electrodes to form virtual devices that have a static placement throughout the execution of the operation. We assume that the biochip architectures consist of a rectangular array of electrodes, and that the biochemical applications are modeled using a graph model. Due to the computational complexity of the compilation problem, it is infeasible to obtain optimal solutions. Therefore, the solution proposed in this chapter is based on a metaheuristic optimization called Tabu Search, which is capable of solving complex compilation problems. The proposed solution is evaluated on several benchmarks and compared to existing compilation approaches.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 7. Module-Based Compilation with Reconfigurable Operation Execution
Abstract
This chapter also proposes a solution to the compilation of biochemical applications on a given biochip architecture. The compilation problem proposed in the previous chapter has assumed that reconfigurable operations are performed inside rectangular modules whose location and shape remain fixed throughout the execution of operations. However, as discussed in Sect. 3.​4, reconfigurable operations can be performed anywhere on the array, by simply routing the corresponding droplets on a sequence of electrodes. In this chapter, we propose two models for operation execution inside virtual devices, which take into consideration the reconfigurability of microfluidic operations: (1) moving a module during the operation execution and (2) changing the shape of the device on which an operation is bound during its execution. These operation execution models aim at reducing the fragmentation of the free space on the microfluidic array during the placement step of the compilation process. In this context, we revisit the compilation problem and present an extension to the Tabu Search metaheuristic optimization solution introduced earlier, with a focus on a new dynamic module placement algorithm. The advantages of the new operation execution models are evaluated using extensive experiments.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 8. Module-Based Compilation with Droplet-Aware Operation Execution
Abstract
The compilation problems discussed so far have assumed that during operation execution in module-based compilation, the droplet repeatedly follows the same pattern inside the virtual module, leading to an operation completion time determined through experiments. The actual position of the droplet inside the virtual device has been ignored, considering that all the electrodes forming the device are occupied throughout the operation execution. In order to avoid the accidental merging of droplets, it was considered that a device is surrounded by a 1-cell segregation area, containing cells that can not be used until the operation performing on the device is completed. In this chapter, we consider rectangular modules (which we also call “black-box modules”), but in contrast to earlier chapters we use a droplet-aware execution of microfluidic operations, which means that we know the exact position of droplets inside the modules at each time step, and we can control them to avoid accidental merging, if necessary. This allows us to utilize the chip area better, since no segregation cells are needed to separate the modules, and improve the routing step, since now the routes can cross over modules, if needed. Another advantage of droplet-aware operation execution, is that it allows the partial overlapping of modules, which can increase parallelism. The proposed compilation solution extends the Tabu Search-based compilation introduced in the earlier chapters.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 9. Routing-Based Compilation
Abstract
In digital microfluidic biochips, the reconfigurable operations are performed by routing the corresponding droplets on a sequence of electrodes on the microfluidic array. In the earlier chapters we have assumed that during execution, droplets are repeatedly transported on groups of adjacent electrodes, forming virtual devices. However, operations can be executed by routing the corresponding droplets anywhere on the array, unconstrained by virtual devices. In this chapter, we remove the concept of “virtual device” and allow operations to execute by routing the droplets on any sequence of electrodes on the array. We call this approach routing-based operation execution. In this context, we propose a compilation solution based on a heuristic algorithm called “Greedy Randomized Adaptive Search Procedure”. The advantage of routing-based operation execution is highlighted using extensive experiments.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen

Compilation for Error Recovery and Uncertainty

Frontmatter
Chapter 10. Fault-Tolerant Module-Based Compilation
Abstract
The chapters so far have ignored fault-tolerance aspects, and have assumed that the biochips are fault-free, which means that all the electrodes on the microfluidic array can be used for the execution of operations. However, this is not always the case, as electrodes on the array can become faulty during the fabrication of the biochip or during its operation. In this chapter, we assume that electrodes can suffer “permanent faults”, and we propose a fault-tolerant compilation method that can bypass such faulty electrodes during the execution of the biochemical application. The solution relies on a droplet-aware compilation approach for fault-tolerant microfluidic biochips. The proposed approach considers the location of droplets on the microfluidic array during the execution of operations. One real-life application as well as a set of three synthetic benchmarks have been used to show the effectiveness of the proposed approach. We have shown that by knowing the position of droplets on the array at each time step, we can efficiently avoid the defective electrodes on the microfluidic array, improving the completion time of applications compared to the traditional, black-box approach.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 11. Compilation for Error Recovery
Abstract
In this chapter, we are interested in fault-tolerance against transient faults, which occur during the execution of the application, see Sect. 3.​3 for a discussion on transient faults and how they can be detected. Biochemical applications are executed based on the electrode actuation sequence, which is produced in the compilation task, see Chap. 5 When a transient error is detected during the execution, the original electrode actuation sequence has to be interrupted, and recovery actions have to be initiated to remedy the error. These recovery actions are a sequence of operations that have to be executed, and will have to be compiled also into an electrode actuation sequence. This chapter presents two approaches to compilation for error recovery, an offline approach, which can be used at design time, and an online approach, which is employed at runtime. The proposed techniques have been evaluated on several real-life and synthetic test cases and compared to related work.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 12. Compilation for Operation Execution Time Variability
Abstract
In this chapter, we address the problem of variability in the execution times of the operations, caused by the randomness in biochemical reactions. In previous chapters, we have proposed compilation techniques that derive the schedule of operations based on the assumption that each operation is characterized by a worst-case execution time (wcet). However, during the execution of the application, operations may finish earlier than their wcets, resulting in unexploited slack in the schedule. In this chapter, we present two strategies that can handle such variabilities: an online approach and an approach based on a quasi-static strategy. The online compilation strategy re-compiles the application at runtime when operations experience variability in their execution time, thus exploiting the slack to obtain shorter application completion times. The quasi-static compilation strategy determines offline a database of alternative implementations. During the execution of the application, several implementations are selected based on the current execution scenario with operation execution time variability. The experiments reflect the advantages and disadvantages of the proposed approaches. Both of our strategies have better results than prior work.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen

Architecture Synthesis

Frontmatter
Chapter 13. Synthesis of Fault-Tolerant Biochips
Abstract
In this chapter, we propose an Integer Linear Programming (ILP) synthesis methodology that, starting from a biochemical application modeled as a sequencing graph and a given biochip, determines the allocation, placement, resource binding, and scheduling of the operations in the application. Our goal is to find that particular implementation of an application onto a biochip, which has the highest probability to be reconfigured successfully in case of multiple faulty cells. We propose a fault model for biochips, and use Monte Carlo simulation to evaluate the probability of successful reconfiguration of each implementation in case of faults. This chapter addresses both the compilation and architecture synthesis tasks. Regarding architecture synthesis, our aim in this chapter is to determine the smallest (and thus, cheapest) biochip architecture that can support a fault-tolerant biochemical application execution (obtained via compilation), in case of permanent faults in the electrodes of the architecture array.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Chapter 14. Synthesis of Application-Specific Architectures
Abstract
All the work presented in this book so far, has considered general-purpose regular biochip architectures, which use a rectangular electrode array. However, in practice, application-specific architectures are often preferred because of their reduced cost. In this chapter, we first motivate the use of application-specific architectures, and present the application-specific architecture synthesis problem. We tackle this problem in the context of permanent faults, aiming to obtain a fault-tolerant application specific architecture. Next, the chapter presents two solutions to the synthesis of fault-tolerant application-specific architectures. Starting from an initial architecture, our synthesis solutions use metaheuristics (Simulated Annealing and Tabu Search) that search through the solution space to find a minimum cost architecture that can satisfy the timing constraints of the application and tolerate a given number k of permanent faults.
Paul Pop, Mirela Alistar, Elena Stuart, Jan Madsen
Metadata
Title
Fault-Tolerant Digital Microfluidic Biochips
Authors
Paul Pop
Mirela Alistar
Elena Stuart
Jan Madsen
Copyright Year
2016
Electronic ISBN
978-3-319-23072-6
Print ISBN
978-3-319-23071-9
DOI
https://doi.org/10.1007/978-3-319-23072-6