Sharing is Hard: Paging problems for shared caches

Wednesday, November 4, 2026 - 4:00pm to 5:00pm

Location:

32-G449 (Kiva/Patil)

Speaker:

Kunal Agrawal (Washington University in St. Louis)

Biography:

Kunal Agrawal is a professor of Computer Science and Engineering at Washington University in St. Louis. She is interested in designing theoretically good and practically efficient algorithms particularly in the domain of parallel computing. In this context she works in diverse areas such as parallel programming runtime systems and tools, parallel algorithms and data structures, real-time scheduling and memory-efficient algorithms.

Seminar group:

Algorithms and Complexity Seminars

Memory hierarchies consist of fast and small caches in order to improve performance in the presence of the memory wall where access times to memory are substantially larger than the time it takes to compute. The classical paging problems asks: Which pages/blocks/cache lines should be keep in fast memory or cache? This problem has been studied for decades for sequential machines. However, memory hierarchies are changing due to the presence of parallelism as well as introduction of new memory technologies. In particular, in the presence of caches which are shared among various processors, the question arises: How should different processors share caches? This talk will present models and provably good algorithms for effectively sharing caches and high bandwidth memory between processors.