NDLI: Sharing-aware algorithms for virtual machine colocation

Please wait, while we are loading the content...

Graph expansion and communication costs of fast matrix multiplication: regular submission

A study of transactional memory vs. locks in practice

Filtering: a method for solving graph problems in MapReduce

Brief announcement: full reversal routing as a linear dynamical system

A tight runtime bound for synchronous gathering of autonomous robots with limited visibility

Approximation algorithms for secondary spectrum auctions

Online packet-routing in grids with bounded buffers

Brief announcement: distributed shared memory based on computation migration

On a local protocol for concurrent file transfers

Brief announcement: a partitioned ticket lock

Tight bounds for anonymous adopt-commit objects

Scheduling irregular parallel computations on hierarchical caches

Near linear-work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs

Optimizing hybrid transactional memory: the importance of nonspeculative operations

Parallelism and data movement characterization of contemporary application classes

Brief announcement: better speedups for parallel max-flow

Stabilizing consensus with the power of two choices

Maximising lifetime for fault-tolerant target coverage in sensor networks

Sparse spanners vs. compact routing

Brief announcement: communication bounds for heterogeneous architectures

On multi-processor speed scaling with migration: extended abstract

Brief announcement: transaction polymorphism

A highly-efficient wait-free universal construction

Sharing-aware algorithms for virtual machine colocation

Linear-work greedy parallel approximate set cover and variants

Flat-combining NUMA locks

Work-stealing for mixed-mode parallelism by deterministic team-building

Brief announcement: reclaiming the energy of a schedule, models and algorithms

Convergence of local communication chain strategies via linear transformations: or how to trade locality for speed

Convergence to equilibrium of logit dynamics for strategic games

Re-Chord: a self-stabilizing chord overlay network

Brief announcement: large-scale multimaps

On scheduling in map-reduce and flow-shops

Brief announcement: multilane - a concurrent blocking multiset

A lock-free algorithm for concurrent bags

Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data

Parallelism in dynamic well-spaced point sets

Location-based memory fences

The pochoir stencil compiler

Brief announcement: paging for multicore processors

The car sharing problem

On a bounded budget network creation game

Recommender systems with non-binary grades

Brief announcement: processor allocation for optimistic parallelization of irregular programs

Finding heavy distinct hitters in data streams

Brief announcement: read invisibility, virtual world consistency and permissiveness are compatible

Understanding bloom filter intersection for lazy address-set disambiguation

Brief announcement: locality-enhancing loop transformations for tree traversal algorithms

Brief announcement: program regularization in verifying memory consistency

Brief announcement: RedRem: a parallel redundancy remover

Sharing-aware algorithms for virtual machine colocation

Content Provider	ACM Digital Library
Author	Shenoy, Prashant Sindelar, Michael Sitaraman, Ramesh K.
Abstract	Virtualization technology enables multiple virtual machines (VMs) to run on a single physical server. VMs that run on the same physical server can share memory pages that have identical content, thereby reducing the overall memory requirements on the server. We develop sharing-aware algorithms that can colocate VMs with similar page content on the same physical server to optimize the benefits of inter-VM sharing. We show that inter-VM sharing occurs in a largely hierarchical fashion, where the sharing can be attributed to VM's running the same OS platform, OS version, software libraries, or applications. We propose two hierarchical sharing models: a tree model and a more general cluster-tree model. Using a set of VM traces, we show that up to 67% percent of the inter-VM sharing is captured by the tree model and up to 82% is captured by the cluster-tree model. Next, we study two problem variants of critical interest to a virtualization service provider: the VM Maximization problem that determines the most profitable subset of the VMs that can be packed into the given set of servers, and the VM packing problem that determines the smallest set of servers that can accommodate a set of VMs. While both variants are NP-hard, we show that both admit provably good approximation schemes in the hierarchical sharing models. We show that VM maximization for the tree and cluster-tree models can be approximated in polytime to within a (1 - 1/e) factor of optimal. Further, we show that VM packing can be approximated in polytime to within a factor of O(log n) of optimal for cluster-trees and to within a factor of 3 of optimal for trees, where n is the number of VMs. Finally, we evaluate our VM packing algorithm for the tree sharing model on real-world VM traces and show that our algorithm can exploit most of the available inter-VM sharing to achieve a 32% to 50% reduction in servers and a 25% to 57% reduction in memory footprint compared to sharing-oblivious algorithms.
Starting Page	367
Ending Page	378
Page Count	12
File Format	PDF
ISBN	9781450307437
DOI	10.1145/1989493.1989554
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2011-06-04
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Page sharing Bin packing Virtualization Optimization
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in