direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Publications by Type: Journal and Magazine Articles

Optimal On-Line Scheduling of Parallel Jobs with Dependencies
Citation key FKST-OOSPJD-98
Author Feldmann, Anja and Kao, Ming-Yang and Sgall, Jiri and Teng, Shang-Hua
Pages 393–411
Year 1998
DOI http://dx.doi.org/10.1023/A:1009794729459
Journal Journal of Combinatorial Optimization
Volume 1
Number 4
Note An earlier version of this appeared as FKST-OOSPJD-93; an even earlier version appeared as FKST-OOSPJD-92.
Abstract 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.
Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe