Optimising resource allocation in data centres: Vector bin packing heuristics and contention quantification models

Modern data centres house thousands of servers that consume vast amounts of energy and produce greenhouse emissions. It is therefore important to maximise resource utilisation and minimise the number of active servers to avoid wasting resources. However, optimising resource allocation for multi-dimensional resources at scale is challenging. Fundamentally, this relates to the vector bin packing problem, which is NP-hard. In addition, applications running on a highly utilised server may suffer performance degradation, particularly in the memory subsystem. Motivated by these two challenges, this thesis first investigates the vector bin packing problem and then investigates the resource contention problem to quantify the performance degradation of co-scheduled applications.

For the vector bin packing problem, we propose three novel heuristics employing various optimisation techniques. These heuristics were extensively evaluated against a wide range of algorithms from the literature using standard benchmarks. The results reveal a clear trade-off between packing quality and runtime. Compared to competitors with similar runtime ranges, our heuristics achieved superior packing quality with acceptable runtime overheads. Next, we focus on quantifying the slowdown of co-scheduled applications caused by resource sharing in the shared cache. We proposed a novel micro-benchmark profiling-based approach to predict the cache occupancy of co-scheduled applications. Based on this, we then developed a model to predict cache misses and runtimes of co-scheduled applications. Our co-scheduling experiments demonstrate that, compared to other micro-benchmark profiling-based approaches, our approach provides significantly better prediction accuracy. We believe that the techniques proposed in this thesis can be applied to optimising resource allocation in real-world data centres across various aspects.