Name
Title | ||
|---|---|---|
Radix-8 Digit-by-Rounding: Achieving High-Performance Reciprocals, Square Roots, and Reciprocal Square Roots |
Abstract | ||
|---|---|---|
We describe a high-performance digit-recurrence algorithm for computing exactly rounded reciprocals, square roots, and reciprocal square roots in hardware at a rate of three result bits -- one radix-8 digit -- per recurrence iteration. To achieve a single-cycle recurrence at a short cycle time, we adapted the digit-by-rounding algorithm, which is normally applied at much higher radices, for efficient operation at radix 8. Using this approach avoids in the recurrence step the lookup table required by SRT -- the usual algorithm used for hardware digit recurrences. The increasing access latency of this table, the size of which grows super linearly in the radix, limits high-frequency SRT implementations to radix 4 or lower. We also developed a series of novel optimizations focused on further reducing the critical path through the recurrence. We propose, for example, decreasing data path widths to a point where erroneous results sometimes occur and then correcting these errors off the critical path. We present a specific implementation that computes any of these functions to 31 bits of precision in 13 cycles. Our implementation achieves a cycle time only 11% longer than the best reported SRT design for the same functions, yet delivers results in five fewer cycles. Finally, we show that even at lower radices, a digit-by-rounding design is likely to have a shorter critical path than one using SRT at the same radix. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/ARITH.2011.28 | IEEE Symposium on Computer Arithmetic |
Keywords | Field | DocType |
digital arithmetic,iterative methods,optimisation,table lookup,SRT design,hardware digit recurrence,high-performance reciprocal,lookup table,radix-8 digit-by-rounding algorithm,reciprocal square roots,recurrence iteration,shorter critical path,single-cycle recurrence,Digit recurrence,exact rounding,prescaling,reciprocal,reciprocal square root,selection by rounding,square root | Reciprocal,Lookup table,Algorithm design,Iterative method,Arithmetic,Algorithm,Radix,Theoretical computer science,Rounding,Critical path method,Square root,Mathematics | Conference |
ISSN | ISBN | Citations |
1063-6889 | 978-1-4244-9457-6 | 4 |
PageRank | References | Authors |
0.42 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Adam Butts | 1 | 249 | 19.76 |
| P. T. P. Tang | 2 | 111 | 11.63 |
| Ron O. Dror | 3 | 439 | 40.56 |
| David Elliot Shaw | 4 | 890 | 139.33 |