Skip to Main content Skip to Navigation
Conference papers

Bounded Stream Scheduling in Polyhedral OpenStream

Nuno Nobre 1 Andi Drebes 2 Graham Riley 1 Antoniu Pop 1
2 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique, Inria de Paris
Abstract : We consider OpenStream, a streaming dataflow language which supports the specification of concurrent tasks that communicate through streams. Streams, in the spirit of classical process networks, have no restrictions on their size. In order to deploy an OpenStream program on a chip, however, the size of the streams has to be bounded. This constricts the range of runtime behavior by restricting the schedules to a subset of parallel executions where the required memory never surpasses the available resources. In this paper we exploit an approach that, conservatively, certifies that augmenting the intrinsic dataflow dependencies of the program with stream bounding constraints does not deadlock the program: it cannot show the existence of a deadlock but can give a certificate for the absence thereof. The aim of this work is to study the limitations of this stream bounding strategy and to demonstrate how it can currently be used to determine if an OpenStream program can execute under the particular memory constraints of a given architecture.
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-02441182
Contributor : Andi Drebes <>
Submitted on : Thursday, February 6, 2020 - 4:28:09 PM
Last modification on : Tuesday, May 4, 2021 - 2:06:02 PM
Long-term archiving on: : Thursday, May 7, 2020 - 4:50:06 PM

File

IMPACT_2020_paper_4.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02441182, version 2

Collections

Citation

Nuno Nobre, Andi Drebes, Graham Riley, Antoniu Pop. Bounded Stream Scheduling in Polyhedral OpenStream. IMPACT 2020 - 10th International Workshop on Polyhedral Compilation Techniques, Jan 2020, Bologna, Italy. ⟨hal-02441182v2⟩

Share

Metrics

Record views

172

Files downloads

228