Hai Nam Tran
email: hai-nam.tran@univ-brest.fr

Alexandre Honorat
email: alexandre.honorat@insa-rennes.fr

Jean-Pierre Talpin
email: jean-pierre.talpin@inria.fr

Thierry Gautier
email: thierry.gautier@inria.fr

Loïc Besnard
email: loic.besnard@irisa.fr

Efficient Contention-Aware Scheduling of SDF Graphs on Shared Multi-bank Memory

Novel memory architectures have been introduced in multi/many-core processors to address the performance bottle neck due to shared memory accesses. Taking the advantages brought by these architectures in scheduling analysis is still an open challenge. In this article, we present a scheduling analysis technique that exploits a shared multi-bank memory architecture to efficiently schedule parallel real-time applications modeled as synchronous data flow (SDF) graphs by minimizing the memory access contentions. Our approach aims at producing a static timetriggered schedule with the objective of minimizing the makespan and buffer size requirements while respecting consistency and data dependency constraints. An Integer Linear Programming formulation of the scheduling problem is presented, as well as a heuristic with significantly lower time complexity. Experimental results are given using synthetic SDF graphs generated by the SDF3 tool and applications available in the StreamIt benchmark.

I. INTRODUCTION

The increasing complexity of signal, image, and control processing applications demands higher computational power and performance to meet real-time constraints [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF]. Multi/manycore processors with novel memory architectures are becoming applicable platforms for executing these applications as they provide both performance and power efficiency. At the moment, they demand the adoption of new programming paradigms to support efficient exploitations. Indeed, processes and threads have been used for decades by programmers, showing advantages but also limitations. Because of shared memory synchronization, processes and threads can yield unexpected behaviors, non-deterministic execution or deadlocks.

The data flow programming paradigm has been introduced to address these limitations. This model is commonly used in embedded system design to describe stream processing or control applications. Its simplicity allows the adaptation of automated code generation techniques to limit the problematic and error-prone task of programming real-time parallel applications. Among data flow models of computation, synchronous data flow (SDF) [START_REF] Lee | Static scheduling of synchronous data flow programs for digital signal processing[END_REF] is one of the most popular in the embedded system community. This model is deterministic in terms of communications: the topology and the amount of data sent and received are known (fixed). Communications between processing elements are clearly isolated through well identified FIFO channels. Task parallelism [START_REF] Gordon | Exploiting coarse-grained task, data, and pipeline parallelism in stream programs[END_REF] in SDF can be exploited systematically: tasks can be mapped to available processing elements, dependencies can be enforced, and tasks on different branches can execute in parallel.

Problem statement: Scheduling analysis on multi/manycore platforms must account for the non-negligible delay due to accesses contention on shared memory [START_REF] Pellizzoni | Toward the predictable integration of real-time cots based systems[END_REF]. Experimental results in [START_REF] Nélis | The variability of application execution times on a multi-core platform[END_REF] show that the execution time can be increased by a factor up to 8. Preliminary works on this scheduling problem only consider shared memory architectures with a single memory bank. They do not fully exploit the advantages of shared multi-bank memory as well as the deterministic communications exposed in SDF graphs to optimize memory access contention.

In addition, they conventionally involve the transformation of an SDF graph into its equivalent homogeneous form (HSDF). While this transformation helps fully expose task and data parallelism of the graph, it also presents several limitations such as an exponential increase of actors, memory consuming schedules and high buffer size requirements. A recent evaluation in [START_REF] Zaki | Implementation, scheduling, and adaptation of partial expansion graphs on multicore platforms[END_REF] has shown that scheduling a partially expanded graph could be as efficient as its HSDF expansion. That motivates our proposal of a solution that explores the design space with the SDF representation.

Contribution: We propose a two-step approach to compute an efficient contention-aware scheduling of SDF graphs on one compute cluster consists of processing elements (cores) and a shared multi-bank memory. First, we compute an abstract schedule defining the dependencies amongst actor firings with the objective of minimizing buffer size requirements. Second, we construct an optimal time-triggered schedule that minimizes the makespan, which is the time difference between the start of the first scheduled actor and the end of the last scheduled actor in one iteration of the SDF graph [START_REF] Sriram | Embedded multiprocessors : scheduling and synchronization[END_REF]. Our approach aims at creating a time-triggered schedule that achieves a minimal makespan while trying to reduce the total amount of buffer size requirements. We study a shared multibank memory architecture presented in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF]. This particular architecture already exists in industrial platforms such as the Kalray MPPA [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF] many-core architecture.

The rest of this article is organized as follows. Section II presents related work and positions our contribution. Section III describes our system model, scheduler specification, and provides a brief description of our resource sharing platform model. Section IV provides an overview of our approach. Section V introduces our method of computing an abstract schedule that minimizes buffer space requirement. Then, section VI presents our approach of computing a time-triggered schedule with the objective of optimizing the makespan. The approach is evaluated in section VII with synthetic SDF graphs and applications taken from the StreamIt benchmark [START_REF] Thies | Streamit: A language for streaming applications[END_REF]. Finally, section VIII concludes the article and discusses future work.

II. RELATED WORKS

Our work is closely related to existing works in two domains: [START_REF] Grandpierre | From algorithm and architecture specifications to automatic generation of distributed real-time executives: a seamless flow of graphs transformations[END_REF] scheduling SDF graphs on multi/many-core architectures and (2) contention-aware scheduling analysis.

First, we discuss SDF graphs scheduling. In [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF], the authors presented a scheduling synthesis approach for SDF graphs on partitioned multi-core platform. The approach accounts for both functional properties (mapping) and timing parameters (period, release time and priority). In this work, the author modeled communication channels but did not take into account communication cost. Several conditions are described to guarantee the consistency of SDF graphs. While considering time-triggered scheduling rather than fixed priority and dynamic priority, our work tackles the same problem statement and can be considered as an extension of [START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF].

The work in [START_REF] Caspi | From simulink to scade/lustre to tta: a layered approach for distributed embedded applications[END_REF] addressed the multiprocessor scheduling of synchronous programs under a time-triggered bus architecture. The authors assumed a model of communication in which the bus can only transmit one message at a time and collision of messages implies infeasible schedule. On the contrary, our work assumes a more complex communication model of multiple bus arbiters and accounts for contention.

In [START_REF] Carle | From dataflow specification to multiprocessor partitioned time-triggered real-time implementation[END_REF], the authors considered an implementation of data flow applications on multi-core systems based on the previous work in [START_REF] Potop-Butucaru | Clockdriven distributed real-time implementation of endochronous synchronous programs[END_REF]. The authors focus on the optimization of an offline schedule taking into account non-functional properties such as start time and deadline. This work aims at eliminating the interference on shared resources by providing temporal isolation. In our approach, we account for the interference and hence may be complementary to this previous work.

A large proportion of works presented next are related to the Kalray MPPA many-core architecture. In this architecture, there are 256 processing cores organized in 16 compute clusters (16 cores per cluster) connected by a Network-on-Chip (NoC). These works are classified into either multicluster [START_REF] Tendulkar | Manycore scheduling of data parallel applications using smt solvers[END_REF]- [START_REF] Perret | Mapping hard real-time applications on many-core processors[END_REF] or single-cluster [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF], [START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF]- [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architectures[END_REF] context.

In [START_REF] Tendulkar | Manycore scheduling of data parallel applications using smt solvers[END_REF], the authors presented an approach of mapping and scheduling well-formed split-join SDF graphs on all compute clusters of the Kalray MPPA by using a satisfactory modulo theory (SMT) solver. The well-formed split-join restriction in [START_REF] Tendulkar | Manycore scheduling of data parallel applications using smt solvers[END_REF], which is relaxed in our work, facilitates the HSDF expansion and buffer size computation. Later, the work in [START_REF] Skalistis | Near-optimal deployment of dataflow applications on many-core platforms with real-time guarantees[END_REF] presented an optimization for the schedule generated by the SMT solver developed in [START_REF] Tendulkar | Manycore scheduling of data parallel applications using smt solvers[END_REF]. The authors proposed an approach to identify and exclude the pessimistic estimation of contention by detecting the set of actors that cannot access the same resource at the same time. In our work, we use integer linear programming to find the optimal solution and also provide a heuristic with lower time complexity.

On the topic of contention-aware scheduling, the authors in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF] described a response time analysis for single-period application modeled as a directed acyclic graph (DAG) on a shared multi-bank memory architecture. This work applies to a single cluster of the Kalray MPPA. It is assumed that both mapping and execution order on each core are known. Later, [START_REF] Martinez | Quantifying wcet reduction of parallel applications by introducing slack time to limit resource contention[END_REF] described a scheduling refinement technique that can reduce contention in the schedule of [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF] by introducing processor idle time. In comparison with these works, our approach takes into account both mapping and scheduling problem instead of only scheduling.

In [START_REF] Giannopoulou | Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources[END_REF], the authors proposed a mixed-criticality scheduling response time analysis on the all compute clusters of the Kalray MPPA. The main difference with our approach is that the authors consider a "Flexible Time-Triggered Scheduling" model which divides time into frames and force a global synchronization barrier between frames. As pointed out in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF], this potentially creates core under-utilization while waiting for the barrier. Our proposed scheduling policy does not require any global barrier but is limited to only one compute cluster.

The work in [START_REF] Perret | Mapping hard real-time applications on many-core processors[END_REF] focused on the problem of mapping large multi-cluster applications consisting of periodic tasks while maintaining a strong temporal isolation from co-running applications. The application model and optimization objective in this work is different from our approach.

An ILP formulation and a heuristic aiming at scheduling periodic independent PRedictable Execution Model (PREM) based tasks [START_REF] Pellizzoni | A predictable execution model for cots-based embedded systems[END_REF] in a single cluster of the Kalray MPPA is proposed in [START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF]. The authors systematically create a contentionfree schedule. Our work differs in the considered application model as well as the goal to reach. The authors consider sporadic independent tasks to which they aim at finding a valid schedule that meets deadlines. In contrast, we consider one iteration of an SDF graph and aim at finding the shortest schedule.

The authors in [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architectures[END_REF] also presented an ILP formulation and a heuristic to schedule and map DAG graphs in which each node is a PREM-based task [START_REF] Pellizzoni | A predictable execution model for cots-based embedded systems[END_REF] with the objective of minimizing the makespan. The authors took memory access contention into account but only assumed a single bank memory architecture. Comparing to this work, we assume a simpler task model while accounting for a more complex application model and memory architecture.

We position our work in the single cluster context as the ones in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF], [START_REF] Becker | Contention-free execution of automotive applications on a clustered many-core platform[END_REF]- [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architectures[END_REF]. Comparing to the state of the art, the novelty of our work lies at the exploitation of the shared multibank architecture and the well determined communication model in SDF graphs to optimize memory access contention. In this work, given an acyclic delayless synchronous data flow (SDF) graph, our aim is to compute the mapping and scheduling of one iteration of the graph on a resource-sharing platform model consisting of processing cores and a multibank shared memory. We first introduce the SDF model and present our scheduler specification in section III-A and III-B. In addition, we detail our assumptions regarding the acyclic and delayless property of SDF graphs. We also explain our motivation behind the choice of such model and scheduler. Then, we describe our resource sharing platform model in section III-C and illustrate the problem of memory access contention in section III-D.

A. Synchronous Data Flow Model

A synchronous data flow (SDF) graph is a directed graph G = (V, E) consisting of a finite set of actors V = {v 1 , ..., v N } and a finite set of one-to-one channels E. A channel e ab = (v a , v b , p, q) ∈ E connects the producer v a to the consumer v b such that the production (resp. consumption) rate is given by an integer p ∈ N (resp. q ∈ N). Every time an actor fires, it consumes a fixed number of tokens from its input channels and produces a fixed number of tokens to its output channels.

An actor v a is characterized by its execution profile denoted as C a = {PD a , MD a }. In contrary to the notion of worstcase execution time (WCET) used in previous literature, the execution profile is decoupled into processor demand and memory demand. The processor demand (PD a ) denotes the computation or CPU time of v a , without considering the time spent on fetching data from the memory. The memory demand (MD a ) denotes the number of memory accesses per actor firing. Such decoupling of the WCETs is proved to be feasible on fully timing compositional platform [START_REF] Wilhelm | Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems[END_REF] such as the Kalray MPPA [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF], which has been studied in the project CERTAINTY FP7.

A channel e ab has a bounded buffer size δ(e ab ). If the buffer sizes for certain channels are too small, the SDF graph could deadlock. For example, with the graph in Figure 1, the channel e 12 connecting v 1 and v 2 needs a minimum buffer size of 6. The reason is that v 1 must be fired at least 3 times before v 3 is fired and then v 2 can be fired. If δ(e 12 ) = 5, the graph deadlocks after two firings of v 1 and no actors can be fired. There can be a number of initial tokens associated with each channel. It is called the delay of a channel since it can induce an offset in the execution of the consumer in relation to the producer [START_REF] Battacharyya | Software Synthesis from Dataflow Graphs[END_REF]. We study only delayless SDF graphs in which the number of initial tokens on all channel is 0.

Definition 1 (Iteration [START_REF] Battacharyya | Software Synthesis from Dataflow Graphs[END_REF]): The iteration of an SDF graph is a non-empty sequence of firings that returns the graph to its initial state. Two concepts that are related to an iteration of the graph are defined below.

Definition 2 (Makespan [START_REF] Sriram | Embedded multiprocessors : scheduling and synchronization[END_REF]): The makespan of an SDF graph is the time difference between the start of the first scheduled actor and the end of the last scheduled actor in one iteration of the SDF graph.

Definition 3 (Repetition Vector [START_REF] Battacharyya | Software Synthesis from Dataflow Graphs[END_REF]): The repetition vector of an SDF graph is an array of length equal to the number of actors in SDF, such that if each actor is invoked for the number of times equal to its entry, the number of tokens on each edge of SDF remains unchanged.

For the graph in Figure 1, firing actor v 1 3 times, actor v 2 2 times and actor v 3 1 time forms an iteration. The repetition vector -→ z = (3, 2, 1) indicates the number of actor firings per iteration. If such a vector exists, then the graph is said to be consistent. In this paper, we study only consistent acyclic SDF graphs. Inconsistent graphs are of less importance since they cannot be implemented with bounded memory without deadlock. The repetition vector can be computed efficiently by applying a depth-first search algorithm presented in [START_REF] Battacharyya | Software Synthesis from Dataflow Graphs[END_REF].

B. Scheduler specification

In this work, we assume a non-preemptive time-triggered scheduler in a partitioned scheme of actor assignment. The term time-triggered scheduling refers to the fact that the overall behavior of the system is controlled by a recurring clock tick, the only event within the system which can trigger an action. There is an a-priori global schedule, which is computed offline, specifying the release times of all tasks. Time-triggered scheduling especially fits the needs of safetycritical applications. This special type of scheduling proved to be successful in such diverse areas as automotive electronics and aerospace industry [START_REF] Schild | Scheduling of time-triggered real-time systems[END_REF]. Regarding the scheduling policy in each core, we consider a non-preemptive scheduler and hence do not deal with cache-related preemption delay or context-switch overhead.

Actors are assigned to a core at design time and are not allowed to migrate from theirs assigned core to another one at runtime. It implies that multiple simultaneous firings of an actor cannot be executed in parallel. As accounting for autoconcurrency can lead to a complex contention-aware analysis, it is not considered in this article. Interested readers can refer to [START_REF] Zaki | Implementation, scheduling, and adaptation of partial expansion graphs on multicore platforms[END_REF], [START_REF] Kudlur | Orchestrating the execution of stream programs on multicore platforms[END_REF] for further detail.

C. Resource-Sharing Platform Model

We study the shared multi-bank memory introduced in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF]. This particular architecture already exists in industrial platforms such as the Kalray MPPA [START_REF] De Dinechin | Timecritical computing on a single-chip massively parallel processor[END_REF].

A compute cluster P consists of m homogeneous processing elements (cores), P = {P 1 , ..., P m }. Each core in P has access to a private cache memory and to a local shared memory M. The shared memory M is divided into m memory banks, M = {b 1 , ..., b m }, as illustrated in Figure 2. Each bank has an equal fixed size, denoted as s. Each core has a private path (bus) to the shared memory and each memory bank is accessed via a separate bus arbiter. The private paths of the cores are connected to all bank arbiters, as depicted abstractly for Ar 1 in Figure . 1. Under these assumptions, two concurrently executed tasks on different cores can perform parallel accesses to the shared memory without delaying each other provided that they access different banks.

Only one core can access a given bank at a time and once granted, bank access is completed within a fixed time interval noted memory delay (d), which is the same for read/write operations and for all banks. In the meantime, pending requests to the same bank from other cores stall execution on their cores until they are served.

D. Memory Access Contention

In our model, each actor has a local memory buffer, and the buffers of all actors running on the same core are mapped to the same memory bank. Buffer spaces for all input channels of an actor are allocated in the memory bank of this actor. Under these assumptions, read accesses are private but write requests may access to another core's memory bank. Contention may occur on the memory bus when two cores access to the same memory bank. This assumption is indeed an arbitrary choice. We are aware that optimizing buffer spaces allocation to minimize memory access contention is an interesting problem but it complex to tackle at the same time with the task mapping and scheduling problem.

Access requests from the cores inside one compute cluster are subject to a round-robin arbitration [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF]. For example, we assume that two firings of actors v a and v b access to the same memory bank and execute in parallel. In the absence of detailed information on the pattern of access requests within an actor, we consider that any two firings that overlap in time can interfere on each of their accesses. The memory contention between two firings, denoted as γ a,b , is given by:

γ a,b = min(MD a , MD b ) • d (1)
We take a simple example to illustrate the contention-aware scheduling problem on a shared multi-bank memory in Figure 3. Actors v 1 and v 2 are executed in parallel. Actor v 1 has write accesses to the memory bank of actor v 3 . In the (a) case, actor v 3 is mapped to core P 1 and there is no contention. In the (b) case, actor v 3 is mapped to core P 2 . Thus, there is contention between actor v 1 , which writes data to bank 2, and actor v 2 , which reads data from bank 2. This contention can be effectively optimized when we compute the schedule.

In this section, we have introduced our system model and assumptions taken. In the next sections, we present our approach of computing an efficient contention-aware scheduling of SDF graphs on shared multi-bank memory.

IV. GENERAL APPROACH

Considering SDF graphs, we need to allocate storage spaces and schedule the actors so that deadlock, overflow and underflow do not occur. In addition, we need to compute timing parameters, processor mapping and to take into account the contention due to shared memory accesses. If all these variables are considered in a monolithic optimization problem, it would result in a very complex set of constraints and would be practically solvable for only a very small number of actors. From this observation, we propose a two-step approach in which each step focuses on solving a subset of problems.

First, we compute an abstract schedule defining data dependencies between actors in one iteration of an SDF graph with the objective of minimizing storage space requirement. It is abstract in the sense that the schedule neither depends on processor mapping nor real-time scheduling, which are taken into account later. We show in the next section that our abstract schedule can be computed by simply solving the minimum buffer size scheduling problem [START_REF] Čubrić | Minimal memory schedules for dataflow networks[END_REF].

Second, from the computed abstract schedule, we synthesize a time-triggered schedule that minimizes the makespan. This schedule defines processor mapping and timing parameters of all actor firings in one iteration of the SDF graph. Contention due to shared memory accesses is considered when we compute the schedule. To achieve the objective, we propose two solutions: an integer linear programming formulation that can be used to find the optimal schedule and a heuristic with significant lower complexity.

V. ABSTRACT SCHEDULE

In this step, first, we need to compute the minimum buffer sizes required for the channels. Second, based on the computed buffer sizes, we enforce the constraints related to firing dependencies so that the schedule guarantees that neither overflow nor underflow will occur. Indeed, firing dependencies define the data dependencies between the two actors connected by a channel. At this step, we do not compute the precise mapping or timing activation of actors. Only the dependencies between actor firings are computed.

Min buffer size analysis: Given a consistent acyclic SDF graph with its repetition vector, there exists schedules that result in different buffer size requirements. It has been proved in [START_REF] Battacharyya | Software Synthesis from Dataflow Graphs[END_REF] that the problem of computing a minimum buffer schedule for even an arbitrary SDF graph is NP-complete. However, a heuristic with polynomial complexity has been given in [START_REF] Čubrić | Minimal memory schedules for dataflow networks[END_REF] where the authors established its optimality for acyclic, delayless SDF. To keep the article concise, we do not detail the algorithm. Interested readers can refer to [START_REF] Battacharyya | Software Synthesis from Dataflow Graphs[END_REF] or [START_REF] Čubrić | Minimal memory schedules for dataflow networks[END_REF] for a simple pseudo code and details. This algorithm helps us computing the minimum buffer size that allows for a schedule without deadlock.

After buffer sizes for all channels are identified, we can compute the firing dependencies between actors by applying the two analysis belows:

Underflow analysis: we have an underflow when an actor attempts to read and there are not enough tokens on the channel. Thus, we need to compute the firing dependencies that guarantee no overflow. For a channel v a p q ---→ v b , the

n th firing of v b (denoted v b [n]
) is enabled if and only if the number of produced tokens is larger than q • n. Hence, v b has to wait for the l th firing of v a (denoted v a [l]) such that:

l • p -n • q ≥ 0 (2)
The firing dependency between v a and v b is formalized by the following equation:

v b [n] ≥ v a [l] with l = n • q p (3)
Overflow analysis: we have an overflow when an actor attempts to write and there are not enough empty spaces on the channel. For a channel v a p q ---→ v b of size δ(e ab ), the l th firing of v a (denoted v a [l]) is enabled if and only if the number of produced tokens is smaller than or equal to the number of empty spaces. Hence, v a has to wait for the n th firing of v b (denoted v b [n]) such that:

l • p -n • q ≤ δ(e ab ) (4)
The firing dependency between v a and v b is formalized by the following equation:

v a [l] ≥ v b [n] with n = l • p -δ(e ab ) q (5)
At the end of this step, by applying the analysis based on equations 3 and 5 on the SDF graph in Figure 1, we have the following result:

Repetition Vector : - → z = (3, 2, 1)
Buffer Size : δ(e 12 ) = 6, δ(e 13 ) = 3, δ(e 32 ) = 2 Firing Dependencies :

v 1 [2] > v 2 [1]; v 1 [3] > v 2 [2] ; v 1 [3] > v 3 [1]; v 3 [1] > v 2 [1]; v 3 [1] > v 2 [2]
Firing dependencies between v a [l] and v a [l+1] is implicit. We recall that in our scheduler specification, auto-concurrency is not allowed. The l th firing of actor v a must finish before the (l + 1) th firing starts. The abstract schedule above requires a total buffer size of 11 and guarantees no overflow and underflow exception. However, this schedule does not precise the mapping and timing parameters of actors in the SDF graph. In the next step we present our approach to build a concrete schedule from the abstract one.

VI. CONTENTION-AWARE SCHEDULE

This section presents two solutions to compute a concrete schedule and mapping from an abstract schedule. The first solution adopts an Integer Linear Programming formulation of the problem. The optimal schedule can be found with this solution. The second solution is a heuristic based on LIST scheduling, which allows us to find a valid schedule fast and generally close to the optimal one. The main outcome of both solutions is a static mapping and schedule for each core.

As we assume a time-triggered scheduler, it requires us to compute the timing parameters for all actor firings in one iteration of the SDF graph. In other words, we need to treat each actor firing as a real-time task. We first detail our transformation of actor firings to tasks in Algorithm 1.

Algorithm 1: Actor firings to tasks transformation

Input: SDF graph G, abstract schedule S A Output:

Task set T 1 T ← ∅ 2 foreach v a ∈ G do 3 for l = 1 to - → z (v a ) do 4 Create task τ i 5 τ i .C i ← C a 6 τ i .A i ← v a 7 τ i .prd(i) ← prd(v a [l]) ∪ v a [l -1] 8 T = T ∪ {τ i } 9 return T
Each firing of an actor v a in one iteration of the SDF graph is mapped to a real-time task τ i (line 2-8). We recall that one iteration of the SDF graph is defined by its repetition vector -→ z . Hence, the loop at line 3 is ranging from 1 to -→ z (v a ), which is the number of firings of v a in one iteration. The execution profile C i of τ i is identical to the one of the actor (line 5). The variable A i is used to save the actor that τ i represents. It is used in our algorithm to enforce partitioned mapping as an actor can only be mapped to one processor. Then, all firings of the actor must be on the same processor. The precedence dependencies of τ i are computed by taking into account firing dependencies of v a [l], denoted prd(v a [l]) (line 7). In addition, τ i must start after the firing v a [l -1] with regard to our assumption about non-auto-concurrency. This transformation effectively transforms our original problem into a scheduling problem of real-time tasks with dependencies. Next, our integer linear programing (ILP) formulation of the problem is presented.

A. Integer Linear Programming formulation

Our scheduling problem can be formulated as an Integer Linear Programming (ILP) problem. The objective is to obtain the shortest schedule while scheduling the tasks on a fixed number of processors and accounting for memory contention. In order to keep the presentation of ILP formulations short and concise, we use two logical operators ∨ and ∧ directly when describing the constraints. Transformation rules [START_REF] Brown | Formulating integer linear programs: A rogues' gallery[END_REF] can be used to transform these operators into linear constraints. Some ILP solvers such as IBM CPLEX support automatic transformation of these operators.

Our goal is to minimize the makespan of the schedule. In other words, it is minimizing the end time of the last scheduled task. The objective function, given in equation 6, is to minimize the makespan. Equation 7 enforces that the completion time of all tasks must be inferior or equal to the makespan.

Minimize: makespan (6)

makespan ≥ End i , ∀τ i ∈ T (7)
Scheduling constraints: The following constraints enforce basic rules which guarantee the validity of the computed schedule. Equation 8 enforces that a task is mapped on exactly one core. Equation 9enforces that all tasks representing firings of an actor must be mapped to the same core. Equation 10enforces that the completion time of a task is equal to its start time plus the response time R i .

m k=1 p i,k = 1, ∀τ i ∈ T ( 8
)
p i,k = p j,k , ∀τ i , τ j | A i = A j ( 9
)
End i = Start i + R i ( 10
)
Dependency constraints: Equation 11 enforces data dependencies, a task τ i can only be released when all tasks τ j ∈ prd(i) are completed. The precedence dependencies of the tasks are computed from the abstract schedule as we mention in Algorithm 1.

Start i ≥ End j , ∀τ j ∈ prd(i) (11)
Task overlapping constraints: Equations 12, 13 and 14 enforces that the executions of two tasks mapped the same core cannot be overlapped. In other words, task τ i cannot overlap any task τ j running on the same processor as τ i . The overlapping condition of two intervals [Start i , End i ] and [Start j , End j ], denoted o i,j , is computed by Equation 13. The condition of whether τ i and τ j are mapped on the same core is computed by Equation 14. We note that the value of c i,j , which is a binary variable, can only be either 1 or 0 as the unicity of task mapping is guaranteed by Equation 8.

o i,j ∧ c i,j = 0, ∀τ i , τ j ∈ T ; i = j ( 12
)
o i,j = (Start i < End j ) ∧ (End i > Start j ) ( 13
)
c i,j = m k=1 (p i,k ∧ p j,k ) (14)
Bank access constraints: Equations 15 and 16 imply that if task τ i is mapped to core p k , it has accesses to memory b k . In addition, τ i also has write accesses to the memory bank of the consumers of actor A i . We emphasize the fact that we use the consumer of actor A i which is extracted from the SDF graph in this constraint. Equation 17determines whether two tasks access to the same memory bank.

b i,k = p i,k (15)
b i,k = p j,k , ∀τ j | A j ∈ snk(i) (16)
a i,j = m k=1 (b i,k ∧ b j,k ) (17)
Equation 18 enforces that the total memory space requirement of actors mapped to one processor cannot be larger than the size of the memory bank associated to this processor. We assume that channels are allocated in the memory bank corresponding to the processing core where the consumers are mapped to. Because all tasks (firings) of an actor are mapped to the same processor, we only need to choose one task of each actor to generate this constraint.

Ai∈G p i,k • M R i ≤ s, ∀k ∈ [0, m] (18)
Memory access contention: Equation 19 computes whether two tasks τ i and τ j that are overlapped in time also access to the same memory bank. Equation 20 computes the memory access contention between two tasks. Finally, the response time R i is computed by applying Equation 21.

t i,j = o i,j ∧ a i,j (19)
γ i,j = t i,j • min(M D i , M D j ) • d (20)
R i = P D i + M D i • d + τj ∈T γ i,j (21)
Processor symmetry break: The presence of symmetry is common in many job-shop scheduling type problems that consider multiple identical machines. We apply a technique presented in [START_REF] Ostrowski | Symmetry in scheduling problems[END_REF] to break the processor symmetry in our problem. We let processor 1 run actor v 1 then processor 2 run the lowest index actor not running on processor 1, etc. This constraint is added to limit the search space and improve the performance of the ILP solver. It can be easily seen that the cost regarding buffer space requirements and memory contentions remains unchanged with such restrictions.

p i,k ≤ i-1 j=1 p j,k-1 , ∀(i, k), i ≥ k ≥ 2 (22)
The result of the scheduling problem after being solved by an ILP solver is then defined by two sets of variables. Task mapping is defined by variables p i,k . The static schedule on every core is defined by variables Start i and End i , which define the start and end time of tasks.

B. Heuristic

We propose a heuristic based on list scheduling. Tasks are firstly sorted in a topological order based on the position of their corresponding actors in the SDF graph. We are fully aware that it is an arbitrary choice; however, task ordering is beyond the scope of this article. Next, we find a set of ready tasks and schedule each task one by one without backtracking. The goal is to minimize the overall makespan of the schedule.

List scheduling: The heuristic is described in Algorithm 2. In order to keep the description short and concise, we only detail important functions of the algorithm while providing a short description for other functions.

The input of the algorithm is an abstract schedule and a set of processors. At the beginning all tasks are in the waiting queue (QWait); other queues are empty (lines 1-4). Then a loop iterates until all tasks are scheduled (lines Inside the loop, we first find tasks that can be scheduled immediately without any dependencies to be satisfied and put them into the ready queue (QReady). Function Ge-tReadyQueue (line 6) computes this information based on tasks in the waiting queue and complete queue. Another loop iterates while there exists tasks ready to be scheduled (lines [START_REF] Thies | Streamit: A language for streaming applications[END_REF][START_REF] Bouakaz | Real-time scheduling of dataflow graphs[END_REF][START_REF] Caspi | From simulink to scade/lustre to tta: a layered approach for distributed embedded applications[END_REF][START_REF] Carle | From dataflow specification to multiprocessor partitioned time-triggered real-time implementation[END_REF][START_REF] Potop-Butucaru | Clockdriven distributed real-time implementation of endochronous synchronous programs[END_REF][START_REF] Tendulkar | Manycore 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][START_REF] Giannopoulou | Mixed-criticality scheduling on cluster-based manycores with shared communication and storage resources[END_REF].

Function MapEarliestStart (line 12) tries to schedule the task as early as possible on a processor. This heuristic uses the As Soon As Possible (ASAP) strategy when mapping a task. This function also verifies whether it exists a previously released task corresponding to the same actor with the current task in order to guarantee that they are mapped to the same core. In this case, we do not need to try to map the tasks to other cores.

It is important to note that task mapping has an effect on memory contention. After scheduling each task, the contention in relation with the newly scheduled task must be recomputed and tasks must be moved on the time line of each involved core to ensure a valid schedule. This problem is illustrated in Figure 4. We assume that τ 1 and τ 2 both produce data to τ 3 . Before the mapping of task τ 3 on processor P 1 , there is no contention between two tasks τ 1 and τ 2 . However, after τ 3 is mapped to processor P 1 , because τ 1 and τ 2 both write to the memory bank of τ 3 , there must be contention added to the execution time of the two tasks. As a result, we have to recompute the response time in order to account for the added delay.

Function UpdateSchedule (line 13), which is described in Algorithm 3, handles this problem. This algorithm is based on the contention-aware multi-core response time analysis presented in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF]. Comparing to [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF], our algorithm uses a more pessimistic but less complex contention computation and we also take into account non-auto concurrency.

Functon MinMakespan (line 14) compares the new schedule with the previously constructed schedule and returns the one with shorter makespan. Our algorithm chooses to map a task on a core that results in a schedule with the shortest makespan.

When a task is scheduled, it is removed from ready queue (line 16) and moved to complete queue (QComplete, line 17). The heuristic terminates when all tasks are scheduled.

Update schedule: Algorithm 3 computes the memory contention introduced by adding a new task. The implementation of function GetContention is based on Equation 20. Since the potential contention depends on the start time (Start i ) and response time (R i ), and the response times depend on the contention, this requires a fixed-point iteration. After computing

P 1 P 2 (a) τ 1 τ 2 P 1 P 2 (b) τ 1 τ 2 τ 3
(i) = prd(i) ∪ GetLastTask(p) 2 do 3 do 4 R i ← R i 5 foreach τ i ∈ pSched do 6 R i = P D i + M D i * d + GetContention(τ i , pSched) 7 while (exist τ i | R i = R i ); 8 Start i ← Start i 9 foreach τ i ∈ pSched do 10 Start i = max(Start + R j |j ∈ prd()) 11 while exist τ i | Start i = Start i ;
12 return pSched the response times, the schedule we get may not respect the firing dependencies and sequential constraints. We modify the start time so that each task is released immediately after each of the tasks it depends on is guaranteed to have completed.

Modifying the start times may change the contention, hence we have to recompute it until a fixed point is reached. The proof of convergence for these fixed-point iterations can be found in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF].

The output of the heuristic is a time-triggered schedule that gives the start times and response times of tasks on each core. Indeed, the makespan can be easily computed from this schedule. In the next section, we compare the ILP formulation and the proposed heuristic by evaluating their scalability and the computed makespans.

VII. IMPLEMENTATION & EVALUATION

Implementation of our approach is realized in ADFG [START_REF] Honorat | Adfg: a scheduling synthesis tool for dataflow graphs in real-time systems[END_REF], which is a real-time scheduling analysis tool for data flow graphs. SDF graphs model and several consistency verification methods are already provided by ADFG, which gives us a good facility to integrate our contribution. We extended the tool so that it computes the abstract schedule and exports constraints that can be presented to an ILP solver. The ILP solver used is IBM CPLEX v12.7.1 with a timeout of 1 hour -the solver stops even if the optimal solution is not found.

Experiments have been conducted to evaluate our approach, with the particularity of using shared multi-bank memory. In section VII-A, we evaluate the scalability of the ILP solution and the heuristic with regard to the size of the scheduling problem. Then, in section VII-B, we evaluate the quality of the heuristic by comparing its result to the ILP solution. We also provide a comparison between single-bank and multibank memory in section VII-C. We performed experiments with synthetic SDF graphs generated by the SDF3 graph generator [START_REF] Stuijk | SDF 3 : SDF For Free[END_REF] as well as a subset of applications taken from a refactored version of StreamIt benchmark [START_REF] Rouxel | Str2rts: Refactored streamit benchmarks into statically analysable parallel benchmarks for wcet estimation & realtime scheduling[END_REF], which is easily analyzable by static WCET estimation tools. SDF3 tool allows us to generate SDF graphs with various parameters such as: number of actors, number of firings per iteration of the SDF graph and actor's WCET. In addition, the generator allows us to set the max width of the graph and choose whether a graph is acyclic or not.

The general configuration of synthetic graphs is as follows. We generated two sets of synthetic SDF graphs as described in Table II. This idea of two-set configuration has been proposed in [START_REF] Rouxel | Tightening contention delays while scheduling parallel applications on multi-core architectures[END_REF] as it allows an adequate evaluation of scalability and quality. The small set is used to evaluate the ILP solution's scalability as well as comparing the ILP solution with the heuristic. The large set is used to evaluate the heuristic's scalability. For each set, 100 graphs were generated. Experiments with small set and large set are conducted with different numbers of cores. It is because SDF graphs in the small sets do not benefit from a high number of cores.

Actors in synthetic SDF graphs were generated so that their memory demand made up 10% to 30% of their WCETs. For actors taken from the refactored version of the StreamIt benchmark [START_REF] Rouxel | Str2rts: Refactored streamit benchmarks into statically analysable parallel benchmarks for wcet estimation & realtime scheduling[END_REF], memory requirement is computed by their generated code size, local variables and buffer spaces of input channels. In addition, memory demand of an actor is computed based on its production/consumption rate and the amount of data transfered per memory access, which is 64 bytes in our case. Memory access delay is set to 10 cycles as obtained from internal specifications [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF].

A. Scalability

The configuration with the small set of SDF graphs is used in this experiment. Figure 5.a displays the average ILP solving time per number of tasks in each graph. As the scheduling problem of tasks on multi-core platforms is known to be NPhard, the average solving time increases exponentially when the number of tasks increases. It clearly shows that a heuristic is necessary; however, the ILP solution can still be used to evaluate the quality of the heuristic.

We also evaluate the scalability of our heuristic with the large set of SDF graphs. the schedule. For the largest generated SDF graph with 100 actors and 1000 firings, it only takes around 40 seconds to compute the schedule.

B. Quality of the heuristic

Two baselines are used to evaluate the quality of our heuristic: (1) a basic solution which is a simple forward LIST scheduling and (2) the optimal solution computed by applying the ILP formulation. For this experiment, we use the small set configuration.

A basic solution is a simple forward LIST scheduling that only assigns a task to a core but does not verify whether the assignment results in the shortest makespan in a contentionaware context. As depicted in Figure 3, it can lead to unnecessary contention that could be either avoided or reduced. After the schedule is computed, the actual makespan is obtained by applying the contention-aware WCRT analysis presented in [START_REF] Rihani | Response time analysis of synchronous data flow programs on a many-core processor[END_REF].

We denote the makespan of the schedule obtained with the basic solution as M n , the heuristic as M aware and the ILP as M ILP . The difference of the makespan in percentage is computed by (M aware -M n )/M n when comparing with the basic solution and (M aware -M ILP )/M ILP when comparing with the ILP solution. The results are shown in Table III.

Comparing with the basic solution, the average speedup achieved with the heuristic is 18.3%. Considering that we only generate SDF graphs with low memory demand, the contention that could be reduced by the heuristic is relevant.

Comparing with the ILP solution, in the worst case, the heuristic performs 14.5% worse. We can see that the average degradation is only 5.7%. It shows that our heuristic has an acceptable quality. The difference in the length of computed makespan between two solutions comes from two reasons. First, in the heuristic, tasks are allocated to processors without any backtracking. We know that different methods of ordering tasks in ready queue can affect the schedule; however, this Multi-bank Fig. 6. Performance gain comparing to single-bank memory architecture achieved with the heuristic is a complex problem and not considered in the scope of the work. Second, we have observed that the ILP solution allows the existence of processor idle time in the schedule to avoid memory contention. In other words, instead of overlapping the execution time of two tasks on two processors, the schedule waits until one task is completed then schedules another task.

From the experiments in Section VII-A and VII-B, we can see that the heuristic has better scalability compared to the ILP solution while provides acceptable results.

C. Multi-bank and single-bank

The objective of this experiment is to compare the difference in performance between shared memory with single-bank and multi-bank. In the experiment, we apply our heuristic to a subset of applications in the StreamIt benchmark. Memory contention is accounted for in two ways: single-bank and multi-bank. With shared single-bank memory, any tasks that are overlapping in time can introduce contention. The makespan of the schedule obtained with shared multi-bank memory is denoted as M multi and the other is M single The speedup factor is computed by (M single -M multi )/M single .

The result is provided in Figure 6. The key reasons of the speedup come from the utilization of shared multi-bank memory. It allows actors to access shared memory in parallel without contention. Our first observation is that the speedup varies significantly between applications. In fact, it depends on the width of the SDF graph or application's parallelization level. For applications such as CFAR or ComplexFIR, the width of the SDF graph is 1. Thus, shared multi-bank memory does not bring any advantage. For applications such as BeamFormer in which the graph is highly parallelized, we can see a significant speedup up to 50%.

VIII. CONCLUSIONS

In this article, we present an approach of achieving efficient contention-aware scheduling of SDF graphs on a shared multibank memory architecture. The approach consists of two steps. First, we compute an abstract schedule defining firing dependencies with the objective of minimizing the buffer size requirement. Then from this abstract schedule we synthesize a time-triggered scheduling table with the objective of minimizing the makespan. The scheduling table can be computed by either the ILP formulation or the proposed heuristic based on LIST scheduling. Our experiments have shown that the proposed heuristic offers acceptable results, with only 5.7% degradation on average, and a significant lower complexity.

For future works, we would like to take into account different schedulers such as periodic fixed priority. We also want to provide a more comprehensive evaluation of the heuristic with different metrics such as schedulability, processor utilization and scalability when the number of cores increases. Furthermore, we want to study a more precise the contention model to reduce the pessimism by accounting for the actual duration of memory access phases. A possible research direction is taking into account a refined task execution model such as PRedictable Execution Model (PREM) [START_REF] Pellizzoni | A predictable execution model for cots-based embedded systems[END_REF] that splits a task into a read phase and an execute phase.

Fig. 1 .

 1 Fig. 1. A simple acyclic delayless SDF graph III. SYSTEM MODEL AND ASSUMPTIONS

Fig. 2 .

 2 Fig. 2. Shared multi-bank memory architecture. Only buses connecting cores and arbiter 1 (Ar 1 ) are illustrated.

Fig. 3 .

 3 Fig. 3. (a) v 1 only accesses to memory bank 1, there is no contention (b) v 1 accesses to memory bank 1 and 2, memory access contention between v 1 (write) and v 2 (read) on bank 2

Algorithm 2 : 7 QWait = QWait \ QReady 8 foreach τ i ∈ QReady do 9 tmpSched.makespan ← ∞ 10 foreach p ∈ P do 11 pSched ← S C 12 MapEarliestStart 15 S C ← tmpSched 16 QReady

 27891011121516 List scheduling Input: An abstract schedule S A , set of processors P Output: A concrete schedule: S C 1 QWait ← GetWaitingQueue() 2 QReady ← ∅ 3 QComplete ← ∅ 4 S C ← ∅ 5 while QWait = ∅ do 6 QReady ← GetReadyQueue(QWait,QComplete) (pSched, τ i , p) 13 UpdateSchedule (pSched, τ i , p) 14 tmpSched ← MinMakespan(tmpSched, pSched) = QReady \ {τ i } 17 QComplete = QComplete ∪ {τ i } 18 return S C

Fig. 4 . 3 Algorithm 3 :

 433 Fig. 4. (a) The schedule before the mapping of τ 3 , there is no contention. (b) The schedule must be recomputed after τ 3 is mapped to processor P 1 because τ 1 and τ 2 write data to the memory bank of τ 3

Figure 5 .Fig. 5 .

 55 Fig. 5. Average ILP (a) and heuristic (b) computation time. Time units are different in 5.a and 5.b.

TABLE III HEURISTIC

 III QUALITY COMPARED TO THE BASIC AND THE ILP SOLUTION

		Min	Max	Average
	vs. Basic	0%	-29.4%	-18.3%
	vs. ILP	0%	14.5%	5.7%


Rachid Boudhan

Aurélie Joubert

Sylvain Durécu

Kamal Gueraoui

Laurence Le Coq

Influence of air humidity on particle filtration performance of a pulse-jet bag filter

Keywords:

A pulse-jet bag filter, representative of those implemented in waste incineration plants for flue gas treatment, was studied at laboratory scale to evaluate the influence of air humidity on the filtration performance. Several cycles of clogging/unclogging were performed with non-hygroscopic submicronic particles with a nanosized fraction with on-line cleaning at operating conditions as similar as possible to those found in the flue gas treatment of waste incineration plants (150 °C -73 g/m 3 of absolute humidity), and in dry conditions (150 °C).

The results revealed a significant influence of air humidity on the bag filter performance: faster increase of bag filter pressure drop during clogging in presence of humidity due to water capillary condensation, lower efficiency of particulate cake unclogging and better collection efficiency of particles between 110 and 300 nm in diameter.

Introduction

Bag filters are frequently used within industries for flue gas treatment because of their high particle collection efficiency over a wide range of particle sizes. They are designed to treat high particle concentration with an on-line cleaning system. Bag filters are among the most effective and efficient gas/particle separation processes.

Several physical mechanisms contribute to enhance the collection efficiency of particles by fibrous or fabric filters such as bag filters. The main mechanisms are Brownian diffusion, interception, and inertial impaction; for each mechanism, the efficiency depends mainly on the particle size to collect. The particles deposited onto the filter media surface contribute to increase filtration efficiency [START_REF] Thomas | Clogging of fibrous filters by solid aerosol particles Experimental and modelling study[END_REF]. In fact, the collected particles bridge together to form the so-called dust cake on the filter media. The formation and detachment of the dust cake from the filter surface influence the filtration performance of the bag filter. The structural proprieties of the dust cake, and so the ability of dust cake detachment, are influenced by different parameters such as filtration velocity or dust concentration [START_REF] Cheng | Factors influencing pressure drop through a dust cake during filtration[END_REF][START_REF] Saleem | Effect of filtration velocity and dust concentration on cake formation and filter operation in a pilot scale jet pulsed bag filter[END_REF] and probably the air water content.

The effect of air humidity on filtration performance of filtering media is not fully understood because it depends on several parameters such as the hygroscopicity of the particles, their size, the nature and size of the fibers and their ability to sorb water, or the loaded mass of particles on the filter. The literature [START_REF] Gupta | Effect of humidity and particle hygroscopicity on the mass loading capacity of high efficiency particulate air (HEPA) filter[END_REF][START_REF] Joubert | Influence of humidity on clogging of flat and pleated HEPA filters[END_REF][START_REF] Miguel | Effect of air humidity on the evolution of permeability and performance of a fibrous filter during loading with hygroscopic and non-hygroscopic particles[END_REF][START_REF] Montgomery | Impact of relative humidity on HVAC filters loaded with hygroscopic and non-hygroscopic particles[END_REF] shows that for a given mass of collected particles, the pressure drop of fibrous filters decreases with increasing humidity; with higher effect with hygroscopic submicronic particles of soda chlorine below the deliquescent point than with non-hygroscopic micrometric aluminum oxide particles. [START_REF] Ribeyre | Impact of relative humidity on a nanostructured filter cakeexperimental and modelling approaches[END_REF] studied the influence of humidity on three different nanostructured filter cakes formed in dry air by three different non-hygroscopic nanoparticles and their results showed that the filter pressure drop increases when the relative humidity (RH) increased gradually from 0% to 85% (i.e. around 20 g/m 3 of absolute humidity AH). While [START_REF] Joubert | Modelling the pressure drop across HEPA filters during cake filtration in the presence of humidity[END_REF] showed that the exposure to a humid airflow of the loaded cake filter formed under dry conditions (with hygroscopic submicronic and non-hygroscopic micrometric particles) leads to the reduction of the specific cake resistance i.e. a decrease in the filter pressure drop.

Regarding the influence of humidity on filter collection efficiency, [START_REF] Kim | Filtration efficiency of a fibrous filter for nanoparticles[END_REF] tested the filtration of NaCl nanoparticles (diameters ranged between 3 and 70 nm) by a fiberglass filter. The results demonstrated no significant influence of humidity on the filtration efficiency for RH between 1% and 92% (i.e. 0.2 and 16 g/m 3 AH). However, [START_REF] Miguel | Effect of air humidity on the evolution of permeability and performance of a fibrous filter during loading with hygroscopic and non-hygroscopic particles[END_REF] observed an increase of fibrous filter efficiency with an increase of air humidity during the collection of aluminum particles in the size range of 0.8 -6 µm.

In the literature, the influence of humidity on aerosol filtration was mainly investigated with fibrous filters of HVAC systems in flat or pleat geometries. We inventoried no study about the influence of humidity on bag filter performance during clogging with submicronic particles at the operating conditions found in flue gas treatment of waste incineration plants i.e. high temperature of 150 °C and high absolute humidity of around 73 g of water vapor /m 3 of air (i.e. 3% RH).

This study focuses on the influence of air humidity on the filtration performance of a bag filter at the beginning of the filter lifetime before stabilizing the residual filter pressure drop resulting from previous filtration cycles. The study aims to investigate the influence of air humidity on experimental pressure drop evolution, particle collection efficiency and cake detachment.

Material and methods

Experimental set-up

To investigate the evolution of pressure drop and filtration efficiency of a pulse-jet bag filter, an experimental set-up was developed and described by [START_REF] Boudhan | Pulse-jet bag filter performances for treatment of submicronic and nanosized particles from waste incineration[END_REF], so as to be representative of the bag filter unit in flue gas treatment of waste incineration in terms of temperature, humidity, filtration velocity, aerosol size distribution and load, and the on-line pulse-jet unclogging system.

To study the influence of air humidity on the filtration performance, the set-up operated at two conditions, namely (150 °C -0% RH), and (150 °C -3% RH), i.e. absolute humidity of 0 and about 73 g/m 3 AH, with a filtration velocity of 1.9 cm s -1 and 10 successive clogging/unclogging cycles. For high temperatures, relative humidity is not the most relevant parameter to illustrate the quantity of water vapor in the air, which is why we used absolute humidity (AH) giving the water vapor in the air, regardless of temperature and expressed in mass of water vapor per cubic meter of air (g/m 3 ).

The experimental set-up is illustrated in Fig. 1. In particular, in area 2, the air is heated up to 80 °C and moistened by steam countercurrent injection (steam generator semiautomatic NEMO 1.6 kW). The RH of air is measured with a capacitive hygrometer. In area 3 the air temperature is up to 150 °C. The pulse-jet cleaning of the bag is ensured by short pulses of compressed air (0.3 s at 6 bar). A filter pressure drop controller which manually triggers the cleaning operation once the maximum pressure drop is reached, set at 150 Pa for this study.

Aerosol

A non-hygroscopic carbon aerosol, representative of the particle size and concentration in flue gas of waste incineration plants, was generated upstream of the bag filter from DNP-2000 generator (Palas) with carbon electrodes. The applied discharge at high temperature between carbon graphite electrodes leads to the evaporation of carbon producing high number concentration of nanosized particles (primary particles of 3-10 nm) which coagulate to produce agglomerates. The size of the agglomerates increases with increasing spark frequency. The particle size distribution and numerical concentration of the aerosol during the tests were determined by adjusting the generator characteristics to be representative of particle emission from carbon nanowaste incineration in a lab-scale furnace described by Le [START_REF] Le Bihan | Characterization and reduction of particulate emissions from the incineration of wastes containing engineered nanomaterials144 (Final report of the NanoFlueGas ADEME Project[END_REF]. The particle size distribution of the carbon particles expressed in number, determined by SMPS (Grimm) measurements upstream of the bag filter for the two operating conditions studied, are presented in Fig. 2. The particle concentration, median diameter and geometric standard deviation of the distributions are summarized in Table 1. The morphology of the carbon nanoparticles, sampled with a glassfiber filter, was identified from SEM observations. The results in the Fig. 3 confirm that the carbon particles are generated as agglomerates from the DNP-2000 (Palas) generator.

Tested filter

The tested bag filter, supplied by Trédi, was dismantled from the industrial bag filter unit of a waste incineration plant. The tested bag filter was a used filter with residual particles inside. It was received with a height of 5 m and reduced to 0.44 m for the experimental set-up in the laboratory with a diameter of 0.15 m. The filter media is a non-woven structure composed of Teflon fibers (Polytetrafluoroethylene, PTFE). The main structural parameters of the filter are: thickness of 1256 ± 31 µm, fiber median diameter

Table 1

Particle concentration, particle median diameter and geometric standard deviation for the two operating conditions.

Filter particle collection efficiency

Filter efficiency was calculated from particle sampling and counting with SMPS (Grimm) in the set-up. VKL diluter was implemented before the SMPS particle counter, to decrease temperature and humidity of the air.

In order to avoid a systematic error of calculated filtration efficiency of the bag filter, we considered the large number of particles deposited on the walls of the filter holder. Thus, the results were expressed with the fractional efficiency determined as:

= - E (t) N ̅ N ( t ) N ̅ d upstream,d downstream,d upstream,d p p p p
With N downstream,dp the number of particles of diameter d p measured downstream of the tested filter whose value varies as a function of filtration time.

N ̅ upstream,dp is a constant value (for given temperature and humidity conditions) pre-determined before the filtration tests and representing the upstream number of particles of diameter d p determined from particle counting in the experimental set-up without bag filter at the downstream filter particle sampling location.

Error bars efficiency were calculated considering = × ΔN 5 % N downstream downstream the accuracy of the SPMS for single particle counting. As N upstream,dp is a constant value (for a given d p ) determined from preliminary experiments, ΔN upstream,dp is obtained from the experimental uncertainty of the particle counting measured for 6 samplings carried out.

Results

Influence of humidity on filter airflow resistance

3.1.1. Evolution of bag filter pressure drop Fig. 4 shows the evolution of bag filter pressure drop with filtration time at the two operating conditions studied: (150 °C -0 g/m 3 AH) and (150 °C -73 g/m 3 AH). The results reveal that the pressure drop evolution is influenced by the content of humidity in the air which influences, in turn, the total filtration time per 10 filtration cycles: 1850 min for a bag filter clogged at 73 g/m 3 AH against 5000 min at 0 g/m 3 AH. For both filtration conditions, the duration of the clogging phase decreases gradually with the number of clogging/unclogging cycles.

For the first filtration cycle, the evolution of the filter pressure drop can be assumed from the model of [START_REF] Novick | The effect of solid particle mass loading on the pressure drop of HEPA filters[END_REF] where the pressure drop across the filter results from the pressure drop across the clean filter ΔP 0 and the pressure drop across the cake ΔP cake (assuming that the particle deposit inside the filter has a negligible air resistance).

= + ΔP ΔP ΔP 0 c a k e
Moreover, assuming that the porosity of the particle deposit is constant and independent of the cake thickness, the pressure drop across the filter during clogging is expressed by:

= • • • V K ΔP w µ f c cake
With the specific cake resistance K c (m kg -1 ), the areal collected particle mass w (kg m -2 ), the gas viscosity µ (Pa s), and the filtration velocity V f (m s -1 ).

Thus, the ratio

- • V (ΔP ΔP )/(µ ) f 0
corresponds to the cake resistance to air flow independently of the air viscosity variations with water content.

Fig. 5 compares the evolution of cake resistance

- • V (ΔP ΔP )/(µ ) f 0
in relation to the number of particles collected by the filter during the first filtration cycle at 150 °C for dry (0 g/m 3 AH) and humid conditions (73 g/m 3 AH). The results indicate a higher increase of cake resistance with particle loading in presence of water vapor in air, suggesting an influence of water content on the structural properties of the particle cake. At the maximum value of particulate cake resistance (3.25 × 10 8 m -1 ), the number of particles collected by the filter is significantly higher in dry air (0 g/m 3 AH) as compared to 73 g/m 3 AH, respectively 2.5 × 10 15 and 7.0 × 10 14 particles. Hence, a significant effect of absolute humidity was observed on the evolution of particulate cake resistance in the two conditions studied despite close relative humidity rates (3% vs. 0% RH).

These results differ from the conclusions of [START_REF] Gupta | Effect of humidity and particle hygroscopicity on the mass loading capacity of high efficiency particulate air (HEPA) filter[END_REF] and [START_REF] Joubert | Influence of humidity on clogging of flat and pleated HEPA filters[END_REF] regarding the influence of air water content on the evolution of particulate cake resistance during clogging. We assume that the opposite conclusions come from the filtration conditions in terms of temperature (150 °C), humidity, and also aerosol nature and size: the particles should have a good affinity with water molecules for surface interactions considering the high absolute humidity in the present study and the small size of particles (16-310 nm) i.e. high specific surface area of particles which increases their ability of water sorption.

Influence of air humidity on pulse-jet cleaning of the bag filter

The influence of air humidity on pulse-jet cleaning efficiency of the bag filter is studied in Fig. 6 with the evolution of the residual particulate cake resistance according to the filtration cycles for the two experimental conditions (150 °C -73 g/m 3 AH) and (150 °C -0 g/m 3 AH). The ratio

- • V (ΔP ΔP )/µ f res 0
at the beginning of each clogging/unclogging cycle is calculated from the residual pressure Fig. 5. Evolution of particulate cake resistance as a function of collected particle number during first filtration cycles at (150 °C -73 g/m 3 AH) and (150 °C -0 g/m 3 AH).

drop (ΔP res ) resulting from the overall pressure drop across the filter media (ΔP 0 ) and the residual cake remaining on the filter surface after pulse-jet cleaning.

The results indicated in Fig. 4 that the residual pressure drop of the bag filter ΔP res as a function of filtration cycles at 73 and 0 g/ m 3 AH increases respectively from 22 to 111 Pa and from 19 to 87 Pa between cycle 1 and cycle 10. Thus, Fig. 6 confirms that the increase of residual particulate cake resistance with clogging/unclogging cycles is higher in wet conditions of clogging than for dry air, which means that the pulse-jet cleaning system implemented in the study is more efficient to remove the cake formed in dry conditions on the surface of the bag filter.

In fact, the deposited particles on the filter surface are subject to different forces applied by reverse air flow during the unclogging phase, mainly the pressure forces such as pressure-gradient forces and friction forces. We assume that the presence of water on the surface of the particles by capillary condensation leads to the formation of liquid bridges between them [START_REF] Feng | Effect of liquid addition on the packing of mono-sized coarse spheres[END_REF] and therefore to a capillary condensation at the meniscus of pore size formed by two or more neighboring particles which increases the particle-particle adhesion forces. Consequently, the cake becomes more resistant to the forces applied by air flow and cake removal with the pulse-jet method becomes more difficult. Moreover, the humidity may also influence the particles penetrating in-depth the fibrous filter by increasing the particle-fiber adhesion forces.

Discussion of the results

The presence of humidity between two neighboring solid surfaces causes an attractive force called the capillary force [START_REF] Butt | Normal capillary forces[END_REF]. This adhesion force may lead to an agglomeration of particles when flowing in a gas at high particle concentration and reduce the distance between particles when deposited on the filter surface and lead to the formation of a compact particulate cake on the surface media. Hence, this can explain the faster increase of pressure drop with clogging in humid air conditions compared with dry gas. SEM observations of carbon nanoparticles generated at 150 °C -0 g/m 3 AH and 150 °C -73 g/m 3 AH were performed from sampling with glassfiber filters to illustrate the effect of humidity on the particle deposit (Fig. 7).

Two solid spheres of rough surface get connected by the capillary bridges formed in between surface asperities. The surface asperities can strongly influence the capillary forces between the two particles. [START_REF] Butt | Normal capillary forces[END_REF] distinguished three regimes Fig. 6. Evolution of residual particulate cake resistance at the beginning of each filtration cycle at (150 °C -73 g/m 3 AH) and (150 °C -0 g/m 3 AH). -At low vapor pressure, capillary bridges are few between the two solid surfaces. The capillary force is low due to the small curvature radius formed. -At intermediate vapor pressure, the amount of capillary bridges formed between the asperities of the two solid surfaces is higher.

-At high vapor pressure, the number of capillary bridges between asperities increases and they interact with each other to form a continuous capillary bridge.

The capillary forces can depend sensitively on the shape of the contact. As the surface structure of the collected particles, formed at the dry and humid cases, are different (Fig. 7), the capillary condensation should be more rely on absolute humidity or vapor pressure rather than the relative humidity.

In terms of comparison, the experimental results of filtration were also investigated at room conditions (24 °C, 45% RH, 10 g/m 3 AH) as an intermediate value of humidity. In Table 2, the water vapor pressure and absolute humidity are reported for the experimental filtration conditions of (150 °C, 3% RH, 73 g/m 3 AH), and (150 °C, 0% RH, 0 g/m 3 AH) and the room conditions.

The water vapor pressure increases with increase of absolute humidity, so that for 150 °C -73 g/m 3 AH, the vapor pressure is 10 times higher than at (24 °C -10 g/m 3 AH) increasing the formation of capillary condensation and capillary bridges between the deposited particles. Thus, we assume that in presence of humidity, capillary condensation leads to a decrease in the particulate cake porosity and thus to an increase of the filter resistance to airflow. This hypothesis is in accordance with Fig. 8 reporting the evolution of particulate cake resistance during 10 clogging/unclogging cycles at the three tested conditions (150 °C -73 g/m 3 AH; 150 °C -0 g/ m 3 AH; and 24 °C -10 g/m 3 AH). The evolution of particulate cake resistance to air flow with filtration time is higher at (150 °C -73 g/m 3 AH) than (24 °C -10 g/m 3 AH).

Further explanation of cake resistance increase at the humid conditions can be enhanced from the SEM observation (Fig. 7), the images show the fluffy nature of generated particles, capillarily-condensed water may have enough surface tension to break the particle microstructure and cause collapse and coalescence of the structure.

Influence of air humidity on particle collection efficiency

The evolution of fractional efficiency of the bag filter at different values of pressure drop during the first filtration cycle at 150 °C in dry (0 g/m 3 AH) and humid (73 g/m 3 AH) conditions is reported Fig. 9. The three main conclusions are: (1) the most penetrating particle size is 80 ± 10 nm; (2) the fractional efficiency is lower in humid conditions as compared to dry one whatever the particle diameter is (in the studied range) for a given level of filter pressure drop, with minimum efficiency of 96.7% ± 1% for humid conditions (73 g/m 3 AH) against 98.5% ± 0.5% for dry conditions (0 g/m 3 AH); (3) For the two hygrometry conditions, the increase of fractional efficiency with the increase of filter pressure drop is clearly observed whatever the particle diameter is.

The influence of humidity regarding fractional efficiency can be explained by the number of collected particles in the two Fig. 8. Evolution of particulate cake resistance during 10 clogging/unclogging cycles at (150 °C -73 g/m 3 AH) and (150 °C -0 g/m 3 AH) and room conditions (24 °C -10 g/m 3 AH). operating conditions. For example, at filter pressure drop of ΔP = 50 Pa, the number of collected particles at 73 g/m 3 AH is 1.0 × 10 14 against 4 × 10 14 at 0 g/m 3 AH. As the particles deposited on the filter surface contribute to collection efficiency, this can explain the results in Fig. 9. The evolution of fractional efficiency for the same number of collected particles, in humid (73 g/m 3 AH) and dry (0 g/m 3 AH) conditions, is plotted in Fig. 10. The results indicate two ranges of particle diameter: particle size range between 16 and 100 nm with no significant influence of humidity in fractional efficiency observed; submicron particles higher than 110 nm in diameter with higher filtration efficiency reported at high humidity conditions (73 g/m 3 AH) compared with dry air (0 g/m 3 AH), for collected particle numbers equal to 1.0 × 10 14 and 3.5 × 10 14 (i.e. beginning of clogging).

Note that the cake structural properties are different in the case of humid and dry gas, which certainly lead to a different contribution of particle cake to particle capture efficiency once the filter surface is sufficiently charged.

Discussion of the results

For particles with a diameter above 110 nm, their collection is dominated by the inertia impaction mechanism. We assume that the capillary force leads to increase the adhesion forces between the aggregates and to decrease in particular the distance between them during their transportation in the gas flow (as observed in Fig. 2) of particle size distribution upstream of bag filter: for particles with a diameter higher than 100 nm, there is a slight increase of concentration at (150 °C -73 g/m 3 AH) in comparison to (150 °C -0 g/m 3 AH) probably due to the formation of clusters of aggregates. Thus, we assume that particle density, which is a key parameter affecting the particle collection by inertial impaction mechanism, is influenced by capillary condensation. Indeed, due to their high inertia, the heavier particles tend not to follow the deviation of the streamline of the carrier gas where they get close to the collector, which leads them to touch the latter and be captured [START_REF] Ramskill | The inertial mechanism in the mechanical filtration of aerosols[END_REF]. Thus, by increasing the particle density, the presence of water vapor in air increases the particle collection efficiency by an impaction mechanism with non-hygroscopic carbon particles.

The results of this study are consistent with the literature findings [START_REF] Kim | Filtration efficiency of a fibrous filter for nanoparticles[END_REF][START_REF] Miguel | Effect of air humidity on the evolution of permeability and performance of a fibrous filter during loading with hygroscopic and non-hygroscopic particles[END_REF] regarding the influence of humidity on fiber filter efficiency on the two particle size ranges.

Conclusion

The experimental results showed that the presence of water vapor in the treated gas has a significant influence on bag filter performance at 150 °C even for low relative humidity (3%) demonstrating that absolute humidity is a more relevant parameter than relative humidity. The air humidity (in large quantity as tested in this study) may significantly increase the particulate cake resistance to airflow, because of the water capillary condensation leading to the formation of compact particulate cake. Bag cleaning system by pulse-jet is less efficient in the presence of water vapor in gas than with dry gas. For a given number of collected particles, the collection efficiency at 150 °C increases with humidity for particle sizes higher than 110 nm in diameter; the explanation proposed in the study would be the direct consequence of humidity on particle density leading to improve particle collection by inertial impaction mechanism. At the same time, no effect of humidity was observed for nanoparticle collection efficiency (below 100 nm).

To conclude, air humidity increases the efficiency of bag filter particle collection but accelerates the increase of filter pressure drop and reduces the unclogging efficiency leading to an increase of the residual cake which is the major parameter that reduces the lifetime of the bag filter.

Fig. 1 .

 1 Fig. 1. Experimental set-up for bag filter clogging tests (adapted from Boudhan et al. (2017)).

Fig. 2 .

 2 Fig. 2. Particle size distribution of carbon particles upstream of the bag filter for the two operating conditions (150 °C -73 g/m 3 AH) and (150 °C -0 g/m 3 AH).

  , total porosity of 0.64 and basis weight of 750 g m -2 . Note that a new clean filter was also provided by Trédi and used to quantify the initial filter pressure drop ΔP 0 at the temperatures and humidities tested.2.4. Filter performance measurement2.4.1. Filter pressure dropThe evolution of the pressure drop generated by the gas flow through the filter during clogging is measured by a pressure sensor (FCO model 332), with a pressure measuring range of 0-200 Pa and measuring accuracy < 0.5%.

Fig. 3 .

 3 Fig. 3. SEM observations of the carbon nanoparticles generated by the DNP-2000 (Palas).

Fig. 7 .

 7 Fig. 7. SEM observations of carbon nanoparticles generated at a) 150 °C -0 g/m 3 AH and b) 150 °C -73 g/m 3 AH.

Fig. 9 .

 9 Fig. 9. Fractional efficiency of bag filter for different filter pressure drop levels during the first clogging cycle with carbon nanoparticles at (150 °C -73 g/m 3 AH) and (150 °C -0 g/m 3 AH).

Fig. 10 .

 10 Fig. 10. Fractional efficiency of bag filter for different numbers of collected carbon nanoparticles during the first clogging cycle at (150 °C -73 g/m 3 AH) and (150 °C -0 g/m 3 AH).

Table 2

 2 Vapor pressure and absolute humidity at different filtration conditions.

	Operating parameters (T -RH)	Absolute humidity AH (g water vapor / m 3 air)	Water vapor pressure (Pa)
	150 °C -0% RH	0	0
	24 °C -45% RH	10	1347
	150 °C -3% RH	73	14285