# US 8,280,939 B2 · Methods and apparatus for automatic accuracy-sustaining scaling of block-floating-point operands

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,939 B2
- Document ID: US8280939B2
- Status: Granted
- Kind: B2
- Application number: 12/125,536
- Filed: 2008-05-22
- Published: 2009-11-26
- Granted: 2012-10-02
- Earliest claimed: 2008-05-22
- Assignees: VideoIQ, Inc.
- Inventors: Igor Reyzin; Aleksey Lipchin
- Web page: https://patentgrep.com/patent/US8280939B2

## CPC

- G06F 7/483: Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers {(G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence)}
- G06F 2207/3824: Accepting both fixed-point and floating-point numbers
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A computer-implemented method performs an operation on a set of at least one BFP operands to generate a BFP result. The method is designed to reduce the risks of overflow and loss of accuracy attributable to the operation. The method performs an analysis to determine respective shift values for each of the operands and the result. The method calculates result mantissas by shifting the stored bit patterns representing the corresponding operand mantissa values by their respective associated shift values determined in the analysis step, performing the operation on shifted operand mantissas to generate preliminary result mantissa, and shifting the preliminary result mantissas by a number of bits determined in the analysis step.

## Claims

### Claim 1

A computer-implemented method of performing an operation on a set of at least one operand objects to generate a result object, the method designed to reduce the risks of overflow and loss of accuracy attributable to the operation, the method being implemented on a computer comprising a memory and an arithmetic unit, the method comprising:
representing and storing in the memory each of the operand objects in a BFP form having an array of mantissa values as well as a common exponent for all mantissa values in the array for a given object, wherein each mantissa value and common exponent is stored in the memory as a bit pattern; and
generating the result object in a BFP format having an array of mantissa values and a common exponent for all mantissa values associated with the result object, wherein each mantissa value and common exponent is stored in the memory as a bit pattern, wherein the generating step comprises:
performing an analysis step to determine respective shift values for each of the operand objects and a shift value for the result object; and
calculating a result mantissa value for each corresponding set of mantissa values associated with the operand objects by: shifting the stored bit patterns representing the corresponding mantissa values in the operand objects by numbers of bits equal to their respective associated shift values determined in the analysis step, performing the operation on corresponding mantissa values in the array portions of the operand objects using the arithmetic unit to generate respective preliminary mantissa values for the result object, shifting a bit pattern representing the preliminary mantissa values for the result object by a number of bits equal to the shift value for the result object as determined in the analysis step, and storing the shifted preliminary mantissa values in the array portion of the result object in the memory.

### Claim 2 (depends on 1)

A method according to claim 1, wherein the set of at least one operand objects consists of one scalar operand object.

### Claim 3 (depends on 1)

A method according to claim 1, wherein the set of at least one operand objects consists of two operand objects.

### Claim 4 (depends on 1)

A method according to claim 1, wherein the set of at least one operand objects comprise more than two operand objects.

### Claim 5 (depends on 1)

A method according to claim 1, wherein one or more of the arrays are scalar values.

### Claim 6 (depends on 1)

A method according to claim 1, wherein one or more of the arrays are one-dimensional and have a plurality of elements.

### Claim 7 (depends on 1)

A method according to claim 1, wherein one or more of the arrays are two-dimensional and have a plurality of elements.

### Claim 8 (depends on 7)

A method according to claim 7, wherein the one or more two-dimensional arrays contain image data.

### Claim 9 (depends on 1)

A method according to claim 1, wherein the operation comprises addition.

### Claim 10 (depends on 9)

A method according to claim 9, wherein determining respective shift values for each of the operand objects comprises finding a common value for all of the common exponents associated with all of the operand objects.

### Claim 11 (depends on 10)

A method according to claim 10, wherein the common value for all of the exponents associated with the operand objects is chosen to avoid overflow while minimizing right shifting of the mantissa bit patterns so as to sustain accuracy.

### Claim 12 (depends on 1)

A method according to claim 1, wherein the operation comprises multiplication.

### Claim 13 (depends on 12)

A method according to claim 12, wherein the number of operand objects is two and the operand objects are denoted A and B, wherein A has a larger mantissa than B, and determining respective shift values for each of the operand objects comprises:
shifting the mantissa of A right, if necessary, by a number of bits so that the size of the mantissa of A equals the size of the mantissa of B; and
shifting the mantissas of both A and B, if necessary, right by approximately the same number of bits, wherein the same number of bits is approximately one-half of the size available for the mantissa of the result.

### Claim 14 (depends on 1)

A method according to claim 1, wherein the operation comprises one or more of the set of operations consisting of assignment, subtraction, division, matrix multiplication, vector multiplication, convolution, and correlation.

### Claim 15 (depends on 1)

A method according to claim 1, wherein the step of calculating a result mantissa value for each corresponding set of mantissa values associated with the operand objects comprises iterating through a loop a number of iterations equal to the number of elements in the result array.

### Claim 16 (depends on 1)

A method according to claim 1, wherein the step of calculating a result mantissa value for each corresponding set of mantissa values associated with the operand objects is performed utilizing an accumulator.

### Claim 17 (depends on 1)

A method according to claim 1, wherein the operation is a compound operation comprising two simple operations in an order, and the analysis step further comprises:
first determining respective shift values for each of the operand objects and a shift value for the result object for the first of the two operations; and
determining respective shift values for each of the operand objects and a shift value for the result object for the second of the two operations, wherein one or more outputs from the first determining step are utilized as inputs.

### Claim 18 (depends on 1)

A method according to claim 1, wherein the analysis step is based at least in part on extreme values of the operand objects.

### Claim 19 (depends on 18)

A method according to claim 18, wherein the extreme values comprise maximum values.

### Claim 20 (depends on 18)

A method according to claim 18, wherein the extreme values comprise minimum values.

### Claim 21 (depends on 18)

A method according to claim 18, wherein the extreme values comprise actual values.

### Claim 22 (depends on 18)

A method according to claim 18, wherein the extreme values comprise theoretically possible extreme values.

### Claim 23 (depends on 18)

A method according to claim 18, wherein the extreme values comprise estimates.

### Claim 24 (depends on 1)

A method according to claim 1, wherein the method is performed by a compiler.

### Claim 25 (depends on 1)

A method according to claim 1, wherein the computer comprises a digital signal processor.

### Claim 26

A computer-readable medium on which is embedded program code for implementing method of performing an operation on a set of at least one operand objects to generate a result object, the method designed to reduce the risks of overflow and loss of accuracy attributable to the operation, the method being implemented on a computer comprising a memory and an arithmetic unit, the method comprising:
representing and storing in the memory each of the operand objects in a BFP form having an array of mantissa values as well as a common exponent for all mantissa values in the array for a given object, wherein each mantissa value and common exponent is stored in the memory as a bit pattern; and
generating the result object in a BFP format having an array of mantissa values and a common exponent for all mantissa values associated with the result object, wherein each mantissa value and common exponent is stored in the memory as a bit pattern, wherein the generating step comprises:
performing an analysis step to determine respective shift values for each of the operand objects and a shift value for the result object; and
calculating a result mantissa value for each corresponding set of mantissa values associated with the operand objects by: shifting the stored bit patterns representing the corresponding mantissa values in the operand objects by numbers of bits equal to their respective associated shift values determined in the analysis step, performing the operation on corresponding mantissa values in the array portions of the operand objects using the fixed-point arithmetic unit to generate respective preliminary mantissa values for the result object, shifting a bit pattern representing the preliminary mantissa values for the result object by a number of bits equal to the shift value for the result object as determined in the analysis step, and storing the shifted preliminary mantissa values in the array portion of the result object in the memory.

### Claim 27

An apparatus for performing an operation on a set of at least one operand objects to generate a result object, the apparatus designed to reduce the risks of overflow and loss of accuracy attributable to the operation, the apparatus works in conjunction with a computer comprising a memory and an arithmetic unit, the apparatus comprising:
a means for representing and storing in the memory each of the operand objects in a BFP form having an array of mantissa values as well as a common exponent for all mantissa values in the array for a given object, wherein each mantissa value and common exponent is stored in the memory as a bit pattern; and
a means for generating the result object in a BFP format having an array of mantissa values and a common exponent for all mantissa values associated with the result object, wherein each mantissa value and common exponent is stored in the memory as a bit pattern, wherein the generating means comprises:
a means for performing an analysis step to determine respective shift values for each of the operand objects and a shift value for the result object; and
a means for calculating a result mantissa value for each corresponding set of mantissa values associated with the operand objects by: shifting the stored bit patterns representing the corresponding mantissa values in the operand objects by numbers of bits equal to their respective associated shift values determined in the analysis step, performing the operation on corresponding mantissa values in the array portions of the operand objects using the fixed-point arithmetic unit to generate respective preliminary mantissa values for the result object, shifting a bit pattern representing the preliminary mantissa values for the result object by a number of bits equal to the shift value for the result object as determined in the analysis step, and storing the shifted preliminary mantissa values in the array portion of the result object in the memory.

### Claim 28

A computer-implemented method for scaling a plurality of BFP-formatted operands to perform a mathematical operation on the operands to generate a BFP-formatted result, wherein each BFP-formatted operand comprises an array of operand mantissa values and a common operand exponent for all mantissa values in an operand array for an individual operand, and wherein the BFP-formatted result comprises an array of result mantissa values and a common result exponent for all mantissa values in the array for the result, the method implemented on a computer on which program instructions are executed and comprising:
analyzing, by executing instructions of a program operating on computer processing circuitry, each of the plurality of the operands to determine scaling factors for each of the operands, wherein the scaling factors are chosen on the basis of extreme mantissa values of the operands and a permissible range of result mantissa values, and wherein a criterion for determining the scaling factors is sustaining accuracy of the result subject to the constraint that overflow of the result be avoided;
on the basis of the scaling factors, shifting bit patterns representing the mantissas right to avoid overflow and left to sustain accuracy and incrementing or decrementing the corresponding exponent when the mantissas are shifted left or right, respectively; and
using the computer processing circuitry to compute each element of the array of result mantissa values on the basis of corresponding shifted operand mantissa element values, from which a result mantissa element value is derived.

### Claim 29 (depends on 28)

A method according to claim 28, wherein the operation comprises addition.

### Claim 30 (depends on 29)

A method according to claim 29, wherein determining respective shift values for each of the operand objects comprises finding a common value for all of the common exponents associated with all of the operand objects.

### Claim 31 (depends on 30)

A method according to claim 30, wherein the common exponents associated with all of the operand objects is chosen to avoid overflow while minimizing right shifting of the mantissa bit patterns so as to sustain accuracy.

### Claim 32 (depends on 28)

A method according to claim 28, wherein the operation comprises multiplication.

### Claim 33 (depends on 32)

A method according to claim 32, wherein the number of operand objects is two and the operand objects are denoted A and B, wherein A has a larger mantissa than B, and determining respective shift values for each of the operand objects comprises:
shift the mantissa of A right by a number of bits so that the size of the mantissa of A equals the size of the mantissa of B; and
if necessary, shift the mantissas of both A and B right by the same number of bits, wherein the same number of bits is one-half of the size available for the mantissa of the result.

### Claim 34 (depends on 28)

A method according to claim 28, wherein the operation is a compound operation comprising two simple operations in an order, and the analysis step further comprises:
first determining respective shift values for each of the operand objects and a shift value for the result object for the first of the two operations; and
determining respective shift values for each of the operand objects and a shift value for the result object for the second of the two operations, wherein one or more outputs from the first determining step are utilized as inputs.

### Claim 35 (depends on 28)

A method according to claim 28, wherein the analysis step is based at least in part on extreme values of the operand objects.

### Claim 36

A computer system for implementing a floating-point array operation using an arithmetic unit while reducing the risks of overflow and loss of accuracy attributable to the operation, the system comprising:
program code that calls for an operation performed on at least one floating-point array operands to yield a floating-point array result;
memory in which is stored each of the at least one floating-point array operands in respective BFP formats as well as the result operand in a BFP format, each BFP-formatted data structure having an array of mantissas as well as a common exponent for all mantissas in its corresponding array of mantissas, wherein each mantissa and common exponent is stored in the memory as a bit pattern;
a scaling routine called by the program code to analyze the operands to determine scaling factors for each of the operands, wherein the scaling factors are chosen on the basis of extreme mantissa values of the operands and a permissible range of result mantissa values, and wherein a criterion for determining the scaling factors is maximizing accuracy of the result subject to the constraint that overflow of the result be avoided, the scaling routine returning mantissa shift values for each of the operands and the result, wherein the both left and right shift values are permissible;
an arithmetic unit programmed to compute an element of the result mantissa array using the corresponding elements of the operand mantissa arrays as inputs;
wherein the program code shifts the elements of the operand mantissa arrays in accordance with shift values returned by the scaling routine, and wherein the program code comprises a loop through all elements of the result mantissa array to cause the arithmetic unit to compute the elements of the result mantissa array using corresponding shifted elements of the operand mantissa arrays as inputs, and wherein the program code shifts elements of the result mantissa array in accordance with a result shift value returned by the scaling routine.

### Claim 37 (depends on 36)

The computer system of claim 36, wherein the program code increments or decrements the common exponents of the operands and result by amounts based on the shift values returned by the scaling routine.

### Claim 38 (depends on 36)

The computer system of claim 36, wherein the arithmetic unit is a fixed point arithmetic unit.

### Claim 39 (depends on 36)

The computer system of claim 36, wherein the operation comprises at least one of addition and multiplication, and wherein the shift values are based at least in part on extreme values of the operands.

### Claim 40 (depends on 36)

The computer system of claim 36, wherein the operation is a compound operation comprising two simple operations in an order, and the scaling routine first determines respective shift values for each of the operand objects and a shift value for the result object for the first of the two operations and then determines respective shift values for each of the operand objects and a shift value for the result object for the second of the two operations, wherein one or more outputs from the first determining step are utilized as inputs.

### Claim 41

A computer-implemented method for autoscaling BFP-formatted operands, intermediate results and a final result for a complex operation that can be decomposed into a sequence of N simple operations consisting of a first simple operation followed by a second simple operation and so on up to a Nth simple operation, wherein the second and subsequent operations utilize as an operand a result from a previous operation in the sequence, the method implemented on a computer on which program instructions are executed and comprising:
analyzing, by executing instructions of a program operating on computer processing circuitry, the sequence of N simple operations in order to determine for each simple operation scaling factors for its operands and its result, wherein a scaling factor for a result of one simple operation is utilized as an input to determine a scaling factor for a subsequent operation in the sequence; and
after analyzing the sequence of N simple operations, performing a calculation loop to calculate mantissa values of the final result in accordance with the complex operation and based on the mantissa values of the operands, intermediate results and their associated scaling factors determined by the analyzing step, whereby the scaling factors reduce risks of overflow and loss of accuracy otherwise attributable to the complex operation or any of its constituent simple operations.

### Claim 42 (depends on 41)

A method according to claim 41, wherein N=2.

### Claim 43 (depends on 41)

A method according to claim 41, wherein N>2.

### Claim 44 (depends on 41)

A method according to claim 41, wherein at least one of the simple operations in the sequence is addition.

### Claim 45 (depends on 41)

A method according to claim 41, wherein at least one of the simple operations in the sequence is multiplication.
