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.
Search WWH ::




Custom Search