Skip to Main content Skip to Navigation
Conference papers

Bounded Stream Scheduling in Polyhedral OpenStream

Nuno Miguel Nobre 1 Andi Drebes 2 Graham Riley 1 Antoniu Pop 1 
2 Parkas - Parallélisme de Kahn Synchrone
DI-ENS - Département d'informatique - ENS Paris, 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
Contributor : Andi Drebes Connect in order to contact the contributor
Submitted on : Thursday, February 6, 2020 - 4:28:09 PM
Last modification on : Wednesday, June 8, 2022 - 12:50:04 PM
Long-term archiving on: : Thursday, May 7, 2020 - 4:50:06 PM


Files produced by the author(s)


  • HAL Id : hal-02441182, version 2



Nuno Miguel 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⟩



Record views


Files downloads