Reliable computing with ultra-reduced instruction set co-processors

This work presents a method to reliably perform computations in the presence of hard faults arising from aggressive technology scaling, and design defects from human error. Our method is based on an observation that a single Turing-complete instruction can mirror the semantics of any other instruction. One such instruction is the subleq instruction, which has been used for instructional purposes in the past. We find that the scope for using such a Turing-complete instruction is far greater, and in this paper, we present its applicability to fault tolerance. In particular, we extend a MIPS processor with a co-processor (called ultra-reduced instruction set co-processor - URISC) that implements the subleq instruction. We use the URISC to execute sequences of subleq that are semantically equivalent to the faulty instructions. We formally prove this, and implement the translations in the back-end of the LLVM compiler. We generate binaries for our hardware prototype called MIPS-URISC, which we synthesize and execute on an Altera FPGA. Our experiments indicate the performance and area overheads, and the efficacy of the proposed approach.