Method and system for performing pipelined reciprocal and reciprocal square root operations

A pipelined circuit configured to generate a Taylor's series approximation at least one function, preferably at least one of the reciprocal and the reciprocal square root, of an input value. The circuit is preloaded with or configured to generate a predetermined set of Taylor's series coefficients for each segment of the input value range. Other aspects of the invention are methods for determining preferred parameters for elements of such a circuit, a circuit designed in accordance with such a method, and a system (e.g., a pipelined graphics processor) for and method of pipelined graphics data processing using any embodiment of the circuit. The preferred parameters are determined by minimizing the circuit's size subject to constraints on input and output value format and output accuracy, assuming a specific function to be approximated and a specific degree for the approximation but allowing variation of parameters such as coefficient width and number of input value range segments.

TECHNICAL FIELD OF THE INVENTION

The invention relates to pipelined arithmetic circuits, to graphics processors (e.g., pipelined vertex processors or other pipelined graphics processors implemented as integrated circuits or portions of integrated circuits), and to methods for pipelined graphics data processing.

BACKGROUND OF THE INVENTION

In three dimensional graphics, surfaces are typically rendered by assembling a plurality of polygons in a desired shape. The polygons (which are typically triangles) are defined by vertices, and each vertex is defined by three dimensional coordinates in world space, by color values, and by texture coordinates and other attributes.

The surface determined by an assembly of polygons is typically intended to be viewed in perspective. To display the surface on a computer monitor, the three dimensional world space coordinates of the vertices are transformed into screen coordinates in which horizontal and vertical values (x, y) define screen position and a depth value z determines how near a vertex is to the screen and thus whether that vertex is viewed with respect to other points at the same screen coordinates. The color values define the brightness of each of red/green/blue (r, g, b) color at each vertex and thus the color (often called diffuse color) at each vertex. Texture coordinates (u, v) define texture map coordinates for each vertex on a particular texture map defined by values stored in memory.

The world space coordinates for the vertices of each polygon are processed to determine the two-dimensional coordinates at which those vertices are to appear on the two-dimensional screen space of an output display. If a triangle's vertices are known in screen space, the positions of all pixels of the triangle vary linearly along scan lines within the triangle in screen space and can thus be determined.

Typically, a rasterizer uses (or a vertex processor and a rasterizer use) the three-dimensional world coordinates of the vertices of each polygon to determine the position of each pixel of each surface (“primitive” surface”) bounded by one of the polygons.

The color values of each pixel of a primitive surface (sometimes referred to herein as a “primitive”) vary linearly along lines through the primitive in world space. A rasterizer performs (or a rasterizer and a vertex processor perform) processes based on linear interpolation of pixel values in screen space, linear interpolation of depth and color values in world space, and perspective transformation between the two spaces to provide pixel coordinates and color values for each pixel of each primitive. The end result of this is that the rasterizer outputs a sequence red/green/blue color values (conventionally referred to as diffuse color values) for each pixel of each primitive.

One or more of the vertex processor, the rasterizer, and a texture processor compute texture coordinates for each pixel of each primitive. The texture coordinates of each pixel of a primitive vary linearly along lines through the primitive in world space. Thus, texture coordinates of a pixel at any position in the primitive can be determined in world space (from the texture coordinates of the vertices) by a process of perspective transformation, and the texture coordinates of each pixel to be displayed on the display screen can be determined. A texture processor can use the texture coordinates (of each pixel to be displayed on the display screen) to index into a corresponding texture map to determine texels (texture color values at the position defined by the texture coordinates for each pixel) to vary the diffuse color values for the pixel. Often the texture processor interpolates texels at a number of positions surrounding the texture coordinates of a pixel to determine a texture value for the pixel. The end result of this is that the texture processor generates data determining a textured version of each pixel (of each primitive) to be displayed on the display screen.

A texture map typically describes a pattern to be applied to a primitive to vary the color of each pixel of the primitive in accordance with the pattern. The texture coordinates of the vertices of the primitive fix the position of the vertices of a polygon on the texture map and thereby determine the texture detail applied to each of the other pixels of the primitive in accordance with the pattern.

FIG. 1is a block diagram of a pipelined graphics processing system that can embody the present invention. Preferably, theFIG. 1system is implemented as an integrated circuit (including other elements not shown inFIG. 1). Alternatively at least one portion (e.g., frame buffer50) of theFIG. 1system is implemented as a chip (or portion of a chip) and at least one other portion thereof (e.g., all elements ofFIG. 1other than frame buffer50) is implemented as another chip (or portion of another chip). Vertex processor10ofFIG. 1generates vertex data indicative of the coordinates of the vertices of each primitive (typically a triangle) of each image to be rendered, and attributes (e.g., color values) of each vertex.

Rasterizer20generates pixel data in response to the vertex data from processor10. The pixel data are indicative of the coordinates of pixels for each primitive, and attributes of each pixel (e.g., color values for each pixel and values that identify one or more textures to be blended with each set of color values). Rasterizer20asserts the pixel data to pixel shader30.

Typically, pixel shader30combines the pixel data received from rasterizer20with texture data and may execute shader programs. For example, one or more texture maps (and a set of texels of each texture map), or no texture maps, are specified for each pixel, and pixel shader30implements an algorithm to generate a texel average in response to the specified texels of each texture map (by retrieving the texels from memory25coupled to pixel shader30and computing an average of the texels of each texture map) and to generate textured pixel data by combining the pixel with each of the texel averages. In typical implementations, pixel shader30can perform various operations in addition to (or instead of) texturing each pixel, such as one or more of the well known operations of format conversion, input swizzle (e.g., duplicating and/or reordering an ordered set of components of a pixel), scaling and biasing, inversion (and/or one or more other logic operations), clamping, and output swizzle.

When pixel shader30has completed all required processing operations on a quantity of pixel data, it asserts the updated (e.g., textured and/or programmably shaded) pixel data to pixel processor40, and pixel processor40performs additional processing on the updated data. In variations on the system ofFIG. 1, pixel processor40is omitted. In this case, pixel shader30is coupled directly to frame buffer50, pixel shader30performs all required processing of the pixels generated by rasterizer20, and pixel shader30is configured to assert the fully processed pixels to frame buffer50. Pixel processor40and/or pixel shader30typically include the OpenGL® “fragment operations.”

Although pixel shader30is sometimes referred to herein as a “texture processor,” in typical implementations it can perform various operations in addition to (or instead of) texturing each pixel, such as one or more of the conventional operations of culling, frustum clipping, polymode operations, polygon offsetting, and fragmenting. Alternatively, texture processor30performs all required texturing operations and pixel processor40performs some or all required non-texturing operations for each pixel.

In typical implementations of pipelined (and other) graphics processors, there is a need to perform reciprocal and reciprocal square root operations (as well as other mathematical operations) on data values. Such operations are commonly performed in vertex processing, pixel shading, and pixel processing units of graphics processors.

Reciprocal and reciprocal square root functions having typically been implemented in hardware using variations of the conventional technique known as Newton-Rapheson iteration. However, the inventors have recognized that generation of the reciprocal (or the reciprocal of the square root) of an input value in pipelined fashion using Newton-Rapheson iteration would require pipelined processing circuitry having an undesirably large number of pipeline stages and an undesirably large footprint (in the case that the processing circuitry is implemented as an integrated circuit or portion of an integrated circuit).

SUMMARY OF THE INVENTION

In accordance with the invention, the reciprocal (or the reciprocal of the square root) of an input value is generated in pipelined fashion in hardware by generating a piecewise quadratic Taylor's series approximation of the desired output value. The piecewise quadratic implementation of reciprocal and reciprocal square root reduces both the pipeline stage latency and the overall silicon area compared to the Newton-Rapheson implementation. For floating point numbers using IEEE 23-bit precision mantissas (IEEE single-precision floating point numbers), the pipeline latency can be reduced by a factor of two (3 cycles vs. 6 cycles) and the overall area can be reduced by 15%.

In a class of embodiments, the invention is a pipelined circuit configured to generate a Taylor's series approximation of at least one and preferably both of the reciprocal and the reciprocal of the square root of an input value. In some such embodiments, the input value is a floating point number having mantissa “x,” and the mantissa of the output value has form A−Bx+Cx2, where A, B, and C are predetermined Taylor's series coefficients. A pipelined processor (e.g., a pipelined graphics processor) can include the inventive pipelined circuit.

All embodiments of the inventive circuit (and processor) are pre-loaded with, or include circuitry for generating, a set of Taylor's series coefficients for each of multiple segments of the input value range. Preferably the range of an input “x” (which can but need not be a mantissa of a floating point word) is partitioned into N segments, “x” is in the “n”th segment when xn-1<x≦xn, with 1≦n≦N, and a set of coefficients An, Bn, and Cnis predetermined for each segment. In order for the circuit to generate the value f(x)=An−Bnx+Cnx2when the input x is in the “n”th segment, the coefficients An, Bn, and Cnfor each segment are predetermined by fitting the curve f(x)=An−Bnx+Cnx2(for x in the relevant segment) to the ideal function curve fideal(x)=A−Bx+Cx2. Preferably, a best combination of the number of segments of the input value range, specific values of coefficients An, Bn, and Cnfor all values of “n,” and word length of the quantity x2to be multiplied by the coefficient Cnis determined by such curve fitting subject to the constraints that the circuit using the coefficients has minimized (or acceptably small) size and that the error in the output value is acceptably small. The number of bits of each coefficient can determine the width of one or more read-only memories (ROMs) for storing them, the number of distinct segments of the input value range can determine the depth of each ROM, and the number of bits of the value Cnx2can determine the size of a multiplier that generates the quantity x2.

In preferred embodiments in which the output value has a mantissa of form An−Bnx+Cnx2, where An, Bn, and Cnare Taylor's series coefficients, the inventive circuit includes three ROMs: one storing the coefficients Anfor all segments of the range of x, another storing the coefficients Bn, and a third storing the coefficients Cn. Optionally, the circuit also includes an error ROM for determining a correction value (e.g., a correction bit) for each input value or each segment of an input value range. If the circuit includes such an error ROM, it can achieve the same accuracy as a CPU; without the error ROM it can achieve such accuracy of plus or minus one LSB. Typically, the circuit has a latency of three clock cycles (one for asserting the coefficients An, Bn, and Cnand a truncated version of x2, another for determining Bnx and Cnx2, and a third for determining An−Bnx+Cnx2(minus the correction bit from the error ROM, optionally) in contrast with the 6-cycle latency of a conventional pipelined circuit. Preferably, the inventive circuit is configured to determine both the reciprocal and the reciprocal of the square root of the input value, and generates an output value in response to the input value and a control word, where the output value is a Taylor's series approximation of the input value's reciprocal when the control word has a first value and the output value is a Taylor's series approximation of the reciprocal of the input value's square root when the control word has a second value. Additional functions can be selected (in response to other values of the control word) if corresponding coefficient tables are stored in the circuit. In variations, the predetermined coefficients are otherwise stored (e.g., in random access memories) or generated by preconfigured circuitry (which can include gate arrays).

In preferred embodiments, the invention is a pipelined circuit in which a set of ROMs (having specific depths and bit widths) stores Taylor's series coefficients for processing input values having floating point format, and a system (e.g., a pipelined graphics processor) including such a circuit. The circuit has a pipeline stage including the set of ROMs (which are preloaded with coefficient values for each term of the approximation of the output word's mantissa) and a multiplier for computing a truncated version of the square of the input value's mantissa. Each ROM preferably has a depth in the range from 128 to 512 bits. In some such embodiments that are configured to process an input value having IEEE floating point format with 23-bit mantissa, “x”, including by generating a 23-bit value An−Bnx+Cnx2, where “n” denotes that x is in the “n”th of N segments of its range, the multiplier outputs a 28-bit value and there are three ROMs (each having depth 256 bits): a first ROM having 26-bit width storing A1coefficients; a second ROM having 19-bit width storing Bicoefficients, and a third ROM having 13-bit width storing C1coefficients.

Another aspect of the invention is a method for determining optimal (or preferred) parameters for elements of a pipelined circuit (or pipelined processor including such a circuit) to include at least one pipeline stage having at least one ROM preloaded with Taylor's series coefficients, a pipelined circuit designed in accordance with such a method, and a pipelined processor including a circuit designed in accordance with such a method. The optimization minimizes the circuit's size (footprint) subject to the constraints that the input and output values have specified format and the output has no more than specified error. The method assumes a specific function (e.g., a reciprocal, reciprocal square root, sine, cosine, or other function) to be approximated using the coefficients and a specific degree for the Taylor's approximation (e.g., a degree of two for a quadratic approximation), but allows variation of such parameters as the length (number of bits) of each coefficient and each generated quantity xn(where x is an input value or truncated input value), and the number of segments of the input value range (each segment having a different set of coefficients). For example, the method can assume generation of the quantity An−Bnx+Cnx2in response to each input value x in an “n”th segment of the input value range, and can determine a combination of the number of segments of the input value range, the specific coefficients An, Bn, and Cn, for each segment, and the word length of the quantity x2multiplied with each coefficient Cn, that minimize the circuit's size subject to given constraints on the format of each input and output value and on maximum allowable error for an output value. Thus, the method can determine an optimal (or preferred) combination of the word length of the output value of a multiplier for computing the quantity x2(i.e., the number of output bits effectively truncated by the multiplier), the width of each ROM that stores coefficients (determined by the word length of each coefficient value stored therein), and the depth of each ROM (the number of segments of the input value range for the relevant term of the Taylor's approximation). For a processor to generate an approximation (whose mantissa has form An−Bnx+Cnx2) of either the reciprocal or reciprocal square root of an input value having IEEE floating point format with 23-bit mantissa “x,” where the processor has a first ROM for the coefficients Ai, a second ROM for coefficients Bi, a third ROM for the coefficients Ci, and a multiplier for generating the quantity x2, the method determines a preferred parameter set specifying that each ROM has 256 bit depth (for storing coefficients for 128 different input value ranges for computing the reciprocal of the input value, for 64 different input value ranges for computing the reciprocal square root of each input value having even exponent, and for 64 different input value ranges for computing the reciprocal square root of each input value having odd exponent), the first ROM has 26-bit width, the second ROM has 19-bit width, the third ROM has 13-bit width, and the multiplier outputs a 28-bit value (effectively truncating 18 bits). For a similar processor for processing input values having floating point format with 16-bit mantissas, including an error ROM in addition to a multiplier, first ROM for Aicoefficients, second ROM for Bicoefficients, and third ROM for Cicoefficients, the method determines a preferred parameter set specifying that each ROM has 512 bit depth (for storing coefficients for 256 different input value ranges for computing the reciprocal of the input value, for 128 different input value ranges for computing the reciprocal square root of each input value having even exponent, and for 128 different input value ranges for computing the reciprocal square root of each input value having odd exponent), the first ROM, second ROM, and third ROM have 24-bit, 16-bit, and 8-bit width, respectively, and the multiplier outputs an 8-bit value (the multiplier receives only the eight most significant bits of the input value and effectively truncates 8 bits of its output). The method searches the parameter space (including the number of bits of each coefficient), which maps to circuit area, for the set of parameters that: (1) can be implemented with the smallest estimated circuit area; and (2) causes all results generated by the pipelined processor to be within 1 LSB accuracy of the ideal result (or some other accuracy measure). The search of the parameter space is optionally done first on a coarse resolution (i.e., not checking every possible parameter value) and then on a fine resolution using the best range found by the coarse search.

Another aspect of the invention is a system for pipelined graphics data processing, including any embodiment of the inventive circuit. For example, the system can include vertex processor (including a triangle setup module), a rasterizer, and a pixel shader. One or more of the components of the system (e.g., both the triangle setup module and the pixel shader) can include the inventive circuit.

Other aspects of the invention are methods for pipelined processing of graphics data to generate an output word in response to an input word of the data, where the input word is indicative of an input value and such that the output word is indicative of a Taylor's series approximation of at least one of the input value's reciprocal and the reciprocal of the square root of the input value.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

The pipelined graphics processing system ofFIG. 1can embody the present invention. The inventive circuitry for determining an input value's reciprocal (and/or the reciprocal of its square root) can be implemented in one or more elements of the system, such as each of vertex processor10(typically in a triangle setup module of vertex processor10), pixel shader30, and pixel processor40.

With reference toFIG. 2, we next describe a pipelined circuit that embodies the invention and can be included in any of vertex processor10, pixel shader30, and pixel processor40ofFIG. 1. The circuitry ofFIG. 2is typically implemented as part of a graphics processing chip that includes numerous components (not shown) in addition to those shown inFIG. 2. The components that are shown inFIG. 2comprise a pipelined circuit that embodies the invention. The pipelined circuit ofFIG. 2is configured to generate, in response to an input value (“x”) and a control word (“Control”), an output value (“Output”) that is a Taylor's series approximation of the reciprocal of the square root of the input value when the control word has a first value, and a Taylor's series approximation of the input value's reciprocal when the control word has a second value. The input value “x” has IEEE floating point format, with a 23-bit mantissa (x_mant[22:0], whose least-significant bit is x_mant[0]), an 8-bit exponent (x_exp[7:0], whose least-significant bit is x_exp[0]), and a sign bit. The output value also has IEEE floating point format, with a 23-bit mantissa (out_mant[22:0]), an 8-bit exponent (out_exp[7:0]), and a sign bit.

The circuit causes the output value's sign bit to equal the input value's sign bit when the circuit implements the “reciprocal” function. The following description assumes that the input value's sign bit is 0 (indicating that the input value is positive) when the circuit implements the “reciprocal of the square root” function. Preferably, the circuit includes logic that recognizes when the input value's sign bit is 1 (indicating that the input value is negative) at a time when the control word has the first value (indicating that the output value is to approximate the reciprocal of the input value's square root), and causes the circuit to output an indication of an invalid operation (rather than a valid output value) in this case.

Some of the coefficients (128 of them in a preferred implementation) stored in each of ROMs41,42, and43are used to compute the reciprocals of input values, and the other coefficients stored in each of ROMs41,42, and43are used to compute the reciprocals of input values' square roots. In a preferred implementation, each of ROMs41,42, and43stores sixty-four coefficients (one for each of sixty-four different input value ranges) for computing the reciprocal square roots of input values having even exponents, and sixty-four coefficients (one for each of sixty-four different input value ranges) for computing the reciprocal square roots of input values having odd exponents, and 128 coefficients (one for each of 128 different input value ranges) for computing the reciprocals of input values (having either even or odd exponents). The control word (“Control”) and the bit indicating whether the input value's exponent is even or odd, asserted to each of ROMs41,42, and43, determine whether the coefficient read from each memory is for computing the reciprocal (or the reciprocal square root) of an input value, and if it is for computing the reciprocal square root, whether the coefficient is for processing an input value having even (or odd) exponent. Preferably, the coefficients stored in ROMs41,42, and43are predetermined in the manner described below.

TheFIG. 2circuit has a latency of three clock cycles. In a first clock cycle, the input value's mantissa and the control word are asserted to each of ROMs41,42, and43and64and each of multiplication circuits44and48, a signal indicative of whether the input value's exponent is even or odd is asserted to each of ROMs41,42, and43, and the mantissa and exponent of the input value are asserted to logic unit56. In response, a 26-bit value indicative of a coefficient Anis asserted from ROM41to math unit51, a 19-bit value indicative of a coefficient Bnis asserted from ROM42to multiplier48, and a 13-bit value indicative of a coefficient Cnis asserted from ROM43to multiplier49. The coefficient values are selected from among those for approximating the input value's reciprocal when the control word has a first value, the coefficient values are selected from among those for approximating the reciprocal of the square root of an input value having even exponent when the control word has a second value and the input value has an even exponent, and the coefficient values are selected from among those for approximating the reciprocal of the square root of an input value having odd exponent when the control word has the second value and the input value has an odd exponent. Also, multiplier44generates a truncated version (a 28-bit value) of the square of the input value's mantissa and asserts this value to multiplier49. Optionally also, control bits are asserted from logic unit56to math unit51.

In a second clock cycle, multiplier48multiplies the input value's mantissa with the coefficient Bnto generate the value “Bnx” and multiplier49multiplies the output of multiplier44(indicative of x2, the square of the input value mantissa) by the coefficient Cnto generate the value “Cnx2.”

In a third clock cycle, math unit51generates a 23-bit value indicative of f(x)=An−Bnx+Cnx2, which is the mantissa of the desired approximation of the reciprocal (or the reciprocal of the square root) of input value x. The output value f(x) is asserted to a first input of multiplexer52. Unless a special case exists, the “special case” control bit from logic unit56causes multiplexer52to pass through the output value f(x) as the output value's mantissa “out_mant[22:0].”

TheFIG. 2circuit employs multiplexers45and46and subtraction unit47to generate the output value's exponent “out_mant[7:0].” The least significant bit (“x_exp[0]”) of the input value's exponent is asserted as a control bit to each of multiplexers45and46. In response, multiplexer45passes to a first input of unit47an 8-bit word indicative of either the value “256” (if x_exp[0]=1) or the value “257” (if x_exp[0]=0), and multiplexer46passes to a second input of unit47an 8-bit word indicative of either the value “190” (if x_exp[0]=1) or the value “191” (if x_exp[0]=0). The seven other bits of the input value's exponent are asserted to the third input of unit47. Depending on the value of the control word, unit47subtracts the value it its third input from either the value at its first input (when the control word has the first value) or the value at its second input (when the control word has the second value) to generate an 8-bit word which is the exponent of the desired approximation of the reciprocal (or the reciprocal of the square root) of the input value, unless a special case exists. Unit47asserts this 8-bit word to a first input of multiplexer53. Unless a special case exists, the “special case” control bit from logic unit56causes multiplexer53to pass through the 8-bit word from unit47as the exponent “out_exp[7:0]” of the output value.

Logic unit56is configured for handling special cases, and is coupled to receive the mantissa and exponent of the input value x. When logic unit56determines that the input value is not a valid number (i.e., that “x” is an “NaN” value rather than a floating point number), it asserts (to a second input of multiplexer52) a 23-bit value and (to a second input of multiplexer53) an eight-bit value that together indicate that “x” is an “NaN” value, and asserts to both multiplexers52and53a “special case” control bit causing the multiplexers to pass through these two values as the mantissa and exponent, respectively, of the output value. When unit56determines that the input value is zero, it asserts to the second input of multiplexer52a 23-bit value and to the second input of multiplexer53an eight-bit value that together indicate that the reciprocal of the square root of “x” is infinity (or that computing the reciprocal of the square root of “x” is an illegal operation), and asserts to multiplexers52and53a special case control bit causing the multiplexers to pass through these two values as the output value. When unit56determines that the input value is an infinite value, it asserts to the second input of multiplexer53a 23-bit value and to the second input of multiplexer53an eight-bit value that together indicate that that the reciprocal of the square root of “x” is zero (or that computing the reciprocal of the square root of “x” is an illegal operation), and asserts to multiplexers52and53a special case control bit causing the multiplexers to pass through these two values as the output value.

Variations on theFIG. 2embodiment employ circuitry configured to generate the appropriate Taylor's series coefficients in response to the input value's mantissa (and a control word indicative of the function to be implemented on the input value) rather than ROMs or other memories (such as random access memories) into which the coefficients are pre-loaded. The coefficient-generating circuitry can include logic circuitry, gates, and/or transistor circuits.

For example, the circuit ofFIG. 4is a variation on theFIG. 2circuit in which coefficient generation circuitry140replaces ROMs41,42, and42, and exponent generation circuitry141replaces elements45,46, and47. With coefficient generation circuitry140configured to generate and assert the same coefficients that are asserted by ROMs41,42, and42in response to the same input values and control word, and exponent generation circuitry141configured to assert the same exponent as does element47(in response to the same input and control word), the other elements ofFIG. 4can be identical to the identically numbered elements ofFIG. 2. Thus, the above description of these elements will not be repeated with reference toFIG. 4. Elements140and141are preferably hardwired but are optionally implemented so as to be programmable.

In all embodiments of the inventive circuit, the circuit is pre-loaded with, or includes circuitry for generating, a predetermined set of Taylor's series coefficients for performing an approximation (which can have either zero or nonzero error) of a desired function (e.g., a reciprocal, reciprocal square root, sine, cosine, or other function) on an input value. The Taylor's series approximation of the function can have any degree, and can employ different sets of coefficients (each set comprising “n+1” coefficients, when the approximation has degree “n”) for input values in different value ranges.

In preferred embodiments, the inventive circuit implements a piecewise quadratic Taylor's series approximation, f(x)=An−Bnx+Cnx2, of an input value x. The range of x is partitioned into N segments, x is in the “n”th segment when xn-1<x≦xn, with 1≦n≦N, and a set of coefficients An, Bn, and Cnfor each segment is predetermined by fitting a curve f(x)=An−Bnx+Cnx2(for x in the segment) to the ideal function curve fideal(x)=A−Bx+Cx2. Preferably, the best combination of coefficients An, Bn, and Cnfor all values of “n,” a total number of segments, and a word length of the quantity x2to be multiplied by Cn, is determined by such curve fitting subject to the constraints that the circuit using the coefficients has acceptably small size and that the error in the output value is acceptably small. The number of bits of each coefficient can determine the width of a read-only memory (ROM) for storing it, the number of distinct segments can determine the depth of each ROM for storing coefficients, and the number of bits of the value Cnx2can determine the size of a multiplier that generates x2. In identifying the best values of the relevant parameters, the number of bits of each coefficient is mapped to the width of the ROM for storing it, the number (N) of distinct segments is mapped to the depth of each ROM for storing components of one term of the Taylor's series approximation (the An, Bn, or Cncomponents), and the number of bits of the value x2is mapped to the size of the circuitry (e.g., a multiplier) that generates x2.

In a class of embodiments, the inventive circuit is configured to implement a Taylor's series approximation of each of at least two functions (f1(x) and f2(x)) on an input value. Each circuit can be configured to approximate additional functions (f3(x), f4(x), etc., in addition to f1(x) and f2(x)) by predetermining a set of Taylor's series coefficients for each additional function, and storing the predetermined coefficients in ROMs or configuring the circuit to generate coefficients from each predetermined set.

Another embodiment of a circuit implemented in accordance with the invention to implement a Taylor's series approximation of the reciprocal of the square root of the input value is that shown inFIG. 3. The circuitry ofFIG. 3is included in a graphics processing chip which, in typical implementations, includes numerous components (not shown) in addition to those shown. The components of the chip that are shown inFIG. 3comprise a pipelined circuit that embodies the invention.

The pipelined circuit ofFIG. 3is configured to respond to an input value (“x”) by asserting an output value (“rsqrt”) that is a Taylor's series approximation of the reciprocal of the square root of the input value. The input value “x” has floating point format, with a 16-bit mantissa (“x_mant[15:0],” whose least-significant bit is x_mant[0]), an 8-bit exponent (“x_exp[7:0],” whose least-significant bit is x_exp[0]), and a sign bit. The output value “rsqrt” also has floating point format, with a 16-bit mantissa (“rsqrt_mant[15:0]),” an 8-bit exponent (“rsqrt_exp[7:0]”), and a sign bit. The following description assumes that the input value's sign bit is 0 (indicating that the input value is positive). Preferably, the circuit includes logic that recognizes when the input value's sign bit is 1 (indicating that the input value is negative) and causes the circuit to output an indication of an invalid operation (rather than a valid output value) in this case.

In some implementations of theFIG. 3circuit, only 256 of the coefficients stored in each of ROMs60,62, and64are used to compute the reciprocal of each input value's square root. For example, 256 coefficients stored in each of ROMs60,62, and64(for computing the reciprocal of each input value's square root) can comprise two subsets: a first subset for each of 128 different ranges of input mantissa values (for input words having even exponents); and a second subset for each of 128 different ranges of input mantissa values (for input words having odd exponents). In other implementations of theFIG. 3circuit, 512 coefficients stored in each of ROMs60,62, and64are used to compute the reciprocal of each input value's square root, with the coefficients stored in each ROM comprising two subsets: a first subset for each of 256 different ranges of input mantissa values (for input words having even exponents); and a second subset for each of 256 different ranges of input mantissa values (for input words having odd exponents).

In all implementations ofFIG. 3, the coefficients are preferably are predetermined in the manner described above with reference toFIG. 2.

In implementations of theFIG. 3circuit in which only 256 coefficients stored in each of ROMs60,62, and64are used to compute the reciprocal of each input value's square root, another set of 256 coefficients is typically stored in each of ROMs60,62, and64for use in computing the reciprocal of each input value. In such typical implementation, the circuit operates in response to a control signal that determines whether to compute the reciprocal (or reciprocal of the square root) of each input value, and the circuit includes circuitry (not shown inFIG. 3) for use in generating either the reciprocal or the reciprocal of the square root of each input value.

Still with reference toFIG. 3, error ROM66(having 153-bit depth and two-bit width) stores a set of correction words, each comprising two bits and being indicative of a correction bit having the value 0, +1, or −1. The words stored in ROM66are predetermined with knowledge of the error that would result from processing (without any correction bit) each input value in theFIG. 3circuit with the set of An, Bn, and Cncoefficients (stored in ROMs60,62, and64) for the segment of the input value range that includes the input value. In response to the mantissa of each input value “x” (and a signal indicative of whether the input value's exponent is even or odd), error ROM66asserts a two-bit word indicative of a correction bit to be subtracted (in unit74) from the value An−Bnx+Cnx2generated by unit74. By including error ROM66and providing correction bits to math unit74, theFIG. 3circuit can assert the output value's mantissa with the same accuracy as can a conventional CPU.

TheFIG. 3circuit has a latency of three clock cycles. In a first clock cycle, the eight most significant bits of the input value's mantissa are asserted to each of ROMs60,62, and64and each of multiplication circuits68and70, a signal indicative of whether the input value's exponent is even or odd is asserted to each of ROMs60,62, and64, and the mantissa and exponent of the input value are asserted to logic unit76. In response, a 26-bit value (indicative of the 24-bit coefficient Anconcatenated with two control bits from logic unit76) is asserted from ROM60to math unit74, a 17-bit value (indicative of the 16-bit coefficient Bnconcatenated with a control bit from logic unit76) is asserted from ROM62to multiplier70, and the coefficient Cnis asserted from ROM64to multiplier72. Also, multiplier68generates an 8-bit value indicative of a truncated version of the square of the input value mantissa and asserts this value to multiplier72.

In a second clock cycle, multiplier70multiplies the eight most significant bits of the input value's mantissa with the coefficient Bnto generate the 25-bit value “Bnx” and multiplier72multiplies the output of multiplier68(indicative of the square of the input value's mantissa) with the coefficient Cnto generate the 16-bit value “Cnx2.”

In a third clock cycle, math unit74generates a 16-bit value indicative of f(x)=An−Bnx+Cnx2−(the correction bit from error ROM66), which is the mantissa of the desired approximation of the reciprocal of the square root of input value x. In some implementations, a rounding bit may need to be added to the other terms to generate the output value f(x). The output value f(x) is asserted to a first input of multiplexer79. Unless a special case exists, the “special case” control bit from logic unit76causes multiplexer79to pass through the output value f(x) as the mantissa “rsqrt_mant[15:0]” of the output value “rsqrt.”

TheFIG. 3circuit employs multiplexer61and subtraction unit63to generate the exponent “rsqrt_mant[7:0]” of the output value “rsqrt.” The least significant bit of the input value's exponent is asserted as a control bit to multiplexer61. In response, multiplexer61passes to a first input of unit63an 8-bit word indicative of either the value “190” (if the least significant bit of the input value's exponent is one) or the value “191” (if the least significant bit of the input value's exponent is zero). The seven other bits of the input value's exponent are asserted to the second input of unit63. Unit63subtracts the value at its second input from the value at its first input to generate an 8-bit word “out_exp” which is the exponent of the desired approximation of the reciprocal of the square root of input value x. The word “out_exp” is asserted to a first input of multiplexer78. Unless a special case exists, the “special case” control bit from logic unit76causes multiplexer78to pass through the word out_exp as the exponent “rsqrt_exp[7:0]” of the output value “rsqrt.”

Logic unit76is provided for handling special cases, and is coupled to receive the mantissa and exponent of the input value x. When logic unit76determines that the input value is not a valid number (i.e., that “x” is an “NaN” value rather than a floating point number), it asserts to a second input of multiplexer79a sixteen-bit value and to a second input of multiplexer78an eight-bit value that together indicate that “x” is an “NaN” value, and asserts to both multiplexers78and79a “special case” control bit causing the multiplexers to pass through these two values as the mantissa and exponent, respectively, of the output value “rsqrt.” When unit76determines that the input value is zero, it asserts to the second input of multiplexer79a sixteen-bit value and to the second input of multiplexer78an eight-bit value that together indicate that the reciprocal of the square root of “x” is infinity (or that computing the reciprocal of the square root of “x” is an illegal operation), and asserts to multiplexers78and79a special case control bit causing the multiplexers to pass through these two values as the output value “rsqrt.” When unit76determines that the input value is an infinite value, it asserts to the second input of multiplexer79a sixteen-bit value and to the second input of multiplexer78an eight-bit value that together indicate that that the reciprocal of the square root of “x” is zero (or that computing the reciprocal of the square root of “x” is an illegal operation), and asserts to multiplexers78and79a special case control bit causing the multiplexers to pass through these two values as the output value “rsqrt.”

In a broad class of preferred embodiments, including preferred implementations of both theFIG. 2andFIG. 3circuits, the invention is a pipelined circuit in which a set of ROMs (having specific depths and bit widths) stores Taylor's series coefficients for processing input values having floating point format. In another broad class of embodiments, the invention is a pipelined graphics processor (or other system) including such a circuit. Each such circuit has a pipeline stage including the set of ROMs (which are preloaded with coefficient values for each term of a Taylor's series approximation that determines the output word's mantissa) and a multiplier for computing a truncated version of the square of the input value's mantissa.

In this class of embodiments, each ROM preferably has a depth in the range from 128 to 512 bits. For example, for one such circuit that generates an output word mantissa having form An−Bpx+Cqx2, where “x” is the mantissa of the input value mantissa (or a truncated version thereof), Anis a coefficient of a first coefficient set, Bpis a coefficient of a second coefficient set, and Cqis a coefficient of a third coefficient set, and 1≦n≦N1, 1≦p≦N2, and 1≦q≦N3, the circuit can have a pipeline stage that includes a first ROM preloaded with N1different ones of the coefficients An, a second ROM preloaded with N2different ones of the coefficients Bp, and a third ROM preloaded with N3different ones of the coefficients Cq, where N1, N2, and N3preferably satisfy 128≦N1≦512, 128≦N2≦512, and 128≦N3≦512. Some embodiments in the class are configured to process input values having IEEE floating point format with 23-bit mantissas, and have three ROMs each having depth 256 bits. Other ones of the embodiments have two ROMs or more than three ROMs. In one preferred embodiment configured to process an IEEE floating point input value having 23-bit mantissa “x,” including by generating a 23-bit value An−Bnx+Cnx2(where “n” denotes that x is in the “n”th of N segments of its range), the multiplier outputs a 28-bit value, and a pipeline stage includes three ROMs (each having depth 256 bits): a first ROM having 26-bit width storing Aicoefficients; a second ROM having 19-bit width storing Bicoefficients, and a third ROM having 13-bit width storing Cicoefficients. Preferably, each ROM stores two sets of Taylor's series coefficients: a first set comprising coefficients for each of 128 different segments of the range of “x” for computing the reciprocal of the input value, and a second set for computing the reciprocal of the input value's square root. Preferably, the set for computing the reciprocal of the input value's square root comprises two subsets: a first subset for each of 64 different segments of the range of “x” (for input words having even exponents); and a second subset for each of 64 different segments of the range of “x” (for input words having odd exponents). Preferably, the circuit generates an output value in response to a control word as well as the input value having IEEE floating point format, the output value is a Taylor's series approximation of the reciprocal of the input value when the control word has a first value, and the output value is a Taylor's series approximation of the reciprocal of the input value's square root when the control word has a second value.

What follows is computer source code, in the language C, which:

simulates theFIG. 2embodiment of the inventive circuit. In the source code, the input value mantissa (“x_mant” inFIG. 2) is denoted as “x” (or “in_mant”), the input value exponent (“x_exp” inFIG. 2) is denoted as “in_exp”, and the control word (“Control” inFIG. 2) is a single bit denoted as “mode.” If the mode bit has a first value (mode=0), the program simulates generation of the reciprocal of the input. If the mode bit has the complementary value (mode=1), the program simulates generation of the reciprocal of the square root of the input. The simulation code assumes that the Taylor's series coefficients have been predetermined and performs special case handling (including by checking for a zero or infinite value of the exponent or mantissa of the input);

determines a set of Taylor's series coefficients for approximating the reciprocal of an input value (the input value is denoted as “g” in the relevant portion of the source code). The code generates three coefficients (An, Bn, and Cn) for each segment of the input value range, assuming a predetermined number of segments (2RCPLU) of the input value range; and

determines a set of Taylor's series coefficients for approximating the reciprocal of the square root of an input value. The code generates three coefficients (An, Bn, and Cn) for each segment of the input value range, assuming a predetermined number of segments (2RSQLU) of the input value range, and taking into account whether the input value has even or odd exponent.

The following parameters are employed in the source code:

EW: the width (number of bits) of the exponent of each input word;

MW: the width (number of bits) of the mantissa of each input word;

RSQLU: 2RSQLUis the number of segments of the input value range for which coefficients are predetermined for use in generating the reciprocal of the square root of the input;

RCPLU: 2RCPLUis the number of segments of the input value range for which coefficients are predetermined for use in generating the reciprocal of the input;

ABITS: the width (number of bits) of each of the Ancoefficients; and

TRUNCK2: the number of bits effectively truncated by the multiplier that generates the square of the input (if the word length of the multiplier's output is L, and the input is a 23-bit mantissa of a floating point word, then TRUNCK2 satisfies TRUNCK2=46−L).

The following values of the last four of these parameters, identified by the optimization method (described below) assuming that EW=10 and MW=23, are typically employed in the source code: RSQLU=6; RCPLU=7; ABITS=26; and TRUNCK2=18.

The portion of the code identified by the comment “first do reciprocal square root table” determines Taylor's series coefficients for use in generating the reciprocal of the square root of the input, including by computing an “exact” mantissa of the reciprocal of the square root of the input (using the Matlab function “1.0/sqrt(g)”) and comparing it with at least one trial value (“guess mantissa”) generated using a trial set of coefficients, for an input value “g” in each segment of the input value range. The following portion of the code (identified by the comment “now do reciprocal table”) determines Taylor's series coefficients for use in generating the reciprocal of the input, including by computing an “exact” mantissa of the reciprocal of the input (using the Matlab function “1.0/g”) and comparing it with at least one trial value (“guess mantissa”) generated using a trial set of coefficients, for an input value “g” in each segment of the input value range.

The remaining portion of the code (beginning at the comment “write the table functions”) simulates theFIG. 2embodiment of the inventive circuit, using a previously determined set of coefficients for generating the reciprocal of the square root of the input and another predetermined set of coefficients for generating the reciprocal of the input. The portion of this code following the comment “check for special cases” simulates the operation of logic unit56, including by identifying whether the input value is not a valid number (setting “out_NaN” equal to 1 when the input value is not a valid number), whether the input value is zero, and whether the input value is infinite.

The source code is as follows:

Another aspect of the invention is a method for determining optimal (or preferred) parameters for elements of a pipelined circuit (or pipelined processor) having at least one pipeline stage including ROMs pre-loaded with Taylor's series coefficients, where the optimization minimizes the circuit's size (footprint) with the constraints that the input values have specified format and the output has no more than acceptable error. The method assumes a specific function (e.g., reciprocal, reciprocal square root, sine, cosine, or some other function) to be approximated using the coefficients and a specific degree for the Taylor's approximation (e.g., a degree of two for a quadratic approximation). For example, the method can assume that a quadratic approximation of form An−Bnx+Cnx2is to be generated for each input value x in the “n”th segment of the input value range, and determine coefficients An, Bn, and Cnfor each segment that minimize the circuit's size subject to given constraints on input value format and output value error. For a circuit having a multiplier for computing a truncated version of the square of the input value as well as ROMs for storing Taylor's series coefficients, the method can determine an optimal (or preferred) combination of the width of each coefficient value (and thus the width of each ROM), the number of segments of the input value range for each term of the Taylor's approximation (and thus the depth of each ROM), and the width of the multiplier's output value (i.e., the number of bits truncated by the multiplier). For a circuit operable to generate an approximation (whose mantissa has form An−Bnx+Cnx2) of either the reciprocal or reciprocal square root of an input word having IEEE floating point format with 23-bit mantissa, where the circuit has a first ROM for Aicoefficients, a second ROM for Bicoefficients, and a third ROM for Cicoefficients, the method determines a preferred parameter set specifying that each ROM has 256 bit depth (for storing coefficients for 128 different input value ranges for computing the reciprocal of the input value, for 64 different input value ranges for computing the reciprocal square root of each input value having even exponent, and for 64 different input value ranges for computing the reciprocal square root of each input value having odd exponent), the first ROM has 26-bit width, the second ROM has 19-bit width, the third ROM has 13-bit width, and the multiplier outputs a 28-bit value (18 bits are effectively truncated). For a similar circuit, where each input word has IEEE floating point format with 16-bit mantissa, the circuit includes an error ROM, and the circuit has a first ROM for Aicoefficients, a second ROM for Bicoefficients, and a third ROM for Cicoefficients, the method determines a preferred parameter set specifying that each ROM has 512 bit depth (for storing coefficients for 256 different input value ranges for computing the reciprocal of the input value, for 128 different input value ranges for computing the reciprocal square root of each input value having even exponent, and for 128 different input value ranges for computing the reciprocal square root of each input value having odd exponent), the first ROM has 24-bit width, the second ROM has 16-bit width, the third ROM has 8-bit width, and the multiplier outputs an 8-bit value (the multiplier receives only the eight most significant bits of the input value and 8 bits of the output are effectively truncated).

Preferably, the parameter-determining method minimizes the width of an multiplier's output value indicative of xn, where x is the input value (i.e., the method maximizes the number of bits truncated by the multiplier) even at the expense of widening the ROMs for storing the Taylor's series coefficients (i.e., even at the expense of using wider coefficients). Preferably, the method searches the parameter space (including the number of bits of each coefficient and the number of input value range segments), which maps to circuit area, for the set of parameters that (1) can be implemented with the smallest estimated circuit area; and (2) causes all results generated by the pipelined circuit to be within 1 LSB accuracy of the ideal result (or some other accuracy measure). The search of the parameter space is optionally done first on a coarse resolution (i.e., not checking every possible parameter value) and then on a fine resolution using the best range found by the coarse search.

Another aspect of the invention is a system for pipelined processing of graphics data, including any embodiment of the inventive circuit for generating an output word in response to an input word indicative of an input value, the output word being indicative of a Taylor's series approximation of the reciprocal (or the reciprocal of the square root) of the input value. For example, the system can include vertex processor (including a triangle setup module), a rasterizer, and a pixel shader. The inventive circuit can be implemented in one or more of the components of the system (e.g., in both the triangle setup module and the pixel shader).

Other embodiments are methods for pipelined processing of graphics data to generate an output word in response to an input word of the data, wherein the input word is indicative of an input value and such that the output word is indicative of a Taylor's series approximation of at least one of the input value's reciprocal and the reciprocal of the square root of the input value, said method including the steps of:

(a) generating a first set of values in response to the input word during a first interval, the values in the first set including a Taylor's series coefficient for each term of a Taylor's series approximation of one of the output word and a mantissa of the output word; and

(b) after step (a), during a subsequent interval, generating the approximation of said one of the output word and the mantissa of the output word by performing at least one of addition, multiplication, and subtraction on a second set of values, wherein the values in the second set include at least one of the values in the first set and at least one intermediate value generated after step (a) and before step (b) in response to values including at least one other one of the values in the first set.

In some embodiments, the input word has a first mantissa and a first exponent, the output word has a second mantissa and a second exponent, the values in the first set include a coefficient value for each term of a Taylor's series approximation of the second mantissa, step (b) includes the step of generating the Taylor's series approximation of the second mantissa, and the method also includes the step of generating the second exponent in response to the first exponent.

In some embodiments, the first mantissa is in one of multiple segments of a range, and step (a) includes the step of generating the coefficient value for said each term of the approximation of the second mantissa in response to data indicating which of the segments includes the first mantissa, or the step of reading the coefficient value for said each term of the approximation of the second mantissa from at least one memory in response to data indicating which of the segments includes the first mantissa.

In some embodiments, the output word is generated in response to the input word and a control word, the output word is indicative of a Taylor's series approximation of the input value's reciprocal when the control word has a first value, and the output word is indicative of a Taylor's series approximation of the reciprocal of the input value's square root when the control word has a second value, and step (a) includes the step of generating the first set of values in response to the input word and the control word.

It should be understood that while certain forms of the invention have been illustrated and described herein, the invention is not to be limited to the specific embodiments described and shown or the specific methods described. The claims that describe methods do not imply any specific order of steps unless explicitly described in the claim language.