A pipelined processing unit for on-line division

ABSTRACT

A division algorithm suitable for pipelining is presented. The algorithm possesses the on-line property: that is, to generate the jth digit of a result (where a digit consists of n bits for base 2n), it is necessary and sufficient to have the operands available only up to the jth digit plus a predetermined number of extra digits which correspond to an “on-line delay”. This delay is shown to be a small, positive, radix dependent constant. The implementation of this algorithm and the implications on cost and speed are then presented. Finally, alterations in the design making the algorithm suitable for pipelining and its benefits are discussed.

REFERENCES

• 1: Anderson, S. F., et. al., "The System/360 Model 91 Floating Point Execution Unit," IBM System Journal 11, Vol. 34, 1967.
• 2: Atkins, D. E., "Higher Radix Division Using Estimates of the Divisor and Partial Remainders," IEEE Transactions on Computers, Vol. C-17, No. 10, pp. 925-934, October 1968.
• 3: Daniel Ewell Atkins, III, A study of methods for selection of quotient digits during digital division, 1970
• 4: Atkins, D. E., "Introduction to the Role of Redundancy in Computer Arithmetic," Computer, Vol. 8, No. 6, pp. 74-76, June 1975.
• 5: Chen, T. C., "Overlap and Pipeline Processing," Introduction to Computer Architecture, H. S. Stone, (Ed.), SRA, Chicago, IL, 1975.
• 6: DeLugish, B. G., "A Class of Algorithms for Automatic Evaluation of Certain Elementary Functions in a Binary Computer," Ph.D. Thesis, Report 399, Department of Computer Science, University of Illinois, Urbana, June 1970.
• 7: Freiman, C. V., "Statistical Analysis of Certain Binary Division Algorithms," Proceedings of the IRE, Vol. 49, pp. 91-103, January 1961.
• 8: Hallin, T. and M. Flynn, "Pipelining of Arithmetic Functions," IEEE Transactions on Computers, Vol. C-21, pp. 880-886, August 1972.
• 9: Irwin, M. J., "An Arithmetic Unit for On-line Computation," Report No. UIUCDCS-R-77-873, Department of Computer Science, University of Illinois, Urbana, May 1977.
• 10: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 11: C. V. Ramamoorthy , H. F. Li, Pipeline Architecture, ACM Computing Surveys (CSUR), v.9 n.1, p.61-102, March 1977 [doi>10.1145/356683.356687]
• 12: Robertson, J. E., "A New Class of Digital Division Methods," IRE Transactions on Electronic Computers, Vol. EC-7, pp. 218-222, September 1958.
• 13: Robertson, J. E., "Methods of Selection of Quotient Digits During Digital Division," Report 663, Department of Computer Science, University of Illinois, Urbana, 1965.
• 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]
• 15: Trivedi, K. S. and M. D. Ercegovac, "On-line Algorithms for Division and Multiplication," Proceedings of Third IEEE Symposium on Computer Arithmetic, Dallas, Texas, November 1975.
• 16: Trivedi, K. and M. D. Ercegovac, "On-line Algorithms for Division and Multiplication," IEEE Transaction on Computers, Vol. C-26, No. 7, pp. 681-687, July 1977.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

General Terms:
Design