Reconfigurable multiplier array

Details Reconfigurable multiplier array Reconfigurable multiplier array

2000-10-10

2002-04-09

Tokar, Michael (Department: 2819)

Electronic digital logic circuitry

Multifunctional or programmable

Array

C326S039000, C708S505000, C708S670000

Reexamination Certificate

active

06369610

ABSTRACT:

RELATED APPLICATIONS
This application is a National Stage application under 35 U.S.C. §371 of International Application No. PCT/GB/03902, which both designated and elected the United States, and claims priority to Great Britain Patent Application No. 9727414.6, filed Dec. 29, 1997.
FIELD OF THE INVENTION
This invention relates to logic circuits, such as so-called field programmable gate arrays (FPGAs) or so-called complex programmable logic devices (CLDs) and to functional logic blocks within such circuits.
BACKGROUND OF THE INVENTION
FPGAs are integrated circuits containing a very large number of logic gates organised as an array, with the interconnections between the logic gates and the function of the gates themselves being controllable or configurable via externally programmed control circuitry. In this way, an FPGA can be adapted, after fabrication, to perform a number of different tasks simply by changing the settings provided by the externally programmed control circuitry.
FPGAs are particularly useful because of their relatively low cost and short design times in comparison with bespoke integrated circuits.
It has been suggested that FPGAs are well suited for use as reconfigurable hardware to accelerate software in many applications [see publication reference 1 below]. Image or video processing tasks are particularly well suited to hardware acceleration, because of the inherent parallelism and data flow structure. Common to many image and video processing tasks is the need for intensive arithmetic operations such as multiplication and addition.
Whilst existing FPGA architectures are well suited to binary addition [2], configuring FPGAs for binary multiplication results in the available reconfigurable resources being used inefficiently [3]. Typically over 70% of the FPGA could be required solely for multiplication in some applications. The literature also suggests that hardware implemented on an FPGA requires as much as 100 times more die area, and will be about 10 times slower than the bespoke hardware equivalent [4].
Hwang has suggested constructing Universal Multiplication Networks using small (4 bit) programmable Additive Multiply (PAM) modules [5]. Whilst simple in design, these networks have the drawback of slow multiplication times and a non-scalable connection pattern, especially for large operand sizes.
Most other multiplier architectures are concerned with the multiplication of two multiplicands of fixed length. The techniques used for speeding us the multiplication are largely at the expense of regularity, such as Wallace Trees [6], or require some form of “pre-processing” of the operands, e.g. Booth's Modified algorithm [7]. Neither of these styles of design is well suited to generalisation for multiplicands of variable size, thus making it difficult to create a reconfigurable multiplier based on these methods.
So, there is a need for a field programmable or configurable logic circuit or circuit element (e.g. as a part of a larger FPGA) which can be used efficiently to carry out multiplication operations.
SUMMARY OF THE INVENTION
This invention provides a logic block comprising:
an m×n array of partial calculating circuits (where m≧2 and n≧2) operable to generate partial product components of an m-bit multiplicand x n-bit multiplicand binary multiplication and to generate a cumulative sum of the partial products for each bit of one of the multiplicands; and
a configurable output circuit operable, under the control of a configuration signal, either:
(a) to sum the cumulative sums of partial products generated by the partial calculating circuits so as to generate a product value; or
(b) to pass data representing the cumulative sums of the partial product components to partial calculating circuits within one or more further logic blocks.
Embodiments of the invention can provide FPGAs combined with reconfigurable multipliers. A design is presented for a reconfigurable multiplier array, constructed using an array of 4 bit flexible array blocks (FABs) which has speed comparable to that of a conventional signed array multiplier, with minimal extra cost in hardware required for reconfiguration. The multiplier can be configured to perform both unsigned, and signed two's complement multiplication.
The logic block can be used to generate simply an m-bit by n-bit product, or in alternative preferred embodiments plural logic blocks can be linked together to form a composite multiplier capable of handling larger multiplicands.
Because the logic blocks are relatively self-contained and so require very little configuration data, there can be a dramatic reduction in the administrative overhead usually needed to configure a gate array to perform large multiplications.
Other respective aspects and features of the invention are defined in the appended claims.


REFERENCES:
patent: 5448186 (1995-09-01), Kawata
patent: 5570039 (1996-10-01), Oswald et al.
patent: 5777915 (1998-07-01), Witte et al.
patent: 5787031 (1998-07-01), Ichikawa et al.
patent: 5805477 (1998-09-01), Perner
patent: 5909385 (1999-06-01), Nishiyama et al.
patent: 5914892 (1999-06-01), Wang et al.
patent: 6130553 (2000-10-01), Nakaya
patent: 6140839 (2000-10-01), Kaviani et al.
patent: 6154049 (2000-11-01), New
patent: 668 659 (1995-08-01), None
“Configurable Multiplier Blocks for embedding in FPGAs” by Haynes, et al.,Electronic Letters34, Apr. 2, 1998, No. 7, Stevenage, Harts GB.

Affiliated with

Also associated with

Rating

Reconfigurable multiplier array does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Reconfigurable multiplier array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconfigurable multiplier array will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2919930