Multiplication matrice creuse – vecteur dense sur des corps finis ...

Sujets

• multiplication

Informations

• Publié par: abubidur
• Nombre de lectures: 312
• Langue: Français

Extrait

Multiplication matrice creuse – vecteur dense sur des corps finis pour architectures GPU et multicœurs. ∗ Brice Boyer 3 avril 2010

1 Introduction.e´emtne´ovsnmilpereefficacdemani`oitano’lere´pasuoN«Sparse Matrix-Vector multiplication»g´ebr´e(enaspmv) sur des corps. L’accent a surtout ´ete´missurdesanneauxdetypeZ/mZavecmplus petit qu’un mot machine. La raison de cet exercice est double. D’une part, les ordinateurs personnels oumˆemeportablescomportentdeplusenplusdecœurs,souventsous-utilis´es, ainsiquedescartesgraphiquesdeplusenplusperformantes,capablesd’ˆetrepro- gramm´eesassezfacilementpouruneutilisationpurementcalculatoire(Nvidia Cuda, Ati Stream, OpenCL). De plus, les cartes graphiques offrent des perfor- mancessup´erieures`aprixcomparable,d’ou`,enlesparall´elisant,uneutilisation possibleentantque“super-calculateur”pourcertainsproble`mes.D’autrepart, l’op´erationspmvenponautitnoe´ar´ettirosemhytedepbadedaselenslgsa«boˆıte noire»et.svssarte`odcnntsoieirraibelttecedsetceridsnoi3[)]l,setulisita([6],

G´en´eralite´ssurl’imple´mentation.aterndioLp´’obesaeetsy←Ax+y, permettantd’effectuerplusg´en´eralementl’op´erationy←αAx+βy. Nous > >> avonsaussibesoind’impl´ementerl’ope´rationtranspos´eey←αxA+βy. Pourcela,lorsquelame´moirelepermet,ilestenl’´etatbienplusefficace(parun ou deux ordres de grandeur) de transposerAet de se reporter au cas de base. L’op´erationY←AX+Y`u,oYsruetse,edcotcevstebluneel´ement´aussiimp carne´cessairedanslesalgorithmesparblocs([5]). Les formats qui servent de base au stockage des matrices sont COO (coordinate format), DIA (diagonal format), CSR (compressedstoragerow format), ELL (Elllonlessesoinesbeapkcid´fi,)omesd´eivalisansl]).Ds([7´dreamstfsroeted ces quatre formats de base figurent notamment ceux pour lesquels les matrices sontconstitue´esuniquementde1(oude−1). En effet, il n’est pas rare que des matrices issues de certaines applications soient riches en±1. On en trouve aussi probablementuneforteproportiondansdesmatricesge´ne´ralessurdepetits anneaux.L’inte´reˆtestalorsdouble:l’espaceme´moiredestin´eauxvaleursnon

∗ [e-mail]´sierblnoreeG,.evinU,KJL 1 https ://ljkforge.imag.fr/projects/ffspmvgpu/

1