Abstract-kommunikation-optimala algoritmer är kända för kvadratmatris multiplikation. Här får vi den första kommunikationsoptimala algoritmen för alla dimensioner av rektangulära matriser. Genom att kombinera den dimensionssplittrande tekniken av Frigo, Leiserson, Prokop och Ramachandran (1999) med den rekursiva BFS/DFS-metoden av Ballard, Demmel, Holtz, Lipshitz och Schwartz (2012) möjliggörs en kommunikationsoptimal samt cache- och nätverksobliviös algoritm. Dessutom är genomförandet enkelt: cirka 50 rader kod för den delade minnesversionen. Eftersom den nya algoritmen minimerar kommunikationen över nätverket, mellan NUMA-domäner och mellan nivåer av cache, fungerar den bra i praktiken på både delade och distribuerade minnesmaskiner. Vi visar betydande hastigheter över befintliga parallella linjära algebra bibliotek både på en 32-kärnig delad minnesmaskin och på en distribuerad-minne superdator.
Demmel m.fl. I REF föreslås en kommunikationseffektiv algoritm för alla dimensioner av rektangulära matriser, bortsett från kvadratiska matriser.
Communication-Optimal Parallel Recursive Rectangular Matrix Multiplication
{'venue': '2013 IEEE 27th International Symposium on Parallel and Distributed Processing', 'journal': '2013 IEEE 27th International Symposium on Parallel and Distributed Processing', 'mag_field_of_study': ['Computer Science']}