TU Berlin

Internet Network ArchitecturesPublications by Type: Conference and Workshop Papers

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

Optimal online scheduling of parallel jobs with dependencies
Zitatschlüssel FKST-OOSPJD-93
Autor Feldmann, Anja and Kao, Ming-Yang and Sgall, Jiri and Teng, Shang-Hua
Buchtitel STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing
Seiten 642–651
Jahr 1993
ISBN 0-89791-591-7
DOI http://dx.doi.org/10.1145/167088.167254
Ort San Diego, California, United States
Adresse New York, NY, USA
Notiz Also appeared unauthorized as: A Dynamic Algorithm for Online Scheduling of Parallel Processes. C.V. Papadopoulos; PARLE'94, pages 600–610, 1994; an earlier version appeared as FKST-OOSPJD-92.
Verlag ACM Press
Zusammenfassung We study the following general online scheduling problem. Parallel jobs arrive on a parallel machine dynamically according to the dependencies between them. Each job requests a certain number of processors in a specific communication configuration, but its running time is not known until it is completed. We present optimal online algorithms for PRAMs, hypercubes, and one-dimensional meshes. For PRAMs we obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested by any job. Our results demonstrate that online scheduling with dependencies differs from scheduling without dependencies in several crucial aspects. First, it is essential to use virtualization, i.e., to schedule parallel jobs on fewer processors than requested. Second, the maximal number of processors requested by a job has significant influence on the performance. Third, the geometric structure of the network topology is an even more important factor than in the absence of dependencies.
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe