Tel-Aviv University - Computer Science Colloquium
Sunday, May 2, 14:15-15:15
at 14:00 Locality of reference is the ability of an algorithm to extensively use data that is stored close to the processor, rather than access data that is stored in distant memories (down the memory hierarchy or on other nodes in a distributed-memory parallel computer). Locality of reference is a key determinant of the performance of an algorithm on many computers. The talk will explain why locality is important, how it is related to parallelism, and how it can be introduced into an algorithm.
In the talk, I will survey the main paradigms for creating locality in numerical algorithms and illustrate them with several concrete examples from my research. I will start with an interesting and essentially optimal schedule for dense Gaussian elimination. I will then describe locality issues in sparse nonsymmetric Gaussian elimination. This is an on-going project. I will discuss the issue of locality in parallel algorithms by showing that conventional FFT algorithms move more data between processors than is necessary. I will show that an approximate discrete Fourier transform can transfer less data than is necessary for exact DFT's. I will also describe locality issues in sparse matrix vector multiplication.
The talk describes joint research with Alan Edelman, Peter McCorquodale, and John Gilbert.
For colloquium schedule, see http://www.math.tau.ac.il/~matias/colloq.html