External Scientific Member, MPI-SWS

http://www.cs.cmu.edu/~rwh/

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

Public Audience

English

60 Minutes

Saarbrücken

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
n
B ) cost sorting algorithm, which is
optimal in the ideal cache and I/O models.
Categories and Subject Descriptors D.3.1 [

Kurt Mehlhorn

--email hidden

passcode not visible

logged in users only