Hardware Reference
In-Depth Information
3.2.2
Dictionary Entries for Single-Operation Errors
By inserting an error in the bioassay and recording the corresponding re-synthesis
results, we can get the entries in Level 1 of the error dictionary. The re-synthesis
problem can also be solved using the PRSA-based global-optimization method [
16
]
while the CPU time is relatively long [
14
].
In [
14
], the algorithm for deriving new sequencing graph with error recovery
operations is proposed. Based on the synthesis result in the error free case, the newly
added operations for error recovery are “inserted” into the synthesis result of the
error free case in a greedy fashion [
14
]. Therefore, the re-synthesis results for error
recovery can be generated within limited CPU time.
By explicitly analyzing all possible situations corresponding to all the potential
single errors that may occur for a bioassay, we can derive the entries in Level 1 of
the error dictionary. For example, the sequencing graph shown in Fig.
2.1
ahasfive
mixing operations, and there are five error candidates if we only consider errors in
mixing and assume that only one error occurs during the bioassay. We can derive
the error-recovery results for all of the potential errors and store the results during
the “off-line data preparation” stage, as shown in Table
3.1
.
Tab le
3.1
is loaded into the memory of the FPGA; it determines the state
transition of the FSM running on the FPGA. At time t
D
0, the FSM comes into
State 0. The biochip begins to execute the bioassay based on the initial synthesis
result. At time t
s
D
6, operation Mix 2 is completed, the sensing system checks
the output of Mix 2. If an error is deemed to have occurred, the FSM transits to the
corresponding state (State 2) and loads the re-synthesis result that is stored in the
error dictionary (the third entry in Table
3.1
). It is important to note that the synthesis
results for all operations in the second entry start from time t
D
6.SinceMix3
is being executed when an error occurs at Mix 2, it will continue to be executed
according to the initial synthesis result. All operations that may be interrupted by
the transition for the state of the controller are marked by “*” in Table
3.1
.In
this manner, the controller can dynamically adapt and do re-synthesis of the on-
chip chemistry by looking up entries in the error dictionary; then the computational
complexity of on-line re-synthesis of the bioassay is reduced to O(1).
Note that each entry in the dictionary contains only the re-synthesis result from
the time moment that the error is detected to the end of the bioassay. For example,
the dictionary entry that corresponds to State 1 shown in Table
3.1
records the
re-synthesis result from the 12th second (i.e., the moment in time that the error
occurs in operation Mix 1 is detected) to the 21st second (i.e., the time moment that
the entire bioassay is completed). The time span of this dictionary entry is 9 s. Based
on the above discussions, we note that there are various time spans for the entries in
Level 1 of the dictionary.
