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: Goto entry point

 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: 20 October 2019 Event End Date: 20 October 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:

 (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
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