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

Tom Plano, Jeremy Buhler

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.

Original languageEnglish
Title of host publication50th International Conference on Parallel Processing Workshop, ICPP 2021 - Proceedings
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450384414
StatePublished - Aug 9 2021
Event50th International Conference on Parallel Processing Workshop, ICPP 2021 - Virtual, Online, United States
Duration: Aug 9 2021Aug 12 2021

Publication series

NameACM International Conference Proceeding Series


Conference50th International Conference on Parallel Processing Workshop, ICPP 2021
Country/TerritoryUnited States
CityVirtual, Online


  • Bounded latency
  • Gpgpu
  • Irregular data-flow
  • Scheduling


Dive into the research topics of 'Enabling real-time irregular data-flow pipelines on SIMD Devices'. Together they form a unique fingerprint.

Cite this