Abstrakt. Generaliserad sparse matris-matris multiplikation (eller SpGEMM) är en viktig primitiv för många högpresterande graf algoritmer samt för vissa linjära lösare, såsom algebraic multigrid. Här visar vi att SpGEMM också ger effektiva algoritmer för allmän sparse-matris indexering i distribuerat minne, förutsatt att den underliggande SpGEMM implementationen är tillräckligt flexibel och skalbar. Vi visar att våra parallella SpGEMM-metoder, som använder tvådimensionella blockdatadistributioner med seriehypersparsekärnor, verkligen är mycket flexibla, skalbara och minneseffektiva i det allmänna fallet. Denna algoritm är den första att ge ökad hastighet på ett obegränsat antal processorer; våra experiment visar skalning upp till tusentals processorer i en mängd olika testscenarier. Nyckelord. Parallell beräkning, numerisk linjär algebra, sparse matris-matris multiplikation, SpGEMM, sparse matris indexering, sparse matris uppdrag, 2D data nedbrytning, hypersparsitet, graf algoritmer, sparse SUMMA, subgraph extraktion, graf sammandragning, graf batch uppdatering. AMS-ämnesklassificeringar. 05C50, 05C85, 65F50, 68W10 1. Inledning. Vi beskriver skalbara parallella implementationer av två glesa matriskärnor. Den första, SpGEMM, beräknar produkten av två glesa matriser över en allmän semiring. Den andra, SpRef, utför generaliserad indexering i en gles matris: Givna vektorer I och J i rad- och kolumnindex, SpRef extraherar submatris A(I, J). Vår nya strategi för SpRef använder SpGEMM som sin viktigaste subrutin, som legaliserar beräknings- och dataåtkomstmönstren; tvärtom, att tillämpa SpGEMM till SpRef betonar vikten av en SpGEMM implementation som hanterar godtyckliga matrisformer och sparbarhetsmönster, och en komplexitetsanalys som gäller för det allmänna fallet. Våra viktigaste bidrag i detta dokument är: för det första visar vi att SpGEMM leder till en enkel och effektiv implementering av SpRef; för det andra beskriver vi en distribuerad memory implementation av SpGEMM som är mer allmän i tillämpning och mer flexibel i processorlayout än tidigare; och för det tredje rapporterar vi om omfattande experiment med prestanda av SpGEMM och SpRef. Vi beskriver också en algoritm för sparse matris uppdrag (SpAsgn), och rapportera dess parallella prestanda. SpAsgn-operationen, formellt A(I, J) = B, tilldelar en sparsam matris till en submatris av en annan gles matris. Det kan användas för att utföra streaming batch uppdateringar till en graf. Parallella algoritmer för SpGEMM och SpRef samt deras teoretiska prestanda beskrivs i avsnitten 3 och 4. Vi presenterar den allmänna SpGEMM algoritmen och dess parallella komplexitet innan SpRef eftersom den senare använder SpGEMM som subrutin och dess analys använder resultat från SpGEMM-analysen. Avsnitt 3.1 sammanfattar våra tidigare resultat om komplexiteten hos olika SpGEMM-algoritmer på distribuerat minne. Avsnitt 3.3 presenterar vår algoritm av val, Sparse SUMMA, på ett mer formellt sätt än tidigare, inklusive en pseudokod general nog att hantera
Den distribuerade SpGEMM genomförande av HipMCL använder Sparse SUMMA algoritm REF.
Parallel Sparse Matrix-Matrix Multiplication and Indexing: Implementation and Experiments
{'venue': 'SIAM J. Sci. Comput., 34(4), 170 - 191, 2012', 'journal': None, 'mag_field_of_study': ['Computer Science']}