TY - JOUR
T1 - Coactive Scheduling and Checkpoint Determination During High Level Synthesis of Self-Recovering Microarchitectures
AU - Orailoglu, Alex
AU - Karri, Ramesh
N1 - Funding Information:
Manuscript received March 1, 1993; revised July 29, 1993 and May 5, 1994. This work was supported by NSF grant MIP-9308535. A. Orailoglu is with the Department of Computer Science and Engineering, University of California, San Diego, La Jolla CA 92093 USA. R. Kani is with the Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 01003 USA. IEEE Log Number 9403699.
PY - 1994/9
Y1 - 1994/9
N2 - The growing trend towards VLSI implementation of crucial tasks in critical applications has increased both the demand for and the scope of fault-tolerant VLSI systems. In this paper, we present a self-recovering microarchitecture synthesis system. In a self-recovering microarchitecture, intermediate results are compared at regular intervals, and if correct saved in registers (checkpointing). On the other hand, on detecting a fault, the self-recovering microarchitecture rolls back to a previous checkpoint and retries. The proposed synthesis system comprises of a heuristic and an optimal subsystem. The heuristic synthesis subsystem has two components. Whereas the checkpoint insertion algorithm identifies good checkpoints by successively eliminating clock cycle boundaries that either have a high checkpoint overhead or violate the retry period constraint, the novel edge-based scheduler assigns edges to clock cycle boundaries, in addition to scheduling nodes to clock cycles. Also, checkpoint insertion and edge-based scheduling are intertwined using a flexible synthesis methodology. We additionally show an Integer Linear Programming model for the self-recovering microarchitecture synthesis problem. The resulting ILP formulation can minimize either the number of voters or the overall hardware, subject to constraints on the number of clock cycles, the retry period, and the number of checkpoints.
AB - The growing trend towards VLSI implementation of crucial tasks in critical applications has increased both the demand for and the scope of fault-tolerant VLSI systems. In this paper, we present a self-recovering microarchitecture synthesis system. In a self-recovering microarchitecture, intermediate results are compared at regular intervals, and if correct saved in registers (checkpointing). On the other hand, on detecting a fault, the self-recovering microarchitecture rolls back to a previous checkpoint and retries. The proposed synthesis system comprises of a heuristic and an optimal subsystem. The heuristic synthesis subsystem has two components. Whereas the checkpoint insertion algorithm identifies good checkpoints by successively eliminating clock cycle boundaries that either have a high checkpoint overhead or violate the retry period constraint, the novel edge-based scheduler assigns edges to clock cycle boundaries, in addition to scheduling nodes to clock cycles. Also, checkpoint insertion and edge-based scheduling are intertwined using a flexible synthesis methodology. We additionally show an Integer Linear Programming model for the self-recovering microarchitecture synthesis problem. The resulting ILP formulation can minimize either the number of voters or the overall hardware, subject to constraints on the number of clock cycles, the retry period, and the number of checkpoints.
UR - http://www.scopus.com/inward/record.url?scp=0028501876&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028501876&partnerID=8YFLogxK
U2 - 10.1109/92.311639
DO - 10.1109/92.311639
M3 - Article
AN - SCOPUS:0028501876
SN - 1063-8210
VL - 2
SP - 304
EP - 311
JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems
JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems
IS - 3
ER -