Optimal On-Line Scheduling of Parallel Jobs with Dependencies

Anja Feldmann, Ming-Yang Kao, Jiří Sgall and Shang-Hua Teng ()
Additional contact information
Anja Feldmann: Carnegie Mellon University
Ming-Yang Kao: Duke University
Jiří Sgall: Mathematical Institute
Shang-Hua Teng: University of Minnesota

Journal of Combinatorial Optimization, 1998, vol. 1, issue 4, No 5, 393-411

Abstract: Abstract We study the following general on-line scheduling problem. Paralleljobs arrive on a parallel machine dynamically according to thedependencies between them. Each job requests a certain number ofprocessors in a specific communication configuration, but its runningtime is not known until it is completed. We present optimal on-linealgorithms for PRAMs and one-dimensional meshes, and efficientalgorithms for hypercubes and general meshes. For PRAMs we obtainoptimal tradeoffs between the competitive ratio and the largestnumber of processors requested by any job. Our results demonstrate that on-line scheduling with dependenciesdiffers from scheduling without dependencies in several crucialaspects. First, it is essential to use virtualization, i.e., toschedule parallel jobs on fewer processors than requested. Second,the maximal number of processors requested by a job has significantinfluence on the performance. Third, the geometric structure of thenetwork topology is an even more important factor than in the absenceof dependencies.

Keywords: Mathematical Modeling; Schedule Problem; Industrial Mathematic; Geometric Structure; Discrete Geometry (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009794729459 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:1:y:1998:i:4:d:10.1023_a:1009794729459

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009794729459

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().