TY - GEN

T1 - Cost-oblivious reallocation for scheduling and planning

AU - Bender, Michael A.

AU - Farach-Colton, Martín

AU - Fekete, Sándor P.

AU - Fineman, Jeremy T.

AU - Gilbert, Seth

N1 - Publisher Copyright:
Copyright © 2015 ACM.

PY - 2015/6/13

Y1 - 2015/6/13

N2 - In a reallocating-scheduler problem, jobs may be inserted and deleted from the system over time. Unlike in traditional online scheduling problems, where a job's placement is immutable, in reallocation problems the schedule may be adjusted, but at some cost. The goal is to maintain an approximately optimal schedule while also minimizing the reallocation cost for changing the schedule. This paper gives a reallocating scheduler for the problem of assigning jobs to p (identical) servers so as to minimize the sum of completion times to within a constant factor of optimal, with an amortized reallocation cost for a lengthw job of O(f(w) · log log Δ), where Δ is the length of the longest job and f() is the reallocation-cost function. Our algorithm is cost oblivious, meaning that the algorithm is not parameterized by f(), yet it achieves this bound for any subadditive f(). Whenever f() is strongly subadditive, the reallocation cost becomes O(f(w)). To realize a reallocating scheduler with low reallocation cost, we design a k-cursor sparse table. This data structure stores a dynamic set of elements in an array, with insertions and deletions restricted to k "cursors" in the structure. The data structure achieves an amortized cost of O(log k) for insertions and deletions, while also guaranteeing that any prefix of the array has constant density. Observe that this bound does not depend on n, the number of elements, and hence this data structure, restricted to k < n cursors, beats the lower bound of Ω(log n) for general sparse tables.

AB - In a reallocating-scheduler problem, jobs may be inserted and deleted from the system over time. Unlike in traditional online scheduling problems, where a job's placement is immutable, in reallocation problems the schedule may be adjusted, but at some cost. The goal is to maintain an approximately optimal schedule while also minimizing the reallocation cost for changing the schedule. This paper gives a reallocating scheduler for the problem of assigning jobs to p (identical) servers so as to minimize the sum of completion times to within a constant factor of optimal, with an amortized reallocation cost for a lengthw job of O(f(w) · log log Δ), where Δ is the length of the longest job and f() is the reallocation-cost function. Our algorithm is cost oblivious, meaning that the algorithm is not parameterized by f(), yet it achieves this bound for any subadditive f(). Whenever f() is strongly subadditive, the reallocation cost becomes O(f(w)). To realize a reallocating scheduler with low reallocation cost, we design a k-cursor sparse table. This data structure stores a dynamic set of elements in an array, with insertions and deletions restricted to k "cursors" in the structure. The data structure achieves an amortized cost of O(log k) for insertions and deletions, while also guaranteeing that any prefix of the array has constant density. Observe that this bound does not depend on n, the number of elements, and hence this data structure, restricted to k < n cursors, beats the lower bound of Ω(log n) for general sparse tables.

KW - Cost-oblivious problems

KW - Reallocation

KW - Resource allocation

UR - http://www.scopus.com/inward/record.url?scp=84950246250&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84950246250&partnerID=8YFLogxK

U2 - 10.1145/2755573.2755589

DO - 10.1145/2755573.2755589

M3 - Conference contribution

AN - SCOPUS:84950246250

T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures

SP - 143

EP - 154

BT - SPAA 2015 - Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures

PB - Association for Computing Machinery

T2 - 27th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2015

Y2 - 13 June 2015 through 15 June 2015

ER -