Hardware Reference
In-Depth Information
finished. This re-scheduling process is repeatedly implemented until the deadlock
no longer occurs. The existence of a schedule without the deadlock is guaranteed by
the following lemma:
Lemma 6.4.
Deadlock never occurs when there are only two droplets concurrently
manipulated by the proposed general-purpose pin-limited biochip.
Proof.
This lemma can be proven by
reductio ad absurdum
. First we assume that
at time t
D
t
d
, deadlock occurs for two droplets D
x
and D
y
. According to the
definition of deadlock, we know the operation on D
x
may lead to the unintended
splitting or movement for D
y
, i.e., S
D
H
.t
d
/
\
S
D
L
.t
d
/
¤
. Then we know the
operation on D
y
may lead to the unintended splitting or movement for D
x
,i.e.,
S
D
y
H
¿
.t
d
/
\
S
D
x
L
.t
d
/
¤
¿
.
t
For each control pin of droplet D
x
, it is either in the set of S
D
x
.t
d
/ or in the set
H
of S
D
L
.t
d
/.SowehaveS
D
H
.t
d
/
\
S
D
L
.t
d
/
D
¿
, and the control pin group of D
x
can be written as CPG
D
x
.t
d
/
D
S
D
x
.t
d
/
[
S
D
x
L
.t
d
/.
H
Similarly, for droplet D
y
,wehaveS
D
y
.t
d
/
\
S
D
y
.t
d
/
D
¿
, and the control pin
H
L
group of D
y
can be written as CPG
D
y
.t
d
/
D
S
D
y
.t
d
/
[
S
D
y
L
.t
d
/.
H
.t
d
/
\
S
D
y
L
.S
D
x
H
Therefore, we have: CPG
D
x
.t
d
/
\
CPG
D
y
.t
d
/
D
.t
d
//
[
.S
D
H
.t
d
/
\
S
D
L
.t
d
//. It is already known that S
D
H
.t
d
/
\
S
D
L
.t
d
/
¤
¿
and
S
D
y
H
.t
d
/
\
S
D
x
L
, we conclude that the CPGs of droplet D
x
and D
y
have at
least two common elements. This is in conflict with Constraint
2
in Sect.
6.1
.This
completes the proof.
Lemma
6.4
shows that in the worst case, we can reduce the number of concurrent
fluid-handling operations to two, and deadlock will not occur. Therefore, by re-
scheduling the fluid-handling operations, we can always implement the bioassay
without deadlock.
The pseudocode for the scheduling algorithm based on pin-actuation sequences
can be found in Fig.
6.15
. Note the scheduling algorithm can be applied to any
pin-limited biochip, including the bioassay-specific biochips proposed in [
9
,
18
].
.t
d
/
¤
¿
6.7
Simulation Results
In this section, we present results for two commercial biochips and several
laboratory prototypes.