Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2014) | last year (2013) | two years ago (2012) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Bast, Hannah

dblp



BibTeX cite key*:

Bast2000b

Title

Title*:

On Scheduling Parallel Tasks at Twilight

Journal

Journal Title*:

Theory of Computing Systems

Journal's URL:

http://link.springer-ny.com/link/service/journals/00224/

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Springer

Publisher's URL:

http://www.springer-ny.com/

Publisher's
Address:

New York, USA

ISSN:

1432-4350

Vol, No, pp, Date

Volume*:

33

Number:

5

Publishing Date:

November 2000

Pages*:

489-563

Number of
VG Pages:

160

Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

We consider the problem of processing a given number of tasks on a given number of processors as quickly as possible when only vague information
about the processing time of a task is available before it is completed. Whenever a processor is idle, it can be assigned, at the price of a certain overhead, a
portion, called a chunk, of the unassigned tasks. The goal is to minimize the makespan, that is, the time that passes until all the tasks are completed. The
difficulty then is to find the optimal tradeoff between the processors' load balance, which is favoured by having small, and therefore many, chunks, and
the total scheduling overhead, which is lower when there are fewer chunks. This scheduling problem has been the subject of intensive research in the
past, and a large variety of heuristics have been proposed. Its mathematical analysis, however, turned out to be difficult even for simplistic models of the
vague-information issue, and little theoretical work has been presented to date. In this work we present a novel theoretical model that covers a
multitude of natural vague-information scenarios, and for which we can prove general upper and lower bounds on the achievable makespan. From
this we derive optimal bounds and algorithms for a whole variety of specific scenarios, including the modelling of task processing times as independent,
identically distributed random variables, which guided the design of most of the previously existing heuristics. Unlike traditional approaches, our model
neither ignores a priori knowledge of the input (the processing times) nor does it restrict the distribution of the input, but instead works with the concepts
of an a priori estimate of the processing times, which is implicit in every algorithm, and a measure for the deviation of this estimate from the actual
processing times, which is not known until all the tasks are completed.

URL for the Abstract:


Categories,
Keywords:

Parallel, Irregular, Scheduling, Uncertainty, Load Balancing, Loops

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


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:

@ARTICLE{Bast2000b,
AUTHOR = {Bast, Hannah},
TITLE = {On Scheduling Parallel Tasks at Twilight},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {5},
VOLUME = {33},
PAGES = {489--563},
ADDRESS = {New York, USA},
MONTH = {November},
ISBN = {1432-4350},
}


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)