  Modern data centers serve workloads which are capable of exploiting
parallelism. When a job parallelizes across multiple servers it will complete
more quickly, but jobs receive diminishing returns from being allocated
additional servers. Because allocating multiple servers to a single job is
inefficient, it is unclear how best to allocate a fixed number of servers
between many parallelizable jobs. This paper provides the first optimal
allocation policy for minimizing the mean slowdown of parallelizable jobs of
known size when all jobs are present at time 0. Our policy provides a simple
closed form formula for the optimal allocations at every moment in time.
Minimizing mean slowdown usually requires favoring short jobs over long ones
(as in the SRPT policy). However, because parallelizable jobs have sublinear
speedup functions, system efficiency is also an issue. System efficiency is
maximized by giving equal allocations to all jobs and thus competes with the
goal of prioritizing small jobs. Our optimal policy, high-efficiency SRPT
(heSRPT), balances these competing goals. heSRPT completes jobs according to
their size order, but maintains overall system efficiency by allocating some
servers to each job at every moment in time. Our results generalize to also
provide the optimal allocation policy with respect to mean flow time. Finally,
we consider the online case where jobs arrive to the system over time. While
optimizing mean slowdown in the online setting is even more difficult, we find
that heSRPT provides an excellent heuristic policy for the online setting. In
fact, our simulations show that heSRPT significantly outperforms
state-of-the-art allocation policies for parallelizable jobs.
