Cache Linien, falsche gemeinsame Nutzung und Ausrichtung

Question

Ich schrieb das folgende kurze C++ Programm den falschen Teilungseffekt zu reproduzieren, wie durch Herb Sutter beschrieben:

sagen, dass wir eine Gesamtmenge von WORKLOAD Integer-Operationen ausführen wollen, und wir wollen, dass sie gleichmäßig auf eine Anzahl (PARALLEL) von Threads verteilt sein. Für den Zweck dieses Tests wird jeder Thread seine eigene dedizierte Variable aus einem Array von ganzen Zahlen inkrementieren, so dass der Prozess idealerweise parallelisierbar sein kann.

void thread_func(int* ptr) 
{ 
    for (unsigned i = 0; i < WORKLOAD/PARALLEL; ++i) 
    { 
     (*ptr)++; 
    } 
} 

int main() 
{ 
    int arr[PARALLEL * PADDING]; 
    thread threads[PARALLEL]; 

    for (unsigned i = 0; i < PARALLEL; ++i) 
    { 
     threads[i] = thread(thread_func, &(arr[i * PADDING])); 
    } 
    for (auto& th : threads) 
    { 
     th.join(); 
    } 
    return 0; 
} 

Ich denke, die Idee ist leicht zu verstehen. Wenn Sie

#define PADDING 16 

jeder Thread gesetzt wird auf einer separaten Cache-Zeile arbeiten (die Länge einer Cache-Zeile 64 Byte unter der Annahme zu sein). Das Ergebnis ist ein linearer Anstieg der Beschleunigung bis PARALLEL> # Kerne. Wenn andererseits PADDING auf irgendeinen Wert unter 16 gesetzt wird, sollte ein starker Konflikt auftreten, da nun mindestens zwei Threads wahrscheinlich auf der gleichen Cache-Zeile operieren, die jedoch durch einen eingebauten Hardware-Mutex geschützt ist. Wir würden erwarten, dass unsere Beschleunigung in diesem Fall nicht nur sublinear ist, sondern aufgrund der unsichtbaren Schleuse auch immer < 1 ist.

Nun erfüllten meine ersten Versuche diese Erwartungen fast, aber der Mindestwert von PADDING, um falsches Teilen zu vermeiden, war um 8 und nicht 16. Ich war eine halbe Stunde lang ziemlich verwirrt, bis ich zu dem offensichtlichen Schluss kam Es gibt keine Garantie dafür, dass mein Array exakt am Anfang einer Cache-Zeile im Hauptspeicher ausgerichtet ist. Die tatsächliche Ausrichtung kann abhängig von vielen Bedingungen einschließlich der Größe des Arrays variieren.

In diesem Beispiel brauchen wir das Array natürlich nicht auf eine spezielle Weise auszurichten, da wir PADDING einfach bei 16 lassen können und alles funktioniert. Man kann sich jedoch Fälle vorstellen, in denen es einen Unterschied macht, ob eine bestimmte Struktur an einer Cache-Zeile ausgerichtet ist oder nicht. Daher habe ich einige Codezeilen hinzugefügt, um Informationen über die tatsächliche Ausrichtung meines Arrays zu erhalten.

int main() 
{ 
    int arr[PARALLEL * 16]; 
    thread threads[PARALLEL]; 
    int offset = 0; 

    while (reinterpret_cast<int>(&arr[offset]) % 64) ++offset; 
    for (unsigned i = 0; i < PARALLEL; ++i) 
    { 
     threads[i] = thread(thread_func, &(arr[i * 16 + offset])); 
    } 
    for (auto& th : threads) 
    { 
     th.join(); 
    } 
    return 0; 
} 

Trotz dieser Lösung in diesem Fall für mich gut geklappt, ich bin nicht sicher, ob es ein guter Ansatz im Allgemeinen wäre. Also hier ist meine Frage:

Gibt es eine gemeinsame Möglichkeit, Objekte im Speicher auf Cache-Zeilen anders als was ich im obigen Beispiel getan haben?

(unter Verwendung von g ++ MinGW Win32 x86 v.4.8.1 POSIX dwarf rev3)

Answer 1

Sie sollten die erforderliche Ausrichtung des Compilers der Lage sein, zu verlangen:

alignas(64) int arr[PARALELL * PADDING]; // align the array to a 64 byte line 

Answer 2

gcc unterstützt ein ausgerichtetes Stichwort: http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html

Sie wollen wahrscheinlich etwas wie folgt aus:

int arr[PARALLEL * 16] __attribute__ ((aligned (8)));

Dies richtet arr auf eine Acht-Byte-Grenze aus.

Visual Studio hat eine ähnliche Funktion auch: http://msdn.microsoft.com/en-us/library/83ythb65.aspx