Biomedical Engineering Reference
In-Depth Information
1
2
3
5
3
5
4
1
4
1
2
3
4
2
3
5
Figure 3.3
A 5-pin layout for a 4 × 4 array.
the largest number of directly adjacent neighbors to any cell is four. Hence,
if
k
denotes the number of independent control pins, we ensure that
k
≥ 5,
such that each cell and all of its directly adjacent neighbors can be assigned
different colors. A possible pin layout using 5 pins for a 4 × 4 array is shown
as an example in Figure 3.3.
3.1.1.3 Pin-Assignment Problem for Two Droplets
We next examine the interference problem for two droplets. For more than
two droplets, the interference problem can be reduced to the two-droplet
problem by examining all possible pairs of droplets. In general, any sequence
of movements for multiple droplets can occur in parallel. We analyze the
interference between two droplets for a single clock cycle, during which time
a droplet can only move to a directly adjacent cell. Any path can be decom-
posed into unit movements, and we say that the two paths are compatible if
and only if all of their individual steps do not interfere.
In some situations, we would like both droplets to move to another cell in
the next clock cycle. If this is not possible without interference, then a contin-
gency plan is to have one droplet undergo a stall cycle (i.e., stay on its current
cell). There are other possibilities such as an evasive move or backtracking to
avoid interference, but these lead to more substantial changes in the sched-
uled droplet paths and are therefore not considered here.
Let us denote two droplets by
D
i
and
D
j
, with the position of droplet
D
i
at time
t
given by
P
i
(
t
). Le
t
N
i
(
t
) be the set of directly adjacent neighbors of
droplet
D
i
. The operator
k
(•) is the set of pins that control the set of cells
given by •. Then, the problem of two droplets moving concurrently can be
formally stated thus:
D
i
moves from
P
i
(
t
) to
P
i
(
t +
1), and
D
j
moves from
P
j
(
t
)
to
P
j
(
t +
1).
We are interested in the overlap of pins between sets of cells for the inter-
ference constraints, rather than the spatial locations of the cells. The latter
are important for the fluidic constraints discussed in [27]. For the purpose of
defining interference behavior, the system is completely determined by the
positional states of the two droplets at times
t
and
t +
1. For droplet
D
i
,
the
positional states are characterized by the quartet (
P
i
(
t
),
P
i
(
t +
1)
, N
i
(
t
),
N
i
(
t +
1))
and, for
D
j
, these are characterized by the quartet (
P
j
(
t
),
P
j
(
t +
1)
, N
j
(
t
),
N
j
(
t +
1)).
