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
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:
Visit our home page-   <>
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Hadas Heier   <>