Vi förbättrar prestandan hos sparse matris-vektorn multiplicera (SpMV) på moderna cache-baserade superskalar maskiner när matrisstrukturen består av flera, oregelbundet riktade rektangulära block. Matriser från finita element modellering program har ofta denna typ av struktur. Vår teknik delar upp matrisen, A, i en summa, A 1 + A 2 +. .. + A s, där varje term lagras i en ny datastruktur, oanpassat block komprimerad sparse rad (UBCSR) format. Den klassiska alternativa metoden att lagra A i ett block komprimerad sparse rad (BCSR) format ger begränsade prestanda vinster eftersom det innebär en särskild anpassning av matrisen non-noll struktur, vilket leder till extra arbete från uttryckligen stoppade nollor. Genom att kombinera delning och UBCSR minskar detta extra arbete samtidigt som de generellt lägre kraven på minne bandbredd och register-nivå tiling möjligheter BCSR. Med hjälp av applikationstestmatriser, visar vi empiriskt att speedups kan vara så hög som 2,1× över inte blockera alls, och så hög som 1,8× över den standard BCSR implementation som används i tidigare arbete. När prestandan inte förbättras kan split UBCSR fortfarande avsevärt minska matrislagringen. Genom omfattande experiment visar vi vidare att det empiriskt optimala antalet klyvningar s och blockstorleken för varje matristerm A i i i praktiken kommer att bero på matrisen och hårdvaruplattformen. Våra data lägger grunden för framtida utveckling av helt automatiserade metoder för att justera dessa parametrar.
Vuduc och Moon REF skriver sparse matris A som summan av flera matriser, som var och en lagras i en blockerad variant av CRS-format, med sin egen blockstorlek och justering av start nonzero.
Fast Sparse Matrix-Vector Multiplication by Exploiting Variable Block Structure
{'venue': 'HPCC', 'journal': None, 'mag_field_of_study': ['Computer Science']}