Nuno Miguel Nobre
email: nunomiguel.nobre@manchester.ac.uk

Andi Drebes
email: andi.drebes@inria.fr

Graham Riley
email: graham.riley@manchester.ac.uk

Antoniu Pop
email: antoniu.pop@manchester.ac.uk

Bounded Stream Scheduling in Polyhedral OpenStream

Keywords: Buffer bounding, Dataflow task-parallelism, Open-Stream

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.

Context

The industry is rapidly shifting to many-core architectures and specialized hardware accelerators, e.g., GPUs, FPGAs and ASICs. The differing capabilities of these devices increase the pressure on the programmer to develop both scalable and performance-portable code, hindering the programming process.

Task-parallel programming models are an answer to these scalability, performance-portability and productivity issues [3-8, 15, 18, 21, 24, 26, 28]. In particular, those based on streaming dataflow principles, e.g., StreamIt [START_REF] Kuo | A Productive Programming Environment for Stream Computing[END_REF][START_REF] Thies | StreamIt: A Language for Streaming Applications[END_REF], ΣC [START_REF] Goubier | ΣC: A Programming Model and Language for Embedded Manycores[END_REF], OpenStream [START_REF] Pop | OpenStream: Expressiveness and Data-flow Compilation of OpenMP Streaming Programs[END_REF], have strong assets to follow this architecture scaling trend. Computations are encapsulated in tasks, IMPACT 2020, January 22, 2020, Bologna, Italy the program's work units, that communicate through explicit, possibly unbounded data channels, or streams 1 . Taskparallel dataflow programs can be represented by directed graphs whose nodes are tasks and whose edges describe the producer-consumer task dependencies resulting from stream accesses. Each task's execution is triggered by the availability of its data operands, allowing latency to be naturally hidden, as well as precise, point-to-point synchronization of parallel activities. This is in stark contrast to fork-join and barrier-based synchronization patterns which require expensive global consensuses between workers. Hence, numerous opportunities for parallelism are naturally exposed [START_REF] Gurd | The Manchester Prototype Dataflow Computer[END_REF][START_REF] Lee | Dataflow Architectures and Multithreading[END_REF], including data, pipeline and task-parallelism [START_REF] Michael | Exploiting Coarse-grained Task, Data, and Pipeline Parallelism in Stream Programs[END_REF]. This class of languages also enforce functional determinism at the language level, a desirable property inherited from Kahn Process Networks (KPNs) [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] which form the basis for most modern deterministic streaming languages.

In order to realize dataflow programs on a tangible chip with bounded resources, streams cannot be allowed to grow beyond the available memory on said device. This poses the question of whether a given specification of a dataflow program can execute under these restrictions. In this paper, we explore a strategy first suggested in [START_REF] Cohen | Static Analysis of OpenStream Programs[END_REF], based on polyhedral model techniques, to answer such question for Open-Stream programs. In essence, the dataflow, Read-after-Write (RaW) producer-consumer task dependencies are augmented with new, artificial, Write-after-Read (WaR) dependencies. These prevent tasks from writing to a full stream by delaying their execution to after other tasks first consume from the stream, thereby freeing some memory. This contrasts with the non-blocking, unconditionally successful writes to unbounded data channels of traditional KPNs and can introduce deadlocks. Furthermore, as even in the polyhedral subset of OpenStream, dependencies might be polynomial, deadlock detection is a semi-decidable, undecidable problem [START_REF] Cohen | Static Analysis of OpenStream Programs[END_REF]. On the bright side, the polynomial extensions to the polyhedral model developed by Feautrier [START_REF] Feautrier | The Power of Polynomials[END_REF] can be leveraged to obtain a (polynomial) schedule, i.e., a task execution order, whose existence certifies the absence of deadlocks. This enables an approach which, conservatively, can certify the execution of a dataflow OpenStream program on memory constrained hardware. The aim of this work is not only to study the limitations of this stream bounding strategy beyond its undecidability restraints, but also to outline some envisioned use cases.

Section 2 provides a brief description of OpenStream, its polyhedral fragment and the technique devised in [START_REF] Cohen | Static Analysis of OpenStream Programs[END_REF][START_REF] Feautrier | The Power of Polynomials[END_REF] to compute polynomial dependencies and schedules. Section 3 outlines the strategy used to bound streams and illustrates its limitations, while Section 4 sketches some guidelines for using it in practice. Section 5 discusses the most closely related work, before we conclude in Section 6.

OpenStream: Dataflow Task-Parallelism

OpenStream is a task-parallel streaming dataflow language implemented as an extension to OpenMP supporting the specification of fine-grained task, data and pipeline parallelism [START_REF] Pop | OpenStream: Expressiveness and Data-flow Compilation of OpenMP Streaming Programs[END_REF]. The fully fledged computational model underlying the operational semantics of the language is detailed in [START_REF] Pop | Control-Driven Data Flow[END_REF] and a simplified, partial-model is also defined in [START_REF] Drebes | Dynamic optimization of data-flow task-parallel applications for large-scale NUMA systems[END_REF]. We briefly recall the three main concepts of OpenStream: streams, dataflow tasks and the control program. We present the restrictions placed upon OpenStreams programs for compatibility with the polyhedral model and review the technical solutions used for computing dependencies and handling polynomial schedules.

Streams and Tasks

A stream is a one-dimensional array of indefinite size, whose elements are of the same type. Each element of a stream is written using Dynamic Single Assignment (DSA), i.e., each stream element is written at most once. Conceptually, a stream 𝑠 has a read pointer 𝐽 𝑠 and a write pointer 𝐼 𝑠 that define which elements of the stream are affected by subsequent read and write accesses. Streams themselves can also be grouped in arrays of arbitrary size and dimension.

A task 𝑡 has a work function, i.e., an arbitrary sequence of instructions acting on local variables and on a finite set of streams. Access to each of the referenced streams is provided through windows. A window on a stream 𝑠 is characterized by the access type it provides (read or write), its horizon ℎ 𝑡,𝑠 , and the burst 𝑏 𝑡,𝑠 . The horizon is a positive integer specifying the size of the window. The burst is a non-negative integer specifying the amount by which the stream's read or write pointer is shifted after task creation. The burst of a write access window is equal to its horizon, guaranteeing single assignment, i.e., dataflow-only dependencies. The burst of a read access is either zero or equal to its horizon. A burst of zero corresponds to the peek operation. Figure 1 depicts how these concepts are used in OpenStream to express the flow of data between producer and consumer tasks. 1. Illustration of stream accesses and the evolution of the read and write pointers for a stream 𝑠 with equal bursts and horizons for all tasks, except 𝑡 3 , and a zero burst for 𝑡 1) shows the initial state of the stream before any access. In ( 2) and (3), producers 𝑡 1 and 𝑡 2 , respectively, are created and the write pointer 𝐼 𝑠 updated. Lastly, in (4) and ( 5), reader 𝑡 3 and consumer 𝑡 4 , respectively, are created and, as the former only peeks on 𝑠, the read pointer 𝐽 𝑠 is advanced solely for 𝑡 4 .

3 (𝑏 𝑡 1 ,𝑠 = ℎ 𝑡 1 ,𝑠 = 3, 𝑏 𝑡 2 ,𝑠 = ℎ 𝑡 2 ,𝑠 = 2, 𝑏 𝑡 4 ,𝑠 = ℎ 𝑡 4 ,𝑠 = 5 and 𝑏 𝑡 3 ,𝑠 = 0, ℎ 𝑡 3 ,𝑠 = 3). (
Stream accesses through windows determine the producerconsumer relationships: a task is a producer for another task if its output window overlaps with the other task's input window. Such relationships are captured in the task graph, such as the one in Figure 2 for the example of the stream accesses in Figure 1.

The Control Program

All task creations take place in the control program, an ordinary function containing task instantiation statements. Each such statement includes the respective list of read and write accesses to streams, each specified as a reference to a stream,

t 2 t 4 t 1 t 3 Figure 2
. Task graph for the example of Figure 1. Task 𝑡 3 reads, without consuming, data produced by 𝑡 1 and must wait for its execution. Task 𝑡 4 consumes data produced by both 𝑡 1 and 𝑡 2 and, thus, must be executed after both 𝑡 1 and 𝑡 2 finish. Tasks 𝑡 1 and 𝑡 2 , however, are dependency-free and can be executed concurrently. a burst and a horizon. The order of task creation is defined by the order in which the control program executes the task instantiation statements. This order defines all producerconsumer relationships, since the read and write pointers at each task creation only depend on the bursts of prior task creations referencing the same streams. Note that the resulting producer-consumer relationships only partially define the order of task execution: unrelated tasks can execute in any order.

The control program for the example in Figures 1 and2 is specified below using the compact OpenStream pseudo-code introduced in [START_REF] Cohen | Static Analysis of OpenStream Programs[END_REF][START_REF] Feautrier | On Polynomial Code Generation[END_REF]. This notation focuses on the dependencies between tasks and generally omits the tasks' work function. It uses an extended C syntax for operations directing the control flow; declarations for parameters, streams and stream arrays; and executable statements for task creation:

The Polyhedral Fragment of OpenStream

The analysis is confined to the subset of OpenStream in which the control program fits the polyhedral model, as first defined in [START_REF] Cohen | Static Analysis of OpenStream Programs[END_REF]. We only consider programs that are deterministic by construction, i.e., programs for which the task creation order in the control program, and thus the interleaving of data in streams, is determined statically. A sufficient (but not necessary) condition is to require a sequential control program [START_REF] Pop | Control-Driven Data Flow[END_REF]. That is, the code of the tasks themselves can be arbitrary, but nested task creation is not allowed, i.e., tasks cannot instantiate other tasks. In addition, communication between tasks and the control program using shared variables and OpenMP-inherited mechanisms like firstprivate or copyin is not allowed. Control flow stems, exclusively, from the textual sequence of statements, affine conditional expressions and arbitrarily nested counted loops with affine bounds in the surrounding loop iterators and global parameters. The only executable statements are task creation statements. Window bursts and horizons may be numeric or parametric constants. Stream array indexing must be affine.

Computing Dependencies and Schedules

If the control program fits in the polyhedral model, we can statically compute closed form expressions for 𝐽 𝑠 (𝑡) and 𝐼 𝑠 (𝑡), the read and write pointers of a stream 𝑠 at a point in the control program where task 𝑡 which reads from or, respectively, writes to stream 𝑠 is instantiated. As, at each task creation, these pointers are incremented by the burst, it is enough to count the number of task creations which read from or, respectively, write to 𝑠 and precede the creation of 𝑡 in the execution of the control program.

Since, within the constraints on the previous section, task creations can be represented as integer tuples in the iteration domain of their task instantiation statements and as these are polyhedra, their count can be obtained using the theory of Ehrhart polynomials [START_REF] Clauss | Counting Solutions to Linear and Nonlinear Constraints Through Ehrhart Polynomials: Applications to Analyze and Transform Scientific Programs[END_REF] or Barvinok's Brion generating functions [START_REF] Verdoolaege | Counting Integer Points in Parametric Polytopes Using Barvinok's Rational Functions[END_REF] which are both available in the barvinok library 2 . The result will, in general, be a polynomial.

As streams have the single assignment property, we need only compute dataflow or RaW dependencies. For a task 𝑡 which writes to 𝑠 through window [𝐼 𝑠 (𝑡), 𝐼 𝑠 (𝑡) + 𝑏 𝑡,𝑠 -1], and a task 𝑡 ′ which reads from 𝑠 through window [𝐽 𝑠 (𝑡 ′ ), 𝐽 𝑠 (𝑡 ′ ) + ℎ 𝑡 ′ ,𝑠 -1], there is a dependency if the two windows overlap, i.e., if:

𝐼 𝑠 (𝑡) ≤ 𝐽 𝑠 (𝑡 ′ ) + ℎ 𝑡 ′ ,𝑠 -1 ∧ 𝐽 𝑠 (𝑡 ′ ) ≤ 𝐼 𝑠 (𝑡) + 𝑏 𝑡,𝑠 -1. (1)
These dependencies inherit the polynomial nature of 𝐽 𝑠 and 𝐼 𝑠 and, thus, define semi-algebraic sets (which take the role of dependence polyhedra in the polyhedral model).

Finding schedules over these semi-algebraic sets can be achieved by leveraging Schweighofer's theorem [START_REF] Schweighofer | An algorithmic approach to Schmüdgen's Positivstellensatz[END_REF] and Feautrier's approach [START_REF] Feautrier | The Power of Polynomials[END_REF] which, respectively, play the role of Farkas lemma and its algorithmic application in traditional tools. In a sentence, this entails finding a polynomial function that can be written as a non-negative linear combination of products of the polynomials that define the set. Unfortunately, deciding on the existence of a schedule over semi-algebraic sets is only semi-decidable. That is, if a schedule is found then, by construction, it is guaranteed to be valid and, thus, rules out the possibility of deadlocks. On the contrary, if no schedule is found, it could be that the search space is limited by the order of the polynomial products considered. As we cannot possibly exhaust all linear combinations of higher degree in finite time, we cannot guarantee the non-existence of a schedule and, therefore, the existence of a deadlock.

Bounding Streams

We present a strategy to bound streams in OpenStream programs by introducing new WaR, 'back-pressure' dependencies in the polyhedral representation of the program. A few example OpenStream programs are presented which illustrate the procedure and its limitations.

Back-pressure Dependencies

If for a task execution schedule 𝜃 and a stream 𝑠 there exists a positive integer 𝑙 𝑠 , for which all indices 𝑖 ≤ 𝑗 -𝑙 𝑠 are dead (i.e. already both produced and consumed), whenever position 𝑗 is written to by some task, then 𝑠 is effectively bound by 𝑙 𝑠 for 𝜃 . This suggests that we can first append back-pressure dependencies that reproduce this behavior to Equation 1 and only then look for a schedule. To do this, we enforce all indices 𝑖 to be consumed before 𝑗 is written, i.e., we introduce a dependency from a task 𝑡 which reads from 𝑠 through [𝐽 𝑠 (𝑡), 𝐽 𝑠 (𝑡) + ℎ 𝑡,𝑠 -1] to a task 𝑡 ′ which writes to 𝑠 through [𝐼 𝑠 (𝑡 ′ ), 𝐼 𝑠 (𝑡 ′ ) + 𝑏 𝑡 ′ ,𝑠 -1] whenever ∃𝑖 ∈ [𝐽 𝑠 (𝑡), 𝐽 𝑠 (𝑡) + ℎ 𝑡,𝑠 -1] and 𝑗 ∈ [𝐼 𝑠 (𝑡 ′ ), 𝐼 𝑠 (𝑡 ′ ) + 𝑏 𝑡 ′ ,𝑠 -1], such that 𝑖 ≤ 𝑗 -𝑙 𝑠 , which is equivalent to:

𝐽 𝑠 (𝑡) ≤ 𝐼 𝑠 (𝑡 ′ ) + 𝑏 𝑡 ′ ,𝑠 -1 -𝑙 𝑠 . (2)
Once the dependencies captured by both Equation 1 and Equation 2 have been added to the dependence relation, Feautrier's approach, as summarized in Subsection 2.4, can be leveraged to find a schedule with bounded streams.

The following example illustrates the result of this procedure. It starts with a dataflow program with a schedule 𝜃 u with trivially-parallel reads and, independently, writes, and obtains a purely sequential schedule 𝜃 b when stream 𝑠 is bounded by 𝑙 𝑠 = 2. Fragment of the dependence task graph for the given example. This depicts the back-pressure dependencies for 𝑡 w,𝑘 as defined by Equation 2for 𝑙 𝑠 = 2 (dashed) and the dataflow dependencies given by Equation 1(solid).

We now provide a few examples that illustrate the limitations of this procedure.

Non-causal schedules

A causal schedule 𝜃 c is a schedule for which writes to a given stream 𝑠 occur in the same order as their write pointer indices advance, i.e., in the same order as the creation of the corresponding tasks. In other words, if 𝑡 and 𝑡 ′ are two producers in 𝑠, and 𝑡 precedes 𝑡 ′ in the control program, then 𝐼 𝑠 (𝑡) < 𝐼 𝑠 (𝑡 ′ ), but also 𝜃 c (𝑡) < 𝜃 c (𝑡 ′ ).

Consider the following example: The dataflow dependencies force the tasks in this program to be sequentially executed in the reverse order of their creation. Thus, this program only admits strict non-causal schedules (as the one given in the listing):

∀𝑡, 𝑡 ′ . 𝐼 𝑠 (𝑡) < 𝐼 𝑠 (𝑡 ′ ) → 𝜃 (𝑡 ′ ) < 𝜃 (𝑡).
However, any stream-bounding dependency of the type of Equation 2 requires at least 'partial causality', i.e., for all indices 𝑖 ≤ 𝑗 -𝑙 𝑠 to be consumed before 𝑗 is written, Equation 1 also implies that they have to be produced before 𝑗 is written. This cannot happen in the present program, and any such dependency will add a cycle to the dependence task graph in Figure 4 and thus introduce a deadlock.

It is important to note that this does not imply that 𝑠 cannot be bounded. In particular, for 𝑙 𝑠 ≥ 2 the program has a

… tw,k-2 tw,k-1 … tw,k ls = 1 … tw,k-3 … tw,k-2 tw,k-1 … tw,k ls = 2 … tw,k-3
4. Fragment of the dependence task graph for the given example. This depicts both the back-pressure dependencies for 𝑡 w,𝑘 for 𝑙 𝑠 ≤ 2 (dashed) and the dataflow dependencies (solid). valid schedule, e.g., the schedule provided in the listing 3 . The current strategy fails to capture this due to its implicit assumption that streams are filled in a (partially) causal order, which is not necessarily true for OpenStream programs. In summary, this shows that 'spurious' deadlocks can be introduced even for programs where streams can be effectively bounded, as the current approach introduces artificial backpressure dependencies that go beyond bounding streams by implicitly enforcing 'some' causality.

Minimizing stream sizes

The programmer could be interested in determining the size 𝑙 𝑠 of each stream 𝑠 such that the global surface of the streams 𝑠 𝑙 𝑠 is minimized and there is no cycle in the dependence graph. Unfortunately, this is not equivalent to a multi-objective problem on the size of each individual stream. In other words, the sizes of different streams are not independent and therefore cannot be optimized separately and successively, one after the other. Consider the following example: (left) and (center) for the two minimal stream size solutions described in the text and (right) for the stream sizes that minimize the global stream surface but cannot be identified with the current strategy due to the 'spurious' deadlock. This depicts both back-pressure dependencies (dashed) and dataflow dependencies (solid).

ls ≥ 3, lt =
an example of an execution where streams are never simultaneously fully utilized. In other words, at no point during the execution do stream 𝑠 and stream 𝑡 simultaneously hold two and three elements, respectively. This shows that, even if a minimum global stream surface were to be found, this would still be a conservative approximation of the actual memory requirements of the program.

Guidelines for Practical Applicability

Despite the undecidability of the scheduling problem and the 'spurious' constraints introduced by the stream bounding strategy, an approach can still be devised through which, given the resource constraints of a particular target architecture, one can, conservatively, decide on the execution feasibility of a particular OpenStream dataflow program.

Consider an arbitrary device, e.g., an FPGA, with some memory of total size 𝑀 and an OpenStream program with 𝑛 streams. We first compute all combinations of (𝑙 𝑠 ) 1≤𝑠 ≤𝑛 such that 𝑛 𝑠=1 𝑙 𝑠 = 𝑀 through any suitable method, e.g., stars and bars. Next, we build the dependence relation for each of these combinations by leveraging Equation 1 and Equation 2. Finally, we apply Feautrier's approach [START_REF] Feautrier | The Power of Polynomials[END_REF] in order to find a schedule. Once a schedule is constructed, we know that if we enforce the same dependencies at runtime, the streams are implemented as bounded streams in accordance to the combination for which the schedule was built, thereby guaranteeing successful execution on said device. Note that it is possible to take into account the resource requirements of tasks' work functions if these are known statically, as it is likely the case for FPGA kernels. In that case, the method just outlined is still applicable by replacing 𝑀 with 𝑀 ′ = 𝑀 -𝑀 wf where 𝑀 wf are the collective memory requirements of the tasks' work functions.

Constraining a dataflow program to run on such devices can, however, diminish the amount of parallelism available. Let us reconsider the example in Subsection 3.3. If 𝑀 = 8, we may set 𝑙 𝑠 = 3 and 𝑙 𝑡 = 5, essentially making the program free from back-pressure dependencies. The program can then execute in three waves: first 𝑡 ws and 𝑡 wt simultaneously; then 𝑡 cst and 𝑡 cts ; and lastly 𝑡 rs and 𝑡 rt . If, however, 𝑀 = 6, the only possibility is, within the proposed strategy, 𝑙 𝑠 = 𝑙 𝑡 = 3 which, as we have seen, serializes the execution of 𝑡 cts after 𝑡 cst .

On the other hand, these memory constrained devices may be massively parallel. Thus, even if some parallelism is lost due to memory constraints, the parallelism opportunities available might still greatly surpass the capabilities of manycore CPUs. In addition, the specialized hardware they expose to the programmer might also allow faster implementations of tasks' work functions, thereby compensating for the restrictions imposed by the constrained memory resources.

Related Work

Kahn Process Networks (KPNs) [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] underpin most modern languages based on streaming computing concepts, including OpenStream. Perhaps unsurprisingly, Parks [START_REF] Thomas | Bounded Scheduling of Process Networks[END_REF] has shown KPNs' expressive power comes at the cost of undecidability for deadlock detection and bounded buffering guarantees.

However, despite the similarities, OpenStream and KPNs have subtle differences and the equivalence of the models is still not fully understood. Unlike KPNs, OpenStream allows streams to be read and written by several tasks; and, unlike OpenStream, KPNs allow conditional decisions on what streams to read from based on the data that circulates on the streams. Nevertheless, Cohen et al. [START_REF] Cohen | Static Analysis of OpenStream Programs[END_REF] have shown the same undecidability properties hold for OpenStream programs.

This leaves a few options to the programmer willing to exploit data-centric programming models: (1) resort to models with restricted expressive power like Synchronous DataFlow (SDF) and Cyclo-Static DataFlow (CSDF) that statically provide deadlock-absence and bounded memory guarantees [START_REF] Parks | A comparison of synchronous and cycle-static dataflow[END_REF]; (2) resort to approaches like the one described here to, in practice, albeit conservatively, certify the execution of more expressive dataflow programs on devices with constrained memory resources; or (3) rely on automated process network generation from static control loop nests initially written in an imperative language, like Verdoolaege's Polyhedral Process Networks [START_REF] Verdoolaege | Polyhedral Process Networks[END_REF] which allow conservative estimation of the required buffer sizes for a given schedule, but are limited to polyhedral-amenable code. This choice will probably be ultimately guided by the application domain, but we believe that current and upcoming architectures require dataflow models that are more expressive -even than the polyhedral subset of OpenStream defined here -that allow irregular, dynamic communication patterns and the execution of non-polyhedral code, e.g., as part of tasks' work functions. In this sense, the presented work builds on this insight and motivates future work in this direction.

Lastly, regarding the stream minimization problem of Subsection 3.3, the work in [START_REF] Benazouz | new approach for minimizing buffer capacities with throughput constraint for embedded system design[END_REF][START_REF] Benazouz | Cyclo-static DataFlow Phases Scheduling Optimization for Buffer Sizes Minimization[END_REF][START_REF] Munier-Kordon | A Buffer Minimization Problem for the Design of Embedded Systems[END_REF] on buffer minimization in the context of restricted KPNs, SDF and CSDF graphs might pave the way for the same kind of optimizations in OpenStream, or a subset of the language, in future work.

Conclusion

We showed how augmenting polyhedral OpenStream programs with back-pressure dependencies can be used to bound streams and statically, albeit conservatively, decide if said programs can be executed in devices with limited memory. We described how the current method is limited in its power due to the introduction of 'spurious' deadlocks, the difficulty of global stream minimization, the overestimation of actual memory usage and detection undecidability.

  stream s; task t1 { write three times to s; } task t2 { write two times to s; } task t3 { peek three times from s; } task t4 { read five times from s; }

Figure 3 Figure 3 .

 33 Figure3illustrates how the back-pressure dependencies introduced for 𝑙 𝑠 = 2 force the execution of 𝑡 w,𝑘 to succeed 𝑡 r,𝑘-1 and precede 𝑡 r,𝑘 .

  (𝑡 sink ) = 𝑁 read once from s; // 𝐽 𝑠 (𝑡 sink ) = 0 } for(k = 1; k < N; ++k) task tw { // 𝜃 (𝑡 w,𝑘 ) = 𝑁 -𝑘 read once from s; // 𝐽 𝑠 (𝑡 w,𝑘 ) = 𝑘 write once to s; // 𝐼 𝑠 (𝑡 w,𝑘 ) = 𝑘 -1 } task tsource { // 𝜃 (𝑡 source ) = 0 write once to s; // 𝐼 𝑠 (𝑡 source ) = 𝑁 -1 }

Figure 5 .

 5 Figure 5. Dependence task graphs for the given example: (left) and (center) for the two minimal stream size solutions described in the text and (right) for the stream sizes that minimize the global stream surface but cannot be identified with the current strategy due to the 'spurious' deadlock. This depicts both back-pressure dependencies (dashed) and dataflow dependencies (solid).

  [START_REF] Blumofe | Cilk: An Efficient Multithreaded Runtime System[END_REF]

	ls = 2, lt ≥ 5			ls = 2, lt = 3
	t ws	t wt	t ws	t wt	t ws	t wt
	t cts	t cst	t cts	t cst	t cts	t cst
	t rt	t rs	t rt	t rs	t rt	t rs

Tasks are also known in the literature as agents, actors, processes and filters. Likewise, data channels or lines are also known as buffers. We adhere to OpenStream's nomenclature, which designates these structures as streams.

[Online] Available at http://barvinok.gforge.inria.fr.

Tasks execute atomically. When a producer task starts execution, it must already have enough space to write to the stream. If, as when 𝑙 𝑠 = 1, a producer relies on itself to free the stream, the program deadlocks.

Acknowledgments

This work was supported by the EU FET-HPC grants ExaN-oDe H2020-671578 EuroEXA H2020-754337. A. Pop is funded by a RAEng University Research Fellowship.

The bound on stream 𝑠 sequentializes the execution of 𝑡 cst after 𝑡 cts , requiring a large enough bound on stream 𝑡 to prevent the introduction of the reverse dependency, as seen in Figure 5 (left). Conversely, if stream 𝑡 is optimized first, 𝑡 wt requires 𝑙 𝑡 ≥ 3, and we find 𝑙 𝑡 = 3 is feasible for 𝑙 𝑠 ≥ 3. Figure 5 (center) shows the corresponding dependence graph.

Minimizing the global stream surface is a well-known problem in the context of KPNs, and has been proven NPcomplete for as few as three tasks [START_REF] Munier-Kordon | A Buffer Minimization Problem for the Design of Embedded Systems[END_REF]. This example shows how, for OpenStream, like for KPNs, a strategy that tries to minimize each stream successively produces different results depending on the order streams are considered in. Next, we show how, unlike for KPNs, it is possible that none of the identified solutions minimizes the global stream surface.

In fact, although within the scope of the back-pressure dependencies strategy introduced in Subsection 3.1 these solutions are both minimal for the component-wise order in (𝑙 𝑠 , 𝑙 𝑡 ), neither solution minimizes the global stream surface. In reality, even though a situation where 𝑙 𝑠 = 2 and 𝑙 𝑡 = 3 apparently introduces a deadlock, as seen in Figure 5 (right), this is a 'spurious' deadlock of the type discussed in Subsection 3.2. For a (non-causal) schedule which executes each of the two (unilaterally) connected components of the dataflow dependence task graph one after the other, these bounds are both respected: sequentially execute 𝑡 ws , followed by 𝑡 cts and 𝑡 rt , and finally 𝑡 wt , followed by 𝑡 cst and 𝑡 rs .

Furthermore, one should note that the determined global stream surface does not correspond to the maximum memory usage of the program. Notice that, even if our strategy were able to identify 𝑙 𝑠 = 2 and 𝑙 𝑡 = 3 as the global stream surface minimizer, the sequential schedule described above provides