Computer Science Colloquia
Friday, April 5, 2013
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
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