Large operand division and an asynchrous approach to fault detection

Citation

Kramer, Kathleen A. (1991) Large operand division and an asynchrous approach to fault detection. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/pt8p-9g83. https://resolver.caltech.edu/CaltechETD:etd-06212007-143920

Abstract

Larger, faster ICs are creating a rash of new problems for the system designer. Designers faced with building larger and larger systems base their architectures on smaller systems that may scale poorly. As a result of VLSI, many new architectures are coming into favor, either because of the changing importance of design factors or because it is now possible to design bigger chips.

Efficient VLSI methods for implementing the basic arithmetic operations can push back many system-performance limitations. There is continued need for re-evaluation of arithmetic architectures, as the efficiency of implementation is related to both implementation technology and size of the operands. A new binary divider for n-bit integer operands, which produces the quotient and remainder in O(n) time using O(n) area, is presented. For very large operands, such as those required in Public Key Cryptography, the new divider is faster than comparable carry-save dividers and is more area-efficient than implementations using more redundant arithmetic.

A further problem faced by the designer of very large systems is their susceptibility to error. The system must be efficiently designed to function in the presence of errors, which become more likely as the size of the system increases. Qualities inherent in many asynchronous designs can be used to provide fault detection and therefore, fault tolerance. An approach to fault tolerance, one not possible with conventional, clocked, systolic arrays, is presented. This method of fault detection/correction exploits the inherent redundancy of architectures using four-state coding, a data-driven technique for implementing bit-level wave-front arrays.

Thesis Files