Thomas Roche
email: thomas.roche@imag.fr

Mathieu Cunche
email: mathieu.cunche@inria.fr

Jean-Louis Roch
email: jean-louis.roch@imag.fr

Algorithm-based Fault Tolerance Applied to P2P Computing Networks

Keywords: ABFT, P2P, distributed computing, SUMMA, linear coding, fault-tolerance

P2P computing platforms are subject to a wide range of attacks. In this paper, we propose a generalisation of the previous disk-less checkpointing approach for fault-tolerance in High Performance Computing systems. Our contribution is in two directions: first, instead of restricting to 2D checksums that tolerate only a small number of node failures, we propose to base disk-less checkpointing on linear codes to tolerate potentially a large number of faults. Then, we compare and analyse the use of Low Density Parity Check (LDPC) to classical Reed-Solomon (RS) codes with respect to different fault models to fit P2P systems. Our LDPC disk-less checkpointing method is well suited when only node disconnections are considered, but cannot deal with byzantine peers. Our RS disk-less checkpointing method tolerates such byzantine errors, but is restricted to exact finite field computations.

I. INTRODUCTION

Gathering thousand of resources, global platforms such as peer-to-peer (denoted P2P) provide large scale computing systems for both data storage and computational power (e.g. BOINC [START_REF] Anderson | Boinc: a system for public-resource computing and storage[END_REF]). However, such a platform may be subject to various kinds of faults: in this paper we focus on failstop (e.g. peer disconnection) and by value errors [START_REF] Avizienis | Dependability and its threats -a taxonomy[END_REF]. In specific contexts, the possible byzantine behaviour of a peer may be statistically modelled. However, since a P2P platform usually operates in an unbounded environment, it may be the victim of orchestrated attacks against widespread vulnerabilities of specific operating systems. Therefore, in the worst case, malicious attacks have to be considered [START_REF] Roch | Probabilistic certification of divide & conquer algorithms on global computing platforms. Application to fault-tolerant exact matrix-vector product[END_REF] that make invalid any quantified model about the attack. Fault-tolerance in such contexts has been widely studied and most of the results are dedicated to Byzantine Agreement and Leader Election algorithms [START_REF] King | Towards secure and scalable computation in peer-topeer networks[END_REF], [START_REF] Kapron | Fast asynchronous byzantine agreement and leader election with full information[END_REF], Although our results enjoy less generality we investigated a more efficient way to tolerate byzantine peers based on coding theory ideas instead of classical voting methods. Nevertheless our results are not dedicated to specific overlay networks, the network geometry and peers hierarchy is not considered here as the our study stays at the application level. Algorithmbased fault tolerance (ABFT), introduced by K.H. Huang et al [START_REF] Huang | Algorithm-based fault tolerance for matrix operations[END_REF], was originally dedicated to matrix operations, for which it provides an efficient solution to fault tolerance in terms of time, space and complexity. It is based on the joint design of a coding technique together with a suited algorithm; due to linear algebra composition, ABFT for matrix operations is based on linear codes. Matrix operations are especially of interest in the context of large scale simulations. The use of ABFT in the context of global computing platforms has been proposed by J.L. Roch et al. [START_REF] Roch | Probabilistic certification of divide & conquer algorithms on global computing platforms. Application to fault-tolerant exact matrix-vector product[END_REF] for exact computations. For high-performance computing (HPC) of matrix multiplication, G. Bosilca et al. [START_REF] Bosilca | Algorithmic based fault tolerance applied to high performance computing[END_REF] propose a new ABFT method for matrix multiplication based on a parity check coding of rows and columns coupled to a SUMMA [START_REF] Van De Geijn | Summa: scalable universal matrix multiplication algorithm[END_REF] algorithm. It is presented in Section 2; its major interest is to consistently perform the computation with disk-less checkpointing of intermediate results. But, this technique is suited to a medium scale HPC machine: the use of parity check tolerates at most either one by-value or three fail-stops errors. Focusing on large scale and P2P platforms, the first contribution of this paper (Section 3) is to generalize this technique to any linear code to efficiently tolerate a large number of errors. Two linear codes are then proposed: low density parity check (LDPC) codes [START_REF] Gallager | Low density parity check codes[END_REF] for floating point computations (Section 4) and Reed-Solomon codes that resist to malicious attacks for exact computations (Section 5). To our knowledge this paper is the first application of LDPC based ABFT for P2P platforms.

II. RELATED RESULTS ON ALGORITHMS-BASED FAULT TOLERANCE (ABFT) FOR HIGH PERFORMANCE COMPUTING

A "consistent" ABFT scheme for matrix multiplication: Let us recall the ABFT scheme proposed in [START_REF] Bosilca | Algorithmic based fault tolerance applied to high performance computing[END_REF] for matrix-matrix multiplication. It is based on two ideas: when the input matrices contain checksum rows and columns then, in absence of error, the output matrix possesses the valid checksum rows and columns; besides, at any point during the multiplication computation, the checksums are consistent (i.e. the intermediate matrices also possess valid checksum rows and columns). Hence, if A and B are the two input matrices and C R and C C be the checksum matrices, the respective encoded matrices A F and B F are :

A F = A AC R C T C A C T C AC R and B F = B BC R C T C B C T C BC R
The equation 1 proves the consistency of checksums for the whole multiplication:

A C T C A × B BC R = AB ABC R C T C AB C T C ABC R (AB) F (1)
Moreover, the multiplication is performed in its outer product version (for k=1:n, C k = C k + A :,k B k,: end): so the intermediate matrices C k are consistent with respect to the checksum matrices C R and C C . Figure 1 details the product with consistent checksum on 3 × 3 matrices.

The Scalable Universal Matrix Multiplication Algorithm (SUMMA, [START_REF] Van De Geijn | Summa: scalable universal matrix multiplication algorithm[END_REF]), is an efficient parallel matrix-matrix multiplication: it is widely used (e.g. in ScaLAPACK [START_REF] Dongarra | Applied Parallel Computing, Computations in Physics, Chemistry and Engineering Science, Second International Workshop, PARA '95[END_REF]). Let us consider p processes performing the matrixmatrix multiplication as a square grid of √ p-by-√ p processes. Let n×k (resp. k×m) be the size of A F (resp. B F ). Columns of A F (resp. lines of B F ) are treated by blocks of size nb, where nb is a tunable parameter. The matrix A F (resp. B F ) is divided in blocks of size √ p-by-k nb (resp. k nb -by-√ p). So, at the ith step of the multiplication (as described on Figure 1), ∀j the (j, i)th block of A F is broadcasted to the jth row of processes and the (i, j)th block of B F is broadcasted to the jth column of processes. Then each process performs a local matrix-matrix multiplication of size n √ pby-nb-by-m √ p that it adds to its local block. The computation ends after k nb iterations. After each of the nb outer product iteration a global synchronisation is performed to assure data consistency. The nb parameter can be tuned from 1 (one consistent state after each computed row) to n (only one consistent state at the end of the computation). Note that all the redundant computations are performed by the processes related to the last row of blocks in A F and the last column of blocks of B F since they contain only checksums data. Hence the fault tolerance cost in number of processes is 2 × √ p -1. Furthermore, if a process crashes during the i-th iteration of the algorithm, its state can be recovered from the redundant information computed by those processes. Actually, due to the 2D checksum, up to 3 process crashes during the same iteration can be recovered. An interesting remark is the strong scalability of this scheme with respect to the fault-tolerance overhead : the proportion of processes used for fault-tolerance (

C 1 × B F A F C 3 = = = × + + × C 2 C 1 C 2 C F
2× √ p-1 p
) decreases when the total number of processes increases.

Result certification: It is important to note here that matrix-matrix multiplication enjoy an efficient post-condition check. Whereas working in finite field or floating-point arithmetic, it is always possible to verify the result C = AB with high probability by randomly choosing a vector x and checking if Cx = A × Bx. The complexity of this check is equal to three matrix-vector product (O(n 2 )) which is negligible compared to the cubic complexity of matrix-matrix multiplication. Furthermore, any of the intermediate C k of the SUMMA algorithm can be certified the same way since C k = A k B k , where A k (resp. B k ) is the matrix A (resp. B) only composed of the first k blocks of nb columns (resp. blocks of nb rows).

Limitations: As the size of the computing platform increases, the number of processes errors and crashes increases as well. However, the described ABFT scheme is limited by the correction capability of the 2D checksums : 3 processes crashes and 1 bit-flip error. As a consequence, it is not suited to P2P networks that are subject to frequent process failures and/or disconnections.

III. GENERALISATION TO LINEAR CODES-BASED CONSISTENT ABFT, EXTENSION

TO P2P COMPUTING NETWORKS To fit to P2P platforms we propose a generalisation of the previous ABFT scheme. Observing that the checksum is in fact a particular linear block code, we propose to generalize this system by using more flexible linear code in order to increase the number of errors and failures that can be tolerated by the system.

A. Linear block codes and consistent matrix multiplication

Linear block codes are a class of codes used for error detection and correction. By adding redundancy to the source data they are able to detect and correct errors and/or erasures. A linear block code C of dimension n and length n + r is a linear subspace of dimension n of the linear space F n+r , where F is a field. The quantity R = n/(n + r) is called the code rate. The elements of F are called symbols, and the elements of C are called codewords.

The correction capabilities of a linear code are usually estimated by a characteristic called minimum distance. The minimum distance (noted d min ) of a linear block code is the minimum number of non null symbols in a codeword (excluding the zero codeword). A code with a minimal distance d min will be able to detect d min -1 and correct ⌊ dmin-1 2 ⌋ errors. More generally, a codeword corrupted with t errors and e erasures can be recovered if d min ≥ 2t + e + 1. Maximum Distance Separable (MDS) codes are such that d min = r + 1: their distance is maximum with respect to the number r of redundant symbols.

The coding scheme proposed in [START_REF] Bosilca | Algorithmic based fault tolerance applied to high performance computing[END_REF] can be easily generalised with any linear code whose symbols field F is compliant with the matrix entries arithmetic. The 2-dimensional parity check C C and C R are replaced by the generator matrices of chosen linear code. Thanks to the algebraic structure of a linear code, the product (as well as the sum) of encoded matrices is still a consistent encoded matrix. In all the sequel, for the sake of simplicity, we consider only the coding of the columns by C C ; the coding of the rows by C R is symmetric.

B. A linear code-based consistent ABFT

Thanks to the previous generalisation, a consistent matrix multiplication can be built to tolerate a large number of errors, by tuning the redundancy of the chosen linear code.

Scheme extension for HPC: We consider a matrix product over a large scale HPC platform. Let's consider the product of A and B with SUMMA as presented in Section II and a linear code of dimension n and length n + r, its code rate is therefore R = n/(n + r).

The n × k matrix A is encoded into a (n + r) × k matrix A F .
Like in Section II, let us consider p resources viewed as a √ p-by-√ p grid. The number of faults that can be tolerated between each iteration of the SUMMA algorithm depends on the amount of redundancy added by the code. In the case of an MDS code, by adding a redundancy of r symbols, the system will be able to correct e erasures and t faults while r = d min -1 ≥ 2t + e. Since a process is in charge of (n + r)/ √ p symbols of a column, a single node failure (fail-stop error) will cause the erasure of the same amount of symbols, and a single byzantine node (by-value error) will corrupt up to this number of symbols.

In order to tolerate E node failures (represented by erasures) and T Byzantine nodes we need to have:

r ≥ 2T (n + r)/ √ p + E(n + r)/ √ p; so r ≥ n(2T +E) √ p-(2T +E)
. Thus the proportion of processes used for faulttolerance is:

(r √ p/(n+r)) √ p p = r/(n + r) = 1 -R.
It depends only on the code rate. This system is therefore weakly scalable, but as opposed to [START_REF] Bosilca | Algorithmic based fault tolerance applied to high performance computing[END_REF], has a constant code rate, which is critical to tolerate errors on P2P computing platforms.

Adaptation to P2P computing networks: Yet, when considering matrices of high dimensions, linear code based-ABFT is very attractive to be able to correct bit-flip errors, to recover lost data and to certify intermediate computations. All these operations are performed in Õ(n 2 ) operations when the overall product needs O(n 3 ). The outer product version of matrix-matrix multiplication will give us a chance to do all this by allowing an efficient faulttolerant checkpoint scheme sketched in figure 2.

Let consider a user U proposing a matrixmatrix multiplication to a P2P computing network. The property of disk-less checkpointing, which is based on a global synchronization of all participating resources, is not suited to P2P networks where all data (A F , B F and the matrices C k ) are shared among the peers. After the data distribution through the whole network by peers downloading and uploading part of the input matrices data and tasks (which are, of course, linked to blocks of data), peers will work on the local data they possess. A fault-tolerant checkpoint is assured by sending the intermediate computations of block to the user U (after each iterations or after a fixed number of iteration). When U has received enough blocks corresponding to matrix C k of iteration k, he can decode C k thus recovering the potentially missing blocks and/or bit-flip errors. Then U performs a post-condition checking on the decoded value in order to certify this state C k . If, for any reason, the post-condition is not passed, he can send a stop message to the peers and resume the computation from the last certified state. Note that the outer product integrates nicely in this P2P protocol. Indeed, due to the highly parallel algorithm, coarse grain tasks can always be divided in smaller tasks up to the finest grain (elements addition or multiplication), hence allowing a very flexible online task division and repartition (suitable to work stealing for instance [START_REF] Roch | Probabilistic certification of divide & conquer algorithms on global computing platforms. Application to fault-tolerant exact matrix-vector product[END_REF]). Moreover, there is no need for the user to divide the input matrices in blocks with respect to the number of resources (which would be impracticable in P2P context anyways): for instance an online recursive splitting of the matrix by work-stealing will automatically load balance the computation among the peers.

IV. LDPC-CONSISTENT ABFT ON TRUSTED P2P COMPUTING NETWORKS

We consider a P2P network where peers can leave before completing their tasks or return erroneous results. This case can be addressed by the use of Low density parity check (LDPC) codes [START_REF] Gallager | Low density parity check codes[END_REF] which name comes from the small number of nonnull entries in the related parity check matrix. Even if their minimal distance is small, those codes show error correction capabilities close to channel capacity when decoded with a linear complexity message passing algorithm.

Since LDPC codes are in fact a concatenation of several simple parity check as used in [START_REF] Bosilca | Algorithmic based fault tolerance applied to high performance computing[END_REF], the numerical properties of the floating point checksums are still valid for LDPC codes when recovering from erasures. Yet, to deal with fault values, LDPC codes are restricted to exact arithmetic.

Using an LDPC-based ABFT enables to tolerate a number of peers disconnections and nonmalicious by-value errors close to the optimal with a high probability (see Table .I). The algorithm used for error correction runs in O(n) [START_REF] Gallager | Low density parity check codes[END_REF], so in the same We now consider the byzantine fault model in the context of P2P networks that are subject to malicious attacks. Indeed in a P2P Network, the peers cannot be trusted. This limits the confidence in the outputted result. While the matrix-matrix multiplication possesses an efficient post-condition (see Section II), one has yet to be sure the postcondition checking was not forged by a malicious peer. Furthermore, assuming the post-condition checking can be trusted, using the fault-tolerance studied in the previous section would allow very cheap Denial of Service attacks. The small minimal distance of LDPC codes means that one can forge a valid codeword with only few modified coordinates (i.e. few peers controlled by an attacker). Codes with large minimum distance will better fit to this case (e.g. MDS codes). Let us assume a part of the available computing platform can be trusted. The size (so the computational power) of this trusted platform is expected to be very small compared to the untrusted platform. The trusted part should be used for decoding and, more importantly, postcondition checking (e.g in figure 2 user U is trusted and the P2P computing network is not).

Reed-Solomon: Reed-Solomon (RS) are MDS codes introduced in 1960 by I. Reed and G. Solomon. RS codes are always able to correct r/2 errors (when it's only under a certain probability of error for LDPC codes) while having a decoding complexity barely higher than LDPC (O(nlog 2 n) [START_REF] Blahut | Theory and Practice of Error Control Codes[END_REF], see Table I). RS codes are well suited to tolerate Byzantine (so malicious) errors with exact arithmetic. Thus, with large enough redundancy, the use of RS-based ABFT for consistent matrix multiplication with exact arithmetic, prevents non massive malicious attacks [START_REF] Roch | Probabilistic certification of divide & conquer algorithms on global computing platforms. Application to fault-tolerant exact matrix-vector product[END_REF]: forging a wrong result would require the attacker to control many peers. However, the non compatibility of underlying arithmetic makes RS-based ABFT not suited to floating point computations.

VI. CONCLUSION AND FUTURE WORK

In this paper, we presented a generalization of consistent ABFT matrix multiplication based on linear codes which is suited to P2P computing. The proposed protocol enables to tolerate the potential erratic behaviour of the P2P network. Considering exact arithmetic, the use of RS code provides efficient fault tolerance not only in case of peer disconnection but also in case of byzantine errors (even considering malicious peers). For floating point arithmetic computations, the use of LDPC codes supports an arbitrary number of fail-stop errors with efficient coding and decoding. Our perspective is to use this protocol for an effective challenge in exact arithmetic computation.

Figure 1 .

 1 Figure 1. Checksum consistent outer product

Figure 2 .

 2 Figure 2. Fault tolerant checkpoint protocol


Falou Ndoye
email: falou.ndoye@inria.fr

Yves Sorel
email: yves.sorel@inria.fr

Safety Critical Multiprocessor Real-Time Scheduling with Exact Preemption Cost

Keywords: multiprocessor real-time scheduling, partitioned scheduling, exact preemption cost, load balancing

In this paper, we address for safety critical applications the problem of multiprocessor real-time scheduling while taking into account the exact preemption cost. In the framework of multiprocessor real-time partitioned scheduling, we propose a greedy heuristic which balances the load of the tasks on all the processors and minimizes the response time of the applications. That heuristic uses a schedulability condition which is based on the ⊕ operation. That operation performs a schedulability analysis while taking into account the exact preemption cost. A performance analysis is achieved which compares the proposed heuristic to the branch and bound exact algorithm and to the worst-fit and best-fit heuristics.

I. INTRODUCTION

For computation power and modularity issues, multiprocessor architectures are necessary to tackle complex applications found in domains such as avionics, automotives, mobile robotics, etc. Some of these applications are safety critical, leading to hard real-time task systems whose number of resources are fixed and constraints must be necessarily satisfied in order to avoid catastrophic consequences. Although fixed priority preemptive real-time scheduling allows a better success ratio than non-preemptive real-time scheduling, preemption has a cost. That cost is usually approximated in the WCET (Worst Case Execution Time) as assumed, explicitly, by Liu and Layland in their pioneering article [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environnment[END_REF]. However, such approximation is dangerous in a safety critical context since an application could miss some deadlines during its real-time execution even though schedulability conditions have been satisfied. This is why it is necessary to be aware of the exact preemption cost. In this paper, we address the problem of multiprocessor real-time scheduling while taking into account the exact preemption cost in safety critical applications. In the framework of multiprocessor real-time partitioned scheduling, we propose a greedy heuristic [START_REF] Martello | Bin packing approximation algorithms: Combinatorial analysis[END_REF] using all the processors and which balances the load of the tasks on all the processors. That heuristic tends to minimize the response time (makespan) of the tasks. The schedulability condition is based on the algebraic ⊕ operation which performs a schedulability analysis taking into account the exact preemption cost.

The remainder of the paper is organized as follows: Section II presents related work about preemption cost and multiprocessor real-time scheduling. Section III describes the model and the schedulability analysis we propose. Section IV presents the proposed multiprocessor scheduling heuristic as well as its complexity, and Section V presents a performance analysis for that heuristic by comparing it with the Branch and Bound (B&B) exact algorithm, the Worst-Fit (WF) and Best-Fit (BF) heuristics. Finally, Section VI concludes and gives some directions for future work.

II. RELATED WORK

A. Exact preemption cost in real-time scheduling

There have been very few studies addressing the exact number of preemptions. Among them, the most relevant are the following. A. Burns, K. Tindell and A. Wellings in [START_REF] Burns | Effective analysis for engineering real-time fixed priority schedulers[END_REF] presented an analysis that enables the global cost due to preemptions to be factored into the standard equations for calculating the worst case response time of any task, but they achieved that by considering the maximum number of preemptions rather than the exact number. Juan Echagüe, I. Ripoll and A. Crespo also tried to solve the problem of the exact number of preemptions in [START_REF] Echague | Hard real-time preemptively scheduling with high context switch cost[END_REF] by computing the schedule using idle times and counting the number of preemptions. However, they did not really determine the execution overhead incurred by the system due to these preemptions. Indeed, they did not take into account the cost of each preemption during the analysis. Hence, this amounts to considering only the minimum number of preemptions because some preemptions are not considered: those due to the increase in the execution time of the task because of the cost of preemptions themselves.

In order to reduce the preemption cost and improve the schedulability of tasks, a lot of work has focused on limitedpreemption policies; among these we can cite fixed priority scheduling with deferred preemption (FPSDP) also called cooperative scheduling [START_REF] Burns | Preemptive priority-based scheduling: An appropriate engineering approach[END_REF] and fixed priority scheduling with a preemption threshold (FPSPT) [START_REF] Wang | Scheduling fixed-priority tasks with preemption threshold[END_REF], [START_REF] Saksena | Scalable real-time system design using preemption thresholds[END_REF]. According to FPSDP, each job of a task is a sequence of sub-jobs, where sub-jobs are not preemptive. When a job is being executed, it can only be preempted between two consecutive sub-jobs. For FPSPT, each task is assigned a nominal and a threshold priority. A preemption will take place only if the preempting task has a nominal priority greater than the preemption threshold of the executing task. None of the previous works considers the exact number of preemptions. Nonetheless, that can affect the correct behavior of the system at run-time, or in any case leads to resources being wasted in terms of time and memory. It is typical and not difficult to determine the constant cost of every preemption which includes the context switch necessary to make the preemption possible together with the choice of the task with the highest priority. However, the exact number of preemptions is difficult to determine since it may vary according to every instance of a task. To our best knowledge there are only few studies that take into account the exact preemption cost in the schedulability conditions, except those presented in [START_REF] Yomsi | Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems[END_REF], [START_REF] Yomsi | An algebraic approach for fixed-priority scheduling of hard real-time systems with exact preemption cost[END_REF]. The authors proposed a scheduling operation named ⊕ that performs a schedulability analysis while computing the exact number of preemptions. The principle of this operation is presented in Section III-B.

B. Multiprocessor real-time scheduling

The scheduling of real-time tasks on multiprocessor architectures can be achieved according to three main approaches: partitioned scheduling, global scheduling, and semi-partitioned scheduling.

In the partitioned scheduling approach [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF], [START_REF] Zapata | Edf and rm multiprocessor scheduling algorithms: Survey and performance evaluation[END_REF] the system of tasks is divided into a number of disjoint subsystems less than or equal to the number of processors in the multiprocessor architecture, and each of these subsystems is allocated to one processor. All the instances, or jobs, of a task are executed on the same processor and no migration is permitted. In this approach, it is necessary to choose a scheduling algorithm for every processor, possibly the same algorithm, and also an allocation algorithm. On the other hand, the allocation problem has been demonstrated to be NP-Hard [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completeness[END_REF]. This complexity is the main drawback of the partitioned scheduling approach.

Heuristics are considered to be the best suited solutions when the execution time is crucial as in the rapid prototyping phase of the design process. In the case of fixed priority scheduling and independent tasks, Davari and Dhall were the first to propose in [START_REF] Dhall | On a real-time scheduling problem[END_REF] two preemptive scheduling algorithms RM-FF (Rate Monotonic First Fit) and RM-NF (Rate Monotonic Next Fit) to solve the multiprocessor realtime scheduling problem. In the proposed algorithms, the uniprocessor RM algorithm [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environnment[END_REF] is used to verify if a task is schedulable on a processor with respectively First-Fit (FF) and Next-Fit (NF) to solve the allocation problem. Another heuristic, RM-BF (Rate Monotonic Best Fit) was proposed in [START_REF] Oh | Tight performance bounds of heuristics for a real-time scheduling problem[END_REF]. It makes it possible to minimize the remaining processor load (1-U pj ), called the unutilized capacity of the processor p j [START_REF] Lupu | Multi-criteria evaluation of partitioning schemes for real-time systems[END_REF], where U pj is the load of the tasks on p j . In contrast to RM-BF, RM-WF [START_REF] Oh | Tight performance bounds of heuristics for a real-time scheduling problem[END_REF] (Rate Monotonic Worst Fit) maximizes the remaining processor load. All these approaches uses the classical Liu and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environnment[END_REF] model of tasks that assumes the preemption cost is approximated in the WCET. In order to tackle this problem [START_REF] Ndoye | Preemptive multiprocessor real-time scheduling with exact preemption cost[END_REF] presents a first solution to take into account the exact preemption cost in multiprocessor real-time scheduling.

In the global scheduling approach [START_REF] Davis | A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems[END_REF], [START_REF] Zapata | Edf and rm multiprocessor scheduling algorithms: Survey and performance evaluation[END_REF], a unique scheduling algorithm is applied globally for every processor of the multiprocessor architecture. All the ready tasks are in a unique queue shared by all the processors. In this queue, the m tasks with the highest priorities are selected to be executed on the m available processors. Besides preemptions, task migrations are permitted. The advantage of the global scheduling approach, is that it allows a better use of the processors. The main drawback of the global scheduling approach, is that each migration nowadays has a prohibitive cost.

In the semi-partitioned scheduling approach [START_REF] Katoa | Semi-partitioning technique for multiprocessor real-time scheduling[END_REF], [START_REF] Anderson | An edf-based scheduling algorithm for multiprocessor soft real-time systems[END_REF], derived from the partitioned scheduling approach, each task is allocated to a specific processor as long as the total utilization of the processor does not exceed its schedulable bound. In this approach, some tasks can be portioned for their executions among multiple processors. During runtime scheduling, a portioned task is permitted to migrate among the allocated processors, while the partitioned tasks are executed on specific processors without any migration. The semi-partitioned scheduling approach allows a reduction of the number in migrations. But again, it is necessary to be aware that every migration has a cost.

C. Our choices

The cost of migrations in the global and semi-partitioned scheduling approaches leads us to choose the partitioned scheduling approach. In addition, since the partitioned scheduling approach amounts to transform the multiprocessor scheduling problem into several uniprocessor scheduling problems, we can take advantage of the numerous research results obtained for the uniprocessor scheduling problem. In order to achieve rapid prototyping, we propose an allocation heuristic rather than a metaheuristic [START_REF] Talabi | Metaheuristics[END_REF] or an exact algorithm [START_REF] Mitchell | Branch-and-cut algorithms for combinatorial optimization problems[END_REF], and a schedulability condition to verify if a task is schedulable on a specific processor. Next-fit (NF) and first-fit (FF) heuristics can not optimize the load of the tasks on the processors, their choice is only based on the first processor which satisfies the schedulability condition. The BF heuristic using the load as a cost function, tries to fill a processor as much as possible before using another one. This technique does not induce load balancing. The only heuristic among the bin-packing heuristics which permits load balancing is WF. But, as with all the other bin-packing heuristics, WF tries to reduce the number of processors and that limits the balancing while multiprocessor architectures used in industrial applications, which we are interested in, have a fixed number of processors. That is why we propose a greedy heuristic similar to the WF heuristic, but which uses all the available processors. This heuristic aims at minimizing the load on each processor. That induces to balance the load on all the processors. This proposed heuristic will be compared to the WF and BF heuristics and to the B&B exact algorithm.

Although preemptive scheduling algorithms are able to successfully schedule some task systems that cannot be scheduled by non-preemptive scheduling algorithms, the preemption has a cost. Indeed, Liu and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environnment[END_REF] assume that the preemption cost is approximated in the WCET. Thus, there are two possible cases: the approximation in time and memory space is high enough and thus will probably lead to wasting resources, or the approximation is low and thus a task system declared schedulable by, let us say RM, may miss some deadlines during its real-time execution. Consequently, we propose using the ⊕ operation [START_REF] Yomsi | Extending rate monotonic analysis with exact cost of preemptions for hard real-time systems[END_REF], [START_REF] Yomsi | An algebraic approach for fixed-priority scheduling of hard real-time systems with exact preemption cost[END_REF]. This is an algebraic operation that two tasks are schedulable, or not, while taking into account the exact preemption cost.

III. MODEL AND SCHEDULABILITY ANALYSIS

A. Model

Let Γ n = {τ 1 , τ 2 , • • • , τ n
} be a system of n preemptive, independent and periodic real-time tasks. Every task is denoted by

τ i = (r 1 i , C i , D i , T i ) where r 1 i , C i , D i and T i are the characteristics of the task. r 1
i is the first activation date, C i is the EET (Exact Execution Time) without any approximation of the preemption cost, D i is the relative deadline, and T i the period of the task τ i . We assume that C i ≤ D i ≤ T i . Here we use the EET rather than the WCET because we assume that the code associated to a task is purely sequential, i.e. there are no conditional branches. Our hypothesis to consider the EET may seem unrealistic, but since we are considering safety critical applications it is mandatory to known the EET. Of course, when dealing with uncritical applications the WCET can be used. Also, we assume that Γ n is scheduled according to the rate monotonic (RM) fixed-priority scheduling policy [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environnment[END_REF] on m identical processors (all the processors have the same computation power). Eventually, we assume that the processors have neither cache nor pipeline, or complex internal architecture. Both preview assumptions are usually made in safety critical applications where determinism is a key issue.

B. Schedulability analysis based on the ⊕ operation

Our schedulability analysis is based on the ⊕ scheduling operation [START_REF] Yomsi | An algebraic approach for fixed-priority scheduling of hard real-time systems with exact preemption cost[END_REF] . This operation is applied to a pair of tasks (τ i , τ j ), such that τ i has the highest priority. It gives as a result a task R, that is R = τ i ⊕ τ j . The ⊕ takes into account the exact preemption cost incurred by the task τ j . The schedulability interval, i.e. the interval in which we study the schedulability of the tasks, comes from the theorem 1 below which was introduced by the J. Gossens [START_REF] Goossens | Scheduling of Hard Real-Time Periodic Systems with Various Kinds of Deadline and Offset Constraints[END_REF].

Theorem 1: For a system Γ n = {τ 1 , τ 2 , • • • , τ n } of n periodic tasks arranged by decreasing priorities with respect to a fixed-priority scheduling policy, let (s ′ i ) i∈N * be the sequence defined by:

       s ′ 1 = r 1 1 s ′ i = r 1 i + (s i-1 -r 1 i ) + T i • T i , 2 ≤ i ≤ n (1)
If there exists a valid schedule of Γ n until the time s

′ n +H n where H n = lcm{T i | i = 1, • • •
, n}, and x + = max(x, 0), then this schedule is valid and periodic of period H n from s ′ n .

Proof: The proof of this theorem is similar to that performed by J. Goossens in his Ph.D. thesis [START_REF] Goossens | Scheduling of Hard Real-Time Periodic Systems with Various Kinds of Deadline and Offset Constraints[END_REF].

A direct consequence of the previous theorem is that in the case of a valid schedule, the result of the schedule of the i first tasks is periodic of period

H i = lcm{T j | j = 1, • • • , i} from s ′ i .
Thus, the interval which precedes s ′ i necessarily contains the transient phase, corresponding to the initial part of the schedule and the interval starting at time s ′ i with length H i is isomorphic to the permanent phase of the schedule of the i first tasks which repeats identically from the instant s ′ i . In order to compute R = τ i ⊕ τ j with j = i + 1, we set ǫ = min(r 1 i , r 1 j ). Since ǫ always exists, the interval [ǫ, s ′ j ] defines the transient phase and the interval [s ′ j , s ′ j + H j ] defines the permanent phase, s j and H j are given by the theorem 1. The schedulability study of the tasks is performed in the interval [ǫ, s ′ j + H j ]. In this interval, the number of instances of a task τ j is given by

n j = (s ′ j +Hj )-r 1 j Tj .

1) Principle of the ⊕ operation:

The principle of ⊕ applied to a pair of tasks (τ i , τ j ) consists in replacing the available time units of the highest priority task τ i with the time units of the lowest priority task τ j . In order to do that, both tasks are initially referenced to the same time origin ǫ. Then, task τ i is rewritten according to the number of instances of task τ j in the interval [r 1 j , s ′ j + H j ] of both task periods. This operation allows not only the identification of the available time units in task τ i , but also the verification that task τ j does not miss any deadlines.

When the task τ j is preempted by the task τ i the exact number of preemptions must be computed for each instance of τ j by considering all its time units. When τ j is preempted, we increment its number of preemptions and we add the cost associated with one preemption in the remaining execution of τ j , i.e. the number of time units that τ j must execute in order to complete its execution. That scheme is repeated to take into account a preemption generated by a previous preemption, and so on. In contrast to other works presented in the literature, this principle makes it possible to have the exact number of preemptions. The cost associated to that exact number of preemptions is added to the EET of τ j to obtain its PET (Preemption Execution Time).

Figure 1 illustrates the PET. In this figure, the PET of task τ i in the instance k + 1 is given by C k+1 i = C i + 2α due to two preemptions, with α being the cost of one preemption. If the amount of PET unit of times fits in the available time Figure 1. PET of a task units of task τ i , the task τ j is schedulable, giving as a result task R, otherwise it is not schedulable. ⊕ is an internal operation, i.e. the result given by ⊕ is also a task, that result may be in turn used as the highest priority task in another ⊕ operation. Thanks to this property it is possible to consider more than two tasks.

In order to perform the schedulability analysis of the task system Γ n = {τ 1 , τ 2 , • • • , τ n }, ordered according to the decreasing priorities of the tasks, the ⊕ operation is applied from the task with the highest priority to the task with the lowest priority. Consequently, if R n is the scheduling task result of Γ n , then R n is obtained by successive iterations:

R 1 = τ 1 R i+1 = R i ⊕ τ i+1 , 1 ≤ i < n As such we have R n = ((τ 1 ⊕ τ 2 ) ⊕ • • • ⊕ τ n-1 ) ⊕ τ n .
The system Γ n will be said schedulable if and only if all the tasks are schedulable. If this is not the case, then the system Γ n is said to be not schedulable.

The complexity of ⊕ applied to a pair of tasks τ i and τ j is O(l) with l is the LCM between the period of τ i and the period of τ j .

We denote by H j = lcm{T l : τ l ∈ hp(τ j )} where T l represents the period of task τ l and hp(τ j ) denotes the subsystem of tasks with a priority higher than the priority of τ j . The number of instances of task τ i in the permanent phase is given by:

σ permj = H j T j = lcm{T l : τ l ∈ hp(τ j )} T j (2)
The exact permanent load of a task τ j , i.e. the load of the task τ j , while taking into account the exact preemption cost, is given by:

U * j = C * j T j with C * j = 1 σ permj σperm j l=1 C l j (3)
In equation 3, C l j corresponds to the PET of the l th instance in the permanent phase. As such, the exact permanent load of the system Γ n composed of n periodic tasks scheduled on a processor p i is given by:

U * pi = n j=1 U * j (4)
2) Example: We apply the ⊕ operation to a system of periodic preemptive real-time tasks while taking into account the exact preemption cost. Let us consider such a system Γ 3 = {τ 1 , τ 2 , τ 3 } of 3 tasks where τ 1 is the task with the highest priority, and τ 3 is the task with the lowest priority. We consider the cost of one preemption to be one time unit for all tasks. The characteristics of the tasks are summarized in table I. The ⊕ operation is applied to a pair of operands. The left operand called the "executed task" corresponds to the result of the tasks previously scheduled, and the right operand called the "executable task" corresponds to the task to be scheduled. We represent an instance of the executable task by a unique sequence of symbols "e", in bold, followed by a sequence of symbols "a". Each symbol "e", in bold, in the executable task represents an executable time unit, i.e. the time unit that the task to be scheduled, must execute. Each symbol "a" represents an available time unit. Actually, such representation is repeated indefinitely since the task is periodic. We represent an instance of an executed task by a sequence of symbols "e" followed by a sequence of symbols "a", possibly repeated several times. Each symbol "e" in the executed task represents one executed time unit, i.e. the time unit executed by all the tasks previously scheduled. From the end of the transient phase, given by theorem 1, such representation is repeated according to the LCM of the tasks already scheduled.

The ⊕ operation aims at replacing all the available time units of the executed task (left operand) by the executable time units of the executable task (right operand). In order to make both tasks comparable, first the executable task is repeated according to the number of its instances in the schedulabity interval. Second, the executed task is rewritten according to the number of instances of the executable task in the schedulability interval. Therefore, the task resulting of the ⊕ operation applied to a pair of tasks, is an executed task represented by a sequence of symbols "e" followed by a sequence of symbols "a", possibly repeated several times.

According to these definitions, each task instance of the system Γ 3 is represented as:    τ 1 = {e, e, e, a, a, a, a, a, a, a, a, a, a, a, a} τ 2 = {e, e, a, a, a, a} τ 3 = {e, e, e, e, a, a, a, a, a, a}

The scheduling task result R 3 which describes the schedule of the task system is obtained by the following successive iterations:

R 1 = Λ ⊕ τ 1 R i = R i-1 ⊕ τ i , i = 2, 3
Λ represents a task only composed with symbols "a" since there are no executed time units. R 1 = Λ⊕τ 1 is computed as follows: according to equation 1 we have s ′ 1 = 0 and H 1 = T 1 = 15. Thus, the result of ⊕ applied to the pair (Λ, τ 1 ) is periodic of period H 1 = T 1 and is repeated indefinitely from s ′ 1 . We obtain R 1 by replacing the 3 first available time units of Λ by the 3 executable time units of τ 1 . Then, we have: R 1 = {e, e, e, a, a, a, a, a, a, a, a, a, a, a, a} [0,15]

First iteration:

Computation of R 2 = R 1 ⊕ τ 2 .
Thanks to equation 1, we have:

       s ′ 1 = 0 s ′ 2 = 5 + (0 -5) + 6 • 6 = 5
We have H 2 = lcm(15, 6) = 30, thus the transient phase belongs to the interval [0, 5] and the permanent phase belongs to the interval [START_REF] Burns | Preemptive priority-based scheduling: An appropriate engineering approach[END_REF]35]. In the schedulability interval [0, 35], R 1 is rewritten as follows:

R 1 = {e, e, e, a, a} [0,5] {a, a, a, a, a, a, a, a, a, a, e, e, e, a, a, a, a, a, a, a, a, a, a, a, a, e, e, e, a, a} [START_REF] Burns | Preemptive priority-based scheduling: An appropriate engineering approach[END_REF]35] Task τ 2 begins its execution at t = 5 corresponding to the beginning of the permanent phase. Its number of instances in the schedulability interval is

n 2 = (s ′ 2 +H2)-r 1 2 T2 = (5+30)-5 6 = 30 6 = 5.
According to the number of instances of τ 2 in the schedulability interval, R 1 is rewritten as follows: R 1 = {e, e, e, a, a} [0,5] {a, a, a, a, a, a} {a, a, a, a, e, e, }{e, a, a, a, a, a} {a, a, a, a, a, a}{a, e, e, e, a, a}

(5) R 2 = R 1 ⊕ τ 2 is
obtained by replacing in the equation 5 for each corresponding instance of τ 2 in R 1 , the available time units "a" of R 1 with the executable time units "e", in bold, of τ 2 . During this replacement a preemption of τ 2 by τ 1 corresponds to the transition ("a" → "e"). The preemption of τ 2 by τ 1 is denoted by the time unit "p" called preemption time unit. When τ 2 is preempted, the next available time unit of R 1 after this preemption is replaced by a preemption time unit "p". After replacing all the available time units of τ 1 with the executable time units of τ 2 and after adding the preemption time unit "p" in R 1 , we obtain: R 2 = {e, e, e, a, a} (0,5) {e, e, a, a, a, a} {e, e, a, a, e, e}{e, e, e, a, a, a} {e, e, a, a, a, a}{e, e, e, e, p, e}

For each corresponding instance of τ 2 in R 2 , its PET is given by the sum of the number of its executable time units e, in bold, and the number of its preemptions time unit "p". In the 4 first corresponding instances of τ 2 in R 2 , the PETs are the same and equal to 2 (PET=EET) because τ 2 is not preempted in these instances, but in its 5 th instance, it is preempted once. That is the reason why its PET is equal to 3. In any corresponding instance of τ 2 in R 2 , the PET fits in the available time units left by R 1 in this instance. Thus, the task τ 2 is schedulable while taking into account the exact preemption cost. Actually, we have: R 2 = {e, e, e, a, a} [0,[START_REF] Burns | Preemptive priority-based scheduling: An appropriate engineering approach[END_REF] {e,e,a,a,a,a,e,e,a,a,e,e, e, e, e, a, a, a, e, e, a, a, a, a, e, e, e, e, p, e} [START_REF] Burns | Preemptive priority-based scheduling: An appropriate engineering approach[END_REF]35] The differences with the previous expression of R 2 is that the executable time units "e", in bold, become executed time units "e", and R 2 does not exhibit the corresponding instances of τ 2 .

Second iteration: Computation of R 3 = R 2 ⊕ τ 3 . Thanks to equation 1, we have:

       s ′ 2 = 5 s ′ 3 = 3 + (5 -3) + 10 • 10 = 13
We have H 3 = lcm(lcm [START_REF] Lupu | Multi-criteria evaluation of partitioning schemes for real-time systems[END_REF][START_REF] Wang | Scheduling fixed-priority tasks with preemption threshold[END_REF], 10) = lcm(30, 10) = 30, thus the transient phase belongs to the interval [0, 13] and the permanent phase belongs to the interval [START_REF] Dhall | On a real-time scheduling problem[END_REF]43]. In the schedulability interval [0, 43], R 2 is rewritten as follows:

R 2 = {e, e, e, a, a, e, e, a, a, a, a, e, e} [0,13] {a, a, e, e, e, e, e, a, a, a, e, e, a, a, a, a, e, e, e, e, p, e, e, e, a, a, a, a, e, e} [START_REF] Dhall | On a real-time scheduling problem[END_REF]43] Task τ 3 begins its execution during the transient phase at t = 3 . Its number of instances in the schedulability interval

is n 3 = (s ′ 3 +H3)-r 1 3 T3 = (13+30)-3 10 = 40 10 = 4.
According to the number of instances of τ 3 in the schedulability interval, R 2 is rewritten as follows: R 2 = {e, e, e}{a, a, e, e, a, a, a, a, e, e} [START_REF] Burns | Effective analysis for engineering real-time fixed priority schedulers[END_REF][START_REF] Dhall | On a real-time scheduling problem[END_REF] {a, a, e, e, e, e, e, a, a, a} {e, e, a, a, a, a, e, e, e, e}{p, e, e, e, a, a, a, a, e, e}

R 3 = R 2 ⊕ τ 3 is (6)
obtained by replacing in the equation 6 for each corresponding instance of τ 3 in R 2 , the available time units "a" of R 2 with the executable time units "e", in bold, of τ 3 . During this replacement, a preemption of the task τ 3 by τ 1 or by τ 2 corresponds to a transition ("a" → "e"). When τ 3 is preempted, the next available time unit of R 2 is replaced by a preemption time unit "p". After replacing the available time units of R 2 with the executable time units of τ 3 and after adding the preemption time units "p" in R 2 , we obtain: R 3 = {e, e, e}{e, e, e, e, p, e, e, a, e, e} [START_REF] Burns | Effective analysis for engineering real-time fixed priority schedulers[END_REF][START_REF] Dhall | On a real-time scheduling problem[END_REF] {e, e, e, e, e, e, e, p, e, e}{e, e, e, e, e, e, e, e, e, e} {p, e, e, e, e, e, e, e, e, e} For each corresponding instance of τ 3 in R 3 , its PET is given by the sum of the number of its executable time units "e", in bold, and the number of its preemptions time units "p". In the 2 first corresponding instances of τ 3 in R 3 , the task τ 3 suffers one preemption. Its PETs in every instance are the same and equal to 5. In its other instances there is no preemption of τ 3 and the PETs of τ 3 in these instances are the same and equal to 4 (PET=EET). In any corresponding instance of τ 3 in R 3 , the PET fits in the available time units of R 2 in this instance. Thus, the task τ 3 is schedulable while taking into account the exact preemption cost. Finally, we have: The differences with the previous expression of R 3 is that the executable time units "e", in bold, become executed time units "e", and R 3 does not exhibit the corresponding instances of τ 3 .

Since all the tasks are schedulable then the system Γ 3 = {τ 1 , τ 2 , τ 3 } is schedulable.

Figure 2 presents the result of the schedule of Γ 3 . In this figure, the permanent phase corresponds to the highlighted zone of the schedule and the transient phase corresponds to the interval preceding that zone. The disk represents only the permanent phase in a more compact form. This double representation of the schedule is obtained from the SAS software [START_REF] Yomsi | Improving the quality of control of periodic tasks scheduled by fp with an asynchronous approach[END_REF].

IV. MULTIPROCESSOR SCHEDULING HEURISTIC

The heuristic presented in Algorithm1 is a greedy heuristic. The solution is built step by step. In each step a decision is taken and this decision is never questioned during the following steps (no backtracking). The effectiveness of such a greedy heuristic is based on the decision taken to build a new element of the solution. In our case, the decision is taken according to a cost function which aims at minimizing the load.

A. Cost function

The cost function allows the selection of the best processor p j to schedule a task τ i . In our case, this cost function is the load U * pj (equation 4) of the task τ i and all the tasks already allocated on the processor p j . The processor which minimizes this cost function for τ i among all the processors, is considered to be the best processor to schedule the task τ i .

In the case of the previous example, according to equation 4, the exact permanent load of the system Γ 3 scheduled on a processor p is given by:

U * p = 3 15 + 1 6 • (2 + 2 + 2 + 2 + 3) 5 + 1 10 • (5 + 4 + 4) 3 = 1

B. Principle of our allocation heuristic

We use a "list heuristic" [START_REF] Chandy | A comparison of list schedules for parallel processing systems[END_REF]. In our case, we initialize this list, called the "candidate task system", with the task system given as input. We use for that candidate task system the decreasing order of the task priorities (according to RM fixed-priority scheduling policy [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environnment[END_REF]). At each step of the heuristic, the task with the highest priority is selected among the candidate task system, and we attempt to allocate it to its best processor according to the cost function presented previously. The heuristic minimizes the load U * pj of the task system on the different processors. It is similar to the WF bin-packing heuristic but all the available processors are used rather than the first processors necessary to schedule the task system.

If Γ n is the task system with n tasks and m is the number of processors, the complexity in the worst case of our heuristic is equal to O(n.m.l), with l = lcm{T i : τ i ∈ Γ n }.

Algorithm 1 Greedy heuristic 1: Initialize the candidate task system W with the task system given as input and in the decreasing order of their priorities, initialize the boolean variable T asksSchedulable to true 2: while W is not empty and T asksSchedulable = true do 3:

Select in W the highest priority task τ i 4:

% Verify on each processor p j if task τ i is schedulable.% for j=1 to m do 6:

if task τ i is schedulable on p j with the exact preemption cost (scheduling operation ⊕ [9]) then 7:

Compute the cost function of task τ i on the processor p j , i.e. the load of p j using the equation 4 given in subsection III-B 8:

end if 9:
end for 10:

% Using the cost function again, choose the best processor for τ i among all the processors on which τ i is schedulable.% 11:

if τ i is schedulable on one or several processors then 12:

Schedule the task τ i on the processor which minimizes the cost function 13:

Remove the task τ i from W . T asksSchedulable = f alse 17:

end if 18: end while V. PERFORMANCE ANALYSIS Our heuristic is compared with the B&B exact algorithm and the WF and BF heuristics. The B&B enumerates all the possible solutions in order to find the best solution which minimizes the load of the tasks on the processors. In the B&B, WF and BF heuristics, we use the ⊕ operation presented in Section III-B as the schedulability condition. We compare the algorithms according to their execution time, their success ratio, the response time of the task systems, i.e. the total execution time of the tasks, and the unutilized capacity of the processors used during the allocation.

A. Execution time of the heuristics

We perform two kinds of tests to compare the execution time of the four algorithms. First, we fix the number of processors to 10 and we vary the number of tasks between 100 to 1000 tasks. Every task system is scheduled with the four algorithms and the corresponding execution times are computed. We obtained the results shown in Figure 3. In the second test, we use a single task system composed of 1000 tasks randomly generated and we vary the number of processors. We obtained the results shown in Figure 4.

In both tests, we notice that the exact algorithm explodes very quickly whereas the heuristics keep a reasonable execution time. Our heuristic up to 1000 tasks is close to the WF and BF heuristics in terms of execution time. However, for higher numbers of tasks less good results are obtained with our heuristic. In Figure 4 we also notice that when the number of processors varies, the execution times of WF and BF are constant, because these heuristics use the minimum number of processors. Another remark about Figure 4 is that the execution time of our heuristic does not increase monotonically with the number of processors, in contrast to Figure 3. Indeed, in our heuristic, increasing the number of processors leads to distributing the tasks on all the processors. That increase in terms of processors, can decrease locally the LCM of the tasks on some processors, and consequently can reduce the execution time of the ⊕ operation.

B. Success ratio

In these tests, we compare the success ratio of our heuristic with the B&B exact algorithm and the WF and BF heuristics. The success ratio of an algorithm is defined as follows: Due to the complexity of the B&B and in order to compare it with the heuristics, we executed each algorithm on 6 task systems. Each task system is composed at most of 10 randomly generated tasks and is executed on 2 processors. At each execution we determine for each algorithm the number of schedulable task systems.

As shown in Figure 5, we notice that WF and BF give better results than our heuristic in terms of success ratio. This loss in terms of success ratio is largely compensated by the gain in terms of response time of the task systems and by the unutilized capacity of the processors, as described in the subsections V-C and V-D.

C. Response time of the task systems

In these tests, we consider 10 task systems. The number of tasks in the task systems varies between 100 and 1000 randomly generated tasks and each task system is executed on 10 processors. We limit the tests to the WF and BF heuristics and our proposed heuristic because of the complexity of the B&B exact algorithm and we know that the B&B already gives better results than the heuristics. For each task system, we determine the allocation found by each heuristic and for this allocation the response time of the task system, i.e., the total execution time of all the tasks, is computed. We compare the response time of the task systems between the heuristics, as shown in Figure 6.

In this figure, we notice that the allocation found by our heuristic gives a better response time than those found by WF and BF. This is due to the fact that the execution of the tasks is parallelized on all the available processors whereas WF and BF attempts to reduce the number of processors rather than parallelize the execution of the tasks.

D. Average of the unutilized capacity of the processors

In these tests, we consider 10 task systems. The number of tasks in the task systems varies between 100 and 1000 randomly generated tasks and each task system is executed on 10 processors. We limit the tests to the WF and BF heuristics and our proposed heuristic because of the complexity of the B&B exact algorithm. In addition, we know that the B&B already gives better results than the heuristics. For each task system we determine the allocation found by each heuristic and for this allocation we compute the average of the remaining processor load (1 -U pj ), called untilized capacity, on the processors p j used in this allocation. We compare the unutilized capacity of the processors used with the heuristics as shown in Figure 7.

In this figure, we observe that the allocation found by our heursitic gives for each processor more flexibility, i.e., more unutilized capacity, than those found by WF and BF. This is due to the fact that our heuristic balances the load on all the available processors, which ensures an execution time slack, whereas the BF heuristic fills the processors as much as possible, which that increases the risk of non schedulabily of a task system at run-time. On the other hand, the WF heuristic, balances the load only on the processors already used and does not consider all the available processors.

VI. CONCLUSION AND FUTURE WORK

In this paper, we have presented a greedy heuristic which allocates and schedules, on a multiprocessor architecture, a system of real-time tasks while balancing the load on the processors. In addition, this heuristic takes into account the exact preemption cost that must be carefully considered in safety critical applications, which is the focus of our work.

We have carried out a performance analysis showing that, up to 1000 tasks, the proposed greedy heuristic, has results close to those of the WF and BF heuristics in terms of execution time. For higher number of tasks less good results can be obtained with our heuristic. On the other, hand the proposed heuristic is better than the WF and BF heuristic in terms of load balancing and flexibility, i.e., more not-utilized capacity, of tasks at run-time. Also the allocation found with our heuristic has better response time than those with WF and BF heuristics.

In future works, we plan to study the multiprocessor realtime scheduling of dependent tasks which leads to deal with data transfers and shared data management.

R 3 =

 3 {e, e, e, e, e, e, e, p, e, e, a, e, e} [0,13] {, e, e, e, e, e, e, e, p, e, e, e, e, e, e, e, e, e, e, e, e, p, e, e, e, e, e, e, e, e, e}[START_REF] Dhall | On a real-time scheduling problem[END_REF]43]

Figure 2 .

 2 Figure 2. Result of the scheduling of Γ 3 , taking into account the exact preemption cost

Figure 3 .

 3 Figure 3. Execution time of the algorithms according the number of tasks

Figure 4 .

 4 Figure 4. Execution time of the algorithms according to the number of processors

Figure 5 .

 5 Figure 5. Sucess ratio

Figure 6 .

 6 Figure 6. Execution time of the task systems

Figure 7 .

 7 Figure 7. Average of (1-load) on the processors used


P Andre

J Aubreton

M Lino

Da Silva

M Dudeck

M F Elchinger

B Lopez

DISCUSSION ON THE COMPOSITION AND TRANSPORT COEFFICIENTS CALCULATION MADE IN PLASMA OUT OF EQUILIBRIUM

In this paper, the composition calculation in plasma out of thermal equilibrium is discussed and we test the viscosity formulations of Wilke, Gupta et al, Chapman Enskog and Sutherland in air plasma out of thermal equilibrium. Finally we applied the formulations to Fire II reentry.

1.

INTRODUCTION

In a first step from the H theorem we discuss the composition obtaining in plasma out of thermal equilibrium. We apply the method to the air plasma. In a second step we discuss the viscosity formulation given by Wilke [1], Gupta et al [2], Sutherland [3] and by Chapman Enskog [4]. Finally we apply them to stagnation line of FIRE II reentry (Earth reentry -1965).

COMPOSITION CALCULATION.

The calculation of composition made in plasma out of thermal equilibrium is debatable, several methods can be used as pseudo kinetic method [5], maximization of entropy method [6], Gibbs free energy minimization [7], mass action laws [8,9], state to state methods [START_REF] Lino | Simulation des propriétés radiatives du plasma entourant un véhicule traversant une atmosphère planétaire à vitesse hypersonique[END_REF]. It seems interesting to start both for the composition and for transport coefficients from the same formulation, respectively the Boltzmann equation and the Boltzmann's H-theorem. As a matter of fact, taking account that the methods classically used to determine the transport coefficients that is to say Chapman Enskog or Grad methods [START_REF] Hischfelder | Molecular theory of gases and liquids[END_REF], begin the calculation with the Boltzmann equation [START_REF] Hischfelder | Molecular theory of gases and liquids[END_REF]:

( )

j ij j j i j i i i i i i i i v d d db b g f f f f v f X m r f v t f r r r r r ε ∑ - ∫∫∫ =         ∂ ∂ +         ∂ ∂ + ∂ ∂ ' ' . 1 .
(1)

where ( )

t v r f i i , , r r
is the distribution function i X r is an external force applied on the particle of the i th species, b is the impact parameter,

i i i f f φ + = 1 0
. This latter assume that the external forces is low enough to consider only a small perturbation of the distribution function. Following the Chapman Enskog resolution and taking Sonine polynomials one can obtain integral series depending of integral cross sections [4]. The H-theorem, or Boltzmann's H-theorem, is a demonstration of the tendency of the particles of an isolated system to approach their equilibrium distribution. The H-function for a mixture of species i with distribution functions ( )

t v r f i i , , r r ,
where r r is the position, i v r is the velocity of species i, and t is the time, is defined as:

( ) ( ) ( ) [ ] r d v d t v r f t v r f t H i i i i i i r r r r r r , , ln , , ∑ ∫ ∫ = (2) It can be shown that k S H v - =
, where v S is the entropy per unit volume, and k is Boltzmann's constant. The H-function can be viewed as generalization of the entropy, since, unlike entropy defined on a strictly thermodynamic basis, it is defined in non-equilibrium situations. The Htheorem states that 0 ≤ dt dH for an isolated system, and is hence a statement of the second law of thermodynamics it can be deduced that (3) where S is the entropy of the whole system, int i S is the entropy related to the distribution function and exchanges between the different species during collisions, and ext i S is the entropy related to the external forces and gradients. In equilibrium, the entropy of the total system, taking into account external forces and gradients, is stable in time. However, it is not possible to draw any conclusions about the evolution of int i

j i T T = , i.e.,

S

or

∑ i i S int .
The calculation shows that minimization of free energy or internal energy is an appropriate method for calculating the composition of a multi-temperature plasma that is stable in time. This result is in accordance with that of Giordano and Capitelli [6].

To use the Chapman Enskog method, we have to assume that the external force is sufficiently low to be considered as a perturbation function and high enough to create a thermal non equilibrium between electrons and heavy species temperature. We have to notice that the latter remarks imply that the plasma is at chemical equilibrium. So we decided to calculate the composition with the Gibbs free energy method. The first limitation is how to calculate the partition function for diatomic species as a matter of fact the partition function is written as

∑ - + ∑ - ∑ - = max max int / ) ( ) 1 2 ( / ) ( / j j v v e
                  = ∑ - + ∑ - ∑ - = = ) 0 max( 0 ) 1 max( 0 int / ) ( 0 ) 1 2 ( / ) ( 1 / j j v v e e rot kT j cF h e j vib kT v cG h ex kT e cT h e e g Z
We have to notice that some authors propose series development to calculate the internal partition see for example [START_REF] Faure | Partition functions for diatomic molecules in plasmas out of thermal equilibrium[END_REF] and literature inside. In the case of plasma out of chemical equilibrium and out of thermal equilibrium the plasma reach a composition at chemical equilibrium but can be out of thermal equilibrium. So we have to consider the external constraints [6] and the hypothesis on the internal temperatures [START_REF] Andre | Numerical Method and Composition at and out of Chemical Equilibrium in a Multitemperature Plasma. Application to a Pure Nitrogen Plasma[END_REF]. In figure 1 we show the composition versus time with a model with 34 reactions [START_REF] Dudeck | Thermodynamics equilibrium and non equilibrium of plasma flows[END_REF] that reach an air plasma out of

thermal equilibrium ( 2 = = H e T T θ
) at T H = 3000 K and at atmospheric pressure for air. The temperatures T e , T H are frozen during the time evolution. We have to note that usually the coefficients rates are not known precisely a factor of one thousand can exist between authors so the inverse reaction coefficients rate are estimated with the chemical equilibrium coefficients. The chemical equilibrium is reach around a time of 10 ms for the main neutral chemical species. However the densities of charged particles continue to increase but with very low concentrations. In the two figures 2 and 3, we represent the composition at chemical equilibrium successively at thermal equilibrium and out of thermal equilibrium obtained by the Gibbs free energy method. Since the energy inside the plasma is higher for a given heavy species temperature the ionization is made at lower temperature. The dissociation is made at lower temperature since the hypothesis on internal temperature is As classic result, the species with a double charge will appear at a greater energy.

TRANSPORT COEFFICIENTS.

In a previous work [4] new transport coefficients in plasma out of thermal equilibrium have been developed. In a recent work [START_REF] Colombo | Two-temperature thermodynamic and transport properties of carbon-oxygen plasmas[END_REF] Colombo and al claim that the results of viscosity are similar between this method and those developed at thermal equilibrium. Taking into account the fact that in plasma modeling it is useful to use fast and quite accurate formulations as those from Wilke [1], Sutherland [3], Gupta and al [2]. It would be interesting to test the formulation used for numerical purpose in the case of plasma out of thermal equilibrium. The viscosity equation of gas has been given by Wilke in 1950 [1] for a mixture in thermal equilibrium. He proposed a simple and convenient formulation in numerical used. It is used until now:

∑ ∑ = ≠ = + = N i N i j j ij j i i Wilke x x 1 , 1 1 1 φ µ µ (4)
where i x is the molar fraction of i chemical species, N the number of chemical species taken into account, i µ is the viscosity of chemical species i given by :

( ) [ ] C B T A i + + = ) ( ln exp 1 . 0 µ
The coefficients A, B and C are Blottner coefficients and be find in several work, we used those given in [START_REF] Leonardo | Numerical simulation of weakly ionized hypersonic flow over reentry capsules[END_REF] and report in table 1. The coefficient ij φ is given by: The Gupta, Yos, Thompson and Lee approach [2] used the formulation given in [START_REF] Hischfelder | Molecular theory of gases and liquids[END_REF] for individual viscosity of each chemical species i µ :

2 1 4 1 2 1 1 2 4 1 2             +                           + = i j i j j i ij M M M M µ µ φ (4
∑ = = N i i i al et Gupta x 1 _ _ µ µ (6)
At thermal equilibrium, with Chapman Enskog method one can reach more accurate transport coefficients. The interaction potential of each collision has to be known precisely: neutral neutral, charged-charged, charged-neutral, electron-neutral [START_REF] Andre | Transport coefficients in thermal plasma. Applications to Mars and Titan atmospheres[END_REF][START_REF] D'angola | A phenomenological approach for the transport properties of air[END_REF]. We have to note that usually a Coulombian shielded potential depending on the Debye length is used for the charged-charged interaction. So, all the interactions between charged particles are identical consequently, we have to find the same viscosity for charged particle. This is not observed in table 1. So we compare the individual viscosity between authors in figure 4 and5. In figure 4, we show the viscosity for N 2 versus temperature and in figure 5 the viscosity for N + versus temperature. For the ions, one can note the large difference of values from Wilke, Gupta and our calculation. Generally, the viscosities of the neutral species are within the same order of magnitude between authors unlike for the ions and electrons. So we propose new Blottner coefficients for charged particles A=-0.769; B=17.4 and C=-106 giving a convenient approximation of the results obtained by the Chapman-Enskog method and able to be easily used in numerical codes. The curves with this set of values are indicated as "Wilke (new)". In figure 6, we have plotted the viscosity at atmospheric pressure and at thermal equilibrium using the various data. In the considered temperature range at thermal equilibrium the results are quiet similar unlike in plasma out of thermal equilibrium represented in figure 7. At high temperature the behavior of the viscosity is strongly depending of the model (figure 7). The viscosity is continually increasing with the models of Wilke (table 1) and Sutherland when its is decreasing after 6000K for the models of Gupta and Chapman Enskog. By comparing the figure 6 and 7 with figures 4 and 5, we observe that the differences are mainly observed when the ionization is made. Consequently, the errors in viscosities are due to the interaction between ionized particles. As a matter of fact classically the Coulombian interaction depends on the Debye that depends on composition.

The FIRE II mission has been done in May 1965 to analyze the radiation heating during an Earth reentry. In figure 8, we have plotted the composition on the stagnation lines in FIRE II reentry [START_REF] Savajano | Radiation analysis for two trajectory points of the Fire II entry[END_REF]. The viscosity obtained through the stagnation is reported in figure 9. We show large discrepancies between the Wilke formulations using the two set of Blottner coefficients. This result suggests that the hydrodynamic models of the plasma flow around the probe could be reexamined with the use of transport coefficients from Chapman-Enskog-Wilke model.

CONCLUSION

Through this paper several questions arise: how can we calculate accurately the diatomic partition function in plasma out of equilibrium? What are the influences of non Bolzmann distribution on the transport coefficients? The applied forces have to be high enough to get plasma out of thermal equilibrium but low enough to use the Chapman Enskog method. How can we check the validity of Chapman Enskog approach?

We have shown that the chemical models using chemical rates as in collisional radiative models have to take good equilibrium constant. That is to say these equilibrium constants have to be calculated taking external constraints and hypotheses on internal temperatures. This is usually not the case. 4. Rat V., Andre P., Aubreton J., Elchinger M. F., Fauchais P., Lefort A., (2001) Transport properties in a two-temperature plasma: Theory and application, Physical Review E, 64, 026409. 5. Rat V., Andre P., Aubreton J., Elchinger M. F., Fauchais P. and Lefort A., (2001) A modified pseudo-equilibrium model competing with kinetic models to determine the composition of a twotemperature SF 6 atmosphere plasma, J. Phys. D: Appl. Phys. ( 34

g

  is the initial relative velocity, and ε is the angle over which integration takes place. The resolution of Boltzmann equation by Chapman Enskog, introduce a perturbation function i φ as ( )

  Figure 1: Air Composition versus time

  upper quantum energy level of molecules are statistically more populated so the ionization is made at lower heavy species temperature.

Figure 3 .

 3 Figure 2. Air Composition at thermal equilibrium

C

  µ are fitting coefficients given in[2]. And finally the total viscosity of the plasma is:

Figure 4 .

 4 Figure 4. Individual viscosity of diatomic nitrogen N2.

Figure 5 .

 5 Figure 5. Individual viscosity of nitrogen ions N + .

Figure 7 .

 7 Figure 6. Viscosity at thermal equilibrium

Figure 8 .Figure 9 .

 89 Figure 8. Composition on stagnation line. The stagnation points located at 0.

  ) 2191. 6. Giordano D. and Capitelli M., (2001) Nonuniqueness of the two temperature Saha equation and related considerations, Physical Review E, (65), 016401. 7. Andre P., (1997), Partition functions and concentrations in plasmas out of thermal equilibrium, Plasma Science, IEEE Transactions on Plasma Sciences, 23 (3), 453-458. 8. Potapov A.V. (1966), Chemical equilibrium of multitemperature systems, High Temp, 4, 48-51.

  Furthermore, we have tested several approaches to determine the viscosity. If the plasma is out of thermal equilibrium, we have shown that if the plasma is highly ionized at low heavy species temperature Wilke formulation using Blottner coefficients cannot be used. Surprisingly, it is used in several calculation code of fluid dynamic without any comments. Comparing with Chapman Enskog methods, Gupta and al approach seems to give better results. So in a future work, we have to test the sensitivity of a fluid calculation code to transport coefficients. We have also to pursue the work by including a state to state model to determine the transport coefficients taking each quantum level into account. Wilke C.R. (1950) A Viscosity Equation for Gas Mixtures, The Journal of Chemical Physics, 18(4), 517-519. 2. Gupta R.N., Yos J.M., Thompson R.A., Lee K.P., (1990), A review of reaction rates and thermodynamic and transport properties for an 11 species Air Model for Chemical and thermal nonequilibrium calculations to 30000 K., NASA

	5.	REFERENCES
	1. Reference Publication 1232.
	3. Lopez B. (2010), Développement d'un code
	d'aérothermique	pour	la	simulation	des
	écoulements	hypersoniques	hors	équilibre
	thermochimique, Thesis, Orléans University in
	French.