Parallella algoritmer för sparse matris-matris multiplikation brukar spendera större delen av sin tid på inter-processor kommunikation snarare än på beräkning, och hårdvarutrender förutsäga den relativa kostnaden för kommunikation kommer bara att öka. Således, sparsam matris multiplikationsalgoritmer måste minimera kommunikationskostnader för att skala till stora processor räkna. I detta dokument överväger vi att multiplicera glesa matriser som motsvarar Erdős-Rényi slumpmässiga grafer på distribuerade parallella maskiner. Vi visar en ny lägre gräns på den förväntade kommunikationskostnaden för en bred klass av algoritmer. Vår analys av befintliga algoritmer visar att, medan vissa är optimala för ett begränsat utbud av matris densitet och antal processorer, ingen är optimal i allmänhet. Vi får två nya parallella algoritmer och bevisar att de matchar den förväntade kommunikationskostnaden lägre gräns, och därmed är de optimala.
En enhetlig kommunikationsanalys av befintliga och nya algoritmer samt en optimal lägre gräns för kommunikationskostnader för två nya parallella algoritmer ges i REF.
Communication optimal parallel multiplication of sparse random matrices
{'venue': "SPAA '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}