NUMA-Aware Virtual Machine Placement: New MMMK Model and Column Generation-Based Decomposition Approach

The efficiency and profitability of cloud data centers are significantly influenced by virtual machine (VM) placement. However, the Non-Uniform Memory Access (NUMA), which has been practically applied to reduce the memory bandwidth competition, is often neglected in the existing research. Actually, the incorporation of NUMA may change the traditional resource allocation mechanism, and demands for a new VM placement model. Hence, considering the multi-NUMA architecture, this paper studies the NUMA-aware VM placement (NAVMP) problem in a cloud computing system, where the resource pool is composed of enormous number of heterogeneous servers with diverse multi-resource remains. The NAVMP problem is analytically formulated as an integer program (IP). Also, for the first time, the incarnations of VM types are introduced to simplify the VM deployment rules originated from complex NUMA architecture. We aim to maximize the VM provision ability (VPA) of the resource pool, and thus propose a novel Value Function to describe servers' VPA. The resulting formulation, which is a new variant of the multiple-choice multiple multi-dimensional knapsack (MMMK) problem, is of significant computational challenges. So we customize a decomposition approach based on Column Generation (CG) to support the offline optimization. Numerical experiments on a practical dataset demonstrate the validity and scalability of the customized CG-based approach. Our approach outperforms a professional IP solver, i.e., Cbc, and a popular meta-heuristic algorithm, i.e., genetic algorithm (GA), and can efficiently address large-scale NAVMP instances with ten thousands of VM demands and servers. Note to Practitioners - This paper proposes a novel IP model for NAVMP. To cope with the complicated deployment logic associated with the complex multi-NUMA architecture of modern multi-core systems, we present an NAVMP formulation from the perspective of incarnations of VM types. Different from the traditional VM placement problem that aims to minimize the number of activated servers, i.e., the vector bin packing (VBP)-based model, we adopt the objective that maximizes the VPA of a resource pool for further improving the resource utilization. The resulting formulation is an MMMK problem, which is computational very challenging for a practical scale resource pool. Hence, to mitigate the computation burden, we design and implement a CG-based decomposition approach to support the offline optimization for NAVMP. Parallelization scheme and nontrivial heuristic strategies are applied to promote the computation efficiency. According to our numerical experiments, the proposed decomposition approach demonstrates a much superior solution capacity to the Cbc solver and GA. In particular, to achieve a comparable solution precision with Cbc, the computing time can be reduced by orders of magnitude. Also the CG-based approach outperforms GA in both the solution quality and computation time for large-scale instances. Besides, compared to the VBP model, our MMMK-based NAVMP model has improved the VPA up to 44.39%. Practically, the proposed offline approach can be leveraged to guide online VM allocation decisions, and perform efficient results evaluation.