Speed scaling on parallel processors with migration

DOI10.1007/978-3-642-32820-6_15MaRDI QIDQ4649807zbMATH OpenOpenAlexFDO

Authors Fadi Kacem, Dimitrios Letsios, Eric Angel, Evripidis Bampis

Publication date 14 November 2012

Published in Euro-Par 2012 Parallel Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.2105, http://hdl.handle.net/10044/1/64456

Mathematics Subject Classification ID

Flows in graphs (05C21) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Programming involving graphs or networks (90C35)

Abstract: We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works), on parallel speed-scaled processors so as to minimize the total energy consumption. We consider that both preemption and migration of jobs are allowed. An exact polynomial-time algorithm has been proposed for this problem, which is based on the Ellipsoid algorithm. Here, we formulate the problem as a convex program and we propose a simpler polynomial-time combinatorial algorithm which is based on a reduction to the maximum flow problem. Our algorithm runs in $O(nf(n)logP)$ time, where $n$ is the number of jobs, $P$ is the range of all possible values of processors' speeds 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, Albers et al. cite{AAG11} proposed an $O(n^{2}f(n))$-time algorithm exploiting the same relation with the maximum flow problem. We extend our algorithm to the multiprocessor speed scaling problem with migration where the objective is the minimization of the makespan under a budget of energy.

Recommendations

• Speed scaling on parallel processors with migration
• On multi-processor speed scaling with migration
• Speed scaling on parallel processors
• Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion
• Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems

Cited in

(27)

• Energy-efficient scheduling and routing via randomized rounding
• Energy-efficient bi-objective single-machine scheduling with power-down mechanism
• Scheduling on power-heterogeneous processors
• Race to idle or not: balancing the memory sleep time with DVS for energy minimization
• Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion
• A fast algorithm for multiprocessor speed-scaling problem minimizing completion time and energy consumption
• Models and algorithms for energy-efficient scheduling with immediate start of jobs
• Online dispatching and parallel processing algorithms for saving money in systems with heterogeneous, single-buffered, speed-scalable processors
• Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
• Green scheduling, flows and matchings
• On multi-processor speed scaling with migration
• Speed scaling on parallel processors with migration
• The bell is ringing in speed-scaled multiprocessor scheduling
• Speed scaling for maximum lateness
• Approximate schedules for non-migratory parallel jobs in speed-scaled multiprocessor systems
• Throughput maximization in multiprocessor speed-scaling
• Scheduling on power-heterogeneous processors
• A survey of offline algorithms for energy minimization under deadline constraints
• Speed scaling for maximum lateness
• Throughput Maximization in Multiprocessor Speed-Scaling
• On speed scaling scheduling of parallel jobs with preemption
• Energy-efficient algorithms for non-preemptive speed-scaling
• Speed scaling on parallel processors
• From preemptive to non-preemptive speed-scaling scheduling
• Green scheduling, flows and matchings
• From preemptive to non-preemptive speed-scaling scheduling
• Machine speed scaling by adapting methods for convex optimization with submodular constraints

This page was built for publication: Speed scaling on parallel processors with migration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4649807)