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

 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 Attachment(s): TOCS897.ps (852.27 KB)

 Journal

 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: (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},