The dataflow graphs used to represent the upper level of execution are composed of streams (the arcs) and tasks (the nodes). A task is the application of a function to a set of input and output streams. A compositing graph operator is provided for representing a function using a dataflow graph. Except for streams, dataflow graph elements are considered immutable once loaded, in order to simplify their duplication and distribution.
A function is an operation that takes some number of stream elements as input parameters, some number of bound dimensions, and produces one or more output stream elements as output parameters. Functions are not allowed to input or output any data except through formally bound parameters - no ``side-effects'' are allowed. Likewise, a function is not allowed to reference along a dimension not formally bound to it. See Section 3 for a longer description.
A function refers to a specific program element which may have either or both an upper and lower level of algorithm representation. The upper level representation is a graph, and a lower level representation will referred to as a sequential function.
A stream is a sequence of stream elements, which are each a tuple of value and location. Each stream element may only have a single value assigned to it. An element may also have no value assigned, in which case the element is considered undefined -- no operation using the value of the element may be performed. All elements of a stream have the same scalar type. The location is an N-tuple of integers, specifying the element's position in an N-dimensional space. A stream is said to span each of the dimensions in its N-dimensional space.
A stream may be written using a particular sequence of stream elements, and read (possibly multiple times) using a different sequence of elements. Its elements may be produced and consumed ``out-of-order''. The number of stream elements in the stream may be unbounded. In particular, the set of defined locations along one or more dimensions may be unbounded. In a realizable implementation, only a [small] finite extent along most dimensions will be defined at any one time. Streams are discussed further in Section 2.
A stream fragment is the set of stream elements with locations inside a particular multidimensional volume. For simplicity, the Q ISA defines this volume as an orthotope -- a multidimensional generalization of a rectangular parallelepiped. Thus a stream fragment is defined as elements of a stream having a location within the multidimensional volume defined by an integer starting position, step, and extent along each dimension spanned by the stream.
The set of stream elements of a single stream accessed by a single invocation of a function is the stream access pattern of the function on that stream. This access pattern is specified in the N-dimensional space defined by the function's bound dimensions, and identifies the data dependencies of a function invocation. Stream access patterns always contain at least one location, and may have a larger extent along any bound dimension. They are defined in a manner similar to stream fragments, and are discussed later.
A task is the application of a particular function to a particular list of bound parameters and dimensions. It is the dataflow graph element which produces or consumes streams.
A graph is a compositing operator, allowing complex operations to be specified as a dataflow graph composed of streams and tasks. It may be specified as an implementation of a function (other possible implementations include, for example, object code for a particular processor or configuration data for a reconfigurable processor).
Unlike sequential function implementations, the internal data objects (streams) in a graph are embedded in the algorithm representation. This requires special considerations when ``calling'' a function represented by a graph, which are described later.