PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Optimierungen der Collatz-App



Gipsel
12.07.2009, 14:49
Hab mal den Cuda Prozess auf Echtzeit gestellt. Die Wu war nach 397 sec fertig (6:37 min) Cputime376 sec. d.h. ein voller virtueller Kern (icore) hat die ganze Zeit Daten nachgeschoben. Denke in der App ist noch reichlich Luft drin.
Zum Vergleich, wenn alles so klappt, wie ich mir das vorstelle, wird eine HD4870 zukünftig vielleicht sogar in 4-5 Minuten fertig sein ;D
Aber erst mal sehen, ob ich dafür Zeit finde. Bei der Gelegenheit werde ich wohl auch gleich mal eine deutlich schnellere CPU-Version basteln müssen, damit die Credits nicht total überhand nehmen.

heavy-Ions@boinc
12.07.2009, 15:49
Zum Vergleich, wenn alles so klappt, wie ich mir das vorstelle, wird eine HD4870 zukünftig vielleicht sogar in 4-5 Minuten fertig sein ;D
Aber erst mal sehen, ob ich dafür Zeit finde. Bei der Gelegenheit werde ich wohl auch gleich mal eine deutlich schnellere CPU-Version basteln müssen, damit die Credits nicht total überhand nehmen.
wenn du dann zeit hast denk auch noch mal über das andere projekt nach ;) ;D

Gipsel
13.07.2009, 02:27
Da hat irgendwer mit unauthorisierten Anwendungen gerechnet (ich war's nicht), was jetzt unterbunden werden soll. Das wird es dann wohl ein wenig schwieriger machen, mal an meiner eigenen Version zu basteln.
.
EDIT :
.
Ach übrgens habe ich mich wohl geirrt, was die Laufzeit der ATIs angeht. Die sind etwa doppelt so schnell, wie von mir behauptet, da Slicker scheinbar den Kernel, den ich ihm vor einiger Zeit geschickt hatte doch 1:1 übernommen hat. Eine HD4870 benötigt also nur etwa 6 Minuten für eine WU. Insofern bin ich mir mit den minimal möglichen gut 4 Minuten für die HD4870 ziemlich sicher. Da wären dann durchschnittlich 4,37 der 5 Slots einer Einheit belegt, es werden also im Prinzip 525 GigaIntegerOps ausgeführt, bei einer HD4890 sogar 595 GigaOps 8)
Leider nicht alle sinnvoll, da die Branchgranularität bei ATI 64 Threads groß ist, bei meiner Vektorisierungslösung, die auch noch ein wenig Overhead kostet (aber unter dem Strich Vorteile hat) sogar effektiv 128. Schätzungsweise bleibt also vielleicht die Hälfte übrig.

Damit sollte man dann praktisch sicher vor einer GTX 285 landen, die mit den normalen ALUs theoretisch nur auf maximal 354 GigaOps kommen kann (240 * 1476MHz). Die SFUs können nur wenig beitragen (maximal 10%), dafür sind die Verluste durch die feinere Branch-Granularität (32 Threads) geringer, aber das dürfte nicht reichen.

Soweit so gut. Jetzt benötige ich nur noch eine Idee, wie man Slicker dazu überredet bekommt, die CPU-Version noch zu beschleunigen und damit die davon abhängigen Credits nach unten anzupassen :]

Gipsel
13.07.2009, 23:45
wenn alles so klappt, wie ich mir das vorstelle, wird eine HD4870 zukünftig vielleicht sogar in 4-5 Minuten fertig sein ;D
Macht mal 2 Minuten draus *suspect* ;D
Das mit der Branchgranularität scheint gar nicht so schlimm zu sein, wie ich gedacht habe.

Running Collatz Conjecture (3x+1) ATI GPU application version 0.1 by Gipsel
Reading input file ... done.
Checking 2147483648 numbers starting with 2361183348087637911912
[..]
Device 0: ATI Radeon HD 3800 (RV670) 512 MB local RAM (remote 28 MB cached + 512 MB uncached)
GPU core clock: 844 MHz, memory clock: 297 MHz
[..]
needed 1467 steps for 2361183348087997950857
1049185876805 total executed steps for 2147483648 numbers

WU completed.
CPU time: 0.96875 seconds, GPU time: 280.328 seconds, wall clock time: 281.417 seconds

Eine HD4870 bei Standardtakt von 750MHz sollte Faktor 2.7 schneller sein (weil Bitshifts bei den HD4000-GPUs schneller sind). Das wären dann nur noch knappe 2 Minuten 8). Außerdem ist die GPU-Last mit einer WU auch erst etwa 85% gewesen, dafür ist die Prozessorlast praktisch exakt Null.

Gipsel
20.07.2009, 14:58
Ich vermute mal, er [Slicker] will vom primitiven Algorithmus weg und einen etwas besseren implementieren und zusätzlich das Handling der großen Zahlen auf das bei den GPUs verwendete System umstellen.
Meine kleine Test-App für ATI (die lief nur offline, außerdem habe ich die erst gestern gebaut, also wegen mir wurde das Projekt nicht vorläufig dicht gemacht) benutzt schon ansatzweise so einen besseren Algo. Das läßt sich aber bestimmt nochmals um den Faktor 2 ausbauen ;D
Ich neige doch immer wieder dazu, sowas zu unterschätzen :]

Can't set up shared mem: -1
Will run in standalone mode.
Running Collatz Conjecture (3x+1) ATI GPU application version 0.1 by Gipsel
Reading input file ... done.
Checking 2147483648 numbers starting with 2361183348087637911912
[..]
Device 0: ATI Radeon HD 3800 (RV670) 512 MB local RAM (remote 28 MB cached + 512 MB uncached)
GPU core clock: 844 MHz, memory clock: 297 MHz
[..]
needed 1467 steps for 2361183348087997950857
1049185876805 total executed steps for 2147483648 numbers

WU completed.
GPU time: 103.172 seconds, wall clock time: 103.374 seconds
Eine HD4870 wäre in unter 40 Sekunden durch, und es geht wohl auch noch ein bißchen ;D
Ich glaube, das Projekt benötigt dringend größere WUs *lol*

Edit:
Nochmal geschraubt, aber mit den HD3000er Karten ist man erst mal am Limit. Da bekommt man nicht mehr Parallelität hin, da dort nur eine der 5 ALUs einer VLIW-Einheit sowohl für Multiplikationen als auch Bit-Shifts zuständig ist. Das ist also ein gehöriger Flaschenhals. Bei den HD4000er Karten kann zwar immer noch nur eine Einheit Multiplikationen, dafür aber alle 5 Bitshifts, so daß dort die Lage erheblich entspannter ist. Dies führt dazu, daß HD4000er Karten den älteren doch recht stark davonziehen werden. Für obiges Beispiel bräuchte eine HD4870 jetzt nur knapp über 30 Sekunden, wäre also gut 3 mal so schnell wie obige (übertaktete) HD3870.

CPUs werden durch den neuen Algorithmus allerdings relativ gesehen deutlich stärker beschleunigt (und 64Bit die 32Bit-Variante deutlich abhängen). Das liegt natürlich zum einen am bisher wahrscheinlich recht ineffizient umgesetzten Algo. Zum anderen aber auch an den größeren Caches (man kann größere Lookup-Tables als bei GPUs benutzen) in Verbindung mit dem besseren Integer-Multiplier der CPUs.

Gipsel
21.07.2009, 21:03
Ich habe mal versucht, Slicker bezüglich der neuen (schnelleren) CPU-Version ein wenig anzuspornen (http://boinc.thesonntags.com/collatz/forum_thread.php?id=8&nowrap=true#161). Wie man sieht, ist da Einiges möglich (knapp 10 Minuten auf 2.5GHz Phenom, 64Bit) ;D

Gipsel
24.07.2009, 23:04
CPUs werden durch den neuen Algorithmus allerdings relativ gesehen deutlich stärker beschleunigt (und 64Bit die 32Bit-Variante deutlich abhängen). Das liegt natürlich zum einen am bisher wahrscheinlich recht ineffizient umgesetzten Algo. Zum anderen aber auch an den größeren Caches (man kann größere Lookup-Tables als bei GPUs benutzen) in Verbindung mit dem besseren Integer-Multiplier der CPUs.
So, nachdem ich eine Stunde damit zugebracht habe einen (weiteren) Bug im Brook-Compiler zu finden und zu umschiffen kann man jetzt auf GPUs genauso große Lookup-Tables wie auf CPUs benutzen. Und was soll ich sagen, der Speed verdoppelt sich nochmal ;D

Checking 2147483648 numbers starting with 2361183348087637911912

Device 0: ATI Radeon HD 3800 (RV670) 512 MB local RAM (remote 28 MB cached + 512 MB uncached)
GPU core clock: 844 MHz, memory clock: 297 MHz

Starting WU on GPU 0

needed 1467 steps for 2361183348087997950857
1049185876805 total executed steps for 2147483648 numbers

WU completed.
GPU time: 51.9355 seconds, wall clock time: 52.352 seconds

[MTB]JackTheRipper
28.07.2009, 11:42
Ich wär dafür für jede gerechnete WU Gipsel einen symbolischen Credit auf seinen Account zu vergeben ;)

Gipsel
28.07.2009, 15:07
Wie sieht es jetzt eigentlich für Euch mit den Credits aus?

Gibt jetzt im Schnitt wohl knapp 80 credits pro WU (statt ~400 vorher). Das ist jetzt nicht mehr fest pro WU sondern abhängig von der Anzahl der in jeder WU ausgeführten Schritte, sollte also in etwa mit der nötigen Zeit zur Berechnung korrelieren. An der Normierung eines 800MHz P3 auf ~100 Cedits am Tag hat sich aber nichts geändert.

Für die CPUs sollte die Creditsituation also ähnlich sein wie vorher (übrigens, 64Bit bringen Faktor 2), GPUs sahnen jetzt nicht mehr so ab (~10k/Tag für eine 9800GT ?)

Sowohl bei CPU als auch GPU sind könnten aber nochmal um den Faktor 10 drin sein, wenn Slicker meinen schnelleren Algorithmus einbaut. Das könnte das Credit-Verhältnis zwischen GPU und CPU auch noch mal etwas verschieben, aber so viel wie vor der Umstellung wird es wohl definitiv nicht mehr werden. Das lag ja hauptsächlich an einer wirklich langsamen CPU-Version.

Crashtest
29.07.2009, 07:16
Leider kann ich noch nicht so richtig die GPUS (nv vs ati) vergleichen

bei ati steht nur 0,5-2s CPU keine GPU-Zeit da ?!?

Credits : nur ein Bruchteil (1/4 bis 1/3 ? ) von dem was man bei MW bekommt...

PRO: man kann ordentlich bunkern - bis zu 3000/WUs/CPU/Tag

Gipsel
31.07.2009, 17:36
Immer diese Selbst-Zitate :]

So, nachdem ich eine Stunde damit zugebracht habe einen (weiteren) Bug im Brook-Compiler zu finden und zu umschiffen kann man jetzt auf GPUs genauso große Lookup-Tables wie auf CPUs benutzen. Und was soll ich sagen, der Speed verdoppelt sich nochmal ;D
Es ist wirklich unglaublich, wieviel Speicherbandbreite GPUs sogar bei zufälligem Zugriffsmuster erreichen können und wie die Latenz dabei versteckt werden kann. Wenn man die Cachegrößen überschreitet, muß man zwar den Speichertakt hochdrehen, damit es nicht einbricht, aber ich will Euch mal nicht vorenthalten, was man nächste Woche zusammen mit gleichfalls ~8x (64Bit ) bis 15x (32Bit) beschleunigten CPU-Versionen in etwa erwarten kann.
Can't set up shared mem: -1
Will run in standalone mode.
Running Collatz Conjecture (3x+1) ATI GPU application version 0.1 by Gipsel

Reading input file ... done.
Checking 2147483648 numbers starting with 2361183348087637911912
CPU: AMD Phenom(tm) 9750 Quad-Core Processor (4 cores/threads) 2.49179 GHz (2ms)

CAL Runtime: 1.3.145
Found 1 CAL devices

Device 0: ATI Radeon HD 3800 (RV670) 512 MB local RAM (remote 28 MB cached + 512 MB uncached)
GPU core clock: 837 MHz, memory clock: 900 MHz
320 shader units organized in 4 SIMDs with 16 VLIW units (5-issue), wavefront size 64 threads
supporting double precision

Initializing lookup tables (16MB) ... done
0 WUs already running on GPU 0
Starting WU on GPU 0
Initialize step arrays on GPU (2 x 16MB)

needed 1467 steps for 2361183348087997950857
1049185876805 total executed steps for 2147483648 numbers

WU completed.
CPU time: 1.90625 seconds, GPU time: 23.3438 seconds, wall clock time: 24.301 seconds, CPU frequency: 2.49609 GHz
Ein wenig langsamer (~15%) wird es noch werden (da fehlt noch was, damit es immer vollkommen identisch rechnet) und es ist die Version für Highend-GPUs. GPUs mit recht wenig Bandbreite/Rechenleistung brechen eventuell damit ziemlich ein (muß noch getestet werden) und fahren vielleicht mit einem bandbreitenschonenderem Algo besser (z.B. eine integrierte Grafikeinheit, die das aus dem Hauptspeicher bestreiten muß).
Eine HD4870 würde etwa 70GB/s benötigen, die HD3870 oben aus dem Beispiel hat ziemlich genau 25GB/s gebraucht. Alles wie gesagt mit quasi zufälligem Zugriffsmuster auf zum Glück jeweils 16Byte. Aber eine CPU würde da wohl auf ein Viertel oder so ihrer nominellen Speicherbandbreite absacken und vor allem die Speicherlatenz die Performance killen. Deswegen gibt es da nur lookup tables im kB Bereich (paßt in L1 Cache) statt MBytes ;) Edit: Dadurch, daß CPUs langsamer rechnen, sind die Bandbreitenanforderungen gar nicht mehr sooo groß, ungefähr 1,6GB/s (pro Kern) bleiben bei einem Phenom 2.5GHz (64Bit Modus) übrig. Das schafft der offensichtlich noch halbwegs mit Dual Channel DDR2-800, selbst bei vier gleichzeitig laufenden Tasks. Man sieht zwar einen kleinen Einbruch bei Überschreiten des L3, aber danach steigt die Performance wieder. Mit 'nem AthlonXP müßte ich es mal ausprobieren, vielleicht legt der 'ne Bauchlandung hin. Aber je langsamer eine CPU, desto weniger Bandbreite benötigt sie, also wahrscheinlich geht es da auch (wenn die Latenz nicht zu hoch ist).

Leider steigt die Performance nur logarithmisch zur Größe der Lookup-Tables. Der Unterschied zwischen 8kB und 16MB ist gerade mal Faktor 2 Rechenaufwand. Für den nächsten Faktor zwei bräuchte man schon 32GB 32TB *buck*. Und für mehr als 16MB Lookup benötige ich schon 64Bit statt 32Bit-Werte (da größer als 2^32), was die nötige Bandbreite nochmal verdoppelt. Aber hmm, für die 64Bit Version könnte man das mal ausprobieren. Ich denke die Version wird der Hammer auf einem Core i7 *lol*

Tejas
31.07.2009, 19:53
If I understand this correctly, you have been able to gain more performance for the ATI cards. *great*

Gipsel
31.07.2009, 19:57
If I understand this correctly, you have been able to gain more performance for the ATI cards. *great*
The same kind of changes work on nvidia GPUs and CPUs too ;)

Probably next week they should be ready for prime time.