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 and I/O-Efficient Functional Algorithms
Speaker:Robert Harper
coming from:Carnegie-Mellon University
Speakers Bio:External Scientific Member, MPI-SWS

Event Type:MPI Colloquium Series Distinguished Speaker
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Wednesday, 22 August 2012
Duration:60 Minutes
Building:E1 4 - MPI-INF
The widely studied I/O and ideal-cache models were developed
to account for the large difference in costs to access memory at
different levels of the memory hierarchy. Both models are based on
a two level memory hierarchy with a fixed size primary memory
(cache) of size M, an unbounded secondary memory, and assume
unit cost for transferring blocks of size B between the two. Many
algorithms have been analyzed in these models and indeed these
models predict the relative performance of algorithms much more
accurately than the standard RAM model. The models, however,
require specifying algorithms at a very low level requiring the user
to carefully lay out their data in arrays in memory and manage their
own memory allocation.
In this paper we present a cost model for analyzing the memory
efficiency of algorithms expressed in a simple functional language.
We show how many algorithms written in standard forms using
just lists and trees (no arrays) and requiring no explicit memory
layout or memory management are efficient in the model. We then
describe an implementation of the language and show provable
bounds for mapping the cost in our model to the cost in the idealcache
model. These bound imply that purely functional programs
based on lists and trees with no special attention to any details
of memory layout can be as asymptotically as efficient as the
carefully designed imperative I/O efficient algorithms. For example
we describe an O( n
B logM=B
B ) cost sorting algorithm, which is
optimal in the ideal cache and I/O models.
Categories and Subject Descriptors D.3.1 [
Name(s):Kurt Mehlhorn
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Created by:Kurt Mehlhorn/AG1/MPII/DE, 08/06/2012 04:25 PMLast modified by:Uwe Brahm/MPII/DE, 08/22/2012 06:00 AM
  • Kurt Mehlhorn, 08/09/2012 11:35 AM
  • Kurt Mehlhorn, 08/06/2012 04:26 PM
  • Kurt Mehlhorn, 08/06/2012 04:25 PM -- Created document.