论文标题
在SIMD体系结构上具有基于区域状态的流式计算
Streaming Computations with Region-Based State on SIMD Architectures
论文作者
论文摘要
大规模数据集的流计算是并行化的有吸引力的候选者，尤其是当它们在流中的项目之间表现出独立性（因此是数据并行性）时。但是，某些流计算是有状态的，这会破坏独立性并可能限制并行性。在这项工作中，我们考虑如何从具有共同的，有限的状态形式的流式计算中提取数据并行性。假定该流被分为可变大小的区域，并且同一区域中的项目在状态的共同环境中进行处理。通常，在流上执行的计算也是不规则的，每个项目都可能进行不同的数据依赖性处理。 这项工作描述了在SIMD并行体系结构（例如GPU）上有效实施此类计算的机制。我们首先开发了一个低级协议，通过该协议可以通过该协议通过该数据流进行增强，并使用流传递到流中心的每个阶段的控制信号。然后，我们描述一个抽象，枚举和聚合，应用程序开发人员可以通过该抽象来指定具有基于区域状态的流媒体应用程序的行为。最后，我们研究了我们的思想的实施，作为用于GPU的不规则流计算计算的Mercator系统的一部分，研究了流中区域边界的频率如何影响SIMD占用率以及应用程序性能。
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.
