Ett nytt format för lagring av sparse matriser föreslås för effektiv sparse matris-vektorn (SpMV) produktberäkning på moderna grafik bearbetningsenheter (GPU). Detta format utökar standardformatet för komprimerad radlagring (CRS) och kan snabbt konverteras till och från det. Beräkningsprestanda för två SpMV-kärnor för det nya formatet bestäms för över 130 glesa matriser på Fermi-klass och Kepler-klass GPUs och jämförs med fem befintliga generiska algoritmer och industriella implementationer, inklusive Nvidia cuSparse CSR och HYB-kärnor. Vi hittade hastigheten på upp till 60 % över det bästa av de fem alternativa kärnorna. Nyckelord. SpMV, CRS-format, CSR-format, CUDA, hårdvaruacceleratorer AMS ämnesklassificeringar. 65F50, 65Y10 1. Inledning. Den sparse matris-vektorn (SpMV) multiplikation är en av de viktigaste kärnorna i vetenskapliga datorer med många program som sträcker sig från sparse linjära lösare till PageRank algoritm som används av Google i sin webb sökmotor. Dess höga bandbreddskrav i kombination med den dåliga datalokalitet som visas av typiska glesa matriser resulterar dock i dålig prestanda på processorer för allmänna ändamål som vanligtvis bara uppnår en liten bråkdel av sin toppprestanda i denna kärna. Den litteratur som ägnas åt SpMV-optimeringsteknik för traditionella, cachebaserade processordesigner är riklig (se [26] för en omfattande översikt), och för närvarande är en av de viktigaste frågorna hur man kan utnyttja nya funktioner som finns i multicore hårdvara. Flera SpMV optimeringsstrategier föreslogs redan för olika konstruktioner av chip multiprocessorer, inklusive flerkärniga centrala processenheter (CPU) från Intel och AMD [27], enkel-och dubbel-socket STI Cell [27], Sun UltraSPARC T2 [27], fältprogrammerbara gate arrays (FPGAs) [7, 8], Intel Xeon Phi coprocessors [14, 20], och grafik bearbetningsenheter (GPU) [1, 2, 4, 9, 11, 15, 17, 18, 23, 24, 28]. På bara några år har GPU utvecklats från fasta pipeline applikationsspecifika integrerade kretsar till mycket programmerbara, mångsidiga datorenheter med maximal beräkningsprestanda som matchar den av de mest kraftfulla superdatorer för bara ett decennium sedan. Dessa enheter kan programmeras på programmeringsspråk på hög nivå, t.ex. Nvidias C++ för CUDA (proprietär) eller OpenCL (öppen standard). Det största problemet i deras användning är programvara: varje ny maskinvaruarkitektur kommer att lyckas endast om lämplig programvara kan utvecklas för att utnyttja parallellismen i hårdvaran effektivt. De nuvarande multicorearkitekturerna är dock så olika och är föremål för så frekventa förändringar att för att utnyttja sin potential måste applikationerna vara mycket specialiserade och använda arkitekturspecifika optimeringsstrategier. Dessutom kräver massivt parallella arkitekturer, liksom den som används i moderna GPU:er, att använda ett nytt programmeringsparadigm, vilket i sin tur kräver en radikal omprövning av hur numeriska beräkningar ska utföras. Eftersom den stora majoriteten av den befintliga vetenskapliga programvaran följer "gamla" programmering paradigm, och sedan utveckling
Andra metoder för lagring av glesa data är komprimerad radlagring (CRS) eller komprimerad gles rad (CSR) mönster REF.
Compressed Multi-Row Storage Format for Sparse Matrices on Graphics Processing Units
{'venue': 'SIAM J. Sci. Comput. 36-2 (2014), pp. C219-C239', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics']}