Aktualisieren von Double-Arrays mit atomaren Operationen

Question

Ich habe versucht, in einem Array von Doppelpunkten auf parallele Weise mit OpenMP zu schreiben (zu aktualisieren). Die Idee ist, dass das Element, das aktualisiert werden muss, mehrmals aktualisiert werden kann und das Element selbst während des Betriebs berechnet wird. Dies macht es sehr anfällig für Race-Bedingungen, es sei denn, ich "sperre" den Speicherbereich entsprechend dem Element, das mit einer atomaren Operation aktualisiert wird. Als Beispiel unten:

#include<omp.h> 
#include<stdlib.h> 

int main() 
{ 

    double *x=NULL, contribution = 1234.5; 
    size_t xlen=1000, i, n; 

    if ((x = (double *) calloc(xlen,sizeof(double))) == NULL) exit(-1) 

    #pragma omp parallel for shared(x) private(n,contribution) 
    for (i=0; i<xlen; i++) { 
     n = find_n_on_the_fly(i); 

     #pragma omp atomic update 
     x[n]+=contribution; // in the more complicated case contributions are different 

    } 

    return 0; 
} 

Ich renne mit diesem Ansatz immer noch in Rennbedingungen. Ich habe versucht, kritische Abschnitte zu verwenden, aber es tötet mich vollständig, da die Arrays groß sind und die Anzahl der Updates ebenfalls groß ist.

Frage: Was ist falsch an diesem Ansatz? Gibt es einen besseren Weg, damit umzugehen?

Hinweis: Um dies zu tun, mache ich etwas Dummes, indem ich Kopien der Arrays für jeden der Threads erstelle und sie später reduziere. Aber Speicherbeschränkungen erlauben mir nicht, weiter zu gehen.

Answer 1

Ich werde dies mit "Ich bin sehr neu in der Parallelverarbeitung" Vorwort und dies möglicherweise nicht funktionsfähig je nach Anwendungsfall.

Eine Idee, die nützlich sein kann, ist es, die Berechnungs- und Aktualisierungsaspekte des Programms zu trennen. Einrichten eines Master-/Steuerprozesses/Threads, der alleinigen Zugriff auf das Array hat und Aktualisierungen in einer Warteschlangenweise aus Informationen ausführt, die von Slave-/Berechnungsprozessen/Threads gesammelt werden. Dies kann dazu dienen, die Notwendigkeit einer Verriegelung im herkömmlichen Sinne zu minimieren.

Ich hoffe, dass zumindest bietet eine andere Sichtweise auf das Problem.

Answer 2

Für mich scheint oben Code effizient.

Allerdings haben Sie zwei Möglichkeiten, es zu verbessern:

1- eine Speicherzuordnungsfunktion _mm_malloc mit Cache-Zeilengröße als eine der Eingabe statt calloc genannt, die Sie verwenden. Das größte Problem, mit dem Sie gerade konfrontiert sind, ist Falsches Teilen. Um die Effekte von FS wegzulassen, zwingen Sie mit der obigen Methode die zugrunde liegende Bibliothek dazu, Speicher (oder Ihr Array) so zuzuweisen, dass sich jedes Element in einer Zeile im Cache befindet. Auf diese Weise kämpfen Threads nicht über eine Cache-Zeile, um zwei verschiedene gemeinsame Variablen abzurufen. Mit anderen Worten, es verhindert die Zuweisung von zwei Variablen in einer Cache-Zeile. Dies erhöht die Leistung in einem Multithread-Programm. Google _mm_malloc für weitere Informationen. Folgende sind jedoch die grundlegende Verwendung. In den meisten modernen Computern ist die Cache-Zeile 64.

#if defined(__INTEL_COMPILER) 
#include <malloc.h> 
#else 
#include <mm_malloc.h> 
#endif 

int CPU_Cache_line_size = 64; 

int xlen = 100; 
double *ptr = _mm_malloc(xlen*sizeof(double), CPU_Cache_line_size); 
/* 
    do something ... 
*/ 
_mm_free(ptr); 

__CPU_CACHE_LINE_SIZE__ kann für Ihr System in folgenden Weise abgefragt werden:

• Linux-Befehl:

  getconf LEVEL1_DCACHE_LINESIZE

• Programatically:

  int CPU_Cache_line_size = sysconf (_SC_LEVEL1_DCACHE_LINESIZE);

• Detaillierte Informationen zu Cache:

  /sys/devices/system/cpu/cpu0/cache/

2- erwähnt du selbst, aber die Grenzen sind für Ihre Situation schwer: ein Array pro Faden und reduzieren sie dann. Dieser Ansatz ist effizienter. Bedenken Sie noch einmal, diesen Ansatz zu verwenden, wenn Sie können.