Scheduling parallelizable jobs online to minimize the maximum flow time

Kunal Agrawal, Jing Li, Kefu Lu, Benjamin Moseley

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

In this paper we study the problem of scheduling a set of dynamic multithreaded jobs with the objective of minimizing the maximum latency experienced by any job. We assume that jobs arrive online and the scheduler has no information about the arrival rate, arrival time or work distribution of the jobs. The scheduling goal is to minimize the maximum amount of time between the arrival of a job and its completion - this goal is referred to in scheduling literature as maximum flow time. While theoretical online scheduling of parallel jobs has been studied extensively, most prior work has focussed on a highly stylized model of parallel jobs called the "speedup curves model." We model parallel jobs as directed acyclic graphs, which is a more realistic way to model dynamic multithreaded jobs. In this context, we prove that a simple First-In-First-Out scheduler is (1 + ϵ)-speed O(1/ϵ-)-competitive for any e > 0. We then develop a more practical work-stealing scheduler and show that it has a maximum flow time of O(1/2ϵ max{OPT, ln(n)}) for n jobs, with (1 + ϵ)-speed. This result is essentially tight as we also provide a lower bound of Ω(log(n)) for work stealing. In addition, for the case where jobs have weights (typically representing priorities) and the objective is minimizing the maximum weighted flow time, we show a non-clairvoyant algorithm is (1 + ϵ)-speed O(1/2ϵ)-competitive for any ϵ > 0, which is essentially the best positive result that can be shown in the online setting for the weighted case due to strong lower bounds without resource augmentation. After establishing theoretical results, we perform an empirical study of work-stealing. Our results indicate that, on both real world and synthetic workloads, work-stealing performs almost as well as an optimal scheduler.

Original languageEnglish (US)
Title of host publicationSPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages195-205
Number of pages11
ISBN (Electronic)9781450342100
DOIs
StatePublished - Jul 11 2016
Externally publishedYes
Event28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016 - Pacific Grove, United States
Duration: Jul 11 2016Jul 13 2016

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures
Volume11-13-July-2016

Other

Other28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016
Country/TerritoryUnited States
CityPacific Grove
Period7/11/167/13/16

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Scheduling parallelizable jobs online to minimize the maximum flow time'. Together they form a unique fingerprint.

Cite this