Summe schneller machen?

nevermore

rapso schrieb:

nevermore schrieb:

Ethon schrieb:

nevermore schrieb:

Wenn du nur einen Akkumulator verwendest könnte das schlecht für das Pipelining der CPU sein. Ethon's Ansatz mit mehreren Akkumulatoren (also r+=... s+=... t+=... und return r+s+t statt nur auf r zu addieren) könnte noch was bringen (zusätzlich zu SSE & Co).

Müsste man dabei aber nicht aufpassen nicht mehr Akkumulatoren zu verwenden als freie Register zur Verfügung stehen? Ich denke da ist jeder Compiler zu schlau, aber angenommen ein Akkumulator lebt als Stackvariable dann wäre das fatal.

Moderne CPUs haben mehr Register als über den Befehlssatz benutzt werden können, die Technik nennt sich "Register Renaming".

diese werden aber fuer die OOO ausfuehrung benutzt, nicht dafuer um register spilling abzufangen. wenn du also mehr variablen nutzt als register frei sind, wird deine cpu diese in den speicher schreiben, weil...

der compiler der cpu nicht mitteilen kann, dass diese memory writes nur auslagerungen sind

die cpu nicht annehmen darf dass irgend ein write unterlassen werden koennte vor einem read (der ja zwangslaeufig folgen wird wenn zuviele temporaries fuer das register set da sind).

Okay, stimmt.

@nevermore
ja das koennte schlecht sein, aber an sich sollte das bei einem add kein problem sein.

Ich glaube schon, dass das was bringt -- wenn die Daten in den Cache passen und das ganze nicht durch die Speicheranbindung limitiert ist.

Was ich mir schon vorstellen könnte ist, dass bei einem Integer der Compiler selber mehrere Akkumulatoren nutzt. Bei Floating Point vermutlich nicht, das könnte ja potenziell das Ergebnis abändern.

otze

Ethon schrieb:

Summe mit mehreren Kernen? Da ist doch sowieso der Speicher der Flaschenhals, ein Kern allein kann doch schon die komplette Speicherbandbreite ausnutzen.

Wie ist es da eigentlich genau: Wenn ich ein Programm hab, bei dem der Speicher der Flaschenhals ist, dann macht es auch keinen Sinn mehr, dieses Programm mehrfach (mit verschiedenen Parametern etc) parallel zu starten, weil der Speicher eben bereits am limit ist und sich die Programme gegenseitig die Bandbreite klaun. oder? Oder gibt s da vielleicht inzwischen auch so etwas wie Parallelisierung?

Ethon

otze schrieb:

Ethon schrieb:

Summe mit mehreren Kernen? Da ist doch sowieso der Speicher der Flaschenhals, ein Kern allein kann doch schon die komplette Speicherbandbreite ausnutzen.

Wie ist es da eigentlich genau: Wenn ich ein Programm hab, bei dem der Speicher der Flaschenhals ist, dann macht es auch keinen Sinn mehr, dieses Programm mehrfach (mit verschiedenen Parametern etc) parallel zu starten, weil der Speicher eben bereits am limit ist und sich die Programme gegenseitig die Bandbreite klaun. oder? Oder gibt s da vielleicht inzwischen auch so etwas wie Parallelisierung?

Ich denke es könnte schneller sein einen großen Speicherbereich in den CPU-Cache zu laden als ihn in kleineren Stückchen (1-16 Byte) einzulesen.
Mit mehreren CPUs hat man auch mehr Cache. Aber ich habe nicht viel Ahnung davon ...

rapso

SeppJ schrieb:

Kannst du auch noch eine kurze Version mit mehreren Threads bauen? Ich bin nicht so gut mit den C-Threads, kann nur C++ . Aber die CPU-Hersteller hätten so gerne, dass man alle Kerne voll ausnutzt, sollen sie mal zeigen was besser ist: SSE oder mehr Kerne? :xmas1:

an sich ganz einfach, vor der inneren schleife

#pragma omp parallel for

eventuel musst du das uint32_t in ein int umwandeln, je nachdem wie penibel der compiler ist.

@Ethon
koennte mir vorstellen, dass vielleicht turbo boost ein wenig mit reinspielt, gerade mobile cpus takten sehr weit runter (manchmal <0.8Ghz) und dann hoch auf 3GHz+ um dann festzustellen es ist zuviel des guten und danng ehen die wieder auf <2GHz. vielleicht ganz oben den loop counter weiter hochdrehen, dann laeuft der test insgesammt laenger, aber die GIntop/s sollten stabil bleiben.
Vielleicht auch die anderen gcc flags probieren, O3 macht nicht alles, und gcc ist sehr penibel was z.b. restrict usw angeht, vielleicht unrollt es deswegen nicht.

otze schrieb:

Ethon schrieb:

Summe mit mehreren Kernen? Da ist doch sowieso der Speicher der Flaschenhals, ein Kern allein kann doch schon die komplette Speicherbandbreite ausnutzen.

Wie ist es da eigentlich genau: Wenn ich ein Programm hab, bei dem der Speicher der Flaschenhals ist, dann macht es auch keinen Sinn mehr, dieses Programm mehrfach (mit verschiedenen Parametern etc) parallel zu starten, weil der Speicher eben bereits am limit ist und sich die Programme gegenseitig die Bandbreite klaun. oder? Oder gibt s da vielleicht inzwischen auch so etwas wie Parallelisierung?

das stimmt zu 50%
wenn du linear speicher liest, bist du an sich nur durchsatz limitiert und moderne cpus haben bei einem core locker genug leistung um am speicher zu saturieren (die benchmarks die memory performance messen laufen entsprechend nur auf einem core). wenn man sich zudem SSE oder AVX bedient, dann ziehen die cpus ziemlich genau am limit vom L1 cache.
-Nahalem: 16byte/cycle -> SSE breite
-sandy bridge: 32byte/cycle -> avx breite
-haswell wird 64byte/cycle leisten -> avx mit FMA, bei fma3 brauchst du pro takt zwei avx quellregister, fma wuerde nichts bringen ohne die doppelte bandbreite, weil man sonst entweder trotzdem nur alle 2 cycles ein fma befuellen kann oder nur lokal auf registern FMAs machen koennte (die benchmarks ala linpack machen das nicht).

64byte/cycle bei 3GHz-4GHz -> 200GB/s bis 250GB/s pro core, bei 4 bis 6 cores hast du entsprechend bis 1.5TB/s bandwidth... ein quad channel prozessor von intel schaft ca 50GB/s.

also ja, ein core kann saturieren.

man muss random reads beachten, dabei saturiert man am zugriff selbst, nicht an der bandbreite, man kann also ein paar cache hits lang arbeiten udn dann wieder wartet der core, in dem fall bietet sich hyper threading sehr an, da der andere thread seine cache hits nutzen kann waehrend der erste stallt. (hab in manchen faellen 30% geschwindigkeitzuwachs durch hyperthreading). man kann sich durch cache polution aber natuerlich die threads auch zerballern und dann ist hyperthreading kontraproduktiv.

Ethon schrieb:

Ich denke es könnte schneller sein einen großen Speicherbereich in den CPU-Cache zu laden als ihn in kleineren Stückchen (1-16 Byte) einzulesen.
Mit mehreren CPUs hat man auch mehr Cache. Aber ich habe nicht viel Ahnung davon ...

cpus arbeiten eh auf cache lines, ob du 1 byte oder 16 laedst, es werden immer 32/64/128 bytes in den cache geladen, je nach cpu. die cache line breite entspricht der 'wort' breite vom ram, also auch wenn man nur 1byte cachen wuerde, die speicherriegel liefern beim auslesen immer die gleiche menge zureuck.
man kann vielleicht an 'ports' limitiert sein von der load/store einheit. diese hat oft unabhaengig der speichermenge die man transferiert, eine fixe groesse. bei den aktuellen intel cpus sind es glaube ich 4 eintraege, schreibt/liest man also 4 einzelne bytes oder 4 mal 32byte, befuellt man diese queue gleich. diese einheit kuemmert sich auch drum unaligned reads durch zwei seperate reads + mergen der bytes zu emulieren.
ich denke das ist weshalb die sse version vielleicht leicht schneller ist. aber an sich sollte jeder i7 prozessor auf 20GB/s (bzw die 3820k 3930k und 3960x auf 50GB/s) kommen.

Ethon

Danke für die ausführlichen Antworten.

Loops mal auf 512 gestellt:

0 12.640s 5436.667MIntop/s 21746.670MB/s
       0 6.270s 10960.045MIntop/s 43840.180MB/s
       0 15.970s 4303.035MIntop/s 17212.141MB/s

Immer noch Manuelles loop unrolling > einfache variante > sse.

Welches Flags wären denn einen Versuch wert? Afaik sind bei O3 ja die ganzen aggressiven Optimierungen alle dabei.

rapso

laut http://ark.intel.com/products/53469/Intel-Core-i7-2670QM-Processor-6M-Cache-up-to-3_10-GHz

hat deine cpu 21.3 GB/s (hatte den benchmark in ner viertelstunde geschrieben deswegen nicht /1024 sondern /1000 geteilt, aber auch dann waerst du noch bei

0 12.640s 5436.667MIntop/s 20739.240MB/s
0 6.270s 10960.045MIntop/s 41809.253MB/s
0 15.970s 4303.035MIntop/s 16414.776MB/s

die 0 am anfang wirkt suspekt und die 41GB/s sind eindeutig ueber dem limit deiner cpu.

hmhmhm. hast du etwas am code modifiziert um es zum laufen zu bringen?

[edit]
bau mal mit -O2, vielleicht geht eine optimierung schief, O2 sollte recht sicher sein, imo.

Ethon

Jetzt ist es anders:

0 42.300s 1624.574MIntop/s 6498.295MB/s
       0 26.790s 2565.117MIntop/s 10260.467MB/s
       0 17.170s 4002.300MIntop/s 16009.198MB/s

Werde mir beide Versionen morgen mal im Decompiler ansehen.

bin gespannt auf den assembler dump, jetzt scheinen die werte viel zu niedrig zu sein.
in den ersten testlaeufen schien ja das ergebnis zu stimmen, muss also eine funky optimierung sein. assembler assembler assembler :xmas1:

SeppJ

raps schrieb:

muss also eine funky optimierung sein.

Das spricht doch auch für einen Code, wenn er sich gut vom Compiler optimieren lässt.

rapso

SeppJ schrieb:

raps schrieb:

muss also eine funky optimierung sein.

Das spricht doch auch für einen Code, wenn er sich gut vom Compiler optimieren lässt.

zweischneidig, entweder der code ist gut oder falsch und der compiler exploited border cases um optimierungen durchzufuehren z.b.

for(...)
{
*pMeinFloatPointer=...
if(*reinterpret_cast<int*>(pMeinFloatPointer)==0)
  break;
...
}

ich denke in VS wuerde es laufen wie man es sich vorstellt, in gcc mit -O0 auch, aber bei -O3 wird gcc annehmen dass das float-write und int-read nicht aliasen und koennte den float write sogar nur als registerwert zwischenspeichern und ausserhalb vom loop dann rausschreiben.
gut zu optimierbarer code, aber ein programmierfehler