Oriel Frigo

Neus Sabater

Julie Delon

Pierre Hellier

Video Style Transfer by Consistent Adaptive Patch Sampling

Keywords: Style Transfer, Texture Synthesis, Non-photorealistic Rendering, Video Processing

This paper addresses the example-based stylization of videos. Style transfer aims at editing an image so that it matches the style of an example. This topic has recently been investigated massively, both in the industry and academia. The difficulty lies in how to capture the style of an image and correctly transferring it to a video. In this paper, we build on our previous work "Split and Match" for still pictures, based on adaptive patch synthesis. We address the issue of extending that particular technique to video, ensuring that the solution is spatially and temporally consistent. Results show that our video style transfer is visually plausible, while being very competitive regarding computation time and memory when compared to neural network approaches.

Introduction

Style transfer consists in transferring the style of an example, typically a painting, to another image or video. This problem has received recently a considerable interest [START_REF] Durand | An invitation to discuss computer depiction[END_REF][START_REF] Kyprianidis | State of the art: A taxonomy of artistic stylization techniques for images and video[END_REF], especially with the blooming of convolutional neural network approaches [START_REF] Gatys | A neural algorithm of artistic style[END_REF][START_REF] Li | Precomputed real-time texture synthesis with markovian generative adversarial networks[END_REF][START_REF] Dumoulin | A learned representation for artistic style[END_REF]. There are many applications to style transfer, ranging from social networks, virtual reality to movie post-production.

The upcoming film "Loving Vincent"1 can be seen as a remarkable example of the practical possibilities of style transfer. This endeavor is claimed to be the first fully painted feature film to be made, and includes an average of 12 oil paintings per second of video. Note that more than 100 painters were involved in the production, which is a painstaking work that could be facilitated by style transfer techniques.

In this paper, we build on our recent paper [START_REF] Frigo | Split and match: Example-based adaptive patch sampling for unsupervised style transfer[END_REF] that proposed a patch-based method for style transfer, and extend this approach to video content. Example-based patch methods have been sucessfully used in various cases, ranging from texture synthesis [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF], inpainting [START_REF] Criminisi | Region filling and object removal by exemplar-based image inpainting[END_REF], to super-resolution [START_REF] Freeman | Example-based super-resolution[END_REF]. These methods have proven their capability to capture knowledge about the image based on the content intra-similarity. In this paper, we extend this patch-based approach to video, where an efficient optical flow method is used to track parts of the image, while inconsistencies of the tracking (captured by a metric on motion reliability) are handled by a spatially and temporally consistent patch synthesis.

Related Work

Style transfer can be traced back to two seminal papers, "Image Analogies" [START_REF] Hertzmann | Image analogies[END_REF] and "Image quilting" [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF], which presented non-photorealistic rendering based on example images as one possible application of texture synthesis. Closely related is the concept of color transfer [START_REF] Reinhard | Color transfer between images[END_REF], where one seeks to transfer the color palette from a target to a source image.

In Image Analogies, style transfer is computed as a pixelwise texture synthesis, inspired by the non-parametric sampling approach of [START_REF] Efros | Texture synthesis by non-parametric sampling[END_REF]. An analogy is defined as the relationship (transformation) between a pair of aligned example images, typically a non-filtered picture of a scene and a stylized painting of this same scene. Then, the task is to apply an analogous transformation to a given input image, such that it has the same rendering of the example painting. Every pixel to be synthesized in the output image is selected from the example painting, by minimizing an energy accounting to the similarity between the input picture and the non-filtered example picture. A seminal work in video style transfer was conducted in [START_REF] Bénard | Stylizing animation by example[END_REF], as an extension of image analogies to stylization of video animations. Temporal coherence is enforced and neighborhood matching is accelerated by using the randomized patch correspondences of "PatchMatch" [START_REF] Barnes | The generalized patchmatch correspondence algorithm[END_REF]. Nevertheless, the method still has high computational complexity as it perform a pixelwise style synthesis, which results in large search space for neighborhood matching. Furthermore, it is worthy noting that approaches based on image analogies assume the existence of a registered pair of example images from which the style analogy is learned, which constrain the practical use of such methods.

The work of [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF], in parallel with [15], have introduced the concept of patch sampling for texture synthesis and texture transfer. These methods perform examplebased synthesis by sampling from a pool of candidate patches, which are selected from an example image. Sampling patches instead of pixels have the advantage of lower computational complexity, but a post-processing step may be required to overcome blocking artifacts. In [15], linear interpolation is used to produce seamless patch blending, while in image quilting [START_REF] Efros | Image quilting for texture synthesis and transfer[END_REF], optimal patch boundary cuts are computed.

Our previous work [START_REF] Frigo | Split and match: Example-based adaptive patch sampling for unsupervised style transfer[END_REF] has shown that the quality of patch-based style transfer can be improved by adapting the patch dimensions to the structure of the original and example images. Inspired by [START_REF] Freeman | Learning low-level vision[END_REF] and [START_REF] Wang | Face photo-sketch synthesis and recognition[END_REF] the "Split and Match" approach considers a Markov Random Field (MRF) probability density modeling and computes an approximate Maximum a Posteriori (MAP) solution through loopy belief propagation [START_REF] Weiss | Belief propagation and revision in networks with loops[END_REF]. A followup patch-based approach [START_REF] Elad | Style-transfer via texturesynthesis[END_REF] for style transfer is also based on adaptive patches for capturing the style from example images. In this paper, we extend our previous still image style transfer [START_REF] Frigo | Split and match: Example-based adaptive patch sampling for unsupervised style transfer[END_REF] to image sequences, as a fast and efficient approach for video style transfer.

The paper of [START_REF] Gatys | A neural algorithm of artistic style[END_REF] has introduced a technique that builds upon deep Convolutional Neural Networks (CNN) to separate and recombine the content and the style of an original and an example image. Their main idea is to represent style by correlations between features from different layers of a CNN, and to represent content by feature responses in higher layers of a CNN. Their method produces impressive results for style transfer, but has the drawback of high computational complexity. This work received a great attention in vision community, inspiring other papers such as [20, ?] and resulted in the development of products such as "DeepArt"

2 and an accelerated smartphone application "Prisma"3 . Furthermore, an adaptation of CNN-based style transfer for post-production of a feature film has been described by [START_REF] Joshi | Bringing impressionism to life with neural style transfer in come swim[END_REF].

Recently, neural style transfer for videos has been proposed by [START_REF] Ruder | Artistic style transfer for videos[END_REF], where temporal coherence is enforced to the stylization by using optical flow guidance. Our approach for temporal coherence is similar in spirit to [START_REF] Ruder | Artistic style transfer for videos[END_REF]: propagate style by motion warping where optical flow is reliable, and resynthesizing style where optical flow is not reliable.

It should be noted that image and video style transfer based on deep CNN's differs considerably from our approach, since it assumes a pre-trained neural network architecture. Although results of neural style transfer are mostly excellent, as remarked by [START_REF] Fišer | Stylit: Illuminationguided example-based stylization of 3d renderings[END_REF], the stylization by neural networks tends to be unpredictable in practice. On the other hand, patch based approaches may be advantageous for a more predictable stylization that better preserves the main structures in the original image.

Split and Match for Still Images

In this section, we briefly review our "Split and Match" approach, which proposes a patch-based algorithm to transfer the style of an example (or style) image to an input image. A more detailed version of this style transfer method can be found in our recent paper [START_REF] Frigo | Split and match: Example-based adaptive patch sampling for unsupervised style transfer[END_REF]. This approach, illustrated by Figure 2, starts by constructing an adaptive quadtree segmentation of the input image geometry, taking into account the capacity of the patches in the quadtree to be represented by patches of the style image. This adaptive partition is necessary to respect the original image geometry, using small patches (fine brushes) along geometric features, while letting large patches (rougher brushes) to capture the style of the example image everywhere else. Let us denote by u : Ω u → R 3 the input image and v : Ω v → R 3 the example image. For two regions R and R ′ of similar size of Ω u and Ω v , we write u(R) and v(R ′ ) the respective restriction of u and v to R and R ′ , and we define the normalized distance between u(R) and v(R ′ ) by

d[u(R), v(R ′ )] = ||u(R) -v(R ′ )|| 2 |R| , with |R| the size of R. (1)
The Split and Match decomposition works as follows.

Starting from the region R 1 := Ω u , each rectangle R i [START_REF] Frigo | Split and match: Example-based adaptive patch sampling for unsupervised style transfer[END_REF] for style transfer between still images. From left to right: the input image u is recursively splitted into patches. Each patch is matched with the example image, and if there is a match sufficiently close, or if the patch variance is sufficiently small, the splitting is ended. Each patch over region R i has a set of label candidate patches L i , from which a best label is computed by loopy belief propagation. As it can be seen in the figure, the patch labels on the left part account mostly for style (homogeneous patches in the original image), while the label patches on the right part account mostly for smaller feature patches, which account for reconstructing details and geometry in the stylized image. of the partition is split into four equal rectangles if

Var(u(R i )) + d[u(R i ), v(R v i )] > ω and |R i | > Υ 0 or |R i | > Υ 1 , (2)
where

R v i is the rectangle R of the style image v min- imizing the distance d[u(R i ), v(R)]
, ω is a similarity threshold (fixed to ω := 15), Υ 0 is the minimum patch size and Υ 1 the maximum patch size allowed in the quadtree (respectively fixed to 8 2 and 256 2 ). At the end of this decomposition, for each region R i of the final quadtree a set of M candidate labels L i = {l im } M m=1 is selected by computing the M-nearest neighbors of the patch u(R i ) in v. The label l im is the central pixel of the m th nearest region of u(R i ) in v. These patch labels are also required to be sufficiently distant from each other to favor label variety.

In a second step, we rely on a Markov Random Field model over the final partition {R i } n i=1 to minimize pairwise distances and patch differences. More precisely, we search for the set of label assignments L = { li } n i=1 maximizing a probability density

P (L) = 1 Z i φ(l i ) (i,j)∈N ψ(l i , l j ), ( 3
)
where Z is a normalization constant, φ is a data fidelity term and ψ a compatibility term between neighboring regions ((i, j) ∈ N means that R i and R j are neighbors in the quadtree). The data fidelity term φ is defined as

φ(l i ) = exp(-λ d d[u(R i ), v(R li )]), (4)
where R li is the region of label l i in v, and λ d a positive weight (fixed to 2 in practice). The role of the function ψ is to ensure that neighboring candidate patches are similar enough at the vicinity of their common frontier. Extending each region R i of the quadtree in each direction by 50% yields overlapping regions R i . For (i, j) ∈ N , ψ(l i , l j ) is then defined as a mix of a smoothness term and a term penalizing local label repetitions

ψ(l i , l j ) = exp(-λ s d ∩ [v( R li ), v( R lj )]+λ r |l i -l j | 2 ), ( 5
)
with λ s and λ r two positive weights (fixed to 2 and 1 in all experiments), and where

d ∩ [v( R li ), v( R lj )] is the normalized quadratic distance between the candidates v( R li ) and v( R lj ) on the overlap R i ∩ R j .
In order to maximize the probability density (3), we adopt the Loopy Belief Propagation method [START_REF] Weiss | Belief propagation and revision in networks with loops[END_REF], [START_REF] Pearl | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference[END_REF]. In this approach, neighboring variables update their likelihoods by message passing which permits to maximize the density (3) in a few number of iterations.

To avoid stitching artifacts along patch borders (see Figure 3), patches are eventually merged through a linear alpha blending, ensuring smoother transitions between neighbors. The last and optional step of the algo- rithm is a color transfer [START_REF] Frigo | Optimal transportation for example-guided color transfer[END_REF] used to match consistently the color palettes of the original and example images, combined with a global contrast specification approximated by a power law model. The whole process results in a stylized image ũ.

Video Style Transfer

We explain in this section how to adapt our Split and Match style transfer to image sequences. Obviously, applying an independent style transfer to each frame of a sequence leads to strong texture flickering and poor visual results, even if neighbor frames share most of their geometry and color (see the left column of Figure 9). In order to impose coherence between frames, we propose a motion-based temporally coherent stylization, illustrated by Figure 4.

In the following, we denote by U = {u t } D t=1 the input image sequence and by v the example (style) image. Each discrete image u t : Ω → R 3 is defined over the same discrete domain Ω. A "keyframe rate" r is chosen in such a way that we have one keyframe for each second of video (typically, r := 25 for a 25 fps video). We write U k,k+r = {u t } k+r-1 t=k+1 the set of all frames delimited between the keyframes u k (also called left keyframe) and u k+r (right keyframe). At the beginning of the algorithm, our Split and Match algorithm is applied to transfer the style of the example image v to the central keyframe of the movie. To ensure a temporally stable stylization, we rely on optical flow to propagate the style to all other keyframes, recomputing the style transfer in regions where motion is unreliable. We call this process Temporal Style Propagation (TSP). Once all keyframes have been stylized, for each set of frames U k,k+r , we propagate the style from the stylized left keyframe u k in forward direction to all images u t from U k,k+r , then we propagate the style from u k+r in backward direction and finally we blend the forward and backward stylized frames by linear interpolation. This stylization "by chunks" is repeated until the end of sequence, as summarized in Algorithm 1 and illustrated by Figure 5. Assuming that the frame u t ⋆ has been stylized, we show how to propagate the stylization to u t (t ⋆ = t -1 when we propagate in the forward direction). On the left, the stylized frame u t ⋆ . Motion warping is applied to the stylized keyframe u t ⋆ to obtain a first estimate of the stylized frame u t . Since motion is not reliable everywhere, a motion reliability map is also deduced (unreliable pixels are shown in black). To improve the first estimate of u t , we re-synthesize all regions containing unreliable pixels by solving an optimal labeling problem. The final stylized image u t (on the right) is obtained by blending the re-synthesized regions with the motion warped estimate.

Algorithm 1 Video Style Transfer

Temporal Style Propagation

We describe in this section the details of our Temporal Style Propagation, used first to ensure coherence between keyframes and then to propagate the style to all frames. In a nutshell, Temporal Style Propagation is a combination of optical flow warping and optimal patch labeling in regions where motion is unreliable.

The whole propagation process is illustrated by Figure 4.

For the sake of simplicity, we assume in the following that a keyframe u k has been stylized (the stylized version is written u k ) and that we wish to propagate the style to all the frames u t for t in the set [k +1, k +r -1]. Writing t ⋆ = t-1, style is propagated in the forward direction from both images u t ⋆ and u k to u t (if t = k + 1, both images u t * and u k are identical). The propagation in the backward direction follows the same path, using t * = t + 1. The propagation between two keyframes in the first part of the algorithm is similar, starting from the central keyframe stylized by Split an Match, and propagating first to subsequent frames and second to previous keyframes.

To estimate motion fields between successive frames, we rely on the recent DeepFlow algorithm [START_REF] Weinzaepfel | DeepFlow: Large displacement optical flow with deep matching[END_REF], which combines a variational approach with descriptor matching to compute a dense offset map from a pair of images. The motion field between u t ⋆ and u t is written as an offset map ∆ t ⋆ ,t such that u t * (x + ∆ t ⋆ ,t (x)) ≃ u t (x) everywhere. We denote the warping of u t ⋆ by

u w t := W (u t ⋆ , ∆ t ⋆ ,t ) = u t * (. + ∆ t ⋆ ,t (.)),
where u t * is interpolated by bicubic interpolation on non integer coordinates. Optical flow between non successive frames (for instance two keyframes) is obtained by composition of successive pairwise optical flows. A first estimate of the stylized frame u t is given by u w t := W ( u t ⋆ , ∆ t ⋆ ,t ). Obviously, warping the pre-viously stylized frame u t ⋆ by optical flow encourages temporal coherence between u t and u t * , but optical flow estimation is not always reliable, and motion vectors remain unknown in some areas (occlusions, domain boundaries). To address these limitations, we compute a reliability map, defined as a combination of an occlusion map and a motion accuracy map. The motion accuracy map is defined as the set of pixels such that the absolute error between the original frame and the motion warped frame is larger than a threshold τ e (set in practice to 25)

A t (x) = 1, if |u t (x) -u w t (x)| < τ e , 0, otherwise.
According to [START_REF] Sundaram | Dense point trajectories by gpu-accelerated large displacement optical flow[END_REF], a simple and effective approach to compute occlusions is to take the residual between the forward and the backward optical flow:

O t (x, y) = 1, if |∆ t ⋆ ,t (x) + ∆ t,t ⋆ (x)| 2 < τ m , 0, otherwise,
where τ m := 0.01(|∆ t ⋆ ,t | 2 + |∆ t+1,t | 2 ) + 0.05. Thus, the set of coordinates where optical flow is not reliable and where style transfer needs to be resynthesized is given by

χ t = (x, y) ∈ Ω A t (x, y)O t (x, y) = 0 . (6)
In order to re-synthesize style on χ t , we start by computing a quadtree partition R = {R i } n i=1 for u t , with a variance only stopping criteria (threshold set to 15 in practice) for the quadtree splitting. Next, we divide this partition in two sets R = R ′ ∪ R ′′ , where

R ′ = {R i ∈ R ′ ; χ t ∩ R i = ∅}
is the set of patches to be relabeled and R ′′ the set of patches considered as already stylized. Temporal style propagation on R ′ can be posed as a supervised style transfer, in the spirit of [START_REF] Hertzmann | Image analogies[END_REF]. Indeed, we know both the keyframe u k and its stylized version u k , and we can take advantage of this knowledge to compute u t . The core idea is that if two patches u t (R i ) and u k (R) are similar in structure, then the patch u t (R i ) should be similar in style to u k (R). Since u t and u k are expected to have considerable overlapping content, it also turns out to be much easier to find patch correspondences between them than between u t and the exemple image v. Consequently, for each region

R i in R ′ , a set of M can- didate labels L i = {l im } M m=1 is selected by computing the M-nearest neighbors of the patch u t (R i ) in u k .
Next, we search for the optimal set of label assignments

L = { l i } #R ′ i=1 (with #R ′ the size of R ′ ) minimizing the energy E(L) = λ d E d (L) + λ s E s (L) + λ t E t (L), ( 7
)
where E d is a data fidelity term, E s is a spatial smoothness term, E t a temporal coherence term and λ d , λ s , λ t the respective weights of each term. These three terms are defined as follows:

1. The data fidelity term is given by

E d (L) = #R ′ i=1 d[u k (R li ), u t (R ′ i )]. ( 8
)
It can be noted that this data term differs from the one used for single image style transfer, since it compares patches of the non-stylized images u t and u k . 2. The spatial smoothness term is defined as

E s (L) = (i,j)∈N d ∩ [ u k ( R li ), u k ( R lj )]. (9)
to encourage smooth transitions between stylized patches (we remind that the notation R denotes extended regions, see Section 3). 3. The temporal coherence term is given by

E t (L) = #R ′ i=1 d[u c t (R i ), u k (R li )], (10)
where u c t is a combination of u w t (stylized frame u t ⋆ warped by optical flow) and u t , defined as

u c t := [(1 -1 χt ) ⊙ u w t ⋆ ] + [1 χt ⊙ u t ]. (11)
This temporal coherence favors intensities of a stylized patch at time t to remain similar to the warped intensities from t ⋆ for all coordinates where optical flow is reliable. This temporal coherence is already guaranteed for patches contained in R ′′ .

Once the optimal set L has been estimated by Loopy Belief Propagation, we use the bilinear patch blending described in Section 3 to obtain an image u l t . The final reconstructed image is

u t := G t ⊙ u w t + (1 -G t ) ⊙ u l t , (12)
where G t := G σ * (1 -1 χt ) is the optical flow reliability map convolved by a gaussian kernel G σ with standard deviation σ, for spatial blending between the motion warped image u w t and the labeled image u l t . Temporal style propagation is summarized in Algorithm 3.

Algorithm 3 TSP (Temporal Style Propagation)

Input: (U k,k+r , u k , k, ǫ) Output: U k,k+r 1: t ← k + ǫ 2: while t = k + r do 3: t ⋆ ← t -ǫ 4:
∆ t ⋆ ,t ← optical flow between u t ⋆ and u t 5: 6:

Warp u t ⋆ and u t ⋆ : 7:

u w t ← W (u t ⋆ , ∆ t ⋆ ,t ) 8: u w t ← W ( u t ⋆ , ∆ t ⋆ ,t ) 9: 10:
Compute the motion accuracy map 11:

A t (x) ← |u t (x) -u w t (x)| < τ e 12:
Compute the occlusion map 13:

O t (x) ← |∆ t ⋆ ,t (x) + ∆ t,t ⋆ (x)| 2 < τ m 14:
Compute the set of coordinates to be resynthesized 15:

χ t ← (x) ∈ Ω O t (x)A t (x) = 0 16: 17:
Select the set of patches R ′ to be labelled by style transfer: 18:

R ′ ← {} 19:

for every region

R i ∈ R do 20: if R i ∩ χ t = ∅ then 21: R ′ ← R ′ ∪ {R i } 22:
end if 23:

end for 24:

Compute M-nearest neighbors: 25:

L i ← L i = {l i m } M m=1 with |l i m -l i m+1 | > χ 26:
Compute optimal labels L for patches in R ′ : 27:

L ← min E(L) 28:

Compute u l t 29: u t ← u l t blended with u w t 30: 31: t ← t + ǫ 32: end while

Forward-backward blending

Temporal style propagation is applied for all sets of frames {u k+1 , u k+2 , ..., u k+r-1 } delimited by a "left keyframe" u k and "right keyframe" u k+r , both in a forward and in a backward pass. We denote the stylized sequence

Input video Stylized video

Fig. 5: Temporal Style Propagation. On the left, original frames, and on the right, stylized frames. Once keyframes have been stylized, for each "chunk" of frames between two keyframes u k and u k+r , we propagate the style from the stylized left keyframe u k in forward direction to all images u t , then we propagate the style from u k+r in backward direction and finally we blend the forward and backward stylized frames by linear interpolation. This stylization "by chunks" is repeated until the end of sequence.

resulting from forward style propagation by U f k,k+r = { u f t } k+r-1 t=k+1 and the sequence resulting from backward propagation as U b k,k+r = { u b t } k+r-1 t=k+1 . We can finally compute u t as a blend of the forward and backward pass

u t = α t u f t + (1 -α t ) u b t , (13)
where α t is the linear temporal weighting factor given by

α t = k + r -t k + r -k . ( 14
)

Experiments

In this section, we provide some results obtained with the style transfer method described in this paper. In Fig. 6 we present an experiment with our style transfer method applied to two different still images with the styles of Signac and Seurat. Remaining experiments concern our method applied to videos. Video results can be found at our project website: http://oriel. github.io/video_style_transfer.html.

The results in Fig. 7 and Fig. 8 were obtained with sequences taken from the Sintel dataset [START_REF] Butler | A naturalistic open source movie for optical flow evaluation[END_REF], which includes ground truth optical flow and occlusions. Thus, for these results, we use the optical flow and occlusion maps provided with the dataset.

In Fig. 9 we illustrate the interest of a temporally coherent video style transfer in comparison to the application of an image style transfer method in a frame-byframe manner. It can be noted in Fig. 9, (in particular on the highlighted red and blue rectangles) that our method guarantees temporal coherency of style, while a stylization performed independently for every frame unsurprisingly results in severe texture variation.

Finally, in Fig. 11, we compare our method to the recent work [START_REF] Ruder | Artistic style transfer for videos[END_REF] on a real sequence. In Fig 10, we present the data that were used to compare our method to [START_REF] Ruder | Artistic style transfer for videos[END_REF]. The top row shows frames of the original sequence, while the second row shows the various style images that were used. Results are then shown in Fig. 11.

For [START_REF] Ruder | Artistic style transfer for videos[END_REF], we used a GPU GTX980 with 4G memory. To fit in memory, the video had to be downsampled to a resolution 440 × 400, and the computation took several hours. Our method runs on CPU and the computation took 45 minutes.

It must first be stated that quantitative evaluation is impossible since there is no ground truth, and different artistic choices can be rated differently by users. The neural method consists in matching statistics over the layers of a deep pre-trained convolutional network. It has been known that some of these layers corresponds to Gabor filters. For this reason, results of [START_REF] Ruder | Artistic style transfer for videos[END_REF] exhibit a better stylization of contours. However, we think that our results preserve better the color tones

Conclusion

This paper has proposed a new approach for video style transfer, in which temporal style propagation is used to obtain temporal coherence between stylized frames. We have seen that the extension of style transfer from images to videos is not straightforward, as a stylization in a frame-by-frame basis is very likely to result in flickering. Thus, we proposed a technique that guarantees a temporally coherent stylization by propagating the style from keyframes. For that, we relied in a combina-tion of optical flow warping and style resynthesis. Our results show that such a technique is well adapted for stylization of videos. However, it should be noted that the quality of video stylization is strongly dependent on the accuracy of optical flow estimation. Hence, our video style transfer would clearly benefit from advances in the field of optical flow estimation. Furthermore, we have shown that decomposing input images into an adaptive patch partition is an efficient approach not only for image style transfer, but also for the extension of style transfer to videos. In this sense, our results suggest, together with [START_REF] Elad | Style-transfer via texturesynthesis[END_REF], that adaptive patches are useful to obtain a completely unsupervised style transfer in which no previous learning is required, differently to the neural network approach [START_REF] Ruder | Artistic style transfer for videos[END_REF]. Another clear advantage of our approach is the reduced computational complexity: while our method needed less than a hour to stylize the video of Fig. 11 using the CPU, the neural network approach needed several hours of processing in a GPU. Canaletto sketch style

Our results

Results by Ruder et. al

Van gogh style

Our results

Results by Ruder et. al [START_REF] Ruder | Artistic style transfer for videos[END_REF] Fig. 11: Real sequence results, where we compare out method to the neural artistic style transfer for videos [START_REF] Ruder | Artistic style transfer for videos[END_REF].

For each style image, the first row corresponds to our method and the second row is [START_REF] Ruder | Artistic style transfer for videos[END_REF]. Result comparison may be subjective and therefore challenging. Nevertheless, for the sketch style, it can be noted that our method stylize consistently the two walls of the bridge, while in the result of [START_REF] Ruder | Artistic style transfer for videos[END_REF], the left wall is brighter and the right wall is darker. As remarked by [START_REF] Fišer | Stylit: Illuminationguided example-based stylization of 3d renderings[END_REF], stylization by neural networks may be unpredictable at times.

Fig. 1 :Fig. 2 :

 12 Fig.1: On the left, MRF over a regular grid and on the right MRF over an adaptive image partition. The bottom layers represent image units from the observed scene, while nodes in the top layer represent hidden image units that we search to estimate through inference. Vertical edges represent data fidelity terms, while horizontal edges represent pairwise compatibility terms.No match found

Fig. 3 :

 3 Fig. 3: Illustration of the bilinear blending used to avoid stitching artifacts.

Input: 2 2:Fig. 4 :

 24 Fig.4: Overview of our Temporal Style Propagation (TSP). Assuming that the frame u t ⋆ has been stylized, we show how to propagate the stylization to u t (t ⋆ = t -1 when we propagate in the forward direction). On the left, the stylized frame u t ⋆ . Motion warping is applied to the stylized keyframe u t ⋆ to obtain a first estimate of the stylized frame u t . Since motion is not reliable everywhere, a motion reliability map is also deduced (unreliable pixels are shown in black). To improve the first estimate of u t , we re-synthesize all regions containing unreliable pixels by solving an optimal labeling problem. The final stylized image u t (on the right) is obtained by blending the re-synthesized regions with the motion warped estimate.

  B a c k w a r d p r o p a g a t i o n F o r w a r d p r o p a g a t i o n

Fig. 6 :

 6 Fig. 6: Results of our still image style transfer method with Signac's and Seurat's paintings as examples. Top row: example images, Left column: original images.

Fig. 7 :

 7 Fig.7: Video style transfer results for three different sequences from Sintel[START_REF] Butler | A naturalistic open source movie for optical flow evaluation[END_REF] with the painting "Cry" by Edvard Munch as example image. It can be noted that the stylized frames resulting from our video style transfer method have temporally coherent style.

Fig. 8 :

 8 Fig.8: Video style transfer results for Sintel synthetic sequence[START_REF] Butler | A naturalistic open source movie for optical flow evaluation[END_REF] and two different example styles. Top row: example images, Left column: original images. It can be noted that the stylized frames resulting from our video style transfer method have temporally coherent style.

Fig. 9 :

 9 Fig.9: Illustration of our temporally coherent video style transfer. The top row shows the middle frame of the original sequence, as well as the example style image (Van Gogh). Next rows show the results of the style transfer, using the frame-independent technique of[START_REF] Frigo | Split and match: Example-based adaptive patch sampling for unsupervised style transfer[END_REF] (left column) and the presented algorithm (right column). It can be noted that the stylized frames generated with frame-by-frame stylization, suffer from texture flicker. The brush strokes highlighted by the red and blue rectangles change abruptly from a frame to the next. On the right column, we show the stylized frames resulting from our video style transfer method, which has temporally coherent style.

FramesFig. 10 :

 10 Fig. 10: Data used for the real sequence comparison. The top row shows the frames of the original sequence, while the second ow shows the style images.

http://join.lovingvincent.com/

https://deepart.io/

http://prisma-ai.com/


Valentin Touzeau
email: valentin.touzeau@imag.fr

Claire Maïza
email: claire.maiza@imag.fr

David Monniaux
email: david.monniaux@imag.fr

Model Checking of Cache for WCET Analysis Refinement *

Keywords: Worst Case Execution Time, Cache Analysis, Model Checking, Least Recently Used Cache

On real-time systems running under timing constraints, scheduling can be performed when one is aware of the worst case execution time (WCET) of tasks. Usually, the WCET of a task is unknown and schedulers make use of safe over-approximations given by static WCET analysis. To reduce the over-approximation, WCET analysis has to gain information about the underlying hardware behavior, such as pipelines and caches. In this paper, we focus on the cache analysis, which classifies memory accesses as hits/misses according to the set of possible cache states. We propose to refine the results of classical cache analysis using a model checker, introducing a new cache model for the least recently used (LRU) policy.

INTRODUCTION

On critical systems, one should be able to guarantee that each task will meet its deadline. This strong constraint can be satisfied when the scheduler has bounds on every tasks' execution time. The aim of a WCET analysis is to compute such safe bounds statically. In order to provide a satisfiable bound, the WCET analysis needs to model the execution of instructions at the hardware level. However, to avoid the huge latency of main memory access, one can copy parts of the main memory into small but fast memories called caches. In order to retrieve precise bounds on the execution time of instructions, it is thus mandatory to know which instructions are in the cache and which are not. In this paper we focus on instruction caches, ie. we aim at knowing whether instructions of the program are in the cache when they are executed.

For efficiency reasons, the main memory is partitioned into fixed size blocks. To avoid repeated accesses to the same block, they are temporary copied into the cache when requested by the CPU. This way, they can be retrieved faster on the next access, without requesting the main memory again. Moreover, to speed up the retrieval of blocks from the cache, caches are usually partitioned into sets of equal sizes. A memory block can only be stored in one set that is uniquely determined by the address of the block. Thus, when searching a block in the cache, it is looked for in only one set. Since the main memory is bigger than the cache, it may happen that a set is already full when trying to store a new block in it. In this case, one block of the set has to be evicted in order to store the new one. This choice does not depend on the content of the other sets and is done according to the cache replacement policy. In our case, we focus on the Least Recently Used (LRU) policy (for other policies, refer to [START_REF] Lv | A survey on static cache analysis for real-time systems[END_REF]). A cache set using the LRU policy can be represented as a queue containing blocks ordered from the most recently accessed (or used) to the least recently accessed. When the CPU requests a block that is not in the cache (cache miss), it is stored at the beginning of the queue (it becomes the most recently used block) and the last block (the least recently used) is evicted. On the other hand, when the requested block is already in the cache, it is moved to the beginning of the queue, delaying its eviction. The position of a block in the queue is called the age of the block: the youngest block is the most recently used and the oldest is the least recently used.

The aim of a cache analysis is to provide a classification of memory accesses as "cache hit", "cache miss" or "unknown" (not always a hit, and not always a miss) to be used as part of the WCET analysis. This classification is usually established by abstract interpretations called "May Analysis" and "Must Analysis" that respectively compute a lower and upper bound of every block's age. For more details about these analysis, refer to [START_REF] Ferdinand | Cache behavior prediction for real-time systems[END_REF]. Must analysis is used to predict the cache hits (if a block must be in the cache when accessing it, access is a hit), whereas may analysis is used to predict the misses (if a block may not be in the cache when accessing it, access is a miss). However, if a block is in the may cache but not in the must cache, it is classified as unknown. This can happen because this access is sometimes a miss and sometimes a hit, or because the abstract interpretation is too coarse. An example is given on Figure 1. Program states (basic blocks) are on the left, whereas abstract cache states (may and must) at the exit of basic blocks are on the right. For simplicity, every basic block is stored in exactly one memory block. For example, at the exit of block 5, the minimum age of blocks a, b, c and d computed by the may analysis are respectively 1, 0, 2 and 1. At block 6, a is accessed and is in the cache (because there are only 4 different blocks, and they all fit together in the cache), thus it should be classified as a hit. However, it is classified as "unknown" by the may and must analysis because of an over-approximation performed by the must analysis. Indeed, at entry of block 5, the must cache is [⊥, ⊥, ⊥, a] because a is the only block that must be accessed, and b, c and d may be accessed since the last access to a. An other possibility to classify memory access as hit or miss is to use a model checker. Both the program and the cache are encoded as a transition system. Then, the question of the existence in the cache of a given block at a given program point is encoded as a logical formula. Both the formula to check and the transition system are provided to the model checker, that classifies the block as "in the cache", "out of the cache" or "unknown". Since the model deals with every reachable program/cache states separately, model checking is usually more precise than abstract interpretation. However, it is also much slower and often requires more memory during the analysis.

To avoid the precision loss of abstract interpretation without performing a heavy analysis using a model checker, we propose to mix both analysis. We first perform the classical may/must analysis by abstract interpretation, and then refine the classification using a model checker. Thus, we only use the model checker to classify blocks that were classified as "unknown" by the abstract interpretation. Moreover, we introduce a new abstract model that can be used by the model checker to efficiently represent LRU cache states.

WCET ANALYSIS

This section gives some basic notions about WCET analysis and explain the link with cache analysis.

Usually, WCET analysis are performed by following steps: First, a control flow graph is retrieved from the binary code under analysis by grouping instructions into basic blocks (sequences of instructions with only one entry point and one exit point). Then, the WCET of the program is computed by bounding the execution time of every basic block and finding the "longest" path inside the CFG.

The computation of basic blocks execution time is done by micro-architectural analysis that models pipelines and caches. Independently, several other analysis like value analysis and loop bound analysis are performed to provide information about the semantics to the WCET analyzer.

At hardware level, the uncertainty about execution times of instructions comes from pipelines (which can start executing an instruction before the previous one is finished) and caches (which avoid costly main memory accesses). The aim of a cache analysis is to classify memory accesses as cache hit or cache miss. Since an access to the main memory can be 100 times slower than an access to a cache, it is mandatory to classify memory access as hit/miss in order to provide accurate bounds on WCET estimations. Moreover, when a memory access is not classified as a hit or a miss, the WCET analysis must treat the both cases [START_REF] Cullmann | Predictability considerations in the design of multi-core embedded systems[END_REF]. Thus, it can make the analysis slower and increase the pessimism.

To avoid this precision loss, we aim at refining the classification of unknown block using a model checker.

RELATED WORK

Some previous works use a model checker for performing WCET analysis of programs. The approach of Lv, Yi, Guan and Yu [START_REF] Lv | Combining abstract interpretation with model checking for timing analysis of multicore software[END_REF] is the following.

Using abstract interpretation, they classify memory access as "cache misses", "cache hits" or "unknown". Every memory access is translated in a timed automaton that describe the access to the memory bus by introducing some delay. Finally, these automata are connected together according to the CFG and the model checker explores the transition system, computing a WCET estimation. This approach allows them to perform WCET analysis of multicore systems. Although they are using a model checker in a WCET analysis, our approach is different and complementary. Indeed, they are using the model checker to refine the timing analysis itself, and not the classification of memory accesses as we do. Therefore, our refinement of the cache content can be added to the first step of their analysis to retrieve better bounds. The work of Chattopadhyay and Roychoudhury [START_REF] Chattopadhyay | Scalable and precise refinement of cache timing analysis via model checking[END_REF] is closer to our approach. They use the model checker to analyze behavior of caches shared by several cores. Moreover, by instrumenting the program at source code level they can take the program semantics into account and do not treat infeasible path, make the analysis more precise. Since they are performing a may/must analysis as a first step, we believe our analysis can be used to refine this first step, before taking shared caches into account.

OUR ABSTRACT MODEL

To perform the cache analysis using a model checker, we have to provide models both for the program and for the cache. We use these models to answer the following questions: "At a given program point, is a given block in the cache whatever the path to reach this point is ?" (classify as hit) and "Is the given block never in the cache at the given program point, whatever the path used to reach this point is ?" (classify as miss).

To model the cache, we use an abstraction of the real cache state to avoid the state space explosion problem one can meet when using a model checker. In the following formal description of our model, we adapt the notations from Jan Reineke's PhD [START_REF] Reineke | Caches in WCET Analysis: Predictability -Competitiveness -Sensitivity[END_REF]: In addition of these notation, to define our abstract model, we introduce the following notations: A, represents the set of abstract cache states, εa ∈ A, represents cache states that does not contain a, and [S]a ∈ A, represents cache states that contains a and some other blocks younger than a (forming the set S), where a ∈ M is a memory block.

Definition 4. Set of Abstract Cache States

A = P(C LRU ) is the power set of reachable cache states.

Definition 5. Abstract Cache States εa = [b1, ..., b k ] ∈ C LRU , ∀i ∈ 1, k , bi = a ∈ A [S]a = [b1, ..., b k ] ∈ C LRU , ∃i ∈ 1, k , bi = a ∧ (bj ∈ S ⇔ j < i) ∈ A
The idea behind the abstract model we define below is to track only one block (noted a). Indeed, to know whether a block is in a LRU cache, you only have to count the number of accesses made to pairwise different blocks since the last access to it. In other words, you do not have to know the age of others blocks, you are only interested in knowing if they are younger than the block you are tracking. Therefore, we group together cache states that have the same set of blocks younger than the block we want to track.

To every cache state p, we associate an abstract state αa(p) which consists of the set of values younger than a in the cache or a special value in the case where a is not in the cache.

Definition 6. Abstraction of Cache States

αa : C LRU → A αa ([b1, ..., b k ]) = εa if ∀i ∈ 1, k , bi = a [{b1, ..., bi-1}]a if ∃i ∈ 1, k , bi = a
For example, when tracking block a, the abstract cache state associated to the exit of block 1 of Figure 1 is [{}]a, symbolizing that a is the least recently used block at this point (the set of younger blocks is empty). At the exit of block 4, the abstract cache state is [{b, c, d}]a.

Additionally, we define the partial function update a LRU (k) , which models the effect of accessing a block on an abstract state. When the abstract cache state does not contain a (i.e. is equal to εa), it remains unchanged until an access to a is made. When a is accessed, every new block access appears into the set S. When the cardinal of S reaches k -1 (a is the least recently used block), a new access to a different block evicts a (and new abstract cache state is reset to εa). If an access to a is done in the meantime, the set S of younger block is reset to {}.

Definition 7. Abstract State Update update a LRU (k) : A × M → A update a LRU (k) (εa, c) = [{}]a if a = c εa if a = c update a LRU (k) ([S]a, c) =          [{}]a if c = a [S]a if c = a and c ∈ S [S ∪ {c}]a if c = a and c / ∈ S and |S| < k -1 εa if c = a and c / ∈ S and |S| = k -1
Considering the example of Figure 1, the model checker associates two different abstract states to block 5 depending on the incoming flow from block 1 or block 4. These states are respectively [{}]a and [{b, c, d}]a. Thus, applying the update function for treating the access made to b in block 5, we obtain [{b}]a and [{b, c, d}]a. Therefore, we know that a is not evicted from the cache by block 5 and access made to a in block 6 is not classified as unknown anymore but as a hit.

The second part of our model is the model of the program. Since we focus on instruction caches, the model we use for the program is a graph obtained from the CFG by splitting basic blocks (when needed) into blocks of the size of a memory block. Thus, a path in the model represents the sequence of memory access that the instruction cache handles during the execution of the program. However, because we only track one memory block at a time, it is also possible to simplify the control flow graph according to this block. Indeed, one can slice the CFG according to the cache set associated to the block we want to track, removing every memory access to an other cache set.

Moreover, we can remove from the obtained graph every node that is not an access to a and that does not contribute to a eviction. Thus, it appears that every node that does not contain a in their entry may cache can be removed. This simplification of the CFG is illustrated on Figure 2. Plain arrows represent program flow potentially manipulating block a, whereas dashed arrows represent flow that does not and that can be simplified in only one arrow. At some point after an access to block a, we can be sure that a is not in the cache anymore. Therefore, it is possible to remove all nodes (dashed arrows) from this point until the next access to a.

IMPLEMENTATION / EXPERIMENTS

This section describe the prototype we build and the experiments we made to valid our proof of concept. The workflow of our analysis is illustrated on Figure 3.

Our implementation does not use directly the binary code to analyze but runs on the LLVM bytecode representation of it. We first build the CFG of the program from the bytecode using the LLVM framework. Since the

Figure 1 :

 1 Figure 1: Example of access classified as "unknown"

Definition 1 .Definition 2 .Definition 3 .

 123 Cache size k ∈ N is the size of the cache set (in blocks) Set of memory blocks M represents the set of memory blocks. M ⊥ = M ∪ {⊥} includes the empty line. Set of Cache States C LRU ⊂ M k ⊥ symbolizes the set of reachable cache states [b1, b2, . . . , b k ] ∈ C LRU represents a reachable state b1 is the least recently used block

Figure 2 :

 2 Figure 2: Simplifying CFG according to access to a

* This work was partially supported by the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement nr. 306595 "STATOR".

LLVM bytecode does not affect any address to instructions, we have to provide a mapping of instructions to the main memory. For our prototype, we assume that every instruction has the same size in memory. Thus, memory blocks contain a fixed number of instructions and can be obtain by splitting basic blocks of the CFG into fixed size blocks. Using this mapping and the CFG, our prototype performs a may/must analysis of the program. For every block access classified as unknown, we build an abstract model of the cache and provide it to the model checker together with the CFG (simplified as explain above). It would be possible to use real addresses from binary code and a correspondence between LLVM bytecode and binary code, as done in [START_REF] Henry | How to compute worst-case execution time by optimization modulo theory and a clever encoding of program semantics[END_REF], but this requires significant engineering and falls outside of the scope of this experiment.

We experiment our prototype with benchmarks of the TacleBench 1 .

Table 1 contains the results of our experiments.

Size of program is given in number of memory block. We run our experiments with caches of only one cache set, with different sizes: 4, 8 or 16 ways. For every experiment, we measure both the amount of accesses classified as "unknown" by the may/must analysis (column "Un") and the amount of accesses newly classified as "always in the cache" or "always out of the cache" among the accesses left "unknown" by the may/must analysis (column Nc). During these experiments, our analysis classifies up to 57.8% of the accesses left unclassified by the abstract interpretation analysis.

CONCLUSION

We proposed to refine classical cache analysis by using a model checker. To avoid the common problem of state space explosion meet when dealing with model checking, we introduce a new abstract cache model. This model allows 1 http://www.tacle.eu/index.php/activities/taclebench us to compute the exact age of a memory block along an execution path of the program. Thus, we can select the memory block we want to refine. Moreover, it allows us to simplify the program model too, by removing some nodes useless to the refinement. Finally, we implement a prototype and test it on a benchmark. Our experiments shows that our approach is able to refine up to 60% of the memory access classified as unknown by the abstract interpretation.

Our prototype runs on LLVM bytecode, and use an unrealistic memory mapping. As future work, we aim at implementing an analyzer that runs on the binary code. To finally validate our approach, it is also possible to compare the performance of our analysis to other analysis refining may/must analysis, like persistence analysis or analysis performing virtual inlining and unrolling.


Dorin Maxim
email: dorin.maxim@loria.fr

Antoine Bertout
email: antoine.bertout@inria.fr

Analysis and Simulation Tools for Probabilistic Real-Time Systems

Keywords: Simulation, Probabilistic Real-Time Systems, Probabilistic Analysis, pWCET, pMIT

In this paper we present two tools meant to simulate and analyze probabilistic real-time task sets. That is, tasks sets which have their timing parameters represented by discrete probabilistic distributions. We describe the main features of each tool and provide configuration details necessary to use them. The two tools are compared, pointing out the advantages and disadvantages of each one, so that interested users can make an informed choice regarding which tool best fits their needs. Both tools are open source and freely available. One of the main objectives of this paper is to make these tools available to the real-time systems research community, which is also invited to participate in their improvements, by giving feedback and even extending the implementations.

I. Introduction

In the real-time community, numerous theoretical analyses have been developed to assess the capability of a system to respect its timing constraint, in other words, its schedulability. In that context, a system is generally described as a set of tasks that are successively released, each described by their worst-case parameters (execution time, arrivals pattern, offset, etc). Analyses have been proposed to compute if the system is schedulable or not. Another way of checking the schedulability of the systems, and at the same time having more details about the execution of various tasks in a given interval (job response time, starting executions date, etc.) is by simulating its run-time execution. This is generally counterbalanced by an accepted (empirical) margin of error introducing a large amount of pessimism to compensate for the potential optimism of the initial results.

Recently, a new trend has emerged for analyzing realtime systems, in the form of probabilistic analysis [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF]- [START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for multi-path programs[END_REF]. That is, task parameters are described using probability distributions (as opposed to single worst-case values) and the analysis computes response time probability distributions from which it is possible to extract the probability that a job may miss its deadline. Probabilistic analyses of real-time systems provide levels of confidence on the response time distributions, helping to assess how safe its use is in practice. Nevertheless, the analysis of some systems might be excessively hard to compute especially considering multiple probabilistic parameters (as probabilistic worst-case execution time and probabilistic minimal inter-arrival time) and asynchronous arrivals of jobs due to the complexity as well as the amount of convolution operations required. An alternative to analyzing a probabilistic task set is to simulate it and gather the relevant information from the traces observed, such as frequency of response times. Although there exist currently several analysis methods for probabilistic realtime systems, very few simulation tools have been proposed by the community. In this paper, we present two tools able to simulate probabilistic task set. The tools are freely available for the community, with great potential to being extended to enhance their capabilities.

Related works:

Various simulators exist to evaluate deterministic task sets (by deterministic we mean that they are not probabilistic). For instance, MAST [START_REF] Harbour | Mast: Modeling and analysis suite for real time applications[END_REF] and Cheddar [START_REF] Singhoff | Cheddar: a flexible real time scheduling framework[END_REF] both provide analysis and simulation. SimSo [START_REF] Chéramy | Simso: A simulation tool to evaluate real-time multiprocessor scheduling algorithms[END_REF] is focused only on the simulation of multiprocessor realtime system with consideration of overhead. Also written in Python, pyCPA [START_REF] Diemer | Compositional performance analysis in python with pycpa[END_REF] is an implementation of the Compositional Performance Analysis approach to analyze worst-case timing behavior of real-time distributed systems. CPAL [START_REF]Cpal[END_REF] is meant to be both an analysis and simulation tool, as well as programming language for real-time systems, in the sense that the simulated model can directly be deployed on the hardware and the system obtained has the same (timing) properties as the simulated one. An existing simulator that can handle probabilistic execution times and probabilistic inter-arrival times of tasks is RTSim [START_REF] Palopoli | An object-oriented tool for simulating distributed real-time control systems[END_REF]. We note that RTSim is not specifically targeted towards probabilistic simulations, but towards deterministic ones.

Organization of the paper:

In Section II we describe our system model composed of tasks with probabilistic parameters. Section III is dedicated to the presentation of PAnSim and of an extension of SimSo, two tools able to simulate probabilistic task sets. We provide a comparison of the two tools in Section IV before concluding in Section V.

II. Model

In this section, we present the task set model used for the simulation and analysis of probabilistic real-time systems. We model the system as a set of n tasks {τ 1 , τ 2 , ..., τ n } scheduled by a preemptive algorithm. Each task τ i generates an infinite number of successive jobs τ i.j , with j = 1, . . . , ∞. All jobs are assumed to be independent of other jobs of the same task and those of other tasks. We assume that a job may miss its deadline and postpone the execution of the next job of the same task.

Each task τ i is characterized by a probabilistic worstcase execution time (pWCET) denoted by C i and by a probabilistic minimal inter-arrival time (pMIT) denoted by T i .

Each parameter is represented by a random variable X having a probability distribution f X (•) with f X (x) = P (X = x). The possible values of X i belong to the interval [X min , X max ]. In this paper we associate the probabilities to the possible values of a random variable using the following notation:

X = X 0 = X min X 1 • • • X k = X max f X (X min ) f X (X 1 ) • • • f X (X max ) where k j=0 f X (X j ) = 1.
The notions of pWCET and pMIT are defined as follows.

For more details about these concepts, the reader can refer to [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF].

Definition 1 (From [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF]). The probabilistic execution time (pET) of a job of a task describes the probability that the execution time of the job is equal to a given value.

Definition 2 (From [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF]). The probabilistic worst-case execution time (pWCET) of a task describes the probability that the worst-case execution time of that task is equal to a given value.

A safe pWCET C i is an upper bound on the pETs C j i , ∀j and it may be described by the relation as C i C j i , ∀j. Graphically this means that the CDF of C i stays under the CDF of C j i , ∀j. Following the same reasoning the probabilistic minimal inter-arrival time (pMIT) denoted by T i describes the probabilistic minimal inter-arrival times of all jobs. Definition 3 (From [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF]). The probabilistic inter-arrival time (pIT) of a job of a task describes the probability that the job arrival time occurs at a given value. Definition 4 (From [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF]). The probabilistic minimal interarrival time (pMIT) of a task describes the probability that the minimal inter-arrival time of that task is equal to a given value.

A safe pMIT T i is a lower-bound on the pITs T j i , ∀j and it may be described by the relation as

T j i T i , ∀j.
Graphically this means that the CDF of T i stays above the CDF of T j i , ∀j. A job of a task must finish its execution before its relative deadline D i with D i = T min i , i.e. the minimal value of the T i distribution. Hence, a task τ i is represented by a tuple (C i , T i , D i ).

We assume that the pWCET and pMIT distributions of two tasks τ i and τ j are independent [START_REF] Cucu-Grosjean | Independence-a misunderstood property of and for probabilistic real-time systems[END_REF]. In this paper, we use the terminology of the probabilistic worstcase response time analysis (pMIT and pWCET). The reader interested in the probabilistic (non worst-case) response time distributions can indistinctly use the same reasoning with pIT and pET parameters. The simulators later presented are agnostic of the chosen reasoning.

Existing probabilistic schedulability analyses [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF], [START_REF] Diaz | Stochastic analysis of periodic real-time systems[END_REF] produce task worst-case response time distribution pWCRT, counterpart of the deterministic worst-case response time (WCRT) [START_REF] Joseph | Finding response times in a real-time system[END_REF]). From the pWCRT, the deadline miss probability (DMP) of a task can be deduced.

III. The proposed simulators

In this section, we describe the two probabilistic simulators and provide an example of use by applying them on the task set depicted in Table I scheduled by a fixedtask priority policy. This task set has 5 tasks, and each task is represented by a pWCET distribution and a pMIT distribution, with 10 values per distribution. For the sake of simplicity all probabilities of appearance are equal to 0.1 and we omit them from the table. Task indexes give their priorities, with task τ 1 having the highest priority and task τ 5 having the lowest one. Throughout the rest of the paper we are interested in analyzing and simulating task τ 5 , unless otherwise specified.

A. PAnSim

PAnSim (short for Probabilistic Analysis and Simulation) is a MATLAB implementation (released under the CeCILL licence, compatible with GNU GPL) consisting of a simulator and an analysis tool. In this regard, PanSim is similar to MAST [START_REF] Harbour | Mast: Modeling and analysis suite for real time applications[END_REF] or Cheddar [START_REF] Singhoff | Cheddar: a flexible real time scheduling framework[END_REF]. The simulator takes as input real-time task sets with parameters given as discrete random variables: worst-case execution time distributions and minimal inter-arrival time distributions. Any of these distributions can be given as a single values distribution, in which case the parameter is deterministic. If all distributions are single values then the entire task set is deterministic, which is a special case of the probabilistic representation of real-time task sets. PAnSim supports fixed priority preemptive scheduling (FPPS) policies, but the simulator can easily be extended to dynamic scheduling policies as well as non-preemptive execution. The simulator also has two deadline miss policies: at the instance when a job misses its deadline it can either be allowed to continue or it can be stopped. The decision of stopping of continuing execution past deadlines is system-wide, meaning that the same policy is applied to all jobs that miss their deadlines and to all tasks amd this can not be changed during the simulation.

Listing 1 details how to define, simulate and analyze a probabilistic task set using a preemptive fixed-task priority scheduling policy with PAnSim, and the main functions of the tool are as follows:

Declaring tasks and task sets: In PAnSim a task is represented as a cell containing two arrays. The first array is the pWCET distribution and the second array is the pMIT distribution. Each of the two array has two lines of equal size, the first line being the possible values that the respective parameter can exhibit and the second line being the occurrence probabilities of these values. The minimal value of the pMIT distribution is consider to be the deadline of the task. This can be extended to the case of arbitrary deadlines or even probabilistic deadlines, but for the sake of simplicity we only present the case of implicit deadline here.

Once all tasks have been declared, the task set can be formed by adding all tasks to a cell array. The order in which the tasks appear in the cell array gives the priority ordering of the set, i.e. taskSet(1) has a higher priority than taskSet(2) which has a higher priority than taskSet(3) and so on.

1) Simulation tool:

Simulating the task set:

The functions simulateP astDeadline and simulateStopAtDeadline are used to perform the simulation of the given task set with two different strategies for deadline misses, i.e. continue the execution of jobs even past their deadlines, respectively abort jobs when they arrive at their deadlines without finishing execution. The simulation returns three outputs. The first output is a cell array containing vectors of observed response times for each task in the set (one vector per task). The other two outputs are used to plot the gantt chart of the run-time execution that was simulated.

The parameter numberOf JobsT oSimulate specifies how many consecutive jobs of the task on the lowest priority should be simulated. This is done in order to guarantee that the desired number of traces are obtained. An alternative way is to specify the length of the time interval to be simulated, but this does not guarantee an exact number of traces due to the probabilistic nature of the periods.

Plotting the results: The gantt chart of the simulated jobs can be plotted by calling the function plotExecutionSchedule. This plotting is meant for small number of jobs in order to obtain intuition from the visual representation of the run-time execution and it is recommended that the function be deactivated (by commenting it) when a large number of jobs is simulated as the gantt chart becomes difficult to read.

2) Analysis tool:

In order to analyze the task set, the function probabilisticW orstCaseResponseT ime needs to be called. This function takes as input four parameters. The first parameter is the task set itself. The second parameters specifies if the analysis should stop once there are no more preemptions that can modify the deadline miss probability (i.e. include only preemptions which arrive before the deadline of the task). The final two parameters specify if resampling is performed on the pWET and pMIT respectively. The re-sampling technique used is 'Uniform Spacing' as described in [START_REF] Maxim | Re-sampling for statistical timing analysis of real-time systems[END_REF] and [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF]. When the re-sampling parameter is zero then re-sampling is not performed, otherwise the parameter needs to be an integer k and in this case resampling will be performed every time the result of a convolution is larger than k.

The output of the analysis is the response time probability distribution of the last task in the input task set. In order to analyze a different task, then the input needs to be given in the form taskSet(1 : k) to analyze, e.g., task k in the set. Note that this function assumes that jobs are allowed to continue execution past their respective deadlines, and this is an upper-bound on the case when jobs are dropped at deadline. Also, computing response time distributions in the case when jobs are stopped at deadline is still an open problem.

The obtained theoretical response time distribution can be plotted alongside the empirical distribution of response times observed during simulation in order to compare the two results, as it is exemplified in the final lines of Listing 1. Also, from the theoretical distribution it is possible to extract the deadline miss probability of the task in order to check if it is lower than a given threshold.

PAnSim was used in the experimental section of [START_REF] Maxim | Response time analysis for fixed-priority tasks with multiple probabilistic parameters[END_REF] for the analytical evaluation and in [START_REF] Maxim | Study of the reliability of statistical timing analysis for real-time systems[END_REF] for doing the simulations necessary in the experimental evaluations. PAnSim is freely available online1 for the benefit of the real-time systems research community.

B. Probabilistic SimSo

We propose here a probabilistic extension for the real-time simulator SimSo [START_REF] Chéramy | Simso: A simulation tool to evaluate real-time multiprocessor scheduling algorithms[END_REF] (short for Simulation of Multiprocessor Scheduling with Overheads).

1) SimSo

: is an open-source multiprocessor simulator of real-time scheduling written in Python released under the CeCILL licence. It provides the main task generators, uniprocessor and multiprocessor scheduling policies and a convenient and concise way to specify new scheduling policies. SimSo also integrates different cache models to evaluate the overhead due to cache misses. Jobs that miss their deadlines can be stopped or allowed to continue (with the abort_on_miss boolean option in Listing 2) their execution and then eventually postpone further jobs. SimSo relies on a discrete-event simulation which allows it to deal with long intervals of simulation. SimSo is divided between the core and the graphical user interface (GUI).

The GUI adorns the core with a display of the gantt chart and scheduling results of the simulation2 . A scheduling configuration (task set, scheduler, etc.) can be described through an XML file, but it can also be directly written in Python using the core component. The separation of the core from the graphical user interface allows SimSo to be called and run as a Python module in a script which is very useful to process the scheduling results. In this regard, SimSo interestingly keeps record of a very complete set of scheduling metrics, such as job response times, number of context-switches, number of preemptions, job migration, etc. that are meaningful information for a later evaluation.

Beyond its very practical usage, SimSo relies on a modular architecture which makes it possible to provide extensions for it, such as the probabilistic extensions that we propose in this paper. In the following, we detail the major additions that have been made to extend the core component of SimSo from a deterministic to a probabilistic behaviour.

2) Probabilistic extension: a) pWCET: We added the possibility to use pWCET by using the concept of SimSo called Execution Time Models (ETM). An ETM is a class that determines the duration of the jobs during the simulation. By default, it can deal with WCET value but it can also dynamically change the execution time of a task during the simulation, taking into account some time overhead (e.g timing penalties coming from cache misses). We implemented a new ETM that draws at each execution the WCET from the pWCET distribution defined. b) pMIT: SimSo allows to define periodic but also sporadic behaviour of tasks by describing the arrival time instants in the configuration files in the interval of simulation chosen. We used this feature to add a step to the parser to generate a set of arrivals drawn from the pMIT defined in the configuration files.

Listing 2 details how to describe and simulate a probabilistic task set using a preemptive fixed-task priority scheduling policy (here Deadline Monotonic). The probabilistic parameters are defined by a vector of tuples corresponding to each random variable and its probability of appearance. The other parameters of the simulation are similar to those of the original SimSo tool and their use is straightforward and commented in the Listing 2. In particular, the logs object contains a set of scheduling metrics as the job response times. The complete set of the available metrics can be found on the SimSo documentation. The whole configuration file can be simply executed as a Python script. The probabilistic extension is fully compatible with the features (scheduling policies, performance metrics, etc.) of the standard core version of SimSo. In this respect, the extension benefits from the documentation of SimSo.

The probabilistic extension of SimSo is freely available online 3 and was recently used in [START_REF] Bertout | Average probabilistic response time analysis of tasks with multiple probabilistic parameters[END_REF].

IV. Comparison between the two simulators

In this section, we compare both tools over their modularity and extensibility, their environment and their functionality.

Modularity:

The extension of SimSo is based upon a powerful and modular simulator. For example, the scheduler is an option in the configuration file and there is no need to modify any line of code related to other functionality of SimSo to implement a new one. Adding a scheduling policy (PanSim implements fixed-task priority preemptive scheduling) in PAnSim is not a burden but requires to modify the core source code.

Environment: PanSim is written in MATLAB language and take advantages of the MATLAB environment. The latter proposes an interactive system that comes with the ability of plotting functions and data. This is particularly useful to compare probabilistic distribution. SimSo benefits from the large support of Python third party libraries (e.g numpy, matplotlib, etc.) but representing data 0.4 0.6 0. a general purpose simulator PanSim goes along with an analysis tool. The first has the advantage to provide a rich set of scheduling metrics of the simulations but the latter provides analytical distributions which may be useful for comparison purpose. PAnSim also does the analysis of the input task set. When the pMITs are single-values, then the analysis is reduced to the Diaz analysis presented in [START_REF] Diaz | Stochastic analysis of periodic real-time systems[END_REF]. If both pWCET and pMIT are deterministic the analysis returns the same result as the state of the art deterministic worst-case response time analysis introduced by [START_REF] Joseph | Finding response times in a real-time system[END_REF]. With both tools, defining and simulating a probabilistic task set is concise as shown in Listings 1 and Listing 2 for respectively PAnSim and SimSo.

The main differences between the two proposed simulators are summarized in Table II and in the rest of the paper we show the type of results that the tools can produce.

Table II.

Main differences between the proposed tools

PAnSim pSimSo

Language

MATLAB Python

Scheduling policies FPPS Several priority schemes

Performs analysis Yes No

Joint usage: We illustrate the possibilities offered by the joint usage of SimSo and PAnSim in Figure 1 and in Figure 2. • the solid line is an empirical 1-CDF distribution obtained by simulating the probabilistic task set and recording the observed response times for 5 • 10 5 consecutive jobs of τ 5 using the probabilistic extension of SimSo.

• for completeness, we have also added the deterministic worst-case response time obtained using the analysis in [START_REF] Joseph | Finding response times in a real-time system[END_REF]. We may note that this value is the largest of the probabilistic response time distribution and represented as a dotted vertical line.

We used the probabilistic extension of SimSo in a different way in Figure 2. We simulated 10 6 times the execution of the two first instances of τ 5 , i.e τ 5.1 and τ 5.2 to obtain their empirical worst-case response time respectively represented as a as a dotted curve. For comparison purpose, we also depicted the analytical probabilistic worst-case response times of the task in the synchronous case (first job). As expected, we can observe that the pWCRT computed with the analysis is an upper bound on the simulated pWCRT of the two first jobs of τ 5 . Interestingly, the simulation provides an approximation of any job pWCRT whose no theoretical analysis yet exists [START_REF] Bertout | Average probabilistic response time analysis of tasks with multiple probabilistic parameters[END_REF].

V. Conclusion

In this paper, we presented an extension of SimSo, a well known academic tool, and PAnSim, an in-house MATLAB implementation. These two tools are dedicated to the simulation and analysis of probabilistic task sets. We presented their characteristics and how they can be used, with strengths and weaknesses for each one of them. Another objective of this paper is to make the tools available to the real-time systems research community.

Many advancements and improvements can be made on each of the tools, such as adding new scheduling policies to PAnSim or adding the probabilistic interface to the graphical version of SimSo. The community is invited to participate in the improvement of these tools, either directly, e.g. by adding extensions and new implementations, or indirectly, by giving feedback to the authors of the tools.

Listing 2

 2 Simulation of a probabilistic task set with the extension of SimSo import sys from simso.core import Model from simso.configuration import Configuration def main(argv): configuration = Configuration() configuration.cycles_per_ms = 1 configuration.etm = "pwcet" configuration.duration = 381360 * configuration.cycles_per_ms # Add tasks:

Figure 1

 1 Figure1depicts the response times of task τ 5 (the task on the lowest priority in TableI) obtained in three different ways:• the dashed curve represents in the form of inverse cumulative distribution function (1-CDF) the probabilistic worst-case response times of the task in the synchronous case (i.e. worst-case conditions)

Figure 2 .

 2 Figure 2. Worst-case response time distributions of τ 5

Table I .

 I

						Probabilistic task set
	task
	τ 1	pWCET	134	137	140	143	146	149	152	155	158	161
		pMIT	3565	3637	3709	3781	3853	3925	3997	4069	4141	4213
	τ 2	pWCET	311	318	325	332	339	346	353	360	367	374
		pMIT	7784	7940	8096	8252	8408	8564	8720	8876	9032	9188
	τ 3	pWCET	2879	2949	3019	3089	3159	3229	3299	3369	3439	3509
		pMIT	26226	26751	27276	27801	28326	28851	29376	29901	30426	30951
	τ 4	pWCET	5540	5675	5810	5945	6080	6215	6350	6485	6620	6755
		pMIT	19617	20010	20403	20796	21189	21582	21975	22368	22761	23154
	τ 5	pWCET	3403	3486	3569	3652	3735	3818	3901	3984	4067	4150
		pMIT	32313	32960	33607	34254	34901	35548	36195	36842	37489	38136

https://github.com/dorinmaxim/PAnSim-Tool

A simpler and intuitive web version of SimSo is also available online http://projects.laas.fr/simso/simso-web which is especially useful for educational purposes

Acknowledgements

This work was partially supported by the RETINA Eurostars Project E10171.