Browse Prior Art Database

Integer Division Implementation for Our Processor

IP.com Disclosure Number: IPCOM000121318D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 4 page(s) / 135K

Publishing Venue

IBM

Related People

Karim, FO: AUTHOR [+2]

Abstract

The requirements for Fixed Point division in the RISC System/6000* (hereinafter "RS/6000") Architecture created implementation problems for our processor. These requirements include two different data length formats, a short divide with two 32-bit 2's complement numbers and long divide with one 64-bit 2's complement and one 32-bit 2's complement number. Another requirement is that division of the maximum representable negative number by negative one should not introduce an overflow.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 39% of the total text.

Integer Division Implementation for Our Processor

      The requirements for Fixed Point division in the RISC
System/6000* (hereinafter "RS/6000") Architecture created
implementation problems for our processor.  These requirements
include two different data length formats, a short divide with two
32-bit 2's complement numbers and long divide with one 64-bit 2's
complement and one 32-bit 2's complement number.  Another requirement
is that division of the maximum representable negative number by
negative one should not introduce an overflow.

      The other major problem is the severe size constraint of our
processor.  We were required to use existing data flow elements as
much as possible, in order to fit this processor on a single chip.

      The solution is in several steps as follows:
      1) The first step is to combine the two formats, divide long
and divide short, into one type so our divide algorithm will not have
to discriminate between them.  This also allows one piece of hardware
to implement both divides.  The divide short requires dividing RA, a
32-bit 2's complement number, by RB, another 32-bit 2's complement
number.  The long divide requires concatenating RA with the MQ
register (32 bits) to create a 64-bit 2's complement number, to be
divided by RB.

      One solution would be to convert the short format into a long
by sign extending RA by 32 bits.  However, this solution would
require more cycles to execute a divide short, causing a large
performance impact.

      The performance problem is resolved by treating both divides as
short, which actually enhances performance of the divide long.
      2) The algorithm chosen is a Radix 2 Nonrestoring division.
This meets our requirement of being able to reuse existing dataflow
elements in our divide implementation.
      3) Nonrestoring division is well suited for positive numbers.
However, it is not well suited for negative numbers in 2's complement
representation.  2's complement representation of negative numbers is
really nothing more than a convention.  For example, negative X is
represented in 2's complement as:
      (2**N)-X...... N being number of the bits in the original X
format
      By dividing the above quantity by Y, it will yield:
      (2**N)/Y - X/Y  which is the wrong result
      The correct result should be:
      (2**N) - X/Y

      To ensure we generate a correct result, we have two choices.
We could convert the negative dividend to a positive one at the
beginning of the divide operation.  This would require both
additional circuits and additional cycles.  A second solution would
be to fix the results as the above equations show.  In terms of both
space and number of cycles, this solution is more cost effective.  We
add {(2**N) *divisor} to the negative dividend to achieve this
fix-up.  Since this addition is only approximated, fix-up may be
required at the end of the operation...