Ich hatte eine etwas zufriedenstellende Lösung, also falls jemand interessiert ist, dachte ich, ich würde sie teilen. Ich würde mich immer noch freuen, wie man den Ansatz verbessert/optimiert.
Grundsätzlich habe ich beschlossen, dass der einzig vernünftige Weg darin besteht, ein (sehr) rudimentäres Modell des Schedulers für die Parallelschleife zu erstellen:
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
Der Parameter cost_it
Denn eine leere Iteration ist eine grobe Mischung aus vielen verschiedenen Nebenwirkungen, die möglicherweise getrennt werden könnte: die Kosten einer leeren Iteration in a for
/parfor
-Loop (könnte auch pro Block unterschiedlich sein) sowie die Startzeit. Datenübertragung der parfor
-Loop (und wahrscheinlich mehr). Mein Hauptgrund, alles zusammenzubringen, ist, dass ich die körnigeren Kosten nicht schätzen/bestimmen möchte.
Ich verwende die obige Routine, um den Grenzwert auf folgende Weise zu bestimmen:
% 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
Insbesondere habe ich den Wert von nicht aufblasen/ändere est_cost_para
was voraussetzt (abgesehen von cost_it
) Die optimistischste Planung möglich. Ich lasse es wie vor allem, weil ich nicht weiß, was am besten funktionieren würde. Um konservativ zu sein (dh vermeiden, zu große Blöcke zur parallelen Schleife zu füttern), könnte man natürlich einen gewissen Prozentsatz als Puffer hinzufügen oder sogar eine Leistung> 1 verwenden, um die parallelen Kosten zu erhöhen.
Beachten Sie auch das est_cost_para
wird mit sukzessiven Blöcken aufgerufen (obwohl ich den variablen Namen verwende cost_blocks
Für beide Routinen ist eine Teilmenge des anderen).
Im Vergleich zu dem Ansatz in meiner wortreichen Frage sehe ich zwei Hauptvorteile:
- Die relativ komplizierte Abhängigkeit zwischen den Daten (sowohl die Anzahl der Blöcke als auch deren Kosten) und die Anzahl der Kerne wird mit dem simulierten Scheduler viel besser erfasst als mit einer einzigen Formel möglich.
- Durch die Berechnung der Kosten für alle möglichen Kombinationen der seriellen/parallelen Verteilung und dann des Minimums kann man nicht zu früh "stecken" werden, während man die Daten von einer Seite auslegt (z. B. durch einen Sprung, der im Vergleich zu den bisherigen Daten groß ist. aber klein im Vergleich zum Gesamtbetrag).
Natürlich ist die asymptotische Komplexität durch Aufrufen höher est_cost_para
mit seiner Weile-Loop die ganze Zeit, aber in meinem Fall (num_blocks<500
) Das ist absolut vernachlässigbar.
Schließlich, wenn ein anständiger Wert von cost_it
Es gibt nicht ohne weiteres sich selbst, man kann versuchen, es zu berechnen, indem man die tatsächliche Ausführungszeit jedes Blocks sowie den rein parallelen Teil davon misst und dann versucht, die resultierenden Daten an die Kostenvorhersage anzupassen und einen aktualisierten Wert von zu erhalten cost_it
Für den nächsten Anruf der Routine (durch Verwendung der Differenz zwischen Gesamtkosten und parallelen Kosten oder durch Einfügen von Nullkosten in die angepasste Formel). Dies sollte hoffentlich auf den nützlichsten Wert von "konvergieren" cost_it
für das fragliche Problem.