## 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 language | English (US) |
---|---|

Title of host publication | SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures |

Publisher | Association for Computing Machinery |

Pages | 195-205 |

Number of pages | 11 |

ISBN (Electronic) | 9781450342100 |

DOIs | |

State | Published - Jul 11 2016 |

Externally published | Yes |

Event | 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016 - Pacific Grove, United States Duration: Jul 11 2016 → Jul 13 2016 |

### Publication series

Name | Annual ACM Symposium on Parallelism in Algorithms and Architectures |
---|---|

Volume | 11-13-July-2016 |

### Other

Other | 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016 |
---|---|

Country | United States |

City | Pacific Grove |

Period | 7/11/16 → 7/13/16 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Hardware and Architecture