Throughput Maximization in Multiprocessor Speed-Scaling

From MaRDI portal
Publication:2942633

DOI10.1007/978-3-319-13075-0_20zbMATH Open1433.68063arXiv1402.3782OpenAlexW2356268455MaRDI QIDQ2942633FDOQ2942633


Authors: Vincent Chau, Nguyen Kim Thang, Eric Angel, Evripidis Bampis Edit this on Wikidata


Publication date: 11 September 2015

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

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 rj, its deadline dj, its processing volume pi,j if j is executed on machine i and its weight wj. 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. pi,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 rilerj if and only if diledj, for which we present a pseudopolynomial-time algorithm. Both algorithms are based on a discretization of the problem and the use of dynamic programming.


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




Recommendations



Cites Work


Cited In (12)





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)