Constant modulo via recirculant reduction
AssigneeIntel Corporation
InventorsTheo Drane, Christopher Louis Poole, William Zorn, Emiliano Morini
Life of this patent
Estimating the term…
Abstract
Described herein is a generalized optimal reduction scheme for reducing an array modulo a constant. The constant modulo operation calculates a result for array of bits xi, width n modulo an odd positive integer constant d, (e.g., x[n:0] mod d). Circuitry to perform such operation can be configured to compress the array of bits xi, width n into an array of bits yi width m. The techniques described herein enable the design of optimal circuitry via iterative exploration of all potential reduction strategies that are available given the input constraints.
Claims20
An apparatus comprising:
- a memory device;
- and
- circuitry coupled with the memory device, the circuitry configured to compute a modulus of an n-bit value with respect to an odd positive integer constant via addition of a plurality of m-bit values to generate an m-bit sum, m is less than n, and the circuitry is configured to:
- sum the plurality of m-bit values via a binary array adder having m one-bit columns;
- and
- compute the modulus of the m-bit sum with respect to the odd positive integer constant.
A method comprising:
- determining an input bit width and an odd positive integer d for circuitry to compute x[n:0] mod d;
- generating a set of possible reduction strategies to assemble a compressor array to compute x[n:0] mod d;
- determining delay, area, and power metrics for each reduction strategy;
- selecting a reduction strategy based on the delay, area, and power metrics;
- generating a circuit description for a selected reduction strategy;
- and
- adding the circuit description to a target design.
A non-transitory machine-readable medium having instructions stored thereon, the instructions, when executed by one or more processors, cause the one or more processors to perform operations comprising:
- determining an input bit width and an odd positive integer d for circuitry to compute x[n:0] mod d;
- generating a set of possible reduction strategies to assemble a compressor array to compute x[n:0] mod d;
- determining delay, area, and power metrics for each reduction strategy;
- selecting a reduction strategy based on the delay, area, and power metrics;
- generating a circuit description for a selected reduction strategy;
- and
- adding the circuit description to a target design.
Dependencies are inferred from the claim text.