Sanjoy K Baruah
email: baruah@cs.unc.edu

Vincenzo Bonifaci
email: vincenzo.bonifaci@iasi.cnr.it

Renato Bruni
email: bruni@diag.uniroma1.it

Alberto Marchetti-Spaccamela
email: alberto@diag.uniroma1.it

ILP-based approaches to partitioning recurrent workloads upon heterogeneous multiprocessors

The problem of partitioning systems of independent constrained-deadline sporadic tasks upon heterogeneous multiprocessor platforms is considered. Several different integer linear program (ILP) formulations of this problem, offering different tradeoffs between effectiveness (as quantified by speedup bound) and running time efficiency, are presented.

I. INTRODUCTION

Heterogeneous multicore CPUs -CPUs in which the processing elements differ from one another with respect to functionality or processing speed -are currently widely available and increasingly becoming the common case. The presence of such heterogeneity requires choices to be made when mapping software components onto processing elements. The need to resolve such choices adds considerable complexity to resource allocation, and inhibits the adoption of such platforms by the embedded computing industry despite significant potential benefits in terms of balancing performance and energy.

We consider here real-time systems that are modeled as collections of independent sporadic tasks (the model is described in detail in Section II). We seek to devise algorithms for implementing such systems upon heterogeneous multiprocessor platforms under the partitioned paradigm. To our knowledge, this topic has not been studied much previously:

• On the one hand, most prior real-time scheduling research that considers heterogeneous platforms (see, e.g., [START_REF] Chwa | Optimal real-time scheduling on two-type heterogeneous multicore platforms[END_REF], [START_REF] Raravi | Task assignment algorithms for two-type heterogeneous multiprocessors[END_REF], [START_REF] Raravi | Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors[END_REF], [START_REF] Raravi | A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors[END_REF], [START_REF] Wiese | Partitioned EDF scheduling on a few types of unrelated multiprocessors[END_REF]; [START_REF] Raravi | Real-Time Scheduling on Heterogeneous Multiprocessors[END_REF] has a nice survey) has restricted attention to implicit-deadline sporadic tasks. • On the other hand, prior research that does address the partitioned scheduling of task systems represented using models that are more general than the implicit-deadline model considers identical multiprocessor platforms only (see, e.g., [START_REF] Baruah | The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems[END_REF], [START_REF] Chen | Resource augmentation for uniprocessor and multiprocessor partitioned scheduling of sporadic real-time tasks[END_REF]). In this paper, we initiate a methodical study of the problem of partitioning, upon heterogeneous multiprocessor platforms, task systems that are represented using the more general constrained-deadline sporadic task model 1 . We assume that once the partitioning has been performed and tasks assigned to the processors, run-time scheduling is done on each processor using the earliest deadline first (EDF) scheduling algorithm, which is known to be optimal for this purpose [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF], [START_REF] Dertouzos | Control robotics : the procedural control of physical processors[END_REF].

Our approach. We will derive various approaches to task partitioning. These algorithms share the commonality that they are all based upon formulating the task partitioning problem as an integer linear program (ILP). For implicit-deadline task systems, this is not particularly difficult to do; indeed most of the research on partitioning implicit-deadline sporadic task systems (including the works [START_REF] Raravi | Task assignment algorithms for two-type heterogeneous multiprocessors[END_REF], [START_REF] Raravi | Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors[END_REF], [START_REF] Raravi | A PTAS for assigning sporadic tasks on two-type heterogeneous multiprocessors[END_REF], [START_REF] Wiese | Partitioned EDF scheduling on a few types of unrelated multiprocessors[END_REF] cited above) has been based upon first formulating such an ILP, and then seeking polynomial-time algorithms for obtaining approximate solutions to these ILPs (solving an ILP is known to be NP-hard [START_REF] Karp | Reducibility among combinatorial problems[END_REF], and hence unlikely to be solvable exactly in polynomial time).

Despite this inherent intractability of solving ILPs, however, the optimization community has recently been devoting immense effort to devise extremely efficient implementations of ILP solvers, and highly-optimized libraries with such efficient implementations are widely available today. Modern ILP solvers, particularly when running upon powerful computing clusters, are often capable of solving ILPs with tens of thousands of variables and constraints. We therefore believe that it is reasonable to attempt to solve ILPs exactly rather than only approximately, and seek to obtain ILP formulations that we will seek to solve exactly to solve the partitioning problem for constrained-deadline sporadic task systems. Since the running time of ILP solvers tends to increase with the number of variables and constraints in the ILP to be solved, we seek to develop ILPs for task partitioning in which the number of variables and constraints are restricted to be loworder polynomials of the representation of the task system. While the number of constraints may not always be a good indicator of the complexity of an ILP formulation, we use it as a first approximation: indeed, the best known complexity bounds for solving ILPs do increase with the number of linear constraints [START_REF] Frank | An application of simultaneous diophantine approximation in combinatorial optimization[END_REF]Theorem 5.3]. Possibly more refined metrics, such as the constrained induced-width [START_REF] Freuder | A sufficient condition for backtrack-bounded search[END_REF] or the constraint density [START_REF] Achlioptas | On the solutionspace geometry of random constraint satisfaction problems[END_REF], have also been suggested in other settings, but not in the context of the problem of partitioning tasks onto heterogeneous processors -not even implicit-deadline tasks [START_REF] Kamath | Unrelated parallel machine scheduling-perspectives and progress[END_REF]; these refinements fall outside the scope of this work.

Our results. In partitioning implicit-deadline sporadic task systems, an ILP represents an exact solution to the partitioning problem -solving an ILP exactly therefore constitutes an optimal algorithm for performing such partitioning. For

3. n + m + nmk 1 + 1 k In Section IV. k is any integer ≥ 1. 4. n + m + m log ρ dmax 2 + ρ + ρ 2 ρ-1
In Section V. A "poorer" version of row 2 -same number of constraints, larger speedup factor. But more amenable to polynomial-time approximation -see Section V for details

Table I SUMMARY OF RESULTS

partitioning constrained-deadline systems, however, we do not know how to obtain such an exact ILP representation of this problem with only polynomially many constraints -this difficulty was previously identified even for partitioning upon identical multiprocessors in [START_REF] Baruah | Partitioned scheduling of sporadic task systems: an ILP-based approach[END_REF]. Instead, our goal here is to obtain polynomial-sized ILP representations of the problem of partitioning constrained-deadline sporadic task systems upon heterogeneous multiprocessor platforms with the property that exact solutions of the ILP constitute approximate solutions to the partitioning problem. Our metric of effectiveness of such an approximate solution is the speedup factor -an ILP formulation has speedup factor f , f ≥ 1, if any constraineddeadline sporadic task system that can be partitioned upon a particular heterogeneous platform by a hypothetical optimal algorithm can be partitioned using this ILP formulation upon a platform in which each processor is at least f times as fast.

We have derived several different ILP representations for the problem of partitioning constrained-deadline sporadic task systems upon heterogeneous multiprocessor platforms, all of which have number of variables and constraints polynomial in the representation of the task system. All these ILP formulations have nm integer variables, where n is the number of tasks and m the number of processors, but specify different numbers of constraints and offer different speedup guarantees -they are summarized in Table I.

II. SYSTEM MODEL, BACKGROUND, AND NOTATION

We seek to partition a sporadic task system τ comprising the n independent sporadic tasks τ 1 , τ 2 , . . . , τ n upon an unrelated multiprocessor platform π comprising the m processors π 1 , π 2 , . . . , π m . The i'th sporadic task τ i is characterized by a period p i and a relative deadline d i , and m worst-case execution time (WCET) parameters c i,1 , c i,2 , . . . c i,m , with c i,j denoting the WCET of τ i if it executes upon processor π j . In this paper, we restrict attention to task systems in which d i ≤ p i for each task τ i ∈ τ -such sporadic task systems are called constrained-deadline sporadic task systems. During run-time, τ i releases a sequence of jobs at time-instants that are not known beforehand, but with the constraint that successive jobs are released at least p i time units apart. Each job of τ i has a deadline d i time units after its release time; the amount of execution needed by this job depends upon the identity of the processor on which it executes. More specifically, since we are studying partitioned scheduling in this paper, given task system τ and multiprocessor platform π, our objective is to obtain a partitioning of the tasks upon the processors. Let f (i) ∈ {1, 2, . . . , m} denote the index of the processor to which each τ i is assigned under such a partitioning; each job of τ i needs to execute for up to c i,f (i) time units upon processor π f (i) .

Since the preemptive Earliest Deadline First scheduling algorithm (EDF) is known to be optimal for scheduling a single preemptive processor, we will use EDF as the scheduling algorithm upon each individual processor during run-time. The demand bound function (dbf) [START_REF] Baruah | Preemptively scheduling hard-realtime sporadic tasks on one processor[END_REF] of a sporadic task is widely used to quantify the computational demand of such a task, where the dbf(τ i , t) of sporadic task τ i with period p i , relative deadline d i , and WCET c i for an interval of duration t is defined as follows

dbf(τ i , t) := t + p i -d i p i c i
It is known that a collection of sporadic tasks can be scheduled to always meet all deadlines upon a preemptive uniprocessor by EDF if and only if for all t ≥ 0, the sum of the dbf's of all the tasks in the collection for an interval of duration t does not exceed t.

Some additional notation:

• Let N := {1, 2, . . . , n} denote the task index set.

• Let M := {1, 2, . . . , m} denote the processor index set.

• Let u i,j := c i,j /p i denote the utilization of task τ i on processor π j . • Let d max := max 1≤i≤n {d i } denote the largest relative deadline parameter of any task in τ .

As above, let f : N → M denote a partitioning of the task system τ upon multiprocessor platform π. We use the notation dbf f,j (t) to denote the sum of the dbf's of all the tasks in τ that have been assigned to processor π j under the partitioning f , for interval duration t:

dbf f,j (t) := i∈N :f (i)=j t + p i -d i p i c i,j

III. A SIMPLE ILP MODEL FOR TASK PARTITIONING

Marchetti-Spaccamela et al. have previously [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF] derived a polynomial-time algorithm for assigning sporadic tasks to heterogeneous processors, and shown that this algorithm has a speedup bound of (8+2 √ 6) or ≈ 12.9. An intermediate step in [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF] is the derivation of a 0/1 ILP representation of the partitioning problem with nm variables and (n+m+m log d max ) linear constraints, and a proof that this ILP representation has a speedup factor of 6. In this section, we present two results:

1) We derive, in Theorem III. A. A review of some results from [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF] First a preliminary definition. Let D denote the set of values

0, 1, 2, 4, . . . , 2 log 2 dmax
We call D the deadline checkpoint set for task system τ . The starting point of the reasoning in [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF] is the following lemma.

Lemma III.1 (from [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF]). Let f : N → M denote an assignment of the tasks in task system τ to the processors of unrelated multiprocessor platform π such that, for each j ∈ M i:f (i)=j u i,j ≤ β and for each j ∈ M and k, 1

≤ k ≤ log 2 d max , i:(f (i)=j)∧(2 k-1 <di≤2 k ) c i,j ≤ β • 2 k .
Then for each j ∈ M , dbf f,j (t) ≤ 6βt for all t ≥ 0.

Let us try and understand what this lemma means. The first set of inequalities requires that the cumulative utilization assigned to each processor not exceed β; the second, that the sum of the WCETs of all tasks assigned to a processor that have relative deadlines between two successive powers of two not exceed β times the larger power of two. (For example, considering k ← 6, the second constraint mandates that the sum of the WCETs of all tasks with relative deadline in the range (32, 64] not exceed 64β.) The lemma asserts that if these conditions are satisfied by an assignment, then this assignment constitutes a valid partitioning upon processors of speed 6×β. Now, suppose that τ is feasible upon π under partitioned scheduling, i.e., there is an assignment f : N → M of τ upon π such that all jobs of all tasks will always complete by their deadlines if tasks are assigned according to this partitioning, and each processor scheduled during run-time by EDF. For this assignment f , it is evident that the utilization constraints of Lemma III.1 are satisfied for β = 1. The second set of constraints in Lemma III.1 will also be satisfied for β = 1, by the following reasoning:

• Since the partitioning f is feasible, the sum of the dbf's of all the tasks assigned to the jth processor for interval duration 2 k is no more than 2 k . • Each task with relative deadline in

(2 k-1 , 2 k ] must have dbf(τ i , 2 k ) ≥ c i,j .
• Hence the sum of the c i,j 's for all tasks τ i that have relative deadline in (2 k-1 , 2 k ] and are assigned to the jth processor must be ≤ 2 k .

Hence if τ is feasible upon π, there exists an f : N → M for which the conditions of Lemma III.1 are satisfied with β = 1; therefore dbf f,j (t) ≤ 6t for all t ≥ 0 for each j. Thus [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF] derives the following speedup result:

Corollary III.2. Let f : N → M denote an assignment of tasks to processors satisfying the conditions of Lemma III.1. Then f constitutes a feasible partitioning of τ upon π under a speedup factor of 6β. In particular, if the conditions of the lemma are satisfied with β ≤ 1/6, then assignment f constitutes a feasible partitioning of τ upon the given platform π.

In summary, the conditions of Lemma III.1 are necessary when β = 1 and sufficient when β = 1/6, i.e., they yield a speedup factor of 6 for partitioning constrained-deadline sporadic tasks upon heterogenous multiprocessor platforms.

B. An ILP with speedup factor 4

We now prove an improved version of Lemma III.1 that yields a superior speedup bound (of four, rather than six). The conditions specified in our theorem below differs from those in Lemma III.1 only in that the summation of c i,j 's in the second inequality is over all tasks with relative deadline ≤ 2 k (rather than only those with relative deadline > 2 k-1 and ≤ 2 k ).

Theorem III.3. Let f : N → M denote an assignment of the tasks in task system τ to the processors of unrelated multiprocessor platform π such that, for each j ∈ M

i:f (i)=j u i,j ≤ β (1) for each k, 1 ≤ k ≤ log 2 d max , i:(f (i)=j)∧(di≤2 k ) c i,j ≤ β • 2 k . ( 2
)
Then for each j, 1 ≤ j ≤ m, dbf f,j (t) ≤ 4βt for all t ≥ 0.

Proof. Consider any t ≥ 0 and let s := 2 k denote the smallest integer power of 2 that is not smaller than t (i.e. s = 2 k ≥ t > s/2).

Consider an assignment f : N → M of the tasks to the processors. For any j ∈ M , we have

dbf f,j (t) ≤ dbf f,j (s) = i:f (i)=j∧di≤s s + p i -d i p i c ij ≤ i:f (i)=j∧di≤s s c ij p i + c ij ≤ s i:f (i)=j c ij p j + i:f (i)=j∧di≤s c ij = s i:f (i)=j u ij + β • 2 k ≤ βs + βs ≤ 4βt
and the theorem is proved.

This implies that any f satisfying Inequalities 1 and 2 of Theorem III.3 constitutes a feasible partitioning of the tasks in τ upon the set of heterogeneous processors π, when the processors receive a speedup factor of 4β:

Corollary III.4. Let f : N → M denote an assignment of tasks to processors satisfying Inequalities 1 and 2 of Theorem III.3. Then f constitutes a feasible partitioning of τ upon π under a speedup factor of 4β. In particular, if Inequalities 1 and 2 are satisfied with β ≤ 1/4, then assignment f constitutes a feasible partitioning of τ upon the given platform π.

We now apply the result of Theorem III.3 above to construct a 0/1 integer linear program (ILP) for specifying a feasible partitioning of sporadic task system τ upon the platform π. That is, we will construct a 0/1 ILP, a solution to which will yield a partitioning f : N → M that satisfies Inequalities 1 and 2. This ILP is constructed as follows:

• For each i ∈ N, j ∈ M , we have a 0/1 integer variable (i.e., an integer variable that takes on either the value zero or the value one) x i,j , denoting whether τ i is to be assigned to processor π j . • We specify that each task gets assigned to exactly one processor; this is done by the following n constraints:

∀i ∈ N j∈M x i,j = 1 (3)
• We next specify that Inequality 1 of Theorem III.3 should be satisfied; this is achieved by the following m constraints:

∀j ∈ M i∈N x i,j u i,j ≤ β ( 4
)
• Finally, we specify Inequality 2 of Theorem III.3 by the following (log d max × m) constraints:

∀k ∈ D, ∀j ∈ M (i∈N )∧(di≤2 k ) c i,j x i,j ≤ β • 2 k (5)
By Theorem III.3, any assignment of integer values to the {x i,j } variables satisfying the Constraints 3-5 above bears witness to the schedulability of τ , with a speedup of 4β, upon the platform π. Moreover, for a τ that is feasible upon π the model always admits a solution with β = 1, since all inequalities are clearly valid; thus, this ILP guarantees a speedup factor of at most 4. When the ILP model is feasible with β ≤ 1/4, Theorem III.3 guarantees schedulability on the original platform; hence, a reasonable objective function for the ILP with Constraints 3-5 would be to minimize β.

C. A generalization

Above, we derived an ILP model for the problem of partitioned scheduling of constrained-deadline sporadic task systems upon unrelated multiprocessors, such that any solution to the ILP immediately yields a partitioning algorithm at a speedup bound of 4. We also saw that this ILP has (n+m+m× log 2 d max ) constraints; we now briefly describe how to reduce the speedup bound by increasing the number of constraints.

Recall that we had defined the deadline checkpoint set D as powers of two: D = {0, 2 0 , 2, 2 2 , . . . , 2 log 2 dmax }. For any given constant ρ > 1, we could instead have chosen to define it as

D ρ = {0, 1, ρ, ρ 2 , ρ 3 , . . . , ρ log ρ dmax },
The following generalization of Theorem III.3 is easily proved via a proof analogous to the proof of Theorem III.3: Theorem III.5. Let f : N → M denote an assignment of the tasks in task system τ to the processors of unrelated multiprocessor platform π such that, for each j ∈ M i:f (i)=j u i,j ≤ β, and for each j ∈ M and k,

1 ≤ k ≤ log ρ d max , i∈N :(f (i)=j)∧(di≤ρ k ) c i,j ≤ β • ρ k Then for each j ∈ M , dbf f,j (t) ≤ 2ρβt for all t ≥ 0.
It follows, from arguments virtually identical to those of Corollary III.4, that the speedup bound for the ILP constructed based on Theorem III.5 above is 2ρ; hence by choosing ρ to be smaller than 2 a speedup bound smaller than 4 is obtained. The tradeoff is that the number of constraints increases to

(n + m + m × log ρ d max ); this is > log 2 d max for ρ < 2, becoming larger as ρ → 1.
Theorem III.5 thus suggests one approach for obtaining speedup bounds arbitrarily close to 2, by simply selecting a denser deadline checkpoint set. In Section IV below, we explore another approach, that allows for speedup bounds arbitrarily close to one (once again at the cost of having additional constraints).

IV. A STRENGTHENED ILP FORMULATION

We now explore a different idea that also trades off an increase in the number of constraints in the ILP for a superior speedup bound. Specifically, for any positive integer constant k we will derive an ILP model with (n+m+m n k) constraints, finding a feasible solution to which corresponds a partitioning at a speedup bound of 1 + 1 k . Approximation schemes have been defined for computing the value of dbf to any desired degree of accuracy (see, e.g. [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF]). Equation 6below gives such an approximation scheme; for any fixed positive integer value of k, dbf (k) (τ i , t) defines an approximation of dbf(τ i , t) that is exact for the first k "steps" of dbf(τ i , t), and an upper bound for larger values of t:

dbf (k) (τ i , t) = c i,j × t+pi-di pi if t ≤ (k -1)p i + d i c i + (t -d i )u i otherwise (6)
The following lemma (see, e.g., [START_REF] Baruah | Partitioned scheduling of sporadic task systems: an ILP-based approach[END_REF]) provides a quantitative bound on the degree by which dbf (k) may deviate from dbf:

Lemma IV.1. For all t ≥ 0 dbf(τ i , t) ≤ dbf (k) (τ i , t) < 1 + 1 k dbf(τ i , t).
That is, dbf (k) (τ i , t) provides an upper bound on dbf (k) (τ i , t) that is no more than a fraction 1/k greater than the actual value of dbf (k) (τ i , t).

As previously stated, it is known that a collection of sporadic tasks can be scheduled to always meet all deadlines upon a preemptive uniprocessor by EDF if and only if for all t ≥ 0, the sum of the dbf's of all the tasks in the collection over an interval of duration t does not exceed t. For schedulability, it is clearly necessary that the utilizations of all the tasks in the collection sum to no more than 1. Since dbf (k) is an upper bound on dbf, it follows that a sufficient uniprocessor EDF-schedulability test for a collection of tasks is that the sum of the dbf (k) functions of all the tasks in the collection over an interval of duration t not exceed t. Albers and Slomka showed [START_REF] Albers | An event stream driven approximation for the analysis of real-time systems[END_REF]Lemma 4] that it suffices to validate this fact only for those values of t at which one or more of the dbf (k) functions has a step discontinuity. More precisely, let

S i,k = {t : t = d i + hp i , h = 0, 1, . . . , k} and S k = all i S i,k
It suffices to test that the sum of the dbf (k) functions of all the tasks in the collection over an interval of duration t not exceed t, only for values of t ∈ S k .

We can use this result to define a revised ILP formulation for modeling the partitioned scheduling of sporadic task systems upon heterogeneous multiprocessors. The first part of this revised ILP is identical to the one constructed in Section III:

• As in Section III, we will have a zero-one integer variable

x i,j , denoting whether τ i is to be assigned to processor π j , for each i ∈ N, j ∈ M . • Again as in Section III, the following n constraints specify that each task gets assigned to exactly one processor:

∀i ∈ N j∈M x i,j = 1 (7)
• The following m constraints bound the total utilization on each processor:

∀j ∈ M i∈N x i,j u i,j ≤ β (8)
The final set of constraints replace the Inequalities 5 of the ILP in Section III with constraints based upon the dbf (k) approximation, that express the requirement that the sum of the dbf (k) functions of all tasks assigned each processor over an interval duration not exceed the duration. As we had stated above, this condition only needs to be validated for interval durations in S k ; this motivates the following set of constraints:

∀t ∈ S k , ∀j ∈ M i∈N x i,j × dbf (k) j (τ i , t) ≤ β • t (9)
(where for each j ∈ M , dbf

j (τ i , t) denotes the function dbf (k) (τ i , t) when the WCET of τ i is set equal to c i,j .) Since each τ i contributes at most k distinct points to S k , it follows that |S k | ≤ nk; hence there are at most mnk such constraints.

Note that the Inequalities 9 are constructed for specified values of t; i.e., for each t ∈ S k . For each such specified t, it is straightforward to observe that the inequality is indeed a linear one, since inspection of Expression 6 reveals that for a given value of t for each τ i the expression dbf

(k) j (τ i , t) is a constant.
Theorem IV.2. A feasible solution to the ILP on the 0/1 variables {x i,j }, i ∈ N, j ∈ M , with Constraints 7-9 (defined above) yields a feasible partitioning of the tasks in τ to a platform in which each processor in π is speeded up by a multiplicative factor of (1 + 1/k)β. In particular, if the inequalities are satisfied with β ≤ (1+1/k) -1 , then a feasible solution to the ILP yields a feasible partitioning on the given platform.

Proof. It is evident from the result of Albers and Slomka that satisfying Constraints 7-9 is sufficient for feasibility upon a speed-β(1 + 1/k) platform. Additionally we conclude from the lower bound in Lemma IV.1 that failure to satisfy these conditions implies infeasibility upon a speed-β platform.

The quality of the solution that is obtained by solving the ILP specified by Constraints 7-9 depends on the value of k: the larger this value, the better is the quality (i.e., the lower the speedup factor) of the obtained solution. However we observe that the number of constraints increases with k. It follows that large values of k lead to an ILP that is not solvable with state of the art packages. We explore this tradeoff via schedulability experiments In Section VI.

V. AN ILP THAT IS MORE AMENABLE TO APPROXIMATING IN POLYNOMIAL TIME

In the previous sections, we discussed assignment algorithms based on solving reasonably-sized ILPs. However, in some scenarios the solution of an ILP may be a computational bottleneck -solving an ILP is, after all, a prototypical NP-hard problem. Therefore, the design of efficient (polynomial time) assignment and schedulability algorithms retains interest.

A standard technique that has been developed within the optimization community for efficiently obtaining an approximate solution to an ILP is to first consider the linear program (LP) obtained by "relaxing" (i.e., ignoring) the integrality requirement, solve this LP (this can be done in polynomial time), and then "rounding" the solution so obtained to obtained an integral solution as desired. The main challenge in designing the rounding procedure is to ensure that such rounding does not degrade the feasibility or the quality of the solution (i.e., the value of the objective function that was optimized) too much.

Recently, a new approach to rounding, known as iterative rounding [START_REF] Lau | Iterative Methods in Combinatorial Optimization[END_REF], has been shown to provide improved rounding guarantees. Analogously to prior rounding approaches, the first step requires that an LP-relaxation be solved and a non-integer solution (say, X) be obtained. However, instead of rounding all non integral values of X at the same time, only one variable is rounded; assume, for example, that the value of variable x 1 is set to x1 . Then the method iterates and solves a new LPrelaxation that is obtained from the original LP by fixing the value of x 1 to x1 . In this way, a new solution X is obtained; as in the previous case, the method now rounds one variable of X ; the method is iterated until all variables satisfy the given integrality constraints.

In this section, we seek to construct an ILP formulation of the problem of partitioning sporadic tasks upon heterogeneous multiprocessors that is more amenable to iterative rounding than the ILP formulations we have seen above. It will turn out (Theorem V.1 below) that this ILP has the same number of variables and constraints, but a poorer (larger) speedup factor than the one described in Section III-C (Theorem III.5). Hence from the perspective of just developing an ILP, this is not a particularly useful result. However, we will see that this ILP can in fact be rounded iteratively in a manner that we were unable to pull off with the earlier ILP formulations, resulting in a polynomial-time algorithm for partitioning sporadic tasks upon heterogeneous multiprocessors that has speedup bound of ≈ 7.83, thereby improving the ≈ 12.9 speedup bound of Marchetti-Spaccamela et al. [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF].

As before, we use variables x ij for each pair (i, j) ∈ N ×M , modeling the assignment of τ i to π j . Apart from the usual assignment constraints, the first constraints we consider are the utilization bounds on the tasks assigned to the same processor. That is, we require that

i∈N u ij x ij ≤ 1 ∀j ∈ M. ( 10
)
Now, let ρ denote any constant, ρ > 1. We de-fine the function r(x) := ρ log ρ x , and the set D ρ := {ρ 0 , ρ 1 , . . . , r(d max )}. We want to express the requirement that for all tasks assigned to the same processor with deadline at most ρ k , the sum of their WCETs is at most ρ k . Note that this is the set of tasks with r(d i ) ≤ ρ k . For technical reasons that will become apparent later (in Lemma V.2), we adopt the slightly weaker constraint

i∈N : r(di)≤d c ij 1 - d i p i x ij ≤ d ∀d ∈ D ρ , ∀j ∈ M. ( 11
)
We call these constraints [START_REF] Dertouzos | Control robotics : the procedural control of physical processors[END_REF] the relaxed dbf constraints. It is clear that these constraints have to be fulfilled by any feasible task assignment. (In particular, if

d i ≤ ρ k and x ij = 1, then dbf f,j (ρ k ) ≥ c ij > c ij (1 -d i /p i ),
where f is the assignment represented by x). We therefore arrive at the following ILP, denoted poly-ILP.

j∈M x ij = 1 ∀i ∈ N (12a) i∈N u ij x ij ≤ 1 ∀j ∈ M (12b) i∈N : r(di)≤d c ij 1 - d i p i x ij ≤ d ∀d ∈ D ρ , ∀j ∈ M (12c) x ij ∈ {0, 1} ∀i ∈ N, ∀j ∈ M s.t. c ij ≤ d i . (12d)
If poly-ILP is infeasible, then there can be no feasible task assignment. Now assume that it is feasible and consider its relaxation, which is obtained by replacing each constraint (12d) by

x ij ≥ 0 ∀i ∈ N, ∀j ∈ M s.t. c ij ≤ d i . ( 13
)
Since it is an LP and not an ILP, the relaxation can be solved in polynomial time. Let x * denote its solution. For each j ∈ M and deadline d ∈ D ρ , we compute the value

b j,d := i∈N : r(di)=d c ij (1 -d i /p i )x * ij .
Note that, by (12c),

d ≤d b j,d ≤ d ∀d ∈ D ρ , ∀j ∈ M. ( 14
)
Based on these computed values, we define a variation of poly-ILP, denoted by sparse-ILP in the sequel. We obtain the latter by replacing the constraints (12c) with the following set of constraints:

i∈N : r(di)=d c ij 1 - d i p i x ij ≤ b j,d ∀d ∈ D ρ , ∀j ∈ M.
By dividing both sides of the inequality by d, these constraints can also be written as

i∈N : r(di)=d cijd 1 - d i p i x ij ≤ bj,d ∀d ∈ D ρ , ∀j ∈ M. ( 15
)
where bj,d = b j,d /d ≤ 1 (since x * is feasible for the relaxation of poly-ILP) and cijd

= c ij /d ≤ 1 (since if r(d i ) = d then c ij ≤ d i ≤ d).
Let A be the set of vectors x satisfying (12a).

We can now express sparse-ILP in matrix notation as

{x ∈ A ∩ {0, 1} N ×M : Ax ≤ b, x ≥ 0},
where A and b are, respectively, the matrix of coefficients and the vector of right hand sides of the constraints (12b) and [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. Note that all entries of A and b take values between 0 and 1. By construction, if x * is a feasible solution for the LP relaxation of poly-ILP it is also feasible for the LP relaxation of sparse-ILP, and if the LP relaxation of sparse-ILP is infeasible, then no feasible task assignment exists. Our goal will be to round x * to an integral vector which approximately satisfies the constraints of sparse-ILP.

A reason for preferring sparse-ILP to poly-ILP is that the former is an ILP formulation in which the constraint matrix is sparse: each variable appears in only a small number of constraints. This sparsity gives the potential to derive efficient rounding schemes which result in integral solutions, violating the relaxed dbf-constraints only by constant factors. We present such a rounding scheme below; to this end, the following theorem shows that-even when violated up to constant factors-the relaxed dbf constraints ( 15), together with the utilization constraints (12b), are approximately sufficient.

Theorem V.1. Let β ≥ 1 and let f : N → M be an assignment encoded by a vector x ∈ A ∩ {0, 1} N ×M such that, for each j ∈ M and d ∈ D ρ , i∈N u ij xij ≤ β ( 16
)
and

i∈N : r(di)=d c ij 1 - d i p i xij ≤ b j,d + (β -1) • d. ( 17
)
Then dbf f,j (s) ≤ (β + ρ + (β -1)ρ 2 /(ρ -1))s for all s ≥ 0.

In particular, if β ≤ 2, f is a feasible assignment under a speedup factor of (2 + ρ + ρ 2 /(ρ -1)).

Proof. For any s ≥ 0 and j ∈ M , we bound dbf f,j (s) as follows:

dbf f,j (s) = i∈N : di≤s s + p i -d i p i c ij xij ≤ i∈N : di≤s s c ij p i + c ij 1 - d i p i xij ≤ i∈N : r(di)≤r(s) s c ij p j + c ij 1 - d i p i xij ≤ s i∈N c ij p i xij + i∈N : r(di)≤r(s) c ij 1 - d i p i xij = s i∈N u ij xij + log ρ (r(s)) k=0 i∈N : r(di)=ρ k c ij (1 - d i p i ) xij (16)
≤ βs + log ρ (r(s))

k=0 i∈N : r(di)=ρ k c ij (1 - d i p i ) xij (17)
≤ βs

+ log ρ (r(s)) k=0 b j,ρ k + (β -1)ρ k (14) ≤ βs + ρ log ρ (r(s)) + log ρ (r(s)) k=0 (β -1)ρ k = βs + r(s) + (β -1) log ρ (r(s)) k=0 ρ k = βs + r(s) + (β -1) • ρ log ρ (r(s))+1 -1 ρ -1 = βs + r(s) + (β -1) ρ • r(s) -1 ρ -1 ≤ (β + ρ + (β -1) ρ 2 ρ -1
)s.

The last inequality follows from r(s) ≤ ρ • s.

To construct x, we adopt an iterative rounding procedure that is similar to the procedure presented in [START_REF] Karp | Global wire routing in two-dimensional arrays[END_REF], [START_REF] Marchetti-Spaccamela | Assigning sporadic tasks to unrelated machines[END_REF]. The idea of the iterative rounding procedure is the following. In each iteration k, we first compute an extreme point solution x k of a linear program LP k , where LP 0 is the relaxation of sparse-ILP, and each LP k is obtained by fixing the value for some variables or removing some constraints of LP k-1 .

Given a feasible fractional solution x k , to define LP k+1 we first fix all variables which are integral in x k , i.e., those variables are not allowed to be changed anymore in the remainder of the procedure. Let s be the number of variables in LP k and let r a , r b and r b be the number of constraints of types (12a), (12b) and [START_REF] Karp | Reducibility among combinatorial problems[END_REF], respectively. Let r = r a + r b + r c . To obtain LP k+1 we either delete one or more variables, in case s > r, or delete a constraint while ensuring that in the final solution that constraint will not be violated too much. Along the way we ensure that the constraints of type (12a) are always satisfied exactly, so that x k ∈ A at all times.

Note that if there is some variable x ij that is fixed at value 1 and removed from the program, then for all j ∈ M \ {j}, x ij will be set to 0 and also be removed from the program. The constraint of type (12a) corresponding to this i is then superfluous and will also be removed.

To derive the bounds ( 16)-( 17), we need to study the coefficient matrix A in more detail. Let γ be the maximum, over all x ij , of the sum of the values of the coefficients of variable x ij in constraints (12b) and [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. We first derive a bound on γ. Lemma V.2. For any task set τ , γ ≤ 1.

Proof. Observe that γ is just the maximum value of u ij + cijd (1d i /p i ) across all variables x ij in the program. Recall that for all such pairs (i, j), c ij ≤ d i , i.e., cijd ≤ 1, otherwise the variable x ij is forced to 0 and removed from the LP. We can now bound

u ij + cijd 1 - d i p i ≤ c ij p i + 1 - d i p i ≤ c ij p i + 1 - c ij p i = 1.
The following technical lemma is instrumental to our rounding procedure. It is a specialization to our setting of a more general rounding result for assignment LPs, from another paper currently under review [START_REF] Bonifaci | Hierarchical and semi-partitioned machine scheduling[END_REF].

Lemma V.3. Let LP k be the linear program that is solved in iteration k of the rounding procedure, with s variables and r constraints. Let x k be an extreme point solution to this LP. Then either, (i) x k has at least one integer component; or (ii) there is j ∈ M and a corresponding constraint of type (12b) such that i∈N u ij z ij -i∈N u ij x k ij ≤ γ for any integer solution z; or (iii) there are j ∈ M , d ∈ D ρ and a corresponding constraint of type [START_REF] Karp | Reducibility among combinatorial problems[END_REF] such that

i∈N : r(di)=d cijd 1 - d i p i (z ij -x k ij ) ≤ γ
for any integer solution z.

Proof. Let A be the coefficient matrix of LP k . If s > r, the null space of A is nontrivial, so let x 0 be a nonzero vector in the null space. Since x k is an extreme-point solution to LP k , it cannot be expressed as the convex combination of two (or more) solutions to LP k . If x k does not have any integral entry, then we can find a value δ > 0 such that x k +δx 0 and x k -δx 0 are both solutions to LP k (since A(x ± δx 0 ) = Ax) and, in particular, x k is a convex combination of these two solutions. Therefore x k must have at least one integral entry.

If s ≤ r, we show that there always exists a constraint of type (12b) or type [START_REF] Karp | Reducibility among combinatorial problems[END_REF] such that max z∈S {(Az) l -(Ax) l } ≤ γ, where γ is the maximum sum of coefficients in a column of constraints (12b) and ( 15) and where S is the integer solution space for all remaining variables, i.e., S = {0, 1} s .

We show the statement by contradiction. Assume that the statement is not true, that is, for each constraint l of type (12b) or [START_REF] Karp | Reducibility among combinatorial problems[END_REF] it holds that there exists a vector z ∈ S such that

(Az) l -(Ax) l > γ. ( 18
)
Note that all variables still present in the linear program correspond to a processor j ∈ M and a task i ∈ N that is not yet assigned fully to one processor, but fractionally to multiple processors. Hence, the constraint of type (12a) corresponding to each τ i is still present in the linear program. It follows that j∈M i∈N : xij ∈(0,1)

x ij = r a , ( 19
)
where r a is the number of constraints of type (12b) remaining in LP k . Define L as the set of constraints of types (12b) and [START_REF] Karp | Reducibility among combinatorial problems[END_REF] present in the current linear program, and let r b and r c be their number, respectively (so r a + r b + r c = r). For any q = (i, j), let L q denote the set of these constraints containing variable x q ; by definition of γ, we have

max q l∈L q a lq ≤ γ. ( 20
)
Then,

γ(r -r a ) = γ(r b + r c ) (18)
< l∈L max z∈S ((Az) l -(Ax) l ) as all alq≥0 = l∈L ((A1) l -(Ax) l ) = l∈L q a lq (1 -x q ) = q l∈L q a lq (1 -x q ) ≤ q γ(1 -x q ) = γs - q γx q = γ(s -r a ). (21)
The second inequality follows from [START_REF] Raravi | Real-Time Scheduling on Heterogeneous Multiprocessors[END_REF].

The chain of inequalities implies that γ(rr a ) < γ(sr a ) ⇒ r < s which is a contradiction to being in the case that s ≤ r. Hence we conclude that if s ≤ r, there must be a constraint l of type (12b) or [START_REF] Karp | Reducibility among combinatorial problems[END_REF] for which max z∈S {(Az) l -(Ax) l } ≤ γ. Lemma V.3 is used to guide the rounding process. If Case (i) applies, the variables that have an integer value are fixed at that value and removed from the LP. If a variable x ij is fixed at value 1, then for all j ∈ M \{j}, the variables x ij are fixed at value 0 and the constraint of type (12a) corresponding to i is removed. If we are in Case (ii) or (iii), the constraint for which the claim holds can be found in polynomial time by checking, for each constraint l ∈ L of type (12b) or [START_REF] Karp | Reducibility among combinatorial problems[END_REF], whether q (1x q ) ≤ γ. This is sufficient since all a lq ≥ 0 and the maximum value any variable x q can take is 1. If such a constraint is of type (12b) (Case (ii)) or (15) (Case (iii)), the final task assignment will satisfy [START_REF] Karp | Global wire routing in two-dimensional arrays[END_REF] or [START_REF] Lau | Iterative Methods in Combinatorial Optimization[END_REF] for that constraint, respectively, even if the constraint is dropped; thus, we drop the constraint, obtaining the next (smaller) LP.

After either all constraints have been removed or the values of all variables have been fixed at an integer value, we obtain an integral vector x which satisfies i∈N u ij xij ≤ 1 + γ for each j ∈ M and i∈N : r(di)=d cijd 1 -di pi x ij ≤ bj,d + γ for all j ∈ M and all deadlines d ∈ D ρ . Hence, the vector x satisfies constraints ( 16), [START_REF] Lau | Iterative Methods in Combinatorial Optimization[END_REF] with β := 1 + γ. We are now in the position to invoke Theorem V.1 to obtain our final guarantee.

Theorem V.4. There is a polynomial-time partitioning algorithm with a speedup bound of (5 + 2 √ 2) ≈ 7.83 for the problem of assigning constrained-deadline tasks to heterogeneous processors.

Proof. All steps required to construct x can be carried out in polynomial time. The assignment induced by x satisfies ( 16)-( 17) with β = 1+γ ≤ 2 (Lemma V.2). Thus, by Theorem V.1 with ρ = 1 + 1/ √ 2, the assignment induced by x is feasible with speedup

2 + ρ + ρ 2 ρ -1 = 5 + 2 √ 2 ≈ 7.83.

VI. SCHEDULABILITY EXPERIMENTS

In the sections above, we saw how the problem of partitioned scheduling of sporadic task systems upon unrelated multiprocessors could be modeled by ILPs. Our motivation for doing so is that the optimization community has devoted immense effort to coming up with extremely efficient (although still exponential-time, since solving ILPs is NP-hard) algorithms for solving ILPs, and highly-optimized libraries implementing these efficient algorithms are widely available. This is particularly true for ILPs like the ones we have constructed above, in which each variable is further constrained to take in only the values zero or one. In this section, we validate the performance of our ILP-based schedulability tests against synthetic workloads in terms of the percentage of schedulable task sets. Our results strongly suggest that the ILP model discussed in Section IV is superior in practice.

A. Generation of the task sets and solutions

We developed a parametric framework with several parameters (m, κ, p, Ū , α -they are detailed below) to randomly generate our workloads; this framework is general enough to support our entire range of experiments.

We consider m-processor platforms and n = κm tasks, with κ ≥ 1 an integer-valued parameter. We randomly generate an affinity mask R i,j for each i ∈ N and j ∈ M : R i,j ← 1 with probability p and 0 with probability (1p). These affinity masks help define the C i,j values: C i,j has a value < ∞ if and only if R i,j = 1. If the generated mask does not allow a particular task to be processed on any processor, we then allow that task to be processed upon a randomly chosen processor.

We then generate utilization values for every allowed pair (i, j) for which R i,j = 1. Tasks are grouped into m groups of size κ each: tasks τ 1+(k-1)κ to τ kκ form the kth group. For each group we use the UUNISORT algorithm [START_REF] Bini | Measuring the performance of schedulability tests[END_REF] to generate randomly distributed utilizations with total value Ū for the allowed task-processor pairs in the group. Note that since there are m groups, each of total utilization Ū , the value Ū represents the average load that a processor can expect if tasks are randomly assigned. Note that Ū ≤ 1 is not a necessary condition for schedulability (indeed some of our ILP formulations are able to schedule task sets with Ū > 1).

We generate the periods by setting p i = 2 Δi , with each Δ i uniformly distributed in the range 3...10. The worstcase execution times are computed directly from the periods and utilizations. Finally, the relative deadline of each task is

sampled uniformly in the range

[(1-α)•(max j c ij )+αp i , p i ],
where α ∈ [0, 1].

In the experiments we consider the two ILP models discussed in Section III-B (Eqs. ( 3)-( 5)) and Section IV (Eqs. ( 7)-( 9)), the latter with k = 3. All optimization models have been solved by using a branch-and-cut approach implemented in the mathematical programming solver Gurobi 6.50 [START_REF]Gurobi Optimizer[END_REF] on a PC with Intel i7-4770 CPU at 3.4 GHz and 16Gb RAM. Instances of the ILP model of Section III-B are solved within 3 seconds, and within less than 1 second on average; instances of the ILP model of Section IV are solved within 109 seconds, and within less than 15 seconds on average.

B. Discussion of the results

a) Variation of Ū (Figure 1): In the first type of experiment, we use the average load Ū as the independent variable. We vary Ū from 0.2 to 1.5. We fix m = 10, κ = 10, p = 0.5, α = 0.2. Again, for each experiment, we generated 10 task sets for each value on the x-axis. When the percentage of schedulable task sets was strictly between 0 and 1, we generated 20 additional task sets to achieve a higher precision. Indeed, as could be expected, schedulability decreases when the load factor Ū increases. It is interesting to note that for the strengthened ILP model of Theorem IV.2, more than 90% of the task sets are schedulable as long as Ū ≤ 1.

b) Variation of m (Figure 2(a)): In the second type of experiment, we look at the impact of the number of processors on schedulability, so we vary m from 2 to 10. We fix κ = m, so n = m 2 . In this set of experiments, we fix Ū = 1, p = 1, α = 0.2. For each experiment, we generated 10 task sets for each value on the x-axis. Figure 1 shows the dependency on m of the percentage of task sets are guaranteed to be schedulable by Corollary III.4 (for the first ILP) and Theorem IV.2 (for the second ILP), the latter using a formulation in which k = 3. In both cases, schedulability increases with the number of processors even though Ū is fixed. This is due to the fact that, for a fixed total utilization value of each group, a higher number of tasks in a group implies lower utilization values for the individual tasks, and therefore a more efficient partitioning. c) Variation of p (Figure 2(b)): In the third type of experiment, we control the sparsity of the processor affinity matrix R. We vary p from 0.2 to 0.9. We fix m = 10, κ = 10, Ū = 1, α = 0.2. For each experiment, we generated 10 task sets for each value on the x-axis. We find out that the sparsity has a high impact on schedulability: there are clear schedulability thresholds around p = 0.7 (for the first ILP) and p = 0.45 (for the second ILP). This is not entirely unexpected, as when the affinity matrix is sparser, it may happen that several tasks of large combined utilization can only be assigned to a small set of processors.

VII. SUMMARY AND CONCLUSIONS

In this work, we proposed a partitioning approach for constrained-deadline tasks on heterogenous (unrelated) processors. The approach is based on integer linear programming formulations and allows the derivation of guaranteed speedup bounds and consequently, sufficient schedulability tests.

Experiments among randomly generated task workloads clearly show that one of the proposed approaches is viable in terms of computation time and not as pessimistic in terms of schedulability as could be expected, especially when the task-processor affinity relation is dense.

Figure 1 .

 1 Figure 1. Experimental results I. The diagram show the percentage of task sets found to be schedulable by Corollary III.4 (Eqs. (3)-(5)) and by Theorem IV.2 (Eqs. (7)-(9) with k = 3). (a) Variation of Ū (m = 10, κ = 10, p = 0.5, α = 0.2).

Figure 2 .

 2 Figure 2. Experimental results II. The diagrams show the percentage of task sets found to be schedulable by Corollary III.4 (Eqs. (3)-(5)) and by Theorem IV.2 (Eqs. (7)-(9) with k = 3). (a) Variation of m (κ = m, Ū = 1, p = 1, α = 0.2). (b) Variation of p (m = 10, κ = 10, Ū = 1, α = 0.2).

Although we expect that most of our results will also extend to the arbitrary-deadline sporadic task model, for ease of presentation we do not explore this issue any further in this paper, but leave it for future work.

28th Euromicro Conference on Real-Time Systems 2159-3833/16 $31.00 © 2016 IEEE DOI 10.1109/ECRTS.2016.10

ACKNOWLEDGMENTS

Work supported by NSF grants CNS 1115284, CNS 1218693, CNS 1409175, and CPS 1446631, AFOSR grant FA9550-14-1-0161, ARO grant W911NF-14-1-0499, and a grant from General Motors Corp. This work has also been partially supported by the research project "Designing Human-Agent Collectives for Sustainable Future Societies" (C26A15TXCF) of Sapienza University of Rome.