View Full Document

Graph Expansion and Communication Costs of Fast Matrix Multiplication



View the full content.
View Full Document
View Full Document

11 views

Unformatted text preview:

23rd ACM Symposium on Parallelism in Algorithms and Architectures San Jose California June 4 6 2011 Graph Expansion and Communication Costs of Fast Matrix Multiplication Oded Schwartz1 Joint work with Grey Ballard1 James Demmel1 Olga Holtz1 2 1 UC Berkeley 2 TU Berlin 1 Results by Grey Ballard UCB Aydin Buluc LBL Erin Carson UCB James Demmel UCB Jack Dongarra UTK Ioana Dumitriu U Washington Andrew Gearhart UCB Laura Grigori INRIA Ming Gu UCB Math Mark Hoemmen Sandia NL Olga Holtz UCB Math TU Berlin Nicholas Knight UCB Julien Langou U Colorado Denver Eran Rom IBM Tel Aviv Edgar Solomonik UCB Many others 2 Motivation Two kinds of costs Arithmetic FLOPs Communication moving data between levels of a memory hierarchy sequential case over a network connecting processors parallel case Communication avoiding algorithms Save time save energy Sequential Hierarchy CPU Cache M1 M2 Parallel CPU RAM CPU RAM CPU RAM CPU RAM M3 RAM Mk 3 Motivation expected bottleneck Annual hardware improvements Exponential growth with large gaps Graham Snir Patterson 04 Fuller Millett 10 CPU msec flop 59 DRAM Network Bandwidth msec word 23 26 Latency msec message 5 15 Sequential Hierarchy CPU Cache M1 M2 Parallel CPU RAM CPU RAM CPU RAM CPU RAM M3 RAM Mk 4 Outline Algorithms with flavor of 3 nested loops Lower bounds Sequential Hierarchy Parallel Ballard Demmel Holtz S 2009 Ballard Demmel Holtz S 2011a extending Hong Kung 81 Irony Toledo Tiskin 04 Algorithms Sequential Parallel Many contributions mostly new Strassen like algorithms Lower bounds Sequential Hierarchy Parallel This work Algorithms Sequential Parallel Ballard Demmel Holtz Rom S 2011 5 Lower bounds for algorithms with flavor of 3 nested loops Matrix Multiplication Hong Kung 81 Sequential n 3 M M Irony Toledo Tiskin 04 Sequential and parallel n 3 M M P 6 Lower bounds for algorithms with flavor of 3 nested loops Ballard Demmel Holtz S 2009 Ballard Demmel Holtz S 2011a Following Irony Toledo Tiskin 04 n 3 M M BLAS LU Cholesky LDLT and QR



Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Graph Expansion and Communication Costs of Fast Matrix Multiplication and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Graph Expansion and Communication Costs of Fast Matrix Multiplication and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?