Hardware Reference
In-Depth Information
1: Partition a sequencing graph
G
into directed-trees
{
T
1
,
T
2
, ...,
T
n
}
;
2: for each
T
i
∈{
T
1
,
T
2
, ...,
T
n
}
do
3: Start from leaf nodes, determine relative positions of dilution/mixing modules on a
level-by-level basis;
4: Determine schedules of operations;
5: Package operations the entire directed tree as a “macro-operation”
M
T
i
;
6: end for
7: Sort the directed trees based on operation interdependencies;
8: Merge synthesis results of directed trees based on their orders.
Fig. 4.6
Pseudocode for operation-interdependency-aware synthesis
Hence we have proved that, the conflict relationships between T
x
and T
y
will not
exist. This completes the proof of the lemma.
From the above steps, the synthesis results can be derived for general sequencing
graphs. An example is shown in Fig.
4.4
a. The graph is divided into three parts:
the node that represents operation L, the node that represents operation R,anda
directed tree T . The operations in T are packaged as a “macro-operation” M
T
.As
operation L and R are both predecessors of operations in T , the interdependency of
macro-operation M
T
, operation L and operation R is show in Fig.
4.4
b. According
to the above discussion, the relationship among R, L,andM
T
can be written as
R
D
L>M
T
.
Therefore, operations L and R will be concurrently executed, and operations
in M
T
will be executed after operations L and R are both completed. The
corresponding module-placement result can be derived in a similar way as the
sequencing graph shown in Fig.
4.3
f.
The operation-interdependency-aware algorithm described above can derive the
semi-deterministic synthesis result for a bioassay. The synthesis result assigns
each dilution/mixing operation to a specific D/M phase, while completion-times
of these operations are determined on-line during the execution of the bioassay.
The robust module-placement thus derived is independent of the execution time
for each operation. When timing uncertainties of dilution/mixing operations exist,
the module-placement of a bioassay remains unchanged. The pseudocode for the
entire operation-interdependency-aware synthesis approach is shown in Fig.
4.6
.By
applying the proposed synthesis approach, the completion-time uncertainties are
handled in a reliable manner by on-line decision-making during the execution of the
bioassay, even though the completion-time of fluidic operations are unpredictable
before the bioassay is run on the fabricated biochip.
4.4
Droplet-Routing Procedure
The practical application of cyberphysical microfluidics requires control software
to ensure the synthesis results of the bioassay are routable, and also, to determine
droplet transportation paths for each droplet transportation phase.
