![[ICO]](/icons/blank.gif){kind=icon}
![[DIR]](/icons/back.gif){kind=icon}
![[ ]](/icons/unknown.gif){kind=icon}
![[TXT]](/icons/text.gif){kind=icon}
Unser Beispiel multipliziert zwei 700x700 Matrizen (3.9MB pro Matrix) oder 500x500 Matrizen (2MB/Matrix). Im Prinzip ist dieses Problem extrem gut parallelisierbar. Jedes der 490.000/250.000 Elemente der Ergebnismatrix lässt sich unabhängig von den anderen berechnen, und auch die Berechnung eines Elements ist gut parallelisierbar: Alle verwendeten Elemente der Operandenmatrizen können parallel geladen werden, und alle Elementmultiplikationen können parallel ausgeführt werden; das Aufsummieren der Produkte kann über einen Baum mit einer Tiefe von ld(n)=10 bzw. 9 erfolgen. Das Problem ist daher eher, die Berechnung so zu organisieren, dass die begrenzten Hardwareresourcen möglichst effektiv eingesetzt werden, insbesondere bei den Speicherzugriffen. main.c enthält den Code drumherum, und der bleibt in allen Versionen gleich. mm1.c enthält die erste Version der Matrix-Multiplikation selbst. Sie ist von der Beschreibung der Matrix-Multiplikation in der Wikipedia abgeleitet.
Wir bauen die erste Version mit
make mm1und koennen ein Profil wie folgt machen:
perf record -e cycles mm1 700 perf reportDas Profil zeigt, dass über 99% der Zeit in matmul verbracht wird und nur 0.06% in main, daher konzentrieren wir uns auf matmul. Wir sehen den Assemblercode, in dem die meisten Zyklen ausgeführt werden, mit
perf annotateDas zeigt uns (Ausschnitt):
0.01 |50: movsd (%rax),%xmm0 0.19 | add $0x8,%rax 0.01 | mulsd (%rdx),%xmm0 88.83 | add %r10,%rdx 0.22 | cmp %rdi,%rax 0.01 | addsd %xmm0,%xmm1 10.64 | jne 50 0.01 | movsd %xmm1,(%r8,%r11,1) 0.08 | add $0x8,%r11Bis inkl. dem Befehl
jne ist das die innere Schleife.
Der entsprechende C-Code ist:
for (k=0, r=0.0; k<m; k++)
r += a[i*m+k]*b[k*p+j];
Man sieht hier, dass der Compiler schon eine Menge wegoptimiert hat.
Die Zuordnung der Zyklen zu den Befehlen ist allerdings eher
unwahrscheinlich, da der add-Befehl schnell ist und auf nichts warten
muss, und der jne-Befehl sehr gut vorhersagbar ist. Schauen wir uns
daher an, wie diverse performance-counter-Resultate ausschauen:
make perf MM="mm1 700"Die Ergebnisse sind:
mm1 700
7956199520 cycles
2429183981 instructions # 0.31 insns per cycle
510799 branch-misses
31866923 offcore_response_all_data_rd_llc_miss_dram
691609751 L1-dcache-loads
448132119 L1-dcache-load-misses # 64.80% of all L1-dcache hits
48390933 LLC-loads
82544 LLC-prefetches
691323402 dTLB-loads
331808798 dTLB-load-misses # 48.00% of all dTLB cache hits
Für 500x500 Matrizen schaut das Ergebnis so aus:
mm1 500
573085436 cycles
889598768 instructions # 1.55 insns per cycle
264337 branch-misses
2909385 offcore_response_all_data_rd_llc_miss_dram
252395886 L1-dcache-loads
111869333 L1-dcache-load-misses # 44.32% of all L1-dcache hits
15836588 LLC-loads
65097 LLC-prefetches
251700823 dTLB-loads
2638938 dTLB-load-misses # 1.05% of all dTLB cache hits
Insbesondere ist die Anzahl der Befehle pro Zyklus in der
700x700-Variante wesentlich kleiner, was vermuten läßt, dass diese
Variante einen grossen Teil der Zeit auf Hauptspeicherzugriffe wartet.
Die 500x500-Variante dagegen führt eine Iteration der inneren Schleife dagegen in ca. 4 Zyklen durch, sodass hier wohl die Latenz des addsd-Befehls von 4 Zyklen entscheidend ist: Dieser Befehl hängt vom Resultat des gleichen Befehls in der vorigen Iteration ab.
Das ist ein einfacher Fall einer recurrence, einer Kette von Datenabhängigkeiten in einer Schleife, durch die ein Befehl vom selben Befehl in der vorigen Iteration abhängt. Bei Schleifen mit vielen Iterationen bestimmt die Recurrence mit der längsten Gesamtlatenz die minimalen Zyklen pro Iteration (bei wenigen Iterationen kann die out-of-order execution noch etwas ausgleichen). Die anderen Recurrences in dieser Schleife, je eine pro add-Befehl, haben nur einen Zyklus Latenz.
Bevor wir uns dem Problem der Speicheroptimierung zuwenden (die das Programm etwas unhandlicher machen wird), eliminieren wir zunächst die recurrence durch addsd (und betrachten zunächst nur die 500x500-Variante): Statt ein Element des Resultats auf einmal auszurechnen, berechnen wir alle Elemente der ersten Zeile des Resultats stückweise.
Als ersten Schritt speichern wir das Zwischenresultat nicht in r, sondern im Zielelement von c:
c[i*p+j] += a[i*m+k]*b[k*p+j];Dadurch wird im Ursprungsprogramm die recurrence zwar noch länger (und das Programm langsamer), aber man kann die Instanzen dieser Anweisung jetzt beliebig umordnen: Diejenigen, die auf verschiedene Elemente von c zugreifen, sowieso, und diejenigen, die auf das selbe Element zugreifen, aufgrund des Assoziativgesetzes der Addition (das gilt für Gleitkommaaddition nur näherungsweise, aber da wir schon im Originalprogramm nur eine Näherung des genauen Resultats produzieren, ist das in diesem Fall akzeptabel).
Dazu tauschen wir im Prinzip die innere und die mittlere Schleife aus, und müssen die Zwischenergebnisse der Berechnung dann im Speicher zwischenspeichern. Das Ergebnis ist mm2.c. Die innere Schleife schaut, mit -O2 compiliert, jetzt so aus:
for (j=0; j<p; j++)
c[i*p+j] += a[i*m+k]*b[k*p+j];
5.35 |70: movsd 0x0(%rbp,%rsi,8),%xmm0
22.22 | mulsd (%r10,%rax,8),%xmm0
11.32 | addsd (%rdx,%rax,8),%xmm0
35.22 | movsd %xmm0,(%rdx,%rax,8)
23.27 | add $0x1,%rax
2.20 | cmp %rax,%r9
| jne 70
Die Performance-counter-Resultate sind:
mm2-O2 500
392351753 cycles
888069827 instructions # 2.26 insns per cycle
263770 branch-misses
1538561 offcore_response_all_data_rd_llc_miss_dram
377404137 L1-dcache-loads
15921657 L1-dcache-load-misses # 4.22% of all L1-dcache hits
479594 LLC-loads
15398976 LLC-prefetches
377392786 dTLB-loads
20231 dTLB-load-misses # 0.01% of all dTLB cache hits
Die Zahl der Befehle hat sich zwar kaum geändert (beide inneren
Schleifen haben 7 Befehle/Iteration), die Zahl der Zyklen ist aber um
den Faktor 1.39 gesunken, und die innere Schleife braucht jetzt ca. 3
Zyklen/Iteration. Weiters ist noch die Anzahl der D-cache misses um
den Faktor 7 gesunken: der Zugriff auf die Elemente von b erfolgt
jetzt sequentiell, sodass die Cache lines (64 Bytes, also 8 Elemente)
gut ausgenutzt werden, im Gegensatz zu mm1.
In dieser Version ist jede Iteration der inneren Schleife
unabhängig von den anderen, ideale Voraussetzungen für
Parallelisierung und Vektorisierung. Und mit -O3 vektorisiert gcc-5.4
den Code automatisch. Da der Prozessor AVX (256-bit Vektoren)
unterstützt, aktivieren wir das auch gleich mit (gcc -O3
-mavx).
6.43 |1d7: vmovup (%r15,%rsi,1),%xmm0
11.24 | add $0x1,%r11
2.41 | mov -0x68(%rbp),%rax
3.41 | vinser $0x1,0x10(%r15,%rsi,1),%ymm0,%ymm0
15.26 | vmulpd %ymm1,%ymm0,%ymm0
5.42 | vaddpd (%rax,%rsi,1),%ymm0,%ymm0
35.74 | mov -0x70(%rbp),%rax
3.82 | vmovap %ymm0,(%rax,%rsi,1)
12.25 | add $0x20,%rsi
2.61 | cmp -0x60(%rbp),%r11
| jb 1d7
Auch wenn der Code nicht besonders toll ist, ist durch die
Vektorisierung die Anzahl der Iterationen um den Faktor 4 gesunken,
und der Code entsprechend schneller:
mm2 500
180113115 cycles
365281243 instructions # 2.03 insns per cycle
264519 branch-misses
738836 offcore_response_all_data_rd_llc_miss_dram
192374945 L1-dcache-loads
15905883 L1-dcache-load-misses # 8.27% of all L1-dcache hits
1303267 LLC-loads
14905503 LLC-prefetches
192376408 dTLB-loads
15181 dTLB-load-misses # 0.01% of all dTLB cache hits
Diese Auto-Vektorisierung hat den Code um den Faktor 2.12 schneller
gemacht. Die Anzahl der D-cache misses ist gleich geblieben (es
werden ja immer noch die Zeilen der Vektoren sequentiell gelesen),
aber da die Anzahl der Loads reduziert wurde, ist der Anteil der
misses jetzt größer.
Eventuell können wir durch manuelle Vektorisierung mit Hilfe der GNU C Vector Extensions die Geschwindigkeit noch steigern: mm3.c. Dabei verwenden wir Vektoren mit vier doubles, passend zu den AVX-Befehlen, bei größeren Vektor-Längen generiert gcc schlechten Code. Das Ergebnis schaut besser aus:
|80: vbroad (%r12,%rsi,8),%ymm0
11.02 | vmulpd (%r9,%rax,1),%ymm0,%ymm0
41.63 | vaddpd (%rdx,%rax,1),%ymm0,%ymm0
25.92 | vmovap %ymm0,(%rdx,%rax,1)
13.67 | add $0x20,%rax
7.35 | cmp %rax,%rdi
| jne 80
benötigt deutlich weniger Befehle, und läuft auch etwas (Faktor 1.06)
schneller.
mm3 500
170711879 cycles
231813320 instructions # 1.36 insns per cycle
264335 branch-misses
532507 offcore_response_all_data_rd_llc_miss_dram
96216732 L1-dcache-loads
15952462 L1-dcache-load-misses # 16.58% of all L1-dcache hits
3279321 LLC-loads
13719589 LLC-prefetches
99373015 dTLB-loads
31561 dTLB-load-misses # 0.03% of all dTLB cache hits
Bei diesem Code fällt auf, dass der erste Befehl (Zugriff
auf das Element von a) in jeder Iteration das gleiche Ergebnis
liefert, was der Compiler aber offenbar nicht optimiert. Also machen
wir das händisch: mm4.c.
double aik = a[i*m+k];
for (j=0; j<p; j++)
c[i*p+j] += aik*b[k*p+j];
|a0: vmulpd (%rsi,%rax,1),%ymm1,%ymm0
59.48 | vaddpd (%rdx,%rax,1),%ymm0,%ymm0
21.77 | vmovap %ymm0,(%rdx,%rax,1)
17.46 | add $0x20,%rax
0.65 | cmp %rax,%r9
| jne a0
Der resultierende Code führt zwar weniger Befehle aus, ist aber nicht
nennenswert schneller:
mm4 500
168654314 cycles
201357678 instructions # 1.19 insns per cycle
263821 branch-misses
587776 offcore_response_all_data_rd_llc_miss_dram
65201141 L1-dcache-loads
15945752 L1-dcache-load-misses # 24.46% of all L1-dcache hits
2832521 LLC-loads
14149188 LLC-prefetches
65208359 dTLB-loads
34264 dTLB-load-misses # 0.05% of all dTLB cache hits
Eventuell läuft der Code schon in Begrenzungen wie z.B. die Bandbreite
zum L2 oder L3-cache.
Schauen wir uns jetzt wieder den Fall 700x700 an:
mm4 700
522556081 cycles
539783665 instructions # 1.03 insns per cycle
506069 branch-misses
26036094 offcore_response_all_data_rd_llc_miss_dram
176699150 L1-dcache-loads
43675603 L1-dcache-load-misses # 24.72% of all L1-dcache hits
26831980 LLC-loads
27657539 LLC-prefetches
176682383 dTLB-loads
729519 dTLB-load-misses # 0.41% of all dTLB cache hits
mm4 ist für diesen Fall 15 mal schneller als mm1 (für den 500x500-Fall
3 mal). Schon mm2-O2 (keine Vektorisierung) ist 7 mal so schnell. Da
sowohl mm1 als auch alle folgenden Versionen in der mittleren und
inneren Schleife die b-Matrix komplett lesen (bei den anderen Matrizen
greifen sie nur auf eine einzige Zeile oder Spalte zu), ist die Anzahl
der Hauptspeicherzugriffe nicht so weit auseinander, wie man an den
offcore_response_all_data_rd_llc_miss_dram-Resultaten sieht. [Die
Beschreibung dieses Events ist: "Counts all demand & prefetch data
reads that miss the LLC and the data returned from dram". Zum
Ermitteln dieses Events verwendete ich ocperf.py,
das mehr Events kennt als perf.]
Daher sind die Hauptspeicherzugriffe nicht für den großen Geschwindigkeitsunterschied zwischen mm1 und mm4 bei 700x700 verantwortlich.
Was sonst erklärt den Unterschied? Ein auffälliger Unterschied zwischen mm1 und mm4 ist die grosse Anzahl der dTLB misses in mm1 700 (einer alle 24 Zyklen), während bei mm1 500 viel weniger dTLB misses passieren. mm1 hat auch einen höheren Anteil an L1 cache misses, aber wenn wir uns den 500x500-Fall anschauen, hat das offenbar in diesem Programm keine grosse Auswirkung, weil die Latenz der Ladebefehle sich nicht im kritischen Berechnungspfad befindet. Wenn ein dTLB miss ~20 Zyklen kostet (was durchaus realistisch ist), erklärt das den Unterschied schon.
Warum hat mm1 bei 700x700 so viele TLB misses, bei 500x500 nicht, und warum haben die anderen Versionen auch wenige TLB misses? mm1 700x700 greift in der inneren Schleife auf die Elemente eine Spalte der b-Matrix zu, greift also mit einer Schrittweite von 700*8=5600 Bytes auf diese Elemente zu; da die Seitengröße 4096 beträgt, braucht jeder Elementzugriff einen eigenen TLB-Eintrag. Da die Ivy Bridge-CPU 512 L2-TLB-Einträge hat, werden diese TLB-Einträge bei 700x700 nicht wiederverwendet (capacity miss), bei 500x500 dagegen schon.
mm2 und folgende greifen auf die Daten sequentiell zu, was überhaupt günstig für den TLB ist: jeder TLB-Eintrag deckt 512 sequentielle Elemente ab.
Bei meinen ersten Versuchen erhielt ich immer die langsamen Resultate für mm1 700, später dann oft 4 mal schnellere Resultate mit deutlich weniger dTLB misses. Das ist vermutlich auf die Verwendung von großen Seiten durch das Betriebssystem zurückzuführen. Als ich das mit
#als root echo never > /sys/kernel/mm/transparent_hugepage/enabledabgestellt habe, ergaben sich immer die langsamen Resultate. Umgekehrt kann man bei Problemen mit TLB misses auf verschiedene Arten große Seiten explizit verwenden, sodass man nicht auf Glück angewiesen ist, um sie zu bekommen.
Der nächste Schritt (mm5.c) reduziert die Anzahl der Lese- und Schreib-Operationen auf c, indem die mittlere Schleife um den Faktor 4 entrollt wird, aber das Unrolling auf den Inhalt der inneren Schleife angewandt wird (man kann es auch als Kombination von Loop Interchange und Loop Unrolling sehen):
for (k=0; k<m; k+=4) {
double aik0 = a[i*m+k+0];
double aik1 = a[i*m+k+1];
double aik2 = a[i*m+k+2];
double aik3 = a[i*m+k+3];
for (j=0; j<p; j++) {
v4d r;
r = aik0*b[(k+0)*p+j];
r += aik1*b[(k+1)*p+j];
r += aik2*b[(k+2)*p+j];
r += aik3*b[(k+3)*p+j];
c[i*p+j] += r;
}
}
14.58 | f0: vmulpd (%r9,%rax,1),%ymm4,%ymm1
7.87 | vmulpd (%rsi,%rax,1),%ymm5,%ymm0
5.54 | vaddpd %ymm0,%ymm1,%ymm0
11.66 | vmulpd (%rdi,%rax,1),%ymm3,%ymm1
8.75 | vaddpd %ymm0,%ymm1,%ymm0
14.87 | vmulpd (%r10,%rax,1),%ymm2,%ymm1
13.12 | vaddpd %ymm0,%ymm1,%ymm0
16.62 | vaddpd (%rdx,%rax,1),%ymm0,%ymm0
4.66 | vmovap %ymm0,(%rdx,%rax,1)
| add $0x20,%rax
| cmp %rax,%r8
2.04 | jne f0
Das Ergebnis ist um den Faktor 1.41 schneller:
mm5 500
119689365 cycles
106239905 instructions # 0.89 insns per cycle
76017 branch-misses
714395 offcore_response_all_data_rd_llc_miss_dram
41773156 L1-dcache-loads
16121145 L1-dcache-load-misses # 38.59% of all L1-dcache hits
8485471 LLC-loads
11168943 LLC-prefetches
41766213 dTLB-loads
31007 dTLB-load-misses # 0.07% of all dTLB cache hits
Um festzustellen, wieviel durch Speicherzugriffsoptimierung maximal zu
holen ist, oder ob wir schon an den Grenzen des CPU-Kerns anstehen,
wird mit limit1.c eine Variante getestet, bei
dem die innere Schleife immer auf den gleichen Speicherbereich
zugreift, und damit im L1-Cache bleibt (bei den von uns verwendeten
Grössen). Dabei ergeben sich relativ grosse Schwankungen, eines der
besseren Resultate ist:
limit1 620
98537134 cycles
212526062 instructions # 2.16 insns per cycle
110825 branch-misses
65077 offcore_response_all_data_rd_llc_miss_dram
78562067 L1-dcache-loads
799246 L1-dcache-load-misses # 1.02% of all L1-dcache hits
88883 LLC-loads
23823 LLC-prefetches
78560372 dTLB-loads
7452 dTLB-load-misses # 0.01% of all dTLB cache hits
Da wir hier dieselbe innere Schleife, aber eine andere Größe verwenden
als bei mm5 500, vergleicht man am besten die insns per cycle (IPC).
Hier sieht man, dass Speicheroptimierungen einiges bringen können.
Aber bevor wir uns dem zuwenden, optimieren wir die innere Schleife noch weiter (limit2.c); bei der aktuellen inneren Schleife werden immer 256bits aus b geladen, multipliziert, addiert, und zu c dazugezählt. Wenn man mit Werten von a aus zwei Zeilen multiplizieren würde (also die äussere Schleife um den Faktor 2 entrollen würde), könnte man die geladenen Werte aus b wiederverwenden und so die Anzahl der Loads reduzieren:
double ai0k0 = a[(i+0)*m+k+0];
double ai0k1 = a[(i+0)*m+k+1];
double ai0k2 = a[(i+0)*m+k+2];
double ai0k3 = a[(i+0)*m+k+3];
double ai1k0 = a[(i+1)*m+k+0];
double ai1k1 = a[(i+1)*m+k+1];
double ai1k2 = a[(i+1)*m+k+2];
double ai1k3 = a[(i+1)*m+k+3];
for (j=0; j<p; j++) {
v4d bk0j = b[(k+0)*p+j];
v4d bk1j = b[(k+1)*p+j];
v4d bk2j = b[(k+2)*p+j];
v4d bk3j = b[(k+3)*p+j];
v4d ci0j = ai0k0*bk0j+ai0k1*bk1j+ai0k2*bk2j+ai0k3*bk3j;
v4d ci1j = ai1k0*bk0j+ai1k1*bk1j+ai1k2*bk2j+ai1k3*bk3j;
c[(i+0)*p+j] += ci0j;
c[(i+1)*p+j] += ci1j;
}
5.54 | b0: vmovap (%rsi,%rax,1),%ymm0
1.48 | vmovap (%r8,%rax,1),%ymm1
4.43 | vmulpd %ymm11,%ymm0,%ymm2
| vmovap (%rdi,%rax,1),%ymm13
4.43 | vmovap (%r10,%rax,1),%ymm12
0.37 | vmulpd %ymm10,%ymm1,%ymm3
8.86 | vmulpd %ymm6,%ymm1,%ymm1
0.37 | vaddpd %ymm3,%ymm2,%ymm3
3.32 | vmulpd %ymm9,%ymm13,%ymm2
| vaddpd %ymm2,%ymm3,%ymm3
4.06 | vmulpd %ymm8,%ymm12,%ymm2
3.69 | vaddpd %ymm2,%ymm3,%ymm3
21.03 | vaddpd (%rdx,%rax,1),%ymm3,%ymm3
7.01 | vmovap %ymm3,(%rdx,%rax,1)
2.95 | vmulpd %ymm7,%ymm0,%ymm3
| vmulpd %ymm5,%ymm13,%ymm0
7.38 | vaddpd %ymm1,%ymm3,%ymm2
| vaddpd %ymm0,%ymm2,%ymm1
1.85 | vmulpd %ymm4,%ymm12,%ymm0
| vaddpd %ymm0,%ymm1,%ymm0
11.44 | vaddpd (%rcx,%rax,1),%ymm0,%ymm0
4.43 | vmovap %ymm0,(%rcx,%rax,1)
5.17 | add $0x20,%rax
| cmp %rax,%r9
| jne b0
Das Ergebnis ist eine weitere leichte (Faktor 1.12) Verbesserung
(diesmal wieder die Zyklen vergleichen, die Größe ist gleich, dafür
die Schleife verschieden):
limit2 620
87871273 cycles
204003567 instructions # 2.32 insns per cycle
62162 branch-misses
66178 offcore_response_all_data_rd_llc_miss_dram
52552935 L1-dcache-loads
1441947 L1-dcache-load-misses # 2.74% of all L1-dcache hits
86066 LLC-loads
23600 LLC-prefetches
48666220 dTLB-loads
6135 dTLB-load-misses # 0.01% of all dTLB cache hits
Da mm5 offenbar für 500x500 und 700x700 vom Speichersystem deutlich
gebremst wird, werden Speicheroptimierungen voraussichtlich etwas
bringen.
Bei der Matrizenmultiplikation wird ja je nach Organisation auf die diversen Elemente der Matrix mehrfach im Speicher zugegriffen. Bei der in mm5 700 gewählten Organisation wird auf jedes Element von a ein mal, auf jedes Element von b 700 mal, und auf jedes Element von c 700/4 mal zugegriffen, wobei bei c die 175 Zugriffe auf eine Zeile erfolgen, bevor die nächste Zeile drankommt (zeitliche Lokalität).
In limit2 wird dagegen ein Element von b mit zwei Elementen von a multipliziert, und eine darauf aufbauende Organisation würde die Anzahl der Speicherzugriffe auf b halbieren. Wenn man das ins Extrem treibt, und jedes Element von b nur einmal aus dem Speicher lädt (indem die i-Schleife zur inneren Schleife wird), muss man dafür jedes Element von a 700 mal aus dem Speicher laden (und zwar noch in einer Cache- und TLB-feindlichen Art), und auch jedes Element von c muss 700 mal aus dem Speicher geladen werden und wieder zurückgeschrieben werden, ebenfalls in einer Cache-feindlichen Art.
Durch einfachen loop interchange geht es also nicht, man muss auch Elemente von a bzw. c wiederverwenden, bevor sie aus dem Cache fliegen. Wir können r Elemente von a mit s Elementen von b Multiplizieren, sodass diese r+s Elemente in einen bestimmten Cache-Level passen, und dabei r*s der notwendigen Multiplikationen erledigen (also r-mal weniger Hauptspeicherzugriffe auf b nötig sind als bei mm5); durch geeignete Wahl dieser Elemente kann man auch die Zugriffe auf c gering halten.
Man kann dieses Cache-Blocking auf die Cache-Größe abstimmen, was angesichts von drei Cache-Levels auf der Zielmaschine recht kompliziert wäre. Daher verwenden wir als Alternative einen rekursiven Algorithmus, der in jedem Schritt eine Dimension der Matrizen halbiert und damit die Wiederverwendung auf vielen Ebenen betreibt, von denen einige auf die Cache-Größen passen werden.
Wikipedia empfielt dafür, dass man in allen drei Indizes die Größe halbiert. Ich entschied mich jedoch dafür, lieber die innere (j-)Schleife in voller Länge zu erhalten, weil für unsere Problemgrößen die Daten für eine Iteration (700*4 Elemente, also 22400 Bytes) noch in den L1-Cache passen und der Overhead der Rekursion in dieser Dimension voraussichtlich eine größere Rolle spielen würde. Daher halbiert meine Lösung in jedem Schritt nur den Bereich der Indizes i und k. Das Ergebnis (bei Verwendung der inneren Schleife von mm5/limit1) ist mm6.c.
mm6 500
80226640 cycles
114881301 instructions # 1.43 insns per cycle
94443 branch-misses
185095 offcore_response_all_data_rd_llc_miss_dram
42020170 L1-dcache-loads
5943632 L1-dcache-load-misses # 14.14% of all L1-dcache hits
750481 LLC-loads
1217332 LLC-prefetches
42012886 dTLB-loads
17517 dTLB-load-misses # 0.04% of all dTLB cache hits
Durch Verwendung der inneren Schleife von limit2 ergibt sich mm7.c und folgendes Ergebnis:
mm7 500
65259545 cycles
118610774 instructions # 1.82 insns per cycle
47196 branch-misses
173685 offcore_response_all_data_rd_llc_miss_dram
26424090 L1-dcache-loads
6118630 L1-dcache-load-misses # 23.16% of all L1-dcache hits
904561 LLC-loads
1307343 LLC-prefetches
26417507 dTLB-loads
14207 dTLB-load-misses # 0.05% of all dTLB cache hits
Das ist 8.8 mal schneller als mm1. Bei 700x700 ist das Ergebnis 44
mal schneller als mm1:
mm7 700
181139530 cycles
314590731 instructions # 1.74 insns per cycle
89830 branch-misses
607075 offcore_response_all_data_rd_llc_miss_dram
70001888 L1-dcache-loads
24912916 L1-dcache-load-misses # 35.59% of all L1-dcache hits
3827399 LLC-loads
4830259 LLC-prefetches
70032725 dTLB-loads
37095 dTLB-load-misses # 0.05% of all dTLB cache hits
Diese für das Speichersystem optimierten Varianten sind auch besser
fuer die Parallelisierung geeignet. Statt diese Programme jetzt
tatsächlich zu parallelisieren, schauen wir einfach, wie lange sie
brauchen, wenn man 2 bzw. 4 von ihnen auf der Zielhardware (mit 2
Cores und (per Hyperthreading) 4 threads laufen läßt, z.B. mit diesem
Befehl:
perf stat -r 100 -e cycles -e instructions mm5 700 >/dev/null 2>/dev/null & perf stat -r 90 -e cycles -e instructions mm5 700Für 700x700-Matrizen ergibt das folgende Zyklenzahlen pro Ausführung:
1 2 4 gleichzeitige Ausführungen
403.330.094 846.376.818 1.882.081.370 mm5 700
180.441.876 204.305.921 406.841.878 mm7 700
Eine Zweifach-Parallelisierung von mm5 würde sich auf dieser Hardware
offenbar nicht auszahlen, weil sich die Laufzeit jedes Threads mehr
als verdoppeln würde. Bei Vierfach entsprechend. Bei mm7 ist von
einer Zweifach-Parallelisierung dagegen eine gute Beschleunigung zu
erwarten; Hyperthreading würde zwar hier nichts bringen, aber auch
nicht schaden (doppelt so viele Threads, die halb so schnell wären).
Noch ein Vergleich mit zwei ernsthaften Implementierungen der BLAS-Routine DGEMM:
atlas 700
220709112 cycles
622853379 instructions # 2.82 insns per cycle
58938 branch-misses
1047615 offcore_response_all_data_rd_llc_miss_dram
185087891 L1-dcache-loads
5254856 L1-dcache-load-misses # 2.84% of all L1-dcache hits
388303 LLC-loads
1772143 LLC-prefetches
185111573 dTLB-loads
26917 dTLB-load-misses # 0.01% of all dTLB cache hits
openblas 700 #nur ein core und thread
117681171 cycles
289004803 instructions # 2.46 insns per cycle
28695 branch-misses
520477 offcore_response_all_data_rd_llc_miss_dram
50593095 L1-dcache-loads
11867478 L1-dcache-load-misses # 23.46% of all L1-dcache hits
7422120 LLC-loads
7992466 LLC-prefetches
50578398 dTLB-loads
42115 dTLB-load-misses # 0.08% of all dTLB cache hits
Atlas ist um den Faktor 1.22 langsamer als mm7, OpenBLAS dagegen um
den Faktor 1.54 schneller. Bei den Events gibt es auch Unterschiede,
die auf deutliche Unterschiede in der Implementierung deuten.
Openblas kann auch mehrere Threads nutzen (mit der environment
variable OMP_NUM_THREADS, oder durch Abschalten von
threads):
Openblas 700 0.067s 1 core 1 thread 0.075s 1 core 2 threads 0.042s 2 cores 1 thread/core 0.048s 2 cores 2 threads/coreDie Verwendung eines zweiten Cores resultiert in einer Beschleunigung um den Faktor 1.6, die Verwendung von Hyperthreading allerdings in einer Verlangsamung; offenbar nutzt schon ein Thread die CPU gut aus, und zwei auf dem gleichen Core steigen sich gegenseitig auf die Füße.
| Name | Last modified | Size | Description |
|---|---|---|---|---|
| Parent Directory | - | ||
| Makefile | 11-Feb-2021 00:42 | 1.3K | |
| atlas | 10-Feb-2021 17:40 | 17K | |
| blas | 11-Feb-2021 14:12 | 24M | |
| limit1 | 10-Feb-2021 17:40 | 17K | |
| limit1.c | 16-Nov-2017 14:24 | 563 | |
| limit1.o | 10-Feb-2021 17:40 | 1.3K | |
| limit1a.c | 15-Nov-2017 13:25 | 454 | |
| limit1a.o | 10-Feb-2021 17:40 | 1.6K | |
| limit2 | 10-Feb-2021 17:40 | 17K | |
| limit2.c | 15-Nov-2017 19:09 | 865 | |
| limit2.o | 10-Feb-2021 17:40 | 1.4K | |
| limit2a.c | 15-Nov-2017 19:02 | 455 | |
| limit2a.o | 10-Feb-2021 17:40 | 1.6K | |
| limit3 | 10-Feb-2021 17:40 | 17K | |
| limit3.c | 16-Nov-2017 11:44 | 945 | |
| limit3.o | 10-Feb-2021 17:40 | 1.4K | |
| limit3a.c | 15-Nov-2017 19:02 | 455 | |
| limit3a.o | 10-Feb-2021 17:40 | 1.6K | |
| main.c | 01-Dec-2017 19:40 | 1.3K | |
| main.o | 10-Feb-2021 17:40 | 3.6K | |
| mainblas.c | 03-Dec-2017 18:56 | 1.4K | |
| mainblas.o | 10-Feb-2021 17:40 | 3.7K | |
| matmul.500 | 07-Nov-2017 15:42 | 1.9M | |
| matmul.700 | 05-Nov-2017 23:58 | 3.7M | |
| matmul.out | 30-Jul-2022 14:47 | 275M | |
| mm1 | 10-Feb-2021 17:40 | 17K | |
| mm1.c | 06-Nov-2017 12:15 | 268 | |
| mm1.o | 10-Feb-2021 17:40 | 1.5K | |
| mm2 | 10-Feb-2021 17:40 | 17K | |
| mm2-O2 | 10-Feb-2021 17:40 | 17K | |
| mm2-O2.o | 10-Feb-2021 17:40 | 1.6K | |
| mm2.c | 07-Nov-2017 16:21 | 296 | |
| mm2.o | 10-Feb-2021 17:40 | 2.0K | |
| mm3 | 10-Feb-2021 17:40 | 17K | |
| mm3.c | 07-Nov-2017 17:28 | 420 | |
| mm3.o | 10-Feb-2021 17:40 | 1.6K | |
| mm4 | 10-Feb-2021 17:40 | 17K | |
| mm4.c | 07-Nov-2017 17:46 | 452 | |
| mm4.o | 10-Feb-2021 17:40 | 1.6K | |
| mm5 | 10-Feb-2021 17:40 | 17K | |
| mm5.c | 15-Nov-2017 12:40 | 694 | |
| mm5.o | 10-Feb-2021 17:40 | 1.8K | |
| mm6 | 10-Feb-2021 17:40 | 17K | |
| mm6.c | 16-Nov-2017 13:49 | 1.6K | |
| mm6.o | 10-Feb-2021 17:40 | 2.4K | |
| mm7 | 10-Feb-2021 17:40 | 17K | |
| mm7.c | 17-Nov-2017 19:35 | 1.9K | |
| mm7.o | 10-Feb-2021 17:40 | 2.5K | |
| mm8 | 10-Feb-2021 17:40 | 17K | |
| mm8.c | 17-Nov-2017 19:54 | 2.1K | |
| mm8.o | 10-Feb-2021 17:40 | 2.4K | |
| mm9 | 10-Feb-2021 17:40 | 17K | |
| mm9.c | 16-Nov-2017 13:47 | 1.9K | |
| mm9.o | 10-Feb-2021 17:40 | 2.5K | |
| mma | 10-Feb-2021 17:40 | 17K | |
| mma.c | 08-Feb-2021 14:45 | 2.6K | |
| mma.o | 10-Feb-2021 17:40 | 2.4K | |
| mmb | 11-Feb-2021 23:57 | 9.9K | |
| mmb.c | 10-Feb-2021 15:35 | 1.4K | |
| mmb.o | 10-Feb-2021 17:40 | 2.3K | |
| mmbj.o | 10-Feb-2021 17:40 | 1.5K | |
| mmbj.s | 10-Feb-2021 15:35 | 2.0K | |
| mmc | 11-Feb-2021 23:57 | 9.9K | |
| mmc.o | 11-Feb-2021 14:08 | 1.5K | |
| mmc.s | 11-Feb-2021 00:42 | 2.0K | |
| perf.data | 10-Feb-2021 16:38 | 447K | |
| perf.data.old | 03-Dec-2017 19:03 | 112K | |