Vorhersage der Laufzeit der parallelen Schleife mit A-Priori-Schätzung des Aufwands pro iterand (für eine bestimmte Anzahl von Arbeitnehmern)

Question

Ich arbeite an einer MATLAB-Implementierung einer adaptiven Matrixvektor-Multiplikation für sehr große spärliche Matrizen, die aus einer bestimmten Diskretisierung eines PDE (mit bekannter Sparsity-Struktur) stammen.

Nach viel Vorverarbeitung habe ich eine Reihe verschiedener Blöcke (größer als beispielsweise 200), für die ich ausgewählte Einträge berechnen möchte.

Einer der Vorverarbeitungsschritte besteht darin, die (Anzahl der) Einträge pro Block zu bestimmen, die ich berechnen möchte. Dies gibt mir ein nahezu perfekt Gleiches gilt für jeden Eintrag).

Dank an https://stackoverflow.com/a/9938666/2965879, Ich konnte dies nutzen, indem ich die Blöcke in umgekehrter Reihenfolge bestellte und so Matlab zuerst mit den größten anfing.

Die Anzahl der Einträge unterscheidet sich jedoch so wild von Block zu Block, dass die direkte Ausführung von Parforen durch die Blöcke mit der größten Anzahl von Einträgen stark begrenzt ist, selbst wenn sie umgekehrt in die Schleife eingespeist werden.

Meine Lösung ist es, die größten Blöcke seriell (aber parallel auf der Ebene der Einträge!) Durchzuführen, was in Ordnung ist, solange der Overhead pro iterand nicht zu viel spielt. Die Blöcke werden nicht zu klein. Der Rest der Blöcke, die ich dann mit Parfore mache. Im Idealfall würde ich Matlab entscheiden lassen, wie man damit umgeht, aber da eine verschachtelte Parfore-Loop seine Parallelität verliert, funktioniert dies nicht. Außerdem ist das Verpacken von beiden Schleifen in einem (nahe) unmöglich.

Meine Frage ist nun, wie Sie diesen Grenzwert zwischen der Serie und dem parallelen Regime am besten bestimmen können, wobei die Informationen, die ich über die Anzahl der Einträge habe (die Form der Kurve der geordneten Einträge, für unterschiedliche Probleme abweichen kann) wie bei unterschiedlichen Problemen) sowie die Anzahl der Arbeitnehmer, die ich zur Verfügung habe.

Bisher hatte ich mit den 12 Mitarbeitern zusammengearbeitet, die im Rahmen der Standard-PCT-Lizenz verfügbar sind, aber seit ich jetzt an einem Cluster gearbeitet habe Die serielle Schleife wird im Vergleich zur parallelen Schleife immer teurer, aber ähnlich sind Blöcke, die den Rest noch teurer sind).

Für 12 Kerne (bzw. die Konfiguration des Computerservers, mit dem ich gearbeitet habe) hatte ich einen angemessenen Parameter von 100 Einträgen pro Arbeiter als Abschnitt herausgefunden, aber dies funktioniert nicht gut, wenn die Anzahl der Kerne nicht ist kleiner in Bezug auf die Anzahl der Blöcke (z. B. 64 gegenüber 200).

Ich habe versucht, die Anzahl der Kerne mit unterschiedlichen Kräften (z. B. 1/2, 3/4) zu entleeren, aber dies funktioniert auch nicht konsequent. Als nächstes versuchte ich, die Blöcke in Chargen zu gruppieren und den Grenzwert zu bestimmen, wenn die Einträge größer als der Mittelwert pro Stapel sind. Die Anzahl der Chargen, die sie vom Ende weg sind:

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);

(Hinweis: Dieser Code funktioniert nicht für Vektoren num_entr_asc deren Länge kein Vielfalt von ist num_core, aber ich beschloss, das wegzulassen min(...,end) Konstruktionen für die Lesbarkeit.)

Ich habe auch die weggelassen < max(...,...) Für die Kombination beider Bedingungen (dh zusammen mit Mindesteinträgen pro Arbeiter), was notwendig ist, so dass der Grenzwert nicht zu früh gefunden wird. Ich dachte ein wenig darüber nach, die Varianz irgendwie zu verwenden, aber bisher waren alle Versuche unbefriedigend.

Ich wäre sehr dankbar, wenn jemand eine gute Idee hat, wie er dies lösen kann.

Answer 1

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:

1. 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.
2. 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.