Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Cache-Adaptive Analysis
Speaker:Sam McCauley
coming from:Stony Brook University
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Tuesday, 23 February 2016
Duration:30 Minutes
Building:E1 4
I/O efficient algorithms perform a small number of accesses to external memory. These accesses can be a cost bottleneck for large-scale applications--repeatedly reading data from disk can take much more time than processing it. We analyze algorithms that are I/O-efficient on a cache whose size changes dynamically. This is important when several processes run on a machine simultaneously. While the physical cache stays the same size, each application needs to share its portion of the cache as others come and go. An algorithm is cache adaptive if it optimally takes advantage of these changes in memory.

Previous work showed that some cache-oblivious algorithms (which run efficiently without knowing cache parameters) perform well cache-adaptively. However, these results were limited to a small class of adaptive cache-oblivious algorithms. This left open the question: when exactly is a cache-oblivious algorithm also cache-adaptive (and when is it not)?

Our results give a toolbox for showing when a recursive cache-oblivious algorithm is cache-adaptive. We give a full characterization for a wide class of algorithms, and provide further techniques to analyze other recursive cache-oblivious algorithms. Applying our tools to known cache-oblivious algorithms gives the first examples of algorithms that are provably not cache adaptive, and a greatly expanded class of efficient cache-adaptive algorithms.

Our results are based on a charging argument, which bounds how much work a recursive algorithm does (or fails to do) as the cache size fluctuates adversarially.

(Joint work with Michael Bender, Erik Demaine, Roozbeh Ebrahimi, Jeremy Fineman, Golnaz Ghasemiesfeh, Andrea Lincoln, Rob Johnson, and Jayson Lynch)

Name(s):Mayank Goswami
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Mayank Goswami, 02/04/2016 06:52 PM
  • Mayank Goswami, 02/03/2016 10:18 PM
  • Christina Fries, 02/01/2016 10:05 AM
  • Mayank Goswami, 01/21/2016 05:26 PM -- Created document.