Fast optimal nonconcave resource allocation

摘要: Efficient use of shared resources is a key problem in wide range computer systems, from cloud computing to multicore processors. Optimized allocation among users can result dramatically improved overall system performance. Resource general NP-complete, and past works have mostly focused on studying concave performance curves, applying heuristics nonconcave or finding optimal solutions using slow dynamic programming methods. These approaches drawbacks terms generality, accuracy efficiency. In this paper, we observe that realistic curves are often not concave, but rather be broken into small number convex segments. We present efficient algorithms for approximately resource leveraging idea. also introduce several algorithmic techniques may independent interest. Our algorithm runs O(snα(m)m(log m)2) time, our approximation finds 1 − e any > 0 O(s/e α(n/e)n2 log n/e m) time; here, s the segments, n processes, m amount resource, α inverse Ackermann function ≤ 4 practice. Existing exact O(nm2) O(n2 m/e) running times, resp., so much faster practical case where << m. Experiments show 215 times than when = 1M, produce with 33% better greedy algorithms.