Prestanda hos parallella algoritmer för gles matrismatrismultiplikation bestäms vanligtvis av mängden kommunikation mellan processorer som utförs, vilket i sin tur beror på indatamatrisernas icke-nollstruktur. I detta dokument karakteriserar vi kommunikationskostnaden för en sparse matris-matris multiplikationsalgoritm i termer av storleken på en skärning av en tillhörande hypergraf som kodar beräkningen för en given input nonzero struktur. Att få en optimal algoritm motsvarar att lösa ett problem med partitionering av hypergrafer. Vår hypergraph modell generaliserar flera befintliga modeller för sparse matris-vektor multiplikation, och vi kan utnyttja hypergraf partitioner som utvecklats för den beräkning för att förbättra applikationsspecifika algoritmer för att multiplicera sparse matriser.
I REF Ballard m.fl. Beskriv en hypergraf-partitioneringsmetod för parallell gles matris-matris-multiplikation.
Brief Announcement: Hypergraph Partitioning for Parallel Sparse Matrix-Matrix Multiplication
{'venue': "SPAA '15", 'journal': None, 'mag_field_of_study': ['Computer Science']}