Error-Coded Algorithms for On-Line Arithmetic

摘要

Since on-line arithmetic requires relatively long sequences of operations in order to achieve speed-up over conventional arithmetic, it is important to protect on-line algorithms against hardware failures. If not protected, the hardware failures could quickly contaminant large number of results in progress due to tight coupling of the steps at the digit level. By detecting errors, as they occur, an effective, gracefully degradable organization could be achieved. Namely, error at any step of the algorithms would lead to restriction of precision (significance) of the remaining steps but not catastrophic termination. The main objective of this dissertation is to develop and demonstrate the feasibility of error-coded on-line arithmetic suitable for distributed systems. In this thesis a set of error-coded on-line algorithms was developed for the four bsic operations of addition/subtraction, multiplication and division. Low cost arithmetic error codes (Residue and AN Codes) were found to be suitable for this purpose. Hardware design of the error-coded units at the gate level was considered. A residue-coded on-line division unit was designed based on a already designed digit-slice division unit. A general mathematical model for the cost and speed of the error-coded units was derived and was compared with similar values when no error code is used. Finally, the effectiveness of the proposed detection/correction schemes was considered and proved. (Author)