Perché questo codice parallelo in scala D è così grave?

Question

Ecco un esperimento che ho eseguito confrontando il parallelismo in C++ e D. Ho implementato un algoritmo (uno schema di propagazione di etichette parallele per il rilevamento di comunità nelle reti) in entrambi i linguaggi, utilizzando lo stesso design: Un iteratore parallelo ottiene una funzione di handle (normalmente un chiusura) e lo applica per ogni nodo nel grafico.

Ecco l'iteratore in D, implementato utilizzando taskPool da 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); 
    } 
} 

E questa è la funzione maniglia che viene passato:

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

     } 
    }; 

L'implementazione C++ 11 è quasi identico , ma utilizza OpenMP per la parallelizzazione. Quindi cosa mostrano gli esperimenti di ridimensionamento?

Qui esaminiamo scalatura debole, raddoppiando le dimensioni grafo di input mentre anche raddoppiando il numero di fili e misurando il tempo di esecuzione. L'ideale sarebbe una linea retta, ma ovviamente c'è un sovraccarico per il parallelismo. Io uso defaultPoolThreads(nThreads) nella mia funzione principale per impostare il numero di thread per il programma D. La curva per C++ sembra buona, ma la curva per D sembra sorprendentemente negativa. Sto facendo qualcosa di sbagliato w.r.t. D parallelismo, o questo riflette male sulla scalabilità dei programmi paralleli D?

p.s. flag di compilazione

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

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

pps. Qualcosa deve essere veramente sbagliato, perché l'implementazione D è più lento in parallelo che in sequenza:

PPP. Per i curiosi, ecco gli URL clone Mercurial per entrambe le implementazioni:

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

Answer 1

E 'difficile da dire, perché non capisco appieno come si suppone che l'algoritmo a lavorare, ma sembra che il tuo codice non sia thread-safe, il che sta causando l'esecuzione di più iterazioni del necessario.

ho aggiunto questo al fine PLP.run:

writeln(nIterations); 

Con 1 filo nIterations = 19
Con 10 thread nIterations = 34
Con 100 thread nIterations = 90

Quindi, come potete vedere, non è più tempo a causa di alcuni problemi con std.parallelism, ma semplicemente perché sta facendo più lavoro.

Perché il codice non è thread-safe?

La funzione si esegue in parallelo è propagateLabels, che ha condiviso, non sincronizzato accesso a labels, nUpdated e active. Chissà quale comportamento bizzarro sta causando, ma non può essere buono.

Prima di iniziare la profilatura, è necessario correggere l'algoritmo in modo da essere thread-safe.

Answer 2

Come sottolinea Peter Alexander, il tuo algoritmo sembra essere thread-safe. Per renderlo thread-safe, è necessario eliminare tutte le dipendenze dei dati tra gli eventi che possono verificarsi in thread diversi contemporaneamente o in un ordine non definito. Un modo per farlo è replicare alcuni stati attraverso i thread usando WorkerLocalStorage (fornito in std.parallelism), ed eventualmente unire i risultati in un ciclo relativamente economico alla fine dell'algoritmo.

In alcuni casi il processo di replicare questo stato può essere automatizzato scrivendo l'algoritmo come riduzione e utilizzando std.parallelism.reduce (eventualmente in combinazione con std.algorithm.map o std.parallelism.map) per fare il lavoro pesante.