US 11,436,399 B2Granted

Method and apparatus for performing multiplier regularization

AssigneeIntel Corporation

InventorsMartin Langhammer, Sergey Gribok, Gregg William Baeckler

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for implementing a multiplier on a programmable logic device (PLD) is disclosed. Partial product bits of the multiplier are identified and how the partial product bits are to be summed to generate a final product from a multiplier and multiplicand are determined. Chains of PLD cells and cells in the chains of PLD cells for generating and summing the partial product bits are assigned. It is determined whether a bit in an assigned cell in an assigned chain of PLD cells is under-utilized. In response to determining that a bit is under-utilized, the assigning of the chains of PLD cells and cells for generating and summing the partial product bits are changed to improve an overall utilization of the chains of PLD cells and cells in the chains of PLD cells.

Claims24

Dependent claims

A method for implementing a multiplier on a programmable logic device (PLD), comprising:

identifying partial product bits of the multiplier and how the partial product bits are to be summed to generate a final product from a multiplier value and multiplicand, wherein the partial product bits to be summed are arranged together in a column of a multiplication table;
assigning chains of PLD cells and cells in the chains of PLD cells on the PLD for generating and summing the partial product bits, wherein each cell is assigned to sum together partial product bits in its assigned column;
determining whether a number of inputs for a cell designated for summing a column of partial product bits exceeds input capabilities of the cell;
in response to determining that the number of inputs for the cell exceeds the input capabilities of the cell, configuring a first cell to calculate a first partial product bit for a first column in a chain of PLD cells and a second partial product bit for a subsequent column in the chain of PLD cells;
and
configuring a second cell to compute the sum of a value generated from one or more partial product bits for the subsequent column and the second partial product bit from the first cell.

3 more elements

A method for implementing a multiplier on a programmable logic device (PLD), comprising:

identifying partial product bits of the multiplier and how the partial product bits are to be summed to generate a final product from a multiplier value and multiplicand, wherein the partial product bits to be summed are arranged together in a column of a multiplication table;
assigning chains of PLD cells and cells in the chains of PLD cells on the PLD for generating and summing the partial product bits, wherein each cell is assigned to sum together partial product bits in its assigned column;
determining whether a number of inputs for a cell designated for summing a column of partial product bits exceeds input capabilities of the cell;
in response to determining that the number of inputs for the cell exceeds the input capabilities of the cell, determining whether the column of partial product bits corresponds to a least significant bit of the chains of PLD cells of the multiplier;
and
in response to determining that the column of partial product bits corresponds to the least significant bit of the chains of PLD cells, adding a new bit prior to the least significant bit of the chains of PLD cells and moving one of the partial product bits from the column of partial product bits into a new column of partial product bits that corresponds to the new bit.

3 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/218,179Filed 12 Dec 2018
Published: US 2019/0121927 A125 Apr 2019
Granted: 6 Sep 2022
Term ends: Not estimatedThe source records don’t support an estimate.

Classification8 codes

G06F 30/331
Using simulation: with hardware acceleration, e.g. by using field programmable gate array [FPGA] or emulation
G06F 30/34
Circuit design: for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
H03K 19/17712
Using an AND matrix followed by an OR matrix, i.e. programmable logic arrays: one of the matrices at least being reprogrammable
H03K 19/17728
Structural details of logic blocks: reconfigurable logic blocks, e.g. lookup tables