SOSP '21 | Solving Large-Scale Granular Resource Allocation Problems Efficiently with POP

[mental2008]

Presented in SOSP '21. [ Paper | Video | Code ]

Authors: Deepak Narayanan, Fiodar Kazhamiaka, Firas Abuzaid, Peter Kraft, Akshay Agrawal, Srikanth Kandula, Stephen Boyd, and Matei Zaharia Stanford University, Microsoft Research

[mental2008]

Question

How to solve a resource allocation problem (in many computer systems, e.g., cluster scheduling, traffic engineering, load balancing)?

1. Formulate it as a mathematical optimization problem and find an exact solution (using off-the-shelf solvers). => Not feasible for large problem sizes with tight SLAs.
2. Existing systems choose heuristic algorithms. => Not optimal allocations.

Solution

Propose a technique named Partitioned Optimization Problems (POP).

1. Randomly split the problem into smaller problems.
2. Coalesces the resulting sub-allocations into a global allocation.

Tradeoff between allocation quality and runtime (POP)

• Faster than directly solving mathematical programs.
• Better allocations than existing heuristic algorithms.

I am curious about the detailed algorithm and why random partitioning works well.