Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Bast, Hannah

dblp



Editor(s):





BibTeX cite key*:

Bast1998

Title, Booktitle

Title*:

Dynamic Scheduling with Incomplete Information

Booktitle*:

Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-98)

Event, URLs

URL of the conference:

http://www.uni-paderborn.de/cs/SPAA/1998/index.html

URL for downloading the paper:


Event Address*:

Puerto Vallarta, Mexico

Language:

English

Event Date*
(no longer used):

June 28 - July 2, 1998

Organization:

Association for Computing Machinery (ACM)

Event Start Date:

24 May 2019

Event End Date:

24 May 2019

Publisher

Name*:

ACM Press

URL:


Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

June

Pages:

182-191

Year*:

1998

VG Wort Pages:


ISBN/ISSN:

0-89791-989-0

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We consider the following scheduling problem:
Our goal is to execute a given amount of
arbitrarily decomposable work on a distributed machine
as quickly as possible.
The work is maintained by a central scheduler
that can assign chunks of work of an arbitrary size
to idle processors.
The difficulty is that the processing time required for
a chunk is not exactly predictable---usually the less, the
larger the chunk---and that processors suffer a
delay for each assignment.
Our objective is to minimize the total wasted time of the schedule,
that is, the sum of all delays plus the idle times of processors
waiting for the last processor to finish.

We introduce a new deterministic model for this setting,
based on estimated ranges $[\alpha(w),\beta(w)]$ for processing times
of chunks of size $w$.
Depending on $\alpha$, $\beta$, and a measure for the overall
deviation from these estimates, we can prove matching
upper and lower bounds on the wasted time, the former being
achieved by our new \emph{balancing} strategy.
This is in sharp contrast with previous work that,
even under the strong assumption of independent,
approximately normally distributed chunk processing times,
proposed only heuristic scheduling schemes supported
merely by empirical evidence.
Our model naturally subsumes this stochastic setting, and
our generic analysis is valid for
most of the existing schemes too, proving them to be non-optimal.

Keywords:

Scheduling, Load Balancing, Parallel Loop



Download
Access Level:


Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Bast1998,
AUTHOR = {Bast, Hannah},
TITLE = {Dynamic Scheduling with Incomplete Information},
BOOKTITLE = {Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA-98)},
PUBLISHER = {ACM Press},
YEAR = {1998},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {182--191},
ADDRESS = {Puerto Vallarta, Mexico},
MONTH = {June},
ISBN = {0-89791-989-0},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Hannah Bast
Created
01/21/1999 02:21:32 PM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Uwe Brahm
Hannah Bast
Hannah Bast
Edit Dates
01.04.99 09:34:10
29.03.99 18:26:41
29.03.99 18:26:41
29.03.99 18:26:41