---
_id: '368'
abstract:
- lang: eng
text: We consider the problem of scheduling a number of jobs on $m$ identical processors
sharing a continuously divisible resource. Each job j comes with a resource requirement
r_j \in {0,1}. The job can be processed at full speed if granted its full resource
requirement. If receiving only an x-portion of r_j, it is processed at an x-fraction
of the full speed. Our goal is to find a resource assignment that minimizes the
makespan (i.e., the latest completion time). Variants of such problems, relating
the resource assignment of jobs to their \emph{processing speeds}, have been studied
under the term discrete-continuous scheduling. Known results are either very pessimistic
or heuristic in nature.In this paper, we suggest and analyze a slightly simplified
model. It focuses on the assignment of shared continuous resources to the processors.
The job assignment to processors and the ordering of the jobs have already been
fixed. It is shown that, even for unit size jobs, finding an optimal solution
is NP-hard if the number of processors is part of the input. Positive results
for unit size jobs include an efficient optimal algorithm for 2 processors. Moreover,
we prove that balanced schedules yield a 2-1/m-approximation for a fixed number
of processors. Such schedules are computed by our GreedyBalance algorithm, for
which the bound is tight.
author:
- first_name: Andre
full_name: Brinkmann, Andre
last_name: Brinkmann
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Lars
full_name: Nagel, Lars
last_name: Nagel
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
- first_name: 'Tim '
full_name: 'Suess, Tim '
last_name: Suess
citation:
ama: 'Brinkmann A, Kling P, Meyer auf der Heide F, Nagel L, Riechers S, Suess T.
Scheduling Shared Continuous Resources on Many-Cores. In: Proceedings of the
26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA).
; 2014:128-137. doi:10.1145/2612669.2612698'
apa: Brinkmann, A., Kling, P., Meyer auf der Heide, F., Nagel, L., Riechers, S.,
& Suess, T. (2014). Scheduling Shared Continuous Resources on Many-Cores.
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA), 128–137. https://doi.org/10.1145/2612669.2612698
bibtex: '@inproceedings{Brinkmann_Kling_Meyer auf der Heide_Nagel_Riechers_Suess_2014,
title={Scheduling Shared Continuous Resources on Many-Cores}, DOI={10.1145/2612669.2612698},
booktitle={Proceedings of the 26th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)}, author={Brinkmann, Andre and Kling, Peter and Meyer
auf der Heide, Friedhelm and Nagel, Lars and Riechers, Sören and Suess, Tim },
year={2014}, pages={128–137} }'
chicago: Brinkmann, Andre, Peter Kling, Friedhelm Meyer auf der Heide, Lars Nagel,
Sören Riechers, and Tim Suess. “Scheduling Shared Continuous Resources on Many-Cores.”
In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA), 128–37, 2014. https://doi.org/10.1145/2612669.2612698.
ieee: 'A. Brinkmann, P. Kling, F. Meyer auf der Heide, L. Nagel, S. Riechers, and
T. Suess, “Scheduling Shared Continuous Resources on Many-Cores,” in Proceedings
of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
2014, pp. 128–137, doi: 10.1145/2612669.2612698.'
mla: Brinkmann, Andre, et al. “Scheduling Shared Continuous Resources on Many-Cores.”
Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures
(SPAA), 2014, pp. 128–37, doi:10.1145/2612669.2612698.
short: 'A. Brinkmann, P. Kling, F. Meyer auf der Heide, L. Nagel, S. Riechers, T.
Suess, in: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), 2014, pp. 128–137.'
date_created: 2017-10-17T12:42:03Z
date_updated: 2022-01-06T06:59:30Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2612669.2612698
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-20T07:17:38Z
date_updated: 2018-03-20T07:17:38Z
file_id: '1403'
file_name: 368-BKMNRS14.pdf
file_size: 485767
relation: main_file
success: 1
file_date_updated: 2018-03-20T07:17:38Z
has_accepted_license: '1'
language:
- iso: eng
page: 128-137
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '14'
name: SFB 901 - Subproject C2
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
status: public
title: Scheduling Shared Continuous Resources on Many-Cores
type: conference
user_id: '15415'
year: '2014'
...
---
_id: '451'
abstract:
- lang: eng
text: We introduce the concept of budget games. Players choose a set of tasks and
each task has a certain demand on every resource in the game. Each resource has
a budget. If the budget is not enough to satisfy the sum of all demands, it has
to be shared between the tasks. We study strategic budget games, where the budget
is shared proportionally. We also consider a variant in which the order of the
strategic decisions influences the distribution of the budgets. The complexity
of the optimal solution as well as existence, complexity and quality of equilibria
are analysed. Finally, we show that the time an ordered budget game needs to convergence
towards an equilibrium may be exponential.
author:
- first_name: Maximilian
full_name: Drees, Maximilian
last_name: Drees
- first_name: Sören
full_name: Riechers, Sören
last_name: Riechers
- first_name: Alexander
full_name: Skopalik, Alexander
id: '40384'
last_name: Skopalik
citation:
ama: 'Drees M, Riechers S, Skopalik A. Budget-restricted utility games with ordered
strategic decisions. In: Lavi R, ed. Proceedings of the 7th International Symposium
on Algorithmic Game Theory (SAGT). Lecture Notes in Computer Science. ; 2014:110-121.
doi:10.1007/978-3-662-44803-8_10'
apa: Drees, M., Riechers, S., & Skopalik, A. (2014). Budget-restricted utility
games with ordered strategic decisions. In R. Lavi (Ed.), Proceedings of the
7th International Symposium on Algorithmic Game Theory (SAGT) (pp. 110–121).
https://doi.org/10.1007/978-3-662-44803-8_10
bibtex: '@inproceedings{Drees_Riechers_Skopalik_2014, series={Lecture Notes in Computer
Science}, title={Budget-restricted utility games with ordered strategic decisions},
DOI={10.1007/978-3-662-44803-8_10},
booktitle={Proceedings of the 7th International Symposium on Algorithmic Game
Theory (SAGT)}, author={Drees, Maximilian and Riechers, Sören and Skopalik, Alexander},
editor={Lavi, RonEditor}, year={2014}, pages={110–121}, collection={Lecture Notes
in Computer Science} }'
chicago: Drees, Maximilian, Sören Riechers, and Alexander Skopalik. “Budget-Restricted
Utility Games with Ordered Strategic Decisions.” In Proceedings of the 7th
International Symposium on Algorithmic Game Theory (SAGT), edited by Ron Lavi,
110–21. Lecture Notes in Computer Science, 2014. https://doi.org/10.1007/978-3-662-44803-8_10.
ieee: M. Drees, S. Riechers, and A. Skopalik, “Budget-restricted utility games with
ordered strategic decisions,” in Proceedings of the 7th International Symposium
on Algorithmic Game Theory (SAGT), 2014, pp. 110–121.
mla: Drees, Maximilian, et al. “Budget-Restricted Utility Games with Ordered Strategic
Decisions.” Proceedings of the 7th International Symposium on Algorithmic Game
Theory (SAGT), edited by Ron Lavi, 2014, pp. 110–21, doi:10.1007/978-3-662-44803-8_10.
short: 'M. Drees, S. Riechers, A. Skopalik, in: R. Lavi (Ed.), Proceedings of the
7th International Symposium on Algorithmic Game Theory (SAGT), 2014, pp. 110–121.'
date_created: 2017-10-17T12:42:20Z
date_updated: 2022-01-06T07:01:07Z
ddc:
- '040'
department:
- _id: '63'
- _id: '541'
doi: 10.1007/978-3-662-44803-8_10
editor:
- first_name: Ron
full_name: Lavi, Ron
last_name: Lavi
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-16T11:25:10Z
date_updated: 2018-03-16T11:25:10Z
file_id: '1344'
file_name: 451-DRS14.pdf
file_size: 283266
relation: main_file
success: 1
file_date_updated: 2018-03-16T11:25:10Z
has_accepted_license: '1'
language:
- iso: eng
page: 110-121
project:
- _id: '1'
name: SFB 901
- _id: '14'
name: SFB 901 - Subproject C2
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '7'
name: SFB 901 - Subproject A3
- _id: '2'
name: SFB 901 - Project Area A
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 7th International Symposium on Algorithmic Game Theory
(SAGT)
series_title: Lecture Notes in Computer Science
status: public
title: Budget-restricted utility games with ordered strategic decisions
type: conference
user_id: '477'
year: '2014'
...
---
_id: '435'
abstract:
- lang: eng
text: We give a polynomial time algorithm to compute an optimal energy and fractional
weighted flow trade-off schedule for a speed-scalable processor with discrete
speeds.Our algorithm uses a geometric approach that is based on structural properties
obtained from a primal-dual formulation of the problem.
author:
- first_name: Antonios
full_name: Antoniadis, Antonios
last_name: Antoniadis
- first_name: Neal
full_name: Barcelo, Neal
last_name: Barcelo
- first_name: Mario
full_name: Consuegra, Mario
last_name: Consuegra
- first_name: Peer
full_name: Kling, Peer
last_name: Kling
- first_name: Michael
full_name: Nugent, Michael
last_name: Nugent
- first_name: Kirk
full_name: Pruhs, Kirk
last_name: Pruhs
- first_name: Michele
full_name: Scquizzato, Michele
last_name: Scquizzato
citation:
ama: 'Antoniadis A, Barcelo N, Consuegra M, et al. Efficient Computation of Optimal
Energy and Fractional Weighted Flow Trade-off Schedules. In: Proceedings of
the 31st Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs.
; 2014:63--74. doi:10.4230/LIPIcs.STACS.2014.63'
apa: Antoniadis, A., Barcelo, N., Consuegra, M., Kling, P., Nugent, M., Pruhs, K.,
& Scquizzato, M. (2014). Efficient Computation of Optimal Energy and Fractional
Weighted Flow Trade-off Schedules. In Proceedings of the 31st Symposium on
Theoretical Aspects of Computer Science (STACS) (pp. 63--74). https://doi.org/10.4230/LIPIcs.STACS.2014.63
bibtex: '@inproceedings{Antoniadis_Barcelo_Consuegra_Kling_Nugent_Pruhs_Scquizzato_2014,
series={LIPIcs}, title={Efficient Computation of Optimal Energy and Fractional
Weighted Flow Trade-off Schedules}, DOI={10.4230/LIPIcs.STACS.2014.63},
booktitle={Proceedings of the 31st Symposium on Theoretical Aspects of Computer
Science (STACS)}, author={Antoniadis, Antonios and Barcelo, Neal and Consuegra,
Mario and Kling, Peer and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele},
year={2014}, pages={63--74}, collection={LIPIcs} }'
chicago: Antoniadis, Antonios, Neal Barcelo, Mario Consuegra, Peer Kling, Michael
Nugent, Kirk Pruhs, and Michele Scquizzato. “Efficient Computation of Optimal
Energy and Fractional Weighted Flow Trade-off Schedules.” In Proceedings of
the 31st Symposium on Theoretical Aspects of Computer Science (STACS), 63--74.
LIPIcs, 2014. https://doi.org/10.4230/LIPIcs.STACS.2014.63.
ieee: A. Antoniadis et al., “Efficient Computation of Optimal Energy and
Fractional Weighted Flow Trade-off Schedules,” in Proceedings of the 31st Symposium
on Theoretical Aspects of Computer Science (STACS), 2014, pp. 63--74.
mla: Antoniadis, Antonios, et al. “Efficient Computation of Optimal Energy and Fractional
Weighted Flow Trade-off Schedules.” Proceedings of the 31st Symposium on Theoretical
Aspects of Computer Science (STACS), 2014, pp. 63--74, doi:10.4230/LIPIcs.STACS.2014.63.
short: 'A. Antoniadis, N. Barcelo, M. Consuegra, P. Kling, M. Nugent, K. Pruhs,
M. Scquizzato, in: Proceedings of the 31st Symposium on Theoretical Aspects of
Computer Science (STACS), 2014, pp. 63--74.'
date_created: 2017-10-17T12:42:16Z
date_updated: 2022-01-06T07:00:58Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.4230/LIPIcs.STACS.2014.63
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-16T11:30:23Z
date_updated: 2018-03-16T11:30:23Z
file_id: '1354'
file_name: 435-Kling_C2_STACS2014.pdf
file_size: 525851
relation: main_file
success: 1
file_date_updated: 2018-03-16T11:30:23Z
has_accepted_license: '1'
language:
- iso: eng
page: 63--74
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '14'
name: SFB 901 - Subproject C2
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 31st Symposium on Theoretical Aspects of Computer
Science (STACS)
series_title: LIPIcs
status: public
title: Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off
Schedules
type: conference
user_id: '477'
year: '2014'
...
---
_id: '499'
abstract:
- lang: eng
text: We present a new online algorithm for profit-oriented scheduling on multiple
speed-scalable processors.Moreover, we provide a tight analysis of the algorithm's
competitiveness.Our results generalize and improve upon work by \citet{Chan:2010},
which considers a single speed-scalable processor.Using significantly different
techniques, we can not only extend their model to multiprocessors but also prove
an enhanced and tight competitive ratio for our algorithm.In our scheduling problem,
jobs arrive over time and are preemptable.They have different workloads, values,
and deadlines.The scheduler may decide not to finish a job but instead to suffer
a loss equaling the job's value.However, to process a job's workload until its
deadline the scheduler must invest a certain amount of energy.The cost of a schedule
is the sum of lost values and invested energy.In order to finish a job the scheduler
has to determine which processors to use and set their speeds accordingly.A processor's
energy consumption is power $\Power{s}$ integrated over time, where $\Power{s}=s^{\alpha}$
is the power consumption when running at speed $s$.Since we consider the online
variant of the problem, the scheduler has no knowledge about future jobs.This
problem was introduced by~\citet{Chan:2010} for the case of a single processor.They
presented an online algorithm which is $\alpha^{\alpha}+2e\alpha$-competitive.We
provide an online algorithm for the case of multiple processors with an improved
competitive ratio of $\alpha^{\alpha}$.
author:
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Peter
full_name: Pietrzyk, Peter
last_name: Pietrzyk
citation:
ama: 'Kling P, Pietrzyk P. Profitable Scheduling on Multiple Speed-Scalable Processors.
In: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA). ; 2013:251-260. doi:10.1145/2486159.2486183'
apa: Kling, P., & Pietrzyk, P. (2013). Profitable Scheduling on Multiple Speed-Scalable
Processors. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA) (pp. 251–260). https://doi.org/10.1145/2486159.2486183
bibtex: '@inproceedings{Kling_Pietrzyk_2013, title={Profitable Scheduling on Multiple
Speed-Scalable Processors}, DOI={10.1145/2486159.2486183},
booktitle={Proceedings of the 25th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA)}, author={Kling, Peter and Pietrzyk, Peter}, year={2013},
pages={251–260} }'
chicago: Kling, Peter, and Peter Pietrzyk. “Profitable Scheduling on Multiple Speed-Scalable
Processors.” In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), 251–60, 2013. https://doi.org/10.1145/2486159.2486183.
ieee: P. Kling and P. Pietrzyk, “Profitable Scheduling on Multiple Speed-Scalable
Processors,” in Proceedings of the 25th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), 2013, pp. 251–260.
mla: Kling, Peter, and Peter Pietrzyk. “Profitable Scheduling on Multiple Speed-Scalable
Processors.” Proceedings of the 25th ACM Symposium on Parallelism in Algorithms
and Architectures (SPAA), 2013, pp. 251–60, doi:10.1145/2486159.2486183.
short: 'P. Kling, P. Pietrzyk, in: Proceedings of the 25th ACM Symposium on Parallelism
in Algorithms and Architectures (SPAA), 2013, pp. 251–260.'
date_created: 2017-10-17T12:42:29Z
date_updated: 2022-01-06T07:01:34Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1145/2486159.2486183
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T13:40:02Z
date_updated: 2018-03-15T13:40:02Z
file_id: '1310'
file_name: 499-P._Kling__P._Pietryzk_-_Profitable_Scheduling_on_Multiple_Speed-scalable_Processors__2013_.pdf
file_size: 558661
relation: main_file
success: 1
file_date_updated: 2018-03-15T13:40:02Z
has_accepted_license: '1'
language:
- iso: eng
page: '251-260 '
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '14'
name: SFB 901 - Subproject C2
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA)
status: public
title: Profitable Scheduling on Multiple Speed-Scalable Processors
type: conference
user_id: '477'
year: '2013'
...
---
_id: '580'
abstract:
- lang: eng
text: We present and study a new model for energy-aware and profit-oriented scheduling
on a single processor.The processor features dynamic speed scaling as well as
suspension to a sleep mode.Jobs arrive over time, are preemptable, and have different
sizes, values, and deadlines.On the arrival of a new job, the scheduler may either
accept or reject the job.Accepted jobs need a certain energy investment to be
finished in time, while rejected jobs cause costs equal to their values.Here,
power consumption at speed $s$ is given by $P(s)=s^{\alpha}+\beta$ and the energy
investment is power integrated over time.Additionally, the scheduler may decide
to suspend the processor to a sleep mode in which no energy is consumed, though
awaking entails fixed transition costs $\gamma$.The objective is to minimize the
total value of rejected jobs plus the total energy.Our model combines aspects
from advanced energy conservation techniques (namely speed scaling and sleep states)
and profit-oriented scheduling models.We show that \emph{rejection-oblivious}
schedulers (whose rejection decisions are not based on former decisions) have
– in contrast to the model without sleep states – an unbounded competitive ratio.It
turns out that the jobs' value densities (the ratio between a job's value and
its work) are crucial for the performance of such schedulers.We give an algorithm
whose competitiveness nearly matches the lower bound w.r.t\text{.} the maximum
value density.If the maximum value density is not too large, the competitiveness
becomes $\alpha^{\alpha}+2e\alpha$.Also, we show that it suffices to restrict
the value density of low-value jobs only.Using a technique from \cite{Chan:2010}
we transfer our results to processors with a fixed maximum speed.
author:
- first_name: Andreas
full_name: Cord-Landwehr, Andreas
last_name: Cord-Landwehr
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Fredrik
full_name: Mallmann Trenn, Fredrik
last_name: Mallmann Trenn
citation:
ama: 'Cord-Landwehr A, Kling P, Mallmann Trenn F. Slow Down & Sleep for Profit
in Online Deadline Scheduling. In: Even G, Rawitz D, eds. Proceedings of the
1st Mediterranean Conference on Algorithms (MedAlg). LNCS. ; 2012:218-231.
doi:10.1007/978-3-642-34862-4_17'
apa: Cord-Landwehr, A., Kling, P., & Mallmann Trenn, F. (2012). Slow Down &
Sleep for Profit in Online Deadline Scheduling. In G. Even & D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
(pp. 218–231). https://doi.org/10.1007/978-3-642-34862-4_17
bibtex: '@inproceedings{Cord-Landwehr_Kling_Mallmann Trenn_2012, series={LNCS},
title={Slow Down & Sleep for Profit in Online Deadline Scheduling}, DOI={10.1007/978-3-642-34862-4_17},
booktitle={Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)},
author={Cord-Landwehr, Andreas and Kling, Peter and Mallmann Trenn, Fredrik},
editor={Even, Guy and Rawitz, DrorEditors}, year={2012}, pages={218–231}, collection={LNCS}
}'
chicago: Cord-Landwehr, Andreas, Peter Kling, and Fredrik Mallmann Trenn. “Slow
Down & Sleep for Profit in Online Deadline Scheduling.” In Proceedings
of the 1st Mediterranean Conference on Algorithms (MedAlg), edited by Guy
Even and Dror Rawitz, 218–31. LNCS, 2012. https://doi.org/10.1007/978-3-642-34862-4_17.
ieee: A. Cord-Landwehr, P. Kling, and F. Mallmann Trenn, “Slow Down & Sleep
for Profit in Online Deadline Scheduling,” in Proceedings of the 1st Mediterranean
Conference on Algorithms (MedAlg), 2012, pp. 218–231.
mla: Cord-Landwehr, Andreas, et al. “Slow Down & Sleep for Profit in Online
Deadline Scheduling.” Proceedings of the 1st Mediterranean Conference on Algorithms
(MedAlg), edited by Guy Even and Dror Rawitz, 2012, pp. 218–31, doi:10.1007/978-3-642-34862-4_17.
short: 'A. Cord-Landwehr, P. Kling, F. Mallmann Trenn, in: G. Even, D. Rawitz (Eds.),
Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg), 2012,
pp. 218–231.'
date_created: 2017-10-17T12:42:45Z
date_updated: 2022-01-06T07:02:42Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-34862-4_17
editor:
- first_name: Guy
full_name: Even, Guy
last_name: Even
- first_name: Dror
full_name: Rawitz, Dror
last_name: Rawitz
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-15T09:03:39Z
date_updated: 2018-03-15T09:03:39Z
file_id: '1265'
file_name: 580-P._Kling__F._Mallmann-Trenn__A._Cord-Landwehr_-_Slow_Down___Sleep_for_Profit_in_Online_Deadline_Scheduling.pdf
file_size: 325939
relation: main_file
success: 1
file_date_updated: 2018-03-15T09:03:39Z
has_accepted_license: '1'
language:
- iso: eng
page: 218-231
project:
- _id: '1'
name: SFB 901
- _id: '14'
name: SFB 901 - Subprojekt C2
- _id: '16'
name: SFB 901 - Subproject C4
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg)
series_title: LNCS
status: public
title: Slow Down & Sleep for Profit in Online Deadline Scheduling
type: conference
user_id: '477'
year: '2012'
...
---
_id: '664'
abstract:
- lang: eng
text: 'Web Computing is a variant of parallel computing where the idle times of
PCs donated by worldwide distributed users are employed to execute parallel programs.
The PUB-Web library developed by us supports this kind of usage of computing resources.
A major problem for the efficient execution of such parallel programs is load
balancing. In the Web Computing context, this problem becomes more difficult because
of the dynamic behavior of the underlying "parallel computer": the set of available
processors (donated PCs) as well as their availability (idle times) change over
time in an unpredictable fashion.In this paper, we experimentally evaluate and
compare load balancing algorithms in this scenario, namely a variant of the well-established
Work Stealing algorithm and strategies based on a heterogeneous version of distributed
hash-tables (DHHTs) introduced recently. In order to run a meaningful experimental
evaluation, we employ, in addition to our Web Computing library PUB-Web, realistic
data sets for the job input streams and for the dynamics of the availability of
the resources.Our experimental evaluations suggest that Work Stealing is the better
strategy if the number of processes ready to run matches the number of available
processors. But a suitable variant of DHHTs outperforms Work Stealing if there
are significantly more processes ready to run than available processors.'
author:
- first_name: Joachim
full_name: Gehweiler, Joachim
last_name: Gehweiler
- first_name: Peter
full_name: Kling, Peter
last_name: Kling
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Gehweiler J, Kling P, Meyer auf der Heide F. An Experimental Comparison of
Load Balancing Strategies in a Web Computing Environment. In: Proceedings of
the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM). LNCS. ; 2011:31--40. doi:10.1007/978-3-642-31500-8_4'
apa: Gehweiler, J., Kling, P., & Meyer auf der Heide, F. (2011). An Experimental
Comparison of Load Balancing Strategies in a Web Computing Environment. In Proceedings
of the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM) (pp. 31--40). https://doi.org/10.1007/978-3-642-31500-8_4
bibtex: '@inproceedings{Gehweiler_Kling_Meyer auf der Heide_2011, series={LNCS},
title={An Experimental Comparison of Load Balancing Strategies in a Web Computing
Environment}, DOI={10.1007/978-3-642-31500-8_4},
booktitle={Proceedings of the 9th International Conference on Parallel Processing
and Applied Mathematics (PPAM)}, author={Gehweiler, Joachim and Kling, Peter and
Meyer auf der Heide, Friedhelm}, year={2011}, pages={31--40}, collection={LNCS}
}'
chicago: Gehweiler, Joachim, Peter Kling, and Friedhelm Meyer auf der Heide. “An
Experimental Comparison of Load Balancing Strategies in a Web Computing Environment.”
In Proceedings of the 9th International Conference on Parallel Processing and
Applied Mathematics (PPAM), 31--40. LNCS, 2011. https://doi.org/10.1007/978-3-642-31500-8_4.
ieee: J. Gehweiler, P. Kling, and F. Meyer auf der Heide, “An Experimental Comparison
of Load Balancing Strategies in a Web Computing Environment,” in Proceedings
of the 9th International Conference on Parallel Processing and Applied Mathematics
(PPAM), 2011, pp. 31--40.
mla: Gehweiler, Joachim, et al. “An Experimental Comparison of Load Balancing Strategies
in a Web Computing Environment.” Proceedings of the 9th International Conference
on Parallel Processing and Applied Mathematics (PPAM), 2011, pp. 31--40, doi:10.1007/978-3-642-31500-8_4.
short: 'J. Gehweiler, P. Kling, F. Meyer auf der Heide, in: Proceedings of the 9th
International Conference on Parallel Processing and Applied Mathematics (PPAM),
2011, pp. 31--40.'
date_created: 2017-10-17T12:43:01Z
date_updated: 2022-01-06T07:03:14Z
ddc:
- '040'
department:
- _id: '63'
doi: 10.1007/978-3-642-31500-8_4
file:
- access_level: closed
content_type: application/pdf
creator: florida
date_created: 2018-03-14T13:45:57Z
date_updated: 2018-03-14T13:45:57Z
file_id: '1216'
file_name: 664-PPAM11GKM_01.pdf
file_size: 333335
relation: main_file
success: 1
file_date_updated: 2018-03-14T13:45:57Z
has_accepted_license: '1'
page: 31--40
project:
- _id: '1'
name: SFB 901
- _id: '16'
name: SFB 901 - Subprojekt C4
- _id: '14'
name: SFB 901 - Subproject C2
- _id: '4'
name: SFB 901 - Project Area C
publication: Proceedings of the 9th International Conference on Parallel Processing
and Applied Mathematics (PPAM)
series_title: LNCS
status: public
title: An Experimental Comparison of Load Balancing Strategies in a Web Computing
Environment
type: conference
user_id: '15504'
year: '2011'
...