PPoPP Workshop on Principles of Memory Hierarchy Optimization (PMHO)

Video recordings of this year’s talks:

KEYNOTE: Advances in Modeling and Optimization of Caches. Don Towsley.

Random Walks on Huge Graphs at Cache Efficiency. Ke Yang.

CARL: Compiler Assigned Reference Leasing. Chen Ding.

Caching With Delayed Hits. Nirav Atre.

Delayed Hits in Multi-Level Caches. Benjamin Carleton.

A Study on Modeling and Optimization of Memory Systems. Xian-He Sun.

LHD: Improving Cache Hit Rate by Maximizing Hit Density. Nathan Beckmann.

On the Impact of Network Delays on Time-to-live Caching. Karim Elsayed.

Beyond Time Complexity: Data Movement Complexity Analysis for Matrix Multiplication. Wesley Smith.

Saturday 4/2/2022 1pm to 5pm US EDT (GMT -4), 6pm to 10pm Germany, 10:30pm to 2:30am India, 1am to 5am China, 2am to 6am Korea

Zoom Link: https://acm-org.zoom.us/j/92042756839?pwd=TllNMlVaeXQybkpWczh3ZnMxVDdFZz09
  Meeting ID/Passcode: 920 4275 6839 / PPoPP@2022

KEYNOTE

Recent Advances in the Modeling and Optimization of Caches

Donald F. Towsley, Distinguished Professor, University of Massachusetts Amherst

The keynote lecture covers the following results.

1. An optimization-based approach to caching
2. A simple, very accurate model of LRU and variants
3. A new approach to bounding performance of caching policies based on a very simple ordering of failure rates of request distribution along with an application to on-line caching.  

The material is based on the following publications: Deghgan et al. “A Utility Optimization Approach to Network Cache Design,” IEEE/ACM Transactions on Networking, 27(3), 1013-1027, June 2019; “Sharing Cache Resources among Content Providers: A Utility-Based Approach,” IEEE/ACM Transactions on Networking, 27(2), 477-490, April 2019; Jiang et al. “On the Convergence of the TTL Approximation for an LRU Cache under Independent Stationary Request Processes”, ACM TOMPECS, 3(4), 20:1-20:31, September 2018; Panigrahy et al. “A new upper bound on cache hit probability for non-anticipative caching polices,” IFIP WG 7.3 Performance 2020; and Yan et al. “Learning from Optimal Caching for Content Delivery,” Proc. CoNEXT 2021, December 2021.

Workshop Program

PPoPP Workshop on Principles of Memory Hierarchy Optimization (PMHO)

Saturday 4/2/2022 1pm to 5pm US EDT (GMT -4), 6pm to 10pm Germany, 10:30pm to 2:30am India, 1am to 5am China, 2am to 6am Korea

Welcome and Introduction (1pm)

Keynote (1:10pm to 2:00pm)

Don Towsley: “Recent Advances in the Modeling and Optimization of Caches”.

Session 1 (2:00pm to 2:40pm)

Xian-He Sun: “A Study on Modeling and Optimization of Memory Systems”. JCST Jan. ’21. (2:00pm to 2:20pm)

Karim Elsayed: “On the Impact of Network Delays in Time-To-Live Caching”. Unpublished. (2:20pm to 2:40pm)

Break (2:40pm to 2:50pm)

Chen Ding: “CARL: Compiler Assigned Reference Leasing”. TACO March ’22. (2:50pm to 3:10pm).

Nirav Atre: “Caching with Delayed Hits”. SIGCOMM ’20. (3:10pm to 3:30pm)

Benjamin Carleton: “Evaluating the Impact of Delayed Hits in Multi-Level Caches”. SOSP ’21 SRC Undergraduate Winner. (3:30pm to 3:40pm).

Break (3:40pm to 3:50pm)

Nathan Beckmann: “LHD: Improving Cache Hit Rate by Maximizing Hit Density”. NSDI ’18. (3:50pm to 4:10pm)

Wesley Smith: “Beyond Time Complexity: Data Movement Complexity Analysis for Matrix Multiplication”. Under review. (4:10pm to 4:30pm)

Ke Yang (Video): “Random Walks on Huge Graphs at Cache Efficiency”. SOSP ’21. (4:30pm to 4:45pm)

Open discussion (4:45pm to 5:00pm)

For people who cannot attend, we plan to make the talk videos available as we have done in the 2021 workshop.

Organizers

Faculty:

• Chen Ding, University of Rochester
• Nathan Tallent, Pacific Northwest National Laboratory

Student:

• Wesley Smith, University of Rochester

Call for Presentations

Data movement is now often the most significant constraint on speed, throughput, and power consumption for applications in a wide range of domains. Unfortunately, modern memory systems are almost always hierarchical, parallel, dynamically allocated and shared, making them hard to model and analyze. In addition, the complexity of these systems is rapidly increasing due to the advent of new technologies such as Intel Optane and high-bandwidth memory (HBM).

Conventional solutions to memory hierarchy optimization problems are often compartmentalized and heuristic-driven; in the modern era of complex memory systems these lack the rigor and robustness to be fully effective. Going forward, research on performance in the memory hierarchy must adapt, ideally creating theories of memory that aim at formal, rigorous performance and correctness models, as well as optimizations that are based on mathematics, ensure reproducible results, and have provable guarantees.

Format and Topics

PMHO is an annual specialized and topic-driven workshop to present ongoing, under review, or previously published work related to the following non-exhaustive topic list:

• Mathematical and theoretical models of memory hierarchies including CPU/GPU/accelerator caches, software caching systems, key-value stores, network caches and storage system caches
• Algorithmic and formal aspects of cache management including virtual memory
• Programming models and compiler optimization of hierarchical complex memory systems

There will be no formal peer review process or publication, and presentations will be a mix of selections from submissions and invited presentations.

The 2022 workshop will take place online during the weekend of April 2 (Exact date TBD). It is hosted by the PPoPP 2022 conference.

Submission

Submit your presentation proposal to save-DyfTNd4RHy3y@3.basecamp.com. Submissions should consist of an one-page abstract of the topic you intend to present alongside any (optional) pertinent publications or preprints.

The submission deadline is Monday March 7, 2022 AOE.