Online arithmetic algorithms for efficient implementation
Paul Kang-Guo Tu, M.D. Ercegovac · 1990
On-line arithmetic algorithms introduce parallelism between sequential operations by overlapping these operations in a digit-pipelined fashion. They can reduce the computation time of long sequences of arithmetic operations. Thus on-line arithmetic complements other approaches such as parallel processing and pipelining which exploit parallelism at the numerical algorithms level. The implementation characteristics of on-line arithmetic algorithms and their applications are investigated. First the model of on-line computation is defined, and a systematic and unified derivation of on-line algorithms is given. Parameters that affect the implementation efficiency of an on-line computation are identified and discussed. Gate array implementation of on-line arithmetic units are presented with estimations of the cost and performance. A case study is conducted and the on-line approach is compared with conventional schemes. The study shows that on-line arithmetic is effective and feasible in the implementation of numerical computations where the critical path contains long sequences of arithmetic operations.