Dlaczego ten kod równoległy w skali D tak źle?

Question

Oto jeden z eksperymentów, które przeprowadziłem porównując paralelizm w C++ i D. Zaimplementowałem algorytm (schemat propagacji etykiety równoległej do wykrywania społeczności w sieciach) w obu językach, używając tego samego projektu: iterator równoległy uzyskuje funkcję uchwytu (zwykle zamknięcie) i stosuje go dla każdego węzła na wykresie.

Oto iterator D, realizowane z wykorzystaniem taskPool z std.parallelism:

/** 
* Iterate in parallel over all nodes of the graph and call handler (lambda closure). 
*/ 
void parallelForNodes(F)(F handle) { 
    foreach (node v; taskPool.parallel(std.range.iota(z))) { 
     // call here 
     handle(v); 
    } 
} 

i jest to funkcja, która jest przekazywana rękojeść:

auto propagateLabels = (node v){ 
     if (active[v] && (G.degree(v) > 0)) { 
      integer[label] labelCounts; 

      G.forNeighborsOf(v, (node w) { 
       label lw = labels[w]; 
       labelCounts[lw] += 1; // add weight of edge {v, w} 
      }); 

      // get dominant label 
      label dominant; 
      integer lcmax = 0; 
      foreach (label l, integer lc; labelCounts) { 
       if (lc > lcmax) { 
        dominant = l; 
        lcmax = lc; 
       } 
      } 

     if (labels[v] != dominant) { // UPDATE 
      labels[v] = dominant; 
      nUpdated += 1; // TODO: atomic update? 
      G.forNeighborsOf(v, (node u) { 
       active[u] = 1; 
      }); 
     } else { 
      active[v] = 0; 
     } 

     } 
    }; 

Realizacja C++ 11 jest prawie identyczny , ale używa OpenMP do równoległości. Co pokazują eksperymenty skalowania?

Tutaj badam słabe skalowanie, podwojenie rozmiaru wykresu wejście jednocześnie podwajając liczbę wątków i pomiar czasu pracy. Ideał byłby linią prostą, ale oczywiście istnieje pewne obciążenie dla równoległości. Używam defaultPoolThreads(nThreads) w mojej głównej funkcji do ustawiania liczby wątków dla programu D. Krzywa dla C++ wygląda dobrze, ale krzywa dla D wygląda zaskakująco źle. Czy robię coś złego w.r.t. Równoległość D, czy też źle odzwierciedla skalowalność równoległych programów D?

p.s. flagi kompilatora

dla D: rdmd -release -O -inline -noboundscheck

dla C++: -std=c++11 -fopenmp -O3 -DNDEBUG

PPS. Coś musi być naprawdę źle, ponieważ realizacja D jest wolniejszy niż równolegle kolejno:

PPP. Dla ciekawskich, oto Mercurial urls klonów dla obu implementacjach:

• http://algohub.iti.kit.edu/parco/Prototypes/PLPd
• http://algohub.iti.kit.edu/parco/Prototypes/PLPcpp

Answer 1

Trudno powiedzieć, bo nie w pełni zrozumieć, w jaki sposób algorytm ma działać, ale wygląda na to, że twój kod nie jest wątkowo bezpieczny, co powoduje, że algorytm wykonuje więcej iteracji niż to konieczne.

dodałem to do końca PLP.run:

writeln(nIterations); 

z 1 gwint nIterations = 19
Z 10 wątków nIterations = 34
Z 100 wątków nIterations = 90

Więc jak widać, to nie trwa dłużej z powodu pewnych problemów z std.parallelism, ale po prostu dlatego, że robi więcej pracy.

Dlaczego twój kod nie jest wątkowo bezpieczny?

Funkcja uruchomić równolegle jest propagateLabels, który wspólne, niezsynchronizowane dostęp do labels, nUpdated i active. Kto wie, jakie to dziwne zachowanie powoduje, ale nie może być dobre.

Przed rozpoczęciem profilowania należy ustawić algorytm tak, aby był bezpieczny dla wątków.

Answer 2

Jak wskazuje Peter Alexander, Twój algorytm wydaje się być niebezpieczny dla wątków. Aby było to bezpieczne dla wątków, należy wyeliminować wszystkie zależności danych między zdarzeniami, które mogą wystąpić w różnych wątkach jednocześnie lub w niezdefiniowanej kolejności. Jednym ze sposobów, aby to zrobić, jest replikacja stanu w wątkach przy użyciu WorkerLocalStorage (dostarczanego w standaryzmie standardowym) i możliwie połączenie wyników w stosunkowo tanie pętle na końcu algorytmu.

W niektórych przypadkach proces replikacji tego stanu może być zautomatyzowane pisząc algorytm jako zmniejszenie i korzystania std.parallelism.reduce (ewentualnie w połączeniu z std.algorithm.map lub std.parallelism.map) zrobić dźwiganie ciężarów.