Stanford EE 486 - EE 486 lecture 12- More on Divide, systems issues and SRT

Unformatted text preview:

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

Stanford EE 486 - EE 486 lecture 12- More on Divide, systems issues and SRT

Download EE 486 lecture 12- More on Divide, systems issues and SRT
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view EE 486 lecture 12- More on Divide, systems issues and SRT and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view EE 486 lecture 12- More on Divide, systems issues and SRT 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?