Minimizing Migrations in Fair Multiprocessor Scheduling of Persistent Tasks

Tracy Kimbrel, Baruch Schieber, Maxim Sviridenko

Research output: Contribution to conferencePaperpeer-review

10 Scopus citations

Abstract

Suppose that we are given n persistent tasks (jobs) that need to be executed in an equitable way on m processors (machines). Each machine is capable of performing one unit of work in each integral time unit and each job may be executed on at most one machine at a time. The schedule needs to specify which job is to be executed on each machine in each time window. The goal is to find a schedule that minimizes job migrations between machines while guaranteeing a fair schedule. We measure the fairness by the drift d defined as the maximum difference between the execution times accumulated by any two jobs. Since jobs are persistent we measure the quality of the schedule by the ratio of the number of migrations to time windows. We show a tradeoff between the drift and the number of migrations. Let n = qm + r with 0 < r < m (the problem is trivial for n ≤ m and for r = 0). For any d ≥ 1, we show a schedule that achieves a migration ratio of r(m -r)/(n(q(d - 1) + 1)) + o(1); namely, it asymptotically requires r(m - r) job migrations every n(q(d - 1) + 1) time windows. We show how to implement the schedule efficiently. We prove that our algorithm is almost optimal by proving a lower bound of r(m -r)/(nqd) on the migration ratio. We also give a more complicated schedule that matches the lower bound for an infinite number of instances. Our algorithms can be extended to the dynamic case in which jobs enter and leave the system over time.

Original languageEnglish (US)
Pages975-984
Number of pages10
StatePublished - 2004
Externally publishedYes
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Conference

ConferenceProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Minimizing Migrations in Fair Multiprocessor Scheduling of Persistent Tasks'. Together they form a unique fingerprint.

Cite this