Floating-Point Division and Square Root: Choosing the Right Implementation

this paper is to clarify and evaluate the implementation tradeoffs at the FPU level, thus enabling designers to make informed decisions. Division and square root have long been considered minor, bothersome members of the floating-point family. Microprocessor designers frequently perceive them as infrequent, low-priority operations, barely worth the trouble of implementing; design effort and chip resources are allocated accordingly. The survey of microprocessor FPU performance in Table 1 shows some of the uneven results of this philosophy. While multiplication requires from 2 to 5 machine cycles, division latencies range from 9 to 60. The variation is even greater for square root, which is not supported in hardware in several cases. This data hints at but mostly conceals the significant variation in algorithms and topologies among the different implementations. The error in the Intel Pentium floating-point unit, and the accompanying publicity and $475 million write-off illustrate some of the hazards of an incorrect division implementation [8]. But correctness is not enough; low performance causes enough problems of its own. Even though divide and square root are relatively infrequent operations in most applications, they are indispensable, particularly in many scientific programs. Compiler optimizations tend to increase the frequency of these operations [11]; poor implementations disproportionatelypenalize code which uses them at all [10]. Furthermore, as the latency gap grows between addition and multiplication on the one hand and divide/square root on the other, the latter increasingly become performance bottlenecks [14]. Programmers have attempted to get around this problem by rewriting algorithms to avoid divide/square root operations, but the resulting code generall..