Hardware Reference
In-Depth Information
operations are fixed. Here the operations that are implemented based on the initial
synthesis result are fixed a priori as the “obstacles”. The other operations that are
necessary for recovery are derived through re-synthesis and they are placed in
the remaining available biochip area in a greedy fashion. The detailed steps are
described below.
First, based on the topological sort result for operations, the control software
places all operations that need to be re-scheduled in a priority queue. These
operations include error-recovery operations and all successors of the erroneous
operation. Then the software assigns a priority for each operation in the queue.
The “deepest” operation in the subroutine (i.e., the operation at the bottom of
the list generated by topological sort) is assigned the lowest priority while the
“shallowest” (at the top of the list produced by topological sort) operation is
assigned the highest priority in the queue.
Next the control software allocates on-chip resources to these operations. The
on-chip resource set R changes with time t . The control software will search for
available resources at the current time for the operation with the highest priority.
For example, if the operation with the highest priority is a mixing operation, then
the system will search for an available m
n electrode sub-array that is not occupied
from current time t to t
C4
t. Here
4
t is the time needed for the operation in the
m
n electrode sub-array. If suitable idle resources are available, resource binding
will be successful and the start time of the operation will be deemed to be the
current time. Otherwise, the operation has to be delayed until there are available
resources. If multiple resources are available at the same time, the control software
will randomly choose one and bind it to the corresponding operation. After binding
the resource and determining the start/stop time, the operation will be removed from
the priority queue.
Note that when multiple errors are detected at the same time, the above steps
can also be used to generate re-synthesis results. In this situation, multiple recovery
processes are triggered at the same time and the control software generates a priority
queue for each recovery process. After these priority queues are merged, the control
software assigns a priority for each element based on topological sort. Finally, the
control software determines new synthesis results for every operation in the merged
priority queue.
For a microfluidic biochip with an M
N electrode sub-array and P dispensing
ports, the computational complexity of looking for available resources (i.e. “the
maximum empty rectangle”) in this re-synthesis algorithm is O(
MN
C
P ). This is
because the software will exhaustively search each electrode/dispensing port in the
array and check whether it is available. As the number of dispensing ports can be
viewed as constant and we are interested in algorithm scalability for large arrays,
the worst-case complexity is O(
MN
). The computational complexity for other parts
of the algorithm are all O(1). Hence the overall computational complexity of the
re-synthesis algorithm is O(
MN
). The pseudocode for the re-synthesis procedure is
can be found in Fig.
2.14
.
