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:
- 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.
- 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.