Error-Recovery in Cyberphysical Biochips - Hardware/Software Co-Design and Optimization for Cyberphysical Integration in Digital Microfluidic Biochips - page 44

2.4.1 Off-Line Data Preparation Before Bioassay Execution

The first step in data preparation is converting the sequencing graph of the bioassay
to a directed acyclic graph (DAG) and storing the DAG in memory for use by
the control software. In this DAG, the vertices represent microfluidic handling
operations and the edges represent precedence relations between operations. By per-
forming depth-first search on the graph, the predecessors and successors of any
operation can be determined [ 22 ].
The second step in data preparation is assigning error thresholds for each
operation. These thresholds are determined by the requirement of precision for the
bioassay and they are stored as a table in memory for use by the control software.
During bioassay execution, if a detection result is outside the range of pre-assigned
threshold values, we conclude that an error has occurred at the corresponding
operation.
The last step in data preparation is deriving the initial synthesis result for the
bioassay. In this procedure, we map the sequencing graph of the bioassay and on-
chip resources to the scheduling, resource binding, module placement, and droplet
routing results for each operation.
For a sequencing graph consisting of n operations, the synthesis result can be
written as the following set:

Df M opt 1 , M opt 2 , :::M opt n g S

where M opt i , 1 i n, is the synthesis output for the i th operation opt i .The
element M opt i

can be viewed as an ordered 6-tuple:

M opt i D < ts . opt i /, te . opt i /, x . opt i /, y . opt i /, col . opt i /, row . opt i />

where ts and te are the start time and end time of the operation, respectively; x and y
are the x-coordinate and y-coordinate for the module that implements the operation;
col ( row ) is the quantity of columns (rows) occupied by the operation in the array.
For an arbitrary operation opt i , the order of elements in the tuple M opt i is defined.
Thus we can use M opt i . j/ to represent the j th element in the tuple M opt i .For
example, the start time of i th operation is written as M opt i .1/, the x-coordinate of
i th operation is written as M opt i .3/, and the number of columns occupied by opt i is
written as M opt i .5/.
For simplicity, we use

P to represent the set of all operations in the bioassay;

and we use must satisfy, which include:

1. For any pair of operations opt w and opt v , if the two open intervals (M opt w .1/,
M opt w .2/)and(M opt v .1/, M opt v .2/) overlap, i.e.,

C to refer to the set of constraints that S

.M opt w .1/; M opt w .2// \ .M opt v .1/; M opt v .2// ¤; ;