Data Trace

The data trace is a data structure, which describes the data flow of an individual data element. Each data element contains a data trace. The data trace consists of 2 lists of the exact same size, accessingNodes and dataAccesses. The data access always correspondes to the accessing node on the same index. Furthermore, accessing nodes are only of type ComplexExpressionNode or SimpleExpressionBlockNode. Thus, for further knowledge on the context the parent nodes can be utilized. Data accesses are classified in a few different ways, depending on the parallel pattern context.

Data Access

The data access describes which data elements are accessed and how they are accesses. The based class dataAccess consists of two parameters and covers scalar data accesses regardless of the context and array accesses in a non-parallel context. Data accesses are also parent aware, in the sense, ancestor nodes of the actuall expression also store the access, iff the data element is within the scope of the ancestor.

Parameters

• data: the data element which is accessed.
• isReadAccess: true, iff the data is only read from.

IO Data Access

The IO data access describes data accesses by IO-operations regardless of context. The IO data access extends the base data access, but adds no new parameters.

Map Data Access

The map data access describes data accesses to arrays within a map or reduction pattern. Reminder: besides the reduction step, the reduction can be considered a map pattern. Parallel patterns restrict the accessing scheme for parallel patterns to a W * x + b shape for simplicity. Where, x is the running variable INDEX, W is a scaling factor and b is an offset. Since, the INDEX value is always the same for maps and reductions, only W and b values are stored.

Parameters

• scalingFactor: the value of the scaling factor W.
• shiftOffset: the value of the offset b.

Reduce Data Access

The reduce data access describes the writing data accesses during the reduction step of a reduction pattern. This access is always performed on a scalar value, thus no additional parameters are necessary. The reduce data access extends the base date access.

Recursion Data Access

The recursion data access describes data accesses in the context of a recursive pattern and extends the base data access. Because, the recursion pattern is not yet subject of optimization no additional information needs to be stored.

Dynamic Programming Data Access

The dynamic programming data access describes data accesses to arrays within a dynamic programming pattern. Dynamic programming patterns restrict the accessing scheme for parallel patterns to a x + b shape for simplicity. Where, x is the running variable INDEX0 or INDEX1 and b is an offset. Although, only 1-dimensional arrays can be used as an input for dynamic programming patterns the values of b and x are stored in lists, to account for future extensions.

Parameters

• ruleBaseIndex: the value of the base x, where the first value accounts for the access on the highest dimension.
• shiftOffsets: the values of the offset b, where the first value accounts for the access on the highest dimension.

Stencil Data Access

The stencil data access describes data accesses to arrays within a stencil pattern. Stencil patterns restrict the accessing scheme for parallel patterns to a W * x + b shape for simplicity. Where, x is the running variable INDEX0 up to INDEXN-1 (Where N is the dimension of the output array), W is a scaling factor and b is an offset.

Parameters

• ruleBaseIndex: the value of the base x, where the first value accounts for the access on the highest dimension.
• shiftOffsets: the values of the offset b, where the first value accounts for the access on the highest dimension.
• scalingFactor: the values of the scaling factor W, where the first value accounts for the access on the highest dimension.

Example

An access of the form:

input[3 * INDEX0 + 2][INDEX1]

becomes the lists:

• ruleBaseIndex: [INDEX0,INDEX1]
• shiftOffset: [2,0]
• scalingfactor: [3,1]