I detta arbete visar vi att den vanliga grafdelningsbaserade nedbrytningen av sparse matriser inte återspeglar det faktiska kravet på kommunikationsvolym för parallell matris-vektor multiplikation. Vi föreslår två beräkningshypergrafmodeller som undviker denna kritiska brist på grafmodellen. De föreslagna modellerna minskar nedbrytningsproblemen till det välkända problemet med partitionering av hypergrafer. Det nyligen föreslagna framgångsrika flernivåramverket utnyttjas för att utveckla ett multilevel hypergraph partitioningsverktyget PaToH för experimentell verifiering av våra föreslagna hypergrafmodeller. Experimentella resultat på ett brett spektrum av realistiska testmatriser bekräftar giltigheten hos de föreslagna hypergrafmodellerna. I nedbrytningen av testmatriserna resulterar hypergrafmodellerna med hjälp av PaToH och hMeTiS i upp till 63 % mindre kommunikationsvolym (30 %–38 % mindre i genomsnitt) än grafmodellen med MeTiS, medan PaToH endast är 1,3–2,3 gånger långsammare än MeTiS i genomsnitt. Index Terms-Sparse matriser, matris multiplikation, parallell bearbetning, matris sönderdelning, beräkningskurva modell, graf partitionering, beräknings hypergraph modell, hypergraph partitionering.
Hypergraph partitionering tillämpades först i sparse matris sönderdelning för parallella sparse matris-vektorn multiplikation av Ç atalyürek och Aykanat i REF.
Hypergraph-partitioning based decomposition for parallel sparse-matrix vector multiplication
{'venue': 'IEEE Transactions on Parallel and Distributed Systems', 'journal': None, 'mag_field_of_study': ['Computer Science']}