Computation modification by amplification of stencil including stencil points

Patent metadata

Field	Value
Publication number	US-11567746-B2
Application number	US-202016927016-A
Country	US
Kind code	B2
Filing date	Jul 13, 2020
Priority date	Oct 29, 2014
Publication date	Jan 31, 2023
Grant date	Jan 31, 2023

Abstract

In a sequence of major computational steps or in an iterative computation, a stencil amplifier can increase the number of data elements accessed from one or more data structures in a single major step or iteration, thereby decreasing the total number of computations and/or communication operations in the overall sequence or the iterative computation. Stencil amplification, which can be optimized according to a specified parameter such as compile time, rune time, code size, etc., can improve the performance of a computing system executing the sequence or the iterative computation in terms of run time, memory load, energy consumption, etc. The stencil amplifier typically determines boundaries, to avoid erroneously accessing data elements not present in the one or more data structures.

First claim

What is claimed is:

1. A method for improving processing efficiency, the method comprising performing by a processor the steps of:
in a computation sequence comprising a plurality of sequence steps, identifying a computation using a stencil comprising a set of stencil points, each stencil point corresponding to a value of a respective element of a data structure; and
modifying the computation by amplifying the stencil according to a specified amplification factor (T) by recursively replacing a stencil point with a first-level substencil comprising a set of first-level substencil points corresponding to prior iterations from an immediately prior iteration up to a (T+1)-th prior iteration, each first-level substencil point corresponding to a value of a respective element of the data structure, at least one first-level substencil point being associated with a data-structure element that is different from data-structure elements associated with all stencil points;
wherein one of identifying and modifying the computation comprises representing the computation as a function of values of respective elements of the data structure corresponding to the set of stencil points, each element of the data structure being specified using a central vector associated with the stencil and an offset vector associated with a corresponding stencil point; and
wherein execution of the modified computation reduces a number of iterations of the specified computation by a factor (T+1).

2. The method of claim 1 , wherein modifying the computation comprises generating a loop nest corresponding to at least one stencil point, the loop nest comprising a loop corresponding to a parameterized dimension of the data structure, the loop comprising a statement accessing an element of the data structure in the parameterized dimension according to a parameter based at least in part on the loop index.

3. The method of claim 2 , wherein the loop nest corresponds to at least one absolute dimension of the data structure.

4. The method of claim 1 , wherein modifying the computation comprises generating a statement corresponding to a stencil point at which all dimensions of the data structure are absolute.

5. The method of claim 1 , wherein a cardinality of the central vector and a cardinality of the offset vector are equal to a number of spatial dimensions of the data structure, and each spatial dimension of the data structure corresponds to a respective element of the central vector and a respective element of the offset vector.

6. The method of claim 5 , wherein modifying the computation comprises:
for each first-level substencil point of the first-level substencil, computing a first-level resulting offset vector as a combination of the offset vector associated with the stencil point and an offset vector corresponding to that first-level substencil point; and
representing the stencil point as a function of values of respective elements of the data structure corresponding to the set of first-level substencil points, each element of the data structure being specified using a central vector associated with the stencil and a first-level resulting offset vector associated with a corresponding first-level substencil point.

7. The method of claim 6 , further comprising:
for each spatial dimension associated with the resulting offset vectors corresponding to the first-level substencil:
determining a first-level maximum offset value; and
from a boundary of the data structure in that spatial dimension, designating any data-structure element within a distance less than the first-level maximum offset value as a boundary element;

designating a stencil point from the set of stencil points as a boundary point if that stencil point corresponds to a boundary element; and
selecting a stencil point from the stencil, for replacement thereof with the first-level substencil, only if that stencil point is not designated as a boundary point.

8. The method of claim 6 , further comprising:
remodifying the computation by replacing a first-level substencil point with a second-level substencil comprising a set of second-level substencil points, each second-level substencil point corresponding to a value of a respective element of the data structure from a second previous sequence step, at least one second-level substencil point being associated with a data-structure element that is different from data-structure elements associated with all stencil points and all first-level substencil points.

9. The method of claim 8 , wherein modifying the computation further comprises:
for each second-level sub stencil point of the second-level substencil, computing a second-level resulting offset vector as a combination of the first-level resulting offset vector associated with a first-level substencil point to be replaced with the second-level substencil and an offset vector corresponding to that second-level substencil point; and
representing the first-level substencil point as a function of values of respective elements of the data structure corresponding to the set of second-level substencil points, each element of the data structure being specified using a central vector associated with the stencil and a second-level resulting offset vector associated with a corresponding second-level substencil point.

10. The method of claim 9 , further comprising:
for each spatial dimension associated with the resulting offset vectors corresponding to the second-level substencil:
determining a second-level maximum offset value; and
from a boundary of the data structure in that spatial dimension, designating any data-structure element within a distance less than the second-level maximum offset value as a boundary element;

designating a stencil point from the set of stencil points as a boundary point if that stencil point corresponds to a boundary element; and
selecting a stencil point from the stencil, for replacement thereof with the second-level substencil, only if that stencil point is not designated as a boundary point.

11. The method of claim 8 , wherein at least one of: (i) a cardinality of the set of first-level substencil points, and (ii) a cardinality of the set of second-level substencil points is greater than one.

12. The method of claim 1 , wherein:
each stencil point in a subset of stencil points from the set of stencil points is associated with a respective stencil coefficient;
each first-level substencil point in a subset of first-level substencil points from the set of first-level stencil points is associated with a respective first-level substencil coefficient; and
modifying the computation comprises generating a coefficient computation that produces a resulting coefficient, based on a stencil coefficient and a first-level substencil coefficient.

13. The method of claim 12 , wherein:
the computation comprises a first stencil point and a second stencil point;
modifying the computation comprises:
replacing the first stencil point, having associated therewith a first stencil coefficient, with a first first-level substencil comprising a first first-level substencil point, having associated therewith a first substencil coefficient, and corresponding to a particular element of the data structure; and
replacing the second stencil point, having associated therewith a second stencil coefficient, with a second first-level substencil comprising a second first-level substencil point, having associated therewith a second substencil coefficient, and corresponding to the particular element of the data structure; and

generating the coefficient computation comprises specifying a transform operation that produces the resul

Assignees

• Qualcomm Technologies Inc

Inventors

• Baskaran Muthu M
• Henretty Thomas
• Lethin Richard A
• Meister Benoit J

Classifications

• G06F8/4441 Primary

  Reducing the execution time required by the program code · CPC title

• G06F8/4434

  Reducing the memory space required by the program code · CPC title