Vi undersöker yttre produkt-parallell, inre produkt-parallell, och rad-för-rad-produkt-parallell formuleringar av sparse matris-matris multiplikation (SpGEMM) på distribuerade minnesarkitekturer. För var och en av dessa tre formuleringar föreslår vi en hypergrafmodell och en bipartitkurvamodell för fördelning av SpGEMM-beräkningar baserade på endimensionell (1D) partitionering av ingångsmatriser. Vi föreslår också en kommunikationshybridmodell för varje formulering för distribution av kommunikationsverksamhet. De beräkningsgraf- och hypergrafmodeller som antogs i den första fasen syftar till att minimera den totala meddelandevolymen och balansera beräkningsbelastningarna hos processorer, medan de kommunikationshypergrafmodeller som antogs i den andra fasen syftar till att minimera den totala meddelandemängden och balansera meddelandevolymbelastningarna hos processorer. Det vill säga, de beräkningsbaserade partitioneringsmodellerna minskar bandbreddskostnaden och kommunikationshypergrafmodellerna minskar latenskostnaden. Våra omfattande parallella experiment på upp till 2048 processorer för ett brett spektrum av realistiska SpGEMM instanser visar att även om den yttre produkt-parallell formulering skalor bättre, rad-för-rad-produkt-parallell formulering är mer livskraftig på grund av sin betydligt lägre partitionering overhead och konkurrenskraftig skalbarhet. För beräkningsmässiga partitioneringsmodeller visar våra experimentella resultat att de föreslagna bipartitgrafmodellerna är attraktiva alternativ till deras hypergrafmotsvarigheter på grund av deras lägre partitionering omkostnader. Slutligen visar vi att genom att minska latenskostnaden förutom bandbreddskostnaden genom att använda kommunikationshypergrafmodellerna kan den parallella SpGEMM-tiden förbättras ytterligare upp till 32 procent.  Vi anser att parallelliseringen av sparse matris-matris multiplikation (SpGEMM) av formen C = AB i en distribuerad inställning. Baserat på endimensionell (1D) partitionering av ingångsmatriserna A och B kan fyra parallella algoritmer utformas:
Mer nyligen föreslås hypergraf- och bipartitgrafmodeller i REF för yttre produkt-, inre produkt- och rad-för-rad-produkt-formuleringar av meddelande som passerar SpGEMM-algoritmer på distribuerade minnesarkitekturer.
Partitioning Models for Scaling Parallel Sparse Matrix-Matrix Multiplication
{'venue': 'TOPC', 'journal': None, 'mag_field_of_study': ['Computer Science']}