Discussion :

[ol9245]

Bonjour à tous,

J'ai un algo qui explore et modifie un tableau NxN (N de l'ordre de 1000 à 10000) de proche en proche à partir d'une case de départ quelconque. pseudocode ci-dessous :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
L = 1 ; % une ligne de départ quelconque
C = 1 ; % une colonne de départ quelconque
while 1
if (la case courante n'a plus de voisin à traiter)
    break
end
    cherche tous les voisins non traités de (L,C)
    modifie éventuellement ces voisins
    choisit un des voisins (L1, C1) pour continuer l'algo
    L = L1 ;
    C = C1 ;
end

Pour accélérer le traitement, Je veux exécuter 4 explorations du même tableau en parrallèle. Comme mentionné dans le pseudo-code, chaque exploration doit pouvoir lire et écrire dans le tableau.

Le code auquel je pense ressemblerait à ça :

Code :

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

1
2
3
4
5
6
parfor depart = 1:4
    [L, C] = case_de_depart (depart) ;
    while 1
        l'algo ci-dessus
    end
end

Matlab refuse.
je comprend un peu pourquoi (conflits entre lecture et écriture, etc.) en C, il faudrait utiliser des objets de synchronisation pour bloquer les parties du tableau en cours de lecture, par exemple.

j'ai déja prouvé que mon algo est adapté à ce type de parralélisation. La question n'est donc pas algorithmique, mais purement Matlabesque.

d'ou ma question : je peux faire une parrallélisation de ce genre avec Matlab (accessoirement, comment) ou bien j'oublie ?

[ol9245]

J'ai résumé le problème dans ce petit code :

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
% la fonction test_parfor tente de parcourir un même tableau par deux itératreurs parrallèles et concurrents.
% L'un part du haut, vers le bas. L'autre pars du bas, vers le haut.
% Lorsqu'ils se rejoignent, le traitement s'arrête.
% MATLAB refuse ce type de parrallélisation. Ce refus est bien documenté :
% ??? Error: File: test_parfor.m Line: 31 Column: 9
% The variable M in a parfor cannot be classified.
% See Parallel for Loops in MATLAB, "Overview".

% Ma question : comment implémenter dans Matlab ce type d'itérateurs multiples et concurrents ?
% Note : certainement pas avec un parfor puisque c'est écrit noir sur blanc que ce n'est pas possible. Alors comment ?

function test_parfor()
% le tableau à parcourir
M = rand(1, 1000) ;

% comment chaque thread va explorer le tableau M
start = [1, 1000] ;
stop = [1000, 1] ;
direction = [+1, -1] ;
threads = 2 ;
current = zeros(1, threads) ;

parfor t = 1:threads
    for u = start(t):direction(t):stop(t)
        current(t) = u ; % publie la position courante du thread courant
        switch t % détermine le numéro de "l'autre" thread
            case 1, autre = 2 ;
            case 2, autre = 1 ;
        end
        
        % termine le thread si l'autre a déja fini
        if u * direction(t) > current(autre) * direction (t) % si mon thread a dépassé l'autre
            break
        end
        
        % traite le nombre courant
        M(u) = touch (M, u) ;
    end
end
end

% un exemple rudimentaire de traitement d'une case
function X = touch (Table, index)
X = max(0.999, Table(index)) ;
end

[Jerome Briot]

Ne connaissant rien (ou presque) à cette toolbox, je ne vais pas pouvoir t'aider beaucoup.

Néanmoins, si tu possèdes une machine 64bits, tu devrais pouvoir dupliquer la matrice originale en une matrice NxNx4 (environ 3Go en 10000x10000x4) et lancer le PARFOR sur la 3ème dimension, non ?

Bien entendu, avec une machine 32bits, la limite de la méthode ci-dessus sera plus vite atteinte.

[ol9245]

Ne connaissant rien (ou presque) à cette toolbox, je ne vais pas pouvoir t'aider beaucoup.

Néanmoins, si tu possèdes une machine 64bits, tu devrais pouvoir dupliquer la matrice originale en une matrice NxNx4 (environ 3Go en 10000x10000x4) et lancer le PARFOR sur la 3ème dimension, non ?

Bien entendu, avec une machine 32bits, la limite de la méthode ci-dessus sera plus vite atteinte.

oui, j'ai une machine 64bits avec 8Gig de mémoire pour le développement.
Et j'ai accès à un cluster de 40 processeurs pour la production.

ta suggestion ne fonctionnera pas car les itérateurs modifient la matrice.
Les itérateurs se baladent dans la matrice de proche en proche selon un chemin qui dépend des calculs intermédiaires. Pour effectuer son calcul chaque itérateur doit avoir accès à la matrice la plus récente possible telle que calculée par ses petits copains pour ne pas se trouver dans la situation de recalculer une maille déja calculée ailleurs.

A la relecture de la doc de la toolbox, il semble bien que ce type de calcul est en effet exclu. Si pas de solution, je programmerai par dallage, en itérant la liste de dalles dans un parfor. C'est pas optimal, mais ça sera toujours mieux que du monotâche.

[Jean Dumoncel]

Bonjour,

A la relecture de la doc de la toolbox, il semble bien que ce type de calcul est en effet exclu.

effectivement, les calculs à chaque itération doivent être indépendants, ce qui ne semble pas être le cas pour ton programme.

[ol9245]

Bonjour,

effectivement, les calculs à chaque itération doivent être indépendants, ce qui ne semble pas être le cas pour ton programme.

ouep ouep...
Le gros os, c'est que le dallage est très loin d'être optimal dans le problème actuel.

En gros, j'ai un gros tas de pain sur la planche pour parralléliser ce problème sous Matlab