(Update: eine frühere Version hatte die Indizierung falsch. Diese Version auto-vektorisiert ziemlich leicht).
Verwenden Sie ein mehrdimensionales C-Array (anstelle eines Arrays von Zeigern zu Zeigern) oder ein flaches 1D-Array, das mit i*cols + j indiziert ist, sodass der Speicher zusammenhängend ist. Dies wird einen großen Unterschied in der Effektivität des Hardware-Prefetching machen, um die Speicherbandbreite gut auszunutzen. Lasten mit einer Adresse, die von einer anderen Last kommt, sind wirklich schlecht für die Leistung, oder umgekehrt hilft es, vorhersehbare Adressen zu haben, die schon lange bekannt sind, weil die Lasten lange bevor sie benötigt werden (dank Out-of-Order-Ausführung) starten können.
Auch die Antwort von @ user31264 ist korrekt, Sie müssen die Schleifen austauschen, damit die Schleife über j die äußerste ist. Das ist gut, aber alleine nicht ausreichend.
Dies ermöglicht dem Compiler auch eine automatische Vektorisierung. Tatsächlich hatte ich eine überraschend harte Zeit, um gcc gut vektorisieren zu lassen. (Aber das ist wahrscheinlich, weil ich die Indizierung falsch verstanden, weil ich nur auf dem Code zum ersten Mal sah. So ist der Compiler nicht wissen, dass wir über zusammenhängende Speicher wurden Looping.)
ich gespielt, um mit ihm auf die Godbolt compiler explorer.
Ich habe endlich gut schön Compiler Ausgabe dieser Version, die als flache 1D-Arrays nimmt A und C und hat die Indizierung selbst:
void MatrixAddition_contiguous(int rows, int n, const vector<int>& list,
const int *__restrict__ A, int *__restrict__ C, int cluster)
// still auto-vectorizes without __restrict__, but checks for overlap and
// runs a scalar loop in that case
{
const int cols = 4; // or global constexpr or something
int *__restrict__ Ccluster = C + ((long)cluster) * rows * cols;
for(int i=0;i<rows;i++)
//#pragma omp simd
for(int k=0;k<4;k++)
Ccluster[cols*i + k]=0;
for(int j=0;j < cols;++j) { // loop over clusters in A in the outer-most loop
const int *__restrict__ Alistj = A + ((long)list[j]) * rows * cols;
// #pragma omp simd // Doesn't work: only auto-vectorizes with -O3
// probably only -O3 lets gcc see through the k=0..3 loop and treat it like one big loop
for (int i = 0; i < rows; i++) {
long row_offset = cols*i;
//#pragma omp simd // forces vectorization with 16B vectors, so it hurts AVX2
for(int k=0;k<4;k++)
Ccluster[row_offset + k] += Alistj[row_offset + k];
}
}
}
manuell Hissen der list[j] definitiv den Compiler dazu beigetragen, erkennen, dass Geschäfte in C kann die Indizes nicht beeinflussen, die von list[j] geladen werden. Das manuelle Heben der anderen Sachen war wahrscheinlich nicht nötig.
Hochziehen A[list[j]], anstatt nur list[j], ist ein Artefakt von previous approach where I had the indexing wrong. Solange wir die Last von list[j] so weit wie möglich hissen, kann der Compiler eine gute Arbeit leisten, auch wenn er nicht weiß, dass list sich nicht überschneidet C.
Die innere Schleife, mit gcc 5.3 Targeting x86-64 -O3 -Wall -march=haswell -fopenmp (und -fverbose-asm) ist:
.L26:
vmovdqu ymm0, YMMWORD PTR [r8+rax] # MEM[base: Ccluster_20, index: ivtmp.91_26, offset: 0B], MEM[base: Ccluster_20, index: ivtmp.91_26, offset: 0B]
vpaddd ymm0, ymm0, YMMWORD PTR [rdx+rax] # vect__71.75, MEM[base: Ccluster_20, index: ivtmp.91_26, offset: 0B], MEM[base: vectp.73_90, index: ivtmp.91_26, offset: 0B]
add r12d, 1 # ivtmp.88,
vmovdqu YMMWORD PTR [r8+rax], ymm0 # MEM[base: Ccluster_20, index: ivtmp.91_26, offset: 0B], vect__71.75
add rax, 32 # ivtmp.91,
cmp r12d, r9d # ivtmp.88, bnd.66
jb .L26 #,
es tut acht fügt sofort Also, mit AVX2 vpaddd, mit nicht ausgerichteten Lasten und einem nicht ausgerichteten Speicher zurück in C.
Da dies Auto -Vektoring ist, sollte es guten Code mit ARM NEON oder PPC Altivec, oder alles, was gepackte 32-Bit-Zugabe tun kann.
Ich konnte gcc nicht bekommen, mir irgendetwas mit -ftree-vectorizer-verbose=2 zu erzählen, aber von clang war ein wenig hilfreich.
Die dreifache Ebene der Indirektion allein tötet wahrscheinlich diese Funktion. Wenn Sie versuchen * nicht * Cache-freundlich zu sein, Glückwunsch, ich denke, Sie haben Erfolg. – WhozCraig
Sie müssen uns zeigen, wie Sie diese Arrays zugewiesen haben. Wenn du es naiv gemacht hast, dann ist das, wie @WhozCraig gesagt hat, nicht gut. Wenn Sie einen riesigen Speicherpool zugewiesen und die Zeiger auf die richtigen Stellen in dieser Erinnerung gerichtet haben, dann ist das eine andere Geschichte. – PaulMcKenzie
Es ist eine schlechte Idee, eine Vektor "Liste" aufzurufen. Es ist so, als würde man eine Liste "Vektor" aufrufen, eine "Karte" aufrufen oder die Katze "Hund" rufen. – user31264