Specialized processing block for programmable integrated circuit device

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 a programmable 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 as by Finite Impulse Response (FIR) filtering). Such blocks are also frequently referred to as multiply-accumulate (“MAC”) blocks, because they include structures to perform multiplication operations, and sums and/or accumulations of multiplication results.

For example, PLDs sold by Altera Corporation, of San Jose, Calif., as part of the STRATIX®, ARRIA®, CYCLONE® and HARDCOPY® families include DSP blocks, each of which includes one or more multipliers. Each of those DSP blocks also includes one or more 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. In addition, those DSP blocks can be configured for operation at different precisions.

Such blocks typically have included direct connections that allow certain operations to be performed using only a chain or cascade including multiple ones of such blocks, while other operations cannot be completed without routing outputs from one of such blocks through the general purpose logic and interconnect of the programmable device before entering a subsequent one of such blocks.

SUMMARY OF THE INVENTION

In accordance with embodiments of the present invention, a specialized processing block such as the DSP blocks described above may be enhanced by including direct connections that allow the block output to be directly connected to either the multiplier inputs or the adder inputs of another such block.

Therefore, in accordance with embodiments of the present invention there is provided a specialized processing block on a programmable integrated circuit device. The specialized processing block includes a multiplier having two multiplicand inputs and a product output, an adder having as one adder input the product output of the multiplier, and having a second adder input and an adder output, a direct-connect output of the adder output to a first other one of the specialized processing block, and a direct-connect input from a second other one of the specialized processing block. The direct-connect input connects a direct-connect output of that second other one of the specialized processing block to a first one of the multiplicand inputs.

A programmable integrated circuit device may includes a plurality of such specialized processing blocks.

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 conceptual representation of a polynomial calculation performed by adder and multiplier circuitry;

FIG. 2 shows a logical abstraction of a known specialized processing block used in programmable integrated circuit devices;

FIG. 3 shows the use of specialized processing blocks such as that shown in FIG. 2 to perform a polynomial calculation in a programmable integrated circuit device;

FIG. 4 shows logical abstractions of specialized processing blocks according to an embodiment of this invention for use in programmable integrated circuit devices;

FIG. 5 shows the use of specialized processing blocks such as that shown in FIG. 4 to perform a polynomial calculation in a programmable integrated circuit device;

FIG. 6 shows the addition of pipeline registers to specialized processing blocks according to embodiments of this invention;

FIG. 7 shows the addition of additional pipeline registers to specialized processing blocks according to embodiments of this invention;

FIG. 8 shows the addition of additional pipeline registers to specialized processing blocks according to embodiments of this invention;

FIG. 9 shows logical abstractions of specialized processing blocks according to another embodiment of this invention for use in programmable integrated circuit devices;

FIG. 10 shows the use of specialized processing blocks such as that shown in FIG. 9 to perform a polynomial calculation in a programmable integrated circuit device; and

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

DETAILED DESCRIPTION OF THE INVENTION

Specialized processing blocks of the type disclosed herein are particularly well-suited for polynomial operations, which may be used in advanced filtering applications, curve fitting, unary functions, Digital Pre-Distortion (DPD), Sampling Rate Conversion (SRC), and other applications.

Any polynomial in one variable may be generalized using the following formula:

y ⁡ ( n ) = ∑ k = 0 K ⁢ c k ·  x n  k Eq . ⁢ ( 1 )
The value of K (the highest power to which the variable x is raised in any term of the polynomial) is referred to as the “order” of the polynomial.

Taking as an example a third-order polynomial (K=3), and using a, b, c, d for c₀ to c₃, Eq. (1) can be rewritten as:
y=d·x³+c·x²+b·x+a=((d·x+c)·x+b)·x+a  Eq. (2)
where the second line is a transformation according to Horner's Rule, whereby each subsequent term can be derived by a simple multiplication of the previous result by the scalar input variable (plus addition of a constant). This is illustrated in FIG. 1 where x and d are multiplied at multiplier 101 to create dx to which c is added at adder 102. The resultant sum dx+c is multiplied again by x at multiplier 103 and b is added to that result at adder 104. That sum is multiplied again by x at multiplier 105 and a is added at adder 106, to yield y as set forth above. This can be extended to a polynomial of any order.

FIG. 2 shows a logical abstraction 200 of known DSP blocks, such as those described above. Each block 200 includes at least one real or complex multiplier 201 (represented in this drawing by a single multiplier) whose output is directed to at least one adder 207 (represented in this drawing by a single adder). Input registers and output registers, represented in this abstraction by input register bank 203 and output register bank 204, also may be provided, respectively receiving signals from, and directing signals to, programmable interconnect resources 213, which route signals among programmable logic resources 214. Many known DSP blocks also include input signal direct connection (or input chain connection) 205, which may, e.g., allow a plurality of blocks to be used to construct various filter structures such as, e.g., Finite Impulse Response (FIR) filters. Similarly, many known DSP blocks also include output signal direct connection (or output chain connection) 206 to the adder(s) of a subsequent block.

Existing direct connections 205/206 are insufficient to allow polynomial calculations using chains of DSP blocks without resorting to logic and routing resources outside the blocks. As noted above in the Horner's Rule representation of a polynomial calculation, each stage requires the multiplication of the previous result by the scalar variable. However, as noted above in connection with FIG. 2, existing DSP output chain connections are input to the adder of the subsequent DSP block, but not to the multiplier. Therefore, polynomial calculations cannot be performed without using logic and routing resources outside block 200, as shown in FIG. 3.

As seen in FIG. 3, a first DSP block 301 of the type shown in FIG. 2 may be used to multiply a previous result 302 (such as dx+c) by the variable x input at 303, using multiplier 304 to yield (dx+c)x. Because there is no direct connection to the adder 207 of block 301 other than from multiplier 304 or the previous chaining connection 206, in order to add the constant b to (dx+c)x and then multiply that result by x, the result (dx+c)x must be output from block 301 and added to b using an external adder 305 in the general-purpose logic 214 of the programmable device in which blocks 301/302 are contained. That sum can then be routed using general-purpose routing resources 213 of the programmable device, to input (dx+c)x+b at 312 to block 311. The scalar variable x is input at 313, and multiplier 314 is used to yield ((dx+c)x+b)x, which may be output from block 311 and added to the constant a using an external adder 315 in the general-purpose logic 213. Additional blocks may be used in this way depending on the number of terms in the polynomial.

FIG. 4 shows logical diagrams of two occurrences 401/411 an exemplary DSP block according to an embodiment of the invention. In this logical representation, implementational details, such as additional registers and some programmable routing features—such as additional multiplexers that may allow the output of a particular structure to be routed directly out of block 401/411—are omitted to simplify discussion. In addition, some elements that are shown may, in an actual embodiment, be implemented more than once. For example, each of multipliers 404/414 may actually represent two or more multipliers, as in the DSP blocks of the aforementioned STRATIX® and ARRIA® families of PLDs.

In the logical representation of FIG. 4, output chain connection 206 of each block connects, rather than directly to an input of adder 407/417, both to multiplexer 405/415 which allows either connection 206 or input 402/412 (via connection 408/418) to be input to adder 407/417, and to multiplexer 406/416, which allows either connection 206 or input 402/412 (via connection 409/419) to be input to multiplier 404/414. The ability to connect output chain connection 206 to multiplier 404/414 does not exist in known DSP blocks.

FIG. 5 shows how blocks 401/411 may be used for a polynomial calculation. In this example, dx+c has been calculated in a previous block (not shown). That result is chained from the previous block via its output chain connection 206, using multiplexer 406 to connect connection 206 to multiplier 404, to which x also is input via input 403. At the same time, b is input to input 402 and multiplexer 405 routes input 402 to adder 407. The other input to adder 407 is the output of multiplier 404, which is (dx+c)x, so that adder 407 outputs (dx+c)x+b.

That result is input via output chain connection 206 of block 401 to block 411, where multiplexer 416 connects connection 206 to multiplier 414, to which x is the other input, propagated via input chain 205. At the same time, a is input to input 412 and multiplexer 415 connects input 412 to adder 417. The other input to adder 417 is the output of multiplier 414, which is ((dx+c)x+b)x, so that adder 407 outputs ((dx+c)x+b)x+a=dx³+cx²+bx+a=y. Output y may be further chained on chain output connection 206 of block 411, or directly on output 420 of block 411.

Depending on the size of the polynomial, the number of blocks required may result in unacceptable bit-width growth, which could substantially slow the system. Therefore, additional registers 601 may be provided on the block outputs, including the direct connect outputs to allow for pipelining and implementation of systolic form filters, as seen in FIG. 6. Multiple pipeline registers between stages also can be used, as shown in FIG. 7 where two registers 601 are used between each stage. Moreover, as shown in FIG. 8, some of the pipeline registers 601 can be moved to interior portions of the blocks if that is beneficial in a particular logic implementation.

It may be possible to run specialized processing blocks of the type disclosed at speeds higher than the remainder of the device of which the blocks are a part (e.g., twice the device speed). However, in the examples above the variable x has been input through the regular programmable interconnect of the device, and input of x has therefore would be limited by the clock speed of the device. Accordingly, in the embodiment shown in FIG. 9, a multiplexer 901 is added to allow input chain 905 to propagate not only an input from input register bank 903 of the current block or a previous block, but also a value propagated from elsewhere in a previous block. In such an embodiment, the clock speed of the remainder of the device is not a limiting factor when using multiple blocks together at a higher internal clock speed, allowing an increase in throughput, as compared to the throughput of the scalar input variable x, proportional to the higher speed. In such a case, an initial block, upstream of the first block to perform a calculation, may be “wasted” to allow data aggregation—i.e., to enter the value to be propagated so that it can be propagated to the first block, to perform the calculation at the higher clock speed within the blocks.

Configuring circuitry to perform certain mathematical operations may involve groupings of specialized processing blocks. For example, if the multipliers in the specialized processing blocks are capable of multiplying two 18-bit inputs, two blocks can be used together to multiply an 18-bit input by a 36-bit input, with the upper bits of the 36-bit input x being multiplied by the 18-bit multiplicand in one block, and the lower bits of the 36-bit input x being multiplied by the 18-bit multiplicand in a second block. This arrangement, which is shown conceptually in FIG. 10, can be facilitated by adding a further connection 911 (shown in phantom in FIG. 9) that allows the output of a previous block to be propagated via the input chain to a subsequent block. In addition, pipeline registers 906 may be provided in any or all of the locations within the block shown in FIG. 9.

The foregoing embodiments can be implemented with 18-bit-by-18-bit multipliers, 27-bit-by-27-bit multipliers (this is comparable to the 18-bit-by-36-bit case discussed above) and 36-bit-by-36-bit multipliers. This allows the performance of multiplication at different precisions. In addition, mixed precision also is possible, as long as the most-significant bits are aligned (e.g., by scaling the values to a 1.x format, where x=17 for 8-bit multipliers and x=26 for 27-bit multipliers. For example, in implementing a polynomial calculation, it may be desirable to provide greater precision in the higher-order terms, especially in the last few stages.

The precision at the output of a multiplier is the sum of the precisions at the input. If multipliers of the same precision are to be used in a chain, rounding may be carried out between the multiplier output of a stage and the multiplier input of the next stage. Known rounding methods may be used, such as those shown in commonly-assigned U.S. Pat. No. 7,948,267, which is hereby incorporated by reference herein in its entirety.

Even with rounding, and even if both multiplicands are defined to be between −1 and +1, unacceptable bit growth could occur. One way to minimize unacceptable bit growth is to normalize all constants by dividing by the sum of the maximum absolute value of all of the constants.

Thus it is seen that specialized processing blocks that allow implementation of polynomial calculations, as well as other operations, have been provided.

A PLD 140 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 1400 shown in FIG. 11. Data processing system 1400 may include one or more of the following components: a processor 1401; memory 1102; I/O circuitry 1403; and peripheral devices 1404. These components are coupled together by a system bus 1405 and are populated on a circuit board 1406 which is contained in an end-user system 1107.

System 1400 can be used in a wide variety of applications, such as computer networking, data networking, instrumentation, video processing, digital signal processing, Remote Radio Head (RRH), or any other application where the advantage of using programmable or reprogrammable logic is desirable. PLD 140 can be used to perform a variety of different logic functions. For example, PLD 140 can be configured as a processor or controller that works in cooperation with processor 1401. PLD 140 may also be used as an arbiter for arbitrating access to a shared resources in system 1400. In yet another example, PLD 140 can be configured as an interface between processor 1401 and one of the other components in system 1400. It should be noted that system 1400 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 140 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.