Constructing Dynamic Policies for Paging Mode Selection
Article No.: 72, Pages 1 - 9
Abstract
Virtualization technology is a key component for data center management which allows for multiple users and applications to share a single, physical machine. Modern virtual machine monitors utilize both software and hardware-assisted paging for memory virtualization, however neither paging mode is always preferable. Previous studies have shown that dynamic selection, which at runtime selects paging modes according to relevant performance metrics, can be effective in tailoring memory virtualization to program workload. However, these approaches require low-level manual analysis, or depend on prior knowledge of workload characteristics and phasing.
We map the problem of dynamic paging mode selection to the contextual bandit, a model for sequential decision making in environments with limited feedback. Utilizing random profiling, which executes a workload while regularly selecting paging modes at random, we construct a paging mode selection policy that dynamically optimizes workload performance given page fault and translation lookaside buffer miss counts. Our approach yields an effective policy, DSP-OFFSET, for the dynamic paging mode selection problem. When trained and evaluated on subsets of the SPEC CPU2006 benchmark suite, DSP-OFFSET achieves speedups up to 44% compared to static paging mode selections, which is equivalent to the performance of the state-of-the-art ASP-SVM model. In addition, DSP-OFFSET requires at most a tenth of the profiling time of ASP-SVM (2.5 hours compared to over 24 hours) to achieve equivalent performance.
References
[1]
Keith Adams and Ole Agesen. 2006. A Comparison of Software and Hardware Techniques for x86 Virtualization. In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XII). 2--13.
[2]
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. 2003. The Nonstochastic Multiarmed Bandit Problem. SIAM J. Comput. 32, 1 (2003), 48--77.
[3]
Chang S. Bae, John R. Lange, and Peter A. Dinda. 2011. Enhancing Virtualized Application Performance Through Dynamic Adaptive Paging Mode Selection. In Proceedings of the 8th ACM International Conference on Autonomic Computing (ICAC '11). 255--264.
[4]
Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, and Andrew Warfield. 2003. Xen and the Art of Virtualization. SIGOPS Operating Systems Review 37, 5 (2003), 164--177.
[5]
Alina Beygelzimer and John Langford. 2009. The Offset Tree for Learning with Partial Labels. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '09). 129--138.
[6]
Ravi Bhargava, Benjamin Serebrin, Francesco Spadini, and Srilatha Manne. 2008. Accelerating Two-Dimensional Page Walks for Virtualized Systems. In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XIII). 26--35.
[7]
Nikhil Bhatia. 2009. Performance Evaluation of Intel EPT Hardware Assist. Technical Report. VMWare.
[8]
Miroslav Dudík, John Langford, and Lihong Li. 2011. Doubly Robust Policy Evaluation and Learning. In Proceedings of the 28th International Conference on International Conference on Machine Learning (ICML '11). 1097--1104.
[9]
Charles Elkan. 1997. Boosting And Naive Bayesian Learning. Technical Report. University of California, San Diego.
[10]
Yoav Freund and Robert E. Schapire. 1997. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting. J. Comput. System Sci. 55, 1 (1997), 119--139.
[11]
Matthew Gillespie. 2009. Best Practices for Paravirtualization Enhancements from Intel Virtualization Technology: EPT and VT-d. Technical Report. Intel.
[12]
John L. Henning. 2006. SPEC CPU2006 Benchmark Descriptions. SIGARCH Computer Architecture News 34, 4 (September 2006), 1--17.
[13]
Intel 2016. Intel 64 and IA-32 Architectures Developer's Manual: Volume 3C. Intel.
[14]
Víctor Jiménez, Roberto Gioiosa, Francisco J. Cazorla, Alper Buyuktosunoglu, Pradip Bose, and Francis P. O'Connell. 2012. Making Data Prefetch Smarter: Adaptive Prefetching on POWER7. In 21st International Conference on Parallel Architectures and Compilation Techniques (PACT). 137--146.
[15]
Rebecca Killick, Paul Fearnhead, and I.A. Eckley. 2012. Optimal Detection of Changepoints With a Linear Computational Cost. 107 (2012), 1590--1598.
[16]
Wei Kuang, Laura E. Brown, and Zhenlin Wang. 2015. Selective switching mechanism in virtual machines via support vector machines and transfer learning. Machine Learning 101, 1 (2015), 137--161.
[17]
J. Lange, K. Pedretti, T. Hudson, P. Dinda, Z. Cui, L. Xia, P. Bridges, A. Gocke, S. Jaconette, M. Levenhagen, and R. Brightwell. 2010. Palacios and Kitten: New High Performance Operating Systems for Scalable Virtualized and Native Supercomputing. In 2010 IEEE International Symposium on Parallel Distributed Processing (IPDPS '10). 1--12.
[18]
John Langford, Alexander Strehl, and Jennifer Wortman. 2008. Exploration Scavenging. In Proceedings of the 25th International Conference on Machine Learning (ICML '08). 528--535.
[19]
John Langford and Tong Zhang. 2007. The Epoch-Greedy Algorithm for Contextual Multi-armed Bandits. In Advances in Neural Information Processing Systems 20 (NIPS). 817--824.
[20]
Shih-wei Liao, Tzu-Han Hung, Donald Nguyen, Chinyen Chou, Chiaheng Tu, and Hucheng Zhou. 2009. Machine Learning-based Prefetch Optimization for Data Center Applications. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (SC '09). 1--10.
[21]
Tan T. Nguyen and Scott Sanner. 2013. Algorithms for Direct 0-1 Loss Optimization in Binary Classification. In Proceedings of the 30th International Conference on International Conference on Machine Learning (ICML '13). 1085--1093.
[22]
J. R. Quinlan. 1996. Bagging, Boosting, and C4.S. In Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI '96). 725--730.
[23]
Saami Rahman, Martin Burtscher, Ziliang Zong, and Apan Qasem. 2015. Maximizing Hardware Prefetch Effectiveness with Machine Learning. In Proceedings of the 17th International Conference on High Performance Computing and Communications. 383--389.
[24]
Xipeng Shen, Yutao Zhong, and Chen Ding. 2004. Locality Phase Prediction. In Proceedings of the 11th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XI). 165--176.
[25]
Timothy Sherwood, Erez Perelman, and Brad Calder. 2001. Basic Block Distribution Analysis to Find Periodic Behavior and Simulation Points in Applications. In Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques (PACT '01). 3--14.
[26]
Timothy Sherwood, Suleyman Sair, and Brad Calder. 2003. Phase Tracking and Prediction. In Proceedings of the 30th Annual International Symposium on Computer Architecture (ISCA '03). 336--349.
[27]
B. Sinharoy, R. Kalla, W. J. Starke, H. Q. Le, R. Cargnoni, J. A. Van Norstrand, B. J. Ronchetti, J. Stuecheli, J. Leenstra, G. L. Guthrie, D. Q. Nguyen, B. Blaner, C. F. Marino, E. Retter, and P. Williams. 2011. IBM POWER7 Multicore Server Processor. IBM Journal of Research and Development (2011), 191--219.
[28]
Alexander L. Strehl, John Langford, Lihong Li, and Sham M. Kakade. 2010. Learning from Logged Implicit Exploration Data. In Proceedings of the 23rd International Conference on Neural Information Processing Systems (NIPS '10). 2217--2225.
[29]
Vish Viswanathan. 2014. Disclosure of H/W Prefetcher Control on some Intel Processors. Technical Report. Intel.
[30]
Carl A. Waldspurger. 2002. Memory Resource Management in VMware ESX Server. SIGOPS Operating Systems Review 36, SI (2002), 181--194.
[31]
Xiaolin Wang, Jiarui Zang, Zhenlin Wang, Yingwei Luo, and Xiaoming Li. 2011. Selective Hardware/Software Memory Virtualization. In Proceedings of the 7th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE '11). 217--226.
[32]
Min Yang, Linli Xu, Martha White, Dale Schuurmans, and Yao liang Yu. 2010. Relaxed Clipping: A Global Training Method for Robust Regression and Classification. In Advances in Neural Information Processing Systems 23 (NIPS). 2532--2540.
[33]
Xulei Yang, Qing Song, and Aize Cao. 2005. Weighted Support Vector Machine for Data Classification. In Proceedings of the 2005 IEEE International Joint Conference on Neural Networks, Vol. 2. 859--864.
[34]
Bianca Zadrozny, John Langford, and Naoki Abe. 2003. Cost-Sensitive Learning by Cost-Proportionate Example Weighting. In Proceedings of the Third IEEE International Conference on Data Mining (ICDM '03). 435--442.
Index Terms
- Constructing Dynamic Policies for Paging Mode Selection
Recommendations
Dynamic Memory Pressure Aware Ballooning
MEMSYS '15: Proceedings of the 2015 International Symposium on Memory SystemsHardware virtualization is a major component of large scale server and data center deployments due to their facilitation of server consolidation and scalability. Virtualization, however, comes at a high cost in terms of system main memory utilization. ...
Enhancing virtualized application performance through dynamic adaptive paging mode selection
ICAC '11: Proceedings of the 8th ACM international conference on Autonomic computingVirtual address translation in a virtual machine monitor (VMM) for modern x86 processors can be implemented using a software approach known as shadow paging or a hardware approach known as nested paging. Most VMMs, including our Palacios VMM, support ...
Optimizing guest swapping using elastic and transparent memory provisioning on virtualization platform
On virtualization platforms, peak memory demand caused by hotspot applications often triggers page swapping in guest OS, causing performance degradation inside and outside of this virtual machine (VM). Even though host holds sufficient memory pages, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2018
945 pages
ISBN:9781450365109
DOI:10.1145/3225058
Copyright © 2018 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
In-Cooperation
- University of Oregon: University of Oregon
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 August 2018
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
ICPP 2018
Acceptance Rates
ICPP '18 Paper Acceptance Rate 91 of 313 submissions, 29%;
Overall Acceptance Rate 91 of 313 submissions, 29%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 242Total Downloads
- Downloads (Last 12 months)48
- Downloads (Last 6 weeks)8
Reflects downloads up to 30 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in