[llvm-dev] Zurich Compiler Social - May 8th - "A Fast Analytical Model of Fully Associative Caches"

[Tobias Grosser via llvm-dev]

Dear all,

Thursday 8th May, 19:00, Tobias Gysi will present a fast static cache model at the monthly LLVM compiler social!

"A Fast Analytical Model of Fully Associative Caches"

Abstract:

While the cost of computation is an easy to understand local property, the cost of data movement on cached architectures depends on global state, does not compose, and is hard to predict. As a result, programmers often fail to consider the cost of data movement. Existing cache models and simulators provide the missing information but are computationally expensive. We present a lightweight cache model for fully associative caches with least recently used (LRU) replacement policy that gives fast and accurate results. We count the cache misses without explicit enumeration of all memory accesses by using symbolic counting techniques twice: 1) to derive the stack distance for each memory access and 2) to count the memory accesses with stack distance larger than the cache size. While this technique seems infeasible in theory, due to non-linearities after the first round of counting, we show that the counting problems are sufficiently linear in practice. Our cache model often computes the results within seconds and contrary to simulation the execution time is mostly problem size independent. Our evaluation measures modeling errors below 0.6% on real hardware. By providing accurate data placement information we enable memory hierarchy aware software development.

With Haystack we present the first cache model that is fast enough for providing programmers with cache miss information while programming, e.g. by using in-editor developer hints similar to the code-completion support that is available in visual studio code today. Similarly, the technique could be used by LLVM (or other compiler toolchains) to select cache optimal code transformations. At the LLVM social we hope to inspire a discussion about how we can make our cache model available to a broad audience.

Bio:

Tobias Gysi is a final-year doctoral student at ETH Zurich, working on performance models and optimization techniques for data-locality transformations as well as domain-specific abstractions and programming models for high-performance computing. Before joining the Scalable Parallel Computing Lab, Tobias Gysi received his MSc in computer science from ETH Zurich in 2005. He then worked at a leading Swiss R&D service provider on feasibility studies and application development covering topics such as cryptography, machine learning, or computational physics. In this context, Tobias Gysi introduced GPU accelerated computing into COSMO, the atmospheric model used by MeteoSwiss for day-to-day weather forecasts and long-term climate simulations.

# Registration

https://www.meetup.com/llvm-compiler-and-code-generation-socials-zurich/events/vxmqlqyzhbmb/

# What

A social meetup to discuss compilation and code generation questions with a focus on LLVM, clang, Polly and related projects.

Our primary focus is to provide a venue (and drinks & snacks) that enables free discussions between interested people without imposing an agenda/program. This is a great opportunity to informally discuss your own projects, get project ideas or just learn about what people at  ETH and around Zurich are doing with LLVM.

Related technical presentations held by participants are welcome (please 
contact us).

# Who:  - Anybody interested -

  - ETH students and staff
  - LLVM developers and enthusiasts external to ETH

# When:  09.05.2018, 19:00

# Where: CAB E 72, ETH Zurich

# Earlier Socials

We have videos of earlier socials available at: http://pollylabs.org/llvm-social-zurich.html

Best,
Tobias