Locality Theory 101 -- The Foundation of Fast Code

Monday, December 15, 2025 @ 4PM ET

Chen Ding, University of Rochester

Abstract

Computer memory is not uniform but hierarchical, and the fast memory on most machines today is dynamically managed and shared as caches. The field of locality research is concerned with the analysis and optimization of the memory hierarchy. Poor locality may manifest in three forms: (1) too many cache misses, (2) incomplete temporal or spatial reuse, or (3) too large working sets.

This talk will give an overview of the modern memory hierarchy and then present the Relational Theory of Locality [PACT 2013, ASPLOS 2013, TACO 2019]. It formalizes three types of measures—data movement, reuse, and working set—as mathematical and statistical functions. The key insight is that these functions are mutually convertible and therefore equivalent. This decouples analysis from action: a Fast Coder may diagnose a problem using one measure and optimize it targeting another, free to choose the right tool for the job.

Recording

https://mit.zoom.us/rec/share/afk2752q_G8r7SF9AcTp7XJku3L36-9UTWUSHy_R4L_jK2-pPprDEc0jjbU7RMk0.IsYguFPVZ_tkILWa

Bio

Chen Ding is a full professor and Chair of the Computer Science Department at the University of Rochester. His work received the Young Investigator Award from the US Department of Energy and the CAREER Award from NSF. He held visiting positions at Microsoft Research and MIT and is currently a member of the organizing committee of the International Symposium on Memory Systems (MEMSYS) and ACM International Conference on Supercomputing (ICS).