Paralléliser ou vectoriser tous contre toutes les opérations sur un grand nombre de matrices?

Question

I ai environ 5000 matrices ayant le même nombre de rangées et un nombre variable de colonnes (20 x ~ 200). Chacune de ces matrices doit être comparé à tous les autres dans un algorithme de programmation dynamique.

cette question , j'ai demandé comment effectuer la comparaison rapide et a reçu une excellente réponse impliquant une convolution 2D. En série, en appliquant cette méthode itérative, comme ceci

list = who('data_matrix_prefix*')
H = cell(numel(list),numel(list));  
for i=1:numel(list)
    for j=1:numel(list)
        if i ~= j
            eval([ 'H{i,j} = compare(' char(list(i)) ',' char(list(j)) ');']);
        end
    end
end

est rapide pour les petits sous-ensembles de données (par exemple, pour 9 matrices, 9 * 9 - 9 = 72 appels sont effectués en 1 ~ s, 870 appels à ~ 2,5 s).
Cependant, fonctionnant sur toutes les données nécessite près de 25 millions d'appels.
J'ai aussi essayé d'utiliser beaucoup () pour un réseau de cellules entièrement composé de l'élément suivant des données, pour que je puisse utiliser cellfun () dans une seule boucle:

# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data.
nextData = cell(k,1);
for i=1:k
    [nextData{:}] = deal(data{i});
    H{:,i} = cellfun(@compare,data,nextData,'UniformOutput',false);
end

Malheureusement, ce n'est pas vraiment plus vite, parce que tout le temps est à comparer (). Ces deux exemples de code semblent mal adaptés pour la parallélisation. Je vais avoir du mal à comprendre comment faire mes variables coupées en tranches.
comparer () est totalement vectorisée; il utilise la multiplication de matrices et conv2 () exclusivement (je suis sous l'impression que toutes ces opérations, y compris le cellfun (), devrait être multithread dans Matlab?).

Quelqu'un voit-il une solution parallélisée (explicitement) ou mieux vectorisation du problème?

Remarque Je me rends compte que mes deux exemples sont inefficaces - la première serait deux fois plus vite si elle calcule une matrice de cellules triangulaires, et le second calcule toujours les comparaisons de soi, aussi bien. Mais le gain de temps pour une bonne parallélisation sont plus comme un facteur de 16 (ou 72 si j'installe Matlab sur les machines de tout le monde).

Mis Il y a aussi un problème de mémoire. J'ai utilisé deux evals pour ajouter chaque colonne de H dans un fichier, avec des noms tels que H1, H2, etc., puis clair H _i . Malheureusement, les sauvegardes sont très lentes ...

Answer 1

Le second exemple peut être facilement coupé en tranches pour une utilisation avec la boîte à outils Parallel Processing. Cette boîte à outils distribue des itérations de votre code parmi jusqu'à 8 processeurs différents locaux. Si vous voulez exécuter le code sur un cluster, vous avez également besoin de la Distributed Computing Toolbox.

%# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data.

parfor i=1:k-1 %# this will run the loop in parallel with the parallel processing toolbox
    %# only make the necessary comparisons
    H{i+1:k,i} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false);

    %# if the above doesn't work, try this
    hSlice = cell(k,1);
    hSlice{i+1:k} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false);
    H{:,i} = hSlice;
end

Answer 2

Est

compare(a,b) == compare(b,a)

et

compare(a,a) == 1

Dans ce cas, changer votre boucle

for i=1:numel(list)
    for j=1:numel(list)
    ...
    end
end

à

for i=1:numel(list)
    for j= i+1 : numel(list)
    ...
    end
end

et de traiter le cas de symétrie et de l'identité. Cela permettra de réduire votre temps de calcul de moitié.

Answer 3

Si je comprends bien, vous devez effectuer 5000 ^ 2 comparaisons de la matrice? Plutôt que d'essayer de paralléliser la fonction de comparaison, peut-être vous devriez penser à votre problème étant composé de 5000 ^ 2 tâches? Le parallèle Matlab Compute Boîte à outils prend en charge le parallélisme basé sur les tâches. Malheureusement, mon expérience PCT est avec parallélisation de gros problèmes de type algèbre linéaire, donc je ne peux pas vraiment vous en dire beaucoup plus que cela. La documentation sera sans aucun doute vous aider plus.