Colloquium

Speaker Name: Volker Strumpen<

br>
Speaker Affiliation: IBM Research Austin

Date: November 30
2006

Start Time: 1:30p.m.

End Time: 2:30p.m.

Locat

ion: ACES 3.408

Host: Lorenzo Alvisi

Talk Title: Cache O

blivious Stencil Computations

Talk Abstract:
A stencil describe

s the computation of a grid point at time
step t+1
as a function of

neighboring grid points at time step t.
This
computational pattern a

rises frequently in scientific computing
for
example in explicit fi

nite-difference methods for solving differential
equations.

In th

is talk we discuss a novel algorithm for stencil computations
that appl

ies to arbitrary stencils in n-dimensional space.
On a
machine with

an %60%60ideal cache'''' of size Z for sufficiently large
problems the
algorithm computes M grid elements while incurring
O(M /
Z%5E%7B1/n

%7D) cache misses which matches the lower bound of
%5BHong and
Kung
1981%5D. The algorithm is %60%60cache oblivious:'''' it does
not cont

ain
the cache size Z as a parameter. We also present a cache
oblivi

ous
multithreaded version for parallel machines which is capable
of

amortizing communication latencies.

We applied our algorithms t

o several applications including
LBMHD a
hydrodynamics program from
the HPCC suite of DARPA benchmarks.
Our
cache oblivious sequential
version obtains a speedup of
7x with
respect to the original code.
The performance of our multithreaded
version demonstrates that the algo

rithm relieves the parallel
programmer from worrying about data distribu

tions and processor
locality. We conclude with a brief discussion of th

e potential
of
cache oblivious programs to exploit accelerators suc

h as
FPGA''s with
reasonable programming effort.

Joint work

with Matteo Frigo.

Speaker Bio:
Volker Strumpen is a Resea

rch Staff Member at IBM''s Austin
Research Laboratory. He received a Di

ploma in Electrical
Engineering
from RWTH Aachen and a PhD in Comput

er Science from ETH
Zurich in
1995. He served in various academic p

ositions at MIT Yale
University and the University of Iowa where he p

articipated
in
several research projects including Porch - the porta

ble checkpoint
compiler Cilk - an algorithmic multithreaded programming

language
and Raw - a single-chip 16-processor architecture. Earli

er
he
designed several award-winning systems for large-scale parall

el
distributed computing in workstation networks and the Internet.
Vo

lker helped starting up Akamai Technologies and built
the prototype

of the routing technology that led to Akamai spin-off Sockeye
Networks

which has been acquired by Internap. He also spent
some time
working
on semiconductor technology at Sony.