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)

Dynamic scheduling on parallel machines
Zitatschlüssel FST-DSPM-91
Autor Feldmann, Anja and Sgall, Jiri and Teng, Shang-Hua
Buchtitel Proceedings of the 32nd annual symposium on Foundations of computer science
Seiten 111–120
Jahr 1991
ISBN 0-8186-2445-0
Ort San Juan, Puerto Rico
Adresse Los Alamitos, CA, USA
Verlag IEEE Computer Society Press
Zusammenfassung In this paper, we study the problem of on-line job-scheduling on various parallel architectures. In particular, we give an O(sqrt(loglog n))-competitive algorithm for on-line dynamic scheduling on an nxn mesh. We prove that this algorithm is optimal up to a constant factor–-no on-line algorithm can achieve a competitive ratio better than (1/42) sqrtloglog n. Our algorithm is not greedy and the lower bound proof shows that no greedy-like algorithm can be very good. Our upper bound result can be generalized to any fixed dimensional meshes. We also present competitive scheduling algorithms for other architectures including hypercubes, trees, meshes of trees, and PRAMs.
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe