Apparatus, method and program for calculating the result of a repeating iterative sum

Patent metadata

Field	Value
Publication number	US-9933999-B2
Application number	US-201514878562-A
Country	US
Kind code	B2
Filing date	Oct 8, 2015
Priority date	Oct 31, 2014
Publication date	Apr 3, 2018
Grant date	Apr 3, 2018

Abstract

An apparatus, method and program are provided for calculating a result value to a required precision of a repeating iterative sum, wherein the repeating iterative sum comprises multiple iterations of an addition using an input value. Addition is performed in a single iteration of addition as a sum operation using overlapping portions of the input value and a shifted version of the input value, wherein the shifted version of the input value has a partial overlap with the input value. At least one result portion is produced by incrementing an input derived from the input value using the output from the sum operation and the result value is constructed using the at least one result portion to give the result value to the required precision. The repeating iterative sum is thereby flattened into a flattened calculation which requires only a single iteration of addition using the input value, thus facilitating the calculation of the result value of the repeating iterative sum.

First claim

The invention claimed is:

1. Apparatus for calculating a result value to a required precision of a repeating iterative sum, wherein the repeating iterative sum comprises multiple iterations of an addition using an input value, wherein the apparatus comprises:
an adder capable of performing a single iteration of addition as a sum operation using overlapping portions of the input value and a shifted version of the input value, wherein the shifted version of the input value has a partial overlap with the input value;
at least one incrementer capable of producing at least one result portion derived from the input value using output from the sum operation performed by the adder; and
a result generator capable of constructing the result value using the at least one result portion to give the result value to the required precision,
wherein:
the adder is capable of performing the sum operation to produce a sum value;
the at least one incrementer comprises:
a first incrementer capable of producing a first result portion, wherein producing the first result portion comprises incrementing a most significant portion of the input value which has the partial overlap with the shifted version of the input value using a carry result of the sum operation; and
a second incrementer capable of producing a second result portion, wherein producing the second result portion comprises incrementing the sum value using the carry result of the sum operation; and

the result generator is capable of constructing the result value as the first result portion followed by at least one second result portion to give the result value to the required precision.

2. The apparatus as claimed in claim 1 , wherein a first iteration of the addition comprises addition of the input value to the shifted version of the input value, and wherein each further iteration of the addition comprises addition of a previous iteration addition result to a further shifted version of the input value, wherein the further shifted version of the input value has the partial overlap with the previous iteration addition result.

3. The apparatus as claimed in claim 1 ,
wherein an intermediate portion of the input value has no overlap with the shifted version of the input value,
wherein the first incrementer is capable of producing the first result portion as the most significant portion of the input value which has the partial overlap incremented by an increment value, wherein the increment value is given by the carry result of the sum operation ANDed with a propagate value, wherein the propagate value indicates whether the intermediate portion will carry-propagate in the addition,
the second incrementer is capable of producing the second result portion as the sum value incremented by the increment value,
and the result generator is capable of constructing the result value in which both the first result portion and the second result portion are suffixed by the third result portion.

4. The apparatus as claimed in claim 3 , wherein the apparatus further comprises:
a third incrementer capable of producing a third result portion, wherein producing the third result portion comprises incrementing the intermediate portion by the carry result of the sum operation.

5. The apparatus as claimed in claim 1 , further comprising:
a floating point converter capable of converting the result value into a floating point format value.

6. The apparatus as claimed in claim 1 , wherein the input value comprises an integer portion and a fraction portion.

7. The apparatus as claimed in claim 6 , further comprising:
a floating point converter capable of converting the result value into a floating point format value;
wherein the floating point converter comprises:
a first bit position generator capable of receiving the integer portion of the input value and outputting a most significant bit position as a first bit position output value;
a second bit position generator capable of outputting a most significant bit position of the integer portion of the input value incremented by one as a second bit position output value; and
a third bit position generator capable of generating a position of a most significant bit in the fraction portion of the input value as a third bit position output value,
wherein the floating point converter is capable of generating an exponent portion of the floating point format value using the first bit position output value when the integer portion is non-zero and the carry result is zero, using the second bit position output value when the integer portion is non-zero and the carry result is non-zero, and using the third bit position output value when the integer portion is zero.

8. The apparatus as claimed in claim 7 , wherein the second bit position generator is capable of determining whether the integer portion of the input value comprises a one immediately followed by a zero, and if it does providing the first bit position output value as the second bit position output value, and if it doesn't incrementing the first bit position output value by one to generate the second bit position output value.

9. The apparatus as claimed in claim 8 wherein an intermediate portion of the input value has no overlap with the shifted version of the input value, and wherein:
the adder is capable of performing the sum operation to produce a sum value;
the at least one incrementer comprises:
a first incrementer capable of producing a first result portion, wherein producing the first result portion comprises suffixing a most significant portion of the input value which has the partial overlap with the intermediate portion of the input value to give an first result portion input value, and incrementing the first result portion input value with a carry result of the sum operation; and
a second incrementer capable of producing a second result portion, wherein producing the second result portion comprises incrementing the sum value using the carry result of the sum operation; and

the result generator is capable of constructing the result value as the first result portion followed by at least one second result portion to give the result value to the required precision, wherein the at least second one result portion is suffixed by a least significant portion of the first result value having a same size as the intermediate portion of the input value;
wherein, when the most significant portion of the fraction portion is zero, the third bit position generator is capable of generating the position of the most significant bit in the fraction portion of the input value as the third bit position output value using a replacement fraction portion, the replacement fraction portion comprising:
the intermediate significance portion of the fraction portion suffixed by the least significant portion of the fraction portion.

10. The apparatus as claimed in claim 7 , wherein the first bit position generator, the second bit position generator, and the third bit position generator are capable of parallel operation.

11. The apparatus as claimed in claim 7 , wherein the partial overlap comprises a double self-overlap of the input value in the repeating iterative sum, the double self-overlap comprising addition of a least significant portion of the input value, an intermediate significance portion of the input value and a most significant portion of the input value in a first iteration of the repeating iterative sum, and the apparatus is capable of performing a pre-flattening operation of removing the double self-overlap for the input value in the repeating iterative sum comprising determining a replacement input value for the input value;
wherein, when the most significant porti

Assignees

• Advanced Risc Mach Ltd

Inventors

• Engh-Halstvedt Andreas Due
• Fielding Edvard

Classifications

• G06F7/535

  Dividing only · CPC title

• H03M7/24

  Conversion to or from floating-point codes · CPC title

• G06F7/506 Primary

  with simultaneous carry generation for, or propagation over, two or more stages · CPC title

• G06F7/5272

  with row wise addition of partial products · CPC title

• G06F7/5336 Primary

  overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm · CPC title