Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

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

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Fatourou, Panagiota
Spirakis, Paul G.

dblp
dblp

Not MPG Author(s):

Spirakis, Paul G.

BibTeX cite key*:

Fatourou2000

Title

Title*:

Efficient Scheduling of Strict Multithreaded Computations


TOCS897.ps (852.27 KB)

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:

3

Publishing Date:

May 2000

Pages*:

173-232

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

In this paper we study the problem of
efficiently scheduling a wide class of multithreaded
computations, called {\em strict};
that is, computations in which all dependencies
from a thread go to the thread's
ancestors in the computation tree.
Strict multithreaded computations allow the
limited use of synchronization primitives.
We present the {\em first} fully distributed
scheduling algorithm which applies to {\em any}
strict multithreaded computation. The algorithm
is asynchronous, on-line and follows the
{\em work-stealing} paradigm. We prove that
our algorithm is efficient not only in terms of
its memory requirements and its execution time, but also in terms of its
communication complexity.
Our analysis applies to both shared and distributed memory
machines.

More specifically,
the expected execution time of our algorithm
is $O(T_1/P + hT_{\infty})$, where
$T_1$ is the minimum serial execution
time, $T_{\infty}$ is the minimum execution
time with an infinite number of processors,
$P$ is the number of processors
and $h$ is the maximum ``distance'' in the
{\em computation tree} between
any two threads that need to communicate.
Furthermore, the total space required during the execution
is $O(S_1 P)$, where $S_1$ is the space required
by a serial computer to execute the
computation, while the expected communication cost
incurred by our algorithm is $O(PhT_{\infty} (1+n_d) S_{max})$,
where $n_d$ is the maximum number of dependencies
entering any thread and $S_{max}$ is the largest
amount of storage needed for the execution of
any specific thread of the computation.
Our communication complexity bound is {\em the first}
nontrivial bound ever proved for the
model of strict parallel programming.

URL for the Abstract:


Categories,
Keywords:

multithreaded computations, scheduling algorithms, work-stealing

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

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


BibTeX Entry:

@ARTICLE{Fatourou2000,
AUTHOR = {Fatourou, Panagiota and Spirakis, Paul G.},
TITLE = {Efficient Scheduling of Strict Multithreaded Computations},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2000},
NUMBER = {3},
VOLUME = {33},
PAGES = {173--232},
ADDRESS = {New York, USA},
MONTH = {May},
ISBN = {1432-4350},
}


Entry last modified by Christine Kiesel, 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)
Panagiota Fatourou
Created
02/02/2001 09:57:01 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Edit Dates
26.08.2003 15:05:50
05/02/2001 12:15:26 PM
20.03.2001 17:19:25
20.03.2001 17:13:56
02/02/2001 21:57:03
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
TOCS897.ps