Stream Access Patterns

A Stream Access Pattern

A function reads one or more stream elements from each input stream and writes one or more stream element to each output stream. In order that functions may be executed in a non-blocking manner, the Q ISA requires that the set of stream elements, or stream access pattern, accessed in one function invocation be identified for each stream input or output parameter.

An access pattern spans a specified number of a function's bound dimensions, and is specified with locations relative to a function specific origin, typically located within the set. Nulladic³ input or output parameters are located at this origin, which represents the ``current'' location when a function is invoked.

In order to minimize the complexity and size of the access pattern representation, it is defined as being the ``bounding box'' of the locations of all set elements for a given parameter. More specifically, it is the orthotope⁴ that includes all accessed locations. An access pattern defines the following parameters per specified dimension:

• offset indicates where the start of the access pattern along a dimension is located relative to the ``current'' location.

• extent indicates the size of the access pattern, in distance along the dimension -- not actual number of samples, which is indicated by extent divided by step. A negative extent indicates that the region starts at offset (including it) and extends in the earlier direction.

• sample step indicates the increment between adjacent samples along this dimension. If zero, the same value will be accessed extent times.

• function step indicates the increment between adjacent applications of the function, along this dimension. If zero, then the offset is absolute (not relative) and the indicated region is the only one of interest.

• dimension indexes which of the function's bound dimensions this dimension in the access pattern represents.

The order in which dimensions are defined in an access pattern indicates the desired ordering of the sequence of stream elements accessed by the function. This information is required when a processor utilizes a decoupled memory access mechanism.

It is a common situation for a stream access pattern to be variable, or dependent on the actual data being input. In this case, the access pattern specifies the bounding box of the union of possible sets of stream elements. Upon function termination, the stream fragments passed as parameters will be modified to communicate to the runtime system the number of elements actually consumed along each dimension. Functions with variable access patterns must be explicitly parallelized in an application specific manner, as there is no general solution to the data dependency problem posed. Several Q primitive functions (e.g. resample support access patterns which vary as functions of another function input parameter.

Footnotes

...³

The ``Greek'' terms (monadic, dyadic, etc...) will be used when referring to the number of dimensions, and the ``Latin'' terms (unary, binary, etc...) will be used to refer to the number of input parameters, as suggested by Ashcroft, et al[2]

... orthotope ⁴

An orthotope is a multidimensional generalization of the rectangular parallelepiped. It is a point, line, rectangle, and rectangular parallelepiped in zero, one, two, and three dimensions, respectively.