Abstract:
Circuitry for performing arithmetic operations on a plurality of inputs efficiently performs both fixed-point operations and floating-point operations. Each of at least first and second respective operator circuits operates on a respective subplurality of the plurality of inputs. Other circuitry selectively interconnects the 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 the multiple different results are selectably usable to perform both fixed-point operations and floating-point operations.

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 10  and 1.  9   10 . Therefore, the resultant product can be between 1.0 10  and 3.  9   10 , and may be subject to normalization and rounding. To accommodate normalization and rounding, it may be necessary to add either zero, 1 or 2 10  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 10 , the right-shift is 0 bits; if the result is greater than or equal to 2.0 10  and less than 4.0 10  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 10  or greater than 0.5 10 ) 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 10  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.