Abstract-Sparse matris-vektor och matris-transpose-vektor multiplikation (SpMM T V) upprepade gånger utförs som z A T x och y A z (eller y A w) för samma sparse matris A är en kärna operation allmänt används i olika iterativa lösare. En viktig optimering för serie SpMM T V är att återanvända A-matris nonzeros, vilket halverar kravet på minnesbandbredd. Dock kräver tråd-nivå parallellisering av SpMM T V som återanvänder A-matris nonzeros samtidiga skriver till samma utdata-vektor poster. Dessa samtidiga skriver kan hanteras på två sätt: via atomuppdateringar eller trådlokala temporära utdatavektorer som kommer att genomgå en reduktion operation, som båda inte är effektiva eller skalbara på processorer med många kärnor och komplicerade cache-sammanhållning protokoll. I detta arbete identifierar vi fem kvalitetskriterier för effektiv och skalbar tråd-nivå parallellisering av SpMM T V som använder endimensionell (1D) matrispartitionering. Vi föreslår också två lokala-medvetna 1D-partitioneringsmetoder, som uppnår återanvända A-matris nonzeros och mellanliggande z-vektor poster, utnyttja lokalitet för att få tillgång till x-, y- och z-vektor poster, och minska antalet samtidiga skriver till samma utdata-vektor poster. Dessa två metoder använder radvis och kolumnvis individuellt kantad blockdiagonal (SB) former av A. Vi utvärderar våra metoders giltighet på ett brett spektrum av glesa matriser. Experiment på 60-kärnig cache-sammanhängande Intel Xeon Phi-processor visar giltigheten av de identifierade kvalitetskriterierna och giltigheten av de föreslagna metoderna i praktiken. Resultaten visar också att prestandaförbättringen från återanvändning av A-matris nonzeros kompenserar för omkostnaderna för samtidiga skriver genom de föreslagna SB-baserade metoderna. Index Terms-Cache lokalisering, gles matris, gles matris-vektor multiplikation, matris omordning, ensam kantad block-diagonal form, Intel Många integrerade kärnarkitektur (Intel MIC), Intel Xeon Phi
För sparse matris-vektor och matris-transpose-vektor multiplikation (SpMMTV), som innehåller två på varandra följande SpMVs, Karsavuran et al. REF använder hypergrafmodeller för att utnyttja temporal lokalitet på Xeon Phi.
Locality-Aware Parallel Sparse Matrix-Vector and Matrix-Transpose-Vector Multiplication on Many-Core Processors
{'venue': 'IEEE Transactions on Parallel and Distributed Systems', 'journal': 'IEEE Transactions on Parallel and Distributed Systems', 'mag_field_of_study': ['Computer Science']}