Biomedical Engineering Reference
In-Depth Information
D
1
D
2
D
1
D
2
D
3
D
3
(a)
(b)
D
1
D
2
D
3
(c)
Snapshot
1
2
3
Activation sequence {R3, C1} {R2, C1&C3} {R1, C1&C3&C6}
(d)
Figure 3.21
Schedule B: (a) Snapshot 1; (b) Snapshot 2; (c) Snapshot 3. (d) Activation sequence (in terms of
rows and columns).
Based on the preceding observation, we present an efficient scheduling
algorithm to generate well-aligned snapshots. The pseudocode for this algo-
rithm is sketched in Figure 3.22.
We next use an example to illustrate the algorithm. Figure 3.23 shows a
routing plan with five droplet pathways. Initially, the droplets reside at the
starting points shown in Figure 3.23. The algorithm first moves D
1
one elec-
trode to the right. Next, droplets D
1
and D
2
are moved one electrode to the
right in parallel. D
3
is added and moved one electrode to the right with D
1
and D
2
. At this time, D
1
meets a turning point in its pathway. The algorithm
stops and counts the number of droplet movements in each direction, that is,
two rightward, one downward. Therefore, the algorithm stores these num-
bers in
S
and keeps on moving D
2
and D
3
until they reach their respective
turning points. Next, the algorithm moves them one electrode downward
and one electrode to the right when they meet D
4
. Then, D
2
, D
3
, and D
4
are
moved one electrode to the right.
Next, the algorithm goes back to move the leftover droplets D
1
and D
4
.
Finally, the algorithm generates a routing schedule for D
5
and then integrates
it into the schedule for droplets D
2
~ D
4
.
Next, we evaluate the computational complexity of the algorithm using
step-by-step analysis. We assume that there are
M
droplets on an array of
N
×
N
electrodes
.
Droplet
i
has a pathway of length
L
i
. As shown in Figure 3.22,
Step 1 takes O(
M
) time to determine the starting droplet. For Step 2 and
Step 3 check if there are multiple droplets that can be moved concurrently
