Electrical – SRT division vs Non restoring division

algorithmarithmetic-division

Assuming base b=2, is there a particular advantage in terms of performance when comparing SRT division to non restoring division?

In Non restoring division, for each iteration, the output digits belong to the set {-1,1} which implies that an addition or subtraction is always performed.

In SRT for each iteration the output digits belong to the set {-1,0,1}, where the 0 has the meaning of not performing operation when the partial reminder is particularly small,

Is the only advantage the fact that it allows to bypass some addition subtraction? Does just this thing make the whole division faster? I also suppose that full advantage can be taken if one design such divider asyncronously, am I wrong?

Best Answer

SRT division magic is being able to iterate without having to perform carry propagation over all the bits of the dividend (and partial remainder). That means that you can reach higher frequencies, that an single and double precision divider can use the same clock, or that you can cascade several SRT divisors or use higher radices to calculate more than 1 bit per cycle...

In non-restoring, to decide whether you need to add or subtract, you need to complete the previous addition or subtraction and determine precisely whether the result is positive or negative. In SRT, you only need to check a few MSBs (IIRC, around 2 for SRT radix 2, around 7-10 from the remainder and divisor for radix 4, combining division and square root is also possible with moderate additional complexity) : The SRT algorithm only needs an approximate result to decide whether an addition, a subtraction, or nothing is expected.

Addition and subtraction for SRT should be done using "carry-save" (or borrow-save, etc.) adders that don't perform carry propagation. Carry propagation and conversion to two's complement format is really needed only for the few bits needed for the SRT decision : +1/0/-1 for radix-2 or +2/+1/0/-1/-2 for radix 4, etc.

The result is also calculated without carry propagation by keeping two values R = result and RM=R-1, adding one bit to the right for each cycle :

SRT = 0 : R'=R & '0', RM'=RM & '1'
SRT = +1 : R'=R & '1', RM'=R & '0'
SRT = -1 : R'=R' & '1', RM'=R' & '0'

Related Solutions

Electronic – hardware implementation of division algorithm

Flowcharts are often not a very precise way of indicating what hardware is doing, since flowcharts often imply the existence of a single execution process, whereas hardware often does many overlapping and simultaneous operations.

The portions of the diagram circled in red seem a bit odd. It seems odd to latch A with the value after subtracting B, and then re-add B. More natural would simply be to not bother latching the lower part of the subtraction result. I think the flowchart might be clearer if "named values" were separated into "registers" and "values", and each step either computed values or registers. Thus, for example, one could have something like (assuming 16-bit registers)

C:T[15..0] = (A[14..0]:Q[15]) + ~B-1
if (C or A[15])
  A[15..0] = (A[14..0]:Q[15])
  Q[15..1] = Q[14..0]
  Q[0] = 1
Else
  A[15..0] = T[15..0]
  Q[15..1] = Q[14..0]
  Q[0] = 0
Endif

Every step that updates registers would represent a system clock. Events that merely compute values would not require a clock edge, but would be processed asynchronously.

Electronic – How does division occur in our computers

Division algorithms in digital designs can be divided into two main categories. Slow division and fast division.

I suggest you read up on how binary addition and subtraction work if you are not yet familiar with these concepts.

Slow Division

The simplest slow methods all work in the following way: Subtract the denominator from the numerator. Do this recursively with the result of each subtraction until the remainder is less than the denominator. The amount of iterations is the integer quotient, and the amount left over is the remainder.

Example:

7/3:

$$7-3=4$$
$$4-3=1$$
$$1 < 3$$

Thus the answer is 2 with a remainder of 1. To make this answer a bit more relevant, here is some background. Binary subtraction via addition of the negative is performed e.g.: 7 - 3 = 7 + (-3). This is accomplished by using its two's complement. Each binary number is added using a series of full adders:

enter image description here

Where each 1-bit full adder gets implemented as follows:

enter image description here

Fast Division

While the slower method of division is easy to understand, it requires repetitive iterations. There exist various "fast" algorithms, but they all rely on estimation.

Consider the Goldschmidt method:

I'll make use of the following: $$Q = \frac{N}{D}$$

This method works as follows:

Multiply N and D with a fraction F in such a way that D approaches 1.
As D approaches 1, N approaches Q

This method uses binary multiplication via iterative addition, which is also used in modern AMD CPUs.

Best Answer

Related Solutions

Electronic – hardware implementation of division algorithm

Electronic – How does division occur in our computers

Related Topic