UNIVERSITY OF MASSACHUSETTS Dept of Electrical Computer Engineering Digital Computer Arithmetic CE666 Koren Part 7c 1 ECE 666 Part 7c Fast Division III Israel Koren Spring 2008 Copyright 2008 Koren Speeding Up the Division Process Unlike multiplication steps of division are serial Division step consists of selecting quotient digit and calculating new partial remainder Two ways to speed up division 1 Overlapping full precision calculation of partial remainder in step i with selecting quotient digit in step i 1 Possible since not all bits of new partial remainder must be known to select next quotient digit 2 Replacing carry propagate add subtract operation for calculating new partial remainder by carry save operation CE666 Koren Part 7c 2 Copyright 2008 Koren First Speed Up Method Truncated approximation of new partial remainder calculated in parallel to full precision calculation of partial remainder can be done at high speed Quotient digit determined before current step completed Instead of 1 Calculate ri 1 with carry propagation in step i 1 2 input NP most significant bits to PLA to determine qi Use a small adder with inputs most significant bits of previous partial remainder ri 2 and most significant bits of corresponding multiple of divisor qi 1D Approximate Partial Remainder APR adder CE666 Koren Part 7c 3 Copyright 2008 Koren Approximate Partial Remainder Adder Produces approximation of NP most significant bits of partial remainder ri1 before full precision add sub operation ri 1 ri 2 qi 1D is completed Allows to perform look ahead selection of qi in parallel with calculation of ri 1 Size of APR adder determined so that sufficiently accurate NP bits generated Uncertainty in result of this adder larger than of truncated previous partial remainder ri 2 may need additional inputs for quotient lookup table 8 bit APR adder sufficient to generate necessary inputs to PLA for 4 2 CE666 Koren Part 7c 4 Copyright 2008 Koren Example P D Plot 4 2 D 1 2 Horizontal lines determined to reduce complexity of PLA Only 3 divisor bits needed as PLA inputs most significant bit of divisor always 1 For partial remainder 5 bits including sign bit sufficient in most cases CE666 Koren Part 7c 5 Copyright 2008 Koren Positive Remainder 3 cases a b c when additional bit required Case a D 1 001 P 1 1 single fractional bit of P insufficient Divisor can assume any value from 1 001 to 1 010 Partial remainder can have a value from 1 1 to 10 0 range for P D from 1 1 1 010 1 2 to 10 0 1 001 1 77 First requires q 1 while second requires q 2 Add 2nd fractional bit to P Can select q 1 for P 1 10 and q 2 for P 1 11 CE666 Koren Part 7c 6 Copyright 2008 Koren Cases b and c 8 bit APR adder may introduce additional error increasing P D range Case b D 1 100 P 10 0 No APR adder P D range from 10 0 1 101 1 23 to 10 1 1 100 1 66 q 1 can be selected 8 bit APR adder introduces error of up to 2 in ri 1 increases to 2 after multiplying by 4 This 6additional error increases maximum value of P D from 1 66 to 4 1 7 requiring q 2 An extra fractional bit of P solves this problem CE666 Koren Part 7c 7 Copyright 2008 Koren Negative Partial Remainder Represented in two s complement 6 cases 1 or even 2 additional output bits of APR adder required to guarantee correct selection of quotient digit CE666 Koren Part 7c 8 Copyright 2008 Koren Second Speed Up Method In first method time needed for division step determined by add subtract for remainder quotient digit selected in previous step Second method avoids time consuming carry propagation when calculating remainder Truncated remainder sufficient for selecting next quotient digit no need to complete calculation of remainder at any intermediate step Replace carry propagate adder by carry save adder Partial remainder in a redundant form using 2 sequences of intermediate sum and carry bits stored in 2 registers Only most significant sum and carry bits must be assimilated using APR adder to generate approximate remainder and allow selection of quotient digit CE666 Koren Part 7c 9 Copyright 2008 Koren SRT Divider with Redundant Remainder Most time consuming calculate approximate remainder and select quotient digit In each division step carrysave adder calculates remainder APR adder accepts most significant sum and carry bits of remainder generates required inputs to quotient selection PLA As in first method number of PLA inputs and its entries need to be calculated taking into account uncertainty in sum and carry bits representing truncated remainder CE666 Koren Part 7c 10 Copyright 2008 Koren Example An algorithm for high speed division with 4 2 D 1 2 has been implemented Partial remainder calculated in carry save manner resulting in a somewhat more complex design 8 bit APR adder used to generate most significant remainder bits inputs to quotient selection PLA Inputs to APR adder 8 most significant sum bits and carry bits in redundant representation of remainder Outputs of APR adder converted to a signmagnitude representation only 4 bits of approximate partial remainder needed in most cases Additional bit required only in 4 cases simple PLA CE666 Koren Part 7c 11 Copyright 2008 Koren Further Speed up of SRT Division Achieved by increasing radix to 8 or higher Reduces number of steps to n 3 or lower Several radix 8 SRT dividers have been implemented Main disadvantage high complexity of PLA most time consuming unit of divider m Avoiding complex PLA implementing radix 2 SRT unit as a set of m overlapping radix 2 SRT stages Radix 2 SRT requires very simple quotient selection logic qi 1 0 1 solely determined by remainder independent of divisor Must overlap quotient selections for m bits all m quotient bits generated in one step CE666 Koren Part 7c 12 Copyright 2008 Koren Two Overlapping Radix 2 SRT Stages Implementing radix 4 division All 3 possible values of qi 1 generated using 3 Qsel units correspond to 3 possible intermediate remainders 2Only most bits ri 1 D 2ri 1significant 2riremainders generated 1 D of 3 Overall delay CSA Qsel two Mux and final CSA May be faster than radix 4 stage higher complexity of radix 4 PLA CE666 Koren Part 7c 13 Copyright 2008 Koren Extending to Radix 8 SRT division More complex quotient selection circuit 3 quotient digits qi qi 1 qi 2 generated in parallel For qi 1 calculate speculative remainders 2ri 1 D 2ri 1 2ri 1 D For qi 2 calculate 4ri 4ri 1 3D 4ri 1 2D 4ri 1 D 4ri 1 4ri 1 D 1 2D 4ri 1 3D Only most significant bits of these 7 remainders 7 Qsel units