On-line algorithms for the design of pipeline architectures

ABSTRACT

This paper presents a class of algorithms, On-Line Continued Sums/Products, which are amenable for the efficient implementation by a pipeline architecture. The implementation of these algorithms provides a simple and fast method for the evaluation of several of the elementary functions; i.e., addition, subtraction, multiplication, division, logarithm, exponentiation, sine, cosine, and tangent. In addition to possessing the expected properties necessary for the efficient implementation in a pipeline architecture, the On-Line Continued Sums/Products algorithms allow for the possibility of implementing a pipeline architecture which is dynamically reconfigurable and which can process variable precision operands.

REFERENCES

• 1: D. E. Atkins, "Introduction to the Role of Redundancy in Computer Arithmetic," Computer, Vol. 8, No. 6, pp. 74-76, June 1975.
• 2: F. A. Rohatsch, "A Study of Transformations Applicable to the Development of Limited Carry-Borrow Propagation Adders," Ph.D. Thesis, Report No. 226, Department of Computer Science, University of Illinois, Urbana, June 1967.
• 3: J. E. Volder, "The CORDIC Trigonometric Computing Technique," IRE Transactions on Electronic Computers, Vol. EC-8, No. 5, pp. 330-334, Sept. 1959.
• 4: B. G. DeLugish, "A Class of Algorithms for Automatic Evaluation of Certain Elementary Functions in a Binary Computer," Ph.D. Thesis, Report No. 339, Department of Computer Science, University of Illinois, Urbana, June 1970.
• 5: P. W. Baker, "More Efficient Radix-2 Algorithms for Some Elementary Functions," IEEE Transactions on Computers, Vol. C-24, No. 11, Nov. 1975.
• 6: W. H. Specker, "A Class of Algorithms for Ln X, Exp X, Sin X, Cos X, Tan-1 X, Cot-1 X," IEEE Transactions on Electronic Computers, Vol. EC-14, No. 1, pp. 85-86, Feb. 1965.
• 7: J. E. Robertson, "A New Class of Digital Division Methods," IRE Transactions on Electronic Computers, Vol. EC-7, pp. 218-222, Sept. 1958.
• 8: M. D. Ercegovac, "Radix-16 Evaluation of Certain Elementary Functions," IEEE Transactions on Electronic Computers, Vol. C-22, No. 6, pp. 561-566, June 1973.
• 9: Mary Jane Irwin, Reconfigurable Pipeline Systems, Proceedings of the 1978 annual conference, p.86-92, December 04-06, 1978, Washington, D.C., United States [doi>10.1145/800127.804073]
• 10: Mary Jane Irwin, An arithmetic unit for on-line computation., 1977
• 11: K. S. Trivedi & M. D. Ercegovac, "On-Line Algorithms for Division and Multiplication," IEEE Transactions on Computers, Vol. C-26, No. 7, pp. 681-687, July 1977.
• 12: Milos Dragutin Ercegovac, A general method for evaluation of functions and computations in a digital computer., 1975
• 13: M. D. Ercegovac, "An On-Line Square Rooting Algorithm," Proceedings of Fourth Symposium on Computer Arithmetic, Santa Monica, CA, October 1978.
• 14: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.1 Design Styles
          Subjects: Pipeline

General Terms:
Algorithms, Design

Keywords:
Continued sums/products, Dynamically reconfigurable, Elementary functions, On-line algorithms, Pipeline architecture, Redundancy