Implementing multipliers in a programmable integrated circuit device

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.

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.

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 is a diagram of the logic flow, and a circuit configuration with which a programmable device may be programmed, for performing multiplication in accordance with an embodiment of the invention;

FIG. 2 is a more detailed representation of the logic flow, and a circuit configuration with which a programmable device may be programmed, for performing multiplication in accordance with an embodiment of the invention;

FIG. 3 is a representation of the logic flow, and a circuit configuration with which a programmable device may be programmed, for performing multiplication in accordance with a first variant of the embodiment of FIG. 2 ;

FIG. 4 is a representation of the logic flow, and a circuit configuration with which a programmable device may be programmed, for performing multiplication in accordance with a second variant of the embodiment of FIG. 2 ;

FIG. 5 is a representation of the logic flow, and a circuit configuration with which a programmable device may be programmed, for performing multiplication in accordance with an alternative to the embodiment of FIG. 2 ;

FIG. 6 is a schematic representation of the implementation of an embodiment of the invention in a device having a particular arrangement of specialized processing blocks;

FIG. 7 is a schematic representation of the interior of one embodiment of a specialized processing block in which the invention may be implemented;

FIG. 8 is a cross-sectional view of a magnetic data storage medium encoded with a set of machine-executable instructions for performing the method according to the present invention;

FIG. 9 is a cross-sectional view of an optically readable data storage medium encoded with a set of machine executable instructions for performing the method according to the present invention; and

FIG. 10 is a simplified block diagram of an illustrative system employing a programmable logic device incorporating the present 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 a 1 :a 0 and b 1 :b 0 , so that their product M can be represented as follows:

M =(2 x a 1 +a 0 )*(2 x b 1 +b 0 )

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= 2 x a 1 b 1 +2 x ( a 1 b 0 +a 0 b 1 )+ a 0 b 0

There are four unique terms a n b m , so four multipliers are required.

Instead, however, in a recursive decomposition, such as the “Karatsuba multiplication” described, e.g., in Weisstein, E. W., “Karatsuba Multiplication,” MathWorld—A Wolfram Web Resource , http://mathworld.wolfram.com/KaratsubaMultiplication.html, the 18-bit components a n , b m can be combined as follows:

A =( a 1 +a 0 )*( b 1 +b 0 )= a 1 b 1 +a 1 b 0 +a 0 b 1 +a 0 b 0

Substituting A into the linear decomposition:

M= 2 2x a 1 b 1 +2 x ( A−a 1 b 1 +a 0 b 0 )+ a 0 b 0

In this formulation of the computation, there is a total of five terms, but only three unique terms A and a n b n (n=0,1). By comparison, the linear decomposition includes four unique terms a n b m (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 (a 1 +a 0 ) and (b 1 +b 0 ), 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 to FIGS. 1-7 .

FIG. 1 is a diagram 100 of 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 blocks 101 , 102 may 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 block 101 , 102 has conductors that allow it to communicate with each neighboring block 101 , 102 to the right or to the left. Each block 101 , 102 has two partial multipliers 103 , 104 , each of which may include a partial-product generator and a compressor, to provide redundant partial multiplication vectors 113 , 114 that may be combined in combinatorial circuitry 105 , which is described in more detail below.

In accordance with an embodiment of the invention, each specialized processing block 101 , 102 may be provided with input adders 106 , 107 (shown only in block 101 ) that allow addition of various ones of inputs 111 , 121 , 131 , 141 prior to multiplication. In this embodiment, inputs 111 , 131 and inputs 121 , 141 may be added together. In addition, conductor 108 may be provided between blocks 101 , 102 , allowing partial multiplication vector 113 of block 102 to be combined with partial multiplication vectors 113 , 114 of block 101 in combinatorial circuitry 105 of block 101 . In this way, partial multiplier 103 of block 102 may be “borrowed” or “stolen” as a “third multiplier” for block 101 .

If, as shown in FIG. 1 , the most-significant group of bits a 1 , b 1 of a and b is input via inputs 111 , 121 of block 101 to partial multiplier 103 of block 101 and to input adders 106 , 107 of block 101 , and the least-significant group of bits a 0 , b 0 of a and b is input via inputs 131 , 141 of block 101 to partial multiplier 103 of block 101 and to input adders 106 , 107 of block 101 , and via inputs 111 , 121 of block 102 to partial multiplier 103 of block 102 , then partial multiplier 103 of block 101 computes the a 1 b 1 term to be used in computing M, and partial multiplier 103 of block 102 computes the a 0 b 0 term to be used in computing M, while partial multiplier 104 of block 102 computes the A term to be used in computing M.

As seen in FIG. 2 , the result M is then a 1 b 1 shifted left 18 places, plus (A−a 1 b 1 −a 0 b 0 ), plus a 0 b 0 shifted right 18 places, which generates a 54-bit result out of the block 101 (the lower 18 bits of a 0 b 0 may be truncated insofar as they do not contribute to the required precision).

The 18 bit left shift for a 1 b 1 may be performed by shifter 201 in block 101 . Additional arithmetic logic 202 may be added to the specialized processing block described in the above-incorporated applications to perform the −a 1 b 1 −a 0 b 0 +(a 0 b 0 >>18) portion of the calculation. Arithmetic logic 202 may be implemented with right shifter 212 and two 4-2 compressors—one 37-bit 4-2 compressor 222 for −a 1 b 1 −a 0 b 0 , and one shorter 19-bit 4-2 compressor 232 to add (a 0 b 0 >>18). A multiplexer (not shown) may be added before arithmetic circuitry 202 , to select between that new arithmetic circuitry or the existing connections from the adjacent block 102 .

Although these changes have been described in connection with block 101 , there is likely to be an entire row of blocks 101 , 102 , and any one of them may play the role of block 101 or of block 102 . Thus, additional arithmetic logic 202 may be added to each specialized processing block 101 , 102 .

The output vectors of partial multiplier 104 and left-shifter 201 may be compressed by 57-bit 4-2 compressor 203 . The carry-save vectors output by 4-2 compressor 203 and 4-2 compressor 232 may be further compressed by 57-bit 4-2 compressor 204 . The carry-save vectors output by 4-2 compressor 204 may be input to carry-propagate adder 205 to provide result 206 (M).

Slight variations of this basic arrangement may be necessary depending on the size of the multiplications to be performed. FIGS. 3 and 4 compare 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 of FIG. 3 , the outputs of adders 106 , 107 may be 19 bits wide. Therefore, 18-bit-by-18-bit partial multiplier 104 may be replaced by 19-bit-by-19-bit partial multiplier 304 to accommodate this case. In the 32-bit-by-32-bit case of FIG. 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 shifter 201 to 17-bit left shifter 401 , and changing 18-bit right shifter 212 to a 17-bit right shifter (not shown) in arithmetic logic 402 .

An alternative arrangement 500 to the basic arrangement shown in FIGS. 2-4 is shown in FIG. 5 . Here, arithmetic logic 502 includes only shifter 212 and compressor 222 , with the output of shifter 212 , along with the output of compressor 204 may be further compressed by 4-2 compressor 501 before the final result is computed in carry-propagate adder 205 .

Although the discussion heretofore has assumed that the a 0 b 0 term would be computed in a specialized processing block 102 to the right of the block 101 that carried out the remainder of the calculation, in fact the bidirectional connection between blocks 101 , 102 allows the a 0 b 0 term to come from the left as well. A multiplexer 771 (see FIG. 7 ) would allow right shifter 212 to 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 in FIG. 6 , where block 661 borrows one partial multiplier 103 from block 662 to its left, while block 663 borrows the other partial multiplier 104 from block 662 to 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. 7 shows the details of a specialized processing block 770 , similar to those of the above-incorporated applications, but modified in accordance with the present invention as depicted in FIG. 2 . Because block 770 may 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 multipliers 103 , 104 , input adders 106 , 107 , shifter 201 , arithmetic logic 202 (including compressors 222 , 232 and shifter 212 ), compressors 203 , 204 , and carry-propagate adder 205 also are included, along with compressor 775 , which may be used to carry out an accumulation function. Also seen in FIG. 7 are multiplexers 772 , 773 , for selectively bypassing input adders 106 , 107 to carry out operations in which input adders 106 , 107 are 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 a 0 b 0 term. 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 in FIGS. 1-6 to 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. 8 presents a cross section of a magnetic data storage medium 600 which 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. Medium 600 can be a floppy diskette or hard disk, or magnetic tape, having a suitable substrate 601 , which may be conventional, and a suitable coating 602 , 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, medium 600 may also have an opening (not shown) for receiving the spindle of a disk drive or other data storage device.

The magnetic domains of coating 602 of medium 600 are 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. 9 shows a cross section of an optically-readable data storage medium 700 which 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. Medium 700 can 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. Medium 700 preferably has a suitable substrate 701 , which may be conventional, and a suitable coating 702 , which may be conventional, usually on one or both sides of substrate 701 .

In the case of a CD-based or DVD-based medium, as is well known, coating 702 is reflective and is impressed with a plurality of pits 703 , 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 coating 702 . A protective coating 704 , which preferably is substantially transparent, is provided on top of coating 702 .

In the case of magneto-optical disk, as is well known, coating 702 has no pits 703 , 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 coating 702 . 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 PLD 90 programmed according to the present invention may be used in many kinds of electronic devices. One possible use is in a data processing system 900 shown in FIG. 10 . 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 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.