UNIVERSITY OF MASSACHUSETTS Dept of Electrical Computer Engineering Digital Computer Arithmetic CE666 Koren Part 7b 1 ECE 666 Part 7b Fast Division II Israel Koren Spring 2008 Copyright 2008 Koren High Radix Division Number of add subtracts in radix 2 SRT is data dependent Asynchronous circuit needed to use reduced number of nonzero bits in quotient Increasing number of 0 s in quotient limited practical significance Number of add subtracts reduced by increasing radix m 2 m quotient bits generated each step Number of steps reduced to n m Recursive equation for remainder ri ri 1 qi Dm Multiply by 2 shift left remainder by m bit positions Digit set for quotient 0 1 1 for restoring division Up to 1 1 0 1 1 for high radix SRT division CE666 Koren Part 7b 2 Copyright 2008 Koren High Radix Restoring Division All previous division algorithms can use radix 2 Restoring division Initial guess qi 1 If remainder ri 1 D 0 increase to qi 2 Subtract D from temporary remainder ri 1 2D Repeat until qi j temporary remainder ri 1 jD negative Remainder restored by adding D ri 1 j 1 D qi j 1 Time consuming no advantage over binary algorithm Can be parallelized by circuits comparing ri 1 to several multiples jD selecting smallest positive remainder substantial hardware requirement Binary nonrestoring division similar changes CE666 Koren Part 7b 3 Copyright 2008 Koren High Radix SRT Algorithm Faster than binary version Quotient digit qi signed digit in range 1 1 0 1 where 1 2 1 1 Finding possible choices for in high radix division Quotient digit qi selected so that ri D otherwise next quotient digit may be or larger Guarantees convergence of division procedure For maximal remainder ri 1 D ulp and positive D largest value for qi should guarantee ri in allowable region CE666 Koren Part 7b 4 Copyright 2008 Koren Reducing Remainder Range ri D ulp D D ulp Select for only maximum value 1 May consider division where ri k D k is a fraction reduce size of allowable for remainder ri k D ulp D ulp k 1 region k D k 1 1 2 k 1 allows selection of any in 1 2 1 Larger k larger redundancy for quotient CE666 Koren Part 7b 5 Copyright 2008 Koren 4 2 Example k 1 2 3 ri kD 2 3 D ri 1 4ri 1 8 3 D or ri D 2 3 and 4ri 1 D 8 3 Digit set for qi 2 1 0 1 2 Region for selecting q 2 3 4ri 1 D q 2 3 or 2 3 q 4ri 1 D 2 3 q Region examples For selecting qi 2 8 3 4 3 4ri 1 D For selecting qi 1 1 3 4ri 1 D 5 3 Overlapping region 4 3 4ri 1 D 5 3 select either qi 1 or qi 2 Similar overlapping regions exist for any 2 adjoining digits CE666 Koren Part 7b 6 Copyright 2008 Koren Measure of Redundancy Ratio k 1 measure of redundancy in representation of quotient Larger k larger overlap regions in plot of ri D vs ri1 D Example 3 4 k 1 maximum redundancy Region for qi 1 0 4ri 1 D 2 Region for qi 2 1 4ri 1 D 3 Overlapping region 1 4ri 1 D 2 Larger than overlap region for 2 4 k 2 3 CE666 Koren Part 7b 7 Copyright 2008 Koren Implication of Overlap Region Provides choice of comparison constants for partial remainder and divisor Can be selected to require as few digits as possible Reducing execution time of comparison step when determining quotient digit Larger larger overlap region larger choice fewer digits On the other hand larger more D multiples extra hardware and or time required For given determining number of bits of partial remainder and divisor to be examined is the most difficult step when developing highradix SRT Can be done numerically analytically graphically or by combination of techniques CE666 Koren Part 7b 8 Copyright 2008 Koren Graphical Approach P D Plotremainder ri Basic equation for partial 1 ri qiD Notation P previous partial remainder ri 1 Partial remainder vs Divisor plot indicates regions in which given values of q may be selected Limits on P for given q k D ri k D Pmin k q D Pmax k q D Regions for q j and q j 1 Only positive values of divisor overlap and partial remainder 1 4 of complete P D plot plot symmetric about both axes Only values of D in Dmin Dmax are of interest e g 0 5 1 1 2 IEEE floating point CE666 Koren Part 7b 9 Copyright 2008 Koren Separating Selection Regions Value of P separating selection regions of q j q j 1 Serves as comparison constant Its number of bits determines necessary precision when examining partial remainder to select q Line separating regions is horizontal P c selection independent of D if k j Dmin c k j 1 Dmax Otherwise line is stairstep partitioning Dmin Dmax into intervals Stepping points determine precision number of digits of examining D Height of steps determines precision examining partial remainder CE666 Koren Part 7b 10 of q and only if subof Copyright 2008 Koren Determining Precision Notation X Y maximum width height of a step between D1 and D2 Horizontal vertical distance between the 2 lines defining overlap region X D2 D1 P k j 1 P k j P 2k 1 j j 1 k 1 k X minimal when j is max and P is min jmax 1 P minimal when D1 Dmin Xmin Dmin k 1 2k 1 1 k 1 k Y k j D k j 1 D 2k 1 D Y is minimal when D Dmin It is sufficient to consider overlapping region between q and q 1 near Dmin CE666 Koren Part 7b 11 Copyright 2008 Koren Precision Cont Notation NP ND number of examined bits of partial remainder divisor P D number of fractional bits in NP ND Selecting q look up table implemented in a PLA programmable logic array with NP ND inputs Minimizing size of look up table speeds up division D p Precision of partial remainder truncated p D divisor 2 2 2 Xmin 2 Ymin Only upper bounds for precision the 2 extreme points X Y may require higher precision more than CE666 Koren Part 7b 12 P D fractional bits Copyright 2008 Koren Using P D Plot To determine precision To select q for each P D when truncated to NP ND bits Limited precision taken into account Point P D represents all partial remainder divisor pairs with P partial remainder P 2 p D divisor D 2 D Selected q must be legitimate for all pairs in range Example Point A Divisor D2 select q j 1 divisor D2 2 select q j DA or any Conclusion do not select q j 1 for point other point in overlap region whose horizontal distance from the line k j 1 D 2 CE666 Koren Part 7b 13 D Copyright 2008 Koren Example P D Plot …