
NSF Org: |
CNS Division Of Computer and Network Systems |
Recipient: |
|
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 2018 = $15,876.00 |
History of Investigator: |
|
Recipient Sponsored Research Office: |
1400 TOWNSEND DR HOUGHTON MI US 49931-1200 (906)487-1885 |
Sponsor Congressional District: |
|
Primary Place of Performance: |
1400 Townsend Dr Houghton MI US 49931-1295 |
Primary Place of
Performance Congressional District: |
|
Unique Entity Identifier (UEI): |
|
Parent UEI: |
|
NSF Program(s): |
Special Projects - CNS, CSR-Computer Systems Research |
Primary Program Source: |
01001819DB NSF RESEARCH & RELATED ACTIVIT |
Program Reference Code(s): |
|
Program Element Code(s): |
|
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.
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.