Abstrakt. I den här artikeln introducerar vi en cache-oblivious metod för sparse matris-vektor multiplikation. Vår metod försöker att permutera rader och kolumner i inmatningsmatrisen med hjälp av en rekursiv hypergraph-baserad sparse matris partitionering schema så att den resulterande matrisen inducerar cache-vänligt beteende under sparse matris-vektor multiplikation. Matriser antas lagras i rad-större format med hjälp av komprimerad radlagring (CRS) eller dess varianter av inkrementell CRS och sick-zag CRS. Datastrukturen zig-zag CRS visas passa bra med den hypergrafmetriska metod som används vid partitionering av glesa matriser för parallell beräkning. Formuläret för separat blockdiagonal (SBD) visas vara lämplig matrisstruktur för cacheförstärkning. Vi har implementerat ett cachesimuleringsbibliotek som gör det möjligt för oss att analysera cachebeteendet för godtyckliga matriser och godtyckliga cacheegenskaper under matris-vektorns multiplikation inom en k-way set-associativ idealiserad cachemodell. Resultaten av dessa simuleringar verifieras sedan genom faktiska experiment som körs på olika cachearkitekturer. I alla dessa experiment, använder vi Mondriaan sparse matris partitioner i endimensionellt läge. De besparingar i beräkningstiden som uppnås genom våra matrisomställningar når upp till 50 procent, i fallet med en stor länkmatris.
En mer praktisk algoritm använder sparse matris partitioneringsmetoder REF.
Cache-oblivious sparse matrix-vector multiplication by using sparse matrix partitioning methods
{'venue': 'SIAM Journal on Scientific Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}