Parallellmatrismultiplikation är ett av de mest studerade grundläggande problemen i distribuerade och högpresterande datorer. Vi får en ny parallellalgoritm som baseras på Strassens snabba matrismultiplikation och minimerar kommunikationen. Algoritmen överträffar alla kända parallella matrismultiplikationsalgoritmer, klassiska och Strassen-baserade, både asymptotiskt och i praktiken. En kritisk flaskhals i parallelliseringen Strassen algoritm är kommunikationen mellan processorer. Ballard, Demmel, Holtz och Schwartz (SPAA '11) bevisar lägre gränser för dessa kommunikationskostnader, med hjälp av expansionsegenskaper hos den underliggande beräkningskurvan. Vår algoritm matchar dessa nedre gränser, och det är kommunikation-optimalt. Den uppvisar perfekt stark skalning inom maximalt möjligt område. Benchmarking vår implementering på en Cray XT4, vi får speedups över klassiska och Strassen-baserade algoritmer som sträcker sig från 24% till 184% för en fast matris dimension * Forskning som stöds av Microsoft (Award #024263) och Intel (Award #024894) finansiering och genom att matcha finansiering av UC. Discovery (Award #DIG07-10227 Tillstånd att göra digitala eller hårda kopior av hela eller delar av detta arbete för personligt bruk eller klassrumsbruk beviljas utan avgift, förutsatt att kopior inte görs eller distribueras för vinst eller kommersiella fördelar och att kopior är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. För att kopiera på annat sätt, för att återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Vår parallelliseringsstrategi generaliserar till andra snabba matrismultiplikationsalgoritmer.
I REF beskrivs en parallell algoritm baserad på Strassens snabba matrismultiplikation, CommunicationUndvikande Parallel Strassen (CAPS).
Communication-optimal parallel algorithm for strassen's matrix multiplication
{'venue': "SPAA '12", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}