# US 2010/0146020 A1 · System and Method for the Parallelization of Saturated Accumulation Operations

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

- Number: US 2010/0146020 A1
- Document ID: US20100146020A1
- Status: Published application
- Kind: A1
- Application number: 12/405,868
- Filed: 2009-03-17
- Published: 2010-06-10
- Earliest claimed: 2008-12-05
- Assignees: Broadcom Corporation
- Inventors: Alexander J. BURR; Timothy M. Dobson
- Web page: https://patentgrep.com/patent/US20100146020A1

## CPC

- G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)}
- G06F 7/49921: {Saturation, i.e. clipping the result to a minimum or maximum value}
- G06F 7/509: for multiple operands, e.g. digital integrators
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A system and method for parallelization of saturated accumulation is provided. In the method, an input sequence is divided into a plurality of subsequences. For each subsequence, three parallel saturating additions are performed. The local saturation minimum is the saturating addition of the global saturation minimum and the values of the subsequence. The local midpoint is the saturating addition of the values of the subsequence and the local saturation maximum is the saturating addition of the global saturation maximum and the values of the subsequence. In embodiments, the accumulation total for a subsequence is calculated as the saturating addition of the accumulation total for prior subsequences and the local midpoint of the current subsequence, wherein the accumulation total of the last subsequence is the result of the saturated accumulation for the sequence. In another embodiment, the saturated addition of subsequence results are further parallelized before the final result is reached.

## Claims

### Claim 1

A method for performing saturated accumulation of a sequence, comprising:
(a) dividing the sequence of values into a series of subsequences, each subsequence including a plurality of values; and
(b) determining a local saturation minimum, local midpoint, and local saturation maximum for one or more subsequences, wherein, for each subsequence, step (b) comprises:
(i) determining, in a processing unit, the local saturation minimum via a saturating addition of a global saturation minimum and the plurality of values in the subsequence, wherein the global saturation minimum is a first value of the saturating addition,
(ii) determining, in a processing unit, the local midpoint via a saturating addition of the plurality of values in the subsequence, and
(iii) determining, in a processing unit, the local saturation maximum via a saturating addition of a global saturation maximum and the plurality of values in the subsequence, wherein the global saturation maximum is a first value of the saturating addition.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
(c) calculating an accumulation total, using saturating addition, for each subsequence in the series of subsequences,
wherein an accumulation total for an immediately prior subsequence is added to the local midpoint of a current subsequence, except if the current subsequence is an initial subsequence in the series, and the local saturation minimum and local saturation maximum of the current subsequence are used to define the saturation range for the saturation addition,
wherein the accumulation total for an initial subsequence is the local midpoint of the initial subsequence,
wherein the accumulation total for the last subsequence in the series is the result of the saturating accumulation for the sequence.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
(c) dividing local subsequence results into further subtotal subsequences, each subtotal subsequence including a local saturation minimum, a local saturation maximum, and a local midpoint for a first and second subsequence; and
(d) determining a local saturation minimum, local midpoint, and local saturation maximum for two or more subtotal subsequences, wherein, for each subtotal subsequence, step (d) comprises:
(i) determining, in a processing unit, the subtotal subsequence local saturation minimum via a saturating addition of the local saturation minimum of the first subsequence and the local midpoint of the second subsequence,
(ii) determining, in a processing unit, the subtotal subsequence local midpoint via a saturating addition of the local midpoints of the first and second subsequences, and
(iii) determining, in a processing unit, the subtotal subsequence local saturation maximum via a saturating addition of the local saturation maximum of the first subsequence and the local midpoint of the second subsequence.

### Claim 4 (depends on 3)

The method of claim 3, wherein step (d) is performed for two or more subtotal subsequences substantially in parallel.

### Claim 5 (depends on 3)

The method of claim 3, wherein steps (c) and (d) are repeated in subsequent stages of parallelization until three or less local subsequence results remain.

### Claim 6 (depends on 5)

The method of claim 5, wherein the saturating addition of the remaining subsequence results are accumulated linearly.

### Claim 7 (depends on 3)

The method of claim 3, wherein the subtotal subsequence local minimum calculation of step (d)(i) saturates to a range defined by the local saturation minimum and the local saturation maximum of the second subsequence.

### Claim 8 (depends on 3)

The method of claim 3, wherein the subtotal subsequence local midpoint calculation of step (d)(ii) saturates to a range defined by the difference between the global saturation minimum and the global saturation maximum and the difference between the global saturation maximum and the global saturation minimum.

### Claim 9 (depends on 3)

The method of claim 3, wherein the subtotal subsequence local maximum calculation of step (d)(iii) saturates to a range defined by the local saturation minimum and the local saturation maximum of the second subsequence.

### Claim 10 (depends on 3)

The method of claim 3, wherein at least two of steps (d)(i), (d)(ii), and (d)(iii) are performed substantially in parallel.

### Claim 11 (depends on 3)

The method of claim 3, wherein steps (d)(i), (d)(ii), and (d)(iii) are performed in software executing on parallel hardware processing units.

### Claim 12 (depends on 1)

The method of claim 1, wherein a global saturation range for the saturating additions performed in steps (b)(i) and (b)(iii) is defined by the global saturation minimum and the global saturation maximum.

### Claim 13 (depends on 1)

The method of claim 1, wherein a global saturation range for the saturating addition performed in step (b)(ii) is defined by the difference between the global saturation minimum and the global saturation maximum and the difference between the global saturation maximum and the global saturation minimum

### Claim 14 (depends on 1)

The method of claim 1, further comprising, for an initial subsequence, determining a local midpoint for the initial subsequence via a saturating addition of the plurality of values in the subsequence.

### Claim 15 (depends on 1)

The method of claim 1, wherein step (b) is performed for two or more subsequences substantially in parallel.

### Claim 16 (depends on 1)

The method of claim 1, wherein step (b)(i) comprises:
(A) providing a first saturating multiply-accumulate instruction using saturating arithmetic, MAC acc, x, y, to a processing unit to determine the local minimum for the subsequence, wherein the product of x and y is a value in the subsequence.

### Claim 17 (depends on 16)

The method of claim 16, wherein the saturation range is defined by the global saturation minimum and the global saturation maximum.

### Claim 18 (depends on 16)

The method of claim 16, wherein step (b)(ii) comprises:
(A) providing a second saturating multiply-accumulate instruction using saturating arithmetic, MAC acc, x, y, to a processing unit to determine the local midpoint for the subsequence, wherein the product of x and y is a value in the subsequence.

### Claim 19 (depends on 18)

The method of claim 18, wherein step (b)(iii) comprises:
(A) providing a third saturating multiply-accumulate instruction using saturating arithmetic, MAC acc, x, y, to a processing unit to determine the local minimum for the subsequence, wherein the product of x and y is a value in the subsequence.

### Claim 20 (depends on 19)

The method of claim 19, wherein the saturation range is defined by the global saturation minimum and the global saturation maximum.

### Claim 21 (depends on 18)

The method of claim 18, wherein the saturation range is defined by the difference between the global saturation minimum and the global saturation maximum and the difference between the global saturation maximum and the global saturation minimum.

### Claim 22 (depends on 1)

The method of claim 1, wherein at least two of steps (b)(i), (b)(ii), and (b)(iii) are performed substantially in parallel.

### Claim 23 (depends on 1)

The method of claim 1, wherein steps (b)(i), b(ii), and b(iii) are performed in software executing on parallel hardware processing units.

### Claim 24

A system for performing a saturated accumulation of a sequence having a plurality of sequential subsequences, comprising:
a plurality of sets of first-level saturating arithmetic units, wherein each set of first-level saturating arithmetic units receives a different subsequence, wherein each set of first-level saturating arithmetic units includes:
a saturating arithmetic unit configured to perform the saturating addition of a global saturation minimum and the values of the subsequence to determine a local saturation minimum,
a saturating arithmetic unit configured to perform the saturating addition of the values of the subsequence to determine a local midpoint, and
a saturating arithmetic unit configured to perform the saturating addition of a global saturation maximum and the values of the subsequence to determine a local saturation maximum.

### Claim 25 (depends on 24)

The system of claim 24, further comprising:
a plurality of second-level saturating arithmetic units operating on the subsequences in order, wherein each second-level arithmetic unit is configured to perform the saturating addition of an accumulation total of one or more prior subsequences and a local midpoint of a current subsequence, wherein the saturation range for the saturating addition is defined by the local saturation minimum and local saturation maximum of the current subsequence.

### Claim 26 (depends on 25)

The system of claim 25, further comprising:
a saturating arithmetic unit configured to perform the saturating addition of an initial subsequence to determine the local midpoint for the initial subsequence.

### Claim 27 (depends on 25)

The system of claim 25, wherein the accumulation total is initialized to the local midpoint for the initial subsequence.

### Claim 28 (depends on 24)

The system of claim 24, further comprising:
a plurality of sets of second-level saturating arithmetic units, wherein each set of second-level saturating arithmetic units receives a different subtotal subsequence, each subtotal subsequence including a local saturation minimum, a local saturation maximum, and a local midpoint for a first and second subsequence, wherein each set of second-level saturating arithmetic units includes:
a saturating arithmetic unit configured to perform the saturating addition of the local saturation minimum of the first subsequence and the local midpoint of the second subsequence to determine a subtotal subsequence local saturation minimum,
a saturating arithmetic unit configured to perform the saturating addition of the local midpoints of the first and second subsequences to determine a subtotal subsequence local midpoint, and
a saturating arithmetic unit configured to perform the saturating addition of the local saturation maximum of the first subsequence and the local midpoint of the second subsequence to determine a subtotal subsequence local saturation maximum.

### Claim 29 (depends on 28)

The system of claim 28, wherein at least two sets of second-level saturating arithmetic units operate substantially in parallel.

### Claim 30 (depends on 24)

The system of claim 24, wherein the saturation range for the saturating additions performed to determine the local saturation minimum and the local saturation maximum is defined by the global saturation minimum and the global saturation maximum.

### Claim 31 (depends on 24)

The system of claim 24, wherein the saturation range for the saturating addition performed to determine the local midpoint is defined by the difference between the global saturation minimum and the global saturation maximum and the difference between the global saturation maximum and the global saturation minimum.

### Claim 32 (depends on 24)

The system of claim 24, wherein the first-level saturating arithmetic units are multiply-accumulators.

### Claim 33 (depends on 24)

The system of claim 24, wherein at least two sets of first-level saturating arithmetic units operate substantially in parallel.

### Claim 34

A processor for performing a saturated accumulation of a sequence having a plurality of sequential subsequences, comprising:
a plurality of execution units, wherein each execution unit receives a different subsequence, and wherein each execution unit is configured to calculate a local saturation minimum, a local midpoint, and a local saturation maximum for the subsequence using saturating addition, wherein two or more of the execution units operate substantially in parallel; and
a plurality of second-level saturating arithmetic units operating on the subsequences in order, wherein each second-level arithmetic unit is configured to perform the saturating addition of an accumulation total of one or more prior subsequences and a local midpoint of a current subsequence being processed, wherein the saturation range for the saturating addition is defined by the local saturation minimum and local saturation maximum of the current subsequence being processed.

### Claim 35 (depends on 34)

The processor of claim 34, wherein each execution unit receives a single multiply-accumulate instruction which executes the local saturation minimum, local midpoint, and local saturation maximum calculations.

### Claim 36 (depends on 34)

The processor of claim 34, wherein the processor is a sixty-four bit long instruction word processor including a plurality of single instruction multiple data units.
