NDLI: Radix-8 Digit-by-Rounding: Achieving High-Performance Reciprocals, Square Roots, and Reciprocal Square Roots

Content Provider	IEEE Xplore Digital Library
Author	Butts, J.A. Tang, P.T.P. Dror, R.O. Shaw, D.E.
Copyright Year	2011
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.
Starting Page	149
Ending Page	158
File Size	281489
Page Count	10
File Format	PDF
ISBN	9781424494576
ISSN	10636889
DOI	10.1109/ARITH.2011.28
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-07-25
Publisher Place	Germany
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Approximation methods Hardware Optimization Delay Equations Algorithm design and analysis Complexity theory selection by rounding Digit recurrence reciprocal square root reciprocal square root exact rounding prescaling
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Complex Square Root with Operand Prescaling (2004)

BComplex Square Root with Operand Prescaling (2004)

Complex Square Root with Operand Prescaling (2006)

Complex square root with operand prescaling (2004).

Very-high radix combined division and square root with prescaling and selection by rounding

Correctly rounded reciprocal square-root by digit recurrence and radix-4 implementation

Complex square root with operand prescaling (2004)

Low latency digit-recurrence reciprocal and square-root reciprocal algorithm and architecture

A Radix-16 Combined Complex Division/Square Root Unit with Operand Prescaling

Radix-8 Digit-by-Rounding: Achieving High-Performance Reciprocals, Square Roots, and Reciprocal Square Roots

Similar Documents

Complex Square Root with Operand Prescaling (2004)

BComplex Square Root with Operand Prescaling (2004)

Complex Square Root with Operand Prescaling (2006)

Complex square root with operand prescaling (2004).

Very-high radix combined division and square root with prescaling and selection by rounding

Correctly rounded reciprocal square-root by digit recurrence and radix-4 implementation

Complex square root with operand prescaling (2004)

Low latency digit-recurrence reciprocal and square-root reciprocal algorithm and architecture

A Radix-16 Combined Complex Division/Square Root Unit with Operand Prescaling

Radix-8 Digit-by-Rounding: Achieving High-Performance Reciprocals, Square Roots, and Reciprocal Square Roots