J'effectue plusieurs multiplications matricielles d'une matrice NXN Sparse (~ 1-2%), appelons-la b, avec une matrice dense NXM, appelons-la a (où m Nous pouvons vérifier que la multithreading n'a aucun effet pour les opérations de matrice clairsemé par le code suivant: Ceci produit la sortie suivante, qui illustre qu'il y a Aucune différence entre utilisation de 1, 2 et 4 threads pour les opérations clairsemées: si, d'autre part, je remplace b par sa forme dense, appelée bf ci-dessus , Je reçois une vitesse significative: (illustrant que les opérations matricielles pour les matrices denses dans MATLAB sont certes implicitement parallélizées) donc, ma question: y a-t-il Toute façon d'accéder à une version parallèle / filetée des opérations matricielles pour les matrices clairsemées (dans Matlab) sans la convertir en une forme dense?
J'ai trouvé un ancien Suggestion impliquant des fichiers .mex à Mathworks , mais il semble que le Les liens sont morts et pas très bien documentés / pas de commentaires? Toute alternative? Il semble s'agir d'une restriction assez sévère de la fonctionnalité de parallélisme implicite, car les matrices clairsemées sont abondantes dans des problèmes de courte durée et des fonctionnalités hyperthreadées hautement souhaitables dans ces cas.
3 Réponses :
sur Matlab Central La même question a été posée et cette réponse a été donnée:
I believe the sparse matrix code is implemented by a few specialized TMW engineers rather than an external library like BLAS/LAPACK/LINPACK/etc...
MATLAB utilise déjà SuitsParse par Tim Davis pour beaucoup de son fonctionnement sur des matrices clairsemées (par exemple Voir ici ), mais aucune des identiques n'est multipliée. < / p>
Les calculs habituellement sur des matrices rares sont liés à la mémoire plutôt que sur la CPU. Donc, même si vous utilisez une bibliothèque multithreadie, je doute que vous verrez d'énormes avantages en termes de performance, du moins pas comparables à ceux spécialisés dans des matrices denses ...
Après tout ce que le conception de matrices rares a des objectifs différents à l'esprit que des matrices denses régulières , où le stockage de la mémoire efficace est souvent plus important.
J'ai fait un rapide Recherchez en ligne et a trouvé quelques implémentations là-bas:
Les bibliothèques prises en charge des matrices clairsemées ne prennent pas nécessairement en charge la multiplication multithreadée des matrices clairsemées.
@Daniyar: Peut-être pas les implémentations de référence, mais les optimisées comme celles de Intel MKL sont multiples pour les routines denses et clairsemées: logiciel.intel.com/en-us/articles/... . Note de mentionner les bibliothèques GPU qui sont intrinsèquement parallèles.
@Daniyar: À propos, MATLAB dispose de la prise en charge des matrices clairsemées parallèles dans Mémoire distribuée scénarios (Par opposition à des multi-threads de mémoire partagée) avec la boîte à outils de calcul parallèle Mathworks.com/ HELP / DISTCOMP / SPARSE.HTML . Ceci est basé sur Bibliothèque Scalapack .
Le calcul parallèle n'autorise-t-il pas la multithreading s'il est utilisé sur un seul ordinateur? (Comme je l'ai suggéré dans ma réponse)
@Dennisjaharuddin: quelle implémentation parlez-vous? Intel MKL, alors oui. Mais Matlab n'utilise pas les routines rares de MKL, plutôt de la bibliothèque de SuiteParse. Quant à la boîte à outils PCT Distribué des tableaux , celles-ci sont parallélisées avec des multi-processus non multi-threads (penser MPI )
Je suis clairement hors de ma profondeur car je ne connais pas la moitié des mots de votre réponse !! Ma ligne de pensée: Par Porfor tente de calculer les choses en parallèle, si vous avez simplement 1 ordinateur, j'ai supposé que cela entraînerait l'utilisation de threads multiples. Je suppose que ce sont en fait de multiples processus, mais je pense que cela ne devrait pas avoir d'importance que j'ai suggéré de faire a * b parallèlement à c * d où il n'y a pas de chevauchement de mémoire .
@Dennisjaharuddin: Paracor sera exécuté en parallèle (avec plusieurs processus d'arrière-plan localement ou même sur un cluster d'ordinateur distant) lorsque vous avez des itérations de boucle indépendantes, mais il ne peut pas diviser une matrice dans une expression à l'intérieur du bloc de boucle . Si vous voulez ce genre de parallélisme, vous devrez utiliser explicitement distribué tableaux: mathworks.com/help/distCompc/distributed-Arrays-and-spmd.html
@Dennisjaharuddin: Si vous êtes intéressé à voir un exemple, j'ai répondu à une question dans le passé en utilisant smpd avec différents types de tableaux "distribués" de la boîte à outils PCT: Stackoverflow.com/a/21130157/97160
J'ai fini par écrire mon propre fichier MEX avec OpenMP pour Multhreading. Code comme suit. N'oubliez pas d'utiliser -LargeArrayDims et / openmp (OpenMP (ou -Fopenmp) des drapeaux lors de la compilation.
#include <omp.h>
#include "mex.h"
#include "matrix.h"
#define ll long long
void omp_smm(double* A, double*B, double* C, ll m, ll p, ll n, ll* irs, ll* jcs)
{
for (ll j=0; j<p; ++j)
{
ll istart = jcs[j];
ll iend = jcs[j+1];
#pragma omp parallel for
for (ll ii=istart; ii<iend; ++ii)
{
ll i = irs[ii];
double aa = A[ii];
for (ll k=0; k<n; ++k)
{
C[i+k*m] += B[j+k*p]*aa;
}
}
}
}
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[])
{
double *A, *B, *C; /* pointers to input & output matrices*/
size_t m,n,p; /* matrix dimensions */
A = mxGetPr(prhs[0]); /* first sparse matrix */
B = mxGetPr(prhs[1]); /* second full matrix */
mwIndex * irs = mxGetIr(prhs[0]);
mwIndex * jcs = mxGetJc(prhs[0]);
m = mxGetM(prhs[0]);
p = mxGetN(prhs[0]);
n = mxGetN(prhs[1]);
/* create output matrix C */
plhs[0] = mxCreateDoubleMatrix(m, n, mxREAL);
C = mxGetPr(plhs[0]);
omp_smm(A,B,C, m, p, n, (ll*)irs, (ll*)jcs);
}
+ 1 pour fournir le code, même si ce algorithme naïf est inefficace, avec une course cube Temps O (m * p * n) . Il serait intéressant de voir comment cela se compare à la mise en œuvre optimisée (et multithread) dans Intel MKL, à savoir la routine: MKL_DCSRMM (produit Matrix-matrix C = A * B avec A Matrice de nettoyage général du format CSR et B et C matrices denses)
@Amro C'est naïf, car il utilise la structure de données de Matlab. La version non naïve peut fonctionner mieux, mais cela dépend de la starsity de la matrice.
@Daniyar pourriez-vous inclure une référence? De préférence, on montrent un cas typique où cela est plus rapide et où la fonctionnalité de base est plus rapide?
@Dennisjaharuddin Cela devrait être au moins aussi rapide que la multiplication MATLAB par défaut juste à cause de la multi-threading.
@Daniyar Peut-être que ça devrait être ', mais ce serait bien de voir que c'est vraiment (et combien de fois).
mathworks.com/help/matlab/math/sparse-matrix- opérations.html et mathworks.com/matlabentral/answers/...
@Yvon dans les liens Je vois une description générale de la façon dont les choses fonctionnent, mais je ne peux pas dire comment il est pertinent pour la question.
Juste une coupelle idiote: cela aide-t-il à faire la matrice complète de la matrice?
@Dennisjaharuddin Il aide en termes d'enregistrement, mais il n'est pas pratique en termes de mémoire. C'est la raison de la question.
@Daniyar Les informations que M était grande était grande était cachée par un problème de formatage, a modifié la question de résoudre ce problème. - Néanmoins, allant du plein à plat ne doit que rendre la matrice deux fois plus grande à stocker, donc à moins que vous n'êtes proche de la limite de mémoire, il s'agisse d'une approche intéressante.
@Dennisjaharuddin J'ai un problème très similaire, mais pour moi, la dense est de 1000 fois de plus que peuplement, et pas possible du tout. :(
@Daniyar, j'ai suggéré d'aller de dense à graver, plutôt que de se débattre à dense. Je ne sais pas si cela vous aidera, mais au moins, vous multipliez deux matrices du même type.
@ Dennisjaheruddin Oh. Même problème cependant.
Avez-vous essayé SuitSesparse ? En C, il y a aussi Csparse .