Efficient FPGA multipliers

1. A circuit comprising:

a 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 four of the twelve block inputs are provided as outputs of the building block without being provided as inputs to either of the two six-input LUTs.

2. The circuit of claim 1 , wherein:

three of the four block inputs that are provided to each of the two six-input LUTs are Booth-encoded bits from a multiplicand.

3. The circuit of claim 1 , wherein:

the building block is a first building block;

the first building block further comprises:

an adder that receives a carry input and generates a carry output;

the circuit further comprises one or more additional building blocks, each additional building block having the same structure as the first building block; and

the carry input of each additional building block is coupled to the carry output of another additional building block or the carry output of the first building block.

4. The circuit of claim 3 , wherein three Booth-encoded bits from a multiplicand are received as inputs to the first building block and each additional building block of the one or more additional building blocks.

5. The circuit of claim 3 , 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; 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 from the second building block to generate the one-bit carry output and one bit of the eight-bit product output.

6. The circuit of claim 5 , 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.

7. The circuit of claim 1 , wherein the building block is configured to support multiplication of unsigned numbers.

8. The circuit of claim 1 , wherein the building block is configured to support multiplication of sign-magnitude numbers.

9. 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 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 four of the twelve block inputs are provided as outputs of the building block without being provided as inputs to either of the two six-input LUTs.

10. The machine-readable storage medium of claim 9 , wherein:

three of the four block inputs that are provided to each of the two six-input LUTs are Booth-encoded bits from a multiplicand.

11. The machine-readable storage medium of claim 9 , wherein:

the building block is a first building block;

the first building block further comprises:

an adder that receives a carry input and generates a carry output;

the circuit further comprises one or more additional building blocks, each additional building block having the same structure as the first building block; and

the carry input of each additional building block is coupled to the carry output of another additional building block or the carry output of the first building block.

12. The machine-readable storage medium of claim 11 , wherein three Booth-encoded bits from a multiplicand are received as inputs to the first building block and each additional building block of the one or more additional building blocks.

13. The machine-readable storage medium of claim 11 , 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; 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 from the second building block to generate the one-bit carry output and one bit of the eight-bit product output.

14. The machine-readable storage medium of claim 13 , wherein:

the eight-bit Booth multiplier building block is a first eight-bit Booth multiplier building block;

the circuit further comprises a second eight-hit 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-hit 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 f an eight-hit multiplier with an eight-bit multiplicand.

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 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 four of the twelve block inputs are provided as outputs of the building block without being provided as inputs to either of the two six-input LUTs.

16. The system of claim 15 , wherein:

three of the four block inputs that are provided to each of the two six-input LUTs are Booth-encoded bits from a multiplicand.

17. The system of claim 15 , wherein:

the building block is a first building block;

the first building block further comprises:

an adder that receives a carry input and generates a carry output;

the circuit further comprises one or more additional building blocks, each additional building block having the same structure as the first building block; and

the carry input of each additional building block is coupled to the carry output of another additional building block or the carry output of the first building block.

18. The system of claim 17 , wherein three Booth-encoded bits from a multiplicand are received as inputs to the first building block and each additional building block of the one or more additional building blocks.

19. The system of claim 17 , 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; 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 from the second building block to generate the one-bit carry output and one bit of the eight-bit product output.

20. The system of claim 19 , wherein:

the eight-bit Booth multiplier building block is a first eight-hit 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-hit 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.