Enabling real-time irregular data-flow pipelines on SIMD Devices

Streaming data-flow applications arise in many contexts where each item in a data stream must be processed within a bounded latency, or deadline, following its arrival. We consider applications whose behavior is irregular, in the sense that the application may reduce or amplify data volumes dynamically at various stages of its computation. Our implementation target for these applications is SIMD-capable processors such as GPUs. For such devices, organizing the computation so that a full-width SIMD vector of inputs can be processed at once makes efficient use of the processor. However, having parts of the computation wait while full vectors of input accumulate may cause the application to miss deadlines. We present a novel approach to scheduling irregular streaming applications with latency constraints on SIMD devices. After describing a model for executing such applications, we formalize the objective of efficient processor utilization and the constraints associated with bounded latency and sufficient throughput to handle a stream of items arriving at a fixed rate. We introduce a strategy, enforced waits, to optimize the objective subject to the constraints. We demonstrate empirically that, for a test application from bioinformatics, our strategy can lower processor utilization relative to a baseline approach that cannot introduce waits inside the application pipeline. Finally, we characterize the region of parameter space in which the new approach is likely to outperform the baseline.