Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Fast miss ratio curve modeling for storage cache
Hu X., Wang X., Zhou L., Luo Y., Wang Z., Ding C., Ye C. ACM Transactions on Storage14 (2):1-34,2018.Type:Article
Date Reviewed: Dec 24 2018

Miss ratio curve (MRC) profiling techniques are widely used for memory, cache analysis, and design. As noted by the authors, uses include cache partitioning, page size selection, memory management, memory cache prediction, and so on. Thus, MRC profiling techniques are useful to analyze high-throughput storage workloads. This paper describes an average eviction time (AET)-based algorithm for modeling the cache behavior of programs in a multilevel cache. It also shows how to compose an individual program’s cache when the cache is shared in a multiprogrammed environment. The paper provides a good chronology of various breakthroughs in MRC modeling, and guides readers through the improvements to space and time complexity reduction and usage.

Although the paper includes a comprehensive list of relevant work, it principally compares its efficacy against two of the current best known techniques: spatially hashed approximate reuse distance sampling (SHARDS) [1] and counter stacks [2]. Counter stacks use probabilistic counters to generate MRCs by estimating reuse distances from the last access. SHARDS “uses hash-based spatial sampling and a splay tree to track the reuse distances of the sampled data,” reducing space usage significantly. To account for time varying behavior, an adaptive phase sampling technique is described that improves AET’s model accuracy.

In summary, the authors claim that AET is better than counter stacks in space overhead, achieves comparable performance to SHARDS, and is more useful than SHARDS when running in a multiprogrammed environment sharing a least recently used (LRU)-based cache. As we see more computing architectures adopt a memory-centric approach, such papers are timely and useful.

Reviewer:  Shyamkumar Iyer Review #: CR146353 (1903-0081)
1) Waldspurger, C. A.; Park, N.; Garthwaite, A.; Ahmad, I. Efficient MRC construction with SHARDS. In Proc. of the 13th USENIX Conference on File and Storage Technologies USENIX Association, 2015, 95–110.
2) Wires, J.; Ingram, S.; Drudi, Z.; Harvey, N. J. A.; Warfield, A.; Data, C. Characterizing storage workloads with counter stacks. In Proc. of the 11th USENIX Conference on Operating Systems Design and Implementation USENIX Association, 2014, 335–349.
Bookmark and Share
  Reviewer Selected
 
 
Hierarchical Design (D.4.7 ... )
 
 
Modeling Methodologies (I.6.5 ... )
 
 
Storage Management (D.4.2 )
 
Would you recommend this review?
yes
no

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy