Fri 17 Jun 2022 13:30 - 13:50 at Toucan - Verification & Optimization Chair(s): Charith Mendis
Sat 18 Jun 2022 01:30 - 01:50 at Toucan - Verification & Optimization

There is a huge and growing gap between the speed of accesses to data stored in main memory vs cache. Thus, cache misses account for a significant portion of runtime overhead in virtually every program and minimizing them has been an active research topic for decades. The primary and most classical formal model for this problem is that of Cache-conscious Data Placement (CDP): given a commutative cache with constant capacity $k$ and a sequence $\Sigma$ of accesses to data elements, the goal is to map each data element to a cache line such that the total number of cache misses over $\Sigma$ is minimized. CDP has been widely studied since the 1990s. In POPL 2002, Petrank and Rawitz proved a notoriously strong hardness result: They showed that for every $k \geq 3,$ CDP is not only NP-hard but also hard-to-approximate within any non-trivial factor unless $\text{P}=\text{NP}$. As such, all subsequent works gave up on theoretical improvements and instead focused on heuristic algorithms with no theoretical guarantees.

In this work, we present the first-ever positive theoretical result for CDP. The fundamental idea behind our approach is that real-world instances of the problem have specific structural properties that can be exploited to obtain efficient algorithms with strong approximation guarantees. Specifically, the access graphs corresponding to many real-world access sequences are sparse and tree-like. This was already well-known in the community but has only been used to design heuristics without guarantees. In contrast, we provide efficient algorithms that provably approximate the optimal number of cache misses within any factor $1 + \epsilon,$ assuming that the access graph of a specific degree $d_\epsilon$ is sparse, i.e. sparser real-world instances lead to tighter approximations. We also provide experimental results showing that our approach frequently outperforms previous methods.

Fri 17 Jun

Displayed time zone: Pacific Time (US & Canada) change

13:30 - 14:50
Verification & OptimizationPLDI at Toucan +12h
Chair(s): Charith Mendis University of Illinois at Urbana-Champaign
13:30
20m
Talk
Efficient Approximations for Cache-conscious Data Placementvirtual
PLDI
Ali Ahmadi Sharif University of Technology, Majid Daliri University of Tehran, Amir Kafshdar Goharshady Hong Kong University of Science and Technology, Andreas Pavlogiannis Aarhus University
DOI
13:50
20m
Talk
FreeTensor: A Free-form DSL with Holistic Optimizations for Irregular Tensor Programsvirtual
PLDI
Shizhi Tang Tsinghua University, Jidong Zhai Tsinghua University, Haojie Wang , Lin Jiang Tsinghua University, Liyan Zheng Tsinghua University, Zhenhao Yuan Tsinghua University, Chen Zhang Tsinghua University
DOI Pre-print
14:10
20m
Talk
Lasagne: A Static Binary Translator for Weak Memory Model Architecturesvirtual
PLDI
Rodrigo C. O. Rocha University of Edinburgh, UK, Dennis Sprokholt TU Delft, Martin Fink TU Munich, Redha Gouicem TU Munich, Tom Spink University of St Andrews, Soham Chakraborty TU Delft, Pramod Bhatotia TU Munich / University of Edinburgh
DOI
14:30
20m
Talk
Verifying Optimizations of Concurrent Programs in the Promising Semanticsvirtual
PLDI
Junpeng Zha Nanjing University, Hongjin Liang Nanjing University, Xinyu Feng Nanjing University
DOI Pre-print

Sat 18 Jun

Displayed time zone: Pacific Time (US & Canada) change

01:30 - 02:50
Verification & OptimizationPLDI at Toucan
01:30
20m
Talk
Efficient Approximations for Cache-conscious Data Placementvirtual
PLDI
Ali Ahmadi Sharif University of Technology, Majid Daliri University of Tehran, Amir Kafshdar Goharshady Hong Kong University of Science and Technology, Andreas Pavlogiannis Aarhus University
DOI
01:50
20m
Talk
FreeTensor: A Free-form DSL with Holistic Optimizations for Irregular Tensor Programsvirtual
PLDI
Shizhi Tang Tsinghua University, Jidong Zhai Tsinghua University, Haojie Wang , Lin Jiang Tsinghua University, Liyan Zheng Tsinghua University, Zhenhao Yuan Tsinghua University, Chen Zhang Tsinghua University
DOI Pre-print
02:10
20m
Talk
Lasagne: A Static Binary Translator for Weak Memory Model Architecturesvirtual
PLDI
Rodrigo C. O. Rocha University of Edinburgh, UK, Dennis Sprokholt TU Delft, Martin Fink TU Munich, Redha Gouicem TU Munich, Tom Spink University of St Andrews, Soham Chakraborty TU Delft, Pramod Bhatotia TU Munich / University of Edinburgh
DOI
02:30
20m
Talk
Verifying Optimizations of Concurrent Programs in the Promising Semanticsvirtual
PLDI
Junpeng Zha Nanjing University, Hongjin Liang Nanjing University, Xinyu Feng Nanjing University
DOI Pre-print