EE 486 Winter 02-03M. J. Flynn 1Computer Architecture & Arithmetic Group 1 Stanford UniversityEE 486 lecture 12: More on Divide,systems issues and SRT.M. J. Flynn(Figures used in slides 4-13 are fromB. Parhami, Computer Arithmetic)Computer Architecture & Arithmetic Group 2 Stanford UniversityNon restoring division• We define the partial remainder as: s(j) = r s(j-1) - qj d• For binary, r =2 and qj in{-1,1}• So we end up with something like: 1-1-1111-1Computer Architecture & Arithmetic Group 3 Stanford UniversityConversion to binary• Shift left by 1• Pad 1 as the new LSB• Keep the 1 as is and replace any -1 by 0• Complement the MSBProof: use bi = (qi+1)/2 or qi = 2 bi -1Computer Architecture & Arithmetic Group 4 Stanford UniversityNon restoring; two views• These are 2 Partialremainder diagrams;– 2 possible quotient digits(or actions)– 3 digits; now including thepossibility of a 0 quotientdigit (or no op action).– The 3 digit set allows aredundant representationPartial remainder diagrams{1, -1}{1,0,-1}Computer Architecture & Arithmetic Group 5 Stanford UniversityPartial Remainder diagrams• Show the partial remainder’s range and thequotient digit to be selected.• Using the digit set {-1,1} recognizes non restorecorrection but each iteration has a full CPA delay.• Using {-1,0,1} allows us to recognize the skipover 0 case and do a no op (Software, variableshift). Also, redundancy allows the delay of onlya CSA per iteration (Hardware).Computer Architecture & Arithmetic Group 6 Stanford UniversitySRT• Sweeney, Robertson and Tocher (SRT)• Use digit redundancy to simplify/ speed updivide.• If we have a redundant set {-1,0,1} forsome combination of s(j) and d (PDcombination) we can select either 0 or –1:or 0 or 1 and still get the same result.EE 486 Winter 02-03M. J. Flynn 2Computer Architecture & Arithmetic Group 7 Stanford UniversityRadix-2 SRT• Choose q to be 0 in[-1/2, +1/2) and 1 forP>= +1/2 and –1 forP <-1/2• Now comparisons arewith =+/-1/2 not withD.Computer Architecture & Arithmetic Group 8 Stanford UniversityRadix-2 SRT• If P is in [-1/2,+1/2)then q = 0; skip andshift.• If P >= +1/2 then q = 1and subtract D• If P < -1/2 then q = -1and add D• Correct by subtracting-1s from 0sComputer Architecture & Arithmetic Group 9 Stanford UniversitySelecting regions• Overlapping regionscan use either digit forquotient. Want tomake the selection tobe easy and well asspeeding up thedivisor add/subtract.Computer Architecture & Arithmetic Group 10 Stanford UniversityUsing CSAs• By forming only ahigh 4b sum for P, wecan select the correctaction; the rest of Pcan be left in S+Cform and returned tothe next iteration thrua CSA (combined withthe D multiple)Computer Architecture & Arithmetic Group 11 Stanford UniversityRadix-4 SRT• Clearly, we want more than 1b per iteration• Radix-4 gives 2b per iteration.• There’s a big tradeoff between theredundancy in the quotient digit set and thequotient selection complexity.• {-3,-2,-1,0,1,2,3} provides easy selection(lots of overlap) but requires +/- 3D.• {-2,-1,0,1,2} makes selection more complexComputer Architecture & Arithmetic Group 12 Stanford UniversityRadix-4 SRTUsing {-3,…,+3)Note the overlap aboveAnd the easy selection(right)EE 486 Winter 02-03M. J. Flynn 3Computer Architecture & Arithmetic Group 13 Stanford UniversityRadix-4 SRTDigit set {-2,..+2}noweasy generation but the selection (right) ismore complex.Computer Architecture & Arithmetic Group 14 Stanford UniversitySRT• Has been the most widely used (especiallyradix-4 ); radix-8 is also sometimes used.That’s probably the practical limit thoughit’s possible to pipeline 2 lower order SRTto get the equivalent of a higher order SRT.• Since it’s subtractive, SRT gives IEEEquotient and the
View Full Document