Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2000-03-02
2001-11-27
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S040000, C326S039000, C326S038000
Reexamination Certificate
active
06323680
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to programmable logic devices that are configured to accommodate multiplication. More particularly, this invention relates to programmable logic devices including logic elements having features that facilitate the performance of multiplication operations with minimal adverse impact on the performance of other operations of the logic elements.
Programmable logic devices (“PLDs”) typically include (
1
) many regions of programmable logic, and (
2
) programmable interconnection resources for selectively conveying signals to, from, and/or between those logic regions. Each logic region is programmable to perform any of several different, relatively simple logic functions. The interconnection resources are programmable to allow the logic regions to work together to perform much more complex logic functions than can be performed by any individual logic region. Examples of known PLDs are shown in U.S. Pat. Nos. 3,473,160, Re. 34,363, 5,689,195 and 5,909,126, and U.S. patent application Ser. No. 09/266,235, all of which are hereby incorporated by reference herein in their entireties.
One of the functions that can be implemented in a PLD is the multiplication of one number by another. Typically, each the multiplicands in such an operation would have multiple bits. As is well known, the first step of such a multiplication can be performed by multiplying each bit of the first multiplicand by the least significant bit of the second multiplicand to form a first partial product. Next, the first multiplicand is shifted left one digit (in a binary number, that has the effect of multiplication by two) and multiplying each bit by the second least significant bit of the second multiplicand to form a second partial product. The same procedure is performed for the remaining bits of the second multiplicand (with appropriate additional shifting of the first multiplicand) to form additional partial products. All of the partial products are added together to form a sum, representing the desired product.
A multiplication operation such as that just described can be implemented in known PLDs, using the logic regions to perform the individual multiplications and summations, and using the interconnect network to route the intermediate results of those individual operations between the appropriate logic regions until the final result has been achieved. However, the need to route each intermediate result onto the general interconnect network results in a significant speed penalty in the determination of the final product. Moreover, the logic regions typically are optimized to perform the more common logic operations, rather than arithmetic operations. Therefore, the multiplication operation is slowed down within the logic regions as well. In addition, in some known devices in which provision for multiplication has been made, AND gates have been provided on the front end of each logic region to facilitate the formation of partial products and sums thereof, but all signals have to pass through those AND gates for all operations, slowing down non-multiplication operations.
It would be desirable to be able to provide a programmable logic device optimized to perform multiplication operations.
It would also be desirable to provide such a programmable logic device with little or no speed penalty in the performance of logic operations.
SUMMARY OF THE INVENTION
It is an object of this invention to provide a programmable logic device optimized to perform multiplication operations.
It is also an object of this invention to provide such a programmable logic device with little or no speed penalty in the performance of logic operations.
In accordance with the present invention, there is provided a programmable logic device having a plurality of regions of programmable logic. Each of the regions has a plurality of input terminals and at least one output terminal. Each of the regions is programmable to selectively perform any of a plurality of logic functions on input signals applied to the input terminals to produce an output signal applied to the output terminal. An interconnection network is programmable to selectively connect the output terminal of substantially any of the regions to at least one of the input terminals of substantially any of the regions. Each region in at least a subset of the plurality of regions of programmable logic has additional logic dedicated to the performance of functions forming at least part of a multiplication operation. Dedicated conductors for the output of at least a portion of the multiplication operation are also provided.
In a preferred embodiment, the invention is implemented in a programmable logic device of the type described in copending, commonly-assigned U.S. patent application Ser. No. 09/516,921, filed concurrently herewith, which is hereby incorporated by reference herein in its entirety, as well as in above-incorporated U.S. Pat. No. 5,689,195 and Applications Nos. 60/122,788, and 60/142,513. In such a programmable logic device, logic is arranged in regions, which are then arranged in groups or blocks spanning, preferably, ten rows of logic regions. The interconnection network includes local conductors, global conductors, and conductors of intermediate lengths.
In the preferred embodiment, each logic region preferably has four inputs and the additional logic in each logic region is a multiplexer into which one bit or digit of a multiplicand, and one bit or digit of that multiplicand shifted left one digit (i.e., multiplied by two), are input as data, and two bits of the other multiplicand are input as control signals. These inputs may be stolen from the same four inputs that otherwise would be used as inputs to the logic region. Alternatively, the inputs for the bits of the first multiplicand and the first multiplicand multiplied by two could be stolen from the ordinary inputs to the logic region as just described, while the bits of the other multiplicand could be input on conductors normally used for signals to multiple logic regions in the group (e.g., clock or clear signals, etc.).
The arrangement just described produces, in a single logic region, one bit or digit of the sum of two partial products. In traditional multiplier arrangements, that result would require at least three logic regions—at least one to form a first partial product, at least one to form a second partial product, and at least one to add the two partial products together. Performing all of these functions in one logic region reduces the number of logic regions required, reduces the use of the interconnection network, and also speeds up this portion of the computation.
Assuming two 16-bit-wide multiplicands, a column of at least sixteen logic regions is required to form two bits of the partial products if two bits of one multiplicand serve as the multiplexer control inputs. Thus, eight such columns of logic regions will form all bits of the partial products. Each column of logic regions will also produce a sum of the two partial products it produces. However, all of those sums of partial products must be further added together to complete the multiplication operation. This can be done in a conventional adder tree, using additional logic regions. But implementation of a conventional adder tree would involve heavy use of the interconnection network. Therefore, in accordance with the invention, each logic region preferably has a dedicated output for its bit of the sum of partial products, for conducting that portion of the sum to a neighboring or nearby logic region. When the programmable logic device is programmed to perform multiplication, the logic preferably is laid out on the device (e.g., by the programming software) so that the logic regions used to form the sums of partial products alternate with other logic regions used in the adder tree, and the dedicated sum output of each logic region is used to conduct the sum of partial products from that logic region to a neighboring logic region that is part of the adder tree (in one embodiment, the dedica
Brown Stephen
Chan Vinson
Huang Wei-Jen
Ngai Tony
Park James
Altera Corporation
Fish & Neave
Ingerman Jeffrey H.
Tan Vibol
Tokar Michael
LandOfFree
Programmable logic device configured to accommodate... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programmable logic device configured to accommodate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable logic device configured to accommodate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583268