Quang-Trung Luu

Olivier Brun

Rachid El-Azouzi

Francesco De Pellegrini

Balakrishna J Prabhu

Cédric Richier
email: cedric.richier@univ-avignon.fr

DCoflow: Deadline-Aware Scheduling Algorithm for Coflows in Datacenter Networks

Keywords: Time-sensitive coflow scheduling, coflow admission control, σ-order, deadline

Datacenter networks routinely support the data transfers of distributed computing frameworks in the form of coflows, i.e., sets of concurrent flows related to a common task. The vast majority of the literature has focused on the problem of scheduling coflows for completion time minimization, i.e., to maximize the average rate at which coflows are dispatched in the network fabric. Modern applications, though, may generate coflows dedicated to online services and missioncritical computing tasks which have to comply with specific completion deadlines. In this paper, we introduce DCoflow, a lightweight deadline-aware scheduler for time-critical coflows in datacenter networks. The algorithm combines an online joint admission control and scheduling logic and returns a σ-order schedule which maximizes the number of coflows that attain their deadlines. Extensive numerical results demonstrate that the proposed solution outperforms existing ones.

I. INTRODUCTION

Modern traffic engineering in datacenter networks is based on the notion of coflow originally defined in [START_REF] Chowdhury | Coflow: A networking abstraction for cluster applications[END_REF]. The interest for this traffic abstraction has originally been motivated by the need to capture the structure of the data exchanges occurring in distributed computing frameworks such as MapReduce or Spark [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF][START_REF] Zaharia | Spark: Cluster computing with working sets[END_REF]. Such software frameworks rely on the so called dataflow computing model for large-scale data processing, i.e., a distributed computing paradigm, where each intermediate computation stage is distributed over a set of nodes and its output is transferred to nodes hosting the next stage. In between two computation stages, such dataflows are producing a set of network flows traversing the datacenter fabric and are abstracted as a coflow. A popular example of such data transfer is the shuffle phase of Hadoop MapReduce [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF].

The customary performance metric for the data transfer phase is the makespan or the weighted coflow completion time (CCT). Minimizing the average CCT is an appropriate goal in order to increase the number of computing jobs dispatched per hour in a datacenter. The weighted CCT minimization has thus been addressed in several works, e.g., [START_REF] Chowdhury | Coflow: A networking abstraction for cluster applications[END_REF][START_REF] Chowdhury | Coflow: A networking abstraction for distributed dataparallel applications[END_REF][START_REF] Shafiee | An improved bound for minimizing the total weighted completion time of coflows in datacenters[END_REF][START_REF] Agarwal | Sincronia: Near-optimal network design for coflows[END_REF]. A decade's research on the problem has shed light on its complexity and several algorithmic solutions have been devised. The problem was proven NP-hard and inapproximable below a factor of 2 by reduction to the job scheduling problem on multiple correlated machines. Near-optimal algorithms with 4-approximation performance bounds have been proposed in the literature [START_REF] Shafiee | An improved bound for minimizing the total weighted completion time of coflows in datacenters[END_REF][START_REF] Agarwal | Sincronia: Near-optimal network design for coflows[END_REF][START_REF] Chowdhury | Near optimal coflow scheduling in networks[END_REF]. However, the context changes radically in the case of time-sensitive jobs, where the data transfer phase may be subject to strict coflow deadlines.

Here, coflow scheduling is typically combined with admission control in order to reduce the number of violations, i.e., the number of coflows to complete after their deadlines. The resulting problem is the coflow deadline satisfaction (CDS) problem introduced in [START_REF] Tseng | Coflow deadline scheduling via network-aware optimization[END_REF]. Each coflow is subject to a completion deadline and the target is to operate joint coflow admission control and scheduling in such a way to maximize the number of admitted coflows which respect their deadlines. This problem is NP-hard as well and it is proved inapproximable within any constant factor from the optimum [START_REF] Tseng | Coflow deadline scheduling via network-aware optimization[END_REF].

Even though the problem has been identified quite early in the literature [START_REF] Chowdhury | Efficient Coflow Scheduling with Varys[END_REF], with a few exceptions, the vast majority of works on coflow scheduling have not dealt with the problem of time-sensitive coflows. On the other hand, as confirmed later in our performance analysis, even near-optimal algorithms for CCT minimization may fail to respect the coflow deadline. In reality, the notion of time-sensitive coflows has become pervasive in the way how modern datacenters operate as distributed networks. In fact, not only computing frameworks are often tasked with time-sensitive jobs: modern web and mobile applications are implemented using microservice architectures, so that the users requests issued to an application may activate hundreds or thousands of services from as many servers to retrieve the users data. The last incoming bit of data, i.e., the CCT of this batch of flows, determines the lag to the service response, and large delays degrade the quality of experience.

In this paper, we address the problem of maximizing the Coflow Acceptance Rate (CAR), in which each coflow is subject to a completion time deadline. In principle, one can solve this problem by formulating a suitable Mixed Integer Linear Program (MILP). However, in datacenters with tens of thousands of coflows [START_REF] Chowdhury | Coflow: A networking abstraction for distributed dataparallel applications[END_REF], techniques based on MILPs or their relaxations may be not viable. For designing scalable algorithms, the main idea appearing in many research works is to schedule coflows using a priority order of coflows. Once an ordering, denoted as σ, is determined, it is enough to adopt a work-conserving transmission policy. We focus on σ-order schedulers since they offer a key implementation advantage: at the level of rate control, any work conserving preemptive dynamic rate allocation is allowed as long as it is compatible with the input coflow priority (the maximal performance loss within said rate allocation policies is bounded by a factor of 2 [START_REF] Agarwal | Sincronia: Near-optimal network design for coflows[END_REF]). For instance, using fixed coflow priorities under DiffServ satisfies the definition of a σ-order scheduler. On the other hand, in order to avoid per-flow rate control, commercial switches have built-in priority queues and per-flow tagging can be used to prioritize active coflows. In principle, this permits to perform a greedy rate allocation which is compatible with a target σ-order. The exact mapping from a coflow σ-order to the switch priority queuing mechanism (and the inevitable limitations of legacy hardware therein) while an interesting subject, is out of the scope of the present paper.

Contributions. This paper proposes a lightweight method to perform coflow scheduling under deadlines. The proposed solution provably outperforms existing ones in the literature and does not rely on the solution of a linear program.

In particular, we propose first a baseline offline admission control policy which is combined with a scheduler drawn in the class of σ-order coflow schedulers [START_REF] Agarwal | Sincronia: Near-optimal network design for coflows[END_REF]. The output of the algorithm is an order of priority restricted to the set of admitted coflows. The algorithm is hence extended to perform joint admission control and scheduling in the online scenario, when coflows are generated at runtime at unknown release times. Through extensive numerical experiments on a wide variety of scenarios, we show that our algorithm systematically outperforms the ones currently available in the literature. These experiments are performed on both offline and online setting using both synthetic traces and real traces obtained from the Facebook data [START_REF] Chowdhury | Efficient Coflow Scheduling with Varys[END_REF]. The main observation is that, under higher workloads (i.e., when the acceptance ratio is lower), our algorithm outperforms significantly the existing ones. Thus, it proves robust to workload variations as well to the type of data set used to generate the coflows.

The rest of the paper is organized as follows. Sec. II describes the general problem tackled in the paper and the coflow ordering models, whereas Sec. III describes the proposed algorithms. Numerical results are then provided in Sec. IV. In Sec. V, we describe the literature on deadline-aware coflow scheduling. Concluding remarks and future research directions are given in Sec. VI.

II. PROBLEM STATEMENT AND THEORETICAL ANALYSIS

In this section, we present the system model and formulate the acceptance rate maximization problem for a given input set of coflows. Table I summarizes the main notations used throughout the paper. The datacenter network (or datacenter fabric) is represented as a Big-Switch model [START_REF] Chowdhury | Efficient Coflow Scheduling with Varys[END_REF], a nonblocking switch whose ingress (egress) port has capacity B equal to the corresponding bandwidth inbound (outbound) capacity to connect servers to the top-of-rack (ToR) switch. Due to large bisection capacity and customary usage of load balancing, in fact, traffic congestion is typically observed only at the rack access ports leading to the ToR switches.

We consider a batch of N coflows C = {1, 2, ..., N }. A coflow is a collection of flows, in which each flow represents a shuffle connection over a pair of fabric ingress-egress ports. Denote F k as the set of flows of coflow k ∈ C and assume that the volume v k,j of each flow j ∈ F k is known. For the sake of clarity, we suppose that all coflows arrive at the same time, i.e., their release time is zero. Also, each coflow k is subject to a completion deadline T k . Similarly, we let F ,k be the set of flows in F k which uses port ∈ L either as ingress port or as egress port. The total volume of data sent by coflow k on port is then given by v ,k = j∈F ,k v k,j . Let p ,k be the transfer completion time in isolation, i.e., at full rate, of coflow k at port , which is given by p ,k = v ,k /B . Let r k,j (t) ∈ R + be the rate allocated to flow j ∈ F k at time t. The CCT of coflow k, denoted as c k , thus writes

c k = max j∈F k v k,j rk,j
, where rk,j = 1

CT k,j CT k,j 0 r k,j (t) dt, (1)
and rk,j is the average rate of flow j through its lifetime and CT k,j is its completion time. This quantity rules the dispatching time for the volume traversing the so-called coflow bottleneck which determines the CCT of the said coflow. Hence a coflow k satisfies the deadline when the last flow of the coflow finishes before T k , i.e., c k ≤ T k . Let z k ∈ {0, 1} be an indicator of whether coflow k finishes before T k . Maximizing the number of coflows meeting their deadline corresponds to maximizing the sum of z k subject to the constraint of bandwidth capacity at ingress and egress ports. The CAR maximization problem can be formulated as

max r k∈C z k (P1) s.t. k∈C j∈F k,l r k,j (t) ≤ B , ∀ ∈ L, ∀t ∈ T , (2)
T k 0 r k,j (t) dt ≥ v k,j z k , ∀j ∈ F k , ∀k ∈ C, (3)
Constraint [START_REF] Dean | MapReduce: Simplified data processing on large clusters[END_REF] expresses that, at any instant t within the time horizon T , the total rate that port assigns to flows cannot exceed its capacity B . Constraint [START_REF] Zaharia | Spark: Cluster computing with working sets[END_REF] ensures that the data of flows of each accepted coflow k should be completely transmitted before the deadline T k .

Lemma 1 (Proposition 1 in [START_REF] Tseng | Coflow deadline scheduling via network-aware optimization[END_REF]). There exists a polynomial time reduction of the CAR problem (P1) to the problem of minimizing the number of late jobs in a concurrent open shop [START_REF] Lin | Customer order scheduling to minimize the number of late jobs[END_REF]. Hence, the CAR problem is NP-hard.

A. Motivating Example

We will take CS-MHA [START_REF] Luo | Decentralized deadline-aware coflow scheduling for datacenter networks[END_REF] as our starting point to address the CAR problem. CS-MHA has introduced a new direction to solve the scheduling problem by means of a static coflow prioritisation. The prioritisation is used in order to approximate the solution of the coflow scheduling problem that maximizes the CAR. CS-MHA computes the scheduling orders at each port using the Moore-Hodgon's algorithm which also determines the set of admitted coflows at each port ∈ L. Since different ports could have different sets of admitted coflows, a coflow is

, • • • , σ N -1 , σ N } T k deadline of coflow k F k (F ,k ) set of flows of coflow k (that use port ) v k,j volume of flow j ∈ F k of coflow k v ,k
total volume transmitted by coflow k on port p ,k processing time of coflow k on port c k (c ,k ) completion time of coflow k on port CT k,j completion time of flow j of coflow k admitted if it is admitted at all ports. For all rejected coflows, a second round is applied to check if some rejected coflows can actually satisfy their deadline. The algorithm selects a coflow with the minimum bandwidth required at the bottleneck port since it is more likely to catch up with its deadline.

The simple example depicted in Fig. 1 illustrates the limitations of CS-MHA. It uses the standard Big-Switch model to abstract a datacenter fabric: the example will be used as a running example throughout the paper. The instance contains 5 coflows: C 1 has 4 flows and C 2 , C 3 , C 4 and C 5 each have one flow. To ease the presentation, the flows are organised in virtual output queues at the ingress ports. The virtual queue index represents the flow output port, modulo the number of machines. The numbers on the flows' representations correspond to their normalized volumes. All fabric ports have the same normalized bandwidth of 1. At the first iteration, CS-MHA computes the scheduling order on each port using Moore-Hodgson algorithm [START_REF] Moore | An n job, one machine sequencing algorithm for minimizing the number of late jobs[END_REF], which is based on the Earliest Due Date rule and is known to minimize the number of missed deadlines on a single machine (or port in the coflow context). Since coflow C 1 uses all ports and has the smallest deadline (T 1 = 1), then at each port, C 1 will be scheduled first. As consequence, all other coflows are rejected since they cannot satisfy their deadline when scheduled after C 1 . Given that coflow scheduling, the CAR is 1 5 . However, an optimal scheduling solution would be {C 2 , C 3 , C 4 , C 5 , C 1 } or any combination that has coflow C 1 as the last one to be scheduled. The latter scheduler attains a CAR of 4 5 . From this example, we can see that CS-MHA can be made arbitrarily worse compared to the optimal solution.

The above example can easily be extended to show that in the worst-case scenario, the CAR of CS-MHA can be made arbitrarily small (as close to 0 as needed). Consider M machines, coflow C 1 that uses all ports, and coflows C 2 , . . . , C M with one flow each. The other parameters remain the same as above. It can be seen that the CAR obtained using CS-MHA and DCoflow are 1 M , M -1 M , respectively. In this setting, the CAR obtained using CS-MHA is close to zero when M is high, while using DCoflow, the CAR is close to one.

The key observation is that CS-MHA neglects the impact that a coflow may have on other coflows on multiple ports. Indeed, a coflow causing multiple deadlines to be missed should have lesser priority, even when its deadline is the earliest. When this is neglected, the coflow ordering is misjudged thus degrading the CAR. In this work, we start from this observation and propose a new σ-order scheduler, called DCoflow.

B. Coflow Ordering

Problem (P1) implicitly depends on the CCT. An alternative approach to maximize the CAR is to order the coflows in some appropriate way, and then to leverage the priority forwarding mechanisms of the underlying transport network [START_REF] Agarwal | Sincronia: Near-Optimal Network Design for Coflows[END_REF].

In this approach, once such an ordering σ is determined, it is enough to adopt work-conserving transmission policies and use forwarding priorities in such a way that a flow j ∈ F σ k is blocked if and only if either its ingress or egress port is busy serving a flow j ∈ F σ k for some k < k, i.e., a flow of a coflow with higher priority according to σ. Such a flow scheduling is called σ-order-preserving.

The formulation of Problem (P1) can be transformed into an Integer Linear Program (ILP) as follows. We define the binary variable δ i,k as 1 if coflow i has higher priority than coflow k = i, and 0 otherwise. The ordering of coflows can then be modeled using the following standard disjunctive constraints

δ k,k + δ k ,k = 1, ∀k, k ∈ C, (4)
δ k,k + δ k ,k" + δ k",k ≤ 2, ∀k, k , k" ∈ C. (5)
It should be clear that the ordering σ can easily be derived from the variables {δ k,k } k,k ∈C . This ordering should be such that as many coflows as possible are accepted, that is, i∈C z k is maximized. A central difficulty here is to compute the completion time of a coflow, which stems from the fact that data transmissions on the various ports are not independent: the transmission of a flow may be blocked until the ingress port becomes available even if the egress port is idle, and vice versa. However, assuming that the ports are independent, we can obtain a lower bound on the completion time of coflow k on port as follows

c ,k ≥ k =k p ,k δ k ,k z k + p ,k , ∀ ∈ L, k ∈ C. (6)
This lower bound assumes that the transmission of coflow k on port can start as soon as all flows of all coflows k scheduled before k have been transmitted on port . Note that the above constraint is not linear due to the product δ k ,k z k . However, it can easily be linearized by introducing binary variables y k ,k satisfying the constraints

y k ,k ≤ z k ; y k ,k ≤ δ k ,k ; y k ,k ≥ z k + δ k ,k -1, (7) (6) thus becomes c ,k ≥ k =k p ,k y k ,k + p ,k , ∀ ∈ L, k ∈ C. (8)
A lower bound on the completion time of coflow k is then obtained as c k = max ∈L c ,k , and this coflow can meet its deadline only if c k ≤ T k . The deadline constraint can then be described as

c ,k ≤ T k z k , ∀ ∈ L, k ∈ C. (9)
We can thus obtain an upper bound on the number of accepted coflows by solving the following ILP,

max k∈C z k , s.t. (4, 5, 7, 8, 9). (P2)
It is easy to verify that Problem (P2) is NP-hard and so that it may become unfeasible to find an optimal solution in large-scale datacenter networks. In the next section, we hence propose an efficient heuristic algorithm to determine the order in which coflows must finish in order to maximize the coflow acceptance rate.

III. σ-ORDER SCHEDULING WITH DCoflow

In this section, we present DCoflow, an algorithm to solve the problem of joint coflow admission control and scheduling. Given a list of N coflows, it provides a permutation σ = (σ 1 , σ 2 , .., σ N ) of these coflows, with the aim of maximizing the coflow acceptance rate. We observe that, when a coflow is served according to the corresponding σ-order-preserving schedule, lower-priority coflows will be impacted. It is hence possible that some of these lower-priority coflows will not respect their deadline. Hence our objective is to evaluate the impact of a scheduled coflow with respect to the original CAR problem. The problem is combinatorial in nature, since there are N ! possible coflow orderings. Hence, we propose a new approach that uses the formulation of Problem (P2) by deriving a necessary condition satisfied by all feasible coflow orders solving Problem (P2).

Consider a feasible solution to Problem (P2) and a subset S ⊆ C of coflows. Given a coflow k ∈ C, let S - k = {k ∈ S : δ k ,k = 1} be the set of coflows in S which are scheduled before k. Condition (6) may be rewritten as

c ,k ≥ p ,k + k ∈S - k p ,k z k , (10)
which implies

c ,k p ,k z k ≥ p 2 ,k z 2 k + p ,k z k k ∈S - k p ,k z k . (11)
Using the inequality T k ≥ c ,k z k and summing over all coflows k ∈ S, we obtain

k∈S p ,k T k ≥ k∈S c ,k p ,k z k ≥ k∈S (p ,k z k ) 2 + k∈S,k ∈S - k p ,k p ,k z k z k = 1 2 k∈S (p ,k z k ) 2 + 1 2    k∈S (p ,k z k ) 2 + 2 k∈S p ,k z k k ∈S - k p ,k z k    = 1 2 k∈S (p ,k z k ) 2 + 1 2 k∈S p ,k z k 2 . ( 12
)
We thus conclude that any feasible solution to Problem (P2) satisfies the condition k∈S p ,k T k ≥ f (S) for any subset S ⊆ C of accepted coflows, where

f (S) = 1 2 k∈S p 2 ,k + 1 2
k∈S p ,k 2 . These conditions are the so-called parallel inequalities and provide valid inequalities for the concurrent open shop problem [START_REF] Mastrolilli | Minimizing the sum of weighted completion times in a concurrent open shop[END_REF]. Note that they do not depend on the ordering of the coflows. We shall use the parallel inequalities to determine the coflows that should not be admitted. Consider a solution to Problem (P2) and assume that, in this solution, there exists a subset S of accepted coflows (i.e., z k = 1 for all k ∈ S) such that k∈S p ,k T k < f (S) for at least one port ∈ L. This implies that this solution is not feasible and can only become feasible by rejecting a coflow k among the accepted coflows using port . We choose this coflow k so as to minimize the quantity f (S \ {k }) -k∈S\{k } p ,k T k , in the hope that it becomes negative. Observe that

f (S) =   1 2 p 2 ,k + 1 2 k∈S\{k } p 2 ,k   + 1 2   p k + k∈S\{k } p k   2 = f S \ {k } + p ,k k∈S p ,k , (13)
from which it follows that

f S \ {k } - k∈S\{k } p ,k T k = f (S) - k∈S p ,k T k + p ,k T k - k∈S p ,k (14)
The above relation will be used to define our coflow admission control algorithm. In general, it suggests possible heuristics to remove a coflow k from S in order to satisfy the parallel inequalities. For instance, one such heuristics is to minimize the quantity

Ψ ,k := p ,k T k - k∈S p ,k . (15)
In fact, the term k∈S p ,k -T k represents how much the completion time of coflow k on port exceeds its deadline, assuming that it is scheduled latest. Hence, we could reject coflow k with both large processing time p ,k on port and large deadline violation. More admission rationales based on (14) will be detailed in describing DCoflow, whose pseudocode is reported in Algorithm 1. Generally, DCoflow takes a list of unsorted coflows and provides as output the b is empty (Lines 14-18), i.e., no coflow respects its deadline when scheduled last on the bottleneck (Line 13), the algorithm selects a coflow to be removed using function RejectedCoflow, whose aim is to comply with parallel inequalities according to [START_REF] Mastrolilli | Minimizing the sum of weighted completion times in a concurrent open shop[END_REF]. We consider two variants, each of which corresponds to a slightly different criterion to select the candidate coflow k by taking into account its weight.

23 while σ = ∅ do 24 k ← arg min k {σ k ∈ σ }; first coflow in σ 25 cσ k ← evalCCT {σ k } k∈[1,k ] ; CCT of coflow σ k 26 if cσ k > Tσ k then 27 σ ← σ\ {σ k }; 28 σ ← σ \ {σ k };
The first variant, namely DCoflow v1, finds the candidate k ∈ S b and every port used by k where it fails to meet the deadline (that is,

Ψ ,k < 0), k = arg min k∈S b :Ψ ,k <0 Ψ ,k . (16)
The second variant, namely DCoflow v2, finds the candidate k ∈ S b and every port used by k that has at least γ times the congested level of the bottleneck, i.e., : j p j ≥ γ j p bj , k = arg min

k∈S b : j p j ≥γ j p bj Ψ k . (17)

Unscheduled coflows (set S)

b Ψ 1 , Ψ 2 , Ψ 3 , Ψ 4 , Ψ 5 S = {C 1 , C 2 , C 3 , C 4 , C 5 } 1 {-4 (1 + ε) , -ε, • , • , • } S = {C 2 , C 3 , C 4 , C 5 } 1 { • , 0, • , • , • } S = {C 3 , C 4 , C 5 } 2 { • , • , 0, • , • } S = {C 4 , C 5 } 3 { • , • , • , 0, • } S = {C 5 } 4 { • , • , • , • , 0}
Once the initial scheduling order σ is obtained, DCoflow uses the function RemoveLateCoflows to estimate the CCT and remove from σ the coflows that do not satisfy the deadline constraint (Line 20). Briefly, RemoveLateCoflows considers each pre-rejected coflow k in σ (Line 24). It calls the function evalCCT to evaluate the CCT of k , given all the coflows in σ that are scheduled before k (Line 25). If k cannot meet its deadline, i.e., c σ k > T σ k , it will be removed permanently from σ and σ. RemoveLateCoflows performs a swipe on the admitted coflows (as in [START_REF] Luo | Decentralized deadline-aware coflow scheduling for datacenter networks[END_REF]) and iteratively removes coflows in σ that belong to σ until the estimated

CCT c σ k of each coflow σ k ∈ σ is of at most T σ k .
It is important to note that the final solution yielded by DCoflow does not guarantee all coflows in σ to satisfy their deadlines. In Sec. IV, the prediction error of DCoflow indicates the gap between the estimated CAR and the actual CAR after applying resource allocation.

Example. To illustrate the difference between DCoflow and CS-MHA, we consider again the example illustrated in Fig. 1. Table II shows the execution of DCoflow v1 on that example. At the first step, DCoflow v1 chooses bottleneck ingress port 1, which is used by coflows C 1 and C 2 . It computes Ψ k = :Ψ ,k <0 Ψ ,k for both coflows and selects the coflow with smallest Ψk (in this case, C 1 ) to be scheduled last. Since all unscheduled coflows do not share any port in the fabric, any ordering of remaining coflows gives the same average CAR. Given the final schedule, DCoflow obtains 4 5 as the average CAR, which is the optimal solution. Online Implementation. DCoflow can be also be run online, when coflows arrive sequentially and possibly in batches. For this, define f to be the frequency of updates, i.e., instants at which DCoflow recomputes a schedule. The updates can be performed either at arrival instants of coflows (in which case we set f = ∞) or periodically with period 1/f . We assume that the scheduler knows the volumes of the flows of each arrived coflow. However, it neither knows the volumes nor the release times of future coflows.

At each update instant, DCoflow recomputes the scheduling order for coflows currently available in the network. These include the ones that were scheduled in the previous scheduling instants and have not yet finished; the ones that were rejected in the previous scheduling instants but whose deadline has not yet expired and the arrivals during the update interval. DCoflow calculates the new order for this set of coflows based on the remaining volumes of the flows and not on the original volumes. Note that it is assumed that coflows can be preempted [START_REF] Chowdhury | Coflow: A networking abstraction for distributed dataparallel applications[END_REF]. This process is repeated at each update instant.

Complexity Analysis. The complexity of DCoflow is O(N2 ). Specifically, in DCoflow, the values i∈S p ,i and Ψ ,x of each remaining coflow x can be pre-stored by calculating them at a cost O(N L), where L = |L| is the number of ports. Then these values can be updated at a cost O(L) per coflow at each iteration. The number of operations required at Lines 11-13 is O(N ) and at Lines 15-16 is O(N ), so that finally across iterations it adds to O(N 2 ). On the other hand, it is easy to verify the complexity of RemoveLateCoflows is O(N L).

IV. PERFORMANCE EVALUATION

We evaluate via simulations our proposed heuristics (two variants of DCoflow1 ) along with some existing algorithms such as CS-MHA 2 and the solution provided by the optimization method CDS-LP proposed in [START_REF] Tseng | Coflow deadline scheduling via network-aware optimization[END_REF]. The relaxed version of CDS-LP, named CDS-LPA, is also implemented 3 . By using the solution derived from CDS-LP as an upper bound, we would get the sense of how close the algorithms are to the optimum. A brief description of the reference algorithms has been given in Sec. I. We also compare the performance of our schedulers against Sincronia [START_REF] Agarwal | Sincronia: Near-Optimal Network Design for Coflows[END_REF] and Varys [START_REF] Chowdhury | Efficient Coflow Scheduling with Varys[END_REF] that aim to minimize the average CCT.

Once we obtained the σ-order, the actual coflow resource allocation for our solution is implemented by the greedy rate allocation algorithm GreedyFlowScheduling [START_REF] Agarwal | Sincronia: Near-Optimal Network Design for Coflows[END_REF]. At any given point of time, GreedyFlowScheduling reserves the full port bandwidth to one flow at the time. It does so by complying to the scheduling order in σ of the coflow to which the flow belongs [START_REF] Agarwal | Sincronia: Near-Optimal Network Design for Coflows[END_REF]. We note that, in the case of CDS-LP, CDS-LPA, and Varys, instead, the rate allocation is part of the algorithmic solution.

The network fabric is represented by M machines or end-hosts connected to a non-blocking Big-Switch fabric, of which each access port has a normalized capacity of 1. The algorithms will be evaluated on both small-scale and largescale networks, where a network is denoted by [M, N ] to indicate different fabric size and number of coflows (N ) used in the simulations. Small-scale networks have a fabric of size M = 10, whereas large-scale networks have a fabric with either 50 or 100 machines. The coflows in these networks are generated from both synthetic and real traffic traces.

The MILP solver gurobi is used to solved CDS-LP and CDS-LPA. Due to the high complexity, CDS-LP and CDS-LPA are only evaluated on small-scale networks. In what follows, the detailed setup, comparison metrics, and simulation results are presented.

A. Simulation Setup Synthetic Traffic. The synthetic traffic comprises two types of coflows. Type-1 coflows have only one flow, whereas the number of flows of Type-2 coflows follows a uniform distribution in [2M/3, M ]. Each generated coflow is randomly assigned to either Class 1 or Class 2 with probability of respectively 0.6 and 0.4. Moreover, each coflow k is assigned a random deadline within [CCT 0 k , 2CCT 0 k ]), where CCT 0 k is the completion time of coflow k in isolation. Flows of Class-1 coflows are assigned a random volume of mean of 1 and standard deviation of 0.2. The volume ratio for the flows of Class-1 and Class-2 coflows is 0.8.

Real Traffic. Real traffic datasets are obtained by the Facebook traces dataset [START_REF] Chowdhury | Efficient Coflow Scheduling with Varys[END_REF], based on a MapReduce shuffle trace collected from one of Facebook's 3000-machine cluster with 150 racks. The data traces consist of 526 coflows. It has a skewed coflow width distribution, ranging from coflows with a single flow to very large ones (the largest coflow has 21170 flows). For detailed statistics of the Facebook traces we refer the reader to [START_REF] Chowdhury | Coflow: A networking abstraction for distributed data-parallel applications[END_REF]. For each configuration [M, N ], N coflows are randomly sampled from the Facebook dataset. Coflows are only selected from the ones that have at most M flows. The volume of each flow is given by the dataset.

Metric. We evaluate the algorithms based on the average CAR. We also present the gains in percentiles of each algorithm with respect to the solution yielded by CDS-LP in terms of CAR. These gains are calculated using the formula: average gain in CAR = compared CAR CAR under CDS-LP -1.

B. Results with Offline Setting

In the offline setting, we consider that all coflows arrive at the same time, i.e., their release time is zero. For each simulation with a specific scale of the network and either synthetic or real traffic traces, we randomly generate 100 different instances and compute the average performance of algorithms over 100 runs.

1) Average CAR Under Synthetic Traffic: Figs. 2a-2b show the average CAR with respectively small-scale networks and large-scale networks. The percentile gains of each algorithm with respect to CDS-LP are shown in Fig. 4a, in terms of average CAR for the configuration [START_REF] Lin | Customer order scheduling to minimize the number of late jobs[END_REF]60].

It is observed that our proposed heuristics are closest in terms of CAR to the optimum (CDS-LP) than all other algorithms, with both small-and large-scale networks. Among two variants of DCoflow, DCoflow v1 yields the best performance and even outperforms CDS-LPA, the approximation version of CDS-LP. For instance, on the network [START_REF] Lin | Customer order scheduling to minimize the number of late jobs[END_REF][START_REF] Lin | Customer order scheduling to minimize the number of late jobs[END_REF], DCoflow v1 improves the CAR on average by 6.5%, 11.5%, 15.1%, and 26.6%, compared respectively to CDS-LPA, CS-MHA, Sincronia, and Varys. Interestingly, the improvement becomes higher when the load is increased. For example, the corresponding improvement on average CAR on a [START_REF] Lin | Customer order scheduling to minimize the number of late jobs[END_REF]60] network are 67.2%, 98.3%, 59.9%, and 36.8% (see Fig. 2a). The improvement is even higher when performed on a largescale netork. For example, compared to CS-MHA, Sincronia, and Varys, on the network [100, 400], the improvement in terms of average CAR are respectively 648.1%, 32.3%, and 17.9%. (see Fig. 2b). It is worth noting how the performance of CS-MHA falls drastically when dealing with large-scale networks. This is expected since CS-MHA computes prioritizes coflows that use a large number of ports over those that use a few. In instances with a large number of coflows of the latter type, the CAR of CS-MHA goes to 0 (see detailed explanation with the motivating example in Sec. II-A)

The result in Fig. 4a shows that the two variants of DCoflow achieve a smaller gap to the optimal in almost all values of percentile compared to other algorithms. For instance, compared to Sincronia, DCoflow v1 improves the CAR in 50% of 100 instances by 50% and it achieves around 43% at 99 th percentile.

2) Average CAR Under Real Traffic Traces: This section presents the results obtained with the Facebook traffic traces, using the same configurations as those used in Sec. IV-B1. Figs. 3a-3b show the average CAR with respectively smalland large-scale networks. The gains in percentiles of each algorithm with respect to CDS-LP, in terms of average CAR when using a [START_REF] Lin | Customer order scheduling to minimize the number of late jobs[END_REF]60] fabric are shown in Fig. 4b. Similar to what observed in the results with the synthetic traces (see Sec. IV-B1), DCoflow v1 and DCoflow v2 yield a significant improvement in terms of average CAR compared to other heuristics. For instance, with a [10, 60] configuration, the two variants of DCoflow improve the average CAR on average by 24.4%, 25%, 52.2%, 93.1%, compared respectively to CDS-LPA, CS-MHA, Sincronia, and Varys. (see Fig. 3a). The improvement is even higher when performed on a large-scale network. For example, compared to CS-MHA, Sincronia, and Varys, on [100, 400] network, the improvement in terms of average CAR are respectively 36.6%, 55.3%, and 147.5%.

Moreover, the results in Fig. 4b show that the two variants of DCoflow achieve a smaller gap to the optimal in almost values of percentile compared to the other algorithms. For instance, compared to Sincronia, DCoflow v1 improves the CAR in 57% of 100 instances by 50% and it achieves around 35% at 99 th percentile.

3) Prediction Error of DCoflow: As mentioned at the end of Sec. III, we also evaluate the prediction error (|σ|-|σ|)/|σ| of our heuristics, where σ ⊆ σ is the set of coflows in σ that satisfy the deadline constraint after performing the actual resource allocation using GreedyFlowScheduling. Both variants of DCoflow provide a prediction of CAR with an average error below 3.6% for both traffic traces.

C. Online Setting

We now present a series of numerical results on the performance of the online version of DCoflow. The metric used for the performance evaluation is the average CAR obtained over 40 instances. In each instance, coflows arrive sequentially according to a Poisson process of rate λ, i.e., the inter-arrival time of coflows is exponentially distributed with rate λ. Unless stated otherwise, coflow priorities are computed upon arrival of a new coflow (f = ∞).

As both versions of DCoflow provide similar results, we only present the results obtained with DCoflow v1. The average CAR obtained with DCoflow v1 is compared against those obtained with the online version of Varys with deadline [START_REF] Ma | Chronos: Meeting Coflow Deadlines in Data Center Networks[END_REF], CS-MHA and Sincronia. We investigate the effect of two main parameters: (i) the coflow arrival rate λ and (ii) the frequency f at which coflow priorities are updated.

1) Impact of Arrival Rate: We first study the impact of the arrival rate λ on the CAR obtained with the various algorithms. The CAR is averaged over 40 instances, each one with 4000 coflow arrivals. The deadline of a coflow k is drawn from a uniform distribution in [CCT 0 k , 4CCT 0 k ]. We also consider two scenarios: a small fabric with M = 10 machines, and a large fabric with M = 50 machines. For each scenario, results are presented for the following values of λ: λ = 8, λ = 12, λ = 16, and λ = 20.

Our results are shown in Figs. 5a and5b, for the small fabric scenario and the large one, respectively. We observe that DCoflow v1 achieves a higher average CAR for all values of λ, and that the gain with respect to the other scheduling algorithms increases with the value of λ. If all algorithms achieve more or less the same CAR for a lightly loaded fabric, DCoflow v1 clearly outperforms the other algorithms when the fabric is highly congested.

Figs. 6a and 6b show respectively the average CAR obtained with M = 10 and M = 100, both with 4000 coflows, using the Facebook dataset. Similar to what obtained with the synthetic traffic traces, DCoflow v1 outperforms all other methods with significant gains. When the fabric is highly congested (i.e., with M = 10), again DCoflow v1 yields a higher gain compared to other algorithms. For instance, DCoflow v1 achieves 9.3% higher CAR than Sincronia when M = 100 (see Fig. 6b), while with M = 10, the gap becomes 16.4% (see Fig. 6a).

2) Impact of Update Frequency: We now evaluate the impact of the update frequency f on the average CAR. We consider the following values of f : f = λ 2 , f = λ, f = 2λ, and f = ∞. Recall that f = ∞ means that priorities are updated upon each coflow arrival. We assume that M = 10 and compute the CAR by averaging over 40 instances. For each instance, we simulate 8, 000 coflow arrivals according to a Poisson process at rate λ, assuming that the deadline of a coflow k is uniformly distributed in The results in Fig. 7a are obtained from a simulation, in which each arrival corresponds to one single coflow. We note, as before, that for a low arrival rate, both algorithms provide a similar average CAR (for λ = 2, CS-MHA achieves a slightly higher CAR than DCoflow v1), but that DCoflow v1 clearly outperforms CS-MHA when the fabric is highly congested. We also note that a higher frequency f significantly improves the CAR for both algorithms. For instance, for λ = 2 (resp. λ = 10), the average CAR is increased by 52% (resp. 46%) if we update coflow priorities upon arrival of each new coflow instead of using the periodic scheme with f = λ 2 . These results suggest that there is a need for a trade-off between the computational complexity of updating coflow priorities at a high frequency and the CAR achieved. In Fig. 7b, we present a similar result, but assuming that coflows arrive in batches. The batch size follows a uniform distribution U( [START_REF] Shafiee | An improved bound for minimizing the total weighted completion time of coflows in datacenters[END_REF][START_REF] Chowdhury | Coflow: A networking abstraction for distributed data-parallel applications[END_REF]). Since the average number of coflows in each batch is 10, in this setting, we divide the batch arrival rate by 10 to obtain the same coflow arrival rates as in Fig. 7a. The results obtained for batch arrivals are similar to those obtained previously, but we note that the gains of DCoflow v1 with respect to CS-MHA are significantly higher in this case. Moreover, we note that the benefit of using a higher update frequency is lower in this case (e.g., for λ = 10, the average CAR is increased only by 17% if we use f = ∞ instead of f = λ 2 ).

Average CAR DCoflow v1, f = λ/2 DCoflow v1, f = λ DCoflow v1, f = 2λ DCoflow v1, f = ∞ CS-MHA, f = λ/2 CS-MHA, f = λ CS-MHA, f = 2λ CS-MHA, f = ∞ (a) Without batch. λ = 2 λ = 4 λ = 6 λ = 8 λ = 10 Arrival rate (λ) 0.0 0.2 0.4 0.6 0.8 1.0 Average CAR DCoflow v1, f = λ/2 DCoflow v1, f = λ DCoflow v1, f = 2λ DCoflow v1, f = ∞ CS-MHA, f = λ/2 CS-MHA, f = λ CS-MHA, f = 2λ CS-MHA, f = ∞ (b) With batch.

V. RELATED WORK

As discussed in Sec. I, most works in the literature focus on CCT minimization, and deadline scheduling has received comparatively less attention. Varys [START_REF] Chowdhury | Efficient Coflow Scheduling with Varys[END_REF] was one of the first algorithms for deadline-sensitive coflow scheduling. It uses a cascade of coflow admission control and scheduling. The scheduler strives for CCT minimization combining (i) a coflow ordering heuristic based on the per coflows bottleneck's completion time; and (ii) an allocation algorithm to assign bandwidth to individual flows of each coflow. Rate allocation in Varys is performed to approximately align the completion time of all coflows to the bottleneck one.

Chronos [START_REF] Ma | Chronos: Meeting Coflow Deadlines in Data Center Networks[END_REF] is a heuristic for deadline scheduling which avoids starvation for flows that do not meet their deadlines by granting them the residual bandwidth. A priority order is determined first, and coflows are hence allocated the minimum necessary bandwidth to meet their individual deadlines. Once all the flows that meet their deadlines have been allocated bandwidth, the residual bandwidth is shared by the remaining coflows in proportion to their demands.

In [START_REF] Luo | Decentralized deadline-aware coflow scheduling for datacenter networks[END_REF], a connection between deadline scheduling of coflows and the well-known problem of minimizing late jobs in a concurrent open shop-a known NP-hard problem, is made. A heuristic based on the Moore-Hodgson's algorithm [START_REF] Moore | An n job, one machine sequencing algorithm for minimizing the number of late jobs[END_REF] for a single link is proposed. Both centralized as well as decentralized heuristics are introduced (namely CS-MHA and D 2 -CAS, respectively).

A formal description of the deadline scheduling problem including bandwidth allocation of flows was given in [START_REF] Tseng | Coflow deadline scheduling via network-aware optimization[END_REF]. The CDS maximization problem is formulated as an MILP (called CDS-LP). Time is divided into intervals whose boundaries are the coflow deadlines arranged in increasing order. The program determines which coflows to accept and the amount of bandwidth to allocate in each interval. CDS-LP is shown to be NP-hard, and an approximation based on LP relaxation (called CDS-LPA) of the binary variables is also proposed. CDS-LPA only accepts coflows for which the relaxed variable is strictly equal to 1, i.e., only coflows that are completely accepted by the LP relaxation are retained.

For completeness, we also cite a few works considering the minimization of CCT [4-6, 17, 18] as well as the survey article [START_REF] Wang | A survey of coflow scheduling schemes for data center networks[END_REF]. Popular among CCT minimization algorithms is Sincronia proposed in [START_REF] Agarwal | Sincronia: Near-Optimal Network Design for Coflows[END_REF]. It considers scheduling on the network bottlenecks and returns a scheduling coflow order achieving a 4-approximation factor.

VI. CONCLUSION AND FUTURE WORK

In this paper, we introduced a new joint coflow admission control and scheduling algorithm for a batch of coflows with deadlines. The proposed schemes leverage results from openshop scheduling to determine a subset of coflows to schedule and a corresponding σ-order which is then employed in order to schedule coflows in priority.

Numerical results show that on small-scale networks, our algorithms perform similar to or better than other deadlinesensitive algorithms proposed in the literature. On large-scale networks, however, it shows significant improvements with respect to existing algorithms, e.g., 98% higher CAR than CS-MHA in an offline setting. Our scheme also has a low prediction error: even though the admission control is performed using a bottleneck approximation for the CCT, almost all accepted coflows actually finish within their deadline when being actually scheduled. This behaviour is observed in both offline and online settings, both with synthetic traces and for real traces from the Facebook data set. This shows that the algorithm is robust with respect to the coflow size distribution and performs very well across a wide range of network sizes.

Several extensions of this research line are possible. In future works, we shall study the performance of our online solution in the case when coflows tend to be released in batches, e.g., when a distributed framework polls worker nodes with given period. Furthermore, a relevant case is that of incomplete information on flow volumes, i.e., because the volume of a flow is not directly available to the scheduler but only, for instance, via some a priori distribution. Finally, issues of starvation and fairness issue among coflows represent interesting issues we have not addressed yet.

Fig. 1 .

 1 Fig. 1. Motivating example with a Big-Switch fabric composed of 4 ingress/egress ports connecting to 4 machines. Flows in ingress ports are organized by destinations and are color-coded by coflows. The example has 5 coflows. Coflow C 1 (blue) has 4 flows, with each ingress port sending 1 units of data to one egress port: its deadline is 1; coflows C 2 (green), C 3 (red), C 4 (orange) and C 5 (purple) have a single flow, each sending (1 + ε) unit of data. The deadline of these coflows is 2.

Algorithm 1 : 6 b 7 S 8 # 10 if S d b = ∅ then 11 kn = arg max k∈C T k ; admit coflow with largest deadline 12 σn = kn; append kn to σ 13 S 15 k 16 σn = k ; append k to σ; 17 σ = σ ∪ {k }; append k to σ 18 S 19 n = n - 1 ;

 16781011121315161718191 DCoflow 1 S = {1, 2, . . . , N }; initial set of unscheduled coflows 2 σ = ∅; initial scheduling order 3 σ = ∅; initial set of pre-rejected coflows 4 n = N ; round counter 5 while S = ∅ do = arg max ∈L k∈S p ,k ; bottleneck port b = k ∈ S : p b ,k > 0 ; set of coflows using b Coflows that can finish in time when scheduled last 9 S d b ← {j ∈ S b | k∈S b p b ,k ≤ T j }; = S \ {kn}; remove kn from S 14 else = RejectedCoflow(S); select a coflow to reject = S\ {k }; remove k from S update the round index 20 σ = RemoveLateCoflows (σ, σ ); 21 return σ; final scheduling order 22 Function RemoveLateCoflows(σ, σ ):

  scheduling order of accepted coflows. It works in rounds and at each round, it either accepts a coflow or it rejects one. DCoflow starts by computing the total completion time at each port and finds the bottleneck b , i.e., the port with the largest completion time. Having this, it determines S d b the set of coflows active on the bottleneck port b (line 8) which complete before their deadline if scheduled last on b . If S d b is not empty (Lines 10-13), it selects a coflow k n ∈ S d b that has the largest deadline in S d b . If S d

  Synthetic traffic traces on a small-scale network. Synthetic traffic traces on a large-scale network.

Fig. 2 .

 2 Fig. 2. Average CAR with synthetic traffic traces using (a) small-scale and (b) large-scale networks. Each point in the x-axis represents the network [M, N ].

  Facebook traffic traces on a small-scale network. Facebook traffic traces on a large-scale network.

Fig. 3 .

 3 Fig. 3. Average CAR with Facebook traces using (a) small-scale network and (b) large-scale network. Each point in the x-axis represents network [M, N ].

Fig. 4 .

 4 Fig. 4. The 1 st -10 th -50 th -90 th -99 th percentiles of the average gain in CAR with small-scale network [10, 60] using (a) synthetic and (b) Facebook traces.

Fig. 5 .

 5 Fig. 5. Average CAR using synthetic traffic with varying λ and (a) M = 10 and (b) M = 50.

  [CCT 0 k , 2CCT 0 k ]. We present the average CAR obtained for different values of f (f ∈ { λ 2 , λ, 2λ, ∞}) and for different values of the arrival

Fig. 6 .

 6 Fig. 6. Average CAR using Facebook traffic with varying λ and (a) M = 10 and (b) M = 100.

Fig. 7 .

 7 Fig. 7. Average CAR of DCoflow v1 and CS-MHA using synthetic traffic with [10, 8000] and varying λ, when obtaining (a) one single coflow per arrival; and (b) a random batch of coflow per arrival.

TABLE II EXECUTION

 II OF DCoflow ON THE EXAMPLE OF FIG. 1.

The flow-level simulator and the implementation of all algorithms tested in this paper are available at https://github.com/luuquangtrung/CoflowSimulator.

We only reimplemented the centralized algorithm (CS-MHA) presented in[START_REF] Luo | Decentralized deadline-aware coflow scheduling for datacenter networks[END_REF], which has been reported to be better than the decentralized version (D 2 -CAS) in terms of CAR.

It is worth noting that the formulation of CDS-LP and CDS-LPA use the same decision variables {z k } k∈C as those introduced in Problem (P1). In CDS-LP, z k are binaries, whereas in CDS-LPA, z k are continuous variables taking values in [0, 1]. For any solution yielded by CDS-LPA, only coflows k whose z k strictly equals 1 are considered as accepted ones.


P.-E Vidal

J.-M Dienot

F Rotella

I Sakhraoui

B Trajin

E Woirgard

G Bayle

S Behar

P Lasserre

Embedded set of sensors for power electronic modules

Keywords:

This study deals with the challenges for driving Wide Band Gap modules to maturity. In this study, development, integration and signal processing techniques of several types of sensors are studied. Industrial and academic partners, within CAPTIF project, are proposing complementary skills and experiences in the technological and scientific domains: multi-physic sensors, signal processing, integration and reliability for power electronics. Nanoparticle-based strain gauges, temperature sensors and electromagnetic array sensors will be validated and integrated in power an electronic power module. A specific multi-physic model will be developed in order to specify the best location of interest within the power module. These features will result in a better knowledge of real-time current density location, as well as current frequencies. For both sensor types, the data packaging will be challenging spin-offs. Finally, advanced data processing techniquesestimation as well as signal processingwill be adapted to numerous sensor outputs. A clean room process flowchart will be established to guarantee an advanced pre-industrial prototyping.

Introduction

The joint emergence of Wide Band Gap materials (SiC, GaN, C) and new generation hybrid integration techniques significantly enhance performances of power electronic modules. Such modules should operate in severe environment and constraints: high temperature high power density, fast switching, etc. The challenges for driving these new modules are about developing, integration and signal processing techniques of several types of sensors. Industrial and academic partners, within CAPTIF project, are proposing complementary skills and experiences in the technological and scientific domains. Indeed, multi-physic sensors, signal processing, integration and reliability for power electronics are the main themes studied. The dedicated multi-physic model highlights the best location for inside measurement. The sensors to be integrated fulfil high integrability and efficiency. To do so, nanoparticle-based strain gauges, temperature sensors and electromagnetic array sensors will be validated and integrated. The main interest of such sensors is their low power consumption, their miniaturization and their possible integration as well as their accuracy. Electromagnetic sensors will be issued from previous studies and adapted to this dedicated device. For both sensor types, the data packaging will be challenging spin-offs. Finally, advanced data processing techniquesestimation as well as signal processingwill be adapted to numerous sensor outputs. Moreover, a clean room process flowchart will be established to guarantee an advanced pre-industrial prototyping. The industrial partners will certify how far the project outputs will be suitable for advanced health monitoring of power device.

Finally, these features will result in a better knowledge of electro thermomechanical behaviour of power modules. Combined with the state of health indicator, the measurements or observations will be applicable to power modules health management and robustness. This paper presents the results obtained in each scientific and technical objectives. The first part of the paper is devoted to describing overall specifications. The second section highlights the design of a set of sensors and their first characterization results. In the third part, multiphysics modelling and preliminary reliability tests will be presented and analysed. The fourth part is dedicated to preliminary developments completed on data processing techniques, as far as filtering and variable estimation are concerned.

Program structure

Five partners carry this project: 2 research laboratories and 3 companies. Research laboratories will design electromagnetic sensors, define the data processing techniques and the multi-physics modelling as well as perform reliability tests for both sensors and functionalized power devices. Industrial partners will provide nanotechnology sensors, adapt the clean room process and guarantee the technology readiness level. As illustrated in Figure 1, six work packages are defined. They are linked with the main role of each partner. The main deliverables are thesis reports, technical reports as well as new products. Effectively for both industrial partners, their product will be updated following the CAPTIF results. Indeed, Nanolike sensors should be applicable to new markets, and more precisely to the power electronics components and systems. aPsi3D products will be fully characterized by the use of several sensors and it is imagined that some future power modules will integrate some sensors.

Specification

The product target for the integrated sensors is defined as a sandwich type power module as illustrated in Figure 2. Based on the geometry and the power density, the specification defines the process related constraints. Indeed, the maximal temperature occurring during the process, and the different process stage are specified. They are a part of the sensor process integration constraint.

Sensor development

To achieve these specifications, three types of sensors are developed: nanoparticle-based strain gauges, temperature sensors and electromagnetic field sensors.

Electromagnetic Field Measurement Principles

With the increase of the operating frequencies, switching rates and voltage/current levels in actual electronics systems, high electromagnetic noise and activity are now emerging over a wide frequency band [START_REF] Redl | Power electronics and electromagnetic compatibility[END_REF]. These can be considered as a good way to acquire an image of real conductive behavior of the devices, with a critical drawback for the integrity of the system: EM couplings and Electromagnetic Compatibility (EMC) increase problems in microelectronics [START_REF] Sicard | Issues in Electromagnetic Compatibility of integrated circuits, Emission and Susceptibility[END_REF]. Near-field measurement techniques have attracted a great deal of attention because of their high temporal and spatial resolutions [START_REF] Bolomey | Introduction to near-field techniques for EMC applications: state of the art and prospectives[END_REF]. The design of EM sensors is focused on magnetic near field measurement. The steps defined for the design of antennas deals with the characterization and the integration and validation. The antenna fulfills the following requirements: to be a punctual receiver; to not disturb the magnetic field distribution ! " "# ; to be sensitive only to the magnetic field. The final design is a 3$%% radius loop associated with 4$&% adapted transmission line. Moreover a parametrized study establishes the size and geometry of loop as well as the influence of the transmission line, for a given radius, length and substrate constitution. Finally as illustrated in Figure 3 the ! " "# field antenna is characterized and modeled as a R, L C equivalent electrical scheme. The simulation results is compared to the impedance measurement |'|.

Nanoparticle sensors

Today strain measurements are mainly made with two technologies: metallic strain gauges and semiconductor strain gauges. Metallic strain gauges have a small sensitivity (gauge factor = 2) but have a significant strain range (typically ± 3%). On the contrary semiconductor strain gauges have a higher sensitivity (gauge factor ~ 100) but a smaller strain range (typically ±0.5%). Nanoparticle-based strain gauges developed by Nanolike look like classical resistive sensors, except that the active area is made of a compact assembly of gold nanoparticles as illustrated in Figure 4.

Figure 4: Nanolike -nanoparticle sensors

As a consequence they combine a high sensitivity (gauge factor ~ 20), because of the tunnel mechanisms governing their electrical properties [START_REF] Moreira | Electron transport in gold colloidal nanoparticle-based strain gauges[END_REF] with a small electrical consumption which makes them very good candidates to be deployed as non-invasive sensors which is one objective of the project. Today, three main technologies are generally used to measure temperature: thermocouples, thermistors and resistance temperature detectors.

Thermistors and Resistance Temperature Detectors (RTD) exhibit correct performance but their electrical consumption and the difficulty of their integration on specific locations do not push them as good candidates to be spread onto PCBs. Thermocouples are easier to integrate on specific locations but one junction needs to be placed at a temperature reference, which leads to problems when the monitored devices are not in a controlled environment. Furthermore, sensitivity and accuracy of common thermocouples is relatively low. Because of these limitations, nanoparticle-based temperature sensors can be better candidates to be directly integrated on devices to monitor their temperature. As nanoparticle-based strain gauges, they are made of a compact assembly of gold nanoparticles the resistance of which depends on temperature. First experiments made on rigid silicon substrates indicate that these sensors can measure temperature with a good sensitivity (-0.5%/°C) and a very small electrical consumption (smaller than 1µW). Moreover, as the active area is very small (typ. 0.1mm²), they can easily be placed in confined areas.

Multi-Physics Modeling

A multi-physics model is necessary to correlate the data obtained by the sensors with the simulated ageing indicators. Multi-physics modeling allows catching in a more precise way the combined influence of several physical phenomena at stake rather than separately (mechanical, thermal and electrical phenomena). Multi-physics coupling and modeling tools, based on finite elements approach, will be used to provide complete numerical model of power modules on which sensors are integrated. The multi-physics models will be further validated thanks to the test vehicle reliability testing results. The multi-physics modelling of the complete module allows identifying the sensitive or fragile areas of the module to be monitored by the sensors. It allows making the link between accelerated ageing tests and real operation thanks to an indicator of the ageing state of the power module. Indeed, the health state indicator defined is the stored energy density function which corresponds to the strain energy density -SED of a material related to its deformation gradient:

()* = + ,-.

/ 0 / 1 1
Where . 2 and . 5 are the strain values of the material considered after a complete thermal cycle. To monitor the increase of the SED, a finite element simulation is used. A thermal cycle 6$ 7 [899°:; <>?9°:] is applied to a simplified power assembly composed of power device, a substrate and. The SED is monitored within the sintering material, all along the thermal cycle and increase step by step, as illustrated in Figure 5.

Such results aim at supplying tools and methodologies to help the design and the sensor integration in power modules.

It would be desirable that the real data provided by the sensors allow estimating in the same way the state of ageing of the module.

Data processing

The purpose of this study is to propose adapted methodologies and designed algorithms of data processing for the monitoring of a power electronics device. Then, efficient, feasible, fast response time and adaptable supervision technique will be selected with respect to the different monitored variables. The electro-thermal behavior of a plane surface made of several plane components and heterogeneous materials is simulated. For our purpose, this simulation is performed by spatial discretization, where elementary surfaces are defined. Each surface is modeled as an equivalent electrical circuit. 6 is the temperature, t the time, k and a some coefficients related to the geometry and materials, and S the power source. To do so, the thermal law: @A @B = CD 5 6 < E( 2 is expressed in a state space formulation as detailed in [START_REF] Trajin | Electrothermal model of an integrated buck converter[END_REF]:

: BF 6 G = H6 < IJ 3 Where T is a vector of local temperatures, C th is a diagonal matrix of thermal capacities, A the thermal resistances matrix, B is the command matrix and u is the vector of boundary conditions made of temperature and heat sources. That model will be combined to local temperature measurements with nanoparticle sensors. Finally, the aim of the study is to estimate the temperature at any point O of a power electronic module. Nevertheless, this simple approach has some drawbacks. One of them is the size of the observer state space model. To overcome this, the study explores two mains alternative strategies: to reduce the model order; to identify a simple transfer function. This last strategy deals with the idea to model the relationship between two local temperature values by an identified transfer function as the Strejc model or Hudzovic model. Indeed, as depicted in Figure 6, the objective is to estimate the temperature value at a given point O. O is situated on the top surface of power module which can be modelled as a discretized surface, as in Eq(3). This value can be obtained thanks the two previously mentioned strategy. F 1 , F 2 , F 3 , F 4 and F 5 model the transfer function between points.

Figure 6: Observer principle

C is where the sensor is set. S is the power source. P is a heat or power disturbance. The value of O should be obtained using a reduced observer, or with a simpler transfer.

Conclusions

CAPTIF aims at reaching a high monitoring knowledge of electro-thermo-mechanical behaviour of power electronics devices. This will be possible thanks to a set of integrated sensors associated with advanced data processing techniques. Indeed optimal design of power electronics would become more accurate than previously, as well as a better knowledge of reliability aspects would be reached.

Figure 1 :

 1 Figure 1: Work Package overview

Figure 2 :Figure 3 :

 23 Figure 2: agile Power Switch 3D-Integration power module

Figure 5 :

 5 Figure 5: Strain Energy Density computed.

Ackowledgement

CAPTIF program is funded by the French National Research Agency ANR-14-CE05-0044.


Imane Sakhraoui
email: imane.sakhraoui@enit.fr

Baptiste Trajin
email: baptiste.trajin@enit.fr

Frédéric Rotella
email: frederic.rotella@enit.fr

Application d'un observateur de fonctionnelle linéaire pour la mesure thermique d'une plaque chauffante

RESUME -La température est un problème crucial dans les modules d'électronique de puissance, or elle n'est pas directement mesurable en tout point de ce module. On propose ici l'application d'un observateur permettant de reconstruire cette grandeur entièrement à partir des mesures fournies par des capteurs thermiques placés en quelques points précis. L'utilisation de cet observateur permet de réduire la dimension du problème considéré.

ABSTRACT -The temperature is an extremely important problem in the power electronics modules, though it is not directly measurable at any point in the module. Here we propose an application of an observer that allows us to remodel this whole physical variable from the measures provided from thermal sensors positioned at a few precise points. The use of this observer permit to reduce the size of the considered problem. MOTS-CLES -Mesure et modèle thermique, observateur de fonctionnelle linéaire.

Introduction

Des études [START_REF] Ciappa | Selected failure mechanisms of modern power modules[END_REF], [START_REF] Ciappa | Some reliability aspects of IGBT modules for high-power applications[END_REF] ont montré que la température avait un impact sur la durée de vie des modules d'électronique de puissance, du fait de l'augmentation des contraintes locales, qu'elles soient purement thermiques ou thermo-mécaniques.

Cependant, la mesure de la température n'est pas possible en tout point. L'objectif consiste donc à reconstruire cette grandeur localement, à partir des données mesurées par des capteurs discrets.

Dans cet article, nous nous intéressons à un système thermique simple 2D, qui sera modélisé en utilisant l'analogie thermique-électrique. Le formalise d'état nous permettra de représenter les équations d'évolution thermique du système. L'utilisation d'un observateur de fonctionnelle linéaire sur ce modèle d'état, nous fournit alors une reconstruction de la température aux points désirés.

Modèle thermique 2D

Dans cet article, nous cherchons à simuler le comportement thermique d'une plaque de surface 30 × 30 mm, qui représente une coupe d'un module d'électronique de puissance.

Figure 1 : Discrétisation surfacique d'une plaque chauffante

Le comportement évolutif thermique de la plaque présentée par la figure 1 est donné en utilisant l'équation de la chaleur (1), [START_REF] Bianchi | Transferts thermiques[END_REF], [START_REF] Pitts | Schaum's Outline of Theory and Problems of Heat Transfer[END_REF], où 𝑇 est la température locale, 𝑡 le temps, 𝜌 la masse volumique, 𝐶 𝑝 la capacité thermique massique, 𝜆 la conductivité thermique, et 𝑠 la chaleur interne produite par le système.

𝜌 𝐶 𝑝 𝜕𝑇(𝑥, 𝑦, 𝑡) 𝜕𝑡 = -𝜆 ( 𝜕 2 𝑇 𝜕𝑥 2 + 𝜕 2 𝑇 𝜕𝑦 2 ) + 𝑠 (1)
L'équation de la chaleur reflète des phénomènes de transferts linéaires comme le transfert conductif et le transfert convectif dus à la présence de gradients de température, [START_REF] Roye | Définitions des règles de modélisation thermique des machines électriques tournantes[END_REF], [START_REF] Chillet | Identification du modèle thermique d'une machine à induction de puissance moyenne[END_REF].

Une discrétisation par différences finies, de cette équation montre que le comportement thermique est analogue à celui d'un circuit électrique composé de résistances représentant la conduction et la convection thermiques, de condensateurs représentant le stockage de la chaleur, de sources de tension représentant des sources de température et de sources de courant représentant des sources de chaleur, [START_REF] Trajin | Electro-thermal model of an integrated buck converter[END_REF]. Le transfert de chaleur conductif (à l'intérieur de la plaque) est caractérisé par une résistance de conduction R cd = 𝑒 𝜆𝑆 , et celui à convection (à l'extérieur de la plaque) est caractérisé par

R cv = 1 ℎ𝑆
où 𝑒 est l'épaisseur de la plaque, S la surface d'échange, et h le coefficient de convection, [START_REF] Bar-Cohen | Advances in thermal modeling of electronic components and systems[END_REF].

De façon générale, il existe une analogie thermique-électrique, [START_REF] Lasance | Thermal Characterization of Electronic Devices with Boundary Condition Independent Compact Models[END_REF]. Cette analogie nous permet d'obtenir un modèle électrique équivalent au modèle thermique issu de l'équation de la chaleur, afin de décrire le comportement de la plaque en utilisant les outils classiques d'étude des circuits.

Représentation d'état de la plaque chauffante

Á partir de la discrétisation par différences finies de la plaque chauffante, le théorème de Millman [START_REF] Palermo | Précis d'électricité l'essentiel du cours, exercices corrigés[END_REF] permet, pour chaque élément de surface d'exprimer la température T en son centre en fonction des températures de ses voisins et des impédances thermiques Z qui caractérisent les différents modes de transfert de chaleur entre les éléments connectés. À partir de ce modèle thermique exprimé dans le domaine électrique, on retrouve les équations différentielles associées à la température de chaque surface élémentaire. On obtient ainsi une réécriture dans le domaine électrique de l'équation de la chaleur discrétisée sous la forme de l'équation matricielle [START_REF] Ciappa | Some reliability aspects of IGBT modules for high-power applications[END_REF].

{ C th T ̇(t) = AT(t) + Bu(t) y(t) = CT(t) (2)
où T est le vecteur des températures T i,j , C th la matrice diagonale des capacités thermiques, A la matrice des résistances thermiques, y le vecteur des mesures. C caractérise donc la position du ou des capteurs. u contient les conditions limites et la puissance thermique injectée P th et B traduit leur influence sur la plaque.

Ce modèle d'état fournit alors la simulation des températures locales où seules certaines températures T i,j seraient accessibles à la mesure. Il convient donc de déterminer un observateur de fonctionnelle linéaire pour reconstruire la température locale qui ne pourrait pas être mesurée.

Observateur de fonctionnelle linéaire

On se place dans le cadre d'un système dont le modèle, est décrit par l'équation d'état : Définissons q comme le plus petit entier tel que, rang Σ q = rang [ Σ q LA q ], où : Σ q = (𝐶 𝑇 𝐿 𝑇 (𝐶𝐴) 𝑇 … (𝐶𝐴 𝑞-1 ) 𝑇 (𝐿𝐴 𝑞-1 ) 𝑇 (𝐶𝐴 𝑞 ) 𝑇 ) 𝑇 (5) D'après [START_REF] Roye | Définitions des règles de modélisation thermique des machines électriques tournantes[END_REF], il existe donc une combinaison linéaire, Γ 𝑖 , pour i = 0, . . . , q, et λ i , pour i = 0, . . . , q -1,

{ ẋ(t) = Ax(t) + Bu(t) y(t) = Cx(t) (3
tel que : LA q = ∑ Γ i q i=0 CA i + ∑ Λ i LA i q-1 i=0
Il a été montré dans [START_REF] Rotella | Minimal single linear functional observers for linear systems[END_REF], [START_REF] Kailath | Linear systems[END_REF] que cela permettrait d'obtenir la structure (4), avec,

F = ( 0 … 0 Λ 0 1 ⋱ 0 Λ 1 ⋮ ⋱ 0 ⋮ 0 0 1 Λ q-1 ) , G = ( Φ 0 Φ 1 ⋮ Φ q-1 ) , H = ( Γ 0 + Λ 0 Γ q Γ 1 + Λ 1 Γ q ⋮ Γ q-1 + Λ q-1 Γ q) , P = [0 0 … 0 1], et V = Γ q où, pour 𝑖 = 0, … , 𝑞 -2, Φ 𝑖 = [LA q-1-i -∑ Γ 𝑗 q j=i+1 𝐶𝐴 j-i-1 -∑ Λ j 𝐿𝐴 j-i-1 q-1 j=i+1 ]𝐵 et, Φ 𝑞-1 = [L -Γ 𝑞 ]𝐵
Lorsque la matrice F est une matrice de Hurwitz, on obtient un observateur asymptotique de la fonctionnelle linéaire Lx(t). Dans le cas contraire ou si les valeurs propres de la matrice ne conviennent pas, il convient d'augmenter l'ordre q et de réitérer la réalisation à un ordre plus élevé, [START_REF] Rotella | Some new standpoints in the design of asymptotic functional linear observers[END_REF], [START_REF] Trinh | Design of scalar functional observers of order less than (𝜈 -1)[END_REF].

Exemple appliqué sur la plaque chauffante

f 0 -d 0 f 0 0 g f 0 -d 0 f 0 -d 0 ) , (6)
C = (0 0 0 1 0 0 0 0 0), L = (0 0 0 0 0 0 0 1 0)

Où, a = -7.6 × 10 -3 , b = 1.3 × 10 -3 , c = -6.4 × 10 -3 , d = -5.1 × 10 -3 , f = 2.5 × 10 -3 et g = 0.1276

Les étapes suivantes illustrent la procédure de conception d'un observateur minimal :

(1) Test pour l'observateur minimum. Comme, CA = (0.0013 0 0 -0.0064 0.0013 0 0.0013 0 0) LA = (0 0 0 0 0.0013 0 0.0013 -0.0064 0.0013) Nous obtenons le rang(Σ 1 ) = 3 et le rang ( Σ 1 𝐿𝐴 ) = 4, donc, l'observateur minimum de premier ordre n'est pas réalisable.

(2) Test pour l'observateur minimal, q=2. Comme, C𝐴 2 = 10 -3 (-0.1781 0.0325 0 0.4528 -0.1461 0.0163 -0.1781 0.0325 0) L𝐴 2 = 10 -3 (0 0.0163 0 0.0325 -0.1461 0.0325 -0.1781 0.4528 -0.1781) Nous obtenons le rang(Σ 2 ) = 5 et le rang ( Σ 2 LA 2 ) = 6, donc, l'observateur minimum de premier ordre n'est pas réalisable.

(3) Test pour l'observateur minimal, q = 3. Nous obtenons le rang(Σ 3 ) = 7 et le rang ( Σ 3 LA 3 ) = 7. Comme, LA 3 ) , P = (0 0 1), V = 1

Compte tenu des ordres des grandeurs des coefficients des matrices G et H, on pourra approximer leurs valeurs par :

G = ( 0 0 -2.7879 × 10 -6 1.6453 × 10 -4 0 0
) , H = ( 0 0 0

) , P = (0 0 1), V = 1

La conception de cet observateur est terminée et la procédure peut être arrêtée. Néanmoins les pôles sont fixes. Si les pôles (-0.0051, -0.0064, -0.0089) ne sont pas acceptables, nous devons augmenter l'ordre de l'observateur.

La figure [START_REF] Roye | Définitions des règles de modélisation thermique des machines électriques tournantes[END_REF], montre le résultat de simulation du l'observateur conçu, et le système initial. On remarque que les conditions initiales sont nulles pour la figure (5-a). En effet, on supposera que le système est à l'équilibre thermique avec le milieu ambiant et que P th = 0, pour t < 0. Ainsi, seule une étude de la variation de température du système autour du point d'équilibre est nécessaire.

Le problème thermique considéré étant symétrique, on devrait avoir G = 0, et une sortie de l'observateur égale à la température simulée.

Afin de tester la robustesse de l'observateur, on a également réalisé une simulation avec des conditions initiales non nulles, qui en pratique seront les conditions initiales précédent chaque nouveau changement de consigne comme le montre la figure (5-b).

On vérifie à nouveau la convergence asymptotique entre la température simulée v, et celle estimée v ̂.

Nous avons effectué également une modélisation du système avec une discrétisation des différences finies plus fine traduit par un modèle d'état d'ordre 121. On choisit les positions du capteur et du point à observer de manière à avoir V ≠ 1. On obtient un observateur de fonctionnelle linéaire d'ordre réduit q = 10.

On vérifie toujours la convergence asymptotique entre la température simulée v, et celle estimée v ̂ suivant la même démarche détaillée ci-dessus. La figure [START_REF] Chillet | Identification du modèle thermique d'une machine à induction de puissance moyenne[END_REF], montre le résultat de simulation.

Conclusion

Nous avons présenté la modélisation thermique d'une plaque chauffante, à travers la discrétisation par différences finies de l'équation de la chaleur, en arrivant à une représentation d'état du système avec une analogie thermique-électrique.

À partir de cette expression d'état, nous avons utilisé une procédure constructive d'un observateur de fonctionnelle linéaire afin d'estimer la température dans des points désirés, ainsi que l'application de ce type d'observateur qui montre une réduction pertinente de l'ordre de l'observateur. La position des capteurs, et les points qu'on cherche à estimer traduit par la matrice L influencent la dimension de l'observateur.

Nous avons traité ici un problème physique thermique 2D. Dans le cadre de l'observation de la température d'un module complet d'électronique de puissance, il sera nécessaire d'établir des modèles thermiques 3D. De plus, ces modèles seront par nature hétérogènes. Ainsi, les représentations d'états obtenues seront potentiellement de très grande dimension. Malgré la réduction de dimension engendrée par l'utilisation d'un observateur de fonctionnelle linéaire, il est probable que l'observateur soit toujours de trop grande dimension pour être implémentable sur calculateur embarqué temps-réel. Dans ce cas, nous pourrions nous intéresser à la construction d'observateurs à partir de transferts identifiés expérimentalement, ce qui permettrait d'en réduire encore l'ordre.

Remerciement

Ces travaux de recherche sont réalisés et financés dans le cadre du projet ANR-CAPTIF (ANR-14-CE05-0044).

  En effet, chaque surface élémentaire est donc représentée par un réseau d'impédances traduisant la conduction entre le centre et les bords de cette surface. Le stockage d'énergie thermique dans une surface élémentaire est modélisé par une capacité thermique 𝐶 𝑡ℎ connectée entre le centre et la masse (référence thermique), et donnée par : C th = ρ C p V. Par ailleurs, on injecte une puissance thermique P th au milieu de la plaque, pour engendrer le fonctionnement dynamique du système thermique. La modélisation complète est ensuite réalisée en juxtaposant les modèles des différentes surfaces élémentaires liées physiquement. La figure (2) présente le modèle thermique associé dans le domaine électrique.

Figure 2 :

 2 Figure 2 : Interconnexion des modèles des différents surfaces élémentaires. [11]

Figure 3 :

 3 Figure 3 : Principe d'un estimateur Afin de concevoir un observateur rapide et implémentable sur un calculateur embarqué, nous devons rechercher l'ordre minimum d'un observateur de fonctionnelle linéaire. En effet, l'ordre de l'observateur dépend de plusieurs facteurs tels que la distance entre les capteurs et le lieu où la température est estimée.

  Pour la clarté de l'exposé, nous choisissons une discrétisation des différences finies en trois blocs, comme le montre la figure (4), qui est exprimé par un modèle d'état d'ordre 9, où Cap est le capteur traduit par la matrice C, S la puissance thermique injectée au milieu de la plaque, O le point qu'on cherche à estimer traduit par la matrice L.

Figure 4 :

 4 Figure 4 : Position des différents capteurs

Σ 3 - 1 =)( 4 )

 314 ( 2.8672 × 10 -7 -2.8672 × 10 -7 1.3387 × 10 -4 -1.3387 × 10 -4 0.0203 1 )On en déduit que, Λ 0 = -2.8672 × 10 -7 , Λ 1 = -1.3387 × 10 -4 , Λ 2 = -0.0203.Les valeurs propres de F sont : (-0.0051 -0.0064 -0.0089), l'observateur d'ordre q = 3, est réalisable. Conception de l'observateur minimal d'ordre q = 3, d'après, LA3 Σ 3 -1 , on a : Γ 0 = 2.8672 × 10 -7 , Γ 1 = 1.3387 × 10 -4 , Γ 2 = 0.0203, Γ 3 = 1 Nous obtenons, G = ( 5.7271 × 10 -19 4.3215 × 10 -18 -2.7879 × 10 -6 1.6453 × 10 -

Figure 5 :

 5 Figure 5 : Résultat de simulation pour la mise en oeuvre d'observateur minimal pour (6)

Figure 6 :

 6 Figure 6 : Résultat de simulation pour la mise en oeuvre d'observateur minimal d'ordre 𝐪 = 𝟏𝟎, pour un modèle d'état d'ordre 121, avec conditions initiales nulles.

4.2 Implémentation sur calculateur embarqué

  Le but de l'observateur de fonctionnelle linéaire d'ordre minimal est de pouvoir être implémenter sur un calculateur numérique embarqué. Pour cela, il est nécessaire, pour une application temps-réel, de minimiser le nombre d'opérations élémentaires effectuées par le calculateur à chaque nouvelle donnée (échantillon) acquise pour estimer la température.Compte tenu de l'équation (4), il vient la dimension des matrices 𝐹(𝑞 × 𝑞), 𝐺(𝑞 × 𝑟), 𝐻(𝑞 × 1), 𝑃(1 × 𝑞) et 𝑉(1 × 1). Il est donc possible d'évaluer aisément un majorant du nombre de multiplications et d'additions nécessaires à la reconstruction de la sortie estimée v ̂ à chaque échantillon. On montre alors qu'un majorant du nombre de multiplications est proportionnel à 𝑞 2 et qu'un majorant du nombre d'additions est proportionnel à 𝑞. On comprend alors la nécessité de minimiser la dimension de l'observateur.Dans le cadre de l'observation d'un problème thermique, les constantes de temps mises en jeu par le système sont souvent « lente » (plusieurs centaines de seconde dans notre exemple). Un calculateur embarqué ayant une fréquence d'échantillonnage adaptée aux constantes de temps du système et une horloge de calcul « rapide » (typiquement quelques dizaines de kilo Hertz) parviendra sans peine à reconstruire la température estimée pour chaque échantillon temporel.