Enver Kayaaslan

Thomas Lambert

Loris Marchal

Bora Uçar

Scheduling Series-Parallel Task Graphs to Minimize Peak Memory

Keywords: series-parallel graphs, scheduling, peak memory minimization graphes séries-parallèles, ordonnancement, minimisation du pic mémoire

We consider a variant of the well-known, NP-complete problem of minimum cut linear arrangement for directed acyclic graphs. In this variant, we are given a directed acyclic graph and asked to find a topological ordering such that the maximum number of cut edges at any point in this ordering is minimum. In our main variant the vertices and edges have weights, and the aim is to minimize the maximum weight of cut edges in addition to the weight of the last vertex before the cut. There is a known, polynomial time algorithm [Liu, SIAM J. Algebra. Discr., 1987] for the cases where the input graph is a rooted tree. We focus on the variant where the input graph is a directed series-parallel graph, and propose a polynomial time algorithm. Directed acyclic graphs are used to model scientific applications where the vertices correspond to the tasks of a given application and the edges represent the dependencies between the tasks. In such models, the problem we address reads as minimizing the peak memory requirement in an execution of the application. Our work, combined with Liu's work on rooted trees addresses this practical problem in two important classes of applications.

Introduction

Scientific applications are often modeled as task graphs, where vertices represent tasks and edges represent the dependencies between tasks. In these models, each task consumes one or more input file/data, and produces one or more output file/data. To be executed, a task also requires an execution file/data. As the size of the data to be processed increases, minimizing the peak memory of an application arises as an important objective. This is so for the following reason. Modern computing platforms exhibit a complex memory hierarchy ranging from caches to RAM and disks and even sometimes tape storage, with the classical property that the smaller the memory, the faster. Thus, to avoid large makespan one must keep the application's peak memory low, so as to avoid using low bandwidth memory as much as possible. We consider the execution of a task graph on a single compute resource, i.e., a single processor and a single memory hierarchy. An execution of the application is defined by a traversal the graph, that is, a schedule of the vertices which respects the dependencies (or topological order). The peak memory of a traversal is the maximum amount of memory needed to store application files/data at any given time throughout the application execution. The question we study in this work is: How should the task graph be traversed so as to minimize the peak memory? This can be seen as a variant of the minimum cut linear arrangement (MCLA) problem on directed acyclic graphs and is NP-complete [START_REF] Wu | Inapproximability of treewidth and related problems[END_REF]. Our focus is on a certain class of applications whose graphs are series-parallel; these applications have already receive some attention in the scheduling literature [START_REF] Cordasco | On scheduling series-parallel dags to maximize area[END_REF][START_REF] Finta | Scheduling uet-uct seriesparallel graphs on two processors[END_REF][START_REF] Monma | Sequencing with series-parallel precedence constraints[END_REF]. We propose a polynomial time algorithm for minimizing the peak memory of this class of task graphs on serial execution environments.

The problem of minimizing the peak memory is also important for parallel execution. While there is an abundant literature on parallel task graph scheduling (see [START_REF] Leung | Handbook of scheduling: algorithms, models, and performance analysis[END_REF] for a survey) where the objective is to minimize the total completion time, or makespan, there is little work in minimizing the peak memory. Although our focus in this paper is on the sequential execution case, these schedules can apply to parallel jobs, where each vertex of the task graph now is a parallel task. Also, our study establishes a theoretical ground needed to study parallel task graph scheduling mixing the makespan and the peak memory objectives in distributed memory systems (as we did for tree-shaped task graphs in previous work [START_REF] Eyraud-Dubois | Parallel scheduling of task trees with limited memory[END_REF]).

Liu [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF]18] investigates the peak memory minimization problem for trees, where the traversal is constrained to be a post-order [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF] or any topological order [18]. In the more general case, Liu makes use of a previous work by Yannakakis [START_REF] Yannakakis | A polynomial algorithm for the min-cut linear arrangement of trees[END_REF]. We, in return, are inspired by Liu's work [18] in designing the proposed algorithm for series-parallel graphs (SP-graphs). This way, we aim to contribute to the theoretical body of the known results for efficiently solvable instances of the peak memory problem. This paper is organized as follows. We briefly discuss previous work in Section 2. We present the problem formally in Section 2.1. We then describe the existing optimal algorithm for trees in Section 3, since this algorithm forms the basis of our proposed algorithms. In the same section, we present the principle of our algorithms on a subclass of SP-graphs. Then, Section 4 presents the proposed algorithm for general SP-graphs as well as the new notion on min-cut optimality needed to prove its correctness. Some of the arguments in our proofs are very lengthy and involved. For the sake of readability, the most demanding proofs are detailed in Appendix.

2 Problem definition and related work

Peak memory minimization: Model and objective

We define the problem in general directed acyclic graphs (DAGs) with vertex and edge weights modeling applications. In this model, a DAG G = (V, E, w n , w e ) contains a vertex for each task of the application and a directed edge (p, q) between two vertices if the task corresponding to the vertex q needs a data produced by the task corresponding to the vertex p. Each task in the graph may have several input data, some execution data (or program), and several output data. We denote by w e (p, q) ≥ 0 the weight of edge (p, q) which represents the size of the data produced by task p for task q, and by w n (p) ≥ 0 the weight of a vertex p which is the size of the execution data of task p.

During the execution of a task (vertex) p, the memory must contain its input data, the execution data, and its output data. The memory needed for executing p is thus: After p has been processed, its input and execution data are discarded, while its output data are kept in memory until they are consumed at the end of the execution of the corresponding tasks. For example, in the graph depicted in Figure 1a, if task A is processed first, 8 units of memory are needed for its processing, but only 4 remains in the memory after its completion. If task C is processed right after task A, 7 units of memory are needed during its processing (4 to store the data produced by A for B, and 3 for the execution and output data of C).

While processing the task graph, memory consumption changes as data are created and deleted. Our objective is to minimize the peak memory, i.e., the maximum amount of memory used in the graph traversal.

More formally, we define a schedule of the task graph as a total order π on the vertices, denoted with ≤ π , such that p ≤ π q means that vertex p is scheduled before vertex q. The precedence constraints of the task graphs impose that this is a topological order: we have p ≤ π q for any edge (p, q) ∈ E. We use the notation max π (resp. min π ) to express the maximum (resp. minimum) according to the order π: min π G is for instance the first vertex scheduled by π. A schedule is also represented as a list of vertices: 1, 2, 3 denotes the schedule π such that 1 ≤ π 2 ≤ π 3.

We define µ(p, π) as the memory required during the execution of a vertex p ∈ V under the schedule π as µ(p, π) = w n (p) + q≤πp≤πr {w e (q, r) : (q, r) ∈ E}.

Note that the edges (q, r) such that q ≤ π p ≤ π r correspond to the data that have been created

but not yet consume while p is being processed. The objective is to find a schedule π for a graph G that minimizes the peak memory, defined as

µ(π) = max p∈V µ(p, π).
Given a directed graph G = (V, E, w n , w e ), we define the reverse graph Ḡ = (V, Ē, w n , w e ) where the orientation of all edges is changed: Ē = {(j, i), (i, j) ∈ E}. Note that vertex and edge weights are kept unchanged. Given a schedule π of G, we may build the reverse schedule π such that q ≤ π p whenever p ≤ π q. It is straightforward to check that both schedules have the same peak memory on their respective graph: µ G (π) = µ Ḡ(π).

Inria

In this paper, we concentrate on series-parallel graphs, which are defined as follows (see for example [START_REF] Eppstein | Parallel recognition of series-parallel graphs[END_REF]). Definition 1. A two-terminal series-parallel graph, or SP-graph, G with terminals s and t is recursively defined to be either:

Base case: A graph with two vertices s and t, and an edge (s, t).

Series composition:

The series composition of two SP-graphs G 1 with terminals s 1 , t The vertices s and t are called source and target of the graph.

When the graph is defined this way, the dependencies are from the source vertices to the target vertices. Series-parallel graphs can be recognized and decomposed into a tree of series and parallel combination in linear time [START_REF] Valdes | The recognition of series parallel digraphs[END_REF].

While solving the peak memory minimization problem for sp-graphs, we will need a solution for a sub-family of sp-graphs, which are called fork-joins defined below. Definition 2. A chain is a two-terminal series-parallel graph obtained without using any parallel composition. A fork-join graph is a two-terminal series-parallel graph obtained by the unique parallel composition of a number of chains. These chains are called the branches of the fork-join graph.

A sample fork-join graph is shown in Fig. 2.

Related work

There have been several studies on graph traversals for minimizing the peak memory in the domain of numerical linear algebra, where the focus is on tree-shaped task graphs. The elimination tree is a graph theoretical model that represents the storage requirements, and computational dependencies and requirements in Cholesky and LU factorization of sparse matrices. Liu [START_REF] Joseph | The role of elimination trees in sparse factorization[END_REF] describes how such trees are built, and how the multifrontal method organizes the computations according to elimination trees. In this context, Liu [START_REF] Joseph | On the storage requirement in the out-of-core multifrontal method for sparse factorization[END_REF] discusses how to find a memory-minimizing postorder traversal when the traversal is required to correspond to a postorder traversal of the tree. In a follow-up study [18], an exact algorithm is shown to solve the problem without the postorder constraint on the traversal (see also [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF] for another algorithm). Memory minimization is still a concern in modern multifrontal solvers when dealing with large matrices. Among others, efforts have been made to design dynamic schedulers that takes into account dynamic pivoting (which impacts the weights of edges and vertices) when scheduling elimination trees with strong memory constraints [START_REF] Guermouche | Memory-based scheduling for a parallel multifrontal solver[END_REF], to consider both task and tree parallelism with memory constraints [START_REF] Agullo | Robust memory-aware mappings for parallel multifrontal factorizations[END_REF], and to incorporate out-of-core storage decisions [START_REF] Jacquelin | On optimal tree traversals for sparse matrix factorization[END_REF]. While these studies try to optimize memory management in existing parallel solvers, we aim at designing a simple model to study the fundamental underlying scheduling problem.

The problem of scheduling a task graph under memory constraints also appears in the processing of scientific workflows whose tasks require large I/O files. Such workflows arise in many scientific fields, such as image processing, genomics, and geophysical simulations. The problem of task graphs handling large data has been identified by Ramakrishnan et al. [START_REF] Ramakrishnan | Scheduling data-intensive workflows onto storage-constrained distributed resources[END_REF] who propose some simple heuristics. Surprisingly, in the context of quantum chemistry computations, Lam et al. [START_REF] Lam | Memory-optimal evaluation of expression trees involving large objects[END_REF] have recently rediscovered the algorithm of Liu [18].

On the more theoretical side, this work builds upon many papers that have addressed the pebble game and its variants. Scheduling a graph on one processor with the minimum amount of memory amounts to revisiting the I/O pebble game with pebbles of arbitrary sizes that must be loaded into main memory before firing (executing) the task. The pioneering work of Sethi and Ullman [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF] deals with a variant of the pebble game that translates into the simplest instance of our problem when all input/output files have weight 1, all execution files have weight 0 and the graph is a rooted tree, where the aim is to minimize the number of registers that are needed to compute an arithmetic expression. The problem of determining whether a general DAG can be executed with a given number of pebbles has been shown NP-complete by Sethi [START_REF] Sethi | Complete register allocation problems[END_REF] if no vertex is pebbled more than once (the general problem allowing recomputation, that is, re-pebbling a vertex which have been pebbled before, has been proven Pspace complete [START_REF] Gilbert | The pebbling problem is complete in polynomial space[END_REF]). However, this problem has a polynomial complexity for tree-shaped graphs [START_REF] Sethi | The generation of optimal code for arithmetic expressions[END_REF], where it corresponds to the MCLA problem for rooted trees. Yannakakis [START_REF] Yannakakis | A polynomial algorithm for the min-cut linear arrangement of trees[END_REF] deals with the MCLA problem for (unrooted) trees where the objective is to minimize the number of edges cut, while Monien et al. [START_REF] Monien | Min cut is NP-complete for edge weighted trees[END_REF] show that the problem becomes NP-complete in the presence of edge weights.

The work of Blumofe and Leiserson [START_REF] Blumofe | Space-efficient scheduling of multithreaded computations[END_REF] provided the foundations for many studies on multithreaded computations [1,[START_REF] Blelloch | Provably efficient scheduling for languages with fine-grained parallelism[END_REF][START_REF] Girija | Scheduling threads for low space requirement and good locality[END_REF]; leading to implementation of compilers for multithreaded parallel computing [4]. Similarly to the series-parallel graphs studied in the present paper, they focus on structured computations which are special classes of DAGs, some of them being close to series-parallel graphs. However, these works are less closely related to the present paper, since most of their effort are devoted to reducing the impact of parallelism on memory. The usual goal is to guarantee that the increase in memory needed for a parallel execution will be limited compared to the memory required by a sequential depth first search traversal of the graph.

Solving the peak memory problem on trees and fork-join graphs

We first recall Liu's algorithm [18] for solving the peak memory minimization problem on trees. We then propose its adaptation for a subclass of series-parallel graphs. The algorithm proposed by Liu applies to in-trees, that is trees whose dependencies are directed towards the root (contrarily to out-trees, where dependencies are directed towards leaves). Note that if T is an in-tree and π is the schedule of T computed by Liu's algorithm, then π is also a peak memory minimizing schedule of the out-tree T .

Liu's algorithm for trees

Liu [18] proposes an algorithm to find an optimal tree traversal for peak memory minimization. We present this algorithm as it serves as a basis of our strategies for fork-join and general seriesparallel graphs. Liu's original work concerns a different model where there is no edge weights (there are only vertex weights). We present here its immediate adaptation to our model. Liu's algorithm is shown in Algorithm 1. To compute an optimal traversal for a tree rooted at vertex k, it first recursively computes an optimal traversal for the subtrees rooted at each of its children, then merges them and finally adds the root at the end. The difficult part is of course how to merge the children traversals. There is no reason to process the subtrees one after the other, and an optimal solution may interleave the processing on one subtree with that of the Require: T = (V, E, w n , w e ): tree with vertex-and edge-weights.

Ensure: π: Schedule with the minimum peak memory µ(π) Base case if V = {u} then return u

General case Let r be the root of T and T 1 , T 2 , . . . , T k its subtrees

for i = 1 to k do π i ← Liu-Tree-Schedule(T i )
Compute the hill-valleys segments of T i in schedule π i Sort all segments of all subtrees in non-increasing (hill -valley) value Based on this segments o, order the vertices in each segment consecutively, followed by the root r, to build π others. Liu makes the observation that in an optimal traversal the switching points between the subtrees' processing have to be local minima in the memory profile: while processing one subtree T i , there is no reason to switch to T j if one can reduce the memory needed for T i by processing one more task in T i . This remark leads to slicing the traversal into atomic parts, called segments. The end-points of segments (which are local minima in the memory profile) are called valleys, while the peak memory vertices of each segment are called hills. The memory occupation at valleys and hills are denoted by M v and M h and are defined as follows, for a given traversal:

• M h 1 is the peak memory of the whole traversal; • M v i is the minimum amount of memory occurring after the step when

M h i is (last) attained, for i ≥ 1 • M h
i is the peak memory after the step when M v i-1 is (last) attained, for i ≥ 2. The sequence of hill-valley ends when the last vertex is reached. The segments consist of the vertices comprised between two valleys. For example, for the tree depicted in Figure 1a, consider the traversal (A, B, C, D, E) of the subtree rooted in E. The memory occupation during and after the processing of the tasks and the segments that are deduced from this memory profile are illustrated in Figure 1c. Simarly, the segments of the traversal (F, G) of the subtree rooted in G are detailed on Figure 1d.

To merge the traversals of the subtrees, the first step is to compute all hill-valley segments. Then the lists of segments are merged using the following criterion: if several segments are available (one for each subtree in the beginning), it is always beneficial to start with the segment with the maximum (hill -valley) difference. Intuitively, the residual memory will only increase when processing segments, so it is better (i) to start with the segment with larger peak memory (hill) to avoid large memory consumption later, and (ii) to start with the segment with smaller residual memory (valley) to ensure an increase of memory as small as possible.

In the example of Figure 1, when merging the traversals from the subtrees rooted at E and G at the vertex H, we start by comparing the first segments of each subtree: segment (F ) is selected because it has a larger (hill -valley) value of 9 -1 = 8. This segment is ordered, and then removed from the segments list, and we proceed by comparing segments (A, B) and (G): (A, B) has larger (hill -valley) value of 8 -1 = 7, so it is selected. By iterating this process, we end up with the following ordering: (F ), (A, B), (C, D, E), (G). The last step is to add the root H of the subtree to the traversal.

Liu proves that Algorithm 1 is correct and its worst-case runtime complexity is O(n 2 ). We note that even if this algorithm is designed for in-trees, we can compute an optimal schedule of an out-tree by reversing all edges to obtain an in-tree, applying this algorithm, and then reversing the obtained schedule.

Algorithm for fork-join graphs

The main idea (summarized in Fig 2) is to remove one edge from each branch, so as to disconnect the graph into one out-tree (the part S in the figure) and one in-tree (the part T in the figure). Then, we can reuse Liu's algorithm to compute an optimal traversal for these two trees. The following lemma states that if the removed edges are of minimal weight in each branch, it is possible to first schedule all the vertices that are before this minimal cut, and then all the vertices after the cut, without increasing the peak memory. This intuitive result can be proved by using Theorem 2, Corollary 1 and Theorem 1 given below. We do not formalize the proof, since the objective of this section is to give an intuition on the algorithm for general sp-graphs.

Thanks to this result, we know that there exists an optimal schedule which ordered first vertices from S, and then vertices from T . Assume for a moment that the weight of all e min i edges is zero (w e (e min i ) = 0). Then, it is as if the graph was disconnected, and we have two separate trees to schedule. T is an in-tree, and Liu's algorithm can compute an optimal schedule π for it. S is an out-tree, so that S is an in-tree: if γ is the optimal schedule computed by Liu's algorithm for S, γ is optimal for S. Then, γ, π is an optimal schedule of the whole graph. This approach can be generalized to fork-join graphs with non-zero weights on the minimal edges, as stated in Algorithm 2. We will prove that this algorithm computes an optimal schedule of all fork-join graphs (Theorem 8).

Algorithm 2 Fork-Join-Schedule(T )

Require: F J = (V, E, w n , w e ): fork-join graph with vertex-and edge-weights. Ensure: π: Schedule with minimal peak memory µ(π)

Let B 1 , . . . , B q be the branches of F J for i = 1 to q do Let e min Consider the two trees T out , T in made by disconnecting F J Let T out be the in-tree obtained by reversing all edges in

T out π 1 ← Liu-Tree-Schedule( T out ) π 2 ← Liu-Tree-Schedule(T in ) return π 1 , π 2

Solving the peak memory problem for series-parallel graphs

In this section, we present our main contribution: a polynomial time algorithm to compute a peak memory minimizing schedule of series-parallel graphs. In order to prove the correctness of the proposed algorithm, we rely one a new graph model, and new metrics. We first present the new model (Section 4.1), then introduce a new relation on schedules and a new objective (Sections 4.2 and 4.3). Next we present our algorithm and the (sketch of) proof of optimality (Sections 4.4 and 4.5). For the sake of readability, some of the detailed proofs are given in the Appendix.

A simpler model with only vertex weights

We introduce here a new task-graph model, called the cumulative weight model, which has only vertex weights (no edge weights). Formally, let G = (V, E, ω), where ω : V → Z is a weight function on the vertices. For a given set U ⊆ V of vertices, ω(U ) denotes the sum of weights of vertices in U , i.e., ω(U ) = v∈U ω(v). The vertex-weight function ω should satisfy ω(G) = 0.

Let π be a schedule and for each vertex v, consider the cumulative sum of the weighs of all vertices scheduled before v:

Σ(v, π) = ω({u ≤ π v}). (1)
We define the cutwidth ρ(π) of a schedule π as the maximum of all these sums:

ρ(π) = max p∈G ω({q ≤ π p}) = max p∈G Σ(p, π). (2)
Below (Theorem 1), we show that by minimizing the cutwidth in the cumulative weight model, one can minimize the peak memory in the original model. For this purpose we need some definitions. Given an instance G = (V, E, w n , w e ) of the peak memory problem, we construct an instance of the cumulative weight problem, with a (directed) bipartite graph G B = (V B , E B , ω) as follows. For each vertex p ∈ V , we introduce a pair of vertices p start , p stop ∈ V B such that (p start , p stop ) ∈ E B . The vertex p start represents the beginning of the computation corresponding to the task p, while p stop represents the end of this computation. For each edge (p, q) ∈ E, we add an edge (p stop , q start ) ∈ E B . For each vertex p, we set

ω(p start ) = w n (p) + (p,r)∈E w e (p, r), (3)
to represent the allocation of temporary and output data in the memory at the beginning of the task p, and

ω(p stop ) = -w n (p) - (q,p)∈E w e (q, p), (4)
to represent the deallocation of temporary and input data from the memory at the end of the task p. Note that with these definitions ω(G B ) = 0. Let π B be a schedule of G B . It is easy to see that a schedule can be constructed for G using the order of "stop" vertices in π B . Given π B , let π be a schedule of G such that p ≤ π q whenever p stop ≤ π B ≤ q stop . Observe that (v stop , π B ) = x≤πv<πy w e (x, y), that is the cumulative weight of v stop corresponds to the weight of the edges (in G) which are cut by an imaginary line just after v under the schedule π. We now show how minimizing the cutwidth in G B minimizes the peak memory in G.

Inria

Theorem 1. Let π B be a schedule of G B whose cutwidth ρ(π B ) is minimum for G B and π be the corresponding schedule of G. Then, µ(π) is the minimum peak memory for G.

Proof. We provide the big lines of the proof by using lemmas proved in Appendix A. By Lemma A.4, we can assume without loss of generality that p start and p stop are consecutive for all p in π B . This implies that µ(π) = ρ(π B ) by Lemma A.3. Suppose for the sake of contradiction that µ(π) is not minimum. In other words, there is a schedule γ of G where µ(γ) < µ(π). Then, we can construct γ B for G B from γ by replacing each vertex p with p start and p stop . By Lemma A.3 again, µ(γ) = ρ(γ B ) and hence ρ(γ B ) < ρ(π B ), a contradiction.

A new relation on schedules

We present here a relation on schedules that allows to compare them. We show that this relation subsumes the comparison using the cutwidth: a schedule minimum for this relation has a minimum cutwidth. This relation extends the partial orders introduced by Liu on pebble cost sequences for trees [18].

Definition of the relation on schedules

Given a directed graph G, two vertices p and q of G, and two schedules π and γ of G, we say that the schedule π at p dominates the schedule γ at q (and we write p → π γ q) if and only if C1. Σ(p, π) ≤ Σ(q, γ), and

C2. min{Σ(s, π) : s ≥ π p} ≤ min{Σ(r, γ) : r ≥ γ q}.
Note that the second condition (C2) is equivalent to that for any r ≥ γ q, there exists s ≥ π p such that Σ(s, π) ≤ Σ(r, γ). Now, we define the relation on the set of schedules for G as follows.

Definition 3 (Relation ). Let π and γ be two schedules of G. We say that π γ for G, if for each p ∈ G, there is a vertex q ∈ G such that p → π γ q. Contrarily to the relation ≺ introduced by Liu on pebble cost sequences [18], our relation is not a partial order, as it is not anti-symmetric. However, we are able to prove that it is reflexive and transitive, and thus is a preorder. Lemma 2. The relation is a preorder (reflexive and transitive).

Proof. We need to show that the relation is both reflexive and transitive. Let α, β, and θ be schedules of G.

(i) Reflexivity. Since p → α α p for each p ∈ V , α α, and thus, is reflexive. (ii) Transitivity. Assume that α β and β θ. Take any p ∈ G. Let v and q be such that p → α β v and v → β θ q. We claim that p → α θ q, as well. There are two conditions we should examine.

1) (C1). This follows as Σ(p, α) ≤ Σ(v, β) and Σ(v, β) ≤ Σ(q, θ), due to the first conditions of p → α β v and v → β θ q. 2) (C2). Take any vertex r ≥ θ q. Then, there exists s ≥ α p and w ≥ β v such that Σ(s, α) ≤ Σ(w, β) ≤ Σ(r, θ), as a consequence of the second conditions of p → α β v and v → β θ q.

Properties of the relation on schedules

We now describe a few properties on the preorder , and especially its connection with the reverse of a graph. We recall and extend the notion of reverse graph from Section 2.1 to the vertex-weighted model: given a graph G = (V, E, ω), its reverse graph Ḡ = (V, Ē, ω) has the same set of vertices as G, however all edges are reversed Ē = {(q, p) : (p, q) ∈ E} and all vertex weights take the opposite sign of their value in G: ω(p) = -ω(p) for any p ∈ V . The reverse of a schedule π is defined as in Section 2.1: q ≤ π p whenever p ≤ π q, for any pair of vertices p, q.

Lemma 3. For any vertex p ∈ G, we have

Σ(p, π) -Σ(p, π) = ω(p), (5)
where Σ(p, π) and Σ(p, π) are defined over G and Ḡ, respectively.

Proof. Notice that {q ≤ π p} = {q ≥ π p} due to the definition above. Recall that ω(G) = 0, and thus ω( Ḡ) = -ω(G) = 0. Then,

Σ(p, π) = ω({q ≤ π p}) = ω({q ≥ π p}) = ω( Ḡ) -ω({q < π p}) = -ω({q < π p}) = ω({q < π p}) = Σ(p, π) -ω(p). Lemma 4. For any schedule π of G, ρ(π) = ρ(π).
Proof. Let p * be a vertex such that ρ(π) = Σ(p * , π) and q be its predecessor under π. Then,

ρ(π) ≥ Σ(q, π) = Σ(p * , π) -ω(p * )
holds by the definitions (1) and (1)

= Σ(p * , π) by Equation (5) = ρ(π).
By noting that the roles of π and π can be changed in the above lines, we obtain ρ(π) ≥ ρ(π) and hence the equality ρ(π) = ρ(π).

The last property on the relations shows that it implies a comparison on the cutwidth, not only for the schedules being compared but also for their reverse. Lemma 5. If π γ then ρ(π) ≤ ρ(γ) and ρ(π) ≤ ρ(γ).

Proof. Assume that π γ. Then for any p ∈ V , there exists q ∈ V such that p → π γ q, and thus, Σ(p, π) ≤ Σ(q, γ). Then, by definition, ρ(π) ≤ ρ(γ). Moreover, thanks to Lemma 4, we have

ρ(γ) = ρ(γ) ≥ ρ(π) = ρ(π).

Min-cut optimality

We are now ready to present the central notion needed to provide an optimal algorithm for series-parallel graphs, namely the min-cut optimality. We show that a min-cut optimal schedule is also cutwidth optimal.

Definition of min-cut optimality

Min-cut optimality is based on the classical notion of cut in a graph: a cut (S, T ) of G is defined as a bisection of its vertices into two nonempty sets S and T . We say that a cut is topological if there exists no edge (p, q) ∈ E such that p ∈ T and q ∈ S (or equivalently, for any edge (p, q) ∈ E, we have either p ∈ S or q ∈ T ). The width of a topological cut (S, T ) is defined as c(S, T ) = ω(S).

Consider a topological cut (S, T ) and a schedule π. If in π all vertices of S appear before all vertices of T , that is, for p ∈ S and q ∈ T , we have p ≤ π q, then we say that π is in compliance with (S, T ). In this case, we have

c(S, T ) = Σ(p * , π), where p * = max π S. (6)
We say that a topological cut (S, T ) is minimum, or a min-ω-cut, if its width is minimum, that is, c(S, T ) = min{c(S , T ) where (S , T ) is a topological cut}.

We define by G[S] the subgraph of G which contains only the vertices in S and the edges between these vertices. Similarly, for any schedule π of G, π[S] is the schedule induced by π on G[S].

Definition 4 (Min-cut optimality). Let (S, T ) be a minimum topological cut. A schedule π is cut-optimal with (S, T ), if π is in compliance with (S, T ), π[S] is minimal for on Ḡ[S], and

π[T ] is minimal for on G[T ]. Furthermore, π is called min-cut optimal if π is cut-optimal with some min-ω-cut of G.
We now state a simple lemma which will be useful in the following. Lemma 6. Let π be a schedule of G. Let (S, T ) be any minimum topological cut of G. Then, c(S, T ) ≤ Σ(p, π), for any p < π max π G.

Proof. Take any p < π max π G. Then suppose for the sake of contradiction that Σ(p, π) < c(S, T ). Consider the topological cut (S p , T p ), where S p = {v ≤ π p}. Then, by [START_REF] Cordasco | Assessing the computational benefits of area-oriented dag-scheduling[END_REF], wehavec(S p , T p ) = ω(S p ) = Σ(p, π) < c(S, T ), which contradicts that c(S, T ) is minimum.

Properties of min-cut optimality

We present two important properties of min-ω-cuts.

The first property is that transforming a schedule so that it is in compliance with a min-ω-cut will not make it larger in the sense of the preorder (and thus, thanks to Lemma 5, will not increase its cutwidth). This is shown in the next theorem. Proof. Since (S, T ) is a topological cut of G, π is a schedule of G. Note that γ may not be in compliance with (S, T ).

The proof relies on the two following properties: for each p ∈ G, p → π γ p (which proves that π γ according to the definition of this relation) and p → π γ p (which proves π γ). We only provide the proof of the first property, as the second one can be proved using the very same arguments.

Let s + be the last scheduled vertex of S in γ. Similarly, let t -be the first scheduled vertex of T in γ. Formally, s + = max γ S, t -= min γ T.

Note that s + is also the last scheduled vertex of S in π (and t -the first scheduled vertex of T in π) and Σ(s + , π) = c(S, T ).

To prove that p → π γ p for p ∈ G, we investigate Σ(p, π) and Σ(p, γ). First, for any p ∈ V , we consider s p (respectively t p ), the last scheduled vertex of S (resp. of T ) that does not come after p in γ:

s p = max γ {s ∈ S, s ≤ γ p}, t p = max γ {t ∈ T, t ≤ γ p}.
Note that s p is always defined since G has a single source vertex. However, t p may not be defined, as the set {t ∈ T, t ≤ γ p} may be empty, which occurs when p ∈ S and p comes before t -in γ; in this case p = s p . If t p is defined, we have:

Σ(p, γ) = Σ(s p , γ[S]) + Σ(t p , γ[T ]) = Σ(s p , π[S]) + Σ(t p , π[T ]) = Σ(s p , π) + Σ(t p , π) -Σ(s + , π) = Σ(s p , π) + Σ(t p , π) -c(S, T ). (7)
As a result,

Σ(p, γ) = Σ(p, π) if t p is not defined, Σ(t p , π) + Σ(s p , π) -c(S, T ) otherwise (8)
We are now ready to show p → π γ p, for any p ∈ V . We verify the two conditions defining this statement given in Section 4.2.1 for any p ∈ V , as follows.

1. The first condition to verify is C1: Σ(p, π) ≤ Σ(p, γ). When t p is not defined, this condition directly derives from Equation [START_REF] Eppstein | Parallel recognition of series-parallel graphs[END_REF]. Consider now that t p is defined. We consider two cases depending on which side of the cut p lies:

(a) (p ∈ S). Then, s p = p. This implies

Σ(p, γ) = Σ(p, π) + Σ(t p , π) -c(S, T ).
Note that t p < γ p < γ max γ G, since p ∈ S. Since Σ(t p , π) ≥ c(S, T ) by Lemma 6, the condition C1 is met.

(b) (p ∈ T ). Then, t p = p. This implies

Σ(p, γ) = Σ(p, π) + Σ(s p , π) -c(S, T ).
Note that s p < γ max γ G, since s p ∈ S. Since Σ(s p , π) ≥ c(S, T ) by Lemma 6, the condition C1 is met.

2. The second condition to verify (C2) writes min{Σ(s, π) : s ≥ π p} ≤ min{Σ(r, γ) : r ≥ γ p} (or equivalently, for any r ≥ γ p, there exists s ≥ π p such that Σ(s, π) ≤ Σ(r, γ)). First, note that the last vertex is the same in both schedules: r = max π G = max γ G and thus Σ(r, π) = Σ(r, γ). Now, consider any r ≥ γ p such that r < γ max γ G. We consider the two following cases:

Inria a) p is in S. Then, Σ(s + , π) = c(S, T ) ≤ Σ(r, γ) and s + ≥ π p. b) p is in T . Let t r = max γ {t ∈ T, t ≤ γ r}.
Note that t r is well defined, since r ≥ γ p. We also have t r ≥ γ p. Then, by Equation [START_REF] Cordasco | On scheduling series-parallel dags to maximize area[END_REF],

Σ(r, γ) = Σ(s r , π) + Σ(t r , π) -c(S, T ).
Since Σ(s r , π) ≥ c(S, T ) by Lemma 6, we have Σ(t r , π) ≤ Σ(r, γ). Notice that t r ≥ π p since t r ≥ γ p, and, both p ∈ T and t r ∈ T .

The following property of min-ω-cuts gives the full importance of min-cut optimality. It states that, for a schedule π, being min-cut optimal implies optimality for the relation both for π and its reverse π.

Theorem 3. Let G be a directed acyclic graph with a single source vertex and a single sink vertex, and π be a min-cut optimal schedule of G. Then, π is minimal for on G and π is minimal for on Ḡ.

Proof. Consider a directed acyclic graph G with single source and sink vertices, and a min-cut optimal schedule π. Since π is min-cut optimal, π is cut-optimal with some min-ω-cut (S, T ). Take any schedule λ of G, and consider the schedule γ = λ[S], λ[T ] , which is in compliance with (S, T ). We have γ λ and γ λ by Theorem 2. Here, we only show π γ for G (which induces π λ), as with similar arguments one can also show π γ (which induces π λ).

By the definition of a min-cut optimal schedule, π[S] (respectively π[T ]) is minimal for on S (resp. on T ), thus π[S] γ[S] and π[T ] γ[T ]. We show that for any vertex p ∈ V , there is a vertex q ∈ V such that p → π γ q. We consider a vertex p ∈ V and distinguish two cases depending where p lies:

1. (p ∈ S). Let q be such that Σ(q, γ[S]) = ρ(γ[S]). We show p → π γ q by examining the two conditions.

(a) (C1:

Σ(p, π) ≤ Σ(q, γ)). Since π[S] γ[S], by Corollary 1 we have ρ(π[S]) ≤ ρ(γ[S]).
Hence,

Σ(p, π) ≤ ρ(π[S]) ≤ ρ(γ[S]) = Σ(q, γ).
(b) (C2: min{Σ(s, π) : s ≥ π p} ≤ min{Σ(r, γ) : r ≥ γ q}). Let t be the sink vertex. Note that Σ(t, π) ≤ Σ(t, γ) and t ≥ π p. Take any r ≥ γ q and r < γ t. For s + = max π {s ∈ S}, we have Σ(s + , π) = c(S, T ) ≤ Σ(r, γ). Notice that s + ≥ π p, as p ∈ S.

(p ∈ T ).

Let q be such that p

→ π[T ] γ[T ] q; such a q exists, because π[T ] γ[T ]. We show p →
π γ q by examining the two conditions:

(a) (C1: Σ(p, π) ≤ Σ(q, γ)). It holds that

Σ(p, π) = Σ(p, π[T ]) + Σ(s + , π[S]) (9)
≤ Σ(q, γ[T ]) + Σ(s + , π[S]) (10)
= Σ(q, γ[T ]) + Σ(s + , γ[S]) = Σ(q, γ). (11)
Equations ( 9) and ( 11) come from the fact that π and γ are in compliance with (S, T ). Equation ( 10) is derived from (9) and p

→ π[T ] γ[T ] q.
(b) (C2: min{Σ(s, π) : s ≥ π p} ≤ min{Σ(r, γ) : r ≥ γ q}). Take any r ≥ γ q. Then, there exists s ≥ π p such that Σ(s, π[T ]) ≤ Σ(r, γ[T ]). Then,

Σ(s, π) = Σ(s, π[T ]) + Σ(s + , π[S]) ≤ Σ(r, γ[T ]) + Σ(s + , π[S]) = Σ(r, γ[T ]) + Σ(s + , γ[S]) = Σ(r, γ).
Note that the previous two theorems only apply to directed graphs with a single source and a single sink, and thus in particular to series-parallel graphs. However, it is easy to transform any directed graph so that it obeys these conditions: simply add two zero-weight artificial vertices, one for the source and one for the sink, connect all sources of the original graph to the new source, and connect the new sink to all original sinks.

Algorithm for general series-parallel graphs

We present here our main contribution, which is a recursive algorithm, called SP-Schedule, that computes a min-cut optimal schedule for a series-parallel graph G in the vertex-weighted model. As presented before, this means that the computed schedule is cut-optimal with some min-ω-cut (S, T ) and implies that it also minimizes the cutwidth. The algorithm also outputs this (S, T ) cut. We consider here series-parallel graphs as defined in Definition 1, with only vertex weights in accordance with the cumulative weight model presented in Section 4.1.

This algorithm relies on an algorithm to compute a min-cut optimal schedule of a fork-join graph, FJ-Schedule which is presented below. This algorithm for fork-join graphs is similar to Algorithm 2, but applies to our new cumulative weight model. Likewise, this latter algorithm relies on an algorithm for trees, Tree-Schedule, which is the translation of Liu's algorithm for the cumulative weight model.

The base case of the algorithm considers a series-parallel graph with a single edge, and outputs the unique schedule along with the unique topological cut.

In the general case, G is a series or parallel composition of two smaller series-parallel graphs G 1 and G 2 . We first recursively compute schedules π 1 and π 2 that are cut-optimal with topological cuts (S 1 , T 1 ) and (S 2 , T 2 ) for G 1 and G 2 .

If G is a series composition, the final schedule is obtained through a simple concatenation of π 1 and π 2 . This schedule of G is cut-optimal with both topological cuts induced by (S 1 , T 1 ) and (S 2 , T 2 ) on G. Thus, we select the one with lower cutwidth as it is a min-ω-cut of G. Therefore, π is a min-cut-optimal schedule of G.

In case of parallel composition, we transform each subgraphs G 1 and G 2 into a chain using Linearize, based on schedules π 1 and π 2 , respectively: G1 (resp. G2 ) is a chain with the same vertices as G 1 (resp. G 2 ) such that its unique topological order is π 1 (resp. π 2 ). The graph obtained by replacing G 1 and G 2 by G1 and G2 is a fork-join graph with two branches. We consider the topological-cut (S, T ) obtained by unifying the min-ω-cuts of G 1 and G 2 : as we will prove later, it is a min-ω-cut of the fork-join graph, but also of the original graph. We then call the routine FJ-Schedule which finds a schedule π that is cut-optimal with this particular topological cut (S, T ).

Algorithm 4 presents FJ-Schedule, which computes a schedule π that is cut-optimal with the given min-ω-cut (S, T ) for a given fork-join graph G. The algorithm simply divides the fork-join graph into two trees according to (S, T ). These trees have a special property: a subtree rooted at every vertex but the root itself has a non-negative total weight. This property follows

G is series or parallel comb. of G 1 and G 2 [π 1 , (S 1 , T 1 )] ← SP-Schedule(G 1 ) [π 2 , (S 2 , T 2 )] ← SP-Schedule(G 2 ) Series Composition if G = G 1 , G 2 then (S, T ) ← min{(S 1 , T 1 ∪ G 2 ), (G 1 ∪ S 2 , T 2 )} return [ π 1 , π 2 , (S, T )] Parallel Composition if G = {G 1 , G 2 } then G 1 ← Linearize(G 1 , π 1 ) G 2 ← Linearize(G 2 , π 2 ) (S, T ) ← (S 1 ∪ S 2 , T 1 ∪ T 2 ) π ← FJ-Schedule( G 1 ∪ G 2 , (S, T )) return [π, (S, T )]
Algorithm 4 FJ-Schedule(G, (S, T ))

Require: G = (V, E, ω): fork-join directed graph. Require: (S, T ): Min-ω-cut of G. Ensure: π: Schedule σ ← Tree-Schedule( Ḡ[S]) τ ← Tree-Schedule(G[T ]) return σ, τ
from the fact that (S, T ) is a min-ω-cut of G. The algorithm then schedules the two trees independently using Tree-Schedule routine, which is a translation of Liu's optimal algorithm for trees for the cumulative weight model, and can be found as Algorithm D.1 in Appendix D.

Correctness of the algorithm

We prove here that SP-Schedule computes a schedule which minimizes the cutwidth (and therefore, thanks to Theorem 1, it also minimizes peak memory). This result is expressed in Theorem 4.

Theorem 4 (Main Theorem). For any series-parallel graph, SP-Schedule computes a schedule π such the cutwidth of π is optimal.

Theorem 4 is easily proved below once the following theorem is proved.

Theorem 5. For any series-parallel graph, SP-Schedule computes a schedule π and a min-ωcut cut (S, T ) such that π is min-cut optimal with (S, T ).

The proof of Theorem 5 is decomposed into several steps, following the different cases in the algorithm. These steps are formalized through the following three theorems.

The first step deals with the series composition. The following theorem states that concatenating two min-cut optimal schedules for the subgraphs leads to a min-cut optimal schedule of their series composition. Theorem 6. Let G 1 and G 2 be two series-parallel directed graphs. Let π 1 and π 2 each be a min-cut-optimal schedule of G 1 and G 2 , respectively. Then, π = π 1 , π 2 is a min-cut-optimal schedule of their series composition

G = G 1 , G 2 .
Proof. The statement follows as a corollary the Lemma B.1 in Appendix B.

The second step deals with the parallel composition. The next theorem states that if we have a min-ω-cut of a series-parallel directed graph and an optimal schedule of each part of this directed graph, then there is an optimal schedule of the whole graph which induces theses two schedules. This theorem is used to compare the schedule returned by SP-Schedule with an optimal one and show that it is indeed optimal itself. Theorem 7. Let G 1 and G 2 be two series-parallel directed graphs, and G = {G 1 , G 2 } be their parallel composition. Let (S, T ) be a min-ω-cut of G, and π 1 and π 2 be schedules that are cutoptimal with the topological cuts induced by (S, T ) on G 1 and G 2 , respectively. For each schedule γ in compliance with (S, T ) of G, there is a schedule π in compliance with (S, T ) of G such that

(i) π induces π 1 and π 2 , (ii) π[S] γ[S] and π[T ] γ[T ]. Proof. See Appendix C.
The final step is to prove that the FJ-Schedule algorithm used to process fork-join graphs produces a min-cut optimal schedule compatible with the provided cut. Theorem 8. For any fork-join graph G and any min-ω-cut (S, T ) of G, FJ-Schedule computes a schedule π that is cut-optimal with (S, T ).

Proof. See Appendix D.

Inria

We are now ready to prove the main theorem by proving Theorem 5.

Proof of Theorem 5. The proof is by induction on the number of edges of G. In the base case, G has a single edge, that connects the source to the sinks. There is a unique schedule of G, which is also cut-optimal with the unique topological cut.

We now assume that the theorem holds for any series-parallel graph with fewer than k edges, where k > 1, and consider a series-parallel graph G with exactly k edges. G is made by the (series or parallel) composition of two series-parallel graphs G 1 and G 2 . Both subgraphs have fewer than k edges, thus by induction hypothesis, the recursive calls to SP-Schedule produce two min-cut-optimal schedules π 1 and π 2 together with their respective min-ω-cuts (S 1 , T 1 ) and (S 2 , T 2 ). We now distinguish between the two possible compositions.

Series composition Theorem 6 shows that the schedule π = π 1 , π 2 computed by SP-Schedule is a min-cut-optimal schedule of G. Besides a min-ω-cut of G can simply be found by selecting one of the min-ω-cut of G 1 and G 2 with minimal cutwidth.

Parallel composition Now, we consider that G = {G 1 , G 2 }. The algorithm first compute the cut (S, T ) such that S = S 1 ∪ S 2 and T = T 1 ∪ T 2 . We first prove that (S, T ) is a min-ω-cut of G. For the sake of contradiction assume the contrary. It means that there exists a topological cut (S * , T * ) such that c(S * , T * ) < c(S, T ). Let (S * 1 , T * 1 ) and (S * 2 , T * 2 ) be the topological cuts induced by (S * , T * ) on G 1 and G 2 , respectively. Then,

c(S * 1 , T * 1 ) + c(S * 2 , T * 2 ) = c(S * , T * ) < c(S, T ) = c(S 1 , T 1 ) + c(S 2 , T 2 ).
This implies c(S * 1 , T * 1 ) < c(S 1 , T 1 ) or c(S * 2 , T * 2 ) < c(S 2 , T 2 ), which is a contradiction as (S 1 , T 1 ) and (S 2 , T 2 ) both are min-ω-cuts.

In the case of a parallel composition, the algorithm computes the chain graph G 1 (respectively G 2 ) by sequencing the vertices of G 1 (resp. G 2 ) in the order of π 1 (resp. π 2 ) and calls FJ-Schedule on the fork-join graph G made by the parallel composition of G 1 and G 2 and the cut (S, T ). Thanks to Theorem 8, we know that FJ-Schedule outputs a schedule π cut-optimal with (S, T ). Thus, for any schedule γ of G in compliance with (S, T ), we have

π[S] γ[S], and π[T ] γ[T ]. (12)
We now show that π is cut-optimal with (S, T ) for G as well, that is, the previous inequalities also holds for any schedule γ of G in compliance with (S, T ). We consider such a schedule γ. Theorem 7 proves that there exists a schedule π * that (i) induces π 1 and π 2 , (ii) π * is in compliance with (S, T ), and (iii)

π * [S] γ[S], and π * [T ] γ[T ]. ( 13
)
As π * induces π 1 and π 2 , π * is a valid schedule of G, we may thus apply Equation ( 12) to γ = π * . Combining it with Equation ( 13), we get

π[S] π * [S] γ[S], and π[T ] π * [T ] γ[T ].

As is a preorder, it is transitive, and we have π[S] γ[S] and π[T ] γ[T ].

Proof of the Main Theorem 4. SP-Schedule computes a schedule π and a min-ω-cut such that π is min-cut optimal with the found cut (see Theorem 5). Theorem 3 implies that π is also minimal for the relation, which in turn means that π minimizes the cutwidth ρ(π) due to Corollary 1.

Algorithm complexity

The FJ-Schedule algorithm calls twice Liu's algorithm for trees, whose worst-case complexity for an input of size n is a O(n 2 ). Except for the recursive calls, this is the most costly step of the SP-Schedule. Since there are at most O(n) recursive calls, the overal worst-case complexity of SP-Schedule is O(n 3 ).

Conclusion

In this paper, we have proposed an algorithm to schedule a series-parallel task graph with the minimum peak memory. To prove the correctness of the algorithm, we have introduced a new and simpler model, based on a vertex-weighted graph. We have shown how to simulate task graphs with weights on vertices and edges using the new model. The proof of the proposed algorithm is complex, and consists in an extension of Liu's work on trees [18].

The use of the proposed algorithm is limited to task graphs structured as series-parallel computations, which constitues an important class of scientific computing applications. However, this algorithm may be applied to general graphs, if we first transform them into series-parallel graphs, for example using the SP-ization process [START_REF] González-Escribano | Mapping unstructured applications into nested parallelism[END_REF], which is also suggested in the literature [START_REF] Cordasco | Assessing the computational benefits of area-oriented dag-scheduling[END_REF]. This will lead to suboptimal schedules, because some fictitious edges are added to a graph when it is turned into a series-parallel graph. Future research directions include looking for optimal schedules for other regular graph structures that appear in scientific computing (such as 2D or 3D meshes), and for graphs made as a combination of these regular structures. w e (q, r) -r<πp q≤πr w e (q, r)

= ω(p start ) + v<πp (ω(v start ) -w n (v)) - v<πp (-ω(v stop ) -w n (v)) = ω(p start ) + v<πp (ω(v start ) -w n (v) + ω(v stop ) + w n (v)) = ω(p start ) + v<πp (ω(v start ) + ω(v stop )).
Lemma A.3. Let π B be a schedule of G B such that p start and p stop are consecutive in π B , for each p ∈ G. Consider the schedule π of G such that p ≤ π q whenever p stop ≤ π B q stop . Then, µ(π) = ρ(π B ).

Proof. As p start and p stop are consecutive in π B , for each p ∈ G, we have

Σ(p start , π B ) = ω(p start ) + v<πp (ω(v start ) + ω(v stop ))
and, due to Lemma A.2, Σ(p start , π B ) = µ(p, π), for any p ∈ G. We consider the vertex p which reaches the cutwidth of π B , as defined by Lemma A.1:

ρ(π B ) = Σ(p start * , π B ). Then, ρ(π B ) = Σ(p start , π B ) = µ(p, π) ≤ µ(π). (A.1)
Let q ∈ G be such that µ(π) = µ(q, π). Then, Proof. Let p ∈ G be such that p start and p stop are not consecutive in π B . We construct a schedule π B from π B , where p start is placed right before p stop . We show that π B has a cutwidth that is smaller than or equal to that of π B . Let q ∈ G be such that ρ(π B ) = Σ(q start , π B ), which exists due to Lemma A.1. We investigate the following two cases of q: Inria • q start is scheduled before p start in π B . Then, moving p start forward does not influence the cutwidth.

µ(π) = µ(q, π) = Σ(q start , π B ) ≤ ρ(π B ). (A.
• q start is scheduled after p start in π B .

We first show that Σ(q start , π B ) ≤ Σ(q start , π B ) as follows. If q start > π B p stop , then Σ(q start , π B ) = Σ(q start , π B ). Otherwise, since ω(p stop ) ≤ 0, we have Σ(q start , π B ) = Σ(q start , π B ) + ω(p stop ) ≤ Σ(q start , π B ). Thus, we have

ρ(π B ) = Σ(q start , π B ) ≤ Σ(q start , π B ) ≤ ρ(π B ).
We repeat this process until p start , p stop vertices are scheduled consecutively, which does not degrade the cutwidth.

B Series composition (used for Theorem 6)

Lemma B.1. Let G 1 and G 2 be two series-parallel directed graphs. Let (S 1 , T 1 ) and (S 2 , T 2 ) be min-ω-cuts, and π 1 and π 2 be schedules cut-optimal with (S 1 , T 1 ) and (S 2 , T 2 ) for G 1 and G 2 , respectively. Let π = π 1 , π 2 be the schedule of the series composition G = G 1 , G 2 inducing π 1 and π 2 . Then,

(i) π is cut-optimal with both (S 1 , T 1 ∪G 2 ) and (G 1 ∪S 2 , T 2 ), (ii) (S, T ) is a min-ω-cut of G, where (S, T ) = min{(S 1 , T 1 ∪ G 2 ), (G 1 ∪ S 2 , T 2 )}.
Proof. We first concentrate on item (i) of the lemma. We only show that π is cut-optimal with (S 1 , T 1 ∪ G 2 ), as the other can be proven similarly. Let (S, T ) = (S 1 , T 1 ∪ G 2 ). We need to show π[S] and π[T ] both are minimal for . First consider π[S]. Since π 1 is cut-optimal with (S 1 , T 1 ) for G 1 , π1 [S 1 ] is minimal for on G 1 . Then, π[S] is minimal for on G.

Now consider τ = π[T ]. For any schedule κ of G[T ], we need to show τ κ. Take any schedule κ of G[T ]. We show that there is a vertex q ∈ T for each vertex p ∈ T such that p → τ κ q. Take any p ∈ T . We consider two scenarios of p ∈ T 1 and p ∈ G 2 , separately.

a) p ∈ T 1 . Let τ 1 = τ [T 1 ] = π 1 [T 1 ] and κ 1 = κ[T 1 ]. Notice that π 1 is min-cut-optimal for G 1 .
Then, π 1 [T 1 ], and equivalently τ 1 , is minimal for by definition. Then, τ 1 κ 1 . Then, there is a vertex q * ∈ T 1 such that p → τ1 κ1 q * . Note that q * ∈ T 1 ⊆ T , and we show p → τ κ q * , as follows.

1) (C1:

Σ(p, τ ) ≤ Σ(q * , κ)). Σ(p, τ ) = Σ(p, τ 1 ) ≤ Σ(q * , κ 1 ) = Σ(q * , κ).
2) (C2: min{Σ(s, τ ) : s ≥ τ p} ≤ min{Σ(r, κ) : r ≥ κ q * }). We examine a vertex r ≥ κ q * , in relation to the vertex t o = max κ T = max τ T , which is the single sink vertex of G.

Case 1. r ∈ T 1 . Since p → τ1 κ1 q * , there is a vertex s ∈ T 1 and s ≥ τ1 p such that Σ(s, τ 1 ) ≤ Σ(r, κ 1 ). Then, s ≥ τ p and

Σ(s, τ ) = Σ(s, τ 1 ) ≤ Σ(r, κ 1 ) = Σ(r, κ). Case 2. r ∈ G 2 , r < κ t o . Consider s ∈ G 2 such that Σ(s, π 2 ) = c(S 2 , T 2 ). Then, Σ(s, π 2 ) ≤ Σ(r, κ 2 ), where κ 2 = κ[G 2 ]
, due to Lemma 6. Then, s ≥ τ p and

Σ(s, τ ) = Σ(s, π 2 ) + ω(T 1 )
≤ Σ(r, κ 2 ) + ω(T 1 ) = Σ(r, κ).

RR n°8975

Case 3. r = t o . Consider s = t o . Then, s ≥ τ p, and

Σ(s, τ ) = Σ(t o , τ ) = Σ(t o , κ) = Σ(r, κ). b) p ∈ G 2 . Let τ 2 = τ [G 2 ] = π 2 and κ 2 = κ[G 2 ]. Notice that π 2 is min-cut-optimal for G 2 .
Then, π 2 , and equivalently τ 2 , is minimal for on G 2 , due to Theorem 3. Then, τ 2 κ 2 . Then, there is a vertex q * ∈ G 2 such that p → τ2 κ2 q * . Notice that Σ(v, τ ) = Σ(v, τ 2 ) + ω(T 1 ) and Σ(v, κ) = Σ(v, κ) + ω(T 1 ), for any vertex v ∈ G 2 . Since both p ∈ G 2 and q * ∈ G 2 , and p → τ2 κ2 q * , it holds p → τ κ q * , and q * ∈ G 2 ⊆ T .

We now concentrate on item (ii) of the lemma. We recall that (S 1 , T 1 ) and (S 2 , T 2 ) are both min-ω-cuts. Now, for the sake of contradiction, suppose that none of (S 1 , T 1 ∪ G 2 ) and (G 1 ∪ S 2 , T 2 ) is a min-ω-cut of G. Take any min-ω-cut (S * , T * ) of G. Consider the vertex, say v, that is shared by G 1 and G 2 . We analyze the cases of v ∈ S * and v ∈ T * , as follows. a) v ∈ S * . Let (S * 2 , T * 2 ) be the topological cut induced by (S * , T * ) on G 2 . Then,

c(S * 2 , T * 2 ) = c(G 1 ∪ S * 2 , T * 2 ) -ω(G 1 ) = c(S * , T * ) -ω(G 1 ) < c(G 1 ∪ S 2 , T 2 ) -ω(G 1 ) = c(S 2 , T 2 ).
This contradicts with the fact that

(S 2 , T 2 ) is a min-ω-cut of G 2 . b) v ∈ T * . Let (S * 1 , T * 1 ) be the topological cut induced by (S * , T * ) on G 1 . Then, c(S * 1 , T * 1 ) = c(S * 1 , T * 1 ∪ G 2 ) = c(S * , T * ) < c(S 1 , T 1 ∪ G 2 ) = c(S 1 , T 1 ).
This contradicts with the fact that (S 1 , T 1 ) is a min-ω-cut of G 1 .

C Compatible orders are sufficient (Theorem 7)

In this section, we prove Theorem 7 which allows to transform subgraphs into chains using Linearize before their parallel composition in Algorithm 3.

Definition C.1 (Segmentation into blocks).

Let G be an directed acyclic graph, and κ be a schedule of G. We say

Q κ = {Q 1 , Q 2 , . . .} is a segmentation into blocks on G for κ, if Q κ is a partition of the vertices of G, and for any two vertices p ∈ Q j and q ∈ Q k , p ≤ κ q implies j ≤ k. Each Q j ∈ Q κ is called a block of Q κ . We define the highest value H(Q j ) of a block Q j ∈ Q κ as H(Q j ) = max q∈Qj Σ(q, κ).
Similar to that of Liu [18], we define the hill-valley segmentation of a schedule of a directed acyclic graph, as follows.

Inria

Definition C.2 (Hill-valley segmentation). Let G be a directed acyclic graph, and τ be a schedule of G. The hill-valley segmentation P τ = {P 1 , P 2 , . . .} is a particular block segmentation into blocks on G for τ , which is defined as follows. Let v 0 = min τ G and

h 1 = max τ {h ∈ G : Σ(h, τ ) = ρ(τ )}.
Define v i and h i , recursively, as

v i = max τ {arg min v≥τ hi Σ(v, τ )},
and

h i = max τ {arg max h>τ vi-1 Σ(h, τ )}.
Finally, define

P 1 = {v : v 0 ≤ τ v ≤ τ v 1 }, and
P i = {v : v i-1 < v ≤ v i }, for i > 1.
We say that each P i ∈ P τ is a segment of P τ . The hill-value H i and the valley-value V i of a segment P i ∈ P τ are defined as H i = Σ(h i , τ ), and

V i = Σ(v i , τ ).
Note that Σ(p, τ ) ≤ H i , for any p ∈ P i .

The following property, similar to that given by Liu [18, Lemma 5.1], of the hill-valley segmentation is clear from the definition.

Lemma C.1. Let G be a directed acyclic graph, τ be a schedule of G, and P τ = {P 1 , P 2 , . . . , P r } be the hill-valley segmentation of G for τ . Then,

H 1 > H 2 > • • • > H r ≥ V r > • • • > V 2 > V 1 .
Hereafter, we assume that P τ implies a hill-valley segmentation of G for a schedule τ , implicitly. Similarly, Q κ implies any arbitrary segmentation, unless explicitly stated, of G into blocks for a schedule κ.

Definition C.3 (Segment indicates block).

Let G be a directed acyclic graph, τ and κ be schedules of G. Let P i ∈ P τ be a segment and Q j ∈ Q κ be a block. We write P i → Q j , and read P i indicates Q j , if there is a vertex q * j ∈ Q j such that h i → τ κ q * j . We now demonstrate some properties of the hill-valley segmentation. For Propositions C.1-C.4, we assume G is any arbitrary directed acyclic, and τ and κ are schedules of G.

Proposition C.1. Let P i ∈ P τ be a segment and Q j ∈ Q κ be a block.

If P i → Q j , then (i) H i ≤ H(Q j ), (ii) V i ≤ min{Σ(r, κ) : r ≥ κ q o j }
, where q o j = max κ Q j . Proof. Assume P i → Q j . Then, there is a q * j ∈ Q j such that h i → τ κ q * j , following the definition of dominance given in Section 4.2.1. We prove the two results separately as follows.

(i) By the first condition (C1) of h i → τ κ q * j , we conclude

H i = Σ(h i , τ ) ≤ Σ(q * j , κ) ≤ H(Q j ).
(ii) By the second condition (C2) of h i → τ κ q * j , we have

V i = min{Σ(s, τ ) : s ≥ τ h i } ≤ min{Σ(r, κ) : r ≥ κ q * j } ≤ min{Σ(r, κ) : r ≥ κ q o j }.
Proposition C.2. Let P i ∈ P τ be a segment and Q j ∈ Q κ be a block. Let Q k ∈ Q κ be another block with k < j.

If P i → Q k and P i → Q j , then H(Q j ) < H i .
Proof. Suppose, for the sake of contradiction, that

P i → Q k and P i → Q j but H(Q j ) ≥ H i . Since P i → Q k , there is q * k ∈ Q k such that h i → τ κ q * k . Then, min{Σ(s, τ ) : s ≥ τ h i } ≤ min{Σ(r, κ) : r ≥ κ q * k }.
Consider q * j ∈ Q j such that Σ(q * j , κ) = H(Q j ). Then, q * k ≤ κ q * j , and thus,

min{Σ(s, τ ) : s ≥ τ h i } ≤ min{Σ(r, κ) : r ≥ κ q * j }. (C.1)
Since H i ≤ H(Q j ), as we have supposed for the sake of contradiction, we have

Σ(h i , τ ) = H i ≤ H(Q j ) = Σ(q * j , κ). (C.2)
Then, Equations (C.1) and (C.2) together imply h i → τ κ q * j , which arises a contradiction with

P i → Q j . Proposition C.3. Let τ κ.
For any segment P i ∈ P τ , there is a block

Q j ∈ Q κ such that P i → Q j .
Proof. Take any P i ∈ P τ . Since τ κ, we have h i → τ κ q * j , for some q * j ∈ G. For q * j ∈ Q j , this implies P i → Q j , by Definition C.3 Definition C.4 (Monotonic segments-to-blocks function). A function g : P τ → Q κ is called monotonic if (i) P i → g(P i ), for any P i ∈ P τ , and (ii) Q j = g(P i ) and Q k = g(P i+1 ) implies j ≤ k.

Proposition C.4, together with Proposition C.3, proves that there is a monotonic segmentsto-blocks function g τ →κ whenever τ κ.

Proposition C.4. Let τ κ. For any consecutive segments P i , P i+1 ∈ P τ and any block

Q j ∈ Q κ with P i → Q j , there is a block Q k ∈ Q κ such that P i+1 → Q k and j ≤ k.
Proof. We prove by contradiction. Suppose the contrary that, P i+1 → Q k for any k ≥ j. Take any Q k ∈ Q κ such that P i+1 → Q k , which exists due to Preposition C.3. Then we have,

P i → Q j , P i+1 → Q j , P i+1 → Q k , and k < j. (1) H i+1 < H i , due to Lemma C.1, (2) H i ≤ H(Q j ), due to Proposition C.1, (3) H(Q j ) < H i+1 , due to Proposition C.2.
Then, we obtain H i+1 < H i+1 , which arises a contradiction.

Hereafter, we focus on a particular kind of directed acyclic graph, so called half-series-parallel. We use half-series-parallel directed graphs and Lemma C.4 as building blocks of the proof of Theorem 7.

Inria

Definition C.5 (Half-series-parallel directed graph). A directed acyclic graph H is called halfseries-parallel, if there is a series-parallel directed graph G and a min-ω-cut (S, T ) of G such that

H = G[T ].
Lemma C.2. Let H be a half-series-parallel directed graph, and t o be the single sink vertex of H. Let τ be a schedule of H. Then, Σ(p, τ ) ≥ 0, for any p ∈ H \ {t o }.

Proof. Consider a series-parallel directed graph G, a min-ω-cut (S, T ) of G such that G[T ] = H. Take any p ∈ H \ {t o }. For the sake of contradiction, suppose Σ(p, τ ) < 0. Consider the set P = {v ∈ T : v ≤ τ p}. Then, (S ∪ P, T /P ) is topological and ω(P ) = Σ(p, τ ) < 0. Therefore, c(S ∪ P, T /P ) = ω(S) + ω(P ) < ω(S) = c(S, T ), which contradicts with the minimality of (S, T ).

Lemma
Σ(p * , λ) = ω({p ∈ H : p ≤ λ p * }) = ω({p ∈ H 1 : p ≤ λ p * }) + ω({p ∈ H 2 : p ≤ λ p * }) = ω({p ∈ H 1 : p ≤ λ[H1] p * 1 }) + ω({p ∈ H 2 : p ≤ λ[H2] p * 2 }) = Σ(p * 1 , λ[H 1 ]) + Σ(p * 2 , λ[H 2 ]).
Lemma C.4. Let H 1 and H 2 be two half-series-parallel directed graphs, and H be the half-seriesparallel directed graph obtained from H 1 and H 2 by unifying their unique sink vertex. Let τ be a schedule of H 1 minimal for . For any schedule λ of H, there is a schedule η of H such that (i) η induces τ , and (ii) η λ.

Before proving Lemma C.4, we state and prove Propositions C.5-C.6, which are used in the proof of Lemma C.4. For Propositions C.5-C.6, we use the definitions in Lemma C.4. That is, H 1 and H 2 are half-series-parallel directed graphs, and H is the half-series-parallel directed graph obtained from H 1 and H 2 by unifying their sink vertex. Accordingly, λ is a schedule of H and induces κ on H 1 (κ = λ[H 1 ]), and Q κ is the segmentation of H 1 into blocks induced by κ. This particular segmentation is built such that for any p, q ∈ H 1 with p ≤ κ q, where p ∈ Q j and q ∈ Q k , it holds that j = k if and only if there is no r ∈ H 2 with p ≤ λ r ≤ λ q. We assume τ is a schedule of H 1 such that τ κ, and g τ →κ : P τ → Q κ is a monotonic segments-to-block function (see Definition C.4 and the discussion after it). We introduce a schedule η which is built upon g τ →κ over λ, as follows. We replace in λ each block Q j ∈ Q with the segments of

g -1 τ →κ (Q j ) = {P i ∈ P τ : g τ →κ (P i ) = Q j }.
By virtue of the monotonic character of g τ →κ , we end up with a schedule η that induces τ by the above-mentioned replacement. Note that η is equivalent to λ on H Proposition C.5. Let P i ∈ P τ be a segment and Q j ∈ Q κ be a block such that g τ →κ (P i ) = Q j . Recall from above that τ is minimal for on H 1 and λ is any schedule of H. Let κ be the schedule induced by λ on H 1 , and η be the schedule of H built upon g τ →κ over λ. For any p ∈ P i and any q ∈ Q j , if Σ(p, τ ) ≤ Σ(q, κ), then Σ(p, η) ≤ Σ(q, λ).

Proof. Assume Σ(p, τ ) ≤ Σ(q, κ). Let p λ = max λ {w ∈ H 2 , w ≤ λ p}. Then, we have two cases to consider.

1. (p λ is not defined). Then, Σ(p, η) = Σ(p, τ ) ≤ Σ(q, κ) = Σ(q, λ).

2. (p λ is defined). Then, by the use of Lemma C.3, we have

Σ(p, η) = Σ(p, τ ) + Σ(p λ , η[H 2 ]) ≤ Σ(q, κ) + Σ(p λ , λ[H 2 ]) = Σ(q, λ).
Note that by construction of η, p λ = max λ {w ∈ H 2 , w ≤ λ q} which justifies the last equality.

Proposition C.6. Recall that η and λ are schedules of H where η is built upon g τ →κ over λ using the same τ and κ as before. Let p ∈ H 1 and p

λ = max λ {w ∈ H 2 , w ≤ λ p}. If p λ is defined, then Σ(p λ , η) ≤ Σ(p, λ).
Proof. Assume p λ is defined. Let p τ = max η {w ∈ H 1 , w ≤ η p λ }. We consider the following two cases, separately.

1. (p τ is not defined). Since H 1 is half-series-parallel, Σ(p, κ) ≥ 0, as suggested by Lemma C.2.

Then, by the use of Lemma C.3, we have

Σ(p λ , η) = Σ(p λ , η[H 2 ]) ≤ Σ(p λ , λ[H 2 ]) + Σ(p, κ) = Σ(p, λ).
2. (p τ is defined). Let P i ∈ P τ such that p τ ∈ P i , and notice that p τ = v i . Similarly, let

Q j ∈ Q κ such that p ∈ Q j . Let Q k = g τ →κ (P i ), and q o k = max κ Q k .
By definition of p λ and Inria p τ , we have k < j, and thus, p ≥ κ q o k . Note that P i → Q k . Then, due to Proposition C.1, we have Proposition C.7. Recall that η and λ are schedules of H where η is built upon g τ →κ over λ using the same τ and κ as before. For any p ∈ H 2 , we have Σ(p, η) ≤ Σ(p, λ).

Σ(p τ , τ ) = V i ≤ min{Σ(r, κ) : r ≥ κ q o k } ≤ Σ(p, κ). Then, by Lemma C.3, we have Σ(p λ , η) = Σ(p τ , τ ) + Σ(p λ , η[H 2 ]) ≤ Σ(p, κ) + Σ(p λ , λ[H 2 ]) = Σ(p, λ). κ = λ[H 1 ] final schedule η segments of τ replacing blocks of κ original schedule λ P i ... ... ... ... H 1 H 2 H 2 H 1 ... ... ... ... p κ Q j Q k p p p τ
Proof. Let p κ = max λ {w ∈ H 1 , w ≤ λ p} and p τ = max η {w ∈ H 1 , w ≤ η p}. Note that when p κ is not defined, then p τ is not defined either. Then, we have the following three cases to consider.

1. (Either p κ or p τ is not defined). Then,

Σ(p, η) = Σ(p, η[H 2 ]) = Σ(p, λ[H 2 ]) = Σ(p, λ). 2. (p κ is defined, but p τ is not). Since H 1 is half-series-parallel, Σ(p κ , κ) ≥ 0, as Lemma C.2
suggests. Thus, by the use of Lemma C.3, we have

Σ(p, η) = Σ(p, λ[H 2 ]) ≤ Σ(p, λ[H 2 ]) + Σ(p κ , κ) = Σ(p, κ).
3. (Both p κ and p τ are defined). Let P i ∈ P τ such that p τ ∈ P i , and notice that

p τ = v i . Similarly, let Q j ∈ Q κ such that p κ ∈ Q j . Let Q k = g τ →κ (P i ), and
q o k = max κ Q k .
By definition of p κ and p τ , we have j ≥ k, and thus, p κ ≥ κ q o k . Note that P i → Q k . Then, due to Proposition C.1, we have

Σ(p τ , τ ) = V i ≤ min{Σ(r, κ) : r ≥ κ q o k } ≤ Σ(p κ , κ). Then, by Lemma C.3, we have Σ(p, η) = Σ(p τ , τ ) + Σ(p, η[H 2 ]) ≤ Σ(p κ , κ) + Σ(p, λ[H 2 ]) = Σ(p, λ).

RR n°8975

Now, we are ready to prove Lemma C.4.

Proof of Lemma C.4. Recall that τ is a schedule of H 1 which is minimal for , and λ is an arbitrary schedule of H that induces κ on H 1 . Since τ is minimal for , τ κ. Then, let g τ →κ be a monotonic segments-to-blocks function, which exists due to Propositions C.3 and C.4. Let η be a schedule of H built upon g τ →κ over λ.

With the above construction (i) is proved, as η induces τ in H 1 .

We now establish (ii) η λ. For this, we show that for each p ∈ H, there is q * ∈ H such that p → η λ q * . For any p, either p ∈ H 1 or p ∈ H 2 . We explore these two cases separately.

a) p ∈ H 1 . Let p ∈ P i and Q j = g τ →κ (P i ). Since P i → Q j , there is a vertex q * j ∈ Q j such that p → τ κ q * j . Now, we show that it also holds p → η λ q * j .

1) (C1: Σ(p, η) ≤ Σ(q * j , λ)). Since p → τ κ q * j , we have Σ(p, τ ) ≤ Σ(q * j , κ). Then, Proposition C.5 suggests that C1 is met.

2) (C2: min{Σ(s, η) : s ≥ η p} ≤ min{Σ(r, λ) : r ≥ λ q * j }). We show that for each r ≥ λ q * j , there is a vertex s ≥ η p such that Σ(s, η) ≤ Σ(r, λ). We examine three cases:

r ∈ Q j , or r ∈ H 1 \ Q j , or r ∈ H 2 . Case 1. r ∈ Q j . Since p → τ κ q * j
, there is a vertex s ≥ τ p such that Σ(s, τ ) ≤ Σ(r, κ). We consider two scenarios of s ∈ P i and s ∈ P i . i) (s ∈ P i ). Then, Proposition C.5 suggests Σ(s, η) ≤ Σ(r, λ), and notice that s ≥ η p, as s ≥ τ p. ii) (s ∈ P i ). Then, s ≥ τ v i ≥ τ p. Since Σ(v i , τ ) ≤ Σ(s, τ ), by the definition of v i , we have Σ(v i , τ ) ≤ Σ(r, κ). Then, Proposition C.5 suggests Σ(v i , η) ≤ Σ(r, λ), and notice that v i ≥ η p, as v i ≥ τ p. Case 2. r ∈ H 1 \ Q j . Let r ∈ Q k and r λ = max λ {w ∈ H 2 , w ≤ λ r}. Since r ≥ κ q * j and r ∈ Q j , it holds k > j, and thus, r λ is defined and r λ ≥ λ q * j . Then, Proposition C.6 suggests Σ(r λ , η) ≤ Σ(r, λ), and notice that r λ ≥ η p, as r λ ≥ λ q * j . Case 3. r ∈ H 2 . Then, Proposition C.7 suggests Σ(r, η) ≤ Σ(r, λ), and notice that r ≥ η p, as r ≥ λ q * j .

b) p ∈ H 2 . We show p → η λ p. The first condition (C1) directly holds due to Proposition C.7. Considering the second condition (C2), we show, for any r ≥ λ p, there is s ≥ η p, such that Σ(s, η) ≤ Σ(r, λ). We explore the two cases of r ∈ H 1 and r ∈ H 2 , separately. D FJ-Schedule is min-cut-optimal (Theorem 8) FJ-Schedule, presented in Algorithm 4, relies on Tree-Schedule to compute schedules for trees that are minimal for . This latter algorithm, which we describe below, in turn relies on Liu's algorithm for trees. However, Liu's algorithm uses another model, namely the generalized pebble game: each node is provided with a number of pebbles which should be use to pebble it. As usual in pebble games, the objective is to pebble the tree up to the root using a minimal number of pebbles. In order to prove that his algorithm is optimal, Liu's relies on the notion of Pcost sequences. In the following, we prove that a schedule minimal for Pcost sequences is also minimal for our relation . The proof of Theorem D.1 thus largely relies on notations and concepts borrowed from [18]. We first introduce a restriction on the trees on which Tree-Schedule may be applied. Definition D.1 (Liu-compatible tree). Let T be a directed in-tree and r be its root vertex. We say T is Liu-compatible if ω(T [v]) ≥ 0 for each vertex v ∈ T -{r}, where T [v] is the subtree rooted at v. Proof. For this proof, we use the notations given in [18], and we assume that the reader is familiar with its results. In this article, Liu considers for any vertex v of a tree a non-negative value τ (v) which represents the number of pebbles required to satisfy this node. We consider here the following pebbling function as defined in Algorithm D.1, namely: We then consider the Pcost(π), the cost sequence of a schedule π, as defined in [18]. We prove that if Pcost(π) ≺ Pcost(γ) then π γ, for two schedules π and γ of T .

Assume Pcost(π) ≺ Pcost(γ). Now, for each vertex p ∈ T , we need to exhibit a vertex q * ∈ T such that p → π γ q * . Since r = max π T = max γ T , we have r → π γ r. Now, take any vertex p ∈ T -{r}. Let p reside in the i th hill-valley segment with respect to π. By definition of ≺ in [18, Section 5.2], there exists j such that Hi ≤ H j , and Ṽi ≤ V j , where ( Hi , Ṽi ) and (H j , V j ) are the hill-valley values for i th and j th segments with respect to schedules π and γ, respectively. Consider a vertex q * ∈ T -{r} so that q * resides in the j th hill-valley segment with respect to γ, and peb γ (q * ) = H j , where such q * exists due to Equation D.1. Now, we show p → π γ q * as follows.

Inria

  p)∈E w e (r, p)   + w n (p) +   (p,q)∈E w e (p, q)  

Inria

Figure 1 :Algorithm 1

 11 Figure 1: Sample in-tree and decomposition of its schedule in segments.

Lemma 1 .

 1 Let G be a fork-join graph. For each branch B i of this graph, let e min i = (u min i , v min i ) be an edge of B i with the minimum weight. Let S be the set of ancestors of the u min i 's, including them. Let T be the set of successors of the v min i 's, including them. Let π be a schedule of G and γ be the schedule obtained from π by scheduling all vertices of S before vertices of T , formally γ = π[S], π[T ] . Then, µ(γ) ≤ µ(π).

Figure 2 :

 2 Figure 2: Sample fork-join graph and its decomposition for Lemma 1. If the dashed edges are minimum in the corresponding branches, an optimal traversal can be found by first ordering the vertices in the set S and then the vertices in the set T .

))

  be the edge of minimum weight in B i Remove the edge e min i from the graph Update the weight of each other edge e of B i : w e (e) ← w e (e) -w e (e min i Update the weight of each vertex u in B i (except s and t): w n (u) ← w n (u) + w e (e min i )

Corollary 1 .

 1 If π is minimal for on G, then π and π have the minimum cutwidths (on G and Ḡ respectively).

Inria

Theorem 2 .

 2 Let G be an acyclic graph with a single source vertex and a single sink vertex, and γ be a schedule of G. Let (S, T ) be a min-ω-cut of G, and π = γ[S], γ[T ] . Then, π γ and π γ.

Inria Algorithm 3

 3 SP-Schedule(G) Require: G = (V, E, ω): series-parallel graph. Ensure: π: schedule and (S, T ): min-ω-cut Base case if |E| = 1 then (S, T ) ← ({v}, {w}) return [ v, w , (S, T )]

  Now, consider any vertex p ∈ G. We have µ(p, π) = w n (p) + q≤πp≤πr w e (q, r) = w n (p) + p≤πr w e (p, r) + q<πp≤πr w e (q, r) = ω(p start ) + q<πp≤πr w e (q, r) + q≤πr<πp w e (q, r) -q≤πr<πp w e (q, r) = ω(p start ) + q<πp   p≤πr w e (q, r) + q≤πr<πp w e (q, r)   -q≤πr<πp w e (q, r) = ω(p start ) + q<πp q≤πr

2 )Lemma A. 4 .

 24 By combining Equations A.1 and A.2, we have µ(π) = ρ(π B ). Let π B be a schedule of G B . There exists a schedule π B of G B such that (i) p start and p stop are consecutive in π B , for each p ∈ G, and (ii) ρ(π B ) ≤ ρ(π B ).

Figure C. 1 :

 1 Figure C.1: Illustration of a schedule η built upon g τ →κ over λ, and notations used in Propositions C.5 and C.6.

Figure C. 2 :

 2 Figure C.2: Illustration of a schedule η built upon g τ →κ over λ, and notations used in Proposition C.7.

Inria Case 1 .

 1 r ∈ H 1 . Let r λ = max λ {w ∈ H 2 , w ≤ λ r}. Since r ≥ λ p and p ∈ H 2 , r λ is defined and r λ ≥ λ p. Due to Proposition C.6, we have Σ(r λ , η) ≤ Σ(r, λ), and notice that r λ ≥ η p, as r λ ≥ λ p.Case 2. r ∈ H 2 . Proposition C.7 suggests Σ(r, η) ≤ Σ(r, λ),and notice that r ≥ η p, as r ≥ λ p.We first recall Theorem 7, and show the proof as a consequence of Lemma C.4.Theorem C.1 (Restatement ofTheorem 7). Let G 1 and G 2 be two series-parallel directed graphs, and G = {G 1 , G 2 } be their parallel composition. Let (S, T ) be a min-ω-cut of G, and π 1 and π 2 be schedules that are cut-optimal with the topological cuts induced by (S, T ) on G 1 and G 2 , respectively. For each schedule γ in compliance with (S, T ) of G, there is a schedule π in compliance with (S, T ) of G such that(i) π induces π 1 and π 2 , (ii) π[S] γ[S] and π[T ] γ[T ].Proof of Theorem 7. Take any schedule γ in compliance with (S, T ) of G. Let (S 1 , T 1 ) be topological cut induced by (S, T ) on G 1 . Considerλ t = γ[T ] and τ t 1 = π 1 [T 1 ]. Then, τ t 1 is minimal for , since π 1 is cut-optimal with (S 1 , T 1 ). Then, we have a schedule η t of G[T ] inducing τ t 1 such that η t λ t , as suggested by Lemma C.4. Now, consider λs = γ[S] and τ s 1 = π1 [S 1 ]. Then, τ s 1 is minimal for , since π 1 is cut-optimal with (S 1 , T 1 ). Then, we have a schedule ηs of G[S] inducing τ s 1 such that ηs λs , as suggested by Lemma C.4. We consider π = η s , η t . We notice that (i) π induces π 1 and γ[G 2 ] on G 1 and G 2 , respectively. It also holds that (ii) π[S] γ[S] and π[T ] γ[T ]. Now, apply the procedure given above on π (instead of γ) for π 2 (instead of π 1 . Then, we obtain π = ηs , ηt that (i) induces π[G 1 ] and π 2 on G 1 and G 2 , respectively. It also holds that (ii) π[S] π[S] and π[T ] π[T ]. As a result, (i) π induces π 1 and π 2 . Secondly, since is transitive, it holds that (ii) π[S] γ[S] and π[T ] γ[T ].

Algorithm D. 1

 1 Tree-Schedule(G, (S, T ))Require: G = (V, E, ω): Liu-compatible vertex-weighted tree with root r Ensure: π: A minimal schedule forfor v ∈ V do if v = r then τ (v) ← ω(T -{r}) else τ (v) ← ω(T -{r}[v]) Call Algorithm 4.1 in[18] ("Pebble-Ordering") on T , with "Combine" procedure from Algorithm 6.1 (ibid.) to compute schedule π return π Theorem D.1. For any Liu-compatible tree T , Algorithm D.1 computes a schedule which is minimal for .

τ

  (v) = ω(T [v]) v ∈ T -{r} ω(T -{r}) v = r. (D.1)Notice that τ (v) ≥ 0 for each v ∈ T , as T is Liu-compatible. Let Parent(v) represent the parent vertex of v, for a vertex v ∈ T -{r}. As in[18], we consider for any schedule π of T the value peb π (v) which represents the "total number of pebbles used during the pebbling of the vertex v" while following schedule π.We first prove that with the previous pebbling function,peb π (v) = Σ(v, π), for each v ∈ T -{r}. Take any v ∈ T -{r}. Let F v = {r ∈ T : r ≤ π v < π Parent(r)},that is, the set populated by the root vertices of the pruned forest. Then, peb π (v) = r∈Fv τ (r) = r∈Fv ω(T [r]) = ω({u ≤ π v}) = Σ(v, π).

  1 and G 2 with terminals s 2 , t 2 formed by identifying s = s 1 , t = t 2 and t 1 = s 2 , and denoted by G 1 , G 2 ; Parallel composition: The parallel composition of two SP-graphs G 1 with terminals s 1 , t 1 and G 2 with terminals s 2 , t 2 formed by identifying s = s 1 = s 2 and t = t 1 = t 2 , and denoted by {G 1 , G 2 }.

  C.3. Let H 1 and H 2 be two half-series-parallel directed graphs, and H be the half-seriesparallel directed graph obtained from H 1 and H 2 by unifying their unique sink vertex. Let λ be a schedule of H and p * ∈ H. Consider p * i = max λ {p ∈ H i : p ≤ λ p * }, for i = 1, 2. If p * 1 and p *

	2
	both are defined, then
	Σ(p * , λ) = Σ(p * 1 , λ[H 1 ]) + Σ(p * 2 , λ[H 2 ]).
	Proof. Assume p * 1 and p * 2 are defined. Then,

  2 , i.e., η[H 2 ] = λ[H 2 ].Figure C.1 and C.2 illustrate the construction of η and the notations used in the following propositions. Then, there only remains to show that η λ in order to prove Lemma C.4. To do so, we need Propositions C.5-C.7, concerned with the schedule η of H that is built upon g τ →κ over schedule λ of H.

			H 1
	...	H 1	H 2	H 2	...	original schedule λ
		Q k	Q j
	...				...	κ = λ[H 1 ]
	...				...	segments of τ replacing blocks of κ
			p
	...				...	final schedule η
		P i	p λ

RR n°8975

Inria

Acknowledgement

We thank Henri Casanova for his comments on an earlier version of this manuscript. Loris Marchal and Bora Uçar were supported in part by French National Research Agency (ANR) project SOLHAR (ANR-13-MONU-0007).

Appendix

The appendix is composed of four parts. Appendix A contains lemmas used in the proof of Theorem 1 in which we proved that minimizing the cutwidth in the cumulative weight model minimizes the peak memory in the original model. The sections Appendix B, C, and D contain lemmas used in showing the correctness of SP-Schedule algorithm. These three sections give the proof of Theorems 6, 7, and 8, respectively. The last section Appendix D also contains the adaptation of Liu's algorithm to the cumulative weight model.

A Problem transformation

Lemmas A.1-A.4 are used in the proof of Theorem 1 and assume the same notation. In particular, the peak memory minimization problem is given by a graph G = (V, E, w n , w e ), and the corresponding cutwidth instance has the bipartite graph

Proof. For the sake of contradiction, assume that ρ(π B ) > Σ(p start , π B ) for every p ∈ G. Consider a vertex q of G such that the cutwidth of π B is reached on q stop , i.e., ρ(π) = Σ(q stop , π B ).

By construction (4), ω(v stop ) ≤ 0, for any vertex v. We consider p start , the last "start" vertex scheduled before q stop in π B : p start = max π ({v start ≤ π B q stop }). Nnote that there exists such a p start since q start is scheduled before q stop . Then,

Then, we have

Proof. For this proof, we extend the definition of the edge weights in such a way that w e (q, r) = 0 if there is no edge (q, r) in E. With this extension, we may write

RR n°8975

Theorem D.2 (Restatement of Theorem 8). For any fork-join graph G and any min-ω-cut (S, T ) of G, FJ-Schedule computes a schedule π that is cut-optimal with (S, T ).

Proof of Theorem 8. Let G be a fork-join directed graph and (S, T ) be a min-ω-cut of G. We first check that both Ḡ[S] and G[T ] are Liu-compatible trees.

We only show that G[T ] is Liu-compatible, as the other can be proven similarly. For the sake of contradiction, suppose that G[T ] is not Liu-compatible. Then, there is a vertex, say v, such that ω(T [v]) < 0. Consider the topological cut (S , T ), where S = S ∪ T

The first steps of FJ-Schedule as described in Algorithm 4 is to compute schedules σ and τ for Ḡ[S] and G[T ] using Tree-Schedule. Thanks to Theorem D.1, we know that these schedules are minimal for .

Then, by definition, π = σ, τ is cut-optimal with (S, T ), as π is in compliance with (S, T ), σ is minimal for on Ḡ[S], and τ is minimal for on Ḡ[S].