Benjamin Rouxel
email: benjamin.rouxel@irisa.fr

Stefanos Skalistis
email: stefanos.skalistis@irisa.fr

Steven Derrien
email: steven.derrien@irisa.fr

Isabelle Puaut
email: isabelle.puaut@irisa.fr

Hiding Communication Delays in Contention-Free Execution for SPM-Based Multi-Core Architectures

Keywords: 2012 ACM Subject Classification Computer systems organization → Embedded and cyber-physical systems; Computer systems organization → Real-time systems Real-time Systems, Contention-Free Scheduling, SPM multi-core architecture Digital Object Identifier 10.4230/LIPIcs.ECRTS.2019.25

Multi-core systems using ScratchPad Memories (SPMs) are attractive architectures for executing time-critical embedded applications, because they provide both predictability and performance. In this paper, we propose a scheduling technique that jointly selects SPM contents off-line, in such a way that the cost of SPM loading/unloading is hidden. Communications are fragmented to augment hiding possibilities. Experimental results show the effectiveness of the proposed technique on streaming applications and synthetic task-graphs. The overlapping of communications with computations allows the length of generated schedules to be reduced by 4% on average on streaming applications, with a maximum of 16%, and by 8% on average for synthetic task graphs. We further show on a case study that generated schedules can be implemented with low overhead on a predictable multi-core architecture (Kalray MPPA).

Introduction

The race for computer performance has always been limited by the memory bottleneck.

To overcome this issue, hardware [START_REF] Michaud | Best-Offset Hardware Prefetching[END_REF], software [START_REF] Alexander | An architecture for software-controlled data prefetching[END_REF] and hybrid [START_REF] Kamruzzaman | Tullsen. Inter-core Prefetching for Multicore Processors Using Migrating Helper Threads[END_REF] prefetching methods have been proposed in the past to bring data closer to the processor before it is needed. However, most prefetchers are not designed for time-critical applications, where predictability is essential. Compared to cache-based architectures, multi-cores with a private ScratchPad Memory (SPM) per core are a very attractive alternative for time-critical embedded applications. Via software-managed SPMs, they offer sufficient computational power and the necessary predictability. Software-managed SPMs enable data-movement decisions, from/to main memory, to be scheduled at design time (off-line), thus restricting or avoiding contention on shared resources. Examples of such architectures are the Cell multi-core architecture [START_REF] James A Kahle | Introduction to the cell multiprocessor[END_REF], the academic core Patmos [START_REF] Schoeberl | Patmos reference handbook[END_REF] or the Kalray MPPA [START_REF] Dupont De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF].

Efficient and predictable management of SPMs are facilitated by application models that offer a high-level view of parallel programs. We focus on applications modelled as directed acyclic task-graphs (DAGs), consisting of dependent tasks that exchange data through shared FIFO channels. In such application models, tasks are executed in three phases: 1) they read data from their input FIFOs, 2) execute their computation, and 3) write the results to their output FIFOs. This order of execution is in accordance with the PRedictable Execution Model (PREM) [START_REF] Pellizzoni | A predictable execution model for COTS-based embedded systems[END_REF][START_REF] Alhammad | Memory efficient global scheduling of real-time tasks[END_REF] and the Acquisition Execution Restitution (AER) execution model [START_REF] Cl | A closer look into the aer model[END_REF]. Such execution models are well-suited for SPM-based architectures, as tasks can prefetch their input FIFOs from the shared memory into the private SPM and, after the task's execution, write-back the produced data to their output FIFOs. Using proper scheduling techniques, this can result in contention-free execution. These DAGs do not necessarily need to be built from scratch, which would require an important engineering effort. Automatic extraction of parallelism, for instance from a high level description of applications in model based design workflows [START_REF] Derrien | WCET-Aware Parallelization of Model-Based Applications for Multi-Cores: the ARGO Approach[END_REF], seems a much more promizing direction.

We believe that this combination of software (DAG with PREM) and hardware (SPMbased multi-cores) is essential to build efficient and predictable systems. In this paper, we propose a scheduling strategy that hides such delays by executing communications in parallel with computation. Our scheduling strategy relies in advancing (resp. postponing) the execution of read (resp. write) phase of a task such that it overlaps with the execution phase of another task, thus hiding the communication delay. The proposed scheduling strategy aims at minimizing the makespan of the total execution and includes an SPM allocation strategy ensuring that there is enough space in SPM at all times. The resulting schedules are contention-free to the shared bus, similarly to [START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF]. Additionally, and in comparison with most related works (such as [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architecture[END_REF][START_REF] Choi | Executing synchronous dataflow graphs on a spm-based multicore architecture[END_REF][START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF][START_REF] Tendulkar | Many-core scheduling of data parallel applications using SMT solvers[END_REF]), we fragment communication phases to augment communication hiding possibilities. In contrast with most other works dealing with SPM, e.g. [START_REF] Deverge | WCET-directed dynamic scratchpad memory allocation of data[END_REF][START_REF] Becker | Scheduling multi-rate real-time applications on clustered many-core architectures with memory constraints[END_REF], that allow some information to stay in global main memory, our SPM allocation scheme imposes that all information accessed by a task is prefetched into SPM beforehand. In summary, the contributions of this work are the following: 1. We propose a strategy to map and schedule a task graph onto cores coupled with an SPM allocation scheme. The generated static contention-free non-preemptive schedules allow, when possible, to overlap communications and computations, through non-blocking loading/unloading of information into/from SPM. Communication phases are fragmented to maximize the duration of overlapping between communications and computations. The proposed strategy is formulated as a heuristic based on list-scheduling to produce schedules very fast. 2. We provide an experimental evaluation showing our method improves the overall makespan, up to 16%, compared to equivalent schedules generated with blocking communications. 3. We evaluate the impact of different granularities for communication fragments on the schedule makespan. 4. We experimentally show on a use case that generated schedules can be implemented with a low overhead on a predictable multi-core architecture (Kalray MPPA [START_REF] Dupont De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]).

The rest of this paper details the proposed strategy and is organized as follows. A motivating example is presented in Section 2, as well as the assumptions made on the hardware and software. Then, Section 3 presents the basic principles of the SPM allocation scheme. The scheduling/mapping/allocation heuristic technique is then detailed in Section 4. Section 5 presents experimental results, including an implementation on the Kalray MPPA platform. Finally, Section 6 presents related works, before concluding in Section 7.

2

Motivating Example and assumptions

Architecture Model

We consider multi-core architectures, where every core has access to a private dual-ported ScratchPad memory (SPM). Cores are connected through an arbitrated bus to a global external shared memory. Access requests are enqueued (one queue per core) and served according to the bus arbitration policy. While in the rest of the paper, we will assume a FAIRround-robin arbitration [START_REF] Kelter | Evaluation of resource arbitration methods for multi-core real-time systems[END_REF], the proposed method is directly applicable for other policies with arbitration based on requests (e.g. first-come-first-served, fixed priority, etc.) and not on time (e.g. time division multiple accesses). All communications are non-preemptable and go through the shared global memory (no SPM to SPM communication). We further assume that the architecture supports loading of information in the dual-ported SPM, in parallel with computations. Provided support may be a hardware Direct Memory Access (DMA) engine or a specific core acting as a DMA software engine as in [START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF]. These assumptions are met in both academic and commercial processors (e.g. Patmos [START_REF] Schoeberl | Patmos reference handbook[END_REF], Kalray MPPA [START_REF] Dupont De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]).

Communications can be implemented in blocking mode or non-blocking mode. In blocking mode, the CPU is in charge of transfers between SPM and the shared memory, and is then stalled during every transfer. In non-blocking mode, transfers are managed asynchronously, allowing the CPU to execute other jobs during memory transfers.

Application Model

We consider applications modeled as directed acyclic graphs (DAGs). A graph G is a pair (V, E) where the vertices in V represent the application's tasks and the edges in E represents the data dependencies between the tasks. This work supports multiple DAGs with same period as is, which is omitted due to space limitations. Extending our work to applications with different periods is deemed as a rather direct transposition, by making schedule generation operate on the hyperperiod. This extension is however left for future work. According to the semantics defined in PREM [START_REF] Pellizzoni | A predictable execution model for COTS-based embedded systems[END_REF][START_REF] Alhammad | Time-predictable execution of multithreaded applications on multicore systems[END_REF] or AER [START_REF] Cl | A closer look into the aer model[END_REF], each task is divided in three phases, namely read, exec and write. The read phase reads/receives the mandatory code and/or data from the main memory to the SPM, such that the exec phase can proceed without access to the shared bus. Finally, the write phase writes the resulting data back from the SPM to the main memory. Using such an application and execution model is central in our method, as it allows to perform offline scheduling which precisely controls resource contention. The exec phase of tasks does not access the shared bus, and thus contentions when accessing the shared bus do not exist between exec phases and read/write phases; the off-line scheduler is in charge of scheduling communication phases in such a way that they E C R T S 2 0 1 9

25:4 Hiding Communication Delays in SPM-Based Multi-Cores

do not conflict with one another; finally, the presence of a dual-ported SPM per core allows calculations and communications to proceed in parallel, provided that they access different address ranges.

Note that considered DAGs with read-exec-write semantics need not be built from scratch. They can be extracted automatically either from a high-level description of applications in model based design workflows [START_REF] Derrien | WCET-Aware Parallelization of Model-Based Applications for Multi-Cores: the ARGO Approach[END_REF], or from legacy code with [START_REF] Mancuso | Light-PREM: Automated software refactoring for predictable execution on COTS embedded systems[END_REF].

As an extension to the original PREM/AER model, we split each communication into fragments. A fragment is some division of the total amount of data that a task produces or consumes. How the data are divided into fragments is determined by the fragmentation scheme. The default fragmentation scheme assumed throughout this paper is to have one fragment for each task communication (edges in the graph). Thus, instead of a task reading/writing all of its inputs/outputs at once, it is done on a per-task basis with the size of the fragment being as the size of the communication. Other fragmentation strategies will be detailed in Section 5.4. A task τ i is a tuple

τ i =< F r i , τ e i , F w i >,
where τ e i is the exec phase, and F r i (resp. F w i ) is the set of fragments read (resp. written) by the task. The f -th fragment of τ i that is read (resp. written) is denoted as

τ r (i,f ) ∈ F r i (resp. τ w (i,f ) ∈ F w i
). An example of a task-graph is illustrated in Figure 1. The figure gives for each task its name, the Worst Case Execution Time (WCET) of its exec phase, and for each edge the amount of data exchanged, among the tasks, in bytes. The WCET of the exec phase, denoted C i , can be estimated in isolation from the other tasks considering a single-core architecture, as there is no access to the main memory (all the required data and code have been loaded into the SPM before the task's execution). In general, read and write fragments could suffer from contentions caused by concurrent accesses to the shared bus, however in this paper the proposed technique produces contention-free schedules.

Since the code in our experimental evaluation, is generally small and likely to be reused along the execution of the application, for simplicity reasons we assume that the code is preloaded in the SPM at startup.

For simplicity when presenting the motivational example, we will assume the SPM to be large enough to store all information (code, data, communication buffers), this assumption will be relaxed in Section 3.

Motivating Example

Figure 2 motivates the use of non-blocking, fragmented communications for the application from Figure 1 assuming a dual-core architecture. Sub-figure 2b depicts the schedule obtained using non-blocking fragmented communications, with one fragment per outgoing edge in the graph, whereas sub-figure 2a depicts the schedule obtained using blocking communications. For each core, the top time-line depicts the scheduling of exec phases (grey boxes) and the bottom one depicts the scheduling of communications (read: white boxes, black font, write: dark boxes, white font). The communication cost is indicated below each communication phase.

In Figure 2a (blocking mode), all parts of the same task are scheduled contiguously on the same core, and the CPU is stalled when accessing the bus. The read and write phases are not fragmented as it would not bring any benefit in blocking mode. Precedence constraints are respected by ordering read phases after their preceding write phases, e.g. τ r C is scheduled after the completion of τ w A . There is no read phase for tasks A and B as they do not have predecessors, hence no data to fetch. The resulting schedule makespan (time at which the last task ends) is 76 time units. In Figure 2b (non-blocking mode), fragmented communication and exec phases overlap, e.g. τ r (H,2) and τ r (H,3) overlap with τ e F , thus hiding the communication delay. Having prefetched all required data into SPM, the exec phase of τ H can start right after τ F . The gain in schedule length from Figure 2b is obtained by introducing the following flexibilities in the scheduling of communication fragments, while respecting read-exec-write phase's order: 1) communication phases of different tasks can have a different order than their respective exec phases, as long as there is no data dependencies between them, e.g. τ r (D,1) is scheduled before τ w (E,1) , in reverse order compared to τ e D and τ e E . 2) communication phases and exec phase of the same task, do not need to be contiguous in time, e.g. τ r (D,1)

and τ e D are not. 3) communications are fragmented, a task with multiple successors does not write all its data at once, e.g. τ B has two successors, thus writing two fragments.

The last point (fragmented communications) is new compared to related work. Considering each fragment individually allows additional overlaps between communications and task execution that were impossible without fragmentation. In the example, it allows to hide part of the write phase of τ A , and part of the read phase of τ J , which was not possible without fragmentation. Thus, splitting communications allows each source/sink of the task graph to hide part of its communications. However, in the example from Figure 2b, the remaining first part A w (τ w (A,1) ) can still not be hidden, but is however smaller than in Figure 2a. The overall makespan of the resulting schedule in non-blocking mode (Figure 2b) is 61 time units, resulting in a gain of 20%.

Principle of SPM allocation scheme

In our motivational example, we assumed the SPM large enough to store all information required to execute the entire application (code, data, communication buffers). To account for limited SPM capacity, our scheduling strategy comes with a SPM allocation strategy that allocates an SPM area (called hereafter region) to each communication fragment and execution phase. Fragment-to-region mapping is performed by the scheduler off-line. However, the same region can be used successively by different fragments, and the scheduler guarantees that the live ranges of the concerned fragments do not overlap. Region sizes vary according to the data stored by fragments/exec phases.

E C R T S 2 0 1 9

25:6 Hiding Communication Delays in SPM-Based Multi-Cores

To isolate bus accesses from computation, we impose that all information accessed by a task is loaded into SPM beforehand. This comes in opposition to most SPM allocation policies that decide which information should be stored in the SPM and which information should remain in the global main memory (e.g. [START_REF] Deverge | WCET-directed dynamic scratchpad memory allocation of data[END_REF]). Our fragment-to-region mapping is inspired by the method proposed in [START_REF] Kim | WCET-aware dynamic code management on scratchpads for software-managed multicores[END_REF].

The regions assigned to fragments F r i contain the input data, fetched from the main memory, which are required by the task's exec phase. These regions contain the data produced by all predecessor tasks. The unique region assigned to τ e i contains any kind of information used locally by the task (code, constants, local data, usually stack-allocated). The regions assigned to F w i contain the data produced by the task. The size of a region obviously depends on the amount of data required by the associated fragment (i.e. amount of data produced by a predecessor in case of a read fragment). Considering a mapping of tasks to cores and a mapping of fragments to SPM regions, the sum of the sizes of regions on a core must not exceed the SPM size. Let us consider the example of Figure 2b, in which for simplicity we concentrate on the communication fragments and ignore the execution phases. If the size of the SPM is 1 Kbytes then on processor P 2 the SPM can be partitioned in seven regions

SP M = {τ w (B,1) , τ w (B,2) , τ r (E,1) , τ w (E,1) , τ r (D,1) , τ r (G,1) , τ w (G,1)
} with respective sizes in bytes {1, 2, 1, 1, 1, 2, 5} (according to the amount of data exchanged between tasks, taken from Figure 1). The sum of the regions' sizes is 13 bytes, which is less than the SPM size. If we now restrict the SPM size to 10 bytes, the previous partitioning of SPM in regions is not valid anymore. However, once τ w (B,1) is completed, the data produced by τ B has been committed to the global shared memory, therefore its assigned region can be reused. In this example, τ r (G,1) starts after the completion of τ w (B,1) , as it is the case for τ w (B,2) and τ w (G,1) . Thus, the fragments τ w (B,1) ,τ r (G,1) and τ w (B,2) ,τ w (G,1) can be assigned to the same SPM region, leaving a partitioning of five regions: SP M = {{τ w (B,1) , τ r (G,1) }, {τ w (B,2) , τ w (G,1) }, τ r (E,1) , τ w (E,1) , τ r (D,1) } with respective sizes (in bytes) {max(1, 2), max(2, 5), 1, 1, 1}. The sum of all regions sizes is 10 bytes, which can fit in the SPM.

In the example, both pairs (τ w (B,1) , τ r (G,1) ) and (τ w (B,2) , τ w (G,1) ) could share the same region, because their lifespan does not overlap. On the other hand, in Figure 2b,τ r (D,1) can not share the same region as τ r (E,1) , because the data consumed by τ E are in use from the start of the read phase F r E up to the end of the execution of τ e E . This leads to define the live range of regions for each type of fragment. Definition 1 defines the live range for a region assigned to a read fragment, while Definitions 2 and 3 give live ranges for regions assigned respectively to an exec and a write fragment.

Definition 1. Data fetched from the main memory by a read fragment are alive from its start time to the end of the corresponding exec phase.

Definition 2. Local information used by an exec phase (code, stack data area) are alive for the whole execution time of the application.

Definition 3. Data written back to main memory by a write fragment are alive from the start time of the corresponding exec phase to its transmission end time.

We assume read/written data can be consumed/produced at any time in the exec phase of the task. Therefore, the live range in Definitions 1 and 3 include the duration of the exec phase.

The scheduler maps fragments to regions, but does not decide the addresses of the regions in the SPM, which is left to the compiler/code generator. Since the number and size of regions is decided off-line, address assignment is straightforward, and does cause external fragmentation. Fragmentation of the SPM can only arise inside regions (internal fragmentation) when two (or more) phases are assigned to the same region but store different amounts of data.

4

Joint-mapping/scheduling and SPM allocation

This section presents a heuristic algorithm based on forward list scheduling that integrates fragmented non-blocking communication and SPM allocation. The main outcome of the proposed algorithm is a static mapping, scheduling and SPM fragment-to-region allocation, for a single application represented as a DAG. The objective is minimizing the overall schedule's makespan. The generated schedule is free from contention. According to the terminology given in [START_REF] Davis | A survey of hard real-time scheduling algorithms for multiprocessor systems[END_REF], the proposed scheduling techniques are partitioned, time-triggered and non-preemptive. Schedule generation operates at task-level (as opposed to job-level as defined in [START_REF] Davis | A survey of hard real-time scheduling algorithms for multiprocessor systems[END_REF]). Heuristics based on forward list scheduling first order input elements (in our specific case exec and communication phases), then add them one by one in the schedule without backtracking. We experimented with three topological sorting algorithms. The first algorithm is a vanilla Depth First Search (DFS) algorithm to walk-through the task graph. Second, we use the same DFS algorithm but we postpone read fragments to avoid too early reading that might delay other fragments in the schedule (further details will be given when describing Algorithm 4.1). The last algorithm is a vanilla Breath First Search (BFS) algorithm. For all three sortings, we used the element memory footprint as tie breaking rule (larger footprint to be scheduled first). Since no sorting algorithm consistently outperforms the others, we generate three schedules, each resulting from one sorting algorithm, and selected the one resulting in the shortest schedule makespan as the heuristic's solution.

Notations and assumptions

Table 1 summarizes the notations that will be used to describe the scheduling algorithm (sets, utility functions and constants).

Calculation of constants DELAY r (i,f ) and DELAY w (i,f ) requires knowledge of the bus arbitration strategy and of concurrent accesses to the bus. The considered bus is characterized by a maximum duration of T slot allocated to each core in a round-robin fashion, with a writing rate of D slot data word per time unit. T slot defines the duration a core is granted the bus, and D slot defines the amount of data transmittable in a T slot duration. For the scope of this paper, we generate contention-free schedules, thus no contention delay is paid, and the duration of a data transfer of d bytes is trivially calculated by equation ( 1). This equation could be refined to account for DRAM access cost, as done in [START_REF] Kim | WCET-aware dynamic code management on scratchpads for software-managed multicores[END_REF].

delay = d/D slot • T slot (1)
In the description of the scheduling algorithm, the cost for setting up non-blocking memory transfers (DMA initialization in case of a hardware DMA engine) will not appear explicitly and is considered included in the WCET of the exec phase. Determination of this cost will be described in Section 5.5.

Scheduling algorithm

The scheduling algorithm is sketched in Algorithm 4.1. It uses the task graph as input, sorts the elements to schedule (exec phases and communication fragments) to create the list (line 2). Then a loop iterates on each element while there exists elements to schedule

F = F r i ∪ F w i , ∀i ∈ T
sets of all fragments from all tasks in T Funcs i = task(f ) utility to retrieve the task of a fragment, fragment f belongs to τi

(j, q) ∈ pred((i, f )) (j, q) means τ X (j,q) is a direct predecessor of τ X (i,f ) Constants SSi local (stack) data size of τ e i CSi code size of τ e i Ci τi execute phase WCET computed in isolation as stated in Section 2 D r (i,f ) , D w (i,f ) size in bytes of τ r (i,f ) DELAY r (i,f ) fragment f of τi, read/write DELAY w (i,f ) latency from Equation (1) SP M SIZEc SPM size of core c Variables ρ r (i,p) , ρ e i , ρ w (i,q)
start times of τ r (i,p) , τ e i and τ w (i,q)

(lines [START_REF] Gerald | Formulating integer linear programs: A rogues' gallery[END_REF][START_REF] Casini | Memory Feasibility Analysis of Parallel Tasks Running on Scratchpad-Based Architectures[END_REF][START_REF] Cheng | Memory Bank Partitioning for Fixed-Priority Tasks in a Multi-core System[END_REF][START_REF] Choi | Executing synchronous dataflow graphs on a spm-based multicore architecture[END_REF][START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF][START_REF] Davis | A survey of hard real-time scheduling algorithms for multiprocessor systems[END_REF][START_REF] Dupont De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF][START_REF] Derrien | WCET-Aware Parallelization of Model-Based Applications for Multi-Cores: the ARGO Approach[END_REF][START_REF] Deverge | WCET-directed dynamic scratchpad memory allocation of data[END_REF][14][15][START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF][START_REF] Giorgi | Exploiting DMA to enable non-blocking execution in Decoupled Threaded Architecture[END_REF][START_REF] Griva | Linear and Nonlinear Optimization[END_REF][START_REF] James A Kahle | Introduction to the cell multiprocessor[END_REF][START_REF] Kamruzzaman | Tullsen. Inter-core Prefetching for Multicore Processors Using Migrating Helper Threads[END_REF]. This heuristic uses an As Soon As Possible (ASAP) strategy when mapping an element. If the element to schedule is a communication fragment (line 8), then there is no need to map it on a core, but it still must be scheduled to avoid interference. If it is an exec phase, then a core is selected and the mapping with the shorter the makespan is selected (line 15). SPM regions can be assigned to elements (exec phases and communication fragments) only when all of its phases are properly scheduled and mapped to a core (lines 18-20). When scheduling the read fragments, the core mapping information is not yet available. Additionally, when mapping the exec phase, we still do not have the information regarding the write fragments that have not been scheduled yet. While assigning the region (lines 18-20), the exec phase goes first then the communication phases. This order is motivated to better handle resident code in SPM and avoid SPM space to be stolen by communication fragments. For example, if there are 5 units of free space (not assigned yet) and the exec needs 5 units while a read/write need 2 units each. Then the task can still be mapped. The exec phase will take the remaining free space, while the communication fragments can share an already created, but available (in time), region (see Definitions 1 and 3).

Scheduling an element

Algorithm 4.2 sketches the method to determine the start time of the considered element (exec phase or communication fragment). First, each element must start after its causal predecessors (line 2) Then, lines 3-9 enforce that no exec phases overlap on the same core and no fragments overlap on the bus. Condition at line 4 enforces the type of cur_elt and e to be identical, and if both are exec phases then they must be mapped on the same core. Finally, line 9 postpones cur_elt start time if overlapping with e.

19 ∀f ∈ F r i , Assign_Region(schedule, Qdone, f, D r (i,f ) , ρ r (i,f ) , ρ e i + Ci) 20 ∀f ∈ F w i , Assign_Region(schedule, Qdone, f, ρ e i , ρ w (i,f ) + DELAY w (i,f ) ) 21 return schedule

Allocation of SPM regions

Algorithm 4.3 associates a SPM region to an element (exec phase, fragment). If there is data to store in the SPM (line 2), then it first tries to reuse an existing region (lines 4-6), thus minimizing the required memory size. If no existing region can be shared, then a new one is created (lines 7-8). Sharing a region imposes that the selected region is big enough to handle the current amount of data and free for use at the required time interval (line 4).

Experimental evaluation

The first presented experiments (Section 5.2) aim at validating the quality of the proposed scheduling technique as compared to a scheduling strategy based on Integer Linear Programming (ILP, see Section 5.1) that provides the optimal solution (shortest schedule makespan). Then, we validate the benefits of hiding communications using the heuristic technique (Section 5.3). In the above-mentioned experiments, the default fragmentation strategy (one fragment per edge in the task graph) is used. We subsequently compare different ways to fragment communications (Section 5.4). Finally, we show in Section 5.5 on a case study that generated schedules can be implemented with low overhead on a Kalray MPPA platform [START_REF] Dupont De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]. In Sections 5.2 to 5.4, scheduler and communication implementation overheads are neglected, but they are considered in Section 5.5.

Experiments have been conducted both on real code, in the form of the open-source Refactored StreamIT benchmark suite STR2RTS [START_REF] Rouxel | STR2RTS: Refactored StreamIT Benchmarks into Statically Analyzable Parallel Benchmarks for WCET Estimation & Real-Time Scheduling[END_REF] and on synthetic task graphs, generated using Task-Graph For Free (TGFF) [14]. Input : the list of scheduled element, the current element to schedule, the current core or null if the element is a fragment Output : The STR2RTS applications1 are modeled using fork-join graphs and come with timing estimates for each task and amount of data exchanged between them. We did not use all the benchmarks and applications provided in the suite as some are not parallel, they are made of a linear chain of tasks (i.e. CFAR, FIR, ComplexFIR, FTT6), making them uninteresting for multi-core platforms. This leaves us 18 benchmarks with 73 tasks in average and average memory footprint of 4 KB.

E C R T S

The synthetic task-graphs were generated with the latest version of the TGFF generation software. Generated task-graphs include chains of tasks with different lengths and widths, fork-join graphs and more evolved structures (e.g. multi-DAGs). The resulting task graph characteristics are presented in Table 2. The table includes the number of task-graphs, their number of tasks, the maximum width of the task-graph, the range of WCET values for each task and the range of amount of exchanged data in bytes between pairs of tasks, the range of code size and stack size for each task, and the global ratio of WCET per amount of exchanged data. The TGFF parameters (average and indicator of variability) are set in such a way that the average values for task WCETs and volume of data exchanged between pairs of tasks correspond to the analogous average values for the STR2RTS benchmarks. All reported experiments have been conducted on several nodes from an heterogeneous computing grid with 138 computing nodes (1700 cores). In all experiments, the duration a core is granted the bus (T slot ) is set to 3 as in [START_REF] Kelter | Evaluation of resource arbitration methods for multi-core real-time systems[END_REF] and shown in [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architecture[END_REF] to have little impact on the schedule length. The transfer rate is one word (4 bytes) per time unit.

Baseline: Integer Linear Programming scheduling

An Integer Linear Programming (ILP) formulation consists of a set of integer variables, a set of constraints and an objective function. Constraints describe the problem to solve in the form of linear inequalities. Solving a problem consists in finding a valuation for each variable satisfying all constraints with the goal of minimizing/maximizing the objective function. Table 3 summarizes the variables used in the ILP formulation. For a concise presentation of constraints, the two logical operators ∨, ∧ are directly used in the text of constraints. These operators can be transformed into linear constraints in order to properly use ILP solvers using simple transformation rules from [START_REF] Gerald | Formulating integer linear programs: A rogues' gallery[END_REF].

Objective function

The objective is to obtain the shortest schedule, and so to minimize the makespan Θ, Equation (2a). Equation (2b) constrains the completion time of all tasks (starting of all write fragment ρ w (i,f ) , plus its latency DELAY w (i,f ) ) to be inferior or equal to the schedule makespan.

minimize Θ (2a) ∀i ∈ T ; ∀f ∈ F w i ; ρ w (i,f ) + DELAY w (i,f ) ≤ Θ (2b)

Problem constraints

Some basic rules of a valid schedule are expressed in the following equations. Equation (3a) ensures the unicity of a task mapping (p i,c = 1 τ i is mapped on core c). Equation (3b) defines if two tasks are mapped on the same core (m i,j = 1). When a ee i,j = 1 then τ e i is scheduled before τ e j , thus Equation (3d) forbids an order of phases (resp. fragments) and its reversed order to be both active but imposes to choose one; one of the a ee i,j , a ee j,i must be equal to 1, but both can not be equal to 1. Equations (3e) unifies Equations (3b) and (3d) to order exec phases only on the same core. In Equation (3d), no equation enforces E C R T S 2 0 1 9 start times of τ r (i,p) , τ e i and τ w (i,q) spmsr c z computed size of SPM region z on core c σ (i,f ) , σi spm reservation start times of τ X (i,f ) , τ e i ω (i,f ) , ωi spm reservation end times of τ X (i,f ) , τ e i Binary variables pi,c = 1 τ e i is mapped on core c mi,j = 1 τ e i & τ e j are mapped on the same core a ee i,j = 1 τ e i is scheduled before τ e j (ρ e i ≤ ρ e j )

25:12 Hiding Communication Delays in SPM-Based Multi-Cores

a XY (i,f ),(j,g) = 1

τ X (i,f ) is scheduled before τ Y (j,g) , in the sense ρ X (i,f ) ≤ ρ Y (j,g)
XY ∈ {rr, ww, rw, wr} am ee i,j = 1 same as a ee i,j but on the same core am XY i,j = 1 same as a XY i,j but on the same core XY ∈ {rr, ww, rw, wr} spmpz,i = 1

τ e i is allocated to SPM region z spmp z,(i,f ) = 1 τ X (i,f ) is allocated to SPM region z spmm (i,f ),(j,g) = 1
τ X (i,f ) and τ X (j,g) are assigned to the same region (similar to mi,j)

spma (i,f ),(j,g) = 1 τ X (i,f ) is causally before τ X (j,g) (similar to ai,j) spmam (i,f ),(j,g) = 1 τ X (i,f
) is causally before τ X (j,g) , and both are assigned to the same region (similar to ami,j)

to have the same ordering for exec phases as for with read phases, because the solver does not have to chose an order between them (see Section 2). The same remark applies to exec phases and write phases.

∀(i, j) ∈ T × T ; XY ∈ {rr, ww, rw, wr}; ∀f ∈

F X i ; ∀g ∈ F Y j ; i = j c∈P p i,c = 1 (3a) m i,j = c∈P (p i,c ∧ p j,c
) and m i,j = m j,i (3b)

a ee i,j + a ee j,i = 1 (3c) a XY (i,f ),(j,g) + a XY (j,g),(i,f ) = 1 (3d) am ee i,j = a ee i,j ∧ m i,j (3e
)

ρ e i + C i ≤ ρ e j + M × (1 -am ee i,j ) (3f) ρ X (i,f ) + DELAY X (i,f ) ≤ ρ Y (j,g) + M × (1 -a XY (i,f ),(j,g) ) (3g)
Equation (3f) forbids the overlapping of two exec phases when mapped on the same core by forcing one to execute after the other. Equation (3g) forbids to have more than one active memory transfer at a time to produce contention-free schedules. Equations (3f) and (3g) must be activated only if the two elements are scheduled in a specific order. Thus, a nullification method is applied by using the classical big-M notation (the big-M notation allows to force a constraint to hold depending on a condition as further explained in [START_REF] Griva | Linear and Nonlinear Optimization[END_REF]). The selected value for the big-M constant is the makespan of a sequential schedule on 1 core, the sum of tasks' WCETs and communication delays, which is the worst scenario that can arise.

Read-exec-write semantics constraints

Equations (4a) and (4b) constrain the order of all phases of a task to be read phase, then exec phase, then write phase. But, these phases will not necessarily be scheduled contiguously. The start date of τ e i (ρ e i ) must be some time after the completion of all read fragments (start of read fragment ρ r (i,f ) + latency DELAY r (i,f ) ). Similarly, each write fragment starts (ρ w (i,f ) ) some time after the end of the exec phase (start of exec phase

ρ e i + WCET C i ). ∀i ∈ T, ∀f ∈ F r i , ρ e i ≥ ρ r (i,f ) + DELAY r (i,f ) (4a) ∀f ∈ F w i , ρ w (i,f ) ≥ ρ e i + C i (4b)

Data dependencies in the task-graph

Equation ( 5) enforces data dependencies by constraining all read fragments to start after the completion of all their respective predecessors. For a read fragment its predecessor is the write fragment of the task that produced the corresponding data.

∀i ∈ T, ∀f ∈ F r i , ∀(j, g) ∈ pred(i, f ) ρ w (j,g) + DELAY w (j,g) ≤ ρ r (i,f ) (5)

Assigning SPM regions

Equations ( 6a) & (6b) force every element (exec and fragments) from τ i to be mapped on one and only one region z. Identically to [START_REF] Kim | WCET-aware dynamic code management on scratchpads for software-managed multicores[END_REF], we initially consider the number of regions to be equal to the number of elements (number of exec phase + number of fragments). With the limited capacity of the SPM, the solver will then be able to minimize the number of effectively used regions.

∀i ∈ T ;

z∈R

spmp z,i = 1 (6a) f ∈ F, i = task(f ); z∈R spmp z,(i,f ) = 1 (6b)
Equations ( 7a) and (7b) set the size (spmsr c z ) of region z on core c to be the largest amount of data that will be stored in it. The data stored by an exec phase includes the code size (CS t ) and local data (SS t , stack data). The data stored by a read or write fragment (D X (i,f ) ) includes all data consumed (or produced) by a task from one predecessor (or one successor). To store data into a given region of a core, both mapping variables for the region spmp z,(i,f ) and the core p i,c must be set to 1.

∀c ∈ P, ∀z ∈ R, ∀i ∈ T, spmsr c z ≥ (SS i + CS i ) (spmp z,i ∧ p i,c ) (7a) ∀χ ∈ {r, w}, ∀f ∈ F χ i ; spmsr c z ≥ D χ (i,f ) (spmp z,(i,f ) ∧ p i,c ) (7b)
Equation ( 8) limits the sum of size for each region for a core to the available SPM size.

∀c ∈ P, z∈R spmsr c z ≤ SP M SIZE c ( 8
)
E C R T S 2 0 1 9

25:14 Hiding Communication Delays in SPM-Based Multi-Cores

Delimiting the usage time of a region by an element relies on Definitions 1, 2 and 3. Equation (9a) sets the allocation start time σ (i,f ) of τ r (i,f ) to be equal to its schedule start time and the allocation end time ω (i,f ) to be the end of the corresponding exec phase. Equation (9b) forces the lifetime of the region used by the exec phase to be the whole duration of the schedule (recall that Θ represents the overall makespan). Equation (9c) sets the allocation start time σ (i,f ) of τ w (i,f ) equal to the beginning of the exec phase and the allocation end time

ω (i,f ) equal to its start time. ∀i ∈ T ∀f ∈ F r i ; σ (i,f ) = ρ r (i,f )
and ω i = ρ e i + C i (9a)

σ i = 0 and ω i = Θ (9b) ∀f ∈ F w i ; σ (i,f ) = ρ e i and ω (i,f ) = ρ w (i,f ) + DELAY w (i,f ) (9c)
Mapping elements (exec phases and communication fragments) to SPM regions is very similar to mapping tasks on cores. Therefore, following equations (10a), (10b), (10c) and (10d) mimic the behaviour of respectively (3b), (3d), (3e) and (3f) by replacing variables m i,j , a i,j and am i,j with spmm i,j , spma i,j and spmam i,j . As a reminder, (10a) detects if two fragments are assigned to the same region from the same core, (10b) represents the causality of a fragment compare to another, and (10c) represents this causality on the same region. Finally, (10d) imposes the mutual exclusion of the reservation time.

∀(f, g) ∈ F × F, f = g, i = task(f ), j = task(g) spmm (i,f ),(j,g) = z∈R (m i,j ∧ spmp z,(i,f ) ∧ spmp z,(j,g) ) (10a) spma (i,f ) + spma (j,g) = 1 (10b) spmam (i,f ),(j,g) = spma (i,f ) ∧ spmm (i,j),(j,g) (10c
)

ω (i,f ) ≤ σ (j,g) + M × (1 -spmam (i,f ),(j,g) ) (10d)

Quality of the heuristic compared to the ILP

The following experiments aim at estimating the gap between makespans of schedules generated by the heuristic opposed to the optimal solutions provided by the ILP solver. We expect this gap to be small. Due to the intrinsic complexity of solving our scheduling problem using ILP, we need for these experiments a large number of small task-graphs, such that the ILP is solved in reasonable time. We thus used synthetic task graphs generated using TGFF (see Table 2). For each graph, we varied the number of cores in {2, 4, 8, 12} and the sizes of the SPM vary in {2KB, 4KB}. SPM sizes allow to cover three situations: 1) all test-cases fit in the SPM (4KB size), 2) some test-cases do not entirely fit in SPM (2KB size), 3) some test-cases are too large, hence unschedulable (2KB size, biggest benchmarks).

The ILP solver used is CPLEX v12.7.1 configured with a timeout of 24 hours. The heuristic is implemented in C++ with a 60 minutes timeout. 4 presents the combined results for all different configurations. First, it shows the number of optimal (including infeasible) results the ILP solver is able to find in the given timeout -68%. The remaining 32% includes all other cases where the solver reaches the timeout without neither an optimal solution nor an infeasibility verdict. Then Table 4 presents the minimum/maximum and the average degradation induced by the heuristic over the ILP. As displayed, the average degradation is low thus showing the quality of our heuristic. Figure 3 shows that solving an ILP problem does not scale with the growing number of tasks. In contrast, we believe that the proposed scheduling technique does, given its low running times: for the synthetic graphs the average schedule generation times are always less than one second, while for the SRT2RTS benchmarks (up to 340 tasks), the heuristic needs 4 minutes on average.

Blocking vs non-blocking communications

To compare the benefit of hiding communication latency, the proposed scheduling technique must be opposed to a scheduler that does not hide it. We preferred to modify our heuristic to implement both the blocking and non-blocking methods instead of reusing a state-of-the-art algorithm. The main reason, as detailed in Section 6, is that related work have characteristics that are hardly compatible with our proposal: different task model [START_REF] Tabish | A real-time scratchpad-centric os for multi-core embedded systems[END_REF], SPM big enough to store all code/data [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architecture[END_REF][START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF], lack of information on SPM management [START_REF] Becker | Scheduling multi-rate real-time applications on clustered many-core architectures with memory constraints[END_REF], different interconnect [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF]. Another reason for this choice is to guarantee that the deviation between the results from the two communication modes will not be affected by any other technical implementation decision (e.g.: sorting algorithm).

To summarize the modifications applied to the heuristic in order to get the blocking mode: 1) we forbid to have more than one phase active at a time (both communication and computation as in the example of Figure 2a) 2) we do not fragment communications. We varied the number of cores in {2, 4, 8, 12}, and the SPM sizes in {4KB, 2M B} (2M B is the SMEM (Shared MEMory) size in one cluster of the Kalray MPPA [START_REF] Dupont De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]). All aforementioned three situations regarding the SPM size are covered with these configurations. Note that STR2RTS benchmarks are larger in term of memory space than synthetic benchmarks. We then calculate the gain of the non-blocking mode versus the blocking mode that we expect to be positive. Figure 4 shows that some benchmarks are unschedulable for some configurations, e.g. FFT2 with 2c-4KB. This comes from a lack of SPM space to place all code and all data. This might be relaxed with code pre-fetching in read phase, which is left for future work. Lower gains are observed when the amount of parallelism is low due to the lack of opportunity to hide communications. For example, Serpent is a chain of fork-joins containing 2 concurrent tasks only, as opposed to FIRBank which includes only one fork-join construct with several long chains of tasks. In addition, higher gains are observed on hardware configurations with lower number of cores -i.e. 6% on average with 2-cores as opposed to 4% with 12-cores. To evaluate the impact of graph shapes on gains, we experimented our heuristic technique on synthetic task graphs, the ones used previously to validate the heuristic. In contrast to STR2RTS graphs, that are fork-join graphs, synthetic task graphs are arbitrary directed acyclic graphs. Results are depicted in Figure 5. We observe these graphs offer more opportunities to hide communication, with an average gain of 8% in total.

Impact of fragmentation strategy

Through the paper, we have split read/write phases according to tasks dependencies (one fragment per edge in the task). We experimented with two more fine-grain splitting strategies:

splitting by D slot : each fragment will fit in a T slot bus period, each transmitting D slot bytes -a task transmitting 5 floats (20 bytes) with a T slot * D slot of 3 * 4 bytes per request will result to 2 fragments, generating 2 communications. splitting by data-type unit (DTU): an application exchanging only floats will have a DTU of 1 float (4 bytes). If a task produces 5 floats, then there is 5 fragments. We conducted the experiments by applying our heuristic on the STR2RTS benchmarks, with the very same experimental setup as before. We include in the comparison scheduling in non-blocking mode without communication fragmentation (label no frag in Figure 6). We expect the gain to increase as the fragment granularity gets smaller. Fragmenting communications always result in shorter schedules than the no frag configuration. In addition, in most cases the smaller granularity results in higher gains. However the better the results are, the higher the schedule generation time is, as given in the legend of the figure. Schedules are generated in less than 1 second on average for no frag and edge, whereas several minutes are required on average for finegrain fragments.

Schedule implementation on a Kalray MPPA platform

We successfully implemented schedules generated with our heuristic targeting one cluster of a Kalray MPPA Bostan platform [START_REF] Dupont De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF]. The final code is largely auto-generated (only the code of the exec phase of each task has to be inserted manually in the generated code). At the time of writing, we managed to run benchmark BeamFormer_12ch_4b from the STR2RTS benchmark suite [START_REF] Rouxel | STR2RTS: Refactored StreamIT Benchmarks into Statically Analyzable Parallel Benchmarks for WCET Estimation & Real-Time Scheduling[END_REF]. Benchmark BeamFormer_12ch_4b is made of 56 tasks with a DAG width of 12. The Kalray MPPA platform includes 16 clusters, each containing 16 cores and a SMEM of 2MB. Four I/O clusters, containing 4 cores each, access either the off-chip global memory or the Ethernet. Clusters are connected through a Network On Chip (NoC).

Following is a summary of the implementation on the Kalray MPPA. Implementation was done at the bare metal level. The SMEM is configured in banked address mapping mode (consecutive addresses are mapped to the same memory bank), with memory banks are split between computing cores at compile time to have a single-bank considered as SPM per core, as assumed in Section 2.

Data exchanges between cores and the off-chip memory walk through the architecture's NoC, which in our experiments is free from interferences as we only use one cluster of the architecture2 . Communications are implemented using the Kalray channel connectors (one channel for reading, one channel for writing), kept open for the whole execution of the application.

Each core runs one thread, in charge of implementing the schedule of exec phases generated off-line, by interleaving a sched function between exec phases. The sched uses busy-waiting (reads the local clock of the core to wait for tasks' start time). The worst-case measured overhead of the sched function due to clock reading is 32 cycles. An ad hoc protocol using barriers is used to re-synchronize local clocks at application start. A specific core is reserved to act as a software DMA engine and is in charge of implementing the schedule of communications (read and write phases) determined off-line, in a contention-free manner. Implementation of communication phases schedule is identical to the one of computation phases. Moreover, the I/O receiving core follows the schedule to receive and store data to the main memory or to send it to the cluster.

We were able to generate the following versions of the benchmark: 1) blocking mode (S bl ), 2) non-blocking mode without communication fragmentation (S nbl ), 3) non-blocking mode with fragmentation by edges (S edge nbl ), 4) non-blocking mode with fragmentation by D slot (12 bytes) (S dslot nbl ), 5)non-blocking mode with fragmentation by DTU, fragment size is one 4-bytes word (1 float) (S dtu nbl ). In terms of implementation overheads, there is no overhead to set up the softwareimplemented DMA at run-time, since channel connectors are initialized only once at application start. The overhead of 32 cycles due to the scheduler implementation is taken into account.

For this experiments, WCETs of computations and communications were estimated using measurements, adding an arbitrarily chosen margin of 20% for safety. Taking into account implementation overheads, as expected, the overall schedule makespans are: S bl > S nbl > S edge nbl > S dslot nbl . The gain of S nbl schedule over the S bl schedule is 1%, the gain of S edge nbl schedule over the S nbl schedule is 36%, and the gain of S dslot nbl over S nbl is 22%.

However, the finer fragmentation policy suffers from an overhead on this platform. The degradation of S dtu nbl over S edge nbl is 24%. The source of this overhead mainly originates from read phases measured time where reading one float takes as much time as reading four floats. Nevertheless, we observe a small decrease in write phases measured time depending on the amount of data exchanged (approximately 1000 cycles on average).

Related work

Accessing the global shared memory has always been a performance bottleneck. To overcome this issue, prefetching mechanisms bring information closer to the processor before it is actually needed. Hardware prefetchers will speculatively request data or instructions based on memory access patterns [START_REF] Michaud | Best-Offset Hardware Prefetching[END_REF]. Software prefetchers give control to the developer or compiler to introspect the code and add prefetching instructions [START_REF] Alexander | An architecture for software-controlled data prefetching[END_REF]. In this paper we propose a software prefetcher that adds prefetching based on a schedule generated off-line. Most of other works considering SPM aim at deciding what should be stored into the SPM and when to evict data, and in cases some information cannot be stored in SPM it stays in main memory. Considered metrics for SPM allocation are average-case performance [15, 25], power consumption [START_REF] Takase | Partitioning and allocation of scratch-pad memory for priority-based preemptive multi-task systems[END_REF], WCET [START_REF] Deverge | WCET-directed dynamic scratchpad memory allocation of data[END_REF], or schedule makespan [START_REF] Becker | Scheduling multi-rate real-time applications on clustered many-core architectures with memory constraints[END_REF]. In contrast to these studies, our work, in order to control resource contention, requires all information to be stored in SPM.

Wasly and Pellizzoni [START_REF] Wasly | A dynamic scratchpad memory unit for predictable realtime embedded systems[END_REF] add a hardware component, named RSMU, to manage the SPM. This RSMU acts similarly as a Memory Management Unit (MMU), except it also uses a previously computed schedule for loads/unloads of code/data from mixed-critical tasks. To use our method, no specific hardware component needs to be added. Giorgi et al. [START_REF] Giorgi | Exploiting DMA to enable non-blocking execution in Decoupled Threaded Architecture[END_REF] introspect the code to add control of the RSMU, in order to prefetch global data from the global external memory into a local memory on a many-core architecture. They modified the compiler to isolate loads into specific basic blocks and added synchronization if the mandatory data are not yet ready for use. However, their study does not include any real-time guarantee on blocking times. We can guarantee the data will be ready for use without blocking time.

Kim et al. [START_REF] Kim | WCET-aware dynamic code management on scratchpads for software-managed multicores[END_REF] present an algorithm to map a function to a specific SPM region, that inspired our phase to region mapping step. They aim at storing the basic blocks into the SPM in order to improve the WCET of an application on a single-core. We improve their work to map multiple tasks on multi-cores.

Cheng et al. [START_REF] Cheng | Memory Bank Partitioning for Fixed-Priority Tasks in a Multi-core System[END_REF] derive a speed-up factor and a resource augmentation factor when partitioning memory banks with minimum interference. At the opposite we have a complete off-line schedule with phase to region allocation on single bank SPM memory.

The PRedictable Execution Model (PREM) from Pellizzoni et al. [START_REF] Pellizzoni | A predictable execution model for COTS-based embedded systems[END_REF][START_REF] Alhammad | Time-predictable execution of multithreaded applications on multicore systems[END_REF] exposes parallelism by splitting tasks in communication/computation phases. PREM has been widely used -e.g. [START_REF] Wasly | A dynamic scratchpad memory unit for predictable realtime embedded systems[END_REF][START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF][START_REF] Wasly | Hiding memory latency using fixed priority scheduling[END_REF][START_REF] Becker | Scheduling multi-rate real-time applications on clustered many-core architectures with memory constraints[END_REF] -because it increases the predictability of an application by isolating memory accesses. Coupling this principle with a software-managed memory (SPM) drastically improves the predictability of the application and so improves its estimated WCET. The authors of [START_REF] Mancuso | Light-PREM: Automated software refactoring for predictable execution on COTS embedded systems[END_REF] present a method to automatically adapt any application to the PREM model, which then allows the application of any SPM load/unload technique including ours. The studies we could find exploiting both the SPM and the PREM model usually fuse the write phase of a task with the next activated read phase on the same core [START_REF] Wasly | A dynamic scratchpad memory unit for predictable realtime embedded systems[END_REF][START_REF] Wasly | Hiding memory latency using fixed priority scheduling[END_REF][START_REF] Alhammad | Memory efficient global scheduling of real-time tasks[END_REF]. As opposed to them, we follow the Acquisition-Execution-Restitution principle from [START_REF] Cl | A closer look into the aer model[END_REF] which adds more freedom to schedule generation.

On a single-core, using PREM, Soliman et al. [START_REF] Refaat | WCET-Driven Dynamic Data Scratchpad Management With Compiler-Directed Prefetching[END_REF] hide the communication latency at the basic-block level thanks to a modification of the LLVM compiler toolchain. Wastly and Pellizzoni [START_REF] Wasly | Hiding memory latency using fixed priority scheduling[END_REF] proposed to dynamically co-schedule, without preemption, DMA accesses and sporadic tasks on a SPM-based single-core. The SPM is split in 2 parts: one assigned to the currently executing task, while the other load information for the next scheduled task. Our work makes a better use of the SPM by allowing more than two regions alive at the same time. This last work has been extended to multi-core in [START_REF] Alhammad | Memory efficient global scheduling of real-time tasks[END_REF].

E C R T S 2 0 1 9 25:20 Hiding Communication Delays in SPM-Based Multi-Cores

Rouxel et al. [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architecture[END_REF] presented a co-scheduling and mapping of computation and communication phases from task-graph for multi-cores. They limited their work to blocking communication whereas we use non-blocking ones and we fragment them to add flexibility in the schedule. They assume an infinite SPM size, which looks to us unrealistic, therefore we relaxed this assumption in our scheduling method. In addition, they showed that their scheduling method with an accurate contention model exhibits similar gain and a larger solving times than contention-free ones. Hence, we use a contention-free model in this paper.

The technique proposed in [START_REF] Becker | Scheduling multi-rate real-time applications on clustered many-core architectures with memory constraints[END_REF] generates contention-free off-line schedules with periodic dependant tasks. Dealing with the SPM, they aim at deciding if a task should be resident in SPM or be fetched before each execution from the global memory. Unfortunately they do not provide information on SPM allocation, raising questions about address allocation and SPM fragmentation. With our region allocation scheme, an SPM allocation scheme that manages fragmentation is proposed.

A technique to hide transfers behind calculations is presented in [START_REF] Tabish | A real-time scratchpad-centric os for multi-core embedded systems[END_REF]. Similarly to [START_REF] Wasly | Hiding memory latency using fixed priority scheduling[END_REF] and [START_REF] Alhammad | Memory efficient global scheduling of real-time tasks[END_REF], the SPM is split in two regions, one used by the application while the other is being loaded. Our work differs from the work in [START_REF] Tabish | A real-time scratchpad-centric os for multi-core embedded systems[END_REF] by the task model under use (dependant tasks in our work, sporadic independent tasks in their work). Moreover, our work make better use of SPM by allowing more than two SPM regions to be alive simultaneously.

The work presented in [START_REF] Durrieu | Predictable flight management system implementation on a multicore processor[END_REF] proposes an off-line scheduling scheme for flight management systems using a PREM-like task model. The proposed schedule avoid interferences to access the communication medium. However, in contrast to our work, there are still interferences in their schedule, due to communications between tasks assigned to different cores.

Other works very close to our research, such as [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF][START_REF] Choi | Stream compilation for real-time embedded multicore systems[END_REF][START_REF] Tendulkar | Many-core scheduling of data parallel applications using SMT solvers[END_REF][START_REF] Skalistis | Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees[END_REF], statically schedule applications represented by synchronous data flow graphs with some form of buffer checking. However, they do not use the PREM/AER model like us [START_REF] Tendulkar | Many-core scheduling of data parallel applications using SMT solvers[END_REF][START_REF] Skalistis | Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees[END_REF], and none of them fragment the communications, which allows us to drastically increase the hiding opportunities. The research presented in [START_REF] Casini | Memory Feasibility Analysis of Parallel Tasks Running on Scratchpad-Based Architectures[END_REF] proposes a feasibility test that verifies whether scratchpad memories are large enough to contain the maximum memory backlog that may be generated by an application modeled as a task graph. In contrast to [START_REF] Casini | Memory Feasibility Analysis of Parallel Tasks Running on Scratchpad-Based Architectures[END_REF], our work focuses not only on memory usage feasibility but also on timing feasibility.

Conclusion

In this work, we have shown how to minimize the impact of the communication latency when mapping/scheduling a task graph on a multi-core, by overlapping communications and computations. We also argued this kind of technique should always be coupled with a memory allocation scheme to guarantee the integrity of the accessed data. Thus we formulated such allocation scheme in our scheduler. Our experimental results show that, compared to a scenario not overlapping communications and computations, our approach improves the schedule makespan by 4% on average on streaming application (8% on synthetic task graphs).

As future work, we plan to improve the accesses of the global main memory such as the DRAM where the scheduler accounts for the locality in this memory. For example, the fragments could be designed to exploit DRAM row locality and read/write switching of the communications. In the near future, we intend to extend this work to applications integrating multiple DAGs. Finally, we plan to strengthen our implementation on the Kalray MPPA platform, especially on the SMEM management.

Figure 1

 1 Figure 1 An example of a task-graph.

( a )

 a Schedule in blocking mode (makespan of 76 time units). (b) Schedule in non-blocking mode (makespan of 61 time units).

Figure 2

 2 Figure 2 Schedules for the example task-graph on a dual-core. For each core, the top time-line depicts the schedule of exec phases (in grey), the bottom one depicts the schedule of read (in white) and write (in black) phases. The communication cost is indicated below each communication phase.

  in SPM-Based Multi-Cores

Algorithm 4 . 1 : 2 Qready 5 while elt ∈ Qready do 6 Qdone

 41256 Scheduling algorithm.Input : A task graph G and a set of processors Output : A schedule 1 Function ListSchedule(G = (T, E), P ) ← Qdone ∪ {elt}

2 0 1 9 25: 10 Algorithm 4 . 2 :

 91042 Hiding Communication Delays in SPM-Based Multi-Cores Scheduling of an element (exec, fragment).

Figure 3

 3 Figure 3 Average ILP solving time for all configurations per number of tasks.

Figure 4

 4 Figure 4 Gain of non-blocking communications over blocking on STR2RTS benchmarks per cores/SPM configuration -avg: 4%.

Figure 4

 4 Figure4presents the average gain per benchmark for all configurations, e.g. 2c-2MB stands for 2-cores and SPM size of 2MB. Unfeasible configurations are denoted by the symbol "x". The maximum gain is 16% (FIRBank on 2 cores with 2MB SPM), whereas the average is 4%.

Figure 5

 5 Figure 5 Gain of non-blocking communications over blocking on TGFF benchmarks.

Figure 6

 6 Figure 6 Average gain of non-blocking over blocking depending on fragmentation strategy.

Figure 6

 6 Figure6presents the results with four granularities: no frag, edge (default configuration), D slot (12 bytes) and DTU (4 bytes). Fragmenting communications always result in shorter schedules than the no frag configuration. In addition, in most cases the smaller granularity results in higher gains. However the better the results are, the higher the schedule generation time is, as given in the legend of the figure. Schedules are generated in less than 1 second on average for no frag and edge, whereas several minutes are required on average for finegrain fragments.

Table 1

 1 Notations.

		T	set of tasks
		P	set of processors/cores
	Sets	R F r i , F w i	set of regions sets of τi fragments

Table 2

 2 Task-graph characteristics for synthetic task-graphs.

	#Task-graphs	50	WCET	[5; 6000[
	#Tasks	5, 69, 22	Code size	[3; 3920[
	Max. width	3, 17,8	Local size	[1; 60]
	Exchanged data	[0; 192]	Ratio W CET data	10

Table 3

 3 ILP variables.

	Int. variables	Θ ρ r (i,p) , ρ e i , ρ w (i,q)	schedule makespan

Table 4

 4 Degradation of the heuristic compared to the ILP on the synthetic task-graphs.

	% of exact results	degradation
	(ILP only)	<min,max,avg> %
	68%	0%, 20%, 3%

Table

A table describing each used benchmark is available in the appendix.

Note that our abstract architecture model from Section 2 uses a bus. Using a NoC in the Kalray MPPA only changes the overall communication delay computed in Equation 1 since the NoC is free from contentions.

Robert P Dick, David L Rhodes, and Wayne Wolf. TGFF: task graphs for free. In Proceedings of the 6th international workshop on Hardware/software codesign, pages 97-101. IEEE Computer Society, 1998.

Boubacar Diouf, Can Hantacs, Albert Cohen, "Ozcan "Ozturk, and Jens Palsberg. A decoupled local memory allocator. ACM Transactions on Architecture and Code Optimization (TACO), 9(4):34, 2013.

Funding This work was partially supported by ARGO (http://www.argo-project.eu/), funded by the European Commission under Horizon 2020 Research and Innovation Action, Grant Agreement Number 688131.

A STR2RTS benchmark suite

Following Table 5 characterise the used benchmarks from STR2RTS benchmark suite. The first column presents the number of tasks and the second column the width of the graph.

Then it gives the average data in bytes sent along all edges. Following is the average memory footprint of all tasks withing a benchmark, it includes the code size and the stack size. Last column shows the average, among all tasks, of WCET estimates. All this information are shipped with the benchmark suite and target a Patmos single core architecture [START_REF] Schoeberl | Patmos reference handbook[END_REF].


Dmitri Gazizulin

Roni Schneck
email: roni.shneck@gmail.com

Renata Klein
email: renata.klein@rkdiagnostics.co.il

Jacob Bortman

Spall Evolution in a Rolling Element Bearing

Rolling element bearing (REB) is one of the basic mechanical components in rotating machinery. It is common to divide the REB wear into two stages, damage initiation and damage propagation. There has been a growing awareness of the need to understand the damage mechanism during the propagation phase. The current work includes a discussion on the ongoing research and the methodology for the development of the prognostic method for damage propagation. The methodology integrates experiments, diagnostic methods, and physics-based models. Endurance tests were conducted in order to learn about the damage propagation process and model validation. Furthermore, Finite Element model of the spalled bearing was developed and validated. The FE model aims to investigate and simulate the damage propagation process. The simulation results are in good agreement with the experimental observation.

Introduction

Failure prognosis of rolling element bearings (REBs) is crucial in rotating machinery PHM. The damage evolution in REBs consists of two main phases: damage initiation and propagation. The conventional REB life models address the lifetime of the bearing to the damage initiation, i.e. first spall formation [START_REF] Sadeghi | A review of rolling contact fatigue[END_REF]. However, after the first spall formation, the bearing might be fully operational for millions of cycles. After the first spall formation, it propagates in the circumferential direction of the raceway, until the bearing becomes non-operational [START_REF] Rosado | Rolling contact fatigue life and spall propagation of aisi m50, m50nil, and aisi 52100, part i: experimental results[END_REF].

Many diagnostic tools have been developed in order to monitor the spall propagation. However, there is lack of reliable prognostic of the remaining useful life (RUL). Physic-based prediction of the damage propagation in the REB, after the first spall generation. The difficulties in prognosis of the propagation stage necessitate deep understanding of the damage mechanisms, the stochastic nature of the spall propagation process, and its modeling [START_REF] Li | Adaptive prognostics for rolling element bearing condition[END_REF][START_REF] Qiu | Damage mechanics approach for bearing lifetime prognostics[END_REF]. The main goal of the current work is to develop a physics-based prognostic method for the spall propagation in REBs. Herein, we present a methodology for the development of the prognostic method, which combines experiments, diagnostic methods, and physics-based models.

Methodology

The proposed methodology for prognostic of the RUL is based on a combination of physics-based models, diagnostic methods and experiments [START_REF] Gazizulin | Physics based methodology for the estimation of bearings' remaining useful life: Physics-based models, diagnostic methods and experiments[END_REF]. The concept is presented in Figure 1. This section includes a description of the objectives that need to be reached in order to achieve the main goal, RUL prognostics. The first objective is the quantitative and qualitative understanding of the damage-driven mechanisms, e.g. plastic strains, residual stresses, etc., of the spall propagation process. In addition, it is important to learn, based on the existing literature and experiments, about the effects of the bearing's features (e.g. hardness, ball mass), and operational conditions (e.g. speed, load) on the propagation process and the trend of the spall growth [START_REF] Arakere | Rolling contact fatigue life and spall propagation of aisi m50, m50nil, and aisi 52100, part ii: stress modeling[END_REF][START_REF] Branch | Stress field evolution in a ball bearing raceway fatigue spall[END_REF]. This objective can be attained by conducting endurance tests. Figure 2 shows an example of a diagnostic indicator evolution, BPFO Z-score distance vs. time. The tests can add insight regarding the spall propagation process and can be used for the physical model validation. The second objective is the development of a model for the damage propagation process. First, the material response in the presence of a defect must be analyzed. This analysis, coupled with the endurance test results, will shed light on the mechanism governing the damage propagation process. For this purpose a physicsbased model of a spalled bearing has been developed. The model is used for analysis of the material response in the presence of a defect. Moreover, the model was used for damage evolution simulation. Figure 3 shows examples of a simulation result and the metallurgical analysis of a bearing from an endurance test. The accomplishment of this objective will provide a mean estimated damage trajectory. However, the damage propagation is a stochastic process. Hence, dispersed results are expected. The third objective of the research, and probably the most challenging, is to model the stochastic nature of the damage propagation. The propagation of the spall in the REB is a stochastic process. Even under well controlled experimental conditions, using allegedly identical bearings, the results of the endurance tests vary [START_REF] Rosado | Rolling contact fatigue life and spall propagation of aisi m50, m50nil, and aisi 52100, part i: experimental results[END_REF]. The prognostic method must consider the uncertainties and the progress of the probability distribution. One of the common methods is to use diagnostic condition indicators in the early stages of the damage in order to monitor its propagation, e.g. oil debris, vibration level, etc. For this purpose, methods for the spall width estimation via time domain analysis were developed [START_REF] Kogan | A new model for spall-rolling-element interaction[END_REF]. The spall width is estimated based on the acceleration and strain signatures,

Summary and Conclusions

The remaining useful life (RUL) estimation using physics-based prognostic method is schematically illustrated in Figure 5. The calibration of the damage model can be implemented by comparing the simulations results with the data extracted from endurance tests. For example, a diagnostic method for the defect severity estimation (fault size, vibration level, etc.) can be implemented during the first stages of the tests. The results obtained by the diagnostic method can be used for the estimation of the damage model parameters and their uncertainties. The integration of the prognostic and the diagnostic methods, has the potential for reliable online estimation of the RUL including probability distribution of the result.

Figure 5: Bearing prognosis -first the damage propagation process is monitored; next, the model parameters are estimated; and the RUL is calculated [START_REF] Gazizulin | Physics based methodology for the estimation of bearings' remaining useful life: Physics-based models, diagnostic methods and experiments[END_REF].

Figure 1 :

 1 Figure 1: Research flow chart describing the steps toward the development of the prognostic method.

Figure 2 :

 2 Figure 2: Damage evolution trajectory during the endurance test. Each data point correspond to the vibration measurement during the test.

Figure 3 :

 3 Figure 3: SEM Image of the spall trailing edge and simulated cracks.

Figure 4 .

 4 The spall width and vibration based CIs will be used for the estimation of the damage model parameters by the trend identification of the spall propagation process. The accomplishment of this goal will complete the development of the physics-based prognostic method.

Figure 4 :

 4 Figure 4: Strain data vs. cycle, based on which the spall size was estimated. The (a) estimated size is 3.9 mm, and the (d) measured size is 4.0 mm.

Acknowledgments

The authors would like to express their deepest appreciations to Pearlstone Center for their support and funds of this work.


Keywords: Guidelines, methodology, performance, stormwater, SuDS

Development of a Guideline for Evaluating the Performance of Multi-objective Sustainable Drainage Systems (SuDS)

Le développement d'un guide méthodologique pour l'évaluation de la performance des ouvrages de maîtrise à la source des eaux pluviales K. Flanagan 1 , S. Ah-Leung 2 , L. Bacot 3 , A. Bak 4 , S. Barraud 5 , P. Branchu 6 , H. Castebrunet 5 , N. Cossais 2 , B. De Gouvello 1,7 , J.-F. Deroubaix 1 , R. Garnier 5 , M.-C. Gromaire 1 , A. Honegger 2 , P. Neveu 8 , J. Paupardin 9 , P.-E. Peyneau 10 , D. Ramier 6 , F. Rodriguez 10 , V. Ruban 10 , M. Seidl 1 , E. Thomas 11 , L. Varnede 1,6,12 1 LEESU, École des Ponts ParisTech, Champs-sur-Marne (kelsey.flanagan@enpc.fr) ; 2 EVS, ENS Lyon, Lyon ; 3 GRAIE, Villeurbanne ; 4 St Dizier Environnement, Boulogne-Billancourt ; 5 Laboratoire DEEP, INSA Lyon, Villeurbanne ; 6 Cerema, Equipe-projet TEAM, Trappes ; 7 CSTB ; 8 STEA de la Ville de Paris, Paris ; 9 Département de Seine Saint Denis, DEA, Bobigny ; 10 LEE, IFSTTAR Nantes, Bouguenais ; 11 Département de Seine et Marne, DPR, Vert Saint Denis ; 12 ECOVEGETAL, Broué RÉSUMÉ L'évaluation in situ des performances des ouvrages de maîtrise à la source des eaux pluviales pose un grand nombre de questions d'ordre méthodologique. Ainsi, dans le cadre de trois projets de recherche français dédiés à ce type d'évaluation, Matriochkas, Micromegas et Roulépur, un groupe de travail sur l'harmonisation des méthodes a été constitué afin de faciliter l'inter-comparaison des résultats issus des projets, mais aussi de rédiger un guide méthodologique à destination des acteurs opérationnels pouvant être amenés à faire ce type d'étude. Ce guide propose une démarche où la performance est évaluée pour chaque fonction de service visée pour l'ouvrage, en réponse à des enjeux locaux. La première partie du guide détaille les fonctions de service pouvant être attendues de ce type d'ouvrage. Ensuite, des indicateurs de performance sont déclinés pour une sélection de fonctions de service couramment rencontrées dans le contexte français et qui ont pu être abordées au cours des projets. Ces indicateurs se regroupent en trois catégories : les indicateurs hydrologiques (relatifs aux flux d'eau), les indicateurs pollutifs (relatifs aux polluants) et les indicateurs sociotechniques. Le guide s'appuie sur des exemples issus des trois projets pour présenter des cas pratiques de dispositifs métrologiques et d'application des indicateurs proposés.

ABSTRACT

Evaluating the performance of sustainable drainage systems (SuDS) in a field context presents a number of methodological problems. For this reason, as a part of three French research projects focused on this type of evaluation, Matriochkas, Micromegas and Roulepur, a working group on methodological harmonisation was established in order to facilitate the inter-comparison of results between the projects and propose a methodological guideline for practitioners carrying out such evaluations. The guideline proposes an approach where performance is evaluated with respect to a service function that the SuDS aims to achieve, itself identified from local issues. Its first section presents the various service functions which may be assigned to these devices. Next, performance indicators are defined for a selection of the identified service functions, common within the French context and studied as a part of the three projects. Three categories of indicators are identified: hydrologic indicators (relative to water flows), pollutant indicators and socio-technical indicators. Examples of instrumentation and of the application of the proposed indicators drawn from the experience of the three projects are also presented.

INTRODUCTION

Over the past decades, in a context combining increased urbanisation and growing concerns over the quality of the environment, urban drainage has undergone a paradigm shift. Approaches have evolved from one of rapid drainage using devices with the sole objective of evacuating stormwater, to one of onsite management using systems designed to achieve multiple objectives, known under a large number of names across the world, including sustainable drainage systems (SuDS), low impact development (LID), water sensitive urban design (WSUD), alternative techniques (techniques alternatives in French) and source control (Fletcher et al., 2014).

As these techniques are relatively recent, their performance in the complex conditions of the field context is not yet fully characterized or understood (Geberemariam, 2016). Thus, in situ performance evaluations are required in order to (i) validate that achieve the expected objectives, (ii) improve understanding of factors affecting performance and (iii) provide a basis for improving system design and optimizing performance.

Such evaluations raise a number of methodological questions. For one thing, given the multifunctional nature of these devices, performance is not a single concept but one which must be defined with respect to the objectives or functions of the system studied (Moura et al., 2011). Once the type of performance is defined, questions arise as to which performance indicators should be used to evaluate each function. The last phase is to select relevant methods for evaluating the performance indicators; this step often requires the implementation of a monitoring system, which must also be defined.

In order to harmonize methods for SuDS performance evaluation, a working group was established between three coordinated French research projects, Matriochkas, Micromegas and Roulépur, all focused on evaluating the performance of SuDS devices and financed as a part of a call for projects by the French Biodiversity Agency (AFB) and the French Water Agencies on micropollutants in urban water. The working group included both researchers and practitioners from several different institutions and served two objectives: (i) to facilitate the inter-comparison of results from the twelve sites studied as a part of the three projects and (ii) to propose a guideline for practitioners needing to carry out performance evaluations. The present article focuses on the latter objective.

METHODS

Working group organisation

The working group met regularly from the beginning of the projects in 2015 in order to discuss (i) the types of performance to be evaluated, (ii) the definition of performance indicators, (ii) the methods for evaluating indicators and, in particular, the monitoring systems to implement when measurements are required and (iv) the application of these indicators to the sites studied in the three projects.

Methodological approach

An approach was developed based on functional analysis, wherein performance is evaluated with respect to service functions intended for the device, themselves defined in response to issues within the local environmental, hydrologic, urban and political context (Figure 1).

Figure 1: Approach for evaluating performance Two types of service functions can be distinguished: usage functions, for which a device was created and constraint functions, which are constraints on the device behaviour and design given that it exists (AFNOR, 1996). Performance indicators were defined with respect to a selection of service functions, common to those observed within the French context and studied within the three research projects.

RESULTS AND DISCUSSION

Definition of issues and functions

Six issues to which sustainable drainage systems (SuDS) may respond were identified (Figure 2): flood reduction, resource preservation, ecological preservation, built environment protection, urban environmental quality and efficient management. Service functions which may be assigned to SuDS in response to each issue were identified; between two and six functions were associated with each issue, each of which was categorized as either a usage or a constraint function. Complementary or conflictual relationships exist between several service functions. When a complementary relationship exists, designing for one service function may provide benefits in terms of the other service function, even if it was not intended at the time of conception. For example, a system may be designed for volume reduction in order to limit flood risk, but volume reduction will also provide benefits in terms of pollutant load limitation. Functions may also respond to two issues; this is notably the case for pollutant load limitation which can respond to both resource and ecological preservation issues. Although the pollutants of concern are likely to be different between the two issues (for example, if the quality of a water body is to be preserved for recreational bathing, human pathogens are of greatest concern, whereas ecosystem preservation requires control of substances leading to eutrophication or ecotoxicity), designing for one of these objectives is likely to provide benefits for the other.

Conversely, when conflictual relationships exist between functions, fulfilling one function could potentially have negative effects on another function. This is the case, for example, between pollutant load limitation, which often involves retaining pollutants in the topsoil of a SuDS device, and the protection of the soil's biodegradation potential, which may be degraded if the soil is polluted. A conflict may also exist between accommodating biodiversity and pest limitation, as some species may be seen as nuisances while also contributing to biodiversity. Likewise, there may be a conflict between functions best achieved by infiltration (volume reduction, contribution to water resources) and prevention of geotechnical or hydrogeological disorders caused by infiltration. In all of these cases, there are tradeoffs between functions which require value judgements to find an optimal balance.

Issues

Service functions

Usage functions

Constraint functions

Performance indicators and monitoring

The guideline proposes performance indicators for the 17 service functions shown in red, bold text in Figure 2. Four types of indicators are identified: (i) relative indicators, which compare a value (often measured at a system outlet) to a reference corresponding to situation before or without the system; (ii) normative indicators, which compare a measured value to a level considered to be acceptable; (iii) descriptive indicators, which describe a system's behaviour, allowing for comparison with values from other systems, and (iv) explicative indicators, which seek to explain a level of performance observed.

For some functions, several indicators are proposed, which provide different types of information and may be more or less difficult to evaluate (for example, some indicators are relevant at the event time scale, others at the annual scale).

Indicators are divided into three categories: hydrologic indicators (relative to water flows or volumes), pollutant indicators (relative to pollutant loads or concentrations) and socio-technical indicators (relative to governance and / or social acceptance and use).

The collection of data necessary for the evaluation of each category of indicator is also discussed, including the identification of the system to be evaluated and the types of measurements to be carried out (flow measurement for hydrologic indicators, flow measurement and analysis of concentrations in water and/or soil for pollutant indicators and characterisation of the socio-technical system through interviews, surveys or observations of human actors for socio-technical indicators). Recommendations as to the metrology necessary to evaluate hydrologic and pollutant indicators are provided. Examples of the metrology implemented on the 12 sites studied as a part of the three projects illustrate practical difficulties associated with monitoring campaigns of SuDS devices, such as the need to choose equipment that is adapted to a site's constraints (e.g. little available space, no electrical connection) or the necessity of using a reference catchment to represent diffuse flows.

Because data collection is often costly and time-consuming, readers are encouraged to seriously consider the feasibility and relevance of the monitoring campaign (given the technical and organisational constraints and the economic, material and human resources available) before investing in the campaign. It is also acknowledged that field monitoring campaigns may not always yield all of the data expected due to unexpected constraints or data invalidation. In this case, it may be necessary to use adapted, non-ideal indicators. For example, it is generally desirable to evaluate relative indicators (for example, concentration reduction) for paired samples from the same event. However, sometimes paired samples are not obtained due to technical difficulties. In this case, distributions established over several events (or median values from these distributions) may be compared rather than paired values for each event.

CONCLUSIONS

A guideline was established to aid practitioners needing to evaluate the performance of sustainable drainage systems (SuDS) as a part of three French research projects dedicated to this goal, in parallel with monitoring campaigns at 12 different sites, enabling the practical experience derived from these projects to be taken into account. The guideline recommends first identifying the issues to which a device responds within the local context and the service functions intended to respond to these issues. Performance indicators are proposed for most of the common service functions and recommendations are made as to methods for acquiring the information required for evaluating these indicators. Once the indicators have been evaluated, the user will have at his disposal information enabling him to make an informed decision regarding the behavior and performance of the device.

Figure 2 :

 2 Figure 2: Issues to which SuDS may respond and service functions which may be expected; functions for which performance indicators are proposed are shown in bold, red text.

LIST OF REFERENCES

 AFNOR (1996). NF EN 1325-1 (Value management, value analysis, functional analysis vocabulary -Part 1: Value analysis and functional analysis). Fletcher, T.D., Shuster, W., Hunt, W.F., Ashley, R., Butler, D., Arthur, S., Trowsdale, S., Barraud, S., Semadeni-Davies, A., Bertrand-Krajewski, J.-L., Mikkelsen, P.S., Rivard, G., Uhl, M., Dagenais, D., Viklander, M. ( 2014). SUDS, LID, BMPs, WSUD and more -The evolution and application of terminology surrounding urban drainage. Urban Water J. 12(7), 525-542.

Geberemariam, T. (2016). Post Construction Green Infrastructure Performance Monitoring Parameters and Their

Functional Components. Environments 4(1), 2. Moura, P., Barraud, S., Baptista, M.B., Malard, F. (2011). Multicriteria decision-aid method to evaluate the performance of stormwater infiltration systems over the time. Water Sci. Technol. 64(10), 1993Technol. 64(10), -2000. .