Efficient FPGA multipliers

Patent metadata

Field	Value
Publication number	US-10963221-B2
Application number	US-202016802966-A
Country	US
Kind code	B2
Filing date	Feb 27, 2020
Priority date	Jul 13, 2018
Publication date	Mar 30, 2021
Grant date	Mar 30, 2021

Abstract

In some example embodiments a logical block comprising twelve inputs and two six-input lookup tables (LUTs) is provided, wherein four of the twelve inputs are provided as inputs to both of the six-input lookup tables. This configuration supports efficient field programmable gate array (FPGA) implementation of multipliers. Each six-input LUT comprises two five-input lookup tables (LUT5s) that are used to form Booth encoding multiplier building blocks. The five inputs to each LUT5 are two bits from a multiplier and three Booth-encoded bits from a multiplicand. By assembling building blocks, multipliers of arbitrary size may be formed.

First claim

What is claimed is:

1. A circuit comprising:
a first building block comprising:
twelve block inputs;
two six-input lookup tables (LUTs), wherein four of the block inputs are provided to each of the two six-input LUTs and three of the four block inputs that are provided to each of the two six-input LUTs are Booth-encoded bits from a multiplicand; and
an adder that receives a carry input and generates a carry output; and

one or more additional building blocks, each additional building block having the same structure as the first building block, the carry input of each additional building block being coupled to the carry output of another additional building block or the carry output of the first building block, each additional building block receiving the three Booth-encoded bits from the multiplicand as input.

2. The circuit of claim 1 , wherein four of the twelve block inputs are provided as outputs of the first building block without being provided as inputs to either of the two six-input LUTs.

3. The circuit of claim 1 , wherein:
the one or more additional building blocks are two additional building blocks comprising a second building block and a third building block; and
the first building block, the second building block, and the third building block are configured to form an eight-bit Booth multiplier building block that generates an eight-bit product output and a one-bit carry output.

4. The circuit of claim 3 , wherein the third building block:
comprises a five-input LUT that generates a one-bit output; and
uses the one-bit output and the carry output generated by the adder of the second building block to generate the one-bit carry output and one bit of the eight-bit product output of the eight-bit Booth multiplier building block.

5. The circuit of claim 3 , wherein:
the eight-bit Booth multiplier building block is a first eight-bit Booth multiplier building block;
the circuit further comprises a second eight-bit Booth multiplier building block, a third eight-bit Booth multiplier building block, and a fourth eight-bit Booth multiplier building block;
the second eight-bit Booth multiplier building block receives input comprising:
six bits of the eight-bit product output from the first eight-bit Booth multiplier building block; and
the one-bit carry output from the first eight-bit Booth multiplier building block;

the third eight-bit Booth multiplier building block receives input comprising:
six bits of the eight-bit product output from the second eight-bit Booth multiplier building block; and
the one-bit carry output from the second eight-bit Booth multiplier building block;

the fourth eight-bit Booth multiplier building block receives input comprising:
six bits of the eight-bit product output from the third eight-bit Booth multiplier building block; and
the one-bit carry output from the third eight-bit Booth multiplier building block; and

the circuit generates a multiplication result of an eight-bit multiplier with an eight-bit multiplicand.

6. The circuit of claim 1 , wherein:
each of the two six-input LUTs comprises two five-input LUTs and provides two outputs, one from each of the two five-input LUTs.

7. The circuit of claim 6 , wherein:
the adder receives the outputs from the four five-input LUTs as input.

8. A machine-readable storage medium containing instructions that when executed by a machine, cause the machine to program a field programmable gate array (FPGA) to generate a circuit comprising:
a first building block comprising:
twelve block inputs;
two six-input lookup tables (LUTs), wherein four of the block inputs are provided to each of the two six-input LUTs and three of the four block inputs that are provided to each of the two six-input LUTs are Booth-encoded bits from a multiplicand; and
an adder that receives a carry input and generates a carry output; and

one or more additional building blocks, each additional building block having the same structure as the first building block, the carry input of each additional building block being coupled to the carry output of another additional building block or the carry output of the first building block, each additional building block receiving the three Booth-encoded bits from the multiplicand as input.

9. The machine-readable storage medium of claim 8 , wherein four of the twelve block inputs are provided as outputs of the first building block without being provided as inputs to either of the two six-input LUTs.

10. The machine-readable storage medium of claim 8 , wherein:
the one or more additional building blocks are two additional building blocks comprising a second building block and a third building block; and
the first building block, the second building block, and the third building block are configured to form an eight-bit Booth multiplier building block that generates an eight-bit product output and a one-bit carry output.

11. The machine-readable storage medium of claim 10 , wherein the third building block:
comprises a five-input LUT that generates a one-bit output; and
uses the one-bit output and the carry output generated by the adder of the second building block to generate the one-bit carry output and one bit of the eight-bit product output of the eight-bit Booth multiplier building block.

12. The machine-readable storage medium of claim 10 , wherein:
the eight-bit Booth multiplier building block is a first eight-bit Booth multiplier building block;
the circuit further comprises a second eight-bit Booth multiplier building block, a third eight-bit Booth multiplier building block, and a fourth eight-bit Booth multiplier building block;
the second eight-bit Booth multiplier building block receives input comprising:
six bits of the eight-bit product output from the first eight-bit Booth multiplier building block; and
the one-bit carry output from the first eight-bit Booth multiplier building block;

the third eight-bit Booth multiplier building block receives input comprising:
six bits of the eight-bit product output from the second eight-bit Booth multiplier building block; and
the one-bit carry output from the second eight-bit Booth multiplier building block;

the fourth eight-bit Booth multiplier building block receives input comprising:
six bits of the eight-bit product output from the third eight-bit Booth multiplier building block; and
the one-bit carry output from the third eight-bit Booth multiplier building block; and

the circuit generates a multiplication result of an eight-bit multiplier with an eight-bit multiplicand.

13. The machine-readable storage medium of claim 8 , wherein:
each of the two six-input LUTs comprises two five-input LUTs and provides two outputs, one from each of the two five-input LUTs.

14. The machine-readable storage medium of claim 13 , wherein:
the adder receives the outputs from the four five-input LUTs as input.

15. A system comprising:
a memory that stores instructions; and
one or more processors configured by the instructions to perform operations comprising:
programming a field programmable gate array (FPGA) to generate a circuit comprising:
a first building block comprising:
twelve block inputs; and
two six-input lookup tables (LUTs), wherein four of the block inputs are provided to each of the two six-input LUTs and three of the four block inputs that are provided to each of the two six-input LUTs are Booth-encoded bits from a multiplicand; and
an adder that receives a carry input and generates a carry output; and

one or more additional building blocks, each additional building block having the same structu

Assignees

• Achronix Semiconductor Corp

Inventors

• Pugh Daniel
• Nijssen Raymond

Classifications

• G06F7/5057

  using table look-up; using programmable logic arrays (G06F7/509 takes precedence) · CPC title

• G06F7/533 Primary

  Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even · CPC title

• H03K19/17728 Primary

  Reconfigurable logic blocks, e.g. lookup tables · CPC title