The Cache-Oblivious Gaussian Elimination Paradigm

Vijaya Ramachandran
University of Texas at Austin

Thursday, November 30 10:30AM ,
CIC 410, (Intel Research) ­ Hot Metal room

Abstract

A cache-oblivious algorithm is a system-independent cache-efficient algorithm that simultaneously adapt to all levels of a multi-level memory hierarchy.

In this talk we present the cache-oblivious Gaussian Elimination Paradigm (GEP), a cache-oblivious framework for problems solvable using a construct similar to the computation in Gaussian elimination without pivoting.

The traditional GEP code executes O(n3) operations and incurs O(n3 / B) I/Os (or transfers of memory blocks), where B is the block size. Our cache-oblivious version executes the same O(n3) operations but incurs only O(n3 / (B\sqrt{M})) I/Os, where M is the size of the cache.

We present two versions of cache-oblivious GEP: -- IGEP, which is in-place and applies to Gaussian elimination without pivoting, Floyd-Warshall's all-pairs shortest paths, and other important special cases of GEP, and -- CGEP, which is completely general and applies to all GEP problems, at the expense of using a modest amount of extra space.

Both IGEP and CGEP have potential application in optimizing compilers as cache-oblivious tiling techniques.

Our experimental results indicate that cache-oblivious GEP provides a fairly attractive trade-off between cache-efficiency and portability.

(This is joint work with Rezaul Alam Chowdhury.)