Fast carry-calculation oriented redundancy-tolerated fixed-point number coding for massive parallel ALU circuitry design in GPU, TPU, NPU, AI infer chip, CPU, and other computing devices
AssigneeJun Zhou
InventorsJun Zhou, Xiaoyun Liu
Life of this patent
Estimating the term…
Abstract
A code method, a computer program product, and a system, for implementing a code method of Redundancy-Tolerated symmetric binary Coding (RTC) for massive parallel ALU circuitry design in GPU (Graphics Processing Unit), TPU (Tensor Processing Unit), NPU (Neural Processing Unit), Artificial Intelligence Inference Chip, CPU, and other computing chips and devices. The method can remove redundancy and reduce the dependency on carry bit computing. RTC code method can provide a redundancy-tolerated digital coding method for negative and positive integers, and can guarantee that number “0” have one and only one representation.
Claims19
A method for encoding numerical data for parallel computation comprising arithmetic operations that eliminate sequential carry propagation, the method comprising:
- A. transforming a first binary-encoded numerical value into a first plurality of digits representing said value in a non-binary, redundant numerical format, wherein each digit in the first plurality of digits is selected from a redundant digit set comprising at least three integer values, including at least one negative integer value and at least two positive integer values;
- B. transforming a second binary-encoded numerical value into a second plurality of digits representing said value in a non-binary, redundant numerical format, wherein each digit in the second plurality of digits is selected from the redundant digit set;
- C. generating an intermediate sum by performing digit-wise addition of the first plurality of digits to the second plurality of digits without propagating carry values between digit positions;
- D. independently and simultaneously determining a local carry-out value for every digit position in the intermediate sum, wherein the determination for each respective digit position is made without dependency on the determination of the carry-out value for any less significant digit position, and is based on applying a predetermined rule set to only the value of the intermediate sum at the respective digit position, wherein the predetermined rule set comprises:
- i. generating a carry-out value of +1 if the value of the intermediate sum at the digit position is greater than or equal to a maximum value of the redundant digit set;
- ii. generating a carry-out value of −1 if the value of the intermediate sum at the digit position is less than or equal to a minimum value of the redundant digit set;
- and
- iii. generating a carry-out value of 0 otherwise;
- and
- E. producing a final sum by applying the local carry-out value from each digit position to an adjacent higher digit position.
A computing system for performing high-speed parallel arithmetic, the system comprising:
- a memory storing instructions and data;
- at least one processor operatively coupled to the memory, the at least one processor comprising:
- A. an encoder circuit configured to transform a standard binary number into a sequence of digits encoded in a redundant format defined by a digit set comprising at least one negative integer, zero, and at least two positive integers;
- B. a parallel arithmetic logic unit (ALU) circuit operatively coupled to the encoder circuit, the parallel ALU circuit comprising a plurality of identical logic cells, each corresponding to a single digit position and configured to:
- i. receive a digit from the sequence of digits,
- ii. generating an intermediate sum digit for its position;
- and
- iii. independently determine a local carry-out value by applying a static rule set to the intermediate sum digit;
- and
- C. a carry resolution network configured to propagate the local carry-out values to adjacent digit positions.
An apparatus for redundant-tolerated arithmetic computation comprising:
- A. means for encoding a first fixed-point number into a first sequence of digits representable by a digit set comprising {−1, 0, 1, 2};
- B. means for generating an intermediate sum by adding the first sequence of digits to a second sequence of digits representing a second fixed-point number;
- C. means for determining a set of carry-out values, in parallel and without sequential carry propagation, by evaluating each digit of the intermediate sum against a rule set, wherein the rule set generates a carry-out of +1 for a digit value >=2, a carry-out of −1 for a digit value <=−1, and a carry-out of 0 for a digit value of 0 or 1;
- and
- D. means for resolving the intermediate sum into a final non-redundant representation based on the set of carry-out values.
A computer program product for designing an arithmetic logic unit (ALU), the computer program product comprising a non-transitory computer-readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
- A. generating a register-transfer level (RTL) description of an arithmetic circuit, the arithmetic circuit comprising:
- 1. a digit-wise addition module configured to output an intermediate sum of two operands encoded in a redundant digit set;
- 2. a plurality of carry generation cells, each cell corresponding to a digit position of the intermediate sum and configured to output a local carry-out value based on applying a predetermined rule set to the value of the intermediate sum at its corresponding digit position, wherein the plurality of carry generation cells are configured to operate in parallel, and wherein the predetermined rule set comprises:
- i. generating a carry-out value of +1 if the value of the intermediate sum at the digit position is greater than or equal to a maximum value of the redundant digit set;
- ii. generating a carry-out value of −1 if the value of the intermediate sum at the digit position is less than or equal to a minimum value of the redundant digit set;
- and
- iii. generating a carry-out value of 0 otherwise;
- and
- 3. a carry application module configured to generate a final sum by applying the local carry-out value from each cell to an adjacent higher digit position;
- and
- B. outputting the RTL description for use in fabricating an integrated circuit.
Dependencies are inferred from the claim text.