Technion Computer Science Colloquium Time+Place : Sunday 11/11/2012 14:30 room 337-8 Taub Bld. Speaker : Oded Schwartz Affiliation: UC Berkeley Host : Johann Makowsky Title : Fast Parallel Matrix Multiplication Abstract : Faster algorithms can be obtained by minimizing communication. That is, reducing the amount of data sent across the memory hierarchy and between processors. The communication costs of algorithms, in terms of time or energy, are typically much higher than the arithmetic costs. We have computed lower bounds on these communication costs by analyzing geometric and expansion properties of the underlying computation graphs of algorithms. These techniques (honored by SIAG-LA prize for 2009-2011 and SPAA'11 best paper award) inspired many new algorithms, where existing ones proved not to be communication-optimal. Parallel matrix multiplication is one of the most studied fundamental problems in parallel computing. We obtain a new parallel algorithm based on Strassen's fast matrix multiplication that is communication-optimal. It exhibits perfect strong scaling, within the maximum possible range. The algorithm asymptotically outperforms all known parallel matrix multiplication algorithms, classical and Strassen-based. It also demonstrates significant speedups in practice, as benchmarked on several super-computers (Cray XT4, Cray XE6, and IBM BG/P). Our parallelization approach is simple to implement, and extends to other algorithms. Both the lower bounds and the new algorithms have an immediate impact on saving power and energy at the algorithmic level. Based on joint work with Grey Ballard, James Demmel, Olga Holtz, Ben Lipshitz Short Bio: Oded Schwartz is a postdoctoral researcher, working in the Parallel Computing Lab at UC Berkeley, with Prof. James Demmel (Math department and CS division) and Prof. Olga Holtz (Math department). He graduated with a PhD in Computer Science from Tel-Aviv University and spent two years at TU-Berlin, and a few months at the Weizmann Institute of Science. Oded's research includes parallel computing, algorithmic linear algebra, high performance computing, and accelerating algorithms by reducing communication costs. His work on analyzing the underlying computation graphs of algorithms brought better understanding of the communication costs of algorithms, as well as new parallel algorithms for matrix multiplication that outperform in practice all existing ones, gaining significant speedups (up to 2500x) over existing kernels in current libraries. His honors include the 2012 SIAG/LA Best Paper Prize (for the years 2009-2011), SPAA Best Paper Award (2011), and the Paul Viderman prize for Outstanding Teaching, Tel-Aviv University. Oded's papers and CV are available at: <http://www.cs.berkeley.edu/~odedsc/> ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>