1.2 Terminology

Definitions of common stream programming terms follow.

• [Record]A record is either an atomic data type such as an integer or a floating point number or an aggregate of records.
• [Stream]A stream is a directed sequence of records. Depending on their direction, streams may be either input streams or output streams. While most streams are very long or never ending, stream programming systems also support some specialized types of streams. Constant streams have a fixed length are often repeatedly reused. Conditional streams access a record from the stream only when a condition code that is computed in a processor or a function unit cluster of a processor is true [10]. They may be input or output streams depending on the direction of access. Most streams are sequential, i.e., for input streams the algorithm can read only the next record in the stream and write the sequentially next record to an output stream. Gather streams allow arbitrary indexing to fetch records [1]. Indexed streams allow accessing elements within a constrained range of one stream to be accessed using indices from another stream [13].
• [Derivation]A new stream defined to contain a subset of the records from another stream is called a derived stream. For example, if the variable x refers to an existing input stream, y is a constant stream containing the integers (0,2,4,8) an indexed stream z may be derived from x and y that is constrained to have the range (0,8) relative to the current position of x. If $S[i]$ denotes the $i^{th}$ record relative to the current position of stream $S$, then $z[0]=x[0]$, $z[1]=x[2],$ and so on. Derivations may be done using other mechanisms such as strided or bit-reversed access. The key point is that the stream compiler should be able to reason about the relationship of records of the derived and base streams.
• [Kernel]A kernel is a function that transforms input streams to output streams. Kernel functions are typically loop oriented computations with few or non-existent conditional branches in the loop body. Simple conditional operations in the original algorithm may often be converted into forms such as predicated execution/if-conversion, conditional moves and input/output to conditional streams.
• [Stream Graph]A stream graph is a directed graph where the nodes are kernels and the edges correspond to streams that convey the data between the kernels.
• [SRF]Stream Register Files (SRF) are specialized storage structures used to hold streaming data. They are essentially large blocks of SRAM under the control of hardware that knows how to fetch and store the sequentially next element of a particular stream, perform operations for gather streams, indexed streams etc.
• [LRF]The complexity of multi-ported register files is one of the critical factors that limits issue width in a traditional microprocessor. Rather than use a single central register file, stream architectures attach Local Register Files (LRF) to execution clusters or function units. These LRFs typically serve only the units they are attached to. Inter-cluster communication is handled by a compiler controlled communication network.
• [Producer-Consumer Locality]It is common in stream applications for a producer kernel to generate and save some results to an SRF and the results are immediately used by a consumer kernel straight out of the SRF without saving intermediate results to lower levels of the memory hierarchy. Such reuse of intermediate results is termed producer-consumer locality.