Discussion :

[ol9245]

Je teste la parrallel toolbox en vue d'une future utilisation possible.
L'idée est de couper une matrice à traiter en 4 dalles et de consacrer un 'worker' Matlab (un thread) à chacune des dalles.

Le test se fait selon le code suivant, qui lance successivement le test sans, puis avec la parrallélisation.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
matlabpool close
parrallelise_calcul_par_dalles
matlabpool open
parrallelise_calcul_par_dalles

Dans le détail, la matrice d'origine est d'abord coupée en 4 et les 4 morceaux stockés dans un tableau de 4 cellules. Chaque worker n'accède qu'à une seule cellule. Les résultats sont consolidés après la boucle parfor.

Mon problème : le gain de temps est dérisoire : 20% pour une matrice à trater de 10000 x 10000.

J'ai raté une marche ou cette toolbox ne sert à rien ?????

PS : pour ceux qui voudraient essayer mon code, il y a 3 fonctions à créer. Pour chacune, les commentaires sont faits de telle sorte que la fonction est 'publiable'. Ca facilite la lecture du code (file/publish..., juste après file/save as...)
------------------

ci-dessous les 3 fonctions nécessaires : l a fonction de calcul par dalle proprement dite, la fonction qui détermine les limites de chaque dalle, et la fonction d'exemple utilisée. ici : une version algorithmique pas très rapide de l'extraction de la racine carrée.

Fonction Fonction parrallelise_calcul_par_dalles

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
%% Fonction parrallelise_calcul_par_dalles
% Lance la fonction fun en parrallèle sur 4 dalles de la matrice d'entrée Minput
% Les dalles de calcul peuvent se chevaucher (paramètre facultatif chevauchement).
%
% *|Arguments|* : 
%
% *Minput* : matrice rectangulaire à traiter. 
%
% *fun* : la fonction à traiter. du style K = fun(M)
%
% *chevauchement* : scalaire : (facultatif, défaut = 0) : largeur de la bande commune à deux dalles consécutives. 
%
% *|Résultat|* : 
%
% *Moutput* : le résultat est la concaténation pure et simple des dallees résultat. (quelque soit la valeur de chevauchement).
%
%%
function Moutput = parrallelise_calcul_par_dalles(Minput, fun, chevauchement)
%% Partie I: tests
if nargin==0
    fprintf(1, 'Il y a actuellement %d workers.\n', matlabpool('size')) 
    n = 10000; 
    disp('preparation') ; 
    M = rand(n) ; 
    disp('calcul') ; 
    tic ; 
    M1 = parrallelise_calcul_par_dalles(M, @racine, 0) ; 
    disp(toc) ; 
    disp('vérification') ; 
    M2 = M1.^2 ; 
    Err = (M2 - M) ; 
    Errmax = max(abs(Err(:))) ;
    disp(Errmax)
    return
end
 
%% Partie II: Arguments facultatifs
if nargin==2
    chevauchement = 0 ;
end
 
%% Partie III: Vérifications des arguments
if any(size(Minput) < 4)
    throw(MException('parrallelise_calcul_par_dalles:IncorrectArgumentMinput', 'Matrix is too small to parrallelize'))
end
 
if ~isscalar(chevauchement)
    throw(MException('parrallelise_calcul_par_dalles:IncorrectArgumentChevauchement', 'chevauchement must be a scalar'))
end
 
if ~isa(fun, 'function_handle')
    throw(MException('parrallelise_calcul_par_dalles:IncorrectArgumentFun', 'fun must be a function handle'))
end
 
%% Partie IV: Code de la fonction
% Calcule les dalles
fprintf(1, '%g dimentionnement\n', toc) ;
[dl, dc, fl, fc] = limites_des_dalles(size(Minput), chevauchement) ;
 
% tronçonne les dalles dans des tableaux de cellule
fprintf(1, '%g tronçonage\n', toc) ;
Min = cell(1, 4) ;
Mout = cell(1, 4) ;
for t = 1:4
    Min{t} = Minput(dl(t):fl(t), dc(t):fc(t)) ;
end
 
% calcule chaque dalle
fprintf(1, '%g calcul\n', toc) ;
parfor t = 1:4
    fprintf(1, 'worker n°%d traite M(%d:%d, %d:%d)\n', t, dl(t), fl(t), dc(t), fc(t))
    Mout{t} = fun ( Min{t} ) ;
    fprintf(1, 'worker n°%d a fini\n', t)
end
 
% consolide les sorties
fprintf(1, '%g consolidation\n', toc) ;
Moutput = [Mout{1} , Mout{3} ; Mout{4}, Mout{2}] ;

Fonction limites_des_dalles

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
%% Fonction limites_des_dalles
% Calcule la manière de couper une matrice en 4 dalles de même taille.
% Les dalles finales peuvent se chevaucher (paramètre facultatif chevauchement).
%
% *|Arguments|* : 
%
% *taille* : matrice 1 ligner x 2 colonnes : la taille de la matrice à découper, telle que donnée par la fonction size().
%
% *chevauchement* : scalaire : (facultatif, défaut = 0) : largeur de la bande commune à deux dalles consécutives. 
%
% *|Résultat|* : 
%
% *dl, dc, fl, fc* : Les lignes (l) et les colonnes (c) des points de départ (d) et de fin (f) des 4 dalles.  
% Tous les résultats sont des vecteurs lignes de 4 valeurs : une pour chaque dalle.
%
% *|Remarque|* : la fonction limites_des_dalles est un helper pour lancer une boucle parfor de 4 process sur une grosse matrice.
%
%%
function [dl, dc, fl, fc] = limites_des_dalles(taille, chevauchement)
%% Partie I: tests
if nargin==0
    [dl, dc, fl, fc] = limites_des_dalles([4, 4]) ;
    assert (all([dl, dc, fl, fc] == [1 3 1 3,  1 3 3 1, 2 4 2 4, 2 4 4 2])) ;
    [dl, dc, fl, fc] = limites_des_dalles([4, 4], 1) ;
    assert (all([dl, dc, fl, fc] == [1 2 1 2,  1 2 2 1, 2 4 2 4, 2 4 4 2])) ;
    return
end
 
%% Partie II: Arguments facultatifs
if nargin==1
    chevauchement = 0 ;
end
 
%% Partie III: Vérifications des arguments
if any(size(taille) ~= [1, 2])
    throw(MException('limites_des_dalles:IncorrectArgumentTaille', 'taille must be a 2-element row vector, as returned by finction size for a matrix.'))
end
 
if ~isscalar(chevauchement)
    throw(MException('limites_des_dalles:IncorrectArgumentChevauchement', 'chevauchement must be a scalar'))
end
 
%% Partie IV: Code de la fonction
s4 = taille ; % fin
moins = round (chevauchement/2) ;
plus = chevauchement - moins ;
s2 = round(s4 / 2) ; % milieu
s3 = s2+1 - moins ; % milieu : début de dalle
s2 = s2 + plus ; % milieu : fin de dalle
s1 = [1, 1] ; % départ
s = [s1 ; s2 ; s3 ; s4] ; % Les limites des dalles sur la diagonale principale
t = [s(:, 1), [s(3:4, 2) ; s(1:2, 2)]] ; % Les limites des dalles sur l'anti-diagonale
lims = [s ; t] ;
dep = lims(1:2:end, :) ;
fin = lims(2:2:end, :) ;
dl = max(1, dep(:,1).') ;
dc = max(1, dep(:,2).') ;
fl = min(taille(1), fin(:,1).') ;
fc = min(taille(2), fin(:,2).') ;
end

Fonction racine (une version lente de l'extraction de la racine carrée)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
function R = racine(C)
R = ones(size(C)) ;
for k=1:numel(C)
    c = C(k) ;
    r = R(k) ;
    err = 1 ;
    while err > 1e-10
        u = c/r ;
        r = 0.5 * (r + u) ;
        err = abs(r-u) ;
    end
    R(k) = r ;
end

[nablovic]

bonjour si tu travaille sur ta machine en local donc utilise matlabpool local est donne le nombre de coeur que tu as , pour plus d'info consulte dividing matlab comutations into tasks

[ol9245]

Merci++ de ta réponse.

J'ai 4 pools matlab (sur mon ordi : un core I7, donc 4 double-couers, mais Matlab n'utilises pas les 8, seulement 4).

J'ai regardé rapidement le lien fourni. cette logique me plait car elle correspond plus à ce que je connais du multithread en C : définir les threads, les lancer, attendre qu'ils soient tous finis, et consolider les résultats.

Par contre, ils ne semblent pas du tout utiliser l'instruction parfor. Est-ce que c'est la manière générale de procéder ? Est-ce que parfor a une utilité spécifique qui ne convient pas à ce que je veux faire ?

Merci encore de tes réponses : j'ai du mal à trouver une doc synthétique là-dessus sur Internet.

J'ajoute que je prototype le mutitâche sur ma machine en local et que l'exploitation du code se fera sur un cluster.

[nablovic]

salut old 9245 désolé de te répondre tardivement car j'ai pu expérimenter la toolbox parallel computing sur un système réel, donc j'ai fait du parallélisme rien en utilisant parfor donc pour parfor il faut que les itérations doivent etre indépendantes entre elles .

[ol9245]

salut old 9245 désolé de te répondre tardivement car j'ai pu expérimenter la toolbox parallel computing sur un système réel, donc j'ai fait du parallélisme rien en utilisant parfor donc pour parfor il faut que les itérations doivent etre indépendantes entre elles .

Merci de ton passage.
C'est bien ce que j'ai fait : rendre mes tâches indépendantes.
J'ai découpé mon gros tableau de données en 4 dalles.
chaque dalle est stockée dans une cellule d'un tableau de cellules.
le parfor est lancé sur les cellules du tableau et la consolidation des données se fait après. Il n'y a donc aucune donnée commune entre deux workers.

je constate bien une accélération du travail (+20%) mais c'est dérisoire. Ce que j'attendais c'est plutôt +380% (=+400% - le côut de construction des dalles et leur consolidation).

[Jerome Briot]

Je déterre un peu le sujet mais j'ai lu pas mal d'articles et de livres ces derniers temps et,
je m’interroge sur ta méthodologie.

Par contre, n'ayant pas accès à la Parallel Computing Toolbox, j'avoue que je connais mal les spécificité de cette Toolbox...

Pourquoi ne demandes-tu que 4 itérations à PARFOR ?
Une matrice 10000x10000 prend environ 763Mo de mémoire (en classe Double).
Si on la divise "seulement" par 4, chaque sous-matrice prends donc 190Mo de mémoire.
Je pense que cela doit créer un certain embouteillage au niveau des accès mémoire pour chaque cœur de calcul.

As-tu essayé en découpant la matrice en blocs plus petits ?
Voire en blocs vraiment plus petits qui pourraient être stockés en cache ?

Et au final, ne serait-ce pas plutôt un travail pour SPMD plutôt que pour PARFOR ?

[ol9245]

Je déterre un peu le sujet mais j'ai lu pas mal d'articles et de livres ces derniers temps et,
je m’interroge sur ta méthodologie.

Merci pour ce déterrage !

Par contre, n'ayant pas accès à la Parallel Computing Toolbox, j'avoue que je connais mal les spécificité de cette Toolbox...

Pourquoi ne demandes-tu que 4 itérations à PARFOR ?
Une matrice 10000x10000 prend environ 763Mo de mémoire (en classe Double).
Si on la divise "seulement" par 4, chaque sous-matrice prends donc 190Mo de mémoire.
Je pense que cela doit créer un certain embouteillage au niveau des accès mémoire pour chaque cœur de calcul.

Le travail auquel je pensais c'est de traiter le MNT (champ d'altitude) d'un pays entier au pas de 30 mètres (données du satellite ASTER). Ces données sont fournies sur des dalles de 1 degré carré. donc des dalles de 3600 x 3600. L'idée est de traiter chaque dalle sur un processeur.

J'ai fait une boucle de 4 pour tester sur un quadri-coeur.

As-tu essayé en découpant la matrice en blocs plus petits ?
Voire en blocs vraiment plus petits qui pourraient être stockés en cache ?

Je crois pas que ça soit l'idée. De toutes façons, comme les threads sont tous lancés en même temps, la charge mémoire reste la même : il faut que tout le chantier rentre en mémoire. Sur un cluster, ça sera la même chose. En tous cas les 763 Mo c'est un pet de lapin (j'ai 32 Go sur mon portable ).

Et au final, ne serait-ce pas plutôt un travail pour SPMD plutôt que pour PARFOR ?

Peut-être. je ne sais pas. La doc de SPMD et les exemples me confortent dans l'idée que je m'était faite après cet essai : la parrallel toolbox est vraiment dédiée cluster. C'est pas une bonne idée de la déployer sur un ordi mono-processeur, même si ce processeur est multi-coeur.

De plus, je ne vois nulle part de processus de synchronisation pour le multithreading. Comment bloquer de la mémoire quand on écrit dedans ? etc. Quand je faisais de la programmation multi-tâche, ces processus étaient vraiment indispensable : je demande l'accès à un espace mémoire prédéfini (un tableau) qui est muni d'objets de synchronisation (des portes) > quand j'ai la main je ferme la porte (accès réservé à moi seul) > je lit la valeur > je la traite > j'écris le résultat > je ré-ouvre la porte.

A chaque frontière de mes dalles d'un degré carré, j'aurais de toutes façon des questions de synchronisation à me poser. Apparemment, Matlab non seulement ne fournit pas les outils, mais interdit carrément l'implémentation de boucles parfor si les données risquent d'être inter-visibles d'un thread à l'autre.

En gros, je trouve cette toolbox assez limitée.
Je voulais confronter cette impression à l'avis de ceux qui l'utilisent.

[Jerome Briot]

Il est vrai que la documentation n'est pas très explicite sur certains points.

Je crois pas que ça soit l'idée. De toutes façons, comme les threads sont tous lancés en même temps, la charge mémoire reste la même : il faut que tout le chantier rentre en mémoire. Sur un cluster, ça sera la même chose. En tous cas les 763 Mo c'est un pet de lapin (j'ai 32 Go sur mon portable ).

Je parlais plutôt de faire correspondre la taille des données à la taille du cache de chaque cœur (chaque sous-matrice) ou au moins au cache L3 (4 sous-matrice) de ton processeur pour réduire les temps d'accès.

As-tu essayé de limiter le calcul à 2 ou 3 cœurs plutôt que 4 ?

Je serais franchement curieux de voir un petit benchmark pour voir le comportement de cette Toolbox

Désolé de rester un peu théorique mais c'est trop tard cette année pour commander la Toolbox au Père Noël

[ol9245]

je pense que ça serait +/- pareil parceque même en piochant dans une grande dalle, chaque coeur va se débrouiller comme il veut pour utiliser son cache à lui. Et de toutes manières, l'heuristique de gestion du cache doit être certainement assez sophistiqué et donc il est difficile d'anticiper ce que le proc va mettre dedans selon les conditions du calcul et l'age du capitaine.

Dans le cas particulier de mon problème, comme j'ai des soucis de synchronisation à la frontière des dalles, l'idée était de traiter des dalles les plus grandes possibles en multi-tâche, d'attendre que toutes les dalles soient finies localement, de synchroniser les frontières en mono-tâche et de reboucler.