Specialized processing block with fixed- and floating-point structures

Description

FIELD OF THE INVENTION

This invention relates to a programmable integrated circuit device, and particularly to a specialized processing block in a programmable integrated circuit device.

BACKGROUND OF THE INVENTION

Considering a programmable logic device (PLD) as one example of an integrated circuit device, as applications for which PLDs are used increase in complexity, it has become more common to design PLDs to include specialized processing blocks in addition to blocks of generic programmable logic resources. Such specialized processing blocks may include a concentration of circuitry on a PLD that has been partly or fully hardwired to perform one or more specific tasks, such as a logical or a mathematical operation. A specialized processing block may also contain one or more specialized structures, such as an array of configurable memory elements. Examples of structures that are commonly implemented in such specialized processing blocks include: multipliers, arithmetic logic units (ALUs), barrel-shifters, various memory elements (such as FIFO/LIFO/SIPO/RAM/ROM/CAM blocks and register files), AND/NAND/OR/NOR arrays, etc., or combinations thereof.

One particularly useful type of specialized processing block that has been provided on PLDs is a digital signal processing (DSP) block, which may be used to process, e.g., audio signals. Such blocks are frequently also referred to as multiply-accumulate (“MAC”) blocks, because they include structures to perform multiplication operations, and sums and/or accumulations of multiplication operations.

For example, PLDs sold by Altera Corporation, of San Jose, Calif., as part of the STRATIX® and ARRIA® families include DSP blocks, each of which includes a plurality of multipliers. Each of those DSP blocks also includes adders and registers, as well as programmable connectors (e.g., multiplexers) that allow the various components of the block to be configured in different ways.

Typically, the arithmetic operators (adders and multipliers) in such specialized processing blocks have been fixed-point operators. If floating-point operators were needed, the user would construct them outside the specialized processing block using general-purpose programmable logic of the device, or using a combination of the fixed-point operators inside the specialized processing block with additional logic in the general-purpose programmable logic.

One impediment to incorporating floating-point operators directly into specialized processing blocks is the need for large addition operations as part of many floating-point operations. For example, floating-point multiplication may require two carry-propagate adders. The carry-propagate adder used in a multiplication operation is an expensive component of the multiplier in terms of both area and latency.

SUMMARY OF THE INVENTION

In accordance with embodiments of the present invention, specialized processing blocks such as the DSP blocks described above may be enhanced by including floating-point addition among the functions available in the DSP block, without increasing the number of carry-propagate adders. This is accomplished, in part, by simultaneously computing a sum, as well as that sum plus 1 (in its least significant bit) and that sum plus 2 (in its least significant bits), and then selecting the appropriate result based on the result of another part of the operation. The same structures, and, in particular, at least the sum and sum-plus-1 computations, may be used for both fixed-point operations and floating-point operations.

An adder circuit capable of both fixed-point addition and floating-point addition may be incorporated into the DSP block, and can be independently accessed, or used in combination with multipliers in the DSP block, or even multipliers in adjacent DSP blocks. A DSP block incorporating a fixed-and-floating-point-capable adder in accordance with the invention remains backward-compatible with fixed-point functionality of known DSP blocks.

Therefore, in accordance with embodiments of the present invention there is provided circuitry for performing arithmetic operations on a plurality of inputs. The circuitry includes at least first and second respective operator circuits. Each of the at least first and second respective operator circuits operates on a respective subplurality of the plurality of inputs. Other circuitry selectively interconnects the at least first and second respective operator circuits so that they can operate together or separately, according to user selection, on selected ones of (a) the full plurality of inputs, (b) individual ones of the respective subpluralities of the plurality of inputs, or (c) combinations of portions of the respective subpluralities of the plurality of inputs. At least one of the respective operator circuits includes circuits for simultaneously computing multiple different results and for selecting among the multiple different results based on an output of another one of the respective operator circuits. One or more of said multiple different results are selectably usable for both fixed-point operations and floating-point operations.

A specialized processing block incorporating the circuitry, and a programmable integrated circuit device incorporating the specialized processing block, are also provided.

BRIEF DESCRIPTION OF THE DRAWINGS

Further features of the invention, its nature and various advantages will be apparent upon consideration of the following detailed description, taken in conjunction with the accompanying drawings, in which like reference characters refer to like parts throughout, and in which:

FIG. 1 shows a logical diagram of a multiplier structure of an exemplary DSP block according to an embodiment of the invention for performing either fixed-point or floating-point operations;

FIG. 2 shows an embodiment of a deconstructed adder in the structure of FIG. 1;

FIGS. 3A and 3B, hereinafter referred to collectively as FIG. 3, show details of one embodiment of one portion of a deconstructed adder such as that of FIG. 2; and

FIG. 4 is a simplified block diagram of an exemplary system employing a programmable logic device incorporating the present invention.

DETAILED DESCRIPTION

In a specialized processing block—particularly a DSP block—in accordance with embodiments of the present invention, the adder is decomposed into a prefix structure aligned with both fixed-point and floating-point modes. In known floating-point structures, a carry-propagate adder is used, followed by normalization and then by rounding, which involves a second carry-propagate adder. But according to embodiments of the invention, three floating-point steps can be combined into a single level of carry-propagate adder by calculating different subsets of the carry propagate adder inputs as sum, sum-plus-1, and sum-plus-2. Other subsets of the larger carry-propagate adder are also calculated at the same time. The different subset results can be combined in multiple ways to implement either a floating-point adder or multiplier or multiple different types of fixed-point adder or multiplier combinations. The different subset results can be assembled into the required floating-point or fixed-point values by concatenation, thereby avoiding the need to propagate additional carry values over the subset results to obtain the correct output values.

FIG. 1 shows a logical diagram of the multiplier structure 100 according to an embodiment of the invention for performing either fixed-point or floating-point operations. In this logical representation, implementational details, such as registers and some programmable routing features—such as multiplexers that may allow the output of a particular structure to be routed around certain components or directly out of a DSP block (when implemented in a DSP block)—are omitted to simplify discussion.

In the logical representation of FIG. 1, the “left multiplier” 101 is a partial product generator such as an 18×18 partial product generator (which may be used, e.g., as two 9×18 partial product generators), which produce two dimensionless output vectors 111, 121. Similarly, the “right multiplier” 102 is a partial product generator such as an 18×18 partial product generator (which may be used, e.g., as a 18×9 partial product generator and a 27×9 partial product generator), which produce two dimensionless output vectors 112, 122. Together, partial product generators 101, 102 can be used as a 27×27 partial product generator, to support single-precision floating-point multiplication, which under the IEEE754-1985 standard has a mantissa size of 23 (exclusive of an implied leading ‘1’). Input multiplexer stage 103 combines and aligns between four and six inputs 113 according to the needs of a particular user logic design.

The four dimensionless output vectors 111, 112, 121, 122 are combined by 4:2 compressor 104 into two dimensionless output vectors 114, 124. Multiplexers 105, 106 can be used to align vectors 111, 121 and 121, 122, respectively, according to the type of operation being performed, as determined by the user logic design. Specifically, the vectors can be totally offset from one another (e.g., to perform two separate smaller multiplications, such as two 9×9 multiplications), totally aligned with one another (e.g., to perform one larger multiplication, such as one 18×18 multiplication), or partially aligned with one another (e.g., to perform a “rectangular” multiplication, such as a 9×18 multiplication). In one implementation, each of the input and output vectors of compressor 104 may be up to 74 bits wide.

Another vector 117 may be input from another similar block. Vector 117, along with vectors 114, 124 are input to a 3:2 compressor 108 to provide vectors 118, 128. A further multiplexer 109 selects between vectors 114, 124 and vectors 118, 128, allowing compressor 108 to be bypassed if cascade input 117 is not used. AND gate 107 allows input 117 to be zeroed when, for example, the structure is being used in an accumulator mode and the accumulator has to be reset. Output vectors 119, 129, each up to 74 bits wide, are input to adder 200 to provide the resultant product of the multiplication operation, which can be a fixed-point output 130 or a floating-point output 131. In a floating-point case, the exponent may be handled at 132.

When multiplying two floating-point numbers according to the IEEE754-1985 standard, the input multiplicands are normalized numbers between 1.0₁₀ and 1. 9₁₀. Therefore, the resultant product can be between 1.0₁₀ and 3. 9₁₀, and may be subject to normalization and rounding. To accommodate normalization and rounding, it may be necessary to add either zero, 1 or 2₁₀ to the least significant bit(s) of the result. Specifically, normalization involves a right-shift of 0 bits or 1 bit (if the result greater than or equal to 1.0 and less than 2.0₁₀, the right-shift is 0 bits; if the result is greater than or equal to 2.0₁₀ and less than 4.0₁₀ the right-shift is 1 bit). In cases where rounding is not applied, whether the normalization is 0 bits or 1 bit, the sum-plus-zero (i.e., the sum) may be used. In cases where rounding is applied, then if the normalization is 0 bits, the sum-plus-1 may be used, while if the normalization is 1 bit, the sum-plus-2 may be used. Therefore, in accordance with embodiments of the invention, and as described in more detail below, those three quantities (sum, sum-plus-1 and sum-plus-2) are generated simultaneously using different portions of the circuitry, and then selected using a carry signal from another portion of the calculation. This avoids the need to wait for that other portion of the calculation before generating the appropriate result (sum, sum-plus-1 or sum-plus-2).

In one embodiment, this is accomplished by decomposing adder 200 into three adders—a low adder 201, a middle adder 202 and a high adder 203. Adders 201, 202, 203 can be used together for a single large fixed-point addition (e.g., adding two 74-bit numbers). For other types of additions (which may result from different multiplication operations), adders 201, 202, 203 can be used in different combinations.

For example, in the example shown in FIG. 2, the inputs of low adder 201 are 23 bits wide, the inputs of adder 202 are 31 bits wide, and the inputs of adder 203 are 20 bits wide. At one extreme, as noted above, adders 201, 202, 203 can be used together to perform a single large fixed-point addition operation (e.g., any addition operation between 55 and 74 bits wide). At the other extreme, adders 201, 202, 203 can be used individually to perform three separate fixed-point addition operations. In between, adders 201, 202, 203 can be used to perform two additions, one or both of which, e.g., may come from separate multipliers. Thus, one addition operation may be performed in low adder 201 and the lower range of middle adder 202, while a second addition operation may be performed in high adder 203 and the upper range of middle adder 202.

When performing two addition operations as just described, each addition operation could be a fixed-point operation. Alternatively, one or both of the two addition operations could be floating-point operations. In the implementation depicted in FIG. 2, the upper addition operation—i.e., the addition operation performed in high adder 230 and the upper range of middle adder 202—would be a fixed-point operation, while the lower addition operation—i.e., the addition operation performed in low adder 201 and the lower range of middle adder 202—could be either a fixed-point operation or a floating-point operation.

Because an addition operation will be spanning the boundary between low adder 201 and middle adder 202, information must be carried across that boundary. As can be seen in FIG. 2, carry information 211 controls multiplexers 212, 222 which, as described in more detail below, are used for fixed-point operations.

In a floating-point context, the location of the least significant bit of the result could actually straddle the boundary—sometimes falling on one side and sometimes falling on the other—depending on the precision and on the particular input values. Information from low adder 201 is needed, along with other information, to establish the location of the least significant bit. Floating-point rounding logic 204 uses the carry information 211, along with the lowermost bits 232 from adder 202 and round-to-nearest-even signal 221 (which combines all but the highest bit from adder 201 in OR-gate 214 to determine the presence of a ‘1’ in any bit location, signifying, when the highest bit from adder 201 is a ‘1’, whether the result from adder 201 is exactly 0.5₁₀ or greater than 0.5₁₀) to generate selection signal 224 to select the correct floating-point output using multiplexer 242.

As discussed briefly above, depending on the particular inputs, the correct output from adder 202 may be either the sum of its inputs (205), the sum of its inputs with 1 added to the least significant bit (206), or the sum of its inputs with 2₁₀ added to the least significant bits (207). In one embodiment, the latter possibility is a possibility only in a floating-point addition, while the other two possibilities are possibilities for either fixed-point addition or floating-point addition. Moreover, where the middle adder 202 is being split between two operations, the upper range output 208 of sum 205 may be output separately.

As also discussed in part above, the selection of the appropriate output(s) from adder 202 is made by multiplexers 212, 222, 242. In the floating-point case, as discussed above, one of sum 205, sum-plus-1 206 and sum-plus-2 207 is selected by multiplexer 242 based on selection signal 224 from floating-point rounding logic 204. In a fixed-point case, multiplexers 212, 222 select between the respective ranges of sum 205 and sum-plus-1 206 based on carry signal 211 from low adder 201 (as noted above, sum plus-2 207 is used only in a floating-point case) or, for multiplexer 212 only, the upper range 208 of the sum.

One possible implementation of middle adder 202 is shown in FIG. 3. 31-bit portions 301, 302 of vectors 119, 129 to be added are input to a half-adder 303, which provides two 32-bit vector outputs, which may be referred to as half-add-sum 313 and half-add-carry 323. Half-add-sum vector 313 is the 31-bit result of the bitwise XOR of vector 301 and vector 302; the 32nd bit is not used. Half-add-carry vector 323 is a 32-bit vector resulting from a 1-bit left-shift of the bitwise AND of vector 301 and vector 302, with a ‘0’ inserted in its least-significant bit position (the most significant bit—i.e., bit 32—of vector 323 is used as carry information from adder 202 to adder 203). The output vectors are divided into lower halves 333, 343 and upper halves 353, 363. These half-adder output vectors are input to a parallel prefix network tree 304, which may include three prefix networks 314, 324, 334. Each prefix network may be, for example, a Kogge-Stone prefix network, which outputs respective generate and propagate vectors.

The lower vectors 333, 343 are input to prefix network 314 to provide generate and propagate vectors 315, 325. The upper vectors 353, 363 are input to prefix network 324 to provide generate and propagate vectors 335, 345. Vectors 335, 345 are input to prefix network 334 along with the prefix(g,p) output 305 of the highest node of network 314. Network 334 outputs generate and propagate vectors 355, 365, which are concatenated with generate and propagate vectors 315, 325 to provide generate and propagate vectors 375, 385.

In order to provide sum output 205, bits 31:2 of half-add vectors 313, 323 are XORed at 306 to provide vector 316, bits 31:3 of which are then XORed at 307 with bits 31:3 of concatenated generate vector 375 to provide vector 317. Vector 317 is then concatenated with the least significant bit 326 of vector 316, and then concatenated with the least significant bit of half-add-sum vector 313 to provide sum 205.

In order to provide sum-plus-1 output 206, bits 31:2 of half-add vectors 313, 323 are XORed at 306 to provide vector 316, bits 31:3 of which are then XORed at 308 with the result of ORing (309) bits 29:1 of concatenated generate vector 375, with the result of ANDing (310) bits 29:1 of concatenated propagate vector 385 and the least significant bit of half-add-sum vector 313, to provide vector 327. Vector 327 is then concatenated with the XOR 318 of the least significant bit of half-add-sum vector 313 and the least-significant bit 326 of vector 316, and then concatenated with the inverse 328 (where nodes 350 are controllable to selectably bypass, or not bypass, inverter 328) of the least significant bit of half-add-sum vector 313 to provide sum-plus-1 206.

Outputs 205 and 206 can be used for both fixed-point and floating-point calculations and therefore are computed to 31 bits of precision. However, in some embodiments sum-plus-2 output 207 might only be used for floating-point operations. Because the mantissa in IEEE754-1985 floating-point operations is 23 bits wide, in such an embodiment sum-plus-2 output 207 need only be 25 bits wide (although in other embodiments, output 207 might be 31 bits wide like the other sum outputs). In order to provide a 25-bit-wide sum-plus-2 output 207, bits 25:2 of half-add vectors 313, 323 are XORed at 306 to provide vector 316, bits 25:3 of which are then XORed at 308 with the result of ORing (309) bits 23:1 of concatenated generate vector 375 with bits 23:1 of concatenated propagate vector 385 to provide vector 327 (where nodes 360 are controllable to selectably bypass, or not bypass, adder 310). Vector 327 is then concatenated with inverse 338 (where nodes 370 are controllable to selectably bypass, or not bypass, inverter 338) of the XOR 318 of the least significant bit of half-add-sum vector 313 and the least-significant bit 326 of vector 316, and then concatenated with the least significant bit of half-add-sum vector 313 to provide sum-plus-2 207.

As discussed above, the upper range output 208 of middle adder 202 could be provided separately—e.g., for combining with the output of high adder 203. There are at least two ways to provide upper range output 208.

One way to provide upper range output 208 is to compute sum 205 as described above, but to partition it into upper and lower portions by disconnecting output 305 of prefix network 314 from prefix network 334 and zeroing bit 15 of half-add-carry 323. Upper range output 208 may then be read directly from the upper 17 bits 31:15 of sum 205.

A second way to provide upper range output 208 is to XOR (390) upper bits 31:17 only of upper portions 353, 363 (31:15) of vectors 313, 323 to produce 15-bit vector 391, then to XOR (392) vector 391 with generate vector 393 (which is the least significant bits of the 17 bits of generate vector 335) from prefix network 324 to provide 15-bit vector 394. Vector 394 may be concatenated with the XOR (395) of respective bits 16 of upper portions 353, 363, and that result may be concatenated with the lowest bit (bit 15) of upper portion 353 of half-add-sum 313 to provide 17-bit output 208.

As discussed above, low, middle and high adders 201, 202, 203 may be combined to perform a single fixed-point operation on their combined of inputs. Alternatively, each of low, middle and high adders 201, 202, 203 may perform a separate respective fixed-point operation on its respective inputs. Finally, portions of different ones of low, middle and high adders 201, 202, 203 may be used together to perform separate operations that are selectably fixed-point operations or floating-point operations. Therefore, as described, the decomposed adder structure of FIGS. 2 and 3 can be used to provide, in hardware, both fixed-point addition and floating-point addition, which in turn can support fixed-point and floating-point multiplication operations.

A PLD 90 incorporating specialized processing blocks according to the present invention may be used in many kinds of electronic devices. One possible use is in an exemplary data processing system 900 shown in FIG. 4. Data processing system 900 may include one or more of the following components: a processor 901; memory 902; I/O circuitry 903; and peripheral devices 904. These components are coupled together by a system bus 905 and are populated on a circuit board 906 which is contained in an end-user system 907.

System 900 can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD 90 can be used to perform a variety of different logic functions. For example, PLD 90 can be configured as a processor or controller that works in cooperation with processor 901. PLD 90 may also be used as an arbiter for arbitrating access to a shared resources in system 900. In yet another example, PLD 90 can be configured as an interface between processor 901 and one of the other components in system 900. It should be noted that system 900 is only exemplary, and that the true scope and spirit of the invention should be indicated by the following claims.

Various technologies can be used to implement PLDs 90 as described above and incorporating this invention.

It will be understood that the foregoing is only illustrative of the principles of the invention, and that various modifications can be made by those skilled in the art without departing from the scope and spirit of the invention. For example, the various elements of this invention can be provided on a PLD in any desired number and/or arrangement. One skilled in the art will appreciate that the present invention can be practiced by other than the described embodiments, which are presented for purposes of illustration and not of limitation, and the present invention is limited only by the claims that follow.