Computer Science Colloquia
Friday, April 5, 2013
Grey Ballard
Host: Andrew Grimshaw
3:30 PM, Rice Hall, Room 130 (auditorium), followed by a reception in Rice Hall Fourth Floor Atrium (west end)
Avoiding Communication in Linear Algebra
ABSTRACT
As our computing capabilities grow, the size and complexity of
numerical simulations that today's computational scientists conduct
continue to increase. Ultimately, these simulations are limited either
by the sheer quantity of computation required by the simulation or by
the inability of the software employed to make effective use of the
hardware. The gap between the peak capabilities of the hardware and the
achieved performance of numerical simulations is caused in large part by
the high cost of communication, or movement of data, between processors
and throughout the memory hierarchy of a single processor.
As expected, much of this communication cannot be avoided when using
parallelism to solve our problems; however, many standard algorithms in
linear algebra move more data than necessary. I will discuss lower
bounds we have proved on the communication required by a wide class of
algorithms and whether standard approaches attain these bounds. In
several cases where gaps exist between algorithms and lower bounds, we
have developed new algorithms that communicate asymptotically less than
previous ones and outperform them on a variety of platforms. These
include algorithms for solving linear systems, least squares problems,
eigenvalue problems, and parallelization of Strassen's matrix
multiplication algorithm.
I'll talk about some open problems in this area, and I'll also discuss
the possibility of reducing both communication and computation in dense
linear algebra using algorithms that perform asymptotically fewer
floating point operations than Strassen's.
Bio: Grey Ballard is currently a PhD candidate at the University of
California at Berkeley, working in the Parallel Computing Laboratory.
His research interests include improving fundamental algorithms for
scientific computing. His work has been recognized by SIAM's Linear
Algebra Prize, by best paper awards at the ACM Symposium on Parallelism
in Algorithms and Architectures and the IEEE International Parallel and
Distributed Processing Symposium, and by the UC Berkeley C.V.
Ramamoorthy Distinguished Research Award.
*Mr. Ballard is a faculty candidate for the Department of Computer Science