Implementing multipliers in a programmable integrated circuit device

The number of multipliers of a particular size that are required to perform a multiplication larger than that size is reduced. In the example of a 36-bit-by-36-bit multiplication, the number of 18-bit-by-18-bit multipliers required may be reduced from four to three. This may be achieved by using recursive decomposition techniques. As discussed in more detail below, if for each of two 36-bit numbers, the “digits” of each respective 36-bit number are added together, and then the two sums are multiplied, the resulting term can be combined additively with the product of the least-significant group of bits of the two 36-bit numbers and the product of the most-significant group of bits of the two 36-bit numbers to provide the desired product. A specialized processing block includes structures to facilitate the recursive decomposition technique.

BACKGROUND OF THE INVENTION

This invention relates to multiplication operations in programmable integrated circuit devices such as, e.g., programmable logic devices (PLDs).

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, some PLDs sold by Altera Corporation, of San Jose, Calif., as part of the STRATIX® family, include DSP blocks, each of which may include four 18-bit-by-18-bit multipliers. Each of those DSP blocks also may include adders and registers, as well as programmable connectors (e.g., multiplexers) that allow the various components to be configured in different ways. In each such block, the multipliers can be configured not only as four individual 18-bit-by-18-bit multipliers, but also as four smaller multipliers, or as one larger (36-bit-by-36-bit) multiplier. In addition, one 18-bit-by-18-bit complex multiplication (which decomposes into two 18-bit-by-18-bit multiplication operations for each of the real and imaginary parts) can be performed. Larger multiplications can be performed by using more of the 18-bit-by-18-bit multipliers—e.g., from other DSP blocks.

SUMMARY OF THE INVENTION

The present invention reduces the number of multipliers of a particular size that are required to perform a multiplication larger than that size. In the example of a 36-bit-by-36-bit multiplication, the number of 18-bit-by-18-bit multipliers required may be reduced from four to three. This may be achieved by using recursive decomposition techniques. As discussed in more detail below, if for each of two 36 bit numbers, the “digits” of each respective 36-bit number are added together, and then the two sums are multiplied, the resulting term can be combined additively with the product of the least-significant bits of the two 36-bit numbers and the product of the most-significant bits of the two 36-bit numbers to provide the desired product.

In such an implementation, while fewer multipliers are required, additional adders may be required. In addition, in at least one embodiment, at least one of the multipliers may be required to handle an additional bit in each input; thus, in the 36-bit-by-36-bit example given above, at least one of the multiplications may be a 19-bit-by-19-bit multiplication. A larger multiplier may be provided to handle this multiplication, or an “extension” of an 18-bit-by-18-bit multiplication may be provided by appropriately configuring available programmable logic.

Therefore, in accordance with the present invention, there is provided a method of configuring a programmable integrated circuit device to perform a multiplication operation on a number of multiplicand input values each having a first plurality of bits, where the programmable integrated circuit device incorporates multiplier circuits for multiplicand input values each having a second plurality of bits. The method includes configuring logic of the programmable integrated circuit device to break up each of the multiplicand input values into a plurality of segments, each segment having the second plurality of bits, where a first one of the segments of one of the multiplicand input values is of greater significance than a second one of the segments of that one of the multiplicand input values, with the second one of the segments being of lesser significance. Logic of the programmable integrated circuit device may be configured for adding together, for each of the multiplicand input values, the segments of greater significance and lesser significance, to create a respective sum for each of the multiplicand values. Logic of the programmable integrated circuit device is configured for multiplying together those segments of greater significance using a first one of the multiplier circuits, multiplying together those segments of lesser significance using a second one of the multiplier circuits, and multiplying together the sums using a third one of the multiplier circuits. Logic of the programmable integrated circuit device also may be configured to shift outputs of the first and second ones of the multiplier circuits by respective amounts and to combine outputs of the first, second and third ones of the multiplier circuits according to a recursive decomposition of the multiplication operation.

A programmable logic device so configurable, and so configured, and a machine-readable data storage medium encoded with software for performing the method, are also provided.

DETAILED DESCRIPTION OF THE INVENTION

When a 36-bit-by-36-bit multiplication is implemented in 18-bit-by-18-bit multipliers using a linear decomposition, each of the two 36-bit operands a and b can be expressed as a set of two 18-bit numbers a1:a0and b1:b0, so that their product M can be represented as follows:
M=(2xa1+a0)*(2xb1+b0)
The power-of-2 factors represent left-shifting by a number of places equal to the exponent. Expanding, the 36-bit-by-36-bit multiplication M is:
M=2xa1b1+2x(a1b0+a0b1)+a0b0
There are four unique terms anbm, so four multipliers are required.

In this formulation of the computation, there is a total of five terms, but only three unique terms A and anbn(n=0,1). By comparison, the linear decomposition includes four unique terms anbm(n=0,1; m=0,1), constituting four total terms. Therefore it is possible to trade off a multiplier (specific and expensive) for adders (more general-purpose and inexpensive).

The term A is a product of two terms (a1+a0) and (b1+b0), each of which is the sum of two 18-bit numbers and therefore may be 19-bits wide. Thus, computing A may require provision of a 19-by-19 multiplier, or the 19-by-19 multiplication may be performed by “extending” an 18-by-18 multiplier using programmable logic resources, as described in copending, commonly-assigned U.S. patent application Ser. No. 12/034,146, filed Feb. 20, 2008 and hereby incorporated by reference herein in its entirety.

The invention will now be described with reference toFIGS. 1-7.

FIG. 1is a diagram100of both the logic flow, and a circuit configuration with which a programmable device may be programmed, for multiplying a first number a by second number b. Each number a and b may be a 36-bit number, or a smaller number such as a 32-bit number. Specialized processing blocks101,102may be row-redundant DSP blocks—i.e., DSP blocks designed to fit in the same space in the device floorplan as a unit of programmable logic such as, in devices from Altera Corporation, a “logic array block”—of the type described, e.g., in copending, commonly-assigned U.S. patent application Ser. Nos. 12/249,051, filed Oct. 10, 2008, 12/380,853, filed concurrently herewith, and 12/380,841, filed concurrently herewith, each of which is hereby incorporated by reference herein in its respective entirety.

As described in the aforementioned incorporated applications, each block101,102has conductors that allow it to communicate with each neighboring block101,102to the right or to the left. Each block101,102has two partial multipliers103,104, each of which may include a partial-product generator and a compressor, to provide redundant partial multiplication vectors113,114that may be combined in combinatorial circuitry105, which is described in more detail below.

In accordance with an embodiment of the invention, each specialized processing block101,102may be provided with input adders106,107(shown only in block101) that allow addition of various ones of inputs111,121,131,141prior to multiplication. In this embodiment, inputs111,131and inputs121,141may be added together. In addition, conductor108may be provided between blocks101,102, allowing partial multiplication vector113of block102to be combined with partial multiplication vectors113,114of block101in combinatorial circuitry105of block101. In this way, partial multiplier103of block102may be “borrowed” or “stolen” as a “third multiplier” for block101.

If, as shown inFIG. 1, the most-significant group of bits a1, b1of a and b is input via inputs111,121of block101to partial multiplier103of block101and to input adders106,107of block101, and the least-significant group of bits a0, b0of a and b is input via inputs131,141of block101to partial multiplier103of block101and to input adders106,107of block101, and via inputs111,121of block102to partial multiplier103of block102, then partial multiplier103of block101computes the a1b1term to be used in computing M, and partial multiplier103of block102computes the a0b0term to be used in computing M, while partial multiplier104of block102computes the A term to be used in computing M.

As seen inFIG. 2, the result M is then a1b1shifted left18places, plus (A−a1b1−a0b0), plus a0b0shifted right18places, which generates a 54-bit result out of the block101(the lower 18 bits of a0b0may be truncated insofar as they do not contribute to the required precision).

The 18 bit left shift for a1b1may be performed by shifter201in block101. Additional arithmetic logic202may be added to the specialized processing block described in the above-incorporated applications to perform the −a1b1−a0b0+(a0b0>>18) portion of the calculation. Arithmetic logic202may be implemented with right shifter212and two 4-2 compressors—one 37-bit 4-2 compressor222for −a1b1−a0b0, and one shorter 19-bit 4-2 compressor232to add (a0b0>>18). A multiplexer (not shown) may be added before arithmetic circuitry202, to select between that new arithmetic circuitry or the existing connections from the adjacent block102.

Although these changes have been described in connection with block101, there is likely to be an entire row of blocks101,102, and any one of them may play the role of block101or of block102. Thus, additional arithmetic logic202may be added to each specialized processing block101,102.

The output vectors of partial multiplier104and left-shifter201may be compressed by 57-bit 4-2 compressor203. The carry-save vectors output by 4-2 compressor203and 4-2 compressor232may be further compressed by 57-bit 4-2 compressor204. The carry-save vectors output by 4-2 compressor204may be input to carry-propagate adder205to provide result206(M).

Slight variations of this basic arrangement may be necessary depending on the size of the multiplications to be performed.FIGS. 3 and 4compare the implementations of 36-bit-by-36-bit multiplication and 32-bit-by-32-bit multiplication, respectively. In the 36-bit-by-36-bit case ofFIG. 3, the outputs of adders106,107may be 19 bits wide. Therefore, 18-bit-by-18-bit partial multiplier104may be replaced by 19-bit-by-19-bit partial multiplier304to accommodate this case. In the 32-bit-by-32-bit case ofFIG. 4, the inputs can be limited to 17 bits, so that the adder outputs remain 18 bits wide. However, this may require changing 18-bit left shifter201to 17-bit left shifter401, and changing 18-bit right shifter212to a 17-bit right shifter (not shown) in arithmetic logic402.

An alternative arrangement500to the basic arrangement shown inFIGS. 2-4is shown inFIG. 5. Here, arithmetic logic502includes only shifter212and compressor222, with the output of shifter212, along with the output of compressor204may be further compressed by 4-2 compressor501before the final result is computed in carry-propagate adder205.

Although the discussion heretofore has assumed that the a0b0term would be computed in a specialized processing block102to the right of the block101that carried out the remainder of the calculation, in fact the bidirectional connection between blocks101,102allows the a0b0term to come from the left as well. A multiplexer771(seeFIG. 7) would allow right shifter212to select either an input from the block to the right or an input from the block to the left. The result of this flexibility is illustrated inFIG. 6, where block661borrows one partial multiplier103from block662to its left, while block663borrows the other partial multiplier104from block662to its left. This bidirectional ability minimizes the waste of partial multipliers, assuring that a first partial multiplier need not be left unused simply because its companion partial multiplier in the same block has been borrowed by an adjacent block. Instead, the first partial multiplier also can be borrowed by a different adjacent block.

FIG. 7shows the details of a specialized processing block770, similar to those of the above-incorporated applications, but modified in accordance with the present invention as depicted inFIG. 2. Because block770may be part of a programmable device that may be configured in different ways, it includes connections, multiplexing options, carry-in/carry-out options, and bit-shifting options, that may not be directly relevant to the present invention. However, partial multipliers103,104, input adders106,107, shifter201, arithmetic logic202(including compressors222,232and shifter212), compressors203,204, and carry-propagate adder205also are included, along with compressor775, which may be used to carry out an accumulation function. Also seen inFIG. 7are multiplexers772,773, for selectively bypassing input adders106,107to carry out operations in which input adders106,107are not used.

The discussion heretofore also has assumed that the complete result would be output by one specialized processing block, leading to truncation of the least-significant 18 bits. However, if the full 72 bits are required, the carry-propagate adder in the adjacent block can be used to output the lower 18 bits of the a0b0term. This may require splitting the carry-propagate adder at some point, but that is known for calculating and outputting independent 18-bit-by-18-bit multiplier results.

The method of the invention configures a programmable integrated circuit device, such as a PLD, incorporating a modified specialized processing block as describe above, to create the structures shown inFIGS. 1-6to perform multiplications of a certain size using a smaller number of multipliers than previous methods.

Instructions for carrying out the method according to this invention may be encoded on a machine-readable medium, to be executed by a suitable computer or similar device to implement the method of the invention for programming or configuring programmable integrated circuit devices to perform operations as described above. For example, a personal computer may be equipped with an interface to which a programmable integrated circuit device can be connected, and the personal computer can be used by a user to program the programmable integrated circuit device using a suitable software tool, such as the QUARTUS® II software available from Altera Corporation, of San Jose, Calif.

FIG. 8presents a cross section of a magnetic data storage medium600which can be encoded with a machine executable program that can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium600can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate601, which may be conventional, and a suitable coating602, which may be conventional, on one or both sides, containing magnetic domains (not visible) whose polarity or orientation can be altered magnetically. Except in the case where it is magnetic tape, medium600may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device.

The magnetic domains of coating602of medium600are polarized or oriented so as to encode, in manner which may be conventional, a machine-executable program, for execution by a programming system such as a personal computer or other computer or similar system, having a socket or peripheral attachment into which the PLD to be programmed may be inserted, to configure appropriate portions of the PLD, including its specialized processing blocks, if any, in accordance with the invention.

FIG. 9shows a cross section of an optically-readable data storage medium700which also can be encoded with such a machine-executable program, which can be carried out by systems such as the aforementioned personal computer, or other computer or similar device. Medium700can be a conventional compact disk read only memory (CD-ROM) or digital video disk read only memory (DVD-ROM) or a rewriteable medium such as a CD-R, CD-RW, DVD-R, DVD-RW, DVD+R, DVD+RW, or DVD-RAM or a magneto-optical disk which is optically readable and magneto-optically rewriteable. Medium700preferably has a suitable substrate701, which may be conventional, and a suitable coating702, which may be conventional, usually on one or both sides of substrate701.

In the case of a CD-based or DVD-based medium, as is well known, coating702is reflective and is impressed with a plurality of pits703, arranged on one or more layers, to encode the machine-executable program. The arrangement of pits is read by reflecting laser light off the surface of coating702. A protective coating704, which preferably is substantially transparent, is provided on top of coating702.

In the case of magneto-optical disk, as is well known, coating702has no pits703, but has a plurality of magnetic domains whose polarity or orientation can be changed magnetically when heated above a certain temperature, as by a laser (not shown). The orientation of the domains can be read by measuring the polarization of laser light reflected from coating702. The arrangement of the domains encodes the program as described above.

Thus it is seen that a method for carrying out multiplications in a programmable integrated circuit device using fewer dedicated multiplier circuits, a programmable integrated circuit device programmed using the method, and software for carrying out the programming, have been provided.

A PLD90programmed according to the present invention may be used in many kinds of electronic devices. One possible use is in a data processing system900shown inFIG. 10. Data processing system900may include one or more of the following components: a processor901; memory902; I/O circuitry903; and peripheral devices904. These components are coupled together by a system bus905and are populated on a circuit board906which is contained in an end-user system907.

System900can 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. PLD90can be used to perform a variety of different logic functions. For example, PLD90can be configured as a processor or controller that works in cooperation with processor901. PLD90may also be used as an arbiter for arbitrating access to a shared resources in system900. In yet another example, PLD90can be configured as an interface between processor901and one of the other components in system900. It should be noted that system900is 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 PLDs90as 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 programmable integrated circuit device 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.