Die Mathe-Redaktion - 22.08.2017 07:09 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 140 Gäste und 7 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Die Collatz-Folge programmieren
Thema eröffnet 2016-10-23 08:10 von gonz
Druckversion
Druckversion
Antworten
Antworten
Seite 13   [1 2 3 4 5 6 7 8 9 10 11 12 13]   13 Seiten
Autor
Kein bestimmter Bereich Die Collatz-Folge programmieren
Amateur
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2012
Mitteilungen: 801
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.480, eingetragen 2017-08-20 16:33


Die ersten 10% der Restklassen sind abgearbeitet und validiert seit dem Start des verteilten Rechnens bei Yoyo@home vor 6 Tagen. Ich bin beeindruckt!
Der Pfadrekord #85 steht seit gestern Vormittag in der Ergebnisliste.

Vielleicht könnte bei Gelegengeit die Kurzbeschreibung des Projektes noch mit einem Windows-Logo versehen werden.

Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
sudden6
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 12.08.2017
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.481, eingetragen 2017-08-20 18:42


Hi cyrix,

Ich habe heute den Grund gefunden, warum ich auf leicht andere checkpoint werte komme. Die Änderung tritt auf mit diesem Commit. Der cast und die Logik hinter dem Commit scheint korrekt zu sein und dürfte eigentlich nichts ändern. Kann es sein, dass da irgendwo ein Überlauf auftritt?



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 3319
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.482, eingetragen 2017-08-20 19:35


2017-08-20 18:42 - sudden6 in Beitrag No. 481 schreibt:
Ich habe heute den Grund gefunden, warum [..]

Es ist mir schon länger aufgefallen, dass ich die Links in deinen Postings alle nicht anklicken kann und ich denke, ich habe heute den Grund gefunden, warum das so ist. Kann es sein, dass du in href='' die beiden Apostrophe überschreibst, statt den Link-url genau dazwischen hineinzukopieren? Sorry, wenn das jetzt ein bißchen off topic ist.  wink



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1929
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.483, eingetragen 2017-08-20 21:41


Es wurde auch ein neuer Hochwert gefunden.

Start 23314617123910465627
Wert  52159921375623872234470241595697335400
126Bit

Restklasse 2901250
Datum 2017.08.20 13:35:20
von zombie67 [MM], scole of TSBT

was mir nicht klar ist, welches Kompilat auf den einzelnen Rechnern läuft.
Sind denn Verbesserungen wie die von sudden denn in BOINC eingepflegt?
Mit avx komme ich auf sehr schnelle Werte, und das kann jeder Intel Core I3 oder AMD ab Sockel AM3+.




  Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2012
Mitteilungen: 801
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.484, eingetragen 2017-08-21 00:06


Hallo Jürgen,

die heute Nachmittag gefundene Zahl ist beachtenswert, aber kein Pfadrekord. Der Startwert ist größer als der Startwert von #88, aber das Pfadmaximum ist kleiner als das von #88.
Einziger Kandidat für einen neuen Pfadrekord bleibt momentan die Zahl 79619863089615381531, 126 Bit, ResCl 286712, die ein größeres Pfadmaximum liefert als #88.

Laut der Anwendungs-Tabelle ist unverändert Programmversion 0.0.1 im Einsatz. Was die aktuelle Entwickler-Versionen betrifft: Könntest Du möglicherweise die von Dir gemessenen Laufzeiten im Vergleich zu einer älteren Version (z.B. aus Beitrag #413) mitteilen?

Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2542
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.485, eingetragen 2017-08-21 00:39


Es wird eine neue Version geben, aber wohl erst übernächste Woche. Bisher läuft auf den BOINC-Clients eine Version ohne AVX-Unterstützung; aber das können wir bei Bedarf sicherlich noch nachholen.

Ich habe die letzten Tage etwas an der Parallelisierung (insbesondere der Einbeziehung der Vorschläge von sudden6) gearbeitet. Der Spaß muss die nächsten Tage noch getestet werden.

Wobei ich erst bei einer deutlichen Laufzeitverbesserung da auf diesen Pfad mehr Energie investieren würde. Für 5% handelt man sich dafür zu viele Scherereien (etwa mit divergierenden Code-Versionen für verschiedene Plattformen, die keine solche Vektorisierung - oder nicht auf genau diese Weise - unterstützen) ein, als dass sich das wirklich lohnen würde.

Wie gesagt: Ich teste noch, inwiefern da was machbar ist.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1929
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.486, eingetragen 2017-08-21 02:23


2017-08-21 00:06 - Amateur in Beitrag No. 484 schreibt:
Hallo Jürgen,

Laut der Anwendungs-Tabelle ist unverändert Programmversion 0.0.1 im Einsatz. Was die aktuelle Entwickler-Versionen betrifft: Könntest Du möglicherweise die von Dir gemessenen Laufzeiten im Vergleich zu einer älteren Version (z.B. aus Beitrag #413) mitteilen?

Viele Grüße A.


Die neueste Version die da steht wo sie immer steht, ich nenne sie Version 11, habe ich mit -mavx compiliert und sie braucht von 1 bis 100 auf 6 Kernen 11:28 min.


Die zeitkritischen Sachen sind in small_ms_without_max und an anderen Stellen wohl:
1) *res64 = (*res64 >> ms_depth) * pot3_64Bit[multistep_odd[*small_res]] + multistep_it_rest[*small_res];

sowie

2) *new_it_f *= multistep_it_f[*small_res];


Die letzte Version von sudden hat viele Formatfehler, bevor ich was dazu sagen kann.
HtH





  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2542
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.487, eingetragen 2017-08-21 11:20


Hm, also meine Tests zur Parallelisierung mit AVX sind jetzt nicht so berauschend ausgefallen:

Auf meinem Bürorechner (Intel Core i3 aus dem Jahr 2011) erhalte ich eine Laufzeitreduktion von ca. 4% gegenüber dem Status Quo, wenn ich den auf mehr Parallelität getrimmten Code (nach der Vorlage durch sudden6) mit AVX verwende. (AVX2, mit Schalter -mavx2 im GCC erreichbar, scheint demgegenüber kaum weitere Vorteile zu bringen. Und AVX512 [Schalter -avx512f ] kann ich hier nicht testen; dafür bräuchte es einen neuen Rechner aus dem High-Performance-Segment. ;) )

Ich lade aber heute Nachmittag mal die "parallelisierte" Version des Quellcodes hoch, sodass auch andere damit spielen können.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2576
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.488, vom Themenstarter, eingetragen 2017-08-21 14:22


Da mir unklar ist, was eigentlich genau passiert wenn man -Ofast gesetzt hat (bzw. das ja auch je nach Compilerversion etc unterschiedlich sein kann), kann es natürlich auch von der speziellen Konfiguration abhängen, was man mit einem zusätzlichen Schalter erzielen kann und was nicht. Ich werde mir mal angucken, wie sich der assemblercode unterscheidet, der erzeugt wird, und das ggf. dann auch mal posten zur gefälligen Einsichtnahme :)

Grüsse
gonz


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2576
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.489, vom Themenstarter, eingetragen 2017-08-21 17:48


hm, der Unterschied in den asm Dateien besteht eigentlich nur darin, dass einzelne Befehle durch die entsprechenden Befehle aus der Erweiterung ersetzt werden (wie logisch), also zB mulsd durch vmulsd in dem uns interessierenden Bereich der multistep-Routine. Es werden die gleichen Registersätze verwendet. An einzelnen Stellen entfällt zusätzlich ein vorhergehendes mov zwischen zwei Registern.

Bei ersten Vergleichen habe ich allerdings auch keinen (wesentlichen) Geschwindigkeitsgewinn feststellen könnnen, dieser liegt bei dem was ich probiert habe unter 5% bis unmessbar.

@juergen: ich habe das auf h2543043 laufen lassen, ist das die Maschine, die du auch verwendet hast?


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2542
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.490, eingetragen 2017-08-21 18:06


Die versprochene, auf Parallelisierung mit den Ideen von sudden6 getrimmte Version findet sich nun unter collatz_sieb_multistep_parallel_loops.c.

Im Wesentlichen sind dabei die ersten drei 10er-Multisteps der first_multistep()-Methode in die einzelnen Berechnungsschritte auseinandergenommen worden, sodass jetzt je no_of_parallels davon parallel ausgeführt werden können. (Diese Anzahl kann man im Kopf der Quelldatei selbst definieren; aktuell ist 4 eingestellt.) Dazu werden im Siebausgang von sieve_third_stage() nicht mehr die erzeugten Startzahlen einzeln an first_multistep() zur weiteren Berechnung übergeben, sondern erst in einem Array aufgesammelt, um dann vektorisiert ihre nächsten Iterationen zu berechnen. Wann diese Übergabe erfolgt (jeweils gemeinsam 38 oder 39 Startzahlen pro Restklasse mod9; oder das Fünffache davon für alle in einem Aufruf von sieve_third_stage() erzeugten Startzahlen), kann mit dem Setzen/ Nichtsetzen des #define inner_loop_output gesteuert werden.


Ich habe bisher nur das Laufzeitverhalten der abgerollten innersten Schleifen betrachtet (also n entsprechend gleiche Anweisungen hintereinander für die parallel zu berechnenden Codeteile). Die hier hochgeladene Variante dagegen fasst - auch der einfacheren Lesbarkeit wegen - diese wieder zu elementaren Schleifen zusammen, sodass die Auto-Vektorisierung des Compilers vielleicht mehr erkennt, was er optimieren kann.

Man kann sich beim GCC hier auch einen Output erzeugen, wo er seine Meinung zu den verschiedenen Schleifen und deren Optimierungs-Fähigkeiten preisgibt. Dazu kann man z.B. mit dem Schalter -fopt-info-loop-optimized-missed=info.txt sich eine Datei info.txt mit Informationen über Schleifen-Optimierung erzeugen lassen. Dabei erhält man hier für die relevanten Schleifen die Information, dass sie einfach abgerollt wurden... (Es gibt noch weitere solche Schalter wie z.B. -fopt-info-vec-all  oder ...-vec-missed  , wobei dort, zumindest bei mir, keine weiteren Informationen über Vektorisierungsversuche zu den relevanten Schleifen zu finden sind.)

Sollte man vielleicht nicht je eine vorgegebene, kleine Anzahl - z.B. 4, wie es aktuell hier implementiert ist, - an Startzahlen herausgreifen und deren Iterationen versuchen einzeln zu parallelisieren; sondern gleich das ganze Array hernehmen? Das werde ich noch einmal in den nächsten Tagen ausprobieren.

Wahrscheinlich rührt die einzige Verbesserungsmöglichkeit in diesem Code daher, dass öfter ähnliche Operationen hintereinander ausgeführt werden. Groß von Parallelisierung kann man aber wohl nicht sprechen.

Cyrix

edit: Auch bei der Benutzung der AVX512 - Flags ändert sich nichts. Die innersten Schleifen werden nur abgerollt, mehr passiert nicht.



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1929
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.491, eingetragen 2017-08-21 21:06


2017-08-21 17:48 - gonz in Beitrag No. 489 schreibt:
hm, der Unterschied in den asm Dateien besteht eigentlich nur darin, dass einzelne Befehle durch die entsprechenden Befehle aus der Erweiterung ersetzt werden (wie logisch), also zB mulsd durch vmulsd in dem uns interessierenden Bereich der multistep-Routine. Es werden die gleichen Registersätze verwendet. An einzelnen Stellen entfällt zusätzlich ein vorhergehendes mov zwischen zwei Registern.

Bei ersten Vergleichen habe ich allerdings auch keinen (wesentlichen) Geschwindigkeitsgewinn feststellen könnnen, dieser liegt bei dem was ich probiert habe unter 5% bis unmessbar.

@juergen: ich habe das auf h2543043 laufen lassen, ist das die Maschine, die du auch verwendet hast?


Die Änderungen die du meinst, beziehen sich wohl auf den -mavx switch?
Ja ich arbeite auf dem genannten Server da läuft auch manchmal ECM..von Boinc gestartet. Es ist der einzige der avx kann.

Ich mache aber keine intensiven Langzeittests..
Interesant wäre mal ne abfrage avx_avail = (cpuid).
vmulsd bringt kaum was gegen mulsd bzw vmovsd gegen movsd. mulsd gegen mul. etc. Das erscheint klar an sich weil ja höhere Datenbreiten nämlich 128 Bit angefasst werden, was nicht immer schneller oder besser ist..


Bis denne !!





  Profil  Quote  Link auf diesen Beitrag Link
sudden6
Junior Letzter Besuch: in der letzten Woche
Dabei seit: 12.08.2017
Mitteilungen: 10
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.492, eingetragen 2017-08-22 00:16


Hi alle zusammen,

Das wichtigste zuerst, mein aktueller branch (diesmal funktionierend  razz ) mit vielleicht ein zwei nützlichen commits ist der hier. Diese Variante ist wahrscheinlich langsamer als die neueste von cyrix, könnte aber vielleicht noch verbessert werden. Warum siehe weiter unten.

Dann danke an @weird ich hab wirklich die Link Funktion falsch benutzt...

Dann eine gute und gleichzeitig schlechte Nachricht, ich hab endlich herausgefunden, warum ich so stark Abweichende Ergebnisse bei den Optimierungen erhalte wie ihr. Anscheinend sind nicht alle Restklassen gleich arbeitsintensiv wie ich angenommen habe. Ich habe nämlich immer die Restklassen 0 - 10 gebenchmarkt und anscheinend sind die nicht sehr Arithmetik lastig, weswegen meine Änderungen immer sehr gute Verbesserungen erzielt haben. Mein neuer Testbereich ist nun von 3042000 - 304200, an diesen fünf Restklassen wird ca. dreimal soviel gerechnet.

Beim Testen habe auch noch herausgefunden, dass wenn man mit "-O3 -msse3" anstatt "-O3 -mavx" compiliert, sich zumindest auf meinen beiden Rechnern eine Geschwindigkeitsverbesserung ergibt. Da SSE3 in so ziemlich allen modernen Prozessoren vorhanden ist, wäre es sicher einen Versuch wert das mal testweise zu aktivieren.

LG

sudden6



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1929
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.493, eingetragen 2017-08-22 02:19


root@h2543043:/home/juergen# gcc collatz_sieb_multistep_parallel_loops.c -Ofast -fopenmp -mavx  -std=c99 -o zcykel12
collatz_sieb_multistep_parallel_loops.c: In function ‘sieve_third_stage’:
collatz_sieb_multistep_parallel_loops.c:1152:6: warning: passing argument 4 of ‘first_multistep’ from incompatible pointer type [enabled by default]
      first_multistep(start_arr, it_arr, &it_f, &ms_start_count, &credits);
      ^
collatz_sieb_multistep_parallel_loops.c:950:15: note: expected ‘const uint32_t *’ but argument is of type ‘uint_fast32_t *’
 __inline void first_multistep(const uint128_t start[], uint128_t number[],
               ^
collatz_sieb_multistep_parallel_loops.c: At top level:
collatz_sieb_multistep_parallel_loops.c:1521:1: fatal error: error writing to /tmp/ccXZi1fV.s: Auf dem Gerät ist kein Speicherplatz mehr verfügbar
 }
 ^
compilation terminated.


Keine Ahnung was da zu ändern ist.
ich nehme immer 1 bis 101 als benchmark. Beste Werte waren bei 5 Minuten auf 12 Kernen.



  Profil  Quote  Link auf diesen Beitrag Link
gonz hat die Antworten auf ihre/seine Frage gesehen.
Seite 13Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]