Speed scaling on parallel processors with migration

Energy consumption is a major issue in our days. Great efforts are devoted to the reduction of energy dissipation in computing environments ranging from small portable devices to large data centers. From an algorithmic point of view, new challenging optimization problems are studied in which the energy consumption is taken into account as a constraint or as the optimization goal itself (for recent reviews see Albers 2010, 2011; Irani and Pruhs 2005). This later approach has been adopted in the seminal paper of Yao et al. (1995) who considered the problem of scheduling a set of jobs with release dates and deadlines on a single processor so that the total energy is minimized, under the so-called speed scaling model in which the speed of a processor can be varied over time and the power consumption is a convex function of the processor’s speed. Specifically, at a given time t, if the speed of a processor is s(t), then the power consumption is \(s(t)^{\alpha }\), where \(\alpha >1\) is a constant, and the energy consumption is the power integrated over time.

Single processor Yao et al. (1995) proposed an optimal offline algorithm, known as the YDS algorithm according to the initials of the authors, for the problem of minimizing the energy with preemptions, i.e., where the execution of a job may be interrupted and resumed later on. In the same work, they initiated the study of online algorithms for this problem, introducing the Average Rate (AVR) and the Optimal Available (OA) algorithms. Bansal et al. (2007) proposed a new online algorithm, the BKP algorithm according to the authors’ initials, which has better competitive ratio than AVR and OA for large values of \(\alpha \).

Multiprocessor When there are multiple processors available, we may consider different variants of speed scaling problems. In the non-migratory variant, we allow preemptions of jobs but not migrations. This means that a job may be interrupted and resumed later on the same processor, but it is not allowed to continue its execution on a different processor. In the migratory variant, both preemptions and migrations of jobs are allowed.

Albers et al. (2007) considered the multiprocessor non-migratory problem of minimizing the energy of a set of unit-work jobs. For the case in which the jobs have agreeable deadlines, they proposed an optimal polynomial time algorithm. Then, they showed that the problem is \(\mathcal {NP}\)-hard when the jobs have arbitrary deadlines and they proposed an \(\alpha ^{\alpha }2^{4\alpha }\)-approximation algorithm for it. Note that, the ratio of this algorithm is constant because \(\alpha \) is a constant. For the more general problem in which the jobs have arbitrary works, Greiner et al. (2009) established a generic reduction transforming a \(\rho \)-approximation algorithm for the single-processor problem to a \(\rho B_{\lceil \alpha \rceil }\)-approximation algorithm for the multiprocessor non-migratory problem, where \(B_{\lceil \alpha \rceil }\) is the \(\lceil \alpha \rceil \)-th Bell number. This result basically implies a constant factor approximation algorithm for the multiprocessor non-migratory problem with arbitrary works.

For the migratory variant, Chen et al. (2004) initiated the study of the multiprocessor speed scaling problem of minimizing the energy and they proposed a greedy algorithm for the basic setting in which all jobs have the same release date and deadline. Bingham and Greenstreet (2008) proposed a polynomial-time algorithm for the more general setting where the jobs have arbitrary release dates and deadlines. The algorithm in Bingham and Greenstreet (2008) needs an algorithm for linear programming as a black box. So, after this work, an intriguing open question was whether there exists a faster combinatorial algorithm.

It has to be noticed that after the conference version of our paper, multiprocessor speed scaling problems attracted much attention and new papers appeared (e.g., Bampis et al. 2012, 2013) in the direction of improving the above results and generalizing them for power-heterogeneous environments in which different processors obey to different power functions.

Multi-objective In general, energy and performance are conflicting objectives and a series of papers addressed speed scaling problems in a multicriteria context. Pruhs et al. (2008) studied the problem of optimizing performance without exceeding a fixed budget of energy. Their objective was total flow time minimization and they presented an optimal polynomial-time algorithm for instances with unit-work jobs. In order to prove the optimality of their algorithm, they formulated the problem as a convex program and they showed that their algorithms always produces a solution satisfying the well-known Karush, Kuhn, Tucker (KKT) conditions which are necessary and sufficient conditions for optimality in convex programming. Albers and Fujiwara (2007) studied the problem of minimizing the total flow time plus energy which is an alternative way for optimizing two conflicting objectives. Finally, Chan et al. (2009) proposed an online algorithm for maximizing the throughput and minimizing the energy of a set of jobs which have to be executed by a processor whose speed is bounded above. Their algorithm has constant competitive ratio in terms of both objectives.

Our contribution and organization of the paper We consider the multiprocessor migratory speed scaling problem and our objective is energy minimization. In Sect. 3, we formulate the problem as a convex program. In Sect. 4, we apply the KKT conditions to our convex program and we obtain a set of structural properties of optimal schedules. Then, in Sect. 5, we propose an optimal algorithm which is based on maximum flow computations. The running time of our algorithm, which we call BAL, is \(O(nf(n)\log U)\), where n is the number of jobs, U is the range of all possible values of processors’ speed divided by the desired accuracy and f(n) is the complexity of computing a maximum flow in a layered graph with O(n) vertices. Independently to our work, Albers et al. (2011) proposed another optimal algorithm for the same problem which also explores the relation of the problem with maximum flow.

We begin with a formal description of our problem and some definitions. An instance of our problem consists of a set of jobs \({\mathcal {J}}=\{J_1,\ldots ,J_n\}\) which have to be executed by m parallel processors. Each job \(J_j\) is specified by an amount of work \(w_j\), a release date \(r_j\) and a deadline \(d_j\). The processors are speed scalable which means that they can vary their speeds dynamically over time. Every processor satisfies the speed-to-power function \(P(s)=s^\alpha \), where P(s) is the processor’s power consumption if it runs with speed s and \(\alpha >1\) is a constant. It has to be noticed that the speed of a processor may be any non-negative value. If a processor runs with speed s for t units of time, then it executes \(t\cdot s\) units of work and it consumes \(t\cdot s^{\alpha }\) units of energy. In our setting, we allow preemptions and migrations of the jobs. That is, a job may be executed on some processor, suspended and resumed later on the same or on a different processor. However, we do not allow parallel execution of a job which means that a job cannot be run by more that one processors at a given time. Our objective is to find a schedule with minimum energy consumption so that every job is entirely executed between its release date and its deadline.

An important remark is that there is always an optimal schedule for our problem such that every job \(J_j\) is executed with fixed speed \(s_j\). This is a well-known fact for most speed scaling problems (see Yao et al. 1995) and it can be derived by using the convexity of the speed-to-power function.

Let \(t_0<t_1<\cdots <t_{\ell }\) be the times which correspond to all the release dates and deadlines of the jobs. We define the intervals \(I_i=[t_{i-1},t_i)\), for all \(1\le i\le \ell \), and we refer by \({\mathcal {I}}\) to the set of all these intervals, i.e., \({\mathcal {I}}=\{I_1,I_2,\ldots , I_{\ell }\}\). For a time interval \(I_i\in {\mathcal {I}}\), we denote by \(|I_i|\) its length and by \({\mathcal {A}}_i\) the set of jobs which are allowed to be executed during \(I_i\), i.e., \({\mathcal {A}}_i=\{J_j\in {\mathcal {J}}:I_i\subseteq [r_j,d_j)\}\). If \(J_j\in {\mathcal {A}}_i\), then we say that job \(J_j\) is active during \(I_i\).

Next, we state a problem which we call Work Assignment Problem (WAP) and which is a key ingredient for our analysis. WAP resembles to our original problem except that the speed of each processor is fixed (it cannot be varied) and the number of available processors is not the same at each time. An instance of WAP consists of a set of jobs \({\mathcal {J}}=\{J_1,\ldots ,J_n\}\) and a set of disjoint time intervals \({\mathcal {I}}=\{I_1,I_2,\ldots ,I_{\ell }\}\). Each job \(J_j\) has an amount of work \(w_j\) and it is active (i.e., it is allowed to be executed) in a subset of the intervals. During interval \(I_i\) there are \(m_i\) available processors. Furthermore, we are given a value v. Our objective is to decide whether there exists a feasible schedule in which all jobs are feasibly executed with a fixed speed v. Note that a schedule is feasible only if each job is entirely executed during the intervals that it is active. Preemptions and migrations of jobs are allowed but parallel execution of a job is not permitted. In WAP, each job \(J_j\) has a fixed processing time equal to \(\frac{w_j}{v}\). Therefore, WAP can be solved in polynomial time with a variant of the optimal algorithm of the well-known scheduling problem \(P|pmtn,r_j,d_j|-\) (see Baptiste et al. 2004).

In this section, we propose a convex program for our problem. We introduce the variables \(s_j\) and \(t_{i,j}\), for all \(J_j\in {\mathcal {J}}\) and \(I_i\subseteq [r_j,d_j)\), corresponding to the speed of job \(J_j\) and the total amount of time that job \(J_j\) is processed during \(I_i\), respectively. Then, the problem can be formulated as follows:Expression (1) corresponds to the total energy consumption. Constraints (3) enforce that at least \(w_j\) units of work are executed for each job \(J_j\). Because of the constraints (4), at most m processors are used at each time. Due to the constraints (5), a job \(J_j\) is executed by at most one processor at each time. Constraints (6) and (6) ensure the non-negativity of the variables \(s_j\) and \(t_{i,j}\). It has to be mentioned that Constraints (1)–(6) are not sufficient for feasibility, i.e., there exist unfeasible schedules satisfying all of them. However, by applying the well-known McNaughton’s algorithm (McNaughton 1959) in each interval \(I_i\in {\mathcal {I}}\), every such schedule can be converted into a feasible one without increasing the total energy consumption.

The single variable functions \(w_js_j^{\alpha -1}\) are convex, as \((w_js_j^{\alpha -1})''=(\alpha -1)(\alpha -2)w_js_j^{\alpha -3}>0\), for each \(\alpha >2\). Similarly, the single variable functions \(w_j/s_j\) are also convex. Because the objective function and Constraints (3) consist of convex function sums while all remaining constraints are linear, the above mathematical program is convex for \(\alpha >2\). By using variable \(t_j\) corresponding to job \(J_j\) processing time instead of variable \(s_j\), we obtain an equivalent mathematical program which is convex for any \(\alpha >1\). In particular, every occurrence of \(s_j\) is replaced by \(w_j/t_j\), the objective function becomes \(\sum _{j\in {\mathcal {J}}}w_j^{\alpha }/t_j^{\alpha -1}\), Constraints (3) become \(\sum _{I_i\subseteq [r_j,d_j)}t_{i,j} \ge t_j\), for \(J_j\in {\mathcal {J}}\), and all other constraints remain identical. Function \(w_j^{\alpha }/t_j^{\alpha -1}\) is convex, since \((w_j^{\alpha }/t_j^{\alpha -1})''=\alpha (\alpha -1)w_j^{\alpha }/t_j^{\alpha +1}>0\), for each \(\alpha >1\). Because speed relationships are more intuitive, we elaborate on the convex program with the \(s_j\) variables. Nevertheless, our analysis may be equivalently applied using the convex program with the \(t_j\) variables and obtain an optimal algorithm for all \(\alpha >1\).

Since our problem can be formulated as a convex program, it can be solved in polynomial time as follows. We solve the convex program in polynomial time by applying the Ellipsoid Algorithm and we obtain a processing time (i.e., speed) for each job. Once these processing times have been computed, we construct a feasible schedule by using an optimal algorithm for the feasibility problem \(P|pmtn,r_j,d_j|-\). In the remainder of the paper, we derive a faster combinatorial algorithm.

In what follows, we elaborate on the structure of an optimal schedule for our problem and we derive some properties which are necessary and sufficient for optimality. These properties are obtained by using the well-known KKT (Karush, Kuhn, Tucker) conditions which are necessary and sufficient for optimality in convex programming (see Nemirovski et al. 1994). A description of the KKT conditions can be found in the “Appendix”. We apply the KKT conditions to the convex program that we presented in the previous section and we obtain the following lemma which specifies the structure of an optimal schedule.

Next, we propose an optimal combinatorial algorithm for our problem which constructs schedules satisfying Lemma 1.

Our algorithm is based on the notion of critical jobs defined below. Initially, the algorithm conjectures that all jobs are executed at the same speed in the optimal schedule and it assigns to all of them a sufficiently large speed. The key idea is to continuously decrease the speeds of the jobs step by step. At each step, it assigns a speed to the critical jobs which are ignored in the subsequent steps and it goes on reducing the speeds of the remaining jobs. At the end of the last step, every job has been assigned a speed. Critical jobs are recognized by finding a minimum (s, t)-cut in an appropriate graph as we describe in the following. Once the algorithm has computed a speed, i.e., a processing time, for each job, it constructs a feasible schedule by applying an optimal algorithm for \(P|pmtn,r_j,d_j|-\).

At a given step, the algorithm performs a binary search in order to reduce the speeds of the jobs. The binary search is performed by solving repeatedly different instances of the WAP. Each instance of the WAP is solved by a maximum flow computation. Specifically, given an instance \(<{\mathcal {J}},{\mathcal {I}},v>\) of the WAP, the algorithm constructs a directed graph G as follows (Fig. 1). There is one node for each job \(J_j\in {\mathcal {J}}\), one node for each interval \(I_i\in {\mathcal {I}}\), a source node s and a destination node t. The algorithm introduces an arc \((s,J_j)\), for each \(J_j\in {\mathcal {J}}\), with capacity \(\frac{w_j}{v}\), an arc \((J_j,I_i)\) with capacity \(|I_i|\), for each couple of job \(J_j\) and interval \(I_i\) such that \(J_j\in {\mathcal {A}}_i\), and an arc \((I_i,t)\) with capacity \(m_i|I_i|\) for each interval \(I_i\in {\mathcal {I}}\). We say that this is the corresponding graph of \(<{\mathcal {J}},{\mathcal {I}},v>\). The algorithm decides if an instance \(<{\mathcal {J}},{\mathcal {I}},v>\) of the WAP is feasible by computing a maximum (s, t)-flow on its corresponding graph G, based on the following theorem.

We are ready to introduce the notion of criticality for feasible instances of the WAP. Given a feasible instance for the WAP, we say that job \(J_c\) is critical if, for any feasible schedule \({\mathcal {S}}\) and for each interval \(I_i\) such that \(J_c\in {\mathcal {A}}_i\), either \(t_{i,c}=|I_i|\) or \(\sum _{J_j\in {\mathcal {A}}_i}t_{i,j}=m_i|I_i|\), where \(t_{i,j}\) is the total amount of time that job \(J_j\) is processed during \(I_i\) in \({\mathcal {S}}\). Moreover, we say that an instance \(<{\mathcal {J}},{\mathcal {I}},v>\) of the WAP is critical if v is the minimum speed so that the set of jobs \({\mathcal {J}}\) can be feasibly executed during the intervals in \({\mathcal {I}}\). We refer to this speed v as the critical speed of \({\mathcal {J}}\) and \({\mathcal {I}}\).

Based on the Theorem 1, we extend the notion of criticality. Let us consider a feasible instance \(<{\mathcal {J}},{\mathcal {I}},v>\) of the WAP and let G be its corresponding graph. Given an arc e and a feasible (s, t)-flow \(\mathcal {F}\) of G, we say that the arc e is saturated by \(\mathcal {F}\) if the amount of flow that crosses the arc e according to \(\mathcal {F}\) is equal to the capacity of e. Additionally, we say that a path p of G is saturated by \(\mathcal {F}\) if there exists at least one arc e in p which is saturated. Then, a job \(J_c\) is critical if every path \(J_c,I_i,t\) is saturated by any maximum (s, t)-flow \(\mathcal {F}\).

In order to continue our analysis, we need the following lemma which relates, in a sense, the notions of critical job and critical instance.

Note that the instance \(<{\mathcal {J}},{\mathcal {I}},v-\epsilon>\) is not feasible if \(<{\mathcal {J}},{\mathcal {I}},v>\) is critical. Up to now, the notion of a critical job has been defined only in the context of feasible instances. We extend this notion for unfeasible instances as follows. In an unfeasible instance \(<{\mathcal {J}},{\mathcal {I}},v-\epsilon>\), a job \(J_j\) is called critical if every path \(J_j,I_i,t\) is saturated by any maximum (s, t)-flow in the corresponding graph \(G'\).

Let \(<{\mathcal {J}},{\mathcal {I}},v>\) be a critical instance of the WAP and let G be its corresponding graph. Next, we propose a way for identifying the critical jobs of \(<{\mathcal {J}},{\mathcal {I}},v>\) using the graph \(G'\) that corresponds to the instance \(<{\mathcal {J}},{\mathcal {I}},v-\epsilon>\), for some sufficiently small constant \(\epsilon >0\) based on Lemmas 3 and 4 below. The value of \(\epsilon \) is such that the two instances have exactly the same set of critical jobs. Moreover, the critical jobs of \(<{\mathcal {J}},{\mathcal {I}},v-\epsilon>\) can be found by computing a minimum (s, t)-cut in the graph that corresponds to \(<{\mathcal {J}},{\mathcal {I}},v-\epsilon>\).

The following lemma is a direct consequence of the definition of criticality on feasible and infeasible WAP instances.

We are now ready to give a high level description of our algorithm. When the algorithm begins, we assume that the optimal schedule consumes a large amount of energy and all jobs are executed with the same speed \(s_{UB}\). This speed value is selected so that there exists a feasible schedule executing all jobs with equal speed \(s_{UB}\). Then, the algorithm decreases the common speed of all jobs up to a point where no further reduction is possible so as to obtain a feasible schedule. At this point, all jobs are assumed to be executed with the same speed, which is critical, and there is at least one job that cannot be executed with speed less than this, in any feasible schedule. The jobs that cannot be executed with speed less than the critical one form the current set of critical jobs. So, the critical job(s) is (are) assigned the critical speed and is (are) ignored thereafter. In what follows, the algorithm considers the subproblem in which some jobs are omitted (critical jobs), because they are already assigned the lowest speed possible (critical speed) so that they can be feasibly executed, and there are less than m processors during some intervals because these processors are dedicated to the omitted jobs.

In more detail, the algorithm schedules the jobs in a sequence of \(\ell \le n\) discrete steps. In the initial step, it identifies the set \({\mathcal {J}}_{crit}\) of critical jobs which are the ones executed with the maximum speed in the optimal schedule. To do so, it first computes the speed \(s_{crit}\) that these jobs are assigned, i.e., the speed for which \(<{\mathcal {J}},{\mathcal {I}},s_{crit}>\) is a critical WAP instance. The value \(s_{crit}\) is determined by performing binary search in the interval \([s_{LB},s_{UB}]\), where \(s_{LB}\) is a speed value such \(<{\mathcal {J}},{\mathcal {I}},s_{LB}>\) is infeasible. Once \(s_{crit}\) is determined, the critical jobs are identified by computing a maximum flow on the infeasible WAP instance \(<{\mathcal {J}},{\mathcal {I}},s_{crit}-\epsilon>\). The value \(\epsilon \) is selected so that it satisfies the requirement of the Lemma 3, i.e., the feasible, critical WAP instance \(<{\mathcal {J}},{\mathcal {I}},s_{crit}>\) and the infeasible WAP instance \(<{\mathcal {J}},{\mathcal {I}},s_{crit}-\epsilon>\) have the same set of critical jobs. Based on the maximum flow computation, the algorithm determines the critical jobs using Lemma 4 which indicates that there is a unique minimum cut on the corresponding graph of \(<{\mathcal {J}},{\mathcal {I}},s_{crit}-\epsilon>\), for any \(\epsilon >0\) upper bounded as indicated by Lemma 3. Note that, if we choose \(\epsilon =0\), then the graph of \(<{\mathcal {J}},{\mathcal {I}},s_{crit}>\) has multiple different minimum cuts with respect to the number of \((s,J_j)\) edges, because it is a feasible WAP instance, and identifying the critical jobs is not obvious. This observation is the reason for detecting the critical jobs on the graph of \(<{\mathcal {J}},{\mathcal {I}},s_{crit}-\epsilon>\). Once the algorithm identifies the critical jobs, it goes on with the remaining jobs and machine-intervals in the same manner. Algorithm 1 is a pseudocode of the proposed algorithm.

Next, we derive a valid, concrete value \(\epsilon \). Given a value \(\epsilon \) in accordance with Lemma 3, Algorithm 1 produces the distinct job speed values \(s_1>s_2>\cdots >s_{\ell }\). Because these speed values are critical speeds of critical jobs in critical WAP instances, they must belong to a well-defined discrete, exponential set as indicated by the following lemma.

In what follows, we derive a suitable value for \(\epsilon \) assuming that input data are integers. However, the arguments can be adapted to obtain an alternative, valid \(\epsilon \) in the case of bounded rational input data. Lemma 3 selects a value \(\epsilon \) such that the feasible, critical WAP instance \(<{\mathcal {J}},{\mathcal {I}},v>\) and the infeasible instance \(<{\mathcal {J}},{\mathcal {I}},v-\epsilon>\) have the same set of critical jobs, and thus the same set of non-critical jobs. In each step of the algorithm, this requirement for the value \(\epsilon \) is equivalent to \(s_k-s_{k+1}\ge \epsilon \). Otherwise, by the way the algorithm computes \(s_k\) and \(s_{k+1}\) and the way \(\epsilon \) is obtained in the proof of Lemma 3, the corresponding WAP instances \(<{\mathcal {J}},{\mathcal {I}},v>\) and \(<{\mathcal {J}},{\mathcal {I}},v-\epsilon>\) in the computation of \(s_k\) would not have the same set of non-critical jobs, i.e., we would have a contradiction. Because the input data are integral and the fact that the speed values produced by the algorithm belong to a discrete set as indicated by Lemmas 5 and 6 derives an appropriate \(\epsilon \) value.

Note that the binary search procedure may compute \(s_{crit}\) subject to \(\epsilon \) accurracy. However, once the set \({\mathcal {J}}_{crit}\) of critical jobs has been determined, we may compute the critical speed exactly as follows. For each interval \(I_i\), let \(m_i\) be the number of available processors. Then, \(\min \{|{\mathcal {J}}_{crit}|,m_i\}\) processors are occupied by the jobs \({\mathcal {J}}_{crit}\) which are scheduled with constant speed so as to occupy these processors in every interval. This last speed is equal toDue to the convexity of the speed-to-power function, we know that each job \(J_j\) cannot be executed with speed less than its density \(\delta _j=\frac{w_j}{d_j-r_j}\) in any optimal schedule. Therefore, given a set of jobs \({\mathcal {J}}\), we know that there does not exist an optimal schedule that executes all jobs with a speed \(s<\max _{J_j\in {\mathcal {J}}}\{\delta _j\}\). Also, observe that if all jobs have speed \(s=\max _{I_i\in {\mathcal {I}}}\{ \frac{1}{|I_i|} \sum _{J_j\in {\mathcal {J}}} w_j\}\), then we can construct a feasible schedule. These bounds define the search space of the binary search performed in the initial step. In the next step the critical speed of the previous step is an upper bound on the speed of all remaining jobs and a lower bound is the maximum density among them. We use these updated bounds to perform the binary search of the current step and we go on like that.

We turn, now, our attention to the running time of the algorithm. Because of Lemma 2, at least one job is scheduled at each step of the algorithm. Therefore, there will be at most n steps. Assume that U is an upper bound on the speed of any job in the optimal schedule, e.g., \(U=\max _{I_i\in {\mathcal {I}}}\{ \frac{1}{|I_i|} \sum _{J_j\in {\mathcal {J}}} w_j\}\). Then, the binary search needs to check \(O(\log \frac{U}{\epsilon })\) values of speed to determine the next critical speed at one step, where \(\epsilon \) is small enough so that Lemmas 3 and 4 are satisfied. That is, BAL performs \(O(\log \frac{U}{\epsilon })\) maximum flow calculations at each step. Thus, the overall complexity of our algorithm is \(O(nf(n)\log \frac{U}{\epsilon })\), where f(n) is the complexity of computing a maximum flow in a graph with O(n) vertices.

In a graph with V vertices and E edges, a maximum flow can be computed in \(O(V^2E)\) time using (i) the push-relabel algorithm (Ahuja et al. 1993), or (ii) Dinic’s blocking flow algorithm (Dinitz 2006). Using the dynamic tree data structure by Sleator and Tarjan (1983), a maximum flow is computed in \(O(VE\log V)\) time. The network of Algorithm 1 contains \(V=O(n)\) vertices and \(E=O(n^2)\) edges. Based on this result, we conclude the following corollary.

We studied the multiprocessor speed scaling problem of minimizing the energy with migrations. We proposed a combinatorial polynomial-time algorithm based on a reduction to the maximum flow problem. Since there is not much work on problems with migrations there are many directions and speed problems to be considered in a multicriteria context. All these problems seem to be very interesting and might require new algorithmic techniques because of their continuous nature. We believe that the approach used in our paper might be useful in this direction.