Parallele Aufgaben erhalten bessere Leistung mit boost :: thread als mit ppl oder OpenMP

Question

Ich habe ein C++ - Programm, das parallelisiert werden könnte. Ich verwende Visual Studio 2010, 32-Bit-Kompilierung.

Kurz die Struktur des Programms ist die folgende

#define num_iterations 64 //some number 

struct result 
{ 
    //some stuff 
} 

result best_result=initial_bad_result; 

for(i=0; i<many_times; i++) 
{ 
    result *results[num_iterations]; 


    for(j=0; j<num_iterations; j++) 
    { 
     some_computations(results+j); 
    } 

    // update best_result; 
} 

Da jeder some_computations() unabhängig ist (einige globale Variablen lesen, aber keine globale Variablen geändert) Ich parallelisiert die innere for -loop.

Mein erster Versuch war mit boost :: thread,

thread_group group; 
for(j=0; j<num_iterations; j++) 
{ 
    group.create_thread(boost::bind(&some_computation, this, result+j)); 
} 
group.join_all(); 

Die Ergebnisse waren gut, aber ich beschloss, mehr zu versuchen.

Ich versuchte, die OpenMP Bibliothek

#pragma omp parallel for 
for(j=0; j<num_iterations; j++) 
{ 
    some_computations(results+j); 
} 

Die Ergebnisse schlechter waren als die boost::thread ‚s diejenigen.

Dann habe ich versucht, die ppl Bibliothek und verwendet parallel_for():

Concurrency::parallel_for(0,num_iterations, [=](int j) { 
    some_computations(results+j); 
}) 

Die Ergebnisse der schlechtesten waren.

Ich fand dieses Verhalten ziemlich überraschend. Da OpenMP und ppl für die Parallelisierung ausgelegt sind, hätte ich bessere Ergebnisse erwartet, als boost::thread. Liege ich falsch?

Warum gibt boost::thread mir bessere Ergebnisse?

Answer 1

OpenMP oder PPL sind nicht so pessimistisch. Sie tun nur, was ihnen gesagt wird, aber es gibt einige Dinge, die Sie berücksichtigen sollten, wenn Sie versuchen, Schleifen zu paralellisieren.

Ohne zu sehen, wie Sie diese Dinge implementiert haben, ist es schwer zu sagen, was die wahre Ursache sein könnte.

Auch wenn die Operationen in jeder Iteration eine Abhängigkeit von anderen Iterationen in der gleichen Schleife haben, wird dies eine Konkurrenz erzeugen, die die Dinge verlangsamen wird. Sie haben nicht gezeigt, was Ihre some_operation-Funktion tatsächlich tut, also ist es schwer zu sagen, ob es Datenabhängigkeiten gibt.

Eine Schleife, die wirklich parallelisiert werden kann, muss in der Lage sein, jede Iteration völlig unabhängig von allen anderen Iterationen ausführen zu lassen, ohne auf den gemeinsamen Speicher in irgendeiner der Iterationen zuzugreifen. Also, am besten schreibst du Sachen in lokale Variablen und kopierst sie dann am Ende.

Nicht alle Schleifen können parallelisiert werden, es hängt sehr von der Art der Arbeit ab.

Zum Beispiel ist etwas, das für die Parallelisierung gut ist, Arbeit an jedem Pixel eines Bildschirmpuffers getan. Jedes Pixel ist völlig unabhängig von allen anderen Pixeln, und daher kann ein Thread eine Iteration einer Schleife nehmen und die Arbeit ausführen, ohne dass er aufgehalten werden muss, während er auf geteilte Speicher- oder Datenabhängigkeiten innerhalb der Schleife zwischen Iterationen wartet.

Wenn Sie über ein zusammenhängendes Array verfügen, befindet sich dieses Array möglicherweise teilweise in einer Cache-Zeile. Wenn Sie Element 5 in Thread A bearbeiten und dann Element 6 in Thread B ändern, kann es zu Cache-Konflikten kommen verlangsamen auch Dinge, da diese in der gleichen Cache-Zeile liegen würden. Ein Phänomen bekannt als falsch teilen.

Es gibt viele Aspekte, über die Sie bei der Schleifenparallelisierung nachdenken sollten.

Answer 2

Kurz gesagt, basiert openMP hauptsächlich auf gemeinsam genutztem Speicher, mit zusätzlichen Kosten für Tasking-Management und Speicherverwaltung. ppl ist entworfen, um generische Muster von allgemeinen Datenstrukturen und Algorithmen zu handhaben, es bringt zusätzliche Komplexitätskosten. Beide haben zusätzliche CPU-Kosten, aber Ihre einfachen fallen boost Threads nicht (boost Threads sind nur einfache API-Wrapping). Deshalb sind beide langsamer als Ihre boost Version. Und da die Beispielberechnung unabhängig voneinander ist, sollte openMP ohne Synchronisation nahe der boost Version sein.

Es tritt in einfachen Szenarien auf, aber für komplizierte Szenarien mit komplizierten Datenlayout und Algorithmen sollte es kontextabhängig sein.