Prédire l'exécution de la boucle parallèle en utilisant une estimation A-priori de l'effort par iterand (pour le nombre donné de travailleurs)

Question

Je travaille sur une implémentation MATLAB d'une multiplication de vecteur matriciel adaptative pour de très grandes matrices clairsemées provenant d'une discrétisation particulière d'un PDE (avec une structure de rareté connue).

Après beaucoup de prétraitement, je me retrouve avec un certain nombre de blocs différents (plus que, disons, 200), pour lesquels je veux calculer les entrées sélectionnées.

L'une des étapes de prétraitement consiste à déterminer le (nombre de) entrées par bloc que je veux calculer, ce qui me donne une mesure presque parfaite du temps que prendra chaque bloc (à toutes fins utiles, l'effort quadrature est l'effort même pour chaque entrée).

Grâce à https://stackoverflow.com/a/9938666/2965879, J'ai pu en faire usage en commandant les blocs dans l'ordre inverse, en poussant ainsi Matlab en commençant par les plus gros en premier.

Cependant, le nombre d'entrées diffère si sauvagement d'un bloc à l'autre, selon lequel le parformité directe est gravement limitée par les blocs avec le plus grand nombre d'entrées, même s'ils sont introduits dans la boucle en sens inverse.

Ma solution est de faire les plus gros blocs en série (mais parallélisé au niveau des entrées!), Ce qui est bien tant que les frais généraux par Iterand n'ont pas trop d'importance, resp. Les blocs ne deviennent pas trop petits. Le reste des blocs que je fais ensuite avec PARFOR. Idéalement, je laisserais Matlab décider comment gérer cela, mais comme une boucle de parfor pour imbriquée perd son parallélisme, cela ne fonctionne pas. De plus, l'emballage des deux boucles en un est (presque) impossible.

Ma question est maintenant de savoir comment déterminer au mieux cette coupure entre la série et le régime parallèle, en tenant compte des informations que j'ai sur le nombre d'entrées (la forme de la courbe des entrées ordonnées peut différer pour différents problèmes), car ainsi que le nombre de travailleurs dont j'ai disponible.

Jusqu'à présent, je travaillais avec les 12 travailleurs disponibles sous une licence PCT standard, mais depuis que j'ai commencé à travailler sur un cluster, la détermination de cette coupure devient de plus en plus cruciale (puisque pour de nombreux cœurs, la surcharge de la La boucle série devient de plus en plus coûteuse par rapport à la boucle parallèle, mais de même, les blocs qui maintiennent le reste sont encore plus coûteux).

Pour 12 cœurs (res. La configuration du serveur de calcul avec lequel je travaillais), j'avais trouvé un paramètre raisonnable de 100 entrées par travailleur comme une coupure, mais cela ne fonctionne pas bien lorsque le nombre de cœurs n'est pas Petit plus par rapport au nombre de blocs (par exemple 64 vs 200).

J'ai essayé de dégonfler le nombre de cœurs avec différentes pouvoirs (par exemple 1/2, 3/4), mais cela ne fonctionne pas non plus de manière cohérente. Ensuite, j'ai essayé de regrouper les blocs en lots et de déterminer la coupure lorsque les entrées sont plus grandes que la moyenne par lot, resp. Le nombre de lots ils sont loin de la fin:

logical_sml = true(1,num_core); i = 0;
while all(logical_sml)
    i = i+1;
    m = mean(num_entr_asc(1:min(i*num_core,end))); % "asc" ~ ascending order 
    logical_sml = num_entr_asc(i*num_core+(1:num_core)) < i^(3/4)*m;  
        % if the small blocks were parallelised perfectly, i.e. all  
        % cores take the same time, the time would be proportional to  
        % i*m. To try to discount the different sizes (and imperfect  
        % parallelisation), we only scale with a power of i less than  
        % one to not end up with a few blocks which hold up the rest  
end  
num_block_big = num_block - (i+1)*num_core + sum(~logical_sml);

(Remarque: ce code ne fonctionne pas pour les vecteurs num_entr_asc dont la longueur n'est pas un multiple de num_core, mais j'ai décidé d'omettre le min(...,end) Constructions pour la lisibilité.)

J'ai également omis le < max(...,...) Pour combiner les deux conditions (c'est-à-dire avec un minimum d'entrées par travailleur), ce qui est nécessaire pour que la coupure ne soit pas trouvée trop tôt. J'ai pensé un peu à utiliser la variance également, mais jusqu'à présent, toutes les tentatives n'ont pas été satisfaisantes.

Je serais très reconnaissant que quelqu'un ait une bonne idée de la façon de résoudre ce problème.

Answer 1

J'ai trouvé une solution quelque peu satisfaisante, donc au cas où quelqu'un serait intéressé, je pensais le partager. J'apprécierais toujours les commentaires sur la façon d'améliorer / affiner l'approche.

Fondamentalement, j'ai décidé que le seul moyen raisonnable est de construire un modèle (très) rudimentaire du planificateur pour la boucle parallèle:

function c=est_cost_para(cost_blocks,cost_it,num_cores)
% Estimate cost of parallel computation

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   c: Estimated cost of parallel computation

num_blocks=numel(cost_blocks);
c=zeros(num_cores,1);

i=min(num_blocks,num_cores);
c(1:i)=cost_blocks(end-i+1:end)+cost_it;
while i<num_blocks
    i=i+1;
    [~,i_min]=min(c); % which core finished first; is fed with next block
    c(i_min)=c(i_min)+cost_blocks(end-i+1)+cost_it;
end

c=max(c);

end

Le paramètre cost_it car une itération vide est un mélange brut de nombreux effets secondaires différents, qui pourraient être séparés: le coût d'une itération vide dans un for/parfor-loop (pourrait également être différent par bloc), ainsi que le temps de démarrage. transmission des données du parfor-loop (et probablement plus). Ma principale raison de tout jeter ensemble est que je ne veux pas avoir à estimer / déterminer les coûts les plus granulaires.

J'utilise la routine ci-dessus pour déterminer la coupure de la manière suivante:

% function i=cutoff_ser_para(cost_blocks,cost_it,num_cores)
% Determine cut-off between serial an parallel regime

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   i: Number of blocks to be calculated serially

num_blocks=numel(cost_blocks);
cost=zeros(num_blocks+1,2);

for i=0:num_blocks
    cost(i+1,1)=sum(cost_blocks(end-i+1:end))/num_cores + i*cost_it;
    cost(i+1,2)=est_cost_para(cost_blocks(1:end-i),cost_it,num_cores);
end

[~,i]=min(sum(cost,2));
i=i-1;

end

En particulier, je ne gonfle pas / ne modifie pas la valeur de est_cost_para qui suppose (à part cost_it) la planification la plus optimiste possible. Je le laisse principalement parce que je ne sais pas ce qui fonctionnerait le mieux. Pour être conservateur (c'est-à-dire éviter de nourrir des blocs trop grands à la boucle parallèle), on pourrait bien sûr ajouter un certain pourcentage comme tampon ou même utiliser une puissance> 1 pour gonfler le coût parallèle.

Notez également que est_cost_para est appelé avec successivement moins de blocs (bien que j'utilise le nom de la variable cost_blocks Pour les deux routines, l'une est un sous-ensemble de l'autre).

Par rapport à l'approche de ma question verbeuse, je vois deux principaux avantages:

1. La dépendance relativement complexe entre les données (à la fois le nombre de blocs ainsi que leur coût) et le nombre de cœurs est beaucoup mieux capturé avec le planificateur simulé que possible avec une seule formule.
2. En calculant le coût de toutes les combinaisons possibles de distribution en série / parallèle, puis en prenant le minimum, on ne peut pas être "coincé" trop tôt lors de la lecture des données d'un côté (par exemple par un saut qui est grand par rapport aux données jusqu'à présent, jusqu'à présent, mais petit par rapport au total).

Bien sûr, la complexité asymptotique est plus élevée en appelant est_cost_para avec sa boucle tout le temps, mais dans mon cas (num_blocks<500) C'est absolument négligeable.

Enfin, si une valeur décente de cost_it Ne se présente pas facilement, on peut essayer de le calculer en mesurant le temps d'exécution réel de chaque bloc, ainsi que la partie purement parallèle, puis en essayant d'ajuster les données résultantes à la prédiction des coûts et d'obtenir une valeur mise à jour de cost_it Pour l'appel suivant de la routine (en utilisant la différence entre le coût total et le coût parallèle ou en insérant un coût de zéro dans la formule ajustée). J'espère que cela devrait "converger" vers la valeur la plus utile de cost_it pour le problème en question.