Throughput Maximization in Multiprocessor Speed-Scaling

DOI10.1007/978-3-319-13075-0_20MaRDI QIDQ2942633zbMATH OpenOpenAlexFDO

Authors Vincent Chau, Nguyen Kim Thang, Eric Angel, Evripidis Bampis

Publication date 11 September 2015

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.3782

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Abstract: We are given a set of $n$ jobs that have to be executed on a set of $m$ speed-scalable machines that can vary their speeds dynamically using the energy model introduced in [Yao et al., FOCS'95]. Every job $j$ is characterized by its release date $r_j$, its deadline $d_j$, its processing volume $p_{i,j}$ if $j$ is executed on machine $i$ and its weight $w_j$. We are also given a budget of energy $E$ and our objective is to maximize the weighted throughput, i.e. the total weight of jobs that are completed between their respective release dates and deadlines. We propose a polynomial-time approximation algorithm where the preemption of the jobs is allowed but not their migration. Our algorithm uses a primal-dual approach on a linearized version of a convex program with linear constraints. Furthermore, we present two optimal algorithms for the non-preemptive case where the number of machines is bounded by a fixed constant. More specifically, we consider: {em (a)} the case of identical processing volumes, i.e. $p_{i,j}=p$ for every $i$ and $j$, for which we present a polynomial-time algorithm for the unweighted version, which becomes a pseudopolynomial-time algorithm for the weighted throughput version, and {em (b)} the case of agreeable instances, i.e. for which $r_{i}le{r}_j$ if and only if $d_{i}le{d}_j$, for which we present a pseudopolynomial-time algorithm. Both algorithms are based on a discretization of the problem and the use of dynamic programming.

Recommendations

• Throughput maximization in multiprocessor speed-scaling
• scientific article; zbMATH DE number 1929944
• Throughput maximization in the speed-scaling setting
• On maximizing the throughput of multiprocessor tasks.
• Speed scaling of processes with arbitrary speedup curves on a multiprocessor
• Throughput maximization for speed scaling with agreeable deadlines
• Throughput maximization for speed-scaling with agreeable deadlines
• Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
• Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
• Speed scaling on parallel processors

Cites work

• scientific article; zbMATH DE number 6381709 (Why is no real title available?)
• scientific article; zbMATH DE number 1306870 (Why is no real title available?)
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs
• Approximation algorithms for variable voltage processors: min energy, max throughput and online heuristics
• Energy efficient scheduling and routing via randomized rounding
• Energy-efficient algorithms for non-preemptive speed-scaling
• From preemptive to non-preemptive speed-scaling scheduling
• Green scheduling, flows and matchings
• How to pack your items when you have to buy your knapsack
• New Results for Non-Preemptive Speed Scaling
• Non-preemptive speed scaling
• On multi-processor speed scaling with migration
• Online matching with concave returns
• Scheduling for Speed Bounded Processors
• Speed scaling on parallel processors
• Speed scaling on parallel processors with migration
• The bell is ringing in speed-scaled multiprocessor scheduling
• Throughput maximization for speed-scaling with agreeable deadlines
• Throughput maximization in the speed-scaling setting
• Tradeoff between energy and throughput for online deadline scheduling

Cited in

(12)

• Non-preemptive throughput maximization for speed-scaling with power-down
• Throughput maximization in multiprocessor speed-scaling
• Throughput maximization for speed scaling with agreeable deadlines
• The effect of multiprocessor radius on scaling
• On maximizing the throughput of multiprocessor tasks.
• Multiprocessor Capacity Metric and Analysis
• Optimizing the steady-state throughput of scatter and reduce operations on heterogeneous platforms
• Throughput maximization for speed-scaling with agreeable deadlines
• Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines
• Maximizing the Throughput of Multiple Machines On-Line
• On multi-processor speed scaling with migration
• Throughput maximization in the speed-scaling setting

This page was built for publication: Throughput Maximization in Multiprocessor Speed-Scaling

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