Method and a circuit using an associative calculator for calculating a sequence of non-associative operations
AssigneeCalifornia Institute of Technology
InventorsAndre M. DeHon, Nachiket Kapre
Life of this patent
Estimating the term…
Abstract
An apparatus and method that use an associative calculator for calculating a sequence of non-associative operations on a set of input data, comprising: using the associative calculator to calculate from the set of input data an evaluated value of each operation of said sequence as if the non-associative operations were associative operations; detecting if some of the evaluated values are erroneous; if there are erroneous evaluated values, correcting the erroneous evaluated values; and if there are no erroneous evaluated value, outputting as the result of the sequence of non-associative operations the evaluated value of the last operation of the sequence.
Claims6
A circuit for calculating a sequence of non-associative operations, comprising:
- an associative calculator for calculating from a set of input data an evaluated value of each operation of said sequence as if the non-associative operations were associative operations;
- a detector for detecting if some of the evaluated values are erroneous;
- and
- a corrector for correcting the erroneous evaluated values, if there are erroneous values, wherein the associative calculator is provided for:
- breaking down each operation in a number of intermediate operations;
- calculating in parallel the results of said intermediate operations;
- and
- using the results of the intermediate operations to calculate the evaluated value of each operation comprising the intermediate operations,
- wherein the operations of the sequence of operations and the intermediate operations are floating point summations,
- wherein the calculator comprises a plurality of adders for calculating in parallel the results of said intermediate operations, and
- wherein the detector is provided for detecting if some of the evaluated values are erroneous by calculating, for the evaluated value of each summation of the sequence, an error value equal to the difference between:
- said evaluated value;
- and
- a sum of
- the evaluated value of the previous summation of the sequence;
- and
- the input data not common to the calculation of said evaluated value and the evaluated value of the previous summation of the sequence.
A circuit for calculating a sequence of non-associative operations, comprising:
- an associative calculator for calculating from a set of input data an evaluated value of each operation of said sequence as if the non-associative operations were associative operations;
- a detector for detecting if some of the evaluated values are erroneous;
- and
- a corrector for correcting the erroneous evaluated values, if there are erroneous values, wherein the associative calculator is provided for:
- breaking down each operation in a number of intermediate operations;
- calculating in parallel the results of said intermediate operations;
- and
- using the results of the intermediate operations to calculate the evaluated value of each operation comprising the intermediate operations,
- wherein the operations of the sequence of operations and the intermediate operations are floating point summations,
- wherein the calculator comprises a plurality of adders for calculating in parallel the results of said intermediate operations, and
- wherein the plurality of adders are controlled according to a hybrid parallel-prefix design which completes in fewer cycles than Brent-Kung or Sklansky when scheduled on a fixed number of processing elements.
Dependencies are inferred from the claim text.