Partition with side effects - Sorbonne Université Access content directly
Conference Papers Year : 2015

Partition with side effects


In data centers, many tasks (services, virtual machines or computational jobs) share a single physical machine. We propose a new resource management model for such colocation. Our model uses two parameters of a task—its size and its type—to characterize how a task influences the performance of the other tasks allocated on the same machine. As typically a data center hosts many similar, recurring tasks (e.g.: a webserver, a database, a CPU-intensive computation), the resource manager should be able to construct these types and their performance interactions. Moreover, realistic variants of our model are polynomially-solvable, in contrast to the NP-hard vector packing used previously. In particular, we minimize the total cost in a model in which each task's cost is a function of the total sizes of tasks allocated on the same machine (each type is counted separately). We show that for a linear cost function the problem is strongly NP-hard, but polynomially-solvable in some particular cases. We propose an algorithm polynomial in the number of tasks (but exponential in the number of types and machines); and another algorithm polynomial in the number of tasks and machines (but exponential in the number of types and admissible sizes of tasks). When there is a single type, we give a polynomial time algorithm. We also prove that, even for a single type, the problem becomes NP-hard for convex costs.
Fichier principal
Vignette du fichier
hipc2015.pdf (289.15 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01304901 , version 1 (20-04-2016)



Fanny Pascual, Krzysztof Rzadca. Partition with side effects. 22nd IEEE International Conference on High Performance Computing, HiPC 2015, Dec 2015, Bengaluru, India. ⟨10.1109/HiPC.2015.52⟩. ⟨hal-01304901⟩
63 View
93 Download



Gmail Facebook X LinkedIn More