High-performance computing in the cloud environment uses ample virtual resources, which in turn require physical infrastructures provided by cloud service providers (CSPs). Naturally, CSPs would like to place virtual ...
详细信息
High-performance computing in the cloud environment uses ample virtual resources, which in turn require physical infrastructures provided by cloud service providers (CSPs). Naturally, CSPs would like to place virtual machines (VM) in a cost-effective way satisfying the resource requirement of the VMs and the capacity constraints of the hosts. Such consideration has led to the well known virtual machine placement (VMP) problem. In this paper, we consider a variant of the VMP, taking into account the communication among the VMs. We introduce the concept of Virtual Cluster, made up of VMs communicating among themselves. It is desirable to place the VMs of a cluster close to each other and thus reduce the communication cost. The objective for the Virtual Cluster Placement (VCP) problem is to reduce the communication cost. For this, we have to consider the network topology of the data center. In this paper, we have proposed some heuristics for both kinds of placement problems (VMP as well as VCP) and given Integer Linear Programming (ILP) formulations. We have also presented algorithms based on Semidefinite Programming (SDP) and meta-heuristic based on Genetic Algorithms. We have compared the performance of proposed heuristics with other existing works and the optimal solutions obtained from ILPs.
Finding a low-dimensional embedding of a graph of n nodes in R-d is an essential task in many applications. For instance, maximum variance unfolding (MVU) is a well-known dimensionality reduction method that involves ...
详细信息
Finding a low-dimensional embedding of a graph of n nodes in R-d is an essential task in many applications. For instance, maximum variance unfolding (MVU) is a well-known dimensionality reduction method that involves solving this problem. The standard approach is to formulate the embedding problem as a semidefinite program (SDP). However, the SDP approach does not scale well to large graphs. In this paper, we exploit the fact that many graphs have an intrinsically low dimension, and thus the optimal matrix resulting from the solution of the SDP has a low rank. This observation leads to a quadratic reformulation of the SDP that has far fewer variables, but on the other hand, is a difficult convex maximization problem. We propose an approach for obtaining a solution to the SDP by solving a sequence of smaller quadratic problems with increasing dimension. Utilizing an augmented Lagrangian and an interior-point method for solving the quadratic problems, we demonstrate with numerical experiments on MVU problems that the proposed approach scales well to very large graphs.
暂无评论