  Streaming computations on massive data sets are an attractive candidate for
parallelization, particularly when they exhibit independence (and hence data
parallelism) between items in the stream. However, some streaming computations
are stateful, which disrupts independence and can limit parallelism. In this
work, we consider how to extract data parallelism from streaming computations
with a common, limited form of statefulness. The stream is assumed to be
divided into variably-sized regions, and items in the same region are processed
in a common context of state. In general, the computation to be performed on a
stream is also irregular, with each item potentially undergoing different,
data-dependent processing.
  This work describes mechanisms to implement such computations efficiently on
a SIMD-parallel architecture such as a GPU. We first develop a low-level
protocol by which a data stream can be augmented with control signals that are
delivered to each stage of a computation at precise points in the stream. We
then describe an abstraction, enumeration and aggregation, by which an
application developer can specify the behavior of a streaming application with
region-based state. Finally, we study an implementation of our ideas as part of
the MERCATOR system for irregular streaming computations on GPUs, investigating
how the frequency of region boundaries in a stream impacts SIMD occupancy and
hence application performance.
