Streams and Stream Access Patterns

The model MagicEight uses for the mapping between a multidimensional array and a linear sequence involves a set of nested, linearly, regularly, and monotonically traversed array dimensions.

Similar data structures are used both to represent fragments of a stream and to represent the set of stream data elements accessed by a particular function.

The largest distinction is whether the mapping is conceptual or physical. Conceptual mappings or may represent unbounded subsections of a stream,

One of the mappings, the stream access pattern, is used to specify the

We standardize the description of these dimensions using two or more integer parameters, which may be repeated in a hierarchical manner to describe either a stream segment accessed by a single invocation of a task, or the mapping between a multidimensional data array and its linear form.

Two example stream access patterns and their parameters are shown in the above figure. Part b of the figure shows an example of a two level access pattern, with the step and extent of only the top level indicated.

The stream access pattern parameters are:

Dimensions

Each stream is defined for some number (possibly zero) of dimensions. There is no change in the stream along undefined dimensions.

Offset

Establishes the absolute location in the stream of the lesser bound of this stream fragment along each defined dimension. (Abbreviated as L , not O .)

Extent

This is the maximum range of the stream fragment along each defined dimension. This may be infinite.

Step

The step parameters give the counter increment in each dimension. There are several ``special'' values that a step parameter may have for a particular dimension. One is zero, which indicates that the same values are to be replicated along that dimension. The value of the extent along any dimension of the stream (denoted by ) may also be specified as a step parameter, allowing the multidimensional array to be stored in a ``packed'' format.

Order

This is the order of counter nesting (e.g. do we scan horizontally and then vertically, or vice versa.)

As there is no limit on the number of dimensions which may be defined in a program, it is safe to say that every stream is embedded in a higher dimensional space. When a task has one or more streams as arguments, it is applied to a particular fragment, or subsection, of each stream. If the task only operates over a lower dimensional or smaller space than the fragment, it will be applied multiple times over subspaces of the fragments. This allows synchronization and scheduling costs to be amortized over multiple task invocations.

• External Interface
• Internal Interface