Daouya Laïche

Éric Sopena

Packing colouring of some classes of cubic graphs

Keywords: Packing colouring, Packing chromatic number, Circular ladder, H-graph, Generalised H-graph 05C15, 05C12

The packing chromatic number χ ρ (G) of a graph G is the smallest integer k such that its set of vertices V (G) can be partitioned into k disjoint subsets V 1 , . . . , V k , in such a way that every two distinct vertices in V i are at distance greater than i in G for every i,

Recently, Balogh, Kostochka and Liu proved that χ ρ is not bounded in the class of subcubic graphs [Packing chromatic number of subcubic graphs, Discrete Math. 341 (2018), 474483],

thus answering a question previously addressed in several papers. However, several subclasses of cubic or subcubic graphs have bounded packing chromatic number. In this paper, we determine the exact value of, or upper and lower bounds on, the packing chromatic number of some classes of cubic graphs, namely circular ladders, and so-called H-graphs and generalised H-graphs.

Introduction

All the graphs we consider are simple. For a graph G, we denote by V (G) its set of vertices and by E(G) its set of edges. The distance d G (u, v) between vertices u and v in G is the length (number of edges) of a shortest path joining u and v. The diameter of G is the maximum distance between two vertices of G. We denote by P n , n ≥ 1, the path of order n and by C n , n ≥ 3, the cycle of order n.

A packing k-colouring of G is a mapping π : V (G) → {1, . . . , k} such that, for every two distinct vertices u and v, π(u) = π(v) = i implies d G (u, v) > i. The packing chromatic number χ ρ (G) of G is then the smallest k such that G admits a packing k-colouring. In other words, χ ρ (G) is the smallest integer k such that V (G) can be partitioned into k disjoint subsets V i , 1 ≤ i ≤ k, in such a way that every two vertices in V i are at distance greater than i in G for every i, 1 ≤ i ≤ k. A packing colouring of G is optimal if it uses exactly χ ρ (G) colours.

The packing colouring of graphs was introduced by Goddard, Hedetniemi, Hedetniemi, Harris and Rall in [START_REF] Goddard | Broadcast chromatic numbers of graphs[END_REF][START_REF] Goddard | Broadcast chromatic numbers of graphs[END_REF], under the name broadcast colouring. In their seminal paper [START_REF] Goddard | Broadcast chromatic numbers of graphs[END_REF], the question of determining the maximum packing chromatic number in the class of cubic graphs of a given order is posed. In [START_REF] Sloper | An eccentric colouring of trees[END_REF], Sloper proved that the packing chromatic number is unbounded in the 1 Faculty of Mathematics, Laboratory L'IFORCE, University of Sciences and Technology Houari Boumediene (USTHB), B.P. 32 El-Alia, Bab-Ezzouar, 16111 Algiers, Algeria.

2 Univ. Bordeaux, Bordeaux INP, CNRS, LaBRI, UMR5800, F-33400 Talence, France.

3 Corresponding author. Eric.Sopena@labri.fr. 1 class of k-ary trees for every k ≥ 3, from which it follows that the packing chromatic number is unbounded in the class of graphs with maximum degree 4.

In [START_REF] Gastineau | S-packing colourings of cubic graphs[END_REF], Gastineau and Togni observed that each cubic graph of order at most 20 has packing chromatic number at most 10. They also observed that the largest cubic graph with diameter 4 (this graph has 38 vertices and is described in [START_REF] Alegre | Some large graphs with given degree and diameter[END_REF]) has packing chromatic number 13, and asked whether there exists a cubic graph with packing chromatic number larger than 13 or not. This question was answered positively by Bre²ar, Klavºar, Rall and Wash [START_REF] Bre²ar | Packing chromatic number under local changes in a graph[END_REF] who exhibited a cubic graph on 78 vertices with packing chromatic number at least 14. Recently, Balogh, Kostochka and Liu nally proved in [2] that the packing chromatic number is unbounded in the class of cubic graphs, and Bre²ar and Ferme gave in [5] an explicit innite family of subcubic graphs with unbounded packing chromatic number.

On the other hand, the packing chromatic number is known to be upper bounded in several classes of graphs with maximum degree 3, as for instance complete binary trees [START_REF] Sloper | An eccentric colouring of trees[END_REF], hexagonal lattices [START_REF] Bre²ar | On the packing chromatic number of Cartesian products, hexagonal lattice, and trees[END_REF][START_REF] Fiala | The packing chromatic number of innite product graphs[END_REF][START_REF] Korºe | On the packing chromatic number of square and hexagonal lattice[END_REF], base-3 Sierpi«ski graphs [START_REF] Bre²ar | Packing Chromatic Number of Base-3 Sierpi«ski Graphs[END_REF] or particular Sierpi«ski-type graphs [4], subdivisions of subcubic graphs [START_REF] Bre²ar | Packing chromatic number, (1, 1, 2, 2)colourings, and characterizing the Petersen graph[END_REF][START_REF] Gastineau | S-packing colourings of cubic graphs[END_REF] and of cubic graphs [3], or several subclasses of outerplanar subcubic graphs [START_REF] Gastineau | On the packing chromatic number of subcubic outerplanar graphs[END_REF].

We prove in this paper that the packing chromatic number is bounded in other classes of cubic graphs, extending in particular partial results given in [START_REF] William | Packing chromatic number of certain graphs[END_REF]. More precisely, we determine the exact value of, or upper and lower bounds on, the packing chromatic number of circular ladders (in Section 3), H-graphs (in Section 4) and generalised H-graphs (in Section 5).

Preliminary results

We give in this section a few results that will be useful in the sequel.

Let G be a graph. A subset S of V (G) is an i-packing, for some integer i ≥ 1, if any two vertices in S are at distance at least i + 1 in G. Note that such a set S is a 1-packing if and only if S is an independent set. A packing colouring of G is thus a partition of V (G) into k disjoint subsets V 1 , . . . , V k , such that V i is an i-packing for every i, 1 ≤ i ≤ k.

For every integer i ≥ 1, we denote by ρ i (G) the maximum cardinality of an i-packing in G. Since at most ρ i (G) vertices can be assigned colour i in any packing colouring of G, we have the

following result. Proposition 1 If G is a graph with χ ρ (G) = k, then i=k i=1 ρ i (G) ≥ |V (G)|. Let H be a subgraph of G. Since d G (u, v) ≤ d H (u, v)
for any two vertices u, v ∈ V (H), the restriction to V (H) of any packing colouring of G is a packing colouring of H. Hence, having packing chromatic number at most k is a hereditary property: Proposition 2 (Goddard, Hedetniemi, Hedetniemi, Harris and Rall [START_REF] Goddard | Broadcast chromatic numbers of graphs[END_REF])

Let G and H be two graphs. If H is a subgraph of G, then χ ρ (H) ≤ χ ρ (G).
In particular, Proposition 2 gives a lower bound on the packing chromatic number of a graph G whenever G contains a subgraph H whose packing chromatic number is known. As we will see later, all the cubic graphs we consider in this paper contain a corona of a cycle as a subgraph. Recall that the corona G K 1 of a graph G is the graph obtained from G by adding a degree-one neighbour to every vertex of G. In [START_REF] Laïche | Packing colouring of some undirected and oriented coronae graphs[END_REF], we have determined with I. Bouchemakh the packing chromatic number of the corona of cycles. Theorem 3 (Laïche, Bouchemakh, Sopena [START_REF] Laïche | Packing colouring of some undirected and oriented coronae graphs[END_REF])

u 0 v 0 u 1 v 1 u 2 v 2 u 3 v 3 u 4 v 4 u 5 v 5 u 6 v 6
The packing chromatic number of the corona graph C n K 1 is given by:

χ ρ (C n K 1 ) = 4 if n ∈ {3, 4}, 5 if n ≥ 5.
This result will thus provide a lower bound on the packing chromatic number of each cubic graph considered in this paper.

Circular ladders

Recall that the Cartesian product G H of two graphs G and H is the graph with vertex set V (G) × V (H), two vertices (u, u ) and (v, v ) being adjacent if and only if either u = v and u v ∈ E(H) or u = v and uv ∈ E(G).

The circular ladder CL n of length n ≥ 3 is the Cartesian product CL n = C n K 2 . Note that CL n is a bipartite graph if and only if n is even.

For every circular ladder CL n , we let

V (CL n ) = {u 0 , . . . , u n-1 } ∪ {v 0 , . . . , v n-1 }, and E(CL n ) = {u i v i | 0 ≤ i ≤ n -1} ∪ {u i u i+1 , v i v i+1 | 0 ≤ i ≤ n -1}
(subscripts are taken modulo n). Figure 1 depicts the circular ladder CL 7 .

Note that for every n ≥ 3, the corona graph C n K 1 is a subgraph of the circular ladder CL n . Therefore, by Proposition 2, Theorem 3 provides a lower bound on the packing chromatic number of circular ladders. More precisely,

χ ρ (CL n ) ≥ 4 if n ∈ {3, 4}, and χ ρ (CL n ) ≥ 5 if n ≥ 5.
William and Roy [START_REF] William | Packing chromatic number of certain graphs[END_REF] proved that the packing chromatic number of a circular ladder of length n = 6q, q ≥ 1, is at most 5. In Theorem 7 below, we extend this result and determine the packing chromatic number of every circular ladder.

We rst need the following technical lemma, which will also be useful in Section 5.

Lemma 4 Let X be the graph depicted in Figure 2, and π be a packing 5-colouring of X. If π(u i ) = 1 and π(v i ) = 1 for some integer i, 3 ≤ i ≤ 5, then either u i or v i has colour 2, and its three neighbours have colours 3, 4 and 5 (the three corresponding edges are the vertical edges surrounded by the dashed box). Proof. The proof is done by case analysis and is given in Appendix A.

u 0 v 0 u 1 v 1 u 2 v 2 u 3 v 3 u 4 v 4 u 5 v 5 u 6 v 6 u 7 v 7 u 8 v 8
Observe now that for every integer n ≥ 9, the subgraph of CL n induced by the set of vertices {u i , v i | 0 ≤ i ≤ 8} contains the graph X of Figure 2 as a subgraph. Moreover, every packing 5-colouring π of CL n , 6 ≤ n ≤ 8, can be unfolded to produce a packing 5-colouring π of X, by setting π (u i ) = π(u i ) and π (v i ) = π(v i ) for every i, 0 ≤ i ≤ n -1, and π (u n-1+j ) = π(u j-1 ) and π (v n-1+j ) = π(v j-1 ) for every j, 1 ≤ j ≤ 9 -n. This follows from the fact that vertices u j and u n+j , as well as vertices v j and v n+j , are at distance n ≥ 6 from each other, while the largest colour used by π is 5. Therefore, thanks to the symmetries of CL n for every n ≥ 6, Proposition 2 and Lemma 4 give the following corollary.

Corollary 5 Let CL n , n ≥ 6, be a circular ladder with χ ρ (CL n ) ≤ 5, and π be a packing 5colouring of CL n . For every integer i, 0 ≤ i ≤ n -1, if π(u i ) = 1 and π(v i ) = 1, then either u i or v i has colour 2, and its three neighbours have colours 3, 4 and 5.

Let CL n be a circular ladder satisfying the hypothesis of Corollary 5, and π be a packing 5-colouring of CL n . From Corollary 5, it follows that if π(u i ) = 1 and π(v i ) = 1 for some edge u i v i of CL n , then the colour 2 has to be used on the edge u i v i and, since the neighbours of the 2-coloured vertex are coloured with 3, 4 and 5, the colour 2 can be replaced by colour 1.

Therefore, we get the following corollary.

Corollary 6 If CL n , n ≥ 6, is a circular ladder with χ ρ (CL n ) ≤ 5, then there exists a packing 5-colouring of CL n such that the colour 1 is used on each edge of CL n .

Note that from Corollary 6, it follows that for every integer n ≥ 6, χ ρ (CL n ) ≤ 5 implies that CL n is a bipartite graph. Hence, χ ρ (CL n ) ≥ 6 for every odd n ≥ 6.

We are now able to prove the main result of this section. Theorem 7 For every integer n ≥ 3,

χ ρ (CL n ) =    5 if n = 3, or n is even and n ∈ {8, 14}, 7 if n ∈ {7, 8, 9}, 6 otherwise.
Proof. We rst consider the case n ≤ 5. Figure 3 describes a packing 5-colouring of CL 3 and CL 4 , and a packing 6-colouring of CL 5 . We claim that these three packing colourings are optimal. To see that, observe that ρ

1 (CL 3 ) = 2, ρ i (CL 3 ) = 1 for every i ≥ 2, ρ 1 (CL 4 ) = ρ 1 (CL 5 ) = 4, ρ 2 (CL 4 ) = ρ 2 (CL 5 ) = 2
, and ρ i (CL 4 ) = ρ i (CL 5 ) = 1 for every i ≥ 3. The optimality for CL 3 and CL 5 then follows from Proposition 1. The optimality for CL 4 also follows, with the additional observation that colour 2 can be used at most once if colour 1 is used four times.

Assume now n ≥ 6. Since n ≥ 6 and every circular ladder CL n contains the corona graph C n K 1 as a subgraph, we get χ ρ (CL n ) ≥ χ ρ (C n K 1 ) ≥ 5 by Theorem 3 and Proposition 2. Moreover, by Corollary 6, we have χ ρ (CL n ) ≥ 6 if n is odd.

We now consider two general cases.

1. n is even and n / ∈ {8, 14}. As observed above, in that case, it is enough to exhibit a packing 5-colouring of CL n to prove χ ρ (CL n ) = 5.

If n ≡ 0 (mod 6), a packing 5-colouring of CL n is obtained by repeating the following circular pattern (the rst row gives the colours of vertices u i , 0 ≤ i ≤ n -1, the second row gives the colours of vertices v i , 0 ≤ i ≤ n -1, according to the value of (i mod 6)):

1 3 1 2 1 5 2 1 4 1 3 1 If n ≡ 2 (mod 6), which implies n ≥ 20, a packing 5-colouring of CL n is obtained by repeating the previous circular pattern n-20 6
times and adding a pattern of length 20, as illustrated below:

1 3 1 2 1 5 1 3 1 2 1 3 1 4 1 5 1 3 1 2 1 3 1 4 1 5 2 1 4 1 3 1 2 1 4 1 5 1 2 1 3 1 2 1 4 1 5 1 2 1 3 1
Finally, if n ≡ 4 (mod 6), which implies n ≥ 10, a packing 5-colouring of CL n is obtained by repeating the same circular pattern n-10 6

times and adding a pattern of length 10:

1 3 1 2 1 5 1 3 1 2 1 3 1 4 1 5 2 1 4 1 3 1 2 1 4 1 5 1 2 1 3 1 2.
n is odd and n ≥ 11.

As observed above, in that case, it is enough to exhibit a packing 6-colouring of CL n to prove χ ρ (CL n ) = 6.

Similarly as in the previous case, if n ≡ 1, 3 or 5 (mod 6), a packing 6-colouring of CL n is obtained by repeating the previous circular pattern n-7 6 , n-9 6 or n-5 6 times, respectively, and adding a pattern of length 7, 9 or 5, respectively, as illustrated below:

1 3 1 2 1 5 1 3 1 4 1 2 6 2 1 4 1 3 1 6 1 2 1 3 1 5 1 3 1 2 1 5 1 4 1 2 3 1 4 1 6 2 1 4 1 3 1 2 1 6 1 5 2 1 3 1 1 3 1 2 1 5 1 3 1 2 6 2 1 4 1 3 1 2 1 4 1 5
It remains to consider four cases, namely n = 7, 8, 9, 14, which we consider separately.

1. n = 7.

We rst claim that χ ρ (CL 7 ) ≥ 7. Note that ρ 1 (CL 7 ) = 6, ρ 2 (CL 7 ) = 3, ρ 3 (CL 7 ) = 2, and ρ i (CL 7 ) = 1 for every i ≥ 4. However, if we use six times colour 1, colour 2 can be used at most twice. Hence, at most 13 vertices of CL 7 can be coloured with a colour in {1, . . . , 6}

and the claim follows.

A packing 7-colouring of CL 7 is given by the following pattern:

1 3 1 2 1 4 5 2 1 6 1 3 1 7 2. n = 8.

We rst claim that χ ρ (CL 8 ) ≥ 7. A packing 7-colouring of CL 8 is given by the following pattern:

1 3 1 2 1 5 1 7 2 1 4 1 3 1 6 1 3. n = 9. We rst claim that χ ρ (CL 9 ) ≥ 7. Note that ρ 1 (CL 9 ) = 8, ρ 2 (CL 9 ) = 4, ρ 3 (CL 9 ) = ρ 4 (CL 9 ) = 2
, and ρ i (CL 9 ) = 1 for every i ≥ 5. However, if we use eight times colour 1, colour 2 can be used at most thrice. Hence, at most 17 vertices of CL 9 can be coloured with a colour in {1, . . . , 6} and the claim follows. A packing 7-colouring of CL 9 is given by the following pattern:

1 3 1 2 1 5 1 4 6 2 1 4 1 3 1 2 1 7

4. n = 14.

We rst claim that χ ρ (CL 14 ) ≥ 6. Note that ρ 1 (CL A packing 6-colouring of CL 14 is given by the following pattern:

1 3 1 2 1 5 1 2 1 4 1 3 1 6 2 1 4 1 3 1 6 1 3 1 2 1 5 1
This completes the proof of Theorem 7.

H-graphs

The H-graph H(r), r ≥ 2, is the 3-regular graph of order 6r, with vertex set

V (H(r)) = {u i , v i , w i : 0 ≤ i ≤ 2r -1},
and edge set (subscripts are taken modulo 2r)

E(H(r)) = {(u i , u i+1 ), (w i , w i+1 ), (u i , v i ), (v i , w i ) : 0 ≤ i ≤ 2r -1} ∪ {(v 2i , v 2i+1 ) : 0 ≤ i ≤ r -1}. u 0 w 0 v 0 u 1 w 1 v 1 u 2 w 2 v 2 u 3 w 3 v 3 u 4 w 4 v 4 u 5 w 5 v 5 u 6 w 6 v 6 u 7 w 7 v 7
Figure 4: The H-graph H(4).

Figure 4 depicts the H-graph H(4). These graphs have been introduced and studied by William and Roy in [START_REF] William | Packing chromatic number of certain graphs[END_REF], where it is proved that χ ρ (H(r)) ≤ 5 for every H-graph H(r) with even r ≥ 4.

We complete their result in Theorem 10 below.

We rst prove a technical lemma. For every pair of integers r ≥ 2 and 0 ≤ i ≤ r-1, we denote by G i (r) the subgraph of H(r) induced by the set of vertices {u 2i , u 2i+1 , v 2i , v 2i+1 , w 2i , w 2i+1 }.

Observe that for every r ≥ 2, all the subgraphs G i (r) are isomorphic to the graph depicted in Figure 5(a), and thus χ ρ (G i (r)) = χ ρ (P 2 P 3 ) = 4 [START_REF] Goddard | Broadcast chromatic numbers of graphs[END_REF].

For a given packing 5-colouring π of H(r), we denote by π(G i (r)) the set of colours assigned to the vertices of G i (r). We then have the following result. Lemma 8 For every integer r ≥ 3 and every packing 5-colouring

π of H(r), π(G i (r)) ∩ π(G i+1 (r)) = {1, 2, 3} for every i, 0 ≤ i ≤ r -1.
Proof. Since χ ρ (P 2 P 3 ) = 4, every packing 5-colouring of H(r) must use colour 4 or colour 5 on every G i (r), 0 ≤ i ≤ r -1. We now prove that if colour 4 (resp. colour 5) is used on G i (r), then colour 4 (resp. colour 5) cannot be used on G i+1 (r). Observe rst that every vertex of G i (r) is at distance at most 5 from every vertex of G i+1 (r). Therefore, colour 5 cannot be used on both G i (r) and G i+1 (r). Suppose now that colour 4 is used on both G i (r) and G i+1 (r). Up to symmetries, we necessarily have one of the two following cases.

1. π(u 2i ) = π(w 2i+3 ) = 4 (see Figure 5(b)).

Since every vertex of G i-1 (r) is at distance at most 4 from u 2i , it follows that G i-1 (r) does not contain the colour 4. This implies that G i-1 (r) contains the colour 5 since χ ρ (G i-1 (r)) > 3. By symmetry, G i+2 (r) must also contain the colour 5. Furthermore, since two consecutive G i (r)s cannot both use colour 5, neither G i (r) nor G i+1 (r) contains the colour 5. Now, on the remaining uncoloured vertices of G i (r), colour 1 can be used at most thrice, colour 2 at most twice and colour 3 at most once. If colour 1 is used thrice, then we

necessarily have π(u 2i+1 ) = π(v 2i ) = π(w 2i+1 ) = 1, so that {π(v 2i+1 ), π(w 2i )} = {2, 3},
and no colour is available for w 2i+2 (recall that colour 5 is not used on G i+1 (r)). If colour 1 is used twice, then we necessarily have, up to symmetry, π(v 2i ) = π(w 2i+1 ) = 1, π(u 2i+1 ) = π(w 2i ) = 2, and π(v 2i+1 ) = 3, and no colour is available for w 2i+2 .

2. π(v 2i ) = π(v 2i+3 ) = 4 (see Figure 5(c)).

Similarly as before, since every vertex of G i-1 (r) is at distance at most 4 from v 2i and two consecutive G i (r)'s cannot both use colour 5, it follows from the rst item of Lemma 8 that colour 5 is used neither on G i (r), nor, by symmetry, on G i+1 (r). Again, on the remaining uncoloured vertices of G i (r), colour 1 can be used at most thrice, colour 2 at most twice and colour 3 at most once. If colour 1 is used thrice, then we

necessarily have π(u 2i ) = π(v 2i+1 ) = π(w 2i ) = 1, so that {π(u 2i+1 ), π(w 2i+1 )} = {2, 3}.
Up to symmetry, we may assume π(u 2i+1 ) = 2 and π(w 2i+1 ) = 3, which implies π(u 2i+2 ) = 1, and no colour is available for v 2i+2 (recall that colour 5 is not used on G i+1 (r)). If colour 1 is used twice, then we necessarily have, up to symmetry, π(u 2i+1 ) = π(w 2i ) = 1, π(u 2i ) = π(w 2i+1 ) = 2, and π(v 2i+1 ) = 3, and no colour is available for u 2i+2 .

This completes the proof.

From Lemma 8, it follows that every G i (r) must use colour 4 or 5, and that no two consecutive G i (r)'s can use the same colour from {4, 5}. Therefore, H(r) does not admit any packing 5colouring when r is odd. Corollary 9 For every odd integer r, r ≥ 3, χ ρ (H(r)) > 5.

We are now able to prove the main result of this section.

Theorem 10 For every integer r ≥ 2, χ ρ (H(r)) = 5 if r is even, and 6 ≤ χ ρ (H(r)) ≤ 7 if r is odd.

Proof. We consider two cases, according to the parity of r.

1. r is even.

Since H(r) contains the corona graph C 6 K 1 as a subgraph (consider for instance the 6-cycle u 1 v 1 w 1 w 2 v 2 u 2 ), we get χ ρ (H(r)) ≥ 5 by Theorem 3 and Proposition 2. A packing 5-colouring of H(r) is then obtained by repeating the pattern depicted in Figure 6(a), and thus χ ρ (H(r)) = 5.

r is odd.

From Corollary 9, we get χ ρ (H(r)) ≥ 6. A packing 7-colouring of H(r) is described in times. This gives χ ρ (H(r)) ≤ 7.

This concludes the proof. 5

Generalised H-graphs

We now consider a natural extension of H-graphs. For every integer r ≥ 2, the generalised H-graph H (r) with levels, ≥ 1, is the 3-regular graph of order 2r( + 2), with vertex set

V (H (r)) = {u i j : 0 ≤ i ≤ + 1, 0 ≤ j ≤ 2r -1}
and edge set (subscripts are taken modulo 2r)

E(H (r)) = {(u 0 j , u 0 j+1 ), (u +1 j , u +1 j+1 ) : 0 ≤ j ≤ 2r -1} ∪ {(u i 2j , u i 2j+1 ) : 1 ≤ i ≤ , 0 ≤ j ≤ r -1} ∪ {(u i j , u i+1 j ) : 0 ≤ i ≤ , 0 ≤ j ≤ 2r -1}.
Figure 7 depicts the generalised H-graph with three levels H 3 (4). Note that generalised H-graphs with one level are precisely H-graphs.

The three following lemmas will be useful for determining the packing chromatic number of generalised H-graphs. Lemma 11 For every pair of integers ≥ 3 and r ≥ 3, let H (r) be a generalised H-graph with χ ρ (H (r)) ≤ 5 and let π be a packing 5-colouring of H (r). For every edge u i 2j u i 2j+1 , 1 ≤ i ≤ , 0 ≤ j ≤ r -1, with π(u i 2j ) = 1 and π(u i 2j+1 ) = 1, either u i 2j or u i 2j+1 has colour 2 and its three neighbours have colours 3, 4 and 5.

Proof. We rst claim that every such edge u i 2j u i 2j+1 belongs to a subgraph of H (r) isomorphic to the graph X depicted in Figure 2, in such a way that u i 2j u i 2j+1 corresponds to one of the edges 2,3 x Lemma 15 For every pair of integers ≥ 3 and r ≥ 3, if H (r) is a generalised H-graph with χ ρ (H (r)) ≤ 5, then there exists a packing 5-colouring π of H (r) such that π(u 0 j ) / ∈ {4, 5} and π(u +1 j ) / ∈ {4, 5} for every j, 0 ≤ j ≤ 2r -1.

Proof. Let π be a packing 5-colouring of H (r) such that colour 1 is used on each edge of H (r)

(the existence of such a colouring is ensured by Corollary 14). Thanks to the symmetries of H (r), it suces to prove the result for any vertex u 0 2j , 0 ≤ j ≤ r -1. Suppose to the contrary that π(u 0 2j ) ∈ {4, 5} for some j, 0 ≤ j ≤ r -1. We have two cases to consider.

1. π(u 0 2j ) = 4. Let Y be the subgraph of H (r) depicted in Figure 8, where the vertex u 0 2j is the unique vertex with colour 4, and vertices with colour 1 are drawn as big vertices. Observe that the three neighbours of x, as well as the three neighbours of y, must use colours 2, 3 and 5. Therefore, the common neighbour of x and y must be assigned colour 5. It then follows that no colour is available for z.

2. π(u 0 2j ) = 5.

The proof is similar to the proof of the previous case, by switching colours 4 and 5.

This completes the proof.

Let H (r) be a generalised H-graph satisfying the hypothesis of Lemma 15, and π be a packing 5-colouring of H (r). From Lemma 15, it follows that the restriction of π to the 2rcycle induced by the set of vertices {u 0 j | 0 ≤ j ≤ 2r -1} is a packing 3-colouring. It is not dicult to check (see [START_REF] Laïche | Packing colouring of some undirected and oriented coronae graphs[END_REF]) that a 2r-cycle admits a packing 3-colouring if and only if r is even. Therefore, we get the following corollary. Corollary 16 For every pair of integers ≥ 3 and r ≥ 3, r odd, χ ρ (H (r)) ≥ 6.

We are now able to prove the main results of this section. We rst consider the case of generalised H-graphs H (r) with / ∈ {2, 5}.

Theorem 17 For every pair of integers ≥ 3, = 5, and r ≥ 2,

χ ρ (H (r)) = 5 if r is even, 6 otherwise. 1 2 1 3 3 1 2 1 4 1 5 1 1 3 1 2 2 1
|0 ≤ i ≤ + 1} ∪ {u i 2 |0 ≤ i ≤ + 1}), we get χ ρ (H (r)) ≥ χ ρ (C 2 +4 K 1 ) = 5
by Theorem 3 and Proposition 2. We now prove χ ρ (H (r)) ≤ 5. Figure 9 depicts a packing 5-colouring of H 4 (2), together with its corresponding colouring pattern. It can easily be checked that this (6 × 4)-pattern is periodic, that is, can be repeated, both vertically and horizontally, to produce a packing 5-colouring of any generalised H-graph of the form H 6i+4 (2j), with i ≥ 0 and j ≥ 1.

If ≡ 4 (mod 6), we use the colouring patterns depicted in Figure 10, depending on the value of modulo 6. The upper six rows of each colouring pattern, surrounded by double lines, can be repeated as many times as required, or even deleted when ≡ 1, 2, 3 (mod 6).

Therefore, these colouring patterns give us a packing 5-colouring of any generalised Hgraph of the form H (2), for every ≥ 3, = 5. It is again easy to check that each of these colouring patterns is horizontally periodic, that is, can be horizontally repeated in order to get a packing 5-colouring of any generalised H-graph of the form H (r), for every ≥ 3, = 5, ≡ 4 (mod 6), and even r.

2. r is odd.

The inequality χ ρ (H (r)) ≥ 6 directly follows from Corollary 16. Therefore, we only need to prove the inequality χ ρ (H (r)) ≤ 6 (recall that ≥ 3 and = 5).

We rst consider a few particular cases. A packing 6-colouring of H 3 (3) is depicted in Figure 11(a), and a packing 6-colouring of H 3 (r), for every odd r ≥ 5, is depicted in In order to produce a packing 6-colouring of H (r), with ≥ 8, r ≥ 3, and r odd, we use the colouring patterns depicted in Figures 13 and14. In both these gures, the four columns surrounded by double lines must be repeated r-3 2 times (and thus do not appear if r = 3) or r-5 2 times when = 9 and r ≥ 5 (and thus do not appear if r = 5). In Figure 14, the six rows surrounded by double lines must be repeated This completes the proof. The last two theorems of this section deal with the cases not covered by Theorem 17, that is, = 2 and = 5, respectively.

(a) H 4 (3) (b) H 4 (r), r ≥ 5, r odd (c) H 6 (r), r ≥ 3,
Theorem 18 For every integer r ≥ 2,

χ ρ (H 2 (r)) = 7 if r ∈ {2, 4, 7, 8, 11}, 6 otherwise.
Proof. The fact that H 2 (r) does not admit a packing 6-colouring for every r ∈ {2, 4, 7, 8, 11}

has been checked by a computer program, using brute-force search. Packing 7-colourings for each of these graphs are depicted in Figure 15.

Assume now r / ∈ {2, 4, 7, 8, 11}. We checked by a computer program, again using brute-force search, that the subgraph of such a generalised H-graph induced by three successive ladders, that is, by the set of vertices {u j i | 0 ≤ i ≤ 5, 0 ≤ j ≤ 3}, does not admit a packing 5-colouring.

Packing 6-colourings of such generalised H-graphs are depicted in Figure 16, according to the value of r, r modulo 3, or r modulo 6 (periodic patterns, made of 6 or 12 columns, are surrounded by double lines).

Theorem 19 For every integer r ≥ 2, χ ρ (H 5 (r)) = 6.

Proof. Again, we checked by a computer program, using brute-force search, that both H 5 (2) and the subgraph of H 5 (r), r ≥ 5, induced by three successive ladders, that is, by the set of vertices {u j i | 0 ≤ i ≤ 5, 0 ≤ j ≤ 6}, do not admit a packing 5-colouring. Packing 6-colourings of H 5 (r), r ∈ {2, 3, 5}, are depicted in Figure 17, while packing 6-colourings of H 5 (r), r = 4 or r ≥ 6, are depicted in Figure 18 according to the value of r modulo 4, or r modulo 6 (periodic patterns, made of eight or twelve columns, are surrounded by double lines and are repeated at least once when r ≡ 0 (mod 4) or r ≡ 3 (mod 6)). [START_REF] Goddard | Broadcast chromatic numbers of graphs[END_REF]

Discussion

In this paper, we have studied the packing chromatic number of some classes of cubic graphs, namely circular ladders, H-graphs and generalised H-graphs. We have determined the exact value of this parameter for every such graph, except for the case of H-graphs H(r) with r ≥ 3, r odd (see Theorem 10), for which we proved 6 ≤ χ ρ (H(r)) ≤ 7. Using a computer program, we have checked that χ ρ (H(r)) = 7 for every odd r up to r = 13. We thus propose the following question.

Question 1 Is it true that χ ρ (H(r)) = 7 for every H-graph H(r) with r ≥ 3, r odd?

In [START_REF] Laïche | On the Packing colouring of Undirected and Oriented Generalized Theta Graphs[END_REF][START_REF] Laïche | Packing colouring of some undirected and oriented coronae graphs[END_REF], we have extended the notion of packing colouring to the case of digraphs. If D is a digraph, the (weak) directed distance between two vertices u and v in D is dened as the length of a shortest directed path between u and v, in either direction. Using this notion of distance in digraphs, the packing colouring readily extends to digraphs. Recall that an orientation of an undirected graph G is any antisymmetric digraph obtained from G by giving to each edge of G one of its two possible orientations. It then directly follows from the denition that χ ρ (D) ≤ χ ρ (G) for any orientation D of G. A natural question for oriented graphs, related to this work, is then the following.

Question 2 Is it true that the packing chromatic number of any oriented graph with maximum degree 3 is bounded by some constant?

Figure 1 :

 1 Figure 1: The circular ladder CL 7 .

Figure 2 :

 2 Figure 2: The graph X.

Figure 3 :

 3 Figure 3: Optimal packing colouring of CL 3 , CL 4 and CL 5 .

Figure 5 :

 5 Figure 5: The subgraph G i (r) and two congurations for the proof of Lemma 8.

Figure 6 (

 6 Figure 6(b), where the circular pattern (surrounded by the dashed box) is repeated r-3 2

3 Figure 6 :

 36 Figure 6: Packing colouring patterns for H-graphs.

zFigure 8 :

 8 Figure 8: The subgraph Y of H (r).

Figure 11 ( 5 2- 3 2

 1153 Figure 11(b) (the rst four columns, surrounded by a double line, are repeated r-5 2 times, and thus do not appear if r = 5). A packing 6-colouring of H 4 (3) is depicted in Figure 12(a), and a packing 6-colouring of H 4 (r), for every odd r ≥ 5, is depicted in Figure 12(b) (the rst four columns are repeated r-5 2 times). A packing 6-colouring of H 6 (r), for every odd r ≥ 3, is depicted in Figure 12(c) (the four columns surrounded by a double line are repeated r-3 2 times, and thus do not appear if r = 3). A packing 6-colouring of H 7 (3) is depicted in Figure 12(d), and a packing 6-colouring of H 7 (r), for every odd r ≥ 5, is depicted in Figure 12(e) (the four columns surrounded by a double line, are repeated r-3 2

- 6 -

 6 ( mod 6) 6 times (and thus do not appear if = 8).

Figure 15 :

 15 Figure 15: Packing 7-colourings of H 2 (r), r ∈ {2, 4, 7, 8, 11}.

Figure 18 :

 18 Figure 18: Colouring patterns for H 5 (r), r = 4 or r ≥ 6.

Figure 21 :

 21 Figure 21: Congurations for the proof of Claim 2 (the double edge is the edge u 0 2 u 0 3 ).

  Note that ρ 1 (CL 8 ) = 8, ρ 2 (CL 8 ) = 4, ρ 3 (CL 8 ) = ρ 4 (CL 8 ) = 2, and ρ i (CL 8 ) = 1 for every i ≥ 5. However, if we use eight times colour 1, colour 2 can be used at most twice, and then colour 4 at most once. On the other hand, if we use seven times colour 1, then, either colour 2 is used thrice, and then colour 4 can be used at most once, or colour 2 is used at most twice, and then colour 4 can be used at most twice. Hence, at most 15 vertices of CL 8 can be coloured with a colour in {1, . . . , 6}

and the claim follows.

  Figure 9: A packing 5-colouring of H 4 (2) and its corresponding colouring pattern. Colouring patterns for H 3 (3) and for H 3 (r), r ≥ 5, r odd.1. r is even. Since the corona graph C 2 +4 K 1 is a subgraph of H (r) for every r ≥ 2 (consider the cycle of length 2 + 4 induced by the set of vertices {u i 1

		13 12 16	12 13 12 15 12 61 23
		21 51 41	41 51 41 31 31 14 51
		14 23 12	13 12 13 14 14 23 12
		31 14 31	51 41 21 21 21 51 41
		12 61 25	12 13 15 16 13 12 13
		(a)	(b)	12 13
	Figure 11:	3	1	21 31 41 51 13 12
	1	5 1	4	15 14 31 21
	12 13	12 13	12 13	12 13	12 13
	41 51	41 51	41 51	41 51	41 51
	13 12	13 12	13 12	13 12	13 12
	21 31	21 31	21 31	21 31	21 31
	15 14	15 14	15 14	15 14	15 14
	31 21	31 21	31 21	31 21	31 21
	14 15	12 13	12 13	12 13	14 15
	21 31	41 51	41 51	41 51	21 31
		13 12	13 12	13 12	13 12
			51 41	51 41	51 41
			12 13	12 13	12 13
			31 21		41 51
			14 15		13 12
			21 31
			15 14
			31 21
	≡ 0 (mod 6)	≡ 1 (mod 6)	≡ 2 (mod 6)	≡ 3 (mod 6)	≡ 5 (mod 6)
	Figure 10: Colouring patterns for H (r), r even.

  r odd Colouring patterns for H 4 (r), H 6 (r) and H 7 (r), r ≥ 3, r odd. Figure 13: Colouring patterns for H (r), 9 ≤ ≤ 11, r ≥ 3, r odd.Figure 14: Colouring patterns for H (r), = 8 or ≥ 12, r ≥ 3, r odd.

	12 13 12 13 16 13 16 21 21	12 13 12 13 16 13 16 12 15 13 16 14 12 17 14 15 12 13 12 13 16 21 21 31 31 21 21 21 51 31 21 31
	41 51 41 51 21 14 17	41 51 41 51 21 14 13 14 12 14 13 13 13 12 13 12 41 51 41 51 21
	13 12 13 12 13 31 51	13 12 13 12 13 31 51 21 71 31 51 71 21 41 51 61 13 12 13 12 13
	21 31 21 31 41	21 31 21 31 41		21 31 21 31 41
	15 14 15 14 12 r = 2	15 14 15 14 12 r = 4	15 14 15 14 12 r = 7
	31 21 31 21 31	31 21 31 21 31		31 21 31 21 31
	12 13 14 31 51 21 16 12 15 21 31 31 14 14 16 31 21 21 15 13 13 21 61 51 13 12 14 (d) H 7 (3) 21 51 41 14 13 12 31 21 31 12 14 15 51 31 21 21 51 41 14 23 12 31 14 31 12 61 25 = 9, r = 3 13 12 16 12 13 12 15 12 61 23 12 13 15 12 16 51 41 21 31 31 13 12 13 14 12 21 31 61 21 51 14 15 14 15 13 31 21 31 31 21 12 13 12 12 14 51 41 51 41 31 13 12 13 16 12 41 51 41 31 31 14 51 13 12 13 14 14 23 12 21 31 21 21 21 51 31 15 14 15 13 13 12 14 31 21 31 51 51 31 21 41 51 41 31 31 21 51 13 12 13 14 14 13 12 51 41 21 21 21 51 41 12 13 15 16 13 12 13 12 13 12 13 16 41 51 41 51 21 13 12 13 12 13 21 31 21 31 41 15 14 15 14 12 31 21 31 21 31 41 51 41 51 21 13 12 13 12 14 21 31 21 31 31 15 14 15 14 12 31 21 31 21 61 = 9, r ≥ 5 = 10, r ≥ 3 41 51 31 12 13 12 51 41 51 13 12 13 21 31 21 14 15 14 31 21 61 15 14 12 21 31 51 13 12 13 61 51 21 12 13 14 13 12 13 12 16 41 51 41 51 31 12 13 12 13 12 51 41 51 41 51 13 12 13 12 13 21 31 21 31 21 14 15 14 15 14 31 21 31 21 61 15 14 15 14 12 21 31 21 31 51 13 12 13 12 13 21 31 21 31 31 41 51 41 51 21 31 21 31 21 51 12 13 12 13 14 14 15 14 15 15 12 13 12 13 14 14 15 14 15 13 61 51 41 51 21 12 13 12 13 15 41 51 41 51 21 13 12 13 12 13 21 41 51 41 41 15 13 12 13 12 31 21 31 21 61 41 31 21 31 21 12 13 12 13 15 41 51 41 51 21 13 12 13 12 16 21 31 21 31 41 15 14 15 14 13 31 21 31 21 21 61 51 41 51 31 13 12 13 12 14 12 13 12 13 15 41 51 41 51 21 13 12 13 12 16 51 41 51 41 31 12 13 12 13 14 31 21 31 21 21 21 31 21 31 51 15 14 15 14 12 31 21 31 21 61 ≡ 0 (mod 6) ≡ 1 (mod 6) ≡ 2 (mod 6) ≥ 12 ≥ 13 ≥ 8 12 13 12 13 16 41 51 41 51 21 13 12 13 12 13 21 31 21 31 41 15 14 15 14 12 31 21 31 21 31 12 13 12 13 15 41 51 41 51 61 13 12 13 12 12 51 41 51 41 41 12 13 12 13 13 31 21 31 21 21 12 13 12 13 16 41 51 41 51 21 13 12 13 12 15 21 31 21 31 31 15 14 15 14 12 31 21 31 21 41 12 13 12 13 13 41 51 41 51 21 13 12 13 12 15 21 31 21 31 61 15 14 15 14 12 31 21 31 21 31 13 12 13 12 16 41 51 41 51 31 12 13 12 13 12 31 21 31 21 41 15 14 15 14 13 21 31 21 31 21 13 12 13 12 15 41 51 41 51 31 12 13 12 13 12 51 41 51 41 61 13 12 13 12 14 21 31 21 31 21 13 16 13 12 17 13 12 15 21 21 21 54 31 21 41 31 14 13 14 21 14 15 13 12 31 51 71 36 21 31 21 61 13 16 13 12 14 13 16 14 12 17 15 21 21 21 51 31 21 21 21 31 31 31 14 13 14 13 12 15 13 13 15 12 12 31 51 71 21 61 31 41 71 21 41 61 (e) H 13 12 16 13 12 13 12 13 12 12 12 14 13 12 13 12 13 15 12 15 14 15 13 12 13 12 13 15 14 15 14 15 13 r = 8 r = 11
	= 11, r = 3 13 12 13 12 14 13 12 13 12 15 = 11, r ≥ 5 51 41 51 41 21 21 31 21 31 31	15 14 15 14 12 21 31 21 31 41
	12 13 12 13 16	15 14 15 14 12		13 12 13 12 13
		31 21 31 21 61		41 51 41 51 21
				12 13 12 13 16
	≡ 3 (mod 6)	≡ 4 (mod 6)		≡ 5 (mod 6)
	≥ 15	≥ 16		≥ 17

7

(r), r ≥ 5, r odd Figure

12:

Proof. We consider two cases, according to the parity of r.

Acknowledgment. This work has been done while the rst author was visiting LaBRI, whose hospitality is gratefully acknowledged.

u 3 v 3 , u 4 v 4 or u 5 v 5 of X. Indeed, consider rst the extremal case of H 3 (3), and observe that X is a subgraph of the subgraph of H 3 (3) induced by the set of vertices {u 0 0 , . . . , u 0 5 } ∪ {u 4 0 , . . . , u 4 5 } ∪ {u 1 2 , u 1 3 , u 2 2 , u 2 3 , u 3 2 , u 3 3 }.

Our claim then follows for H 3 (3) thanks to its symmetries.

It is now easy to see that our claim holds for every generalised H-graph H (r) with , r ≥ 3.

The result then follows by Lemma 4.

From Lemma 11, it follows that if π(u i 2j ) = 1 and π(u i 2j+1 ) = 1 for some edge u i 2j u i 2j+1 of H (r), 1 ≤ i ≤ , 0 ≤ j ≤ r -1, then the colour 2 has to be used on this edge and, since the neighbours of the 2-coloured vertex are coloured with 3, 4 and 5, the colour 2 can be replaced by colour 1. Therefore, we get the following corollary.

Corollary 12 For every pair of integers ≥ 3 and r ≥ 3, if H (r) is a generalised H-graph with χ ρ (H (r)) ≤ 5, then there exists a packing 5-colouring of H (r) such that, for every pair of integers i and j, 1 ≤ i ≤ , 0 ≤ j ≤ r -1, the colour 1 is used on the edge u i 2j u i 2j+1 of H (r).

Lemma 13 For every pair of integers ≥ 3 and r ≥ 3, let H (r) be a generalised H-graph with χ ρ (H (r)) ≤ 5 and π be a packing 5-colouring of H (r). For every j, 0 ≤ j ≤ 2r -1, π must assign colour 1 to one vertex of each of the edges u 0 j u 0 j+1 and u +1 j u +1 j+1 (subscripts are taken modulo 2r).

Proof. The proof is done by case analysis and is given in Appendix B.

Let H (r) be a generalised H-graph with χ ρ (H (r)) ≤ 5. From Corollary 12 and Lemma 13, it follows that one can always produce a packing 5-colouring of H (r) that uses colour 1 on each edge u i 2j u i 2j+1 of H (r), 0 ≤ i ≤ + 1, 0 ≤ j ≤ r -1. Since adjacent vertices cannot be assigned the same colour and H (r) is a bipartite graph, we get the following corollary. Corollary 14 For every pair of integers ≥ 3 and r ≥ 3, if H (r) is a generalised H-graph with χ ρ (H (r)) ≤ 5, then there exists a packing 5-colouring of H (r) such that the colour 1 is used on each edge of H (r).

A Proof of Lemma 4

The congurations used in the proof correspond to partial colourings of the graph X and are depicted in Figures 19 and20, with the following drawing convention. If {a, b} is the set of colours assigned to two distinct vertices, then the colour of both these vertices is denoted a, b. If the same conguration describes two partial colourings of X and the colours assigned to some vertex by these two colourings are respectively a and b, then the colour of this vertex is denoted a|b. Finally, if a vertex has no available colour, its colour is denoted ?.

Suppose that for some i, 3 ≤ i ≤ 5, π(u i ) = 1 and π(v i ) = 1. We rst prove the following claim.

Claim 1 2 ∈ {π(u i ), π(v i )}.

Proof. Assume to the contrary that this is not the case, that is, {π

Thanks to the symmetry exchanging u i and v i , we may assume π(u i ) < π(v i ), without loss of generality. Recall that there is no edge

We consider the following cases (subscripts are taken modulo n).

In that case, we necessarily have π(u i+1 ) ∈ {1, 2, 5}.

, so that π(u i-1 ) = 2 and no colour is available for v i-2 (see Figure 19(a)). If π(u i+2 ) = 2 (and π(v i+1 ) = 5), then {π(u i-1 ), π(v i-1 )} = {1, 2}, and no colour is available either for u i-2 or for v i-2 (see Figure 19

and no colour is available for u i-2 (see Figure 19(c)). If π(v i+1 ) = 1, then either π(u i-1 ) = Figure 19: Congurations for the proof of Lemma 4 (the double edge is the edge u i v i ). This completes the proof of Claim 1.

By Claim 1, we can thus assume π(u i ) = 2, without loss of generality (again, thanks to the symmetry exchanging u i and v i ), so that π(v i ) ∈ {3, 4, 5}. To nish the proof of Lemma 4, we need to prove that {π(u i-1 ), π(u i+1 )} = {3, 4, 5} \ {π(v i )}. Suppose that this is not the case. We consider the following cases, according to the value of π(v i ).

In that case, we necessarily have π(u i+1 ) ∈ {1, 4, 5}.

If π(u i+1 ) = 1, then {π(u i+2 ), π(v i+1 )} = {4, 5}, so that π(u i-1 ) = 1, and no colour is available for v i-1 (see Figure 20(a)).

If π(u i+1 ) = 4, then either π(u i-1 ) = 1, so that π(v i-1 ) = 5, and no colour is available for u i-2 (see Figure 20(b)), or π(u i-1 ) = 5, which contradicts our assumption since it would imply {π(u i-1 ), π(u i+1 )} = {3, 4, 5} \ {π(v i )}.

Similarly, if π(u i+1 ) = 5, then either π(u i-1 ) = 1, so that π(v i-1 ) = 4, and no colour is available for u i-2 (see Figure 20(c)), or π(u i-1 ) = 4, which again contradicts our assumption.

2. π(v i ) = 4 (the case π(v i ) = 5 is similar, by switching colours 4 and 5).

In that case, we necessarily have π(u i+1 ) ∈ {1, 3, 5}.

, and no colour is available for v i-1 . If π(u i+2 ) = 5 and π(v i+1 ) = 3, then π(v i-1 ) = 1, and no colour is available for u i-1 (see Figure 20(d)).

If π(u i+1 ) = 3, then either π(u i-1 ) = 1, so that π(v i-1 ) = 5, and no colour is available for u i-2 , or π(u i-1 ) = 5, which contradicts our assumption (see Figure 20(e)).

Finally, if π(u i+1 ) = 5, then either π(u i-1 ) = 1, so that π(v i-1 ) = 3, and no colour is available for u i-2 , or π(u i-1 ) = 3, which contradicts our assumption (see Figure 20(f )).

This completes the proof of Lemma 4.

B Proof of Lemma 13

We rst prove the following claim.

Claim 2 For every integer j, 0 ≤ j < r, either π(u 0 2j ) = 1 or π(u 0 2j+1 ) = 1. Proof. Thanks to the symmetries of H (r), it is enough to prove the claim for the edge u 0 2 u 0 3 .

Suppose to the contrary that π(u 0 2 ) = 1 and π(u 0 3 ) = 1. Thanks to the symmetries of H (r), we can assume π(u 0 2 ) < π(u 0 3 ), without loss of generality.

We consider four cases. The corresponding congurations are depicted in Figure 21, using the same drawing convention as for the proof of Lemma 4 (see Appendix A).

1. π(u 0 2 ) = 2 and π(u 0 3 ) = 3.

3 )} = {4, 5}, which implies π(u 0 1 ) = 1, and no colour is available for u 0 0 (see Figure 21(a)). If π(u 1 2 ) = 4, then either π(u 0 1 ) = 1, which implies π(u 0 0 ) = 5, and no colour is available for u 1 1 , or π(u 0 1 ) = 5, which implies π(u 0 4 ) = 1, π(u 0 5 ) = 2, and no colour is available for u 1 4 (see Figure 21(b)). The case π(u 1 2 ) = 5 is similar, by switching colours 4 and 5. 2. π(u 0 2 ) = 2 and π(u 0 3 ) = 4 (the case π(u 0 2 ) = 2 and π(u 0 3 ) = 5 is similar, by switching colours 4 and 5).

, and no colour is available for u 1 1 (see Figure 21(c)). If π(u 1 2 ) = 3, then either π(u 0 1 ) = 1, which implies π(u 0 0 ) = 5, and no colour is available for u 1 1 , or π(u 0 1 ) = 5, which implies π(u 2

2 ) = π(u 1 3 ) = 1, so that π(u 2 3 ) = 2, and no colour is available for u 3 2 (see Figure 21(d)). Finally, if π(u 1 2 ) = 5, then either π(u 0 1 ) = 1, which implies π(u 0 0 ) = 3, and no colour is available for u 1 1 , or π(u 0 1 ) = 3, which implies π(u 1 1 ) = 1, π(u 2 1 ) = 2, and no colour is available for u 1 0 (see Figure 21(e)).

π(u 0

2 ) = 3 and π(u 0 3 ) = 4.

3 )} = {2, 5}, and thus either π(u 0 1 ) = 1, so that π(u 0 0 ) = 2, and no colour is available for u 1 1 , or π(u 0 1 ) = 2, so that π(u 0 0 ) = 1, and no colour is available for u 1 0 (see Figure 21(f )). If π(u 1 2 ) = 2, then either π(u 2 2 ) = 1, which implies π(u 3 2 ) = 5, and no colour is available for u 2 3 , or π(u 2 2 ) = 5, which implies π(u 1

3 ) = 1, and no colour is available for u 2 3 (see Figure 21(g)). Finally, if π(u 1 2 ) = 5, then either π(u 0 1 ) = 1, which implies π(u 0 0 ) = 2, and no colour is available for u 1 1 , or π(u 0 1 ) = 2, which implies π(u 1 1 ) = 1, and no colour is available for u 2 1 (see Figure 21(h)).

4. π(u 0 2 ) = 3 and π(u 0 3 ) = 5. This case is similar to the previous one, by switching colours 4 and 5, except when π(u 1 2 ) = 1 (which implies {π(u 2

2 ), π(u 1 3 )} = {2, 4}) and π(u 0 1 ) = 2. In that case, we necessarily have π(u 0 0 ) = π(u 1 1 ) = 1, which implies π(u 1 0 ) = 4, and no colour is available for u 2 1 (see Figure 21(i)).

5. π(u 0 2 ) = 4 and π(u 0 3 ) = 5.

3 ) = 1, and no colour is available for u 3 3 (see Figure 21(j)). If π(u 1 2 ) = 2, then either π(u 0 1 ) = 1, which implies {π(u 0 0 ), π(u 1 1 )} = {2, 3}, so that π(u 1 0 ) = 1, and no colour is available for u 2 0 , or π(u 0 1 ) = 3, which implies π(u 2 2 ) = π(u 1 3 ) = 1, so that π(u 2 3 ) = 3, and no colour is available for u 3 2 (see Figure 21(k)). Finally, if π(u 1 2 ) = 3, then either π(u 0 1 ) = 1, which implies π(u 0 0 ) = 2, and no colour is available for u 1 1 , or π(u 0 1 ) = 2, which implies π(u 0 0 ) = π(u 1 1 ) = 1, so that π(u 1 0 ) = 3, and no colour is available for u 2 1 (see Figure 21(l)).

This completes the proof of Claim 2.

Since the cycle induced by the set of vertices {u 0 0 , u 0 1 , . . . , u 0 2r-1 } has even length, and adjacent vertices cannot be assigned the same colour, it follows from Claim 2 that colour 1 must be used on each edge u 0 j u 0 j+1 , 0 ≤ j ≤ 2r -1 (subscripts are taken modulo 2r). By symmetry, colour 1 must also be used on each edge u +1 j u +1 j+1 , 0 ≤ j ≤ 2r -1. This concludes the proof of Lemma 13.


Romain Fontaine
email: romain.fontaine@insa-lyon.fr

Laure Gonnord
email: laure.gonnord@ens-lyon.fr

Lionel Morel
email: lionel.morel@cea.fr

Polyhedral DataFlow Programming, a Case

Keywords: parallelism, dataflow programming, compilation, runtime system, load-balancing

Dataflow languages expose the application's potential parallelism naturally and have thus been studied and developped for the past thirty years as a solution for harnessing the increasing hardware parallelism. However, when generating code for parallel processors, current dataflow compilers only take into consideration the overall dataflow network of the application. This leaves out the potential parallelism that could be extracted from the internals of agents, typically when those include loop nests, for instance, but also potential application of intra-agent pipelining, or task spliting and rescheduling.

In this work, we study the benefits of jointly using polyhedral compilation with dataflow languages. More precisely, we propose to expend the parallelization of dataflow programs by taking into account the parallelism exposed by loop nests describing the internal behavior of the program's agents. This approach is validated through the development of a prototype toolchain based on an extended version of the ΣC language. We demonstrate the benefit of this approach and the potentiality of further improvements on relevant case studies.

I. INTRODUCTION

Multi-core processors are everywhere, from high-end servers to user-oriented embedded systems like cellphones or task-specific accelerators. Applications that need to take advantage of the parallelism offered by these hardware are now numerous and range from latency-sensitive compression/decompression algorithms (eg video processing) to compute-intensive ones like machine-learning algorithms.

Programming these applications and taking advantage of the hardware parallelism is still a considerable challenge from the programmer's point-of-view. For some of these applications, dataflow programming is a premier choice because this programming style naturally fits the designer abstraction model. As a plus, dataflow is amenable to quite efficient parallelization because it naturally exposes task, data and pipeline parallelism.

In a dataflow programming language, programmers describe their application as a set of side-effect-free actors or agents that communicate solely through First-In-First-Out Part of this work was carried out while Lionel Morel was with INSA Lyon, Université de Lyon. channels (FIFOs). Agents can be seen as independent processes, ie sequential programs, that interact through reading (resp. writing) data from (resp. to) their input (resp. output) FIFOs. There exists a large panel of dataflow languages, whose characteristics differ notably. One major point of variability is the scheduling of agents and their communications. There is indeed a continuum from the synchronous dataflow languages like Lustre [START_REF] Halbwachs | The synchronous data flow programming language lustre[END_REF] or Streamit [START_REF] Thies | Language and compiler support for stream programs[END_REF], where the scheduling is fully static, to general communicating networks like KPNs [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] or RVC-Cal [START_REF] Amer | Reconfigurable video coding on multicore[END_REF] where a dedicated runtime is responsible for scheduling tasks dynamically, when they can be executed.

So far, parallelization techniques for dataflow programs have focused on taking advantage of the decomposition in agents, potentially duplicating some agents to have several instances that work on different data items in parallel [START_REF] Gordon | Compiler techniques for scalable performance of stream programs on multicore architectures[END_REF]. In the presence of big agents, the programmer is left with the splitting (or merging) of these agents by-hand if she wants to further parallelize her program, or at least give this opportunity to the runtime, which in general only sees agents as non-malleable entities. In the presence of arrays and loop-nests or, more generally, some kinds of regularity in the agent's code, we believe however that the programmer would benefit from automatic parallelization techniques such as those implemented within polyhedral compilation tools. We propose to use such sequential code parallelization techniques to parallelize the sequential code that describes an agents' behavior.

The work reported in this paper aims at demonstrating the practical advantage of combining the dataflow paradigm with the polyhedral optimization framework. We empirically demonstrate this by building a proof-of-concept tooling approach, using existing tools on existing languages. This paper's contributions are:

• A tentative approach combining dataflow programming with polyhedral compilation in order to enhance program parallelization by leveraging both inter-agent parallelism and intra-agent parallelism (ie regarding loop nests inside agents). • An implementation of this approach using a state-ofthe-art dataflow language as well as classical polyhedral tools.

• An evaluation of the approach on several example benchmarks.

• A discussion about the costs and benefits of the approach. The rest of the paper is organized as follows. Section II introduces background on both dataflow programming languages (II-A), including the ΣC dataflow language, and the polyhedral model (II-B). Section III explains our proposition, namely conjointly parallelizing loop nests that are found inside dataflow agents. Section IV describes our the experimental setting, the toochain that supports the ΣC language and the Pluto tool we use for automatic loop parallelization. Section V describes our experiments. These comprise three applications: a toy matrix multiplication, an implementation of the Deriche algorithm for image edge detection and a simple instance of artificial neural network used for image classification. Finally, section VIII concludes and draws perspectives to this work.

II. BACKGROUND

A. Data Flow Programming

First dataflow programming models were proposed in the seminal works of G. Kahn [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] and J. Dennis [START_REF] Dennis | First version of a data flow procedure language[END_REF]. The main concept consists in decomposing the application one wants to build as a set of independent processes (we will call them agents in the rest of the paper) that communicate solely through First-In-First-Out (FIFO) channels.

Since the mid 70s, models and languages following the same philosophy have flourished. A main characteristic that distinguishes these models is the ability to determine statically (or not) how many data tokens are exchanged by agents on the FIFO channels. When these quantities can be determined at compile-time, these models are named static (Boolean, static, cyclo-static, etc). This gives nice properties to such programs, namely boundedness of memory usage and static schedulability. When data rates are not fixed statically, agents need to be scheduled at runtime. Such languages are qualified as dynamic dataflow.

ΣC: Our experiments are applied to programs written using the ΣC programming language [START_REF] Aubry | Extended cyclostatic dataflow program compilation and execution for an integrated manycore processor[END_REF]. ΣC implements the Cyclo-Static Dataflow (CSDF) model [START_REF] Bilsen | Cyclo-static dataflow[END_REF] where data rates of agents are known statically and can change periodically.

Throughout this paper, we use the example of the Deriche algorithm [START_REF] Deriche | Using canny's criteria to derive a recursively implemented optimal edge detector[END_REF], an optimal edge-detection algorithm for discrete bi-dimensional images. Here we only describe the structure of the program. Written in ΣC, the implementation is composed of 6 agents that are connected as shown in Figure 1. Each of these agents applies a transformation to an image-size matrix. Links between agents represent FIFO channels, which are the unique mean that can be used to share data among agents. An agent's behavior is defined using a DSL in which one describes: • the interface of the agent (its input and output ports) • a set (at least one) of functions that describe what happens when the agent is activated. The code given in Figure 2 defines the agent L1 to have one input (resp. output) flow on which the agent, everytime it is triggered, will read (resp. write) HEIGHT float values. The start function is triggered at each of L1's activations and performs some computations to define the value to be written on its output flow. Here, the computation consists in a for loop iterating over all the elements read from (resp. written to) input and output ports.

The compilation process implemented in the ΣC toolchain is in charge of transforming these dataflow language concepts into runtime concepts. Agent activities are translated into sequential programs encapsulated into runtime threads. Depending on the target architecture, FIFO communication channels can be translated into efficient shared-memory implementations or into distributed communication mechanisms. The ΣC runtime is then in charge of allocating memory regions and scheduling the activities corresponding to agents, either relying on an underlying operating system or through dedicated scheduling policies.

B. Polyhedral model

The second building block of our approach is a compilation and optimisation framework for imperative kernels that perform intensive computations, namely, the polyhedral model. This framework [START_REF] Feautrier | Dataflow analysis of array and scalar references[END_REF] provides exact dependence analysis information where statement instances (i.e., statements executed at different loop iterations) and array elements are distinguished. The exact dependence information obtained through this analysis and the use of linear programming techniques to explore the space of legal schedules [START_REF]Some efficient solutions to the affine scheduling problem, II, multi-dimensional time[END_REF] is what constitutes the base of the polyhedral model for loop transformations. times during the execution of this loop. The triangular region expressed as a set of constraints, called the domain of S, represents this set of dynamic execution instances. Accesses to array A from each of these statement instances can be succinctly captured through affine functions of the loop iterators. The dependences are also expressed as a function between two statement instances. From this mathematical description, the framework is capable of extracting a set of valid schedules (i.e. new ways to execute loop statements), compute tiled, parallel, pipelined versions of the same code, depending on the optimization function (locality, maximum parallelization, . . . ), and then generate their code.

The "traditional" use of polyhedral techniques in optimizing compilers typically focuses on loop transformations of polyhedral kernels. PLuTo [START_REF] Bondhugula | A practical automatic polyhedral parallelizer and locality optimizer[END_REF] is a now widely used push-button tool for automatically parallelizing polyhedral loop nests that tries to optimize locality in addition to parallelization. There is also significant work in data layout optimization for polyhedral programs where analyses are performed to minimize the program's memory requirement [START_REF] Darte | Lattice-based memory allocation[END_REF]. Polyhedral techniques for loop transformations are now adopted by many production level compilers, such as GCC, IBM XL, and LLVM.

Recently, polyhedral techniques are being applied to many different areas besides loop transformations. One natural application of automatic parallelization techniques is in verification of given parallelizations where the tools take parallelized programs as inputs, and use polyhedral analysis to guarantee the absence of parallel bugs [START_REF] Basupalli | ompVerify: Polyhedral analysis for the OpenMP programmer[END_REF], [START_REF] Yuki | Array dataflow analysis for polyhedral X10 programs[END_REF]. Moreover, a huge amount of research is done to extend the applicability of polyhedral optimizations [START_REF] Benabderrahmane | The polyhedral model is more widely applicable than you think[END_REF], such as hybrid techniques that mix static compilation and dynamic tests [START_REF] Rus | Hybrid analysis: Static and dynamic memory reference analysis[END_REF]- [START_REF] Jimborean | Dynamic and speculative polyhedral parallelization using compiler-generated skeletons[END_REF].

The polyhedral model is becoming a standard to reason about regular programs and to effectively perform kernel optimizations inside SCOPS (static control parts of a program, where it is effectively applicable).

Our proposal, described next, is an integrated language approach to use both task and instruction parallelism within a unique setting.

III. GENERAL APPROACH

This section describes our arguments in favor of a new integrated approach that would mix in the same language dataflow idioms to express dataflow parallelism and " la polyhedral" model to express instruction parallelism.

The advantages of a dataflow approach are:

• Streaming algorithms [START_REF] Amer | Reconfigurable video coding on multicore[END_REF], scientific workflows [START_REF] Travis | LabVIEW for everyone: graphical programming made easy and fun[END_REF], and many other applications, are already thought as agents communicating data through FIFOs. • From Kahn [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] proposition to the Tensorflow [START_REF] Abadi | Tensorflow: A system for large-scale machine learning[END_REF] language, a wide variety of (more or less semantically well-founded) languages share the common idea of letting the programmer express as much parallelism as he can, dataflow being one (or the main) of the paradigm proposed. • In some well-defined variants like the Static/Synchronous DataFlow [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF], the problem of statically scheduling agents with a maximum parallelism is shown to be decidable. It is the case of the ΣC language we use in our experiment. • In some other variants, the user benefits from clever runtime supports. But this is theory. All these approaches compile separately (and agnostically) the code inside the agents, thus they may miss some opportunities for static compilation as well as static or dynamic scheduling, like:

• the intrinsic parallelism of a given agent;

• the organization of data inside a given agent. With this information made explicit, the dataflow compiler and scheduler would take the decision of splitting agents, pipelining or merging them, in order to exploit all the intrinsic parallelism of a given application. We can even imagine being able to express and schedule several applications running on the same parallel machine [START_REF] Morel | CalMAR -a Multi-Application Dataflow Runtime[END_REF].

However, up to now, the developer was in charge of writing "well-optimized" agents. This approach is clearly errorprone, and lack flexibility. Moreover, the agents' code then begins to be overspecialized and not portable anymore. We propose to solve this issue by letting the programmer write the application she has in mind, and have the compilation chain harness the application's potential parallelism.

This integrated approach gives opportunities to the developer to express her knowledge of the application she designs. However the theoretical counterpart would not be trivial as it involves being able to express and compute hierarchical schedules so that the actual aggressive compilations done statically do not interfere with the task scheduling of agents, whether scheduled statically or at runtime. Indeed, there is a huge design space from explicitly expressing all parallel statements as tasks and schedule them independently (with a possibly unreasonable cost) to individual two-steps scheduling of tasks, then sub-tasks (which may be simpler to design but may lose inter-tasks optimization opportunities).

i<HEIGHT;i++){ o[i]=in[0][i]+in[1][i]; } } }
Our long term objective is to go towards such a formal framework to express, compile and run dataflow applications with intrinsic instruction or pipeline parallelism.

Motivating example: As a motivational example, let's look again at the Deriche image transformation application, shown in Figure 1.

This program is intended to deal with images in a pipelined fashion. When L1 and L2 have finished manipulating a first image, the combination phase of their result (agent L3) can start while L1 and L2 are fed with data corresponding to a new image. This program is naturally described in a dataflow manner. More importantly, the succession of phases L1, L2, etc. follows the mathematical description (see [START_REF] Deriche | Using canny's criteria to derive a recursively implemented optimal edge detector[END_REF]).

One of the limitations of dataflow programming as it is done today is that the dataflow compiler sees each agent as a separate compilation unit. It is therefore unable to optimize code across agent's boundaries. As an example, consider the agent L1 of Figure 2. Figure 4 gives the code of agents L2 and L3.

Each of these agents contains a loop iterating on its input data to produce its output data, Intuitively, we would like the compiler to consider these loop nests as a potential source of optimization. It could then decide to 1) fuse actors L1, L2 and L3 as well as 2) apply loop-based parallelization.This would produce an agent L123 such as the one of Figure 5 where for instance a parallel loop has been identified. Of course, this is one possible transformation and our ideal compiler would have many possibilities to choose from.

Proposed approach: This paper is a first proposition of a combination of the polyhedral model framework with a production dataflow language, namely ΣC. Through the implementation of three non trivial case studies, we explore the relationships between dataflow, pipeline and instruction parallelisms, how they interfere at compile time and at runtime.

This relationship is non trivial to predict, since the polyhedral model is able to capture a potentially infinite parallelism that neither the ΣC compiler, or runtime, is capable to reason on. The scheduling of a "parallel" agent has to make a compromise between the number of resulting "sub agents" and the intrinsic cost of having too many agents to orchestrate at runtime. Moreover, the benefit of the potential parallelism may be lost if there is too many FIFOs that increase memory pressure.

In essence, what we state in this paper is that the polyhedral model and the dataflow paradigm are going toward two different directions that will be reconciliated only if we express all their capabilities in a unique formal framework. This paper is a first experimental step to validate the potentiality of the approach.

IV. IMPLEMENTATION

To experiment on the idea of combining polyhedral loop parallelization with agent-level parallelism, we have combined the ΣC language and the ΣC toolchain together with the Pluto optimizing tool.

The complete workflow is depicted in Figure 6. This workflow has been applied identically on all our running examples. First we have written the original ΣC program, defining agents, some with loop nests as required by the application's implementation choices. As the ΣC language only allows one-dimensional arrays, we then have delinearized this version (this could have been done automatically with a technique adapted from [START_REF] Grosser | On recovering multi-dimensional arrays in Polly[END_REF], for instance) and added Pluto annotations on loop nests for which we have identified a potential benefit.

The loop nests are then fed to Pluto individually. For each nest, Pluto returns a semantically-equivalent loop nest along with OpenMP annotations. The original loop nest is then replaced by the new one in the ΣC agent. The ΣC program is then compiled to C and then through GCC to an executable program. We compare the performance of this program with that of the one obtained by compiling the original ΣC program. The annotation needed by Pluto to operate on loop nests is straightforward, consisting, as shown in Figure 8 of simply adding scop/endscop pragmas around the loop nests that need to be parallelized.

V. EXPERIMENTS

A. Use cases

We demonstrate our proposal on three non-trivial example programs.

The first one is the Deriche edge detection implementation already described in Section II-A. This application comprises several agents among which six include loop nests on which polyhedral compilation can be applied.

Our second program is an instance of an artificial neural network (ANN) program that can be used to classify images. ANNs are composed of layers that are pipelined . Each layer comprises a static number of perceptrons that produces a single dataflow output while reading a number of input flows coming from the preceding layer. The architecture of such an ANN is depicted in Figure 7.

Figure 8 shows the ΣC implementation of a layer agent that gathers the activity of column perceptrons. Each perception j of a given layer computes a linear combination of its input in[j] with its weight configuration w[..][j]. All the computations are gathered into a unique loop nest of depth 2. At the end, a non linear function (fns_activ) is applied to the output vector.

This network corresponds to the decision phase of the ANN only. The training of our ANN was performed with another program that exports the weights and the settings of the trained network. This is out of the scope of this paper, but suffice it to say that this training program has been implemented in Python, using the Keras library [START_REF] Branchaud-Charron | Keras: The Python Deep Learning library[END_REF]. The specification of the network (weights and settings) is written by the python training program to a plain-text file. This file is then parsed, at compile time, by the root graph of the ΣC program. It specifies the number of layers, and for each layer, its size, its weight matrix, and the activation function to use. Hence, the whole structure (level of task parallelism, depth) of the ΣC program is configurable by the learning phase.

Finally, we implemented a block-based matrix multipli-

StreamReaderA RowsToBlocks Split StreamReaderB InB[1] InB[2] InB[3]
InA [START_REF] Halbwachs | The synchronous data flow programming language lustre[END_REF] out InA [START_REF] Thies | Language and compiler support for stream programs[END_REF] InA [START_REF] Kahn | The semantics of a simple language for parallel programming[END_REF] cation whose general structure is depicted in Figure 9. The multiplication is based on a grid of multiply-accumulate agents, see Figure 10. At the highest level of the agent hierarchy, extra agents are needed to organize one of the matrix as blocks to be fed to these multiply-accumulate agents (agents RowsToBlocks and BlocksToRows).

Grid subgraph

The whole structure of this dataflow program introduces significant potential parallelism. The level of parallelism (ie the number of agents) depends on 1) the size of the A, B and C matrices and 2) the number of blocks the matrices are split into to feed the Multiply-Accumulate agents.

B. Experimental setting

Our experimental results were obtained using two different configurations. The first one, tagged desktop in the rest of the paper, is a laptop with an Intel Core i7-7700U processor, providing 4 cores. The second platform, tagged cluster, is a Dell PowerEdge R430, with two Intel Xeon E5-2620 v4 CPUs, for a total of 16 cores and 32 threads. This machine was made available through the Grid5000 experiment platform. Both versions where running Fedora 24 (linux kernel version 4.5)

ΣC programs are compiled with a version of the ΣC compiler kindly provided to us by Kalray SA 1 . Several agent-to-thread mapping and agent scheduling strategies are available. In our experiment, we use the thread option which generates one POSIX thread for each agent in the application. From the original ΣC programs, the compiler generates C programs, which are then compiled using GCC 6.3.1. Loop nests are parallelized by Pluto (version 0.11.42 ) which generates semantically equivalent forms annotated with OpenMP pragmas. GCC is then configured with the -fopenmp option and uses version 4.5. Concerning applications, we have made the following and experimentation choices. To further study the capabilities offered by our approach, these choices should be extended to consider larger data and more agents as well, where applicable. In the case of the Matrix Multiplication, we have only manipulated matrices of size 1000*1000 elements. The multiply-accumulate grid consists of only 4 agents. This seemed a reasonable trade-off to limit the amount of data exchanged by agents on FIFO channels. The downside is that it limits the potential parallelism of the application. Concerning the Deriche case study, images used where of size 7786*3000 (ie 23 MPx). The number of agents is fixed by the global design choice and does not depend on data sizes, as it is the case for MatMult. Also, we have implemented a second version of Deriche, where agents L1, L2 and L3 have been manually replaced by agent L123 of fig. 5. Finally, ANN was used to classify 1000 images of 784 pixels each. The network considered contains 3 dense layers of 784 neurons each and an output layer of 10 neurons. This topology has been chosen in order to have several layer agents pipelined as it allows to take advantage of pipeline parallelism.

VI. RESULTS

Figure 11 depicts a comparison of performance results for our three programs running on the full Cluster environment (16 physical cores, 32 threads). Figure 12 shows a similar comparison for the Desktop environment (2 physical cores, 4 threads).

For each program, we use as baseline the timing performance of the initial ΣC program where agents have been implemented following the "dataflow informal semantics of the algorithm" (each agent implements a functionality). We then selected one or two agents as candidates for automatic optimization with tiling, and also compare with automatic parallelization of the same agent(s) with Pluto. Results are reported for execution on 4 cores on the desktop platform and 16 cores on the cluster platform.

The most notable result is that with little effort, essentially consisting in adding straightforward Pluto annotations to loop nests, the user can obtain non-negligible performance improvement on the execution time of her dataflow programs. Performance are improved by tiling alone and can be further slightly more improved by using both tiling and OpenMP parallelization. Again, using these options is straightforward. We can then surely hope to obtain more interesting results by pursuing our goal of tightly combining polyhedral compilation with dataflow programming languages.

Two performance retreats can be observed, for MatMult and ANN, when using OpenMP on the desktop platform. This is explained by the fact that when using tiling all 4 cores of machines are already fully busy. So when trying to parallelize more by creating more threads at runtime, the OpenMP runtime tends to overload the system's scheduler: global performance suffers from the negative impact of too many thread context switches.

Finally, we show in figure 13 the speed-up (in %) that is gained by applying the transformations suggested in section III over the Deriche usecase. The fusion of agents L1, L2 and L3 presented in figure 4 leads to a gain in performance of at least 11% when using tiling on the code of the resulting agent. The gain is limited to a few percents when using both tiling and automatic parallelization. At the time of writing, this still needs to be further investigated in order to understand why both optimizations conflict in this manner. We also need to pursue experiments on cluster-like machines.

VII. RELATED WORK

We already cited some of our inspirations in Section III. In this section we develop other related works.

In the polyhedral model community, the dataflow paradigm is more of an intermediate representation than an actual programming feature. The polyhedral process networks (PPN) [START_REF] Verdoolaege | Polyhedral Process Networks[END_REF], communicating regular processes (CRP) [START_REF] Feautrier | Scalable and structured scheduling[END_REF], and data-aware process networks (DPN) [START_REF] Alias | Data-aware Process Networks[END_REF] are generated from a unique sequential program that is fully polyhedral, or at least, where SCOPs have been correctly identified. Further optimizations are made, like hierarchic polyhedral scheduling for CRPs, or efficient implementation of communicating buffers for DPNs [START_REF] Alias | Improving Communication Patterns in Polyhedral Process Networks[END_REF]. The Compaan compiler [START_REF] Kenhuis | Compaan: deriving process networks from Matlab for embededd signal processing archictures[END_REF] transforms applications in the field of signal and image processing (thus inherently dataflow applications [START_REF] Zhai | Modeling adaptive streaming applications with parameterized polyhedral process networks[END_REF], written in Matlab) to PPNs, from which they can automatically derive an hardware description for FPGA platforms. Although there is a significant amount of research for deriving efficient control for PPNs with particular constraints coming from the hardware [START_REF] Derrien | Deriving efficient control in Process Networks with Compaan/Laura[END_REF], all this process remains polyhedral. Like the synchronous proposition of [START_REF] Didier | Sheep in wolf's clothing: Implementation models for data-flow multi-threaded software[END_REF], we believe that these polyhedral works should be carefully integrated in our setting in order to gain benefit of both task and instruction parallelism; however we do not want to restrict the input language to a particular subclass of statically optimizable kernels, like in [START_REF] Cohen | Static Analysis of OpenStream Programs[END_REF].

The approach described in [START_REF] Sbîrlea | Polyhedral optimizations for a data-flow graph language[END_REF] tries to conciliate what the authors call "macro dataflow" and the polyhedral model in order to benefit from the optimization facilities of the state-of-the-art polyhedral frameworks. This paper is the most related to ours, and is as far as we know the only other attempt at combining explicit agents and polyhedral kernels. Contrarily to our proposition to use an existing language (ΣC) and its ecosystem, they propose to use a more restrictive language (DFGL) to define the "macro" dataflow part as well as kernels, for which they propose a polyhedral compilation ("intra-step" optimization). The coordination of the "inter-step" parallelism is left to the underlying runtime system. The expressivity of the language actually compiled remains however in the classical polyhedral domain, since the scheduling problem is resolved by encoding the whole graph (macro and micro parts) as polyhedral dependencies that are solved (and scheduled) classically. We believe that a more general language approach should at least be able to have the same polyhedral expressivity, but be general enough to express non-regular behaviors inside and outside agents.

Finally, the authors of [START_REF] Balevic | A data parallel view on polyhedral process networks[END_REF] propose an execution model for single program multiple data (SPMD) on GPUs, based on a polyhedral model based formulation. They propose a way to extract "thread parallelism" from actual (non fully polyhedral) applications. This approach is more a runtime approach than a language approach, and is specific to GPUs. In [START_REF] Bosilca | From serial loops to parallel execution on distributed systems[END_REF], the authors propose a polyhedral-based precompilation phase for their runtime system DAGuE, in order to expose data exchange information that is further used by the runtime. Our approach is more "friendly" to the compiler since the SigmaC language makes some of these communications explicit. However both approaches share with us the idea of the integration of polyhedral techniques inside more pragmatic compilers and runtime that target full applications.

VIII. CONCLUSION

We have proposed an approach for parallelizing ΣC programs that takes advantage of the language's constructs to deal with task, pipeline and data parallelism and uses polyhedral compilation techniques to further parallelize loop nests inside the application's agents. The approach is validated with a set of non-trivial case studies. These casestudies show, that the use of polyhedral compilation to parallelize the internals of some agents increases programs' performance by a factor between 1.3 and 3.5, depending on the application and the parallelization technique used on loop nests. We also show in one example case that the combination of agent fusion and loop optimization can improve performance by 11 %.

These results have been obtained with a simple experimental approach only using off-the-shelve tools. These result encourage us to pursue research on combining expertise from dataflow programming languages and polyhedral compilation. Our long term objective is to go towards a formal framework to express, compile and run dataflow applications with intrinsic instruction or pipeline parallelism.

We plan to investigate the following directions:

• A language approach: propose new stream programing models where all kinds of parallelisms are expressed explicitly, and where all activities from code design to compilation and scheduling can be cleanly expressed. • An experimental approach: explore various areas of applications from classical dataflow examples like radio signal and video processing to more recent applications in deep learning algorithmic. This will enable us to identify some potential (intra and extra) agents' optimization patterns that could be leveraged into new languages idioms.

Figure 2 .

 2 Figure 2. ΣC implementation of the L1 agent.

  ; i<N; i++) for (j=i; j< ; j++) S: A[j] = f(A[i], A[j]);

Figure 3 .

 3 Figure 3. An example of polyhedral representation. Loop nests that fit the polyhedral model can be viewed as mathematical (constraint-based) objects, which can also be visualized geometrically. Dependencies here are depicted as arrows from producers to consumers.

Figure 3

 3 Figure 3 illustrates the polyhedral representation with an example. The statement S is executed approximately N 2 2

Figure 4 .

 4 Figure 4. ΣC implementation of agents L2 and L3.

Figure 5 .

 5 Figure 5. ΣC Ideal implementation of an actor L123 resulting in the fusion of agents L1, L2, L3 as well as loop based parallel optimizations.

Figure 6 .

 6 Figure 6. The complete toolchain.

Figure 8 .

 8 Figure 8. Example of a layer agent.

Figure 9 .

 9 Figure 9. General structure of the matrix multiply ΣC program, exposing pipeline parallelism.

Figure 10 .

 10 Figure 10. Structure of the Grid agent, exposing data parallelism.

Figure 11 .

 11 Figure 11. Speed-ups, on the cluster platform.

Figure 12 .

 12 Figure 12. Speed-ups, on the desktop platform.

Figure 13 .

 13 Figure 13. Speed-ups (in %) due to agent fusion.

  Author Version of « Polyhedral DataFlow Programming, a Case Study », Romain Fontaine, Laure Gonnord, Lionel Morel, accepted in SPAC-PAD, 2018.

	ΣC source code
	Array Delinearization
	+ Scope Definition
	(Manual)
	Σ C source code	ΣC binaries
	Tiled, parallel Polyhedral Optimisation (Pluto)	(Manual) Array Linearization	Optimized Compilation (ΣC compiler)
	Σ C code	ΣC source code

http://www.kalrayinc.com/

http://pluto-compiler.sourceforge.net/

ACKNOWLEDGMENT

We are grateful to people at Kalray for allowing us to experiment with their ΣC compiler. Some of the experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

This work was also partially funded by the French National Agency of Research in the CODAS Project (ANR-17-CE23-0004-01).