Houssam Eddine Zahaf

Richard Olejnik

Elhassen Abou

Benyamina

Giuseppe Lipari

Energy-aware Real-Time Task Decomposition for partitioned-EDF Scheduling on Multi-core Uniform Architectures

Keywords: Power, Real-Time, Parallel, Frequency, Periodic tasks, Partitionned, Decomposition

Modern multi-core embedded processors allow to implement increasingly complex processing applications, as any processing of large amount of data. Many of these are submitted to timing constraints, and can be implemented as parallel tasks by taking advantage of a multi-core architecture. However a careless implementation can waste precious energy, especially when processing elements are powered by batteries. Thus, It is necessary to calibrate the operational frequency and voltage of the processors so that the consumed energy is reduced while still meeting the timing requirements.

In this paper, we explore the design choices in implementing parallel realtime applications on multi-core systems. We propose a realistic parallel realtime task model, NLP formulation and some heuristics for allocating threads to processors and selecting in offline their operational frequency. Experimental results with synthetic tasks sets show that it is time consuming to use NLPsolvers and that our heuristics are effective in reducing the power consumption.

Introduction

Power consumption is an increasing concern in cyber-physical real-time systems, especially when processing elements operate on battery power. Embedded Preprint submitted to Journal Of parallel and distributed computing: Special Edition E2MC2December 15, 2015 real-time distributed systems must support increasingly complex applications such as distributed video surveillance, collection and analysis of a large amount of sensor data, etc.

To reduce the network traffic, instead of collecting and sending all data to a remote central server, a part of the processing is done on-site with mediumsize embedded computing boards, so that only a small part of preprocessed data needs to be sent. For example, instead of sending the full video frames, a surveillance system analyses them on-site by extracting the important features, and sends only the features for further processing in the central site. This model of computation is now known as "Fog-computing" [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF].

The embedded platforms used for supporting fog computing are often multicore systems and many of these applications can be easily parallelised by distributing data across the parallel computing elements. Reducing power consumption in these systems is a very serious problem when they are operated by batteries. Even when they are connected to the electric grid, we need to keep the consumption as low as it is possible. Multicore technology can help us in achieving timeliness and low power consumption: in fact, even when the computational load is not very high, multicore processors are more energy efficient than an equivalent single-core platform [START_REF] Wolf | Computers as components: principles of embedded computing system design[END_REF]. The idea is to operate the system at a lower frequency and at the same time reduce the response time by decomposing the tasks into parallel threads to be partitioned across the cores.

Task decomposition is a well-known problem in the parallel programming community. For example, OpenMP [START_REF] Chandra | Parallel programming in OpenMP[END_REF] is an API specification for parallel programming. The section of code that is meant to run in parallel is marked with a pre-compiler directive. One example of such directive is the pragma parallel for. In the OpenMP parallel model, a parallel for loop preceded by the STATIC schedule clause is implemented by distributing the N iteration on p threads into approximately N p iterations per each thread (if no further specification is implied). After the execution of the parallelized code, the threads join back into the master thread, which continues onward to the end of the program. However, this task decomposition does not take into account the task scheduling, the respect of the real-time and energy constraints and the processor frequency definition. In this work we adress these problems.

Goossens et al. in [START_REF] Goossens | Gang ftp scheduling of periodic and parallel rigid real-time tasks[END_REF] classified parallel real-time task models according to the way the level of parallelism is specified and to the moment of this specification.

We can distinguish three types of models:

• rigid : the number of processors assigned to the task is specified independently before the scheduling analysis and does never change;

• moldable: the number of processors assigned to the task is specified off-line using an off-line analysis algorithm, for example during pre-processing or compilation and does not change after;

• malleable: the number of processors assigned to the task may dynamically change during execution.

According to [START_REF] Drozdowski | Scheduling Parallel Tasks Algorithms and Complexity, chapter 25. Handbook of SCHEDULING Algorithms, Models and Performance Analysis[END_REF][START_REF] Mounie | Scheduling Parallel Tasks Approximation Algorithms[END_REF], most parallel applications in the real world are moldable.

Hence we decided to focus our work on moldable real-time tasks.

Contributions of this paper.. This work focuses on intra-task parallelism to reduce energy consumption while respecting timing constraints. We select in off-line the frequencies of the core-groups of a multi-core platforms, by means of schedulability analysis. We propose a parallel task model that accounts for decomposition overhead and different discrete operating frequencies. The problem of finding an optimal solution is very complex, so we propose heuristic algorithms to achieve a good compromise between precision of the solution and running-time of the analysis.

Paper structuring.. The rest of the paper is structured as follows. In Section 2, we discuss the related works. Section 3 is dedicated to describing the model of the system and the problem formulation. We present allocation and frequency definition algorithms in Section 5. The experimental results are discussed in Section 6. Finally, in Section 7 we present our conclusions.

Related work

In the real-time systems literature, a lot of works [START_REF] Bini | Speed modulation in energy-aware realtime systems[END_REF][START_REF] Jejurikar | Leakage aware dynamic voltage scaling for real-time embedded systems[END_REF][START_REF] Pillai | Real-time dynamic voltage scaling for low-power embedded operating systems[END_REF][START_REF] Chen | Energy-efficient scheduling for real-time systems on dynamic voltage scaling (dvs) platforms[END_REF][START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF] focused on static and dynamic Voltage and Frequency scaling for uni-processor architectures, and recently some researchers proposed similar techniques for homogeneous multiprocessors architectures.

Bini et al. [START_REF] Bini | Speed modulation in energy-aware realtime systems[END_REF] proposed a semi-linear model for the variation of the execution of a task τ i , which we use in our own task model (see Section 3). They also proposed an algorithm to set the minimum processor frequency on single processor architectures, so that all the deadlines are respected.

Concerning real-time parallel task scheduling on multi-processors, many papers (e.g. [START_REF] Lakshmanan | Scheduling parallel realtime tasks on multi-core processors[END_REF][START_REF] Courbin | Scheduling of hard real-time multi-phase multi-thread (MPMT) periodic tasks[END_REF][START_REF] Kato | Gang EDF scheduling of parallel task systems[END_REF][START_REF] Manimaran | A new approach for scheduling of parallelizable tasks in real-time multiprocessor systems[END_REF][START_REF] Han | Predictability of least laxity first scheduling algorithm on multiprocessor real-time systems[END_REF][START_REF] Collette | Integrating job parallelism in real-time scheduling theory[END_REF][START_REF] Saifullah | Multi-core real-time scheduling for generalized parallel task models[END_REF]) focused on the intra-task parallelism, without considering energy-aware scheduling. Kato et al. [START_REF] Kato | Gang EDF scheduling of parallel task systems[END_REF] proposed the gang task model. A task is defined by the number of processors used simultaneously, its execution time and the deadline that must be lower than the period (constrainned deadline). All threads of a parallel section in a gang model have to be run in parallel (they must start and stop the execution on their processors simultaneously). However, this model is more difficult to implement, because the scheduler needs to synchronize the execution of the threads among different processors. A different model, easier to implement, is the multi-thread model, where parallel threads are scheduled independently, and in this work we will adopt this model. Lakshmanan et al. [START_REF] Lakshmanan | Scheduling parallel realtime tasks on multi-core processors[END_REF] proposed a fork-join model for representing parallel tasks: each task is a sequence of alternating parallel and sequential segments. Saifullah et al. [START_REF] Saifullah | Multi-core real-time scheduling for generalized parallel task models[END_REF] proposed a parallel task model where a task is composed of segments, and each segments consists of a set parallel threads with the same real time characteristics (e.g. release time, execution time, deadline). At the end of each segment, parallel threads must synchronize. They also proposed a method to adapt other task models to their model. [START_REF] Courbin | Scheduling of hard real-time multi-phase multi-thread (MPMT) periodic tasks[END_REF] proposed a less restrictive model where parallel sub-tasks of each phase 1 have independent real time characteristics. They state that the model proposed in [START_REF] Saifullah | Multi-core real-time scheduling for generalized parallel task models[END_REF] is a specific case of their model. They also proposed an algorithm to assign real time parameters to a fork-join model in order to adapt it to their model called Multi-phase Multi-Thread. These papers [START_REF] Courbin | Scheduling of hard real-time multi-phase multi-thread (MPMT) periodic tasks[END_REF][START_REF] Saifullah | Multi-core real-time scheduling for generalized parallel task models[END_REF][START_REF] Lakshmanan | Scheduling parallel realtime tasks on multi-core processors[END_REF] only address the scheduling problem of parallel task, without considering the energy consumption problem.

Courbin and Goossens

Fisher et al. in [START_REF] Fisher | Energy minimization for parallel real-time systems with malleable jobs and homogeneous frequencies[END_REF] defined the optimal frequency for minimizing energy consumption on homogeneous platforms with malleable tasks (see Section 3).

They target homogeneous processor platforms with the ability of turning off some processors. They considered sporadic implicit deadline tasks and use a canonical parallel scheduler proposed in [START_REF] Collette | Integrating job parallelism in real-time scheduling theory[END_REF], which is an optimal scheduling algorithm for sporadic tasks on homogeneous multiprocessor platforms. We propose a similar approach, but we apply it on uniform multiprocessors and a different task model.

System Model

Task Model

Let T = {τ 1 , τ 2 , . . . , τ n } be a set of periodic moldable independent tasks. Every task τ i is characterised by the tuple τ i = (O i , D i , T i , Γ i ), where:

• O i is the offset. It represents the release time of the first instance of the task τ i . If ∀i, O i = 0, then the task set is synchronous.

• D i is the task's relative deadline, we consider tasks with D i less than T i .

• T i : is the task's period, that means the time between the releases of two consecutive instances of task τ i .

• Γ i is the task's set of k cut-points, Γ i = {γ i,1 , . . . , γ i,Ki }. Each cut-point γ i,k = {Th i,k,1 , Th i,k,2 , . . .} is itself a list of

parallel threads, and it rep-

1 A phase is equivalent to a segment resents one possible parallel decomposition of the task τ i into parallel threads. We denote as |γ i,k | the number of threads in the cut-point.

Each thread Th i,k,z has the same period and the same relative deadline of the task to which it belongs. In this work, we assume that the worst case execution time (C) of every thread depends on the operating frequency of the processor on which it has been allocated:

C i,k,z (f p ) = ct i,k,z (f p ) + mt i,k,z , where ct i,k,z (f p )
is the part of the computation time that depends on the processor frequency and mt i,k,z is the part that does not depend on the processor frequency (e.g. due to central memory accesses), So each thread is defined Th(ct, mt). This model is similar to the one proposed by Bini et al in [START_REF] Bini | Speed modulation in energy-aware realtime systems[END_REF]. In particular, we use a semi-linear model:

C i,k,z (f p ) = ct i,k,z s p + mt i,k,z (1)
where s p = f p /f max is the core speed (or relative frequency) of the core where the task is executing. We denote by C i,k = z C i,k,z (f p ) the sum of the execution times of the threads in the cut-point γ i,k . For every possible combination of operating frequencies, we assume that C i,k is monotonic non decreasing with the number of threads in the cut-point. In other words, using more threads implies a larger overhead, due to several factors: synchronisation, caches, conflicts in accessing the memory bus. Under this assumption, it does not make sense to

have |γ i,k | > m.
For example, consider task τ 1 = (O 1 = 0, D i = 11, T i = 15, Γ 1 ), Γ 1 consists of 3 cut-points (see Fig. 1): Notice that we allow different values of ct and mt among parallel threads belonging to the same cut-point; and we allow many cut points with the same number of threads. Thus, this model is quite general and can be used to represent alternative decompositions for the same level of parallelism.

• γ 1,1 = {Th 1,1,1 (11, 6)}, • γ 1,2 {Th 1,2,1 (6, 3); Th 1,2,2 (6, 4)}, • γ 1,3 = {Th 1,3,1 (2, 4); Th 1,3,2 (6, 2

Uniform architectures and Power Model

In this paper we address uniform multi-core architectures. In this kind of architectures, cores have the same instruction set, and they may differ on their operating frequencies. We assume that the architecture supports voltage and frequency scaling technology, which allows tasks to run at different frequencies/speeds, and that each core has a discrete set of operating frequencies.

The execution time of a task does not depend only on the core speed. Seth et al. [START_REF] Seth | Fast: Frequencyaware static timing analysis[END_REF] noticed that not all the task execution times scale on the core speed (i.e. frequency) because some part of the code deals with the memory and I/O devices.

In order to validate these assumptions, we implemented a simple benchmark consisting of the multiplication of two matrices of 300 × 300. We implemented the task and run it on a Linux OS running on a i3-3217U processor from Intel.

The system has 3Mb of cache memory, two physical cores, each one hosting 2 logical cores by using hyper-threading. The frequency of each physical core can be set independently from 800 MHz to 1800 MHz. The task is implemented in C with using directly the Pthread library and it is decomposed into a set of n threads, with n varying between [START_REF] Bonomi | Fog computing and its role in the internet of things[END_REF][START_REF] Wolf | Computers as components: principles of embedded computing system design[END_REF][START_REF] Goossens | Gang ftp scheduling of periodic and parallel rigid real-time tasks[END_REF][START_REF] Mounie | Scheduling Parallel Tasks Approximation Algorithms[END_REF][START_REF] Jejurikar | Leakage aware dynamic voltage scaling for real-time embedded systems[END_REF]. Each thread process one portion of the matrix, and the decomposition is fair: all threads process approximately 300/n lines. The task is periodic with a period of T = 200 msec. Finally, other tasks in the system run with non-real-time priority trying to load the cache and the sytem.

Energy Consumption

In CMOS circuits, we distinguish between dynamic power consumption, that is the power dissipation due to switching, and static power consumption, mostly due to leakage current dissipated in electronic components like capacitance and transistors.

Jing Mie et al. [START_REF] Mei | Energy-aware preemptive scheduling algorithm for sporadic tasks on DVS platform[END_REF] defined the dynamic power dissipated by a CMOS circuit as the product of a constant coefficient that depends on the technology used ξ, by the square of the voltage, and by the frequency.

E = ξ × V 2 × f (2)
They also defined the frequency as the ratio of the difference between the actual voltage V and V T h raised to the power of a, where V th is the threshold voltage by the product of a constant K and the logic depth L d . a and K are constants that depend on the technology.

f = (V -V T h ) a K × L d (3)
By combining the two equations, the consumed energy E can be expressed as the product of a constant Const by the frequency f power λ (4). We will use this equation to compute the dissipated energy in Section 4.

E(f ) = Const × f λ (4)

Scheduling

In this paper we assume a partitioned Earliest Deadline First (EDF) scheduling. Each core has its own single-processor EDF scheduler and a separate ready-queue. Therefore the scheduling analysis can be performed with wellknow techniques for single-processor scheduling. We assume that all tasks are independent of each other, whereas threads belonging to the same tasks and running on different cores need to synchronize their activation times and deadlines.

The scheduling analysis is based on the well know demand-based analysis.

Let T p denote a task set of n periodic tasks allocated on the same core, T = {τ 1 , τ 2 , . . . , τ n }, and let t be a non-negative integer. The Demand bound function dbf(T , t) denotes the maximum cumulative execution requirement that could be generated by jobs of T p that have both ready times and deadlines within any time interval of duration [0 -t]. Equation ( 5) describes the formula for computing the dbf:

dbf(T p , t) = Thi∈Tp t + T i -D i T i C i (5)
Notice that C i denotes generically the computation time of the thread, and of course it depends on the frequency at which the core is operated, as described in Equation (1).

To be schedulable under EDF, the dbf value of a task set T p at each moment of time t 0 , must be equal or less than t 0 (Equation 6).

∀t 0 ≤ t * , dbf(T p , t 0 ) ≤ t 0 (6)
where t * is a constant that depends on the utilisation of the task set (see [START_REF] Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[END_REF] for more details on the analysis algorithm).

Problem formulation

In order to compare our scheduling and frequency heuristics to optimal ones, we formulate our problem as a non linear optimisation problem, We use the the follow acronyms in problem definition:

• L : it the number of core groups;

• h: is the hyper period of tasks, and it is computed as least common multiple of all periods of tasks;

• f l : is the operating frequency of a core in group l;

• s l : is the speed of a core in group l;

• dbf i,k,z (s p , t): is the value of the demand bound function of thread Th i,k,z when allocated on a core p with speed s p at time t.

Let T = {τ 1 , τ 2 , . . . , τ n } a task set of n periodic tasks on a uniform architecture of m cores. We define the binary variable x i,k,z,p as:

   1 if thread Th i,k,z is allocated on core p 0 otherwise
We assume that the cores of each group are indexed alternatively with the next groups. For example, in an architecture of m = 12 cores with three groups, the cores of group l 0 are indexed as 0, 3, 6, 9, those of l 1 are indexed as 1, 4, 7, 10, and those of l 2 are indexed 2, 5, 8, 11. Thus, the group of core p is l p = p%L.

Given these definitions, we now present one formulation of the problem as a Non-Linear Programming problem:

min E = ξ n i=1 m p=1 K k=1 z k z=1 f 3 lp × ( ct ikz s lp + mt ikz ) × x i,k,z,p (7)
subject to the following constraints:

m j=1 K k=1 m z=1 x i,k,z,p = m ∀i (8)
n i=1 dbf i,k,z (s p , t)x i,k,z,p ≤ t ∀p, t ∈ [0 -h] (9)
x i,k,z,p + x i,k ,z ,p ≤ 1, ∀i, k, z, p, k > k, z , p (10)
m j=1 x i,k,z,p ≤ 1, ∀i, k, z (11)
To grant the respect of the schedulability of each task set T p on core p at each time t, the dbf must verify Condition [START_REF] Pillai | Real-time dynamic voltage scaling for low-power embedded operating systems[END_REF]. Constraint [START_REF] Jejurikar | Leakage aware dynamic voltage scaling for real-time embedded systems[END_REF] expresses that all threads of the same cut point must be scheduled. A correct solution of the problem must verify that all the threads of the same task belong to the same cut-point. We express this as a conflict constraint which mean that whenever a cut-point is choosen, all the other cut-points are ignored. (Constraint [START_REF] Chen | Energy-efficient scheduling for real-time systems on dynamic voltage scaling (dvs) platforms[END_REF]).

Finally, we must verify that each thread is allocated on only one core (Constraint [START_REF] Zhu | The effects of energy management on reliability in real-time embedded systems[END_REF]).

There are many NLP solvers, both freely available as open source software, and commercial ones. We used CPLEX [START_REF] Cplex | .0 users manual[END_REF] and Knitro [START_REF] Byrd | Knitro: An integrated package for nonlinear optimization[END_REF] solvers with academic licences. Unfortunately the problem at hand is a very complicated combinatorial problem, and a small example with 3 task with 5 cut-points per each task, to be executed on 4 cores with 10 frequency levels, takes several hours.

We believe that it is impractical to use a NLP solver for this kind of problems.

Thus, in this paper we propose heuristics to obtain quasi-optimal solutions in a reasonable time. In the next section we present our heuristic algorithms.

Partitioning

In this section we propose some heuristics for solving the problem approximately in a reasonable time. Our algorithm:

• selects the level of decomposition for each task by selecting the cut-points;

• selects the frequency for each core group;

• assigns threads to cores; so to minimise energy consumption while guaranteeing that all deadlines are respected.

Let T = {τ 1 , τ 1 , . . . , τ n } be a set of n tasks. We start by defining the baseline utilisation for each task as U i = Ci Ti , where C i is the WCET of the single-thread cut-point, considering a processor of speed 1. Then U = i U i is the baseline utilisation of the system.

We also define S the cumulative strength of the our architecture, that is the sum of all processors speed: S = m j=1 s j ). To be schedulable, the following necessary condition must hold:

U ≤ m p=1 s lp (12)
We will use a classical "greedy" approach. We start by analysing frequency configuration having the minimal strength that verifies Equation ( 12), then we do partitioning and we check the schedulability. If no feasible solution can be found, we keep increasing the strength until we find a feasible partitioning.

Before explaining our algorithm in more details, we need to introduce some more definitions.

• m l is the number of cores in group l;

• act l is the number of active cores in group l

• sl l is the lower bound speed of the cores in group l

• sh l is the upper bound speed of the cores in group l

• so l is the operating speed of group l

• S l is the cumulative strength of group l, S l = m l s l Step, then it selects the frequencies of all groups by invoking Algorithm 2, and finally it and allocates the threads and checks schedulability by invoking Algorithm 5. It returns true as soon as it finds a feasible solution. In the next subsection we will explain the algorithm for assigning the frequencies and allocating the tasks.

Frequency selection

The goal of this step is to select the frequency of each core group, so that the cumulative strength of the platform equals to S temp . We need also to respect the frequency bounds for each group. We assume that groups are ordered by increasing maximal frequency, so that less powerful groups are loaded by threads before higher frequency groups.

The heuristic returns the operating frequency so l and the number of active cores act l of each group l. As anticipated before, Equation ( 12) must be verified. Let us rewrite this equation by replacing Let ex 0 = U -S 0 be the excess bandwidth for group l = 0. For the following groups, ex l = ex l-1 -S l . By substituting, we get:

∀l ≥ 0, ex l -S l+1 , -. . . -S L ≤ 0
For all groups with ex l > 0, we just turn on all cores and set them at the maximum speed: so l = sh l and act l = m l .

Suppose that ex l ≤ 0 for some group l. It means that the cumulative strength up to group l can support the current load. Then we set all successive strengths S l , l > l to 0 by turning off all cores in the groups. In addition, we distribute the current remaining bandwidth equally on all cores of group l:

so l = round -tomode( ex l-1 m l ) ( 13
)
If the computed speed so l is greater than the lower bound speed of the current group l (see Equation (??)), the number of active cores is set equal to the number of cores in the group:

act l = m l (14)
Otherwise, the frequency is set to the minimal frequency sl and the number of active cores is set to the ratio between the ex l-1 and the operating frequency at the current group so l .

act l = ex l-1 so l ( 15
)
In this case, the assigned speed at this level may be greater than the remaining strength. We compute this overhead as: and we remove it from cores speed of a lower group:

ρ = so l * act l -ex l-1 (16)
so l-1 = so l-1 - ρ act l-1 ( 17
)
The complexity of the setting frequencies Algorithm 2 is trivially Θ(L).

The method round-to-mode selects the first higher possible frequency, since the frequencies are discrete.

CP partitionning

After selecting the frequencies, we proceed to decomposition and allocation.

We consider partitioned-EDF scheduling, and we propose an iterative heuristic for solving the task decomposition and allocation problem at once. At each iteration, we check if the task fits entirely in the current core or if it needs to be split. In the latter case, the heuristic defines the part (threads) that will be partitioned on the current core, and the part (threads) that will be allocated in the next iteration.

We preliminary sort all cores in non-increasing order according to their operating speed, then we go trought three steps. First, we select the task τ at the top of the task list, and the core with the highest index (hence the lower speed), let it be core p. Then the dbf is computed for the set of threads already allocated on the core p, together with the new task τ for the speed s p :

dbf(T ∪ {τ }, s p , t) = dbf(T , s p , t) + dbf({τ }, s p , t) (18) 1. if ∀t, t ∈ [0, t * ] Equation (19) is verified dbf(T ∪ {τ }, s p , t) ≤ t, (19)
the task set T p ∪ {τ } is schedulable, hence task τ is allocated on the core p.

2. if, for some t values, Equation ( 19) is not verified, then the task set T ∪{τ } is not schedulable. In this case, we seek to split the reduce the execution time of task τ so that one part will fit between the dbfand t so that Equation 19 is verified. We call the time to be reduced excess-time. To evaluate the excess-time, first we evaluate the cumulative excess of all instances on the task form 0 to t:

δ = dbf(T p ∪ {τ }, s p , t) -t (20)
so the excess-time by one instance is equal to the ratio of the δ and the number of instances of the task τ in the interval [0, t]:

             δ = dbf(T j , j, t) -t #instances = t T i excess-time(t) = δ #instances (21)
For all t , where condition 19 is not verified, excess-time is evaluated and only the maximal excess-time is maintained. The evaluation of excesstime is described in Algorithm 3. The complexity of this algorithm is

Θ(h × n i=1 max(| γ i,k |)).
Example. In the example of Figure 4, we try to evaluate the excess-time for the task τ (O = 0, D = 7, T = 10, {ct = 8, mt = 1}) on a core of speed s = 0.5. We assume that the task set T is already allocated on this core and the value of the dbf(T , s p , t), t ∈ [0, 25] is presented on the first graph of Figure 4. The second graph represents the dbf of the new task set {T ∪ τ } and the excess-time points, which are reported, also, in table below.

Algorithm 3 excess-timeEvaluation

Input: Taskset:T , core: P, Task :τ

Output: excess-time = 0

Temp-excess:Integer = -1 The value of the excess-time corresponds to the maximum value among all excesses (excess-times = 4, third graph of Figure 4). Now that we have introduced the concept of excess-time, we use a simple heuristic to decompose the tasks that do not fit in a core. If excess-time ≥ cti sp + mt i , (this means that the whole task is in excess), we seek to allocate the selected task on the next core p + 1. If all cores are already investigated, the task set is not schedulable.

t = 0 while (t ≤ h ) do dbf * = dbf(T , s p , t) + t+(Ti-Di) Ti cti sp + mt i if ( dbf * > t ) then δ = dbf * -t n = t
If excess-time ≤ cti sp + mt i , the task τ i must be split according to one possible γ i,k ∈ Γ i . We use a search function that returns two lists: the first one consists of the threads that fit on the current core, whereas the second list of threads is put back into the task list to be allocated in the next iterations.

Let γ i,k be a cut-point of Γ i of the task τ i . The γ i,k is as a corret decomposition according to excess-time if and only if Equation 22 is verified:

∃σ i,k ⊂ γ i,k , σ i,k = ∅, γ i,k = σ i,k T h i,k,z ∈σ i,k C i,k,z ≥ excess-time (22)
where σ i,k is the list of threads to put back to the task list, and γ i,k \ σ i,k is the list of threads to be allocated to the current core. So, For the same excess-time, we can have numerous correct cut-points.

For example, let excess-time = 5 and

Γ 1 = {γ 1,1 = {Th 1,1,1 (mt = 2, ct = 5), Th 1,1,2 (mt = 2, ct = 5), }, γ 1,2 = {Th 1,2,1 (mt = 1, ct = 2), Th 1,2,2 (mt = 1, ct = 2), Th 1,2,3 (mt = 1, ct = 5)
, }}. This task can be split in several threads that respect the excess-time as shown in the following table:

γ 1,k return to TS maintained γ 1,1 Th 1,1,1 Th 1,1,2 γ 1,1 Th 1,1,2 Th 1,1,1 γ 1,2 Th 1,2,1 , Th 1,2,2 Th 1,2,3 γ 1,2 Th 1,2,1 , Th 1,2,3 Th 1,2,2 γ 1,2 Th 1,2,2 , Th 1,2,3 Th 1,2,1 γ 1,2 Th 1,2,3 Th 1,2,1 , Th 1,2,2
Thus, the cut-point selection (Algorithm (4)) has a significant impact on scheduling. The algorithm of search for the cut-point is simple. First, it seeks the thread Th i,k,z that has the exact values of the excess-time. If found, this cut-point will be returned. Otherwise, it looks for the closest combination of threads that is greater or equal to the excess-time.

The complexity of lookForCP search (algorithm 4) is Θ(max

(| Γ i |)×max(| γ i,k |))
. However, after splitting, the cut-points list Γ i is reduced to one cutpoint (constraint that all threads must be from the same cut point, Equation

(γ i,k \ σ) ). Thus, the lookForCP search function complexity is reduced considerably after the first allocation.

The partitioning heuristic is described in (Algorithm 5). The complexity of

this algorithm is Θ(n × m × h × n i=1 max(| γ i,k |)
). The full algorithm (1) combine all the heuristics described in this section. the complexity of this algorithm is Θ(nbrIt

× n × m × h × n i=1 max(| γ i,k |))
where nbrIt is the number of iterations from the lowest cumulated strength to the highest cumulated strength.

Simulations and Results

In order to evaluate our contributions, we applied our algorithm to several synthetically generated scenarios. We selected an architecture consisting of m = 4 processors with L = 2 groups of 2 cores each. Each core has several operating frequency levels ranging from 800MHz to 1800MHz, which corresponds to speed levels ranging in between [0.44, 1]. This corresponds to a cumulative maximum We generate utilization-rates between [1 -4], and the number of tasks between 2 and 5 by core.

Task Generation

The UUniFast method [START_REF] Dais | Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems[END_REF] can be used to generate a number of utilizations factors, whose sum is a given number bounded by 1 (i.e. ∀i, u i ≤ 1). The method has been extended to multi-core systems with the UUniFast-discard algorithm. The latter allows to set the bound to a number m ≥ 1 and adds the constraint that each utilisation must not exceed 1.

In our case, we removed the latest constraint, because we allow tasks whose sequential utilisation is greater than 1.

In order to select the periods, we use the method proposed in [START_REF] Goossens | Limitation of the hyper-period in real-time periodic task set generation[END_REF] to bound the hyperperiod of the task set and generate task periods. Therefore, we compute the computation times of the single-thread cut point for each task as C i = u i × T i . Then, we generate

mt i = C i × P ct i = C i -mt i
where P is the percentage of central memory access operations among all operations. We consider such percentage as a fixed number to reduce the number of parameters and simplify the experiments, but in reality such percentage depends on the structure of the task sets, the amount of data, the cache size, the interference from other tasks in the cache, etc.

Then, for each task we randomly generate the number of cut points i K (| Γ i |) between 2 and 5. For each cut point γ i,k , we generate the number of threads Z i k . Finally, we use again UUniFast to generate the utilisation for each thread. To take into account the overhead of the decomposition (due to synchronization barriers, scheduling, etc.) we inflate the utilisation of the task

to U i = U i × (1 + costZ k )
, where cost is a constant that represent the overhead in percentage. We fixed this overhead to cost = 0.05. If the utilisation of a task exceeds 1, U i ≤ 1, we generate the deadline between C i and T i . Otherwise, the deadline is generated in the interval [P r × T i , T i ] where P r is generated between [0.75 -1]. The task generation is described in Algorithm 6.

Power dissipation model

The goal of these experiments is to compute the relative performance of different algorithms. Therefore, just for the sake of this comparison, we consider ξ = 1. This is the same approach followed in Fisher et al. [START_REF] Fisher | Energy minimization for parallel real-time systems with malleable jobs and homogeneous frequencies[END_REF], and in Han et al [START_REF] Yun | On energy-optimal voltage scheduling for fixed-priority hard real-time systems[END_REF]. So we consider the power consumption as

E(f ) = f 3 . The dynamic energy spent by core p from [t 1 -t 2 ] is simply E = f 3 p × (t 2 -t 1 )
. This allows to relatively compare the energy consumption for different scheduling algorithms but does not give an absolute power value.

Results and discussions

In this section we present and discuss the results of the experiments. Our task model is unique in that it allows parallel decomposition of a task in several different ways. No other algorithm can do the same, so we decided to compare against traditional allocation algorithms that do not decompose tasks.

In particular, the structure of a competing algorithm is the following:

• We first run Algorithm 2 to set the active cores and their frequencies

• Then we run the allocation algorithm on the single-threaded versions of the tasks.

The selected allocation algorithms are Best Fit (BF), Worst Fit (WF), First Fit (FF) and Next Fit (NF). Our algorithm is denoted as Cut-Points (CP).

Notice that, if we consider tasks with only one single-thread cut-point, CP is equivalent to FF. Otherwise the main difference in CP is the decomposition.

Notice also that decomposition make it easier to allocate threads, but increases the total utilisation factor because of the added synchronization overhead. We notice that our heuristic dominate globally the BF, WF, FF, NF heuristics. However, we can notice that when the workload is small, BF and FF are very close to CP, because the non-parallel heuristics (BF, WF, FF, NF) allocates the tasks entirely in one core (no-parallelism) and so they do not run the overhead brought by parallelizing the task. However, CP is stills better even when the computation load is not very high. When the load increases, BF, WF, FF, and NF are too much limited compared to our approach. In particular, our approach is close to the theoretical limit of full utilisation per each core, so the cumulative strength is almost equal to the task set utilisation (the yellow line).

Figure 6 describes the average cumulative strength S by varying the percentage of memory access (mt/(ct + mt)) for the same utilisation (U = 2). Once again, every point represents the average value of S obtained over 500 runs on randomly generated task sets. We notice that a small variation in memory accesses produces a considerable impact on the cumulative strength. However, the strength grows slowly after some percentage because the scheduling heuris- tic behaves in the same manner on all cores and the core speed has less influence on the decomposition and allocation.

Figure 7 describes the average power consumption by varying the utilization rate. We plot only BF, FF and CP because the WF and NF show very bad results. Even if the utilisation produced by CP is higher than the others (due to the overhead of decomposition), it still consumes less energy for all scenarios especially when the load is high. Whereas BF and FF raise the cores frequency to high values, our algorithm keeps the frequency of each core lower. Even when the computation load is low, our approach saves in average 46% , 36% less than BF, FF.

Figure 8 describes the the utilization factor per each core while varying the utilization of the task set. We can notice that when the load is greater then the minimal speed (0.44), the utilization-rate per core gets closer to 1 (it reaches 97%), which means that the optimal solution is not so far.

Conclusion

In this paper we presented a method for minimizing the energy consumption for a realistic task model on multicore uniform architectures. We propose a general model of a multicore, where cores are partitioned in groups, and cores belonging to the same group must share the same frequency. We also allow some processor to go in deep low power state. We also proposed a model for moldable tasks that easily allow to specify parallel decomposition (in the style of OpenMP) taking into account the synchronization overhead and a sound energy consumption model.

Then we proposed a heuristic algorithm for energy-aware EDF-partitioned scheduling, which selects the set of active cores and their frequency, and allocates tasks so that the resulting schedule is feasible. We have performed experiments that show the effectiveness of our algorithm.

In the future, we plan to implement our methodology on the ARM big.LITTLE architecture. Furthermore, we are working on an OpenMP-like API based on pthread for programming moldable tasks.

Figure 1 :

 1 Figure 1: Task decomposition

Figure ( 2 )Figure 2 :Figure ( 3 )Figure 3 :

 2233 Figure[START_REF] Wolf | Computers as components: principles of embedded computing system design[END_REF] shows the average execution time of each thread when all cores operate at a frequency of 1, 800MHz. Each point represent the average execution time of a decomposition from 1 to 8 threads.

Algorithm 1 SAlgorithm ( 1 )

 11 Full algorithm Input: T : T askSet, L : Int, U : F loat, m, sl, sh : Array[Int]; temp = U while S temp ≤ S max do main loop arch = selectFrequencies(L, S temp , m, sl, sh) if isCPSchedulable(Arch, T ) then return true; else S temp = S temp + Step increases the cumulative strength S temp at each iteration by

m p=1 s

  lp by the equivalent value L l=1 S l : U -S 0 -S 1 . . . -S L ≤ 0

Figure 4 :

 4 Figure 4: Decomposition example

T

  Temp-excess = δ n if ( Temp-excess > excess-time ) then T excess-times = Temp-excess

Algorithm 5

 5 cut-point model partitioning OrderTasks() sortCoresBySpeed() for τ i ∈ AllTasks do for P j ∈ AllCores do loop2excess-time = excess-TimeEvaluation(T pj , s j , τ );if ( excessT-time = 0 ) then dbf(T j , s j , t) ≤ t P.Allocate(τ ) break loop2 else if ( C sj i ≤ excess-time ) then (σ, LM)=lookForCP(excess-time,s j , τ i ) τ 1 = createTask (maintained ) τ 2 = createTask (σ) P.Allocate(τ 1 )AllTasks.add(τ 2 ) of S = 4. These parameters correspond to the Intel i3-3217U used for the experiments shown in Section 3.2.

Figure 5

 5 Figure 5 describes the average cumulative strength S of all algorithms by varying the utilisation factor. Each point represent the average value of S on 500 run of randomly generated task sets.

Figure 5 :

 5 Figure 5: Cumulative strength by different utilisation factors.

Figure 6 :

 6 Figure 6: Architecture selected cumulated strength by different Memory rates.

Figure 8 :

 8 Figure 7: Energy Consumption.

Not shown here, to avoid cluttering the figure with too many lines.

for (l = 0 to L -1) do