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

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