Award Abstract # 1618384
CSR: Small: Effective Sampling-based Miss Ratio Curves: Theory and Practice

NSF Org: CNS
Division Of Computer and Network Systems
Recipient: MICHIGAN TECHNOLOGICAL UNIVERSITY
Initial Amendment Date: August 8, 2016
Latest Amendment Date: April 24, 2018
Award Number: 1618384
Award Instrument: Standard Grant
Program Manager: Erik Brunvand
CNS
 Division Of Computer and Network Systems
CSE
 Directorate for Computer and Information Science and Engineering
Start Date: October 1, 2016
End Date: September 30, 2021 (Estimated)
Total Intended Award Amount: $375,000.00
Total Awarded Amount to Date: $390,876.00
Funds Obligated to Date: FY 2016 = $375,000.00
FY 2018 = $15,876.00
History of Investigator:
  • Zhenlin Wang (Principal Investigator)
    zlwang@mtu.edu
Recipient Sponsored Research Office: Michigan Technological University
1400 TOWNSEND DR
HOUGHTON
MI  US  49931-1200
(906)487-1885
Sponsor Congressional District: 01
Primary Place of Performance: Michigan Technological University
1400 Townsend Dr
Houghton
MI  US  49931-1295
Primary Place of Performance
Congressional District:
01
Unique Entity Identifier (UEI): GKMSN3DA6P91
Parent UEI: GKMSN3DA6P91
NSF Program(s): Special Projects - CNS,
CSR-Computer Systems Research
Primary Program Source: 01001617DB NSF RESEARCH & RELATED ACTIVIT
01001819DB NSF RESEARCH & RELATED ACTIVIT
Program Reference Code(s): 7923, 9251
Program Element Code(s): 171400, 735400
Award Agency Code: 4900
Fund Agency Code: 4900
Assistance Listing Number(s): 47.070

ABSTRACT

Caches, such as distributed in-memory cache for key-value store, often play a key role in overall system performance. Miss ratio curves (MRCs) that relate cache miss ratio to cache size are an effective tool for cache management. This project develops a new cache locality theory that can significantly reduce the time and space overhead of MRC construction and thus makes it suitable for online profiling. The research will influence system design in both software and hardware, as nearly every system involves multiple types of cache. The results can thus benefit a wide range of systems from personal desktops to large scale data centers. We will integrate our results into existing open source infrastructure for the industry to adopt. In addition, this project will offer new course materials that motivate core computer science research and practice.

The project investigates a new cache locality theory, applies it to several caching or memory management systems, and examines the impact of different online random sampling techniques. The theory introduces a concept of average eviction time that facilitates modeling data movement in cache. The new model constructs MRCs with data reuse distribution that can be effectively sampled. This model yields a constant space overhead and linear time complexity. The research is focused on theoretical properties and limitations of this model when compared with other recent MRC models. With this lightweight model, the project seeks to guide hardware cache partitioning, improve memory demand prediction and management in a virtualized system, and optimize key-value memory cache allocation.

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Note:  When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

(Showing: 1 - 10 of 23)
Cheng Pan, Lan Zhou, Yingwei Luo, Xiaolin Wang, and Zhenlin Wang "Lightweight and Accurate Memory Allocation in Key-Value Cache" International Journal of Parallel Programming , v.47 , 2019 10.1007/s10766-018-0616-4
Cheng Pan, Xiameng Hu, Lan Zhou, Yongwei Luo, Xiaolin Wang, and Zhenlin Wang "PACE: Penalty Aware Cache Modeling with Enhanced AET" the 2018 ACM Asia-Pacific Workshop on Systems , 2018 10.1145/3265723.3265736
Cheng Pan, Yingwei Luo, Xiaolin Wang, and Zhenlin Wang "Penalty- and Locality-aware Memory Allocation in Redis Using Enhanced AET" ACM Transactions on Storage , v.17 , 2021 , p.1 3447573
Cheng Pan, Yingwei Luo, Xiaolin Wang, and Zhenlin Wang "pRedis: Penalty and Locality Aware Memory Allocation in Redis" the 2019 ACM Symposium on Cloud Computing (SoCC '19) , 2019 3357223.3362729
Daniel Byrne, Nilufer Onder and Zhenlin Wang "Fast Slab Reassignment" the 2019 International Symposium on Memory Systems (MemSys '19) , 2019 10.1145/3357526.3357562
Daniel Byrne, Nilufer Onder and Zhenlin Wang "mPart: Miss-Ratio Curve Guided Partitioning in Key-Value Stores" the 2018 International Symposium on Memory Management , 2018 10.1145/3210563.3210571
Jason Hiebel, Laura Brown, and Zhenlin Wang "Constructing Dynamic Policies for Paging Mode Selection" the 47th International Conference on Parallel Processing , 2018 10.1145/3225058.3225082
Jason Hiebel, Laura Brown, and Zhenlin Wang "Machine Learning for Fine-Grained Hardware Prefetcher Control" the 47th International Conference on Parallel Processing (ICPP'19) , 2019 10.1145/3337821.3337854
Jinyuan Hu, Xiaokuang Bai, Sai Sha, Yingwei Luo, Xiaolin Wang, and Zhenlin Wang "Working Set Size Estimation with Hugepages in Virtualization" the 16th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA '18) , 2018 10.1109/BDCloud.2018.00081
Jinyuan Hu, Xiaokuang Bai, Yingwei Luo, Xiaolin Wang, and Zhenlin Wang "HUB: hugepage ballooning in kernel-based virtual machines" the 2018 International Symposium on Memory Systems (MemSys '18) , 2018 10.1145/3240302.3240420
Sai Sha, Jingyuan Hu, Yingwei Luo, Xiaolin Wang and Zhenlin Wang "Huge Page Friendly Virtualized Memory Management" Journal of Computer Science and Technology , v.35 , 2020 , p.433 s11390-020-9693-0
(Showing: 1 - 10 of 23)

PROJECT OUTCOMES REPORT

Disclaimer

This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.

The research goal of this project is to develop a new cache locality theory that can significantly reduce the time and space overhead of miss ratio curve (MRC) construction and thus makes it suitable for online profiling. With a lightweight model based on the theory, the project seeks to guide hardware cache partitioning, improve memory demand prediction and management in a virtualized system, and optimize key-value memory cache allocation.


The stack-based cache models for constructing a miss ratio curve for the LRU replacement policy can be dated back to 1970s. However, not until the recent decade is the research community able to develop accurate models that are efficient enough for effective online profiling. This project develops and evaluates a new model which constructs MRCs utilizing data reuse distribution that can be effectively sampled on the fly. This model yields a constant space overhead and linear time complexity. The model is based on a new cache locality theory that relates cache replacement to data movement speed along a stack. We have investigated the limitations of this model and extended it to consider variable object sizes, and deletes and updates that appear in in-memory key-values stores. 

The research will influence system design in both software and hardware, as nearly every system involves multiple types of cache. The results can thus benefit a wide range of systems from personal desktops to large scale data centers. We have adopted this model to drive last-level cache partitioning, utilizing the Intel Cache Allocation Technology (CAT). We have implemented the model in Redis and Memcached to guide their memory management. We have also embedded the model in KVM for dynamic memory allocation among the virtual machines which share the host machine memory. The results are available through open source code and publications. 7 journal papers and 16 conference papers were supported, in part, by this grant.

The project has helped to train and educate six PhD students and one MS student in the Department of Computer Science at Michigan Tech. One female MS student received her MS degree when working on the related research. A female undergraduate student was supported with the REU supplement. The PI has presented the research results to prospective CS students and freshmen every year to motivate their interest in computer science and system research. In addition, this project offers new course materials that motivate core computer science research and practice.

 


Last Modified: 12/15/2021
Modified by: Zhenlin Wang

Please report errors in award information by writing to: awardsearch@nsf.gov.

Print this page

Back to Top of page