Arbeit stehlen mit Parallel Computing Toolbox

Question

Ich habe einen kombinatorischen Suchalgorithmus implementiert (zum Vergleich mit einer effizienteren Optimierungstechnik) und versucht, seine Laufzeit mit parfor zu verbessern.

Leider scheinen die Arbeitsaufgaben sehr schlecht unausgewogen zu sein.

Jeder Unterpunkt i hat eine Komplexität von etwa nCr(N - i, 3). Wie Sie sehen können, beinhalten die Aufgaben i < N/4 wesentlich mehr Arbeit als i > 3*N/4, aber es scheint, dass MATLAB alle von i < N/4 einem einzelnen Arbeiter zuweist.

Stimmt es, dass MATLAB die Arbeit auf Basis von gleich großen Teilmengen des Loop-Bereichs teilt?

Nein, this question zitiert die Dokumentation, die es nicht sagt.

Gibt es eine bequeme Möglichkeit, diese neu zu gewichten, ohne die Anzahl der Arbeitnehmer zu (zB wenn ich genau 4 Arbeiter im Pool benötigen, dann könnte ich die beide niedrigsten Bits von i mit zwei höheren Bits, um tauschen, um sicherzustellen, jeder Arbeiter erhielt eine Mischung aus einfachen und harten Aufgaben)?

Ich glaube nicht, eine vollständige „Work-Stehlen“ Implementierung erforderlich ist, vielleicht die Zuordnung nur 1, 2, 3, 4 an die Arbeiter, dann, wenn 4 erste abgeschlossen ist, beginnt seine Arbeiter auf Artikel 5, und so weiter . Die Größe jedes Elements ist ausreichend größer als die Anzahl der Iterationen, und ich bin nicht allzu besorgt über den erhöhten Kommunikationsaufwand.

Answer 1

Wenn die Schleifeniterationen tatsächlich vor der Zeit verteilt sind (was bedeuten würde, dass am Ende ein einzelner Arbeiter mehrere Iterationen ausführen muss, während die anderen Arbeiter im Leerlauf sind), ist das wirklich der Fall?), der einfachste Weg, eine Mischung, um sicherzustellen, ist zufällig die Schleifendurchläufe permutieren:

permutedIterations = randperm(nIterations); 
permutedResults = cell(nIterations,1); %# or whatever else you use for storing results 

%# run the parfor loop, completing iterations in permuted order 
parfor iIter = 1:nIterations 
    permutedResults(iIter) = f(permutedIterations(iIter)); 
end 

%# reorder results for easier subsequent analysis 
results = permutedResults(permutedIterations);