Die Mathe-Redaktion - 26.04.2017 10:02 - Registrieren/Login
Auswahl
Schwarzes Brett
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 673 Gäste und 16 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 5   [1 2 3 4 5 6 7 8]   8 Seiten
Autor
Kein bestimmter Bereich Die Collatz-Folge programmieren
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.160, vom Themenstarter, eingetragen 2016-12-24 13:47


Aaaaalso.... dies ist gleichzeitig mein Weihnachtsbeitrag :) siehe am Ende.

Ich habe einmal * rumhibbel * eine idee, die es vielleicht erlaubt, in einer FPGA Lösung bei der wir die ALU "selber bauen" nochmal einen Faktor von 64 rauszuholen, nämlich durch das interne parallelisieren der Schritte in der Folge über das 128 bit register. im gegensatz zu einem echten addierer, der die beiden summanden eingangsseitig lädt, sie dann addiert, und zwar die 128 bit schön der reihe nach damit über das carry jeweils der übertrag für das höhergelegene bit von dem niederwertigerem übernommen wird, kann man bei einer collatz-folgen-schrittmaschine jeweils über die 128 bit mitgeben, ob jeweils ein even oder ein odd+even schritt gemacht wird, und damit kann der nächste schritt jeweils im abstand von einem bit schon hinterher laufen, also bevor der schritt davor das 128. bit erreicht hat, da jeder schritt ja nur carry_in, carry_out und das datenbit des  höherliegenden bits benötigt (für das shr). damit könnten max. 64 schritte der folge sozusagen parallel durchgerechnet werden. und vielleicht ist damit eine FPGA Lösung doch der bringer, da a) so eine Maschine vielleicht viel schlanker zu implementieren ist als eine komplette ALU, und man ggf. eben 64 schritte in einem machen kann. Wenn man aber statt eines clusters von 64 FPGA nur derer einen bräuchte... (oder doch den Cluster baut, und damit in 7 statt 400 tagen ein ergebnis hat, dann)...

könnt ihr mir folgen? (das folgende Bild entspricht dem noch nicht. anstelle der clk-chain in blau, die die addierer taktet, und der links von den addierern liegenden verteilung des even/odd signals, das vom LSB generiert wird, müsste es zwei Clk signale geben, ein clk_even und ein clk_odd, die über die addiererkette wandern, und die im abstand von einem bit laufen können, und dann... :) tschakkaaaa!



egal. ich werds in ruhe ausarbeiten. und wenn es passt... dann... sollte ich lernen, wie man fpga wirklich programmiert (oder jemanden finden, der...)

kommen wir zum zweiten spielprojekt. ich habe angefangen, das zu entwerfen, und mir überlegt, wie man das visualisiert. erst kam mir povray in den sinn, dann aber... (über die gedankenkette - das könnte vom look and feel was sein um was im steam-punk outfit zu bauen - steam - dampflok - eisenbahnhobby) kam ich auf die idee, dass ich meine eisenbahnsimulation nehmen könnte, um logikelemente zu bauen. klar kann man. anbei ein OR in form von EEP. details erspar ich euch, ihr könnte jetzt denken - bekloppt - und es als kuriosität durchgehen lassen. vielleicht baue ich damit aber auch eine 6bit collatz maschine komplett auf, mit block-copy sollte das eigentlich dann sogar ganz fix gehen :)



soweit
und

EIGENTLICH

ist das mein

HAPPY XMAS

Beitrag. Ich wünsche euch und uns allen ein frohes Fest, geruhsame oder aufregende oder... eben schöne Tage, Frieden und Gesundheit, und alles was dazu gehört.

have fun!

gonz




-----------------
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: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.161, eingetragen 2016-12-24 20:09


Noch kein Durchbruch, aber immerhin etwas: Unerwarteter Weise bringt es etwas, wenn man ein paar mehr Rückwärts-Iterationen betrachtet. Ersetzt man die Methode corfactor, die berechnet, um welchen Faktor ein Vorgänger einer Zahl kleiner ist als der aktuell betrachtete Wert, durch die unten angegebene Erweiterung, dann bleiben nur noch etwas über 20 Millionen Restklassen mod 2^32 übrig, was gegenüber dem bisherigen Stand nur noch ca. 2/3 sind, also den Durchsatz um etwa den Faktor 1,5 steigern sollten:
C
  1. double corfactor(const unsigned int odd, const unsigned __int128 it_rest)
  2. {
  3. double factor = 1;
  4.  
  5. if ((it_rest % 3 == 2) && (odd >= 1))
  6. factor *= 2.0/3; //2k+1 --> 3k+2
  7.  
  8. if (odd >= 2)
  9. {
  10. if (it_rest % 9 == 8)
  11. factor *= 2.0/3; //4k+3 --> 9k+8
  12.  
  13. if (it_rest % 9 == 4)
  14. factor *= 8.0/9; //8k+3 --> 9k+4
  15.  
  16. if (odd >= 3)
  17. {
  18. switch(it_rest % 27)
  19. {
  20. case 13: factor *= 2.0/3; break; //16k+7 --> 27k+13
  21. case 20: factor *= 8.0/9; break; //16k+11 --> 27k+20
  22. case 26: factor *= 2.0/3; break; // 8k+7 --> 27k+26
  23. }
  24.  
  25. if (odd >= 4)
  26. {
  27. switch(it_rest % 81)
  28. {
  29. case 10: factor *= 64.0/81; break; //64k+7 --> 81k+10
  30. case 20: factor *= 2.0/ 3; break; //32k+7 --> 81k+20
  31. case 40: factor *= 2.0/ 3; break; //32k+15--> 81k+40
  32. case 71: factor *= 8.0/ 9; break; //64k+55--> 81k+71
  33. case 76: factor *= 8.0/ 3; break; //64k+59--> 81k+76
  34. case 80: factor *= 2.0/ 3; break; //16k+15--> 81k+80
  35. }
  36. }
  37.  
  38. if (odd >= 5)
  39. {
  40. switch(it_rest % 243)
  41. {
  42. case 76: factor *= 2.0/ 3; break; //128k+ 39 --> 243k+ 76
  43. case 91: factor *= 2.0/ 3; break; //128k+ 47 --> 243k+ 91
  44. case 107: factor *= 8.0/ 9; break; // 64k+ 27 --> 243k+107
  45. case 121: factor *= 2.0/ 3; break; // 64k+ 1 --> 243k+121
  46. case 137: factor *=64.0/81; break; //128k+ 71 --> 243k+137
  47. case 152: factor *= 1.0/ 3; break; // 64k+ 39 --> 243k+152
  48. case 175: factor *= 8.0/ 9; break; //128k+ 91 --> 243k+175
  49. case 182: factor *= 2.0/ 3; break; // 64k+ 47 --> 243k+182
  50. case 233: factor *= 2.0/ 3; break; //128k+121 --> 243k+233
  51. case 236: factor *= 8.0/ 9; break; //128k+123 --> 243k+236
  52. case 242: factor *= 2.0/ 3; break; // 32k+ 31 --> 243k+242
  53. }
  54. }
  55. }
  56. }
  57.  
  58. return factor;
  59. }

Möglicherweise bietet es sich an, einen Präprozess zu schreiben, der den Quellcode für noch zwo oder drei "3x+1"-Rückwärtsschritte mehr ermittelt. Bisher sind die Angaben alle per Hand/ Excel ausgerechnet...


Noch nen Faktor 3-5 erhoffe ich mir daraus, dass man bis Tiefe 32 (wie bisher) vorsiebt, zur besseren Parallelisierung die Daten dort rausschreibt, dann aber in jedem einzelnen der übrig gebliebenen Reste noch einmal ca. 10-20 weitere Bits vorsiebt, bevor man dann in die endgültige Berechnung der Collatz-Iterationen für die einzelnen Kandidaten geht.

Das Schöne ist, dass dies unabhängig von den Optimierungen ist, die gonz gerade an der "inneren Schleife" bastelt. Man würde nur mehr eher die Eingabedaten dafür ordentlich vorsieben...


Viele Grüße und eine geruhsame Zeit
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.162, vom Themenstarter, eingetragen 2016-12-25 13:36


2016-12-24 20:09 - cyrix in Beitrag No. 161 schreibt:

was gegenüber dem bisherigen Stand nur noch ca. 2/3 sind, also den Durchsatz um etwa den Faktor 1,5 steigern sollten


Eingebunden und läuft - die Steigerung um etwa 50% kann ich nach erstem rumprobieren bestätigen.




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



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.163, eingetragen 2016-12-25 23:20


2016-12-24 13:47 - gonz in Beitrag No. 160 schreibt:

im gegensatz zu einem echten addierer, der die beiden summanden eingangsseitig lädt, sie dann addiert, und zwar die 128 bit schön der reihe nach damit über das carry jeweils der übertrag für das höhergelegene bit von dem niederwertigerem übernommen wird,


Vielleicht wg. meines vereinfachten Diagramms (ich wollte keine 80 Register, 160 Multiplexer, 80 Volladdierer und über tausend Leitungen zeichnen - die Leitungen sollen in den meisten Fällen komplette Busse darstellen), scheinst Du falsch zu interpretieren, was auf mikrocontroller.net angedacht wurde und wie der 80bit Addierer funktionieren soll (oder ich verstehe überhaupt nicht, was Dir vorschwebt). Der soll pro Takt zwei 80bit Operanten entgegen nehmen und bis zur nächsten Taktflanke auch ein neues Ergebnis berechnen - also nichts "schön der Reihe nach". Damit das mit einer ordentlichen Taktfrequenz funktioniert, bedarf es FPGAs mit spezieller Logik in den LEs, damit eine schnelle Carry-Logik (Carry-Chain) realisierbar ist - das Carry muss in einem Bruchteil eines Takzykluses vom Bit0 zu Bit79 sausen! Mit FPGAs ohne spezielle Logik für eine Carry-Chain könnete man einen 80-Bit-Addierer wohl nur mit ein paar MHz betreiben (oder würde womöglich sogar im kHz-Bereich landen :-). Mit den auf mikrocontroller.net erwähnten XC5VLX330T-2-FPGA-Bausteinen lassen sich 64bit-Addierer mit weit über 300Mz realisieren.




  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.164, eingetragen 2016-12-26 00:14


Hier mal ein Bild, um das etwas zu veranschaulichen. Bei den erwähnten Xilinx-Bausteinen sind pro CLB vier Register und 4 LUTs vorhanden. Im Bild habe ich 4 Stück zusammenkopiert, wobei ich bei dreien die Register gleich überdeckt habe, weil sie für die Applikation vermutlich verloren sind (gut man weiß nie, was die Software vielleicht doch noch rausholt). Ganz rechts die Register, davor ein Multiplexer, für den Adder in der Mitte bin ich mal davon ausgegangen, das zwei Stufen notwendig sind (vielleicht gelingt es der Software mit einer auszukommen, aber damit kalkulieren würde ich nicht), ganz links der Multiplexer für das Multiplexen eines der Operanten. Das Bild würde also grob vier Bits einer Maschine darstellen also 4 CLBs == 4BIT. Umgerechnet ließen sich also auf einem C5VLX330T-2 rund 500 Collatz-Maschinenzusammenbasteln, falls 80 Bits reichen.
Aber so ein C5VLX330T-2 ist natürlich auch ein riesiges, sauteuers Teil, und Boards damit für Schüler, Stundenten und Hobbyisten eigentlich unerschwinglich - deshalb auch meine Vermutung, dass eher mit Grakas etwas realiseirbar ist.

   



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.165, vom Themenstarter, eingetragen 2016-12-26 08:00


@dlchnr

ich arbeite daran das zu verstehen, offenbar ist im FPGA mehr "vorgefertigt" als ich gedacht hatte. Vielen Dank für die ausführlichen Informationen!

@cyrix & al

Das gefällt mir in Summe sehr, sich "in der Mitte zu treffen". Wir könnten also folgendes Programm starten:

- wir wollen alle Startwerte bis 2^67 abprüfen (cyrix in Beitrag 114). Vielleicht bauen wir es am effizientesten so, dass wir die oberen 3 bit im startwert jeweils in acht verschiedenen codeversionen hart codieren, anstatt ein zusätzliches 64bit register einzuführen (was wir dann auch in sachen stoppwert ja jeweils abprüfen müssten).

- es reicht eine pathlogik im 128bit-bereich. wir könnten zB Kandidaten auswerfen die über 118 bit laufen und damit über den Wert #87 nach Roosendaal, und alle gefundenen Kandidaten dann im Nachlauf nach echten Records aussieben. Die 118 wäre dann einstellbar, die begrenzung auf 2x64 Bit pathregister bringt uns einen echten laufzeitvorteil und wäre damit eine "harte" grenze (Amateur in Beitrag #84).

- wir betrachten Reste nach 2^32, deren Anzahl wir möglichst reduzieren, wobei die 32 nicht hart codiert ist sondern einfach änderbar, solange <64 (cyrix in Beitrag 161)

- wir rechnen verteilt auf CPU und zwar ohne Multistep, dafür mit "der inneren Schleife in Assembler". Die Bedingung "ohne Multistep" erlaubt programmierung in ASM erst, da es sonst zu aufwendig wird (find). wir können natürlich die ersten 32 schritte, die der praeprozessor eh ausführen muss, schon zusammenfassen.

- und peilen zB an auf 50 Kernen in 100 Tagen fertig zu sein.

Ich wäre dann aktuell soweit, dass ich für einen einzelnen Rest auf einem Kern bis zur 64bit Grenze um die 10 Minuten brauche, und würde das für als Benchmark für die optimierung der "inneren Schleife" hernehmen.

Dh obiges Programm dürfte realisierbar sein, wenn man erwartet, dass wir sowohl beim Aussieben der Reste als auch bei der konkreten Programmierung noch je eine (gefühlte) Grössenordnung herausholen können.

mit besten xmas wünschen und so
gonz


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



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.166, eingetragen 2016-12-26 15:03


2016-12-26 08:00 - gonz in Beitrag No. 165 schreibt:
@dlchnr

ich arbeite daran das zu verstehen, offenbar ist im FPGA mehr "vorgefertigt" als ich gedacht hatte. Vielen Dank für die ausführlichen Informationen!



Das Grundprinzip eines FPGAs erklärt eigentlich recht schnell der entsprechende Wikipedia-Eintrag  (de.wikipedia.org/wiki/Field_Programmable_Gate_Array#Aufbau_und_Struktur) bzw. die dort gezeigte Abbildung:

de.wikipedia.org/wiki/Field_Programmable_Gate_Array#/media/File:Logic_block2.svg

Sie zeigt auch das Grundproblem von FPGAs - realisiere ich mit einer LUT eine Funktion, der kein Register folgt, ist das entsprechende Register verloren - habe ich umgekehrt nur ein SynchronisationsFlipFlop, dem keine besondere Funktion vorausgeht, die LUT also dazu "verbraten" werden muss, um einen Eingang auf den Ausgang abzubilden, ist auch die im Prinzip verbraten. Sie ist auch "fast" verbraten, wenn vor dem D-Eingang nur ein mickriges UND-Gatter sitzt. Verschiedene konstruktive Verbesserungen an der Grundzelle adressieren solche Probleme, so dass solche "Verluste" seltener vorkommen (bei obigem FPGA von XILINX läßt sich z.B. die LUT mit 6 Eingängen und 1 Ausgang auch umkonfigurieren in 2 LUTs mit 5 Eingängen und 1 Ausgang). Im Prinzip ist es sogar denkbar, dass LUTs/FlipFlops verloren gehen, weil die Routingmöglichkeiten erschöpft sind oder dafür hergegeben werden müssen, um solche zu schaffen. Auch an der Ecke tut sich was von FPGA-Generation zu Generation, hauptsächlich dürfte dieses Problem aber von der Software adressiert werden.



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.167, eingetragen 2016-12-27 18:44



Dh obiges Programm dürfte realisierbar sein, wenn man erwartet, dass wir sowohl beim Aussieben der Reste als auch bei der konkreten Programmierung noch je eine (gefühlte) Grössenordnung herausholen können.

Wird eigentlich, auch wenn sich bei der Aussieberei noch Verbesserungen ergeben, das Prinzip bleiben, dass pro fixen Zahlenabschnitt eine bestimmte Anzahl von immer gleichen Resten zur Zahlenabschnittsbasis zu berechenen sind (also wie z.B. gehabt 116 Reste für einen 3072-Abschnitt) oder können die zu untersucheneden Startwerten auch "kreuz und quer" dagerkommen?



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.168, vom Themenstarter, eingetragen 2016-12-27 18:53


"oder können die zu untersucheneden Startwerten auch "kreuz und quer" dagerkommen?"

könnten sie gerne, aber mir ist (noch) kein entsprechender algorithmus bekannt geworden. realisieren liesse sich das natürlich recht einfach wenn man wüsste wie und welche :)


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



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.169, eingetragen 2016-12-27 22:12


Mit "kreuz und quer" meine ich: nicht durch eine einfache Formel fassbar. Was im Hinblick auf eine Graka-Lösung sicherlich sehr ungünstig wäre - schön wäre es da, wenn ein Recheneinheit z.B. einen Startwerte bekommt und daraus dann weitere z.B. 256 Startwerte berechnen könnte. Denn bei der Übergabe der Startwerte über das "Global Memory" in OpenCL (nur auf dieses hat die Host-CPU Zugriff) kommen sich die Recheneinheiten erst mal ins Gehege und es geht zunächst mal gar nichts, bis alle Einheiten ihren Wert aus dem globalen Speicher gelesen haben. Es wäre also wünschenswert, pro übergebenen Wert möglichst viel Rechnen zu können.  



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.170, eingetragen 2016-12-27 22:26


Also im Moment schwebt mir dafür gerade folgende Lösung (siehe auch schon weiter oben) vor:

Die Berechnung findet in Blöcken der Startzahl der Größe 2^60 statt. CPU-seitig wird bis auf ca. 50 Bit "vorgesiebt". Dann geht für jede  dieser Restklassen die Berechnung der Startzahlen 0*2^50 + Rest bis 1023*2^50 + Rest (für den ersten 2^60er-Durchlauf, analog für die weiteren) auf die GPU, die dann dort nach entsprechend neuen Pathrecords sucht.

Um dabei auszunutzen, dass die GPU mit Floating-Point-Operationen deutlich schneller ist als mit Ganzzahl-Arithmetik, sollte jene nur im Ausnahmefall zum Einsatz kommen, soweit es geht, nur näherungsweise arbeiten. Ideen dazu gibt es schon im derzeitigen CPU-Code.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.171, eingetragen 2016-12-27 23:18


2016-12-27 22:26 - cyrix in Beitrag No. 170 schreibt:
Um dabei auszunutzen, dass die GPU mit Floating-Point-Operationen deutlich schneller ist als mit Ganzzahl-Arithmetik, sollte jene nur im Ausnahmefall zum Einsatz kommen, soweit es geht, nur näherungsweise arbeiten. Ideen dazu gibt es schon im derzeitigen CPU-Code.

Das klingt nach einem komplizierten Algorithmus und bei GPU-Algorithmen denke ich eher ein einfache Algorithmen (Filter und andere Bildverarbeitungsoperationen)?

Ich habe noch keine Erfahrungen mit OpenCL (das Thema interessiert mich aber), habe aber zunächst mal eher an eine Übertragung der optimierten inneren Schleife gedacht, auch wenn sie mit Integer arbeite, weil ich bei einem komplizierten Algorithmus mit vielen bedingt zu vearbeitenden Blöcken rechne?
Und das funktioniert, wenn ich mich da korrekt eingelesen habe, auf Grakas gar nicht gut.

Ein
C
if (odd) {
  x = 3* x + 1;  
} else {
  x = x / 2;
}

wird in etwas übersetzt, was eher einem
C
{
int tmp:
 
tmp = 3* x + 1; 
x = odd ? tmp : x;
 
tmp = x / 2;
x = !odd ? tmp : x;
}

entspricht, d.h. es werden immer alle Pfade durchlaufen.

Die Frage ist also, läßt sich der Floating-Point-Code da effektiv umsetzen?




  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5260
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.172, eingetragen 2016-12-27 23:40


Hallo cyrix,

GPUs sind vor allem schnell, solange es sich vor allem nur um eine 32 Bit Fließkommazahl handelt, d.h. es stehen dir nur 23 Bit für die Mantisse zur Verfügung.

Auf dafür ausgelegten Grafikkarten, wie z.B. jenen die auf der Kepler Architektur aufbauen, hast du auch für FP64 ein 1:3 FP32 Verhältnis, hier sind 64 Bit Operationen um den Faktor 3 langsamer, viele Grafikkarten haben allerdings ein 1:24 oder 1:32 Verhältnis smile

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.173, eingetragen 2016-12-27 23:52


Naja, man muss ja nicht unbedingt viel verzweigen, sondern einfach auf entsprechende, vorberechnete Werte zurückgreifen: Abhängig von der Restklasse des aktuell betrachteten Werts mod 2^k hat man vortabellierte Koffezienten und Absolutglieder, z.B für k=1:

Koeffizient[0] = 1;
Koeffizient[1] = 3;

Absolutglied[0] = 0;
Absolutglied[1] = 2;


Dann erhält man den Collatz-Nachfolger (wobei nach [3x+1]/2 als ein Schritt zählt) von c direkt durch

Rest = x & (2^1-1);
tmp  = x >> 1;
Nachfolger = Koeffizient[Rest] * tmp + Absolutglied[Rest].


Das verzweigt gar nicht. Und da mittlerweile (zumindest bei neureren CUDA-Versionen, bei OpenCL habe ich nicht geschaut) auch der Speicherzugriff in gewisse Rahmen ohne Zeiteinbußen "ungeordnet" erfolgen kann, führt das hier zum Ziel.

Teuer ist hier nur die 128-Bit-Ganzzahl-Multiplikation im letzten Schritt. Und um die zu vermeiden, sollte man zuvorderst erst einmal die Rechnung mit Floating-Point-Arithmetik überschlagen, ob diese überhaupt nötig ist. (Wahrscheinlich kann man da Ganze sogar so implementieren, dass auf der GPU bis zur 64 Iteration auf der GPU [also nach den 50 vorgesiebten] gar keine solche 128-Bit-Ganzzahl-Multiplikation ausgeführt werden muss. Aber das wäre dann erst bei der Optimierung des Codes anzugehen...)

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1826
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.174, eingetragen 2016-12-28 01:12


2016-12-26 15:03 - dlchnr in Beitrag No. 166 schreibt:
Das Grundprinzip eines FPGAs erklärt eigentlich recht schnell der entsprechende Wikipedia-Eintrag  (de.wikipedia.org/wiki/Field_Programmable_Gate_Array#Aufbau_und_Struktur) bzw. die dort gezeigte Abbildung:

de.wikipedia.org/wiki/Field_Programmable_Gate_Array#/media/File:Logic_block2.svg

Sie zeigt auch das Grundproblem von FPGAs - realisiere ich mit einer LUT eine Funktion, der kein Register folgt, ist das entsprechende


LTU ist lookup tabele hab ich jetzt rausgefunden;) man kann also aus 4 bit input ein flipflop setzen nachdem man für jede beliebige logischen Operation die Verknüfungstabelle erstellt.

Also ich könnte aus dem Input xyzq den wert xor (x,y) and (z,q) erstellen oder?
Aber aus den bit input 0101 könnte ich auch die Summe 01+01 berechnen dann bräuchte ich aber ein paar mehr LTUs oder LEs das ist wohl dasselbe?
Bin blutiger Laie, sry.
Aber ein 8 bit Addierer oder Subtractor müsste doch leicht so realisierbar sein?
Wobei der Output 9 flipflops Lämpchen wären, (an/aus) wovon eins overflow ist?
Verstehe aber die MUX nicht.
Und dann die Steuerung mehrere Schritte. Also ein Prozessor.
ich hinke was hinterher aber ist alles total spannend:)
J








  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.175, eingetragen 2016-12-28 01:30


2016-12-28 01:12 - juergen007 in Beitrag No. 174 schreibt:

Verstehe aber die MUX nicht.


Abhängig von der Auswahl des linken Multiplexers berechnet der Adder den nächsten Startwert, R+R/2+1 oder R/2, der rechte Multiplexer reicht das Ergebnis des Adder weiter an das Register oder wählt statdessen R/4, R/8 oder R/16 aus. Das , was der zweite Multiplexer ausgewählt hat, wird bei der nächsten Taktflanke ins Register übernommen.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.176, vom Themenstarter, eingetragen 2016-12-28 08:57


2016-12-27 23:18 - dlchnr in Beitrag No. 171 schreibt:
 d.h. es werden immer alle Pfade durchlaufen.

Es könnte aber sein, dass genau das überhaupt das Ziel ist, weil (aufgrund irgendeines vorhandenen pipe mechanismus) eben mehr zu rechnen schneller ist als öfter zu verzweigen? Das würde zumindest zu meinen Erfahrungen aus der x86 Assembler Welt passen.


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



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.177, eingetragen 2016-12-28 13:51


hallo miteinander,

ich melde mich dann mal wieder. ich muss erstmal sehen wie ich wieder eine ordentliche wie sagt man? work-life-balance? hinbekomme, es kann sein, dass ich doch erstmal eine weile mit mir selber beschäftigt bin. ich wollte mich jedenfalls als "lebt noch" melden. und werde mir das alles mal in ruhe durchlesen was ihr da so geschafft habt!

einen guten Rutsch und -
ausgiebiger dann im neuen Jahr!

Astrid



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.178, eingetragen 2016-12-28 13:55


2016-12-28 08:57 - gonz in Beitrag No. 176 schreibt:
Es könnte aber sein, dass genau das überhaupt das Ziel ist, weil (aufgrund irgendeines vorhandenen pipe mechanismus) eben mehr zu rechnen schneller ist als öfter zu verzweigen? Das würde zumindest zu meinen Erfahrungen aus der x86 Assembler Welt passen.

Das trifft zu, wenn Du pro relativ weniger Instruktion einen Sprung hast (also z.B. ein Verhältnis 3 bis 5 : 1, mein Beispiel-Code gehört sicherlich dazu), wenn die alternativ auszuführenden Blöcke aber länger werden, heißt Ausführung beider alternativer Blöcke auch nahezu Verdoppelung der Ausführungszeit!  

[Die Antwort wurde nach Beitrag No.176 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1826
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.179, eingetragen 2016-12-28 13:58


z.B. Beim Intel sse2 der Befehl Vpaddq xmm1,xmm2,xmm3 addet sowohl die ober als auch unter häfte gleichzeitig ist aber keine 128 Bit-Addition no carry or overwflow wie  gonz ja siumulierte mittels Shl, Rcr.
Aber das trennen und zusammnführen der 128 Bit Register erscheint schwierig.

Achtung,
Sehr umstaendliche methode EINES 128_bit_schrittes:
assembler
movq  xmm0,rax // get low half to rax
punpckhqdq xmm0,xmm0//broadcast the high half of xmm0 to both
movq xmm0,rdx// get high quadword to rdx
 
SHR $1,rdx // halbiere rdx:rax + carry
RCR $1,rax
 
// zusammenkleben rdx:rax zu xmm0
 
movq rax, xmm0  // zero out 127:64
movq rdx, xmm12  
movlhps xmm12, xmm0 \n\t"  //0:63 unchanged, rdx ´= xmm12 to hi quadword of xmm0
 
// Ergebnnis in xmm0 bzw. rdx:rax


Man könnte also die SIMD facility evtl. dazu nutzen um evtl. mehrere 64 bit Operationen gleichzeitig durchführen.

[Die Antwort wurde nach Beitrag No.176 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.180, eingetragen 2016-12-28 14:13


@astrid: Gut zu hören, dass es dir wieder besser geht! :)

@Assembler-Bastler: Nun, 64-Bit-Arithmetik würde erst einmal ausreichen, um jeweils 64 Schritte "näherungsweise" berechnen zu können:

Relevant für die Frage, ob als nächstes ein "x/2"- oder ein "(3x+1)/2"-Schritt folgt, ist ja nur das letzte Bit. Kennt man also die letzten 64 Bit einer Zahl, so sind die nächsten 64 Schritte dadurch festgelegt. Es genügt also dafür alle Berechnungen mod 2^64 auszuführen; oerflows müssen dabei nicht beachtet werden. (Parallel kann man mit Gleitkomma-Berechnungen Näherungswerte der eigentlichen Zahlen mitführen. Und nur in den seltenen Fällen, dass ein Pathrecord-Kandidat gefunden wurde, oder man nach 64 Schritten noch nicht die Stoppzeit erreicht hat, würde man eine exakte Berechnung nachholen; um dann gegebenenfalls den nächsten 64-Bit-Abschnitt genauso anzugehen...)

@GPU-Bastler: Hier gilt das Gleiche, wohl aber nur mit 32 Bit. Hier könnte ich mir vorstellen, dass man auf der GPU für jeweils eine Folge von Startwerten die nächsten k*32 Schritte näherungsweise (gern auch nur mit Floats, das reicht dafür auch) berechnet, schaut, ob dabei ein Path-Record-Kandidat vorkommt und dann in reduzierter Form noch die Startzahlen zurück-übermittelt, die ihre Stoppzeit noch nicht erreicht haben. Da das relativ wenige sein werden, knnen die dafür notwendigen Berechnungen dann wiederum auf der CPU ausgeführt werden.

(Der Anteil der "überlebenden" Startwerte, die also noch nicht ihre Stoppzeit erreicht haben, sollte exponentiell mit der Anzahl der Schritte abnehmen.)


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1826
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.181, eingetragen 2016-12-28 14:16


2016-12-28 01:30 - dlchnr in Beitrag No. 175 schreibt:
2016-12-28 01:12 - juergen007 in Beitrag No. 174 schreibt:

Verstehe aber die MUX nicht.

Abhängig von der Auswahl des linken Multiplexers berechnet der Adder den nächsten Startwert, R+R/2+1 oder R/2, der rechte Multiplexer reicht das Ergebnis des Adder weiter an das Register oder wählt statdessen R/4, R/8 oder R/16 aus. Das , was der zweite Multiplexer ausgewählt hat, wird bei der nächsten Taktflanke ins Register übernommen.
Vielleicht könnte jemand den VDHL code dafür mal zur Ansicht freigeben?
Ich hab diesen vivado VDHL Emulator von xilinx.
Oder einen ganz einfachen 4bit adder + 1 hinterher mit overflow Bit, mit Ausgabe auf was weiss ich, und woher kommen die Startwerte? usb Bus? wo werden da die muxer eingesetzt? Vielleicht gehört das eher in das andere Forum. namasehn


[Die Antwort wurde nach Beitrag No.179 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.182, vom Themenstarter, eingetragen 2016-12-28 14:53


@astrid:
prima! welcome home :)

2016-12-28 14:13 - cyrix in Beitrag No. 180 schreibt:

@Assembler-Bastler: Nun, 64-Bit-Arithmetik würde erst einmal ausreichen, um jeweils 64 Schritte "näherungsweise" berechnen zu können:
[...]
Cyrix

Ja, das wäre eine gute sache, und vielleicht sogar einfacher zu machen als ich es mir bisher vorstellte. es ginge dann natürlich auch mit bitbreiten<64 bit für den "low-anteil" genauso zu machen. ich denke, wenn ich den "brute force" algo durch habe und da nichts mehr zu holen ist könnte ich mich dessen mal annehmen. (wer vorher mag - immer gerne -)

PS.: die für 2^64 verbleibenden reste sind vielleicht mehr als im RAM Platz haben? aber es muss ja nicht 64 sein siehe oben.


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



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1826
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.183, eingetragen 2016-12-28 19:05


2016-12-28 14:53 - gonz in Beitrag No. 182 schreibt:
@astrid:
prima! welcome home :)

2016-12-28 14:13 - cyrix in Beitrag No. 180 schreibt:

@Assembler-Bastler: Nun, 64-Bit-Arithmetik würde erst einmal ausreichen, um jeweils 64 Schritte "näherungsweise" berechnen zu können:
[...]
Cyrix

Ja, das wäre eine gute sache, und vielleicht sogar einfacher zu machen als ich es mir bisher vorstellte. es ginge dann natürlich auch mit bitbreiten<64 bit für den "low-anteil" genauso zu machen. ich denke, wenn ich den "brute force" algo durch habe und da nichts mehr zu holen ist könnte ich mich dessen mal annehmen. (wer vorher mag - immer gerne -)

PS.: die für 2^64 verbleibenden reste sind vielleicht mehr als im RAM Platz haben? aber es muss ja nicht 64 sein siehe oben.

Man könnte noch alle 2^32-1 = 4,294,967,291 und deren pathrecord in einer Lookup table halten. (array) Zu aufwendig ? OK. Aber:
Davon sind ja nur die interessant die Bit 32 setzen. Das sind nicht sehr viele. Und die rechnet man voraus.
Man braucht das nur einmal machen. Und es bleibt eine kleinere LUT.
Man hat dann eine LUT mit den interesanten Zahlen deren Stopwerte nicht bekannt sind. Nur die sollten weiterverfolgt werden. (if array_key_exists...) in asm.
J
P.S.: Ich versuch immer noch Tasm und Frespascal zu vereinen das mag ich lieber als c++ und dies GAS ding.



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.184, eingetragen 2016-12-28 19:16


2016-12-27 23:52 - cyrix in Beitrag No. 173 schreibt:
z.B für k=1:

Koeffizient[0] = 1;
Koeffizient[1] = 3;

Absolutglied[0] = 0;
Absolutglied[1] = 2;


Dann erhält man den Collatz-Nachfolger (wobei nach [3x+1]/2 als ein Schritt zählt) von c direkt durch

Rest = x & (2^1-1);
tmp  = x >> 1;
Nachfolger = Koeffizient[Rest] * tmp + Absolutglied[Rest].


Ein paar Verständnisfragen - hier geht es um die Multistep-Variante?

Denn für k=1, also (2^1-1) läßt sich das ja ohne Multiplikation lösen:

flag = x & 1;
mask = -((signed uint128_t) flag);
temp = x >> 1;
x &= mask;
x += temp + flag;

[Die Antwort wurde nach Beitrag No.182 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.185, eingetragen 2016-12-28 19:29


2016-12-28 14:13 - cyrix in Beitrag No. 180 schreibt:
Relevant für die Frage, ob als nächstes ein "x/2"- oder ein "(3x+1)/2"-Schritt folgt, ist ja nur das letzte Bit. Kennt man also die letzten 64 Bit einer Zahl, so sind die nächsten 64 Schritte dadurch festgelegt. Es genügt also dafür alle Berechnungen mod 2^64 auszuführen; oerflows müssen dabei nicht beachtet werden. (Parallel kann man mit Gleitkomma-Berechnungen Näherungswerte der eigentlichen Zahlen mitführen. Und nur in den seltenen Fällen, dass ein Pathrecord-Kandidat gefunden wurde, oder man nach 64 Schritten noch nicht die Stoppzeit erreicht hat, würde man eine exakte Berechnung nachholen; um dann gegebenenfalls den nächsten 64-Bit-Abschnitt genauso anzugehen...)

Und hier wird wieder die Single-Step-Variante betrachtet und vorgeschlagen, statt "richtig" (mit 128bit) zu rechnen, nur mit 64bit und jeden Schritt ein zweites mal mit Floiting Point durchzuführen - und bei all denen, die nicht ausgesiebt wurden, dann doch noch mal alles richtig durchrechnen?

Also mit 32 Schritten geht sich das sicherlich nicht aus, wenn gonz für den interessant Bereich (ab #87) durchschnittlich etwas über 24 Schritte bis zum erreichen des Startwerts ermittelt hat - da bleiben nach 32 Schritte doch bestimmt zu viele übrig?



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.186, eingetragen 2016-12-28 20:22


2016-12-28 14:16 - juergen007 in Beitrag No. 181 schreibt:
Ich hab diesen vivado VDHL Emulator von xilinx.
Oder einen ganz einfachen 4bit adder + 1 hinterher mit overflow Bit, mit Ausgabe auf was weiss ich, und woher kommen die Startwerte? usb Bus? wo werden da die muxer eingesetzt?

Die Startwerte kämen von einem Counter, wie hier
LinkDie Collatz-Folge programmieren
schon mal beschrieben.

Hier eine für die "dicken" XILINX-Bauteile optimierte Version (bzw. für alle FPGAs, die eine in zwei 5er-LUTs teilbare 6LUT haben.

Nachteil - die Operation R/4, R/8, R/16 nicht verfügbar.
Vorteile - eine Laufzeit entfällt (dadurch eine höhere Taktfrequenz möglich) und eine einzelne Collatz-Maschine belegt nur noch 3/4 der zunächst angesetzten Resourcen => 33% mehr Collatz-Maschinen auf einem Chip.




  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.187, eingetragen 2016-12-28 20:50


@gonz, jürgen: Also mir ist unklar, was ihr da inhaltlich vorhabt. Man wird nicht 64 (oder auch nur 32) Schritte am Stück gehen können; wohl aber z.B. je 8, deren Ergebnisse man vortabelliert hat. Macht man das mod 2^64, dann gehen einem nach insgesamt 64 Einzelschritten die Informationen aus, sodass man dann, wenn bis dahin noch nicht die Stoppzeit erreicht wurde, noch einmal "richtig", mit "voller Genauigkeit" nachrechnen muss. (Auch hier reicht in den meisten Fällen wohl 128-Bit-Arithmetik aus, da die meisten betrachteten Werte dann bis Schritt 128 ihren Stoppwert erreicht haben werden; und nur für die wenigen, die darüber hinausgehen, werden dann größere Datentypen gebraucht...)

@dlchnr:
*) Beitrag #184: Ja, genau: Das ließe sich gleich auf multi-step verallgemeinern. Dabei könnte man die Arrays in ein const-memory hochladen, da diese ja für jede Berechnung die gleichen sind. Aber ja, deine single-step-Variante sieht gut aus, wobei man zumindest bei CUDA (keine Ahnung bezügl. OpenCL, wobei das nach meinem Empfinden von vor ein paar jahren jeweils weniger Möglichkeiten bot als OpenCL) wohl keine native 128-Bit-Ganzzahl-Unterstützung hat, sich die Sachen also selber bauen müsste. Aber, wie gesagt, zumindest für eine ganze Reihe an Schritten sollte man auch erst einmal nur mit 32- bzw. 64-Bit-Arithmetik auskommen.

*) Beitrag 185: Genau: Erst rechnet man hier einerseits im Ganzzahl-Bereich mod 2^64 (um die jeweils relevanten End-Bits zu erhalten) und per Floating-Point (für die Größe, damit man weiß, ob ein Path-Record bzw. Stoppwert erreicht wurde). Und ert nach insgesamt 64 Einzelschritten muss man bei den üerlebenden Kandidaten die Berechnung noc einmal "exakter" mittels 128-Bit-Arithmetik bzw. noch genauer, wenn danach noch mehr als 64 wetere Schritte benötigt werden, mit beliebiger Genauigkeit nachrechnen... (Auf einer GPU würde an wahrscheinlich hier wohl vermutl. erst einmal nur mod 2^32 rechnen, weil es einfacher erscheint. Dementsprechend müsste man nach 32 Schritten schauen, ...)

Wie weit man hierdurch aussieben kann, müsste man mal experimentell schauen. Dabei sei aber zu beachten, dass schon derzeit aus dem Sieb die Ergebnisse herausfallen, die nach 32 Schritten noch überlebt haben. Und für diese kennen wir das Ergebnis der 32. Iteration schon. (Außerdem, s.o., habe ich vor, das Sieb hierbei bis zur ca. 50. Iteration fortzuführen. Das macht dann die Verwaltung der Path-Record-Kandidaten dann schiweriger, um die man sich ann extra noch einmal kümmern muss...)

Will sagen: Interessant wäre eine Aufstellung, welcher Anteil derjenigen Startzahlen, die nach 32 (später vlt. 50) Iterationen ihre Stoppzeit noch nicht erreicht haben, weitere 32, 64, 128, ... Iterationen überleben.

In gewissem Maße findet man dergleichen bei Olivera e Silva (von Slash in Beitrag #22 dieses Threads verlinkt) in Tabelle 1. Dort ist der Anteil der Restklassen mod 2^k mit Stoppzeiten > k angegeben (vorletzte Spalte). Wenn ich das mal so "Pi mal Daumen" betrachte, könnte man etwa mit einer Halbierung der überlebenden Zahlen alle ca. 8 zusätzliche Schritte rechnen. Runden wir den Anteil der dann noch weiter zu testenden Zahlen pessimistisch etwas auf, so sollten nach 32 weiteren Schritten nur noch ca. jede 10. Startzahl nicht ihren Stoppwert erreicht haben, nach 64 nur noch jede 100.

edit: Schaut man sich die Grafik auf der nächsten Seite des Papers an, ist die Sache doch nicht mehr so optimistisch zu betrachten. Nach den dortigen Abschätzungen sieht bei den späteren Iterationen nur mehr nach einer Halbierung der Kandidatenzahl alle 32 weiteren Iterationen aus, keine Zehntelung...

Cyrix

[Die Antwort wurde nach Beitrag No.185 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.188, vom Themenstarter, eingetragen 2016-12-28 20:54


2016-12-28 20:50 - cyrix in Beitrag No. 187 schreibt:
@gonz, jürgen: Also mir ist unklar, was ihr da inhaltlich vorhabt. Man wird nicht 64 (oder auch nur 32) Schritte am Stück gehen können; wohl aber z.B. je 8, deren Ergebnisse man vortabelliert hat. Macht man das mod 2^64, dann gehen einem nach insgesamt 64 Einzelschritten die Informationen aus, sodass man dann, wenn bis dahin noch nicht die Stoppzeit erreicht wurde, noch einmal "richtig", mit "voller Genauigkeit" nachrechnen muss. (Auch hier reicht in den meisten Fällen wohl 128-Bit-Arithmetik aus, da die meisten betrachteten Werte dann bis Schritt 128 ihren Stoppwert erreicht haben werden; und nur für die wenigen, die darüber hinausgehen, werden dann größere Datentypen gebraucht...)

Ja genau, so habe ich mir das inzwischen auch überlegt. Dh man siebt auf die Art die Folgen aus, die weiter als 64 bit gehen ohne dem Startwert zu nahe zu kommen. Wie viele das sind kann ich einfach mal ausrechnen, indem ich dem klassischen brute force programm beibringe, zu zählen welche folgenlänge mit welcher wahrscheinlichkeit vorkommen.


Auch hier reicht in den meisten Fällen wohl 128-Bit-Arithmetik aus, da die meisten betrachteten Werte dann bis Schritt 128 ihren Stoppwert erreicht haben werden; und nur für die wenigen, die darüber hinausgehen, werden dann größere Datentypen gebraucht...)

genau, damit haben wir einen dreistufigen prozess. aber das ist ja kein problem :)



-----------------
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: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.189, eingetragen 2016-12-28 21:15


@gonz: Ja, so eine Aufstellung wäre ganz gut, damit man sieht, wo man eigentlich wie viel Energie hineinstecken muss.

In einer "Wunsch-Welt" würde das Programm m.E. etwa wie folgt arbeiten:

-1.: Sieb der Restklassen mod 2^32. Diese werden "herausgeschrieben" und können so zur Parallelisierung auf mehrere Threads und auch über verschiedene Rechner verteilt werden.

0.: Jede dieser Restklassen wird intern, innerhalb eines CPU-Threads weiter bis etwa 2^50 vorgesiebt.

1. Abhängig von einer vorgegebenen Startzahl (Vielfaches von 2^60) werden nun für jede dieser Restklassen mod 2^50 für die Startwerte "Startzahl + i * 2^50 + Restklasse", i= 0 bis 1023 entweder direkt, oder schon ihre gerade berechneten 50. Iterationen an die GPU übergeben. (Letzteres ist bezügl. der Berechnung effektiver, da da die Berechnung der 50. Iteration ja schon implizit erfolgt ist; aber bezügl. der Kommunikation via BUS teurer, da mehr Daten transferiert werden müssen.) Dort werden die nächsten 32 oder 64 Schritte für diese konkreten Startwerte näherungsweise und hochgradig parallel berechnet. Zurückgemeldet an die CPU wird, bei welchen - wenigen - Startzahlen eine genauere Berechnung von Nöten ist.

2. Wieder auf der CPU schaut man sich die verhältnismäßig wenigen Startwerte an, die bisher noch nicht aussortiert wurden. Hier könnte der Assembler-Code zum Einsatz kommen, da bei einigen Kandidaten die Stoppzeit eben doch deutlich über dem Durchschnitt liegen wird. (Für die GPU wollen wir aber, dass möglichst viele Threads etwas zu tun haben. Wenn nur noch einer von hundert Threads dort rechnet, ist das ineffizient. Deshalb sollte man schon zuvor wieder von dort auf die CPU zurückkehren.)

3. Es braucht eine Verwaltung potentieller Path-Record-Kandidaten, da die Startwerte nicht in aufsteigender Reihenfolge betrachtet werden. Erst mit dem Abschluss eines solchen 2^60er-Blocks weiß man dann, welche Kandidaten wirklich zu Pathrecords führen... Das erscheint mir aber eine (vom Rechenaufwand her) sehr kleine Aufgabe.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1826
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.190, eingetragen 2016-12-28 23:48


Das ist wahrscheinlich keine Sensation. Mit Intel SSE2 128 Bit Rechenmethoden.

Nach meinem Berechnungen stimmt der pathrecord von Oliveira, wie auf der Website: Rosendaal.

Danach ist pathrecord #88:
Berechnet:

START: 1,980976,057694,848447 loop : 400
flags : E1A

pathrecord #88 = xmm2: 64,024667,322193,133530,165877,294264,738020

Neuer Maximalwert : 64,024667,322193,133530,165877,294264,738020

Hex: 302a b3d0 52fb 87c0 6228 d249 581b e0e4 (126 bit)

Also jedenfalls zum Wert START passt der Wert pathrecord #88 nach obiger Quelle.
Die Werte von #66 - #87 hatte das Prog auch verifiziert, so dass ich ihm vertrauen kann.

Die zwischen (#87-#88) liegenden hab ich noch nicht betrachtet. Bin dabei.


Thx




  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.191, eingetragen 2016-12-29 10:32


Die Werte an sich hatte ich auch schon bestätigt:
www.mikrocontroller.net/topic/413678#4827670

Die Frage ist halt, ob nicht vielleicht die "wahre" #88 zwischen 1,038743,969413,717663 und 1,980976,057694,848447 liegt und
1,980976,057694,848447 vielleicht die #89 ist oder gar ganz aus der Liste verschwindet!?



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.192, eingetragen 2016-12-29 13:53


Das Testen einzelner Startzahlen ist ziemlich wertlos: Davon müssen Billionen und Aberbillionen durchlaufen werden...

@Parallel-Thread bei mikrocontroller: Ihr könnt ruhig auch die Erkenntnisse nutzen, die wir hier schon erarbeitet haben. Insbesondere, dass es zum Einen viel bringt, wenn man nicht nur die ersten 10 Bits - wie du es bisher machst - vorsiebt, sondern deutlich tiefer; und zum Anderen auch, dass "Rückwärts-Iterationen" betrachtet werden, d.h., man eine Zahl/ Restklasse auch dann ausschließen kann, wenn sie einen weiteren Collatz-Vorfahren < sich selbst besitzt. Beide Maßnahmen zusammen bringen uns gegenüber dem Sieben der Startzahl nur bis Bit 10 etwa eine Größenordnung an Durchsatz.

Auch die Überlegung via näherungsweiser Berechnung mod 2^64 und parallel als Gleitkomma-Zahl bringt einen deutlichen Geschwindigkeitsvorteil gegenüber dem Versuch mit Multi-Precission-Datentypen (oder auch nur mit 128-Bit) zu arbeiten.

Es wäre Schade, wenn diese Erkenntnisse versauern. Lieber sollte man alle Ideen gemeinsam in einem einzigen Projekt umsetzen, als zwei halbgare "Konkurenz-Projekte" zu erhalten...

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.193, eingetragen 2016-12-29 16:06


2016-12-29 13:53 - cyrix in Beitrag No. 192 schreibt:

@Parallel-Thread bei mikrocontroller:
:
halbgare "Konkurenz-Projekte"

Cyrix

Ich betrachte die beiden Threads nicht als "Konkurenz-Projekte",
der Thread auf mikrocontroller.net wurde ja von MPlern losgetreten und zum großen Teil bestritten.

Im Prinzip gings dort ja zunächst um FPGAs, bis sich zeigte, dass mit Grakas höchstwahrscheinlich eine kostengünstigere massiv-parallele Lösung möglich ist.

Die OpenCL Richtung würde ich dann sowieso wieder eher hier diskutieren, weil es dann doch nicht mehr so recht zu einem FPGA Forum passt.



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.194, eingetragen 2016-12-29 16:12


2016-12-28 20:50 - cyrix in Beitrag No. 187 schreibt:
Interessant wäre eine Aufstellung, welcher Anteil derjenigen Startzahlen, die nach 32 (später vlt. 50) Iterationen ihre Stoppzeit noch nicht erreicht haben, weitere 32, 64, 128, ... Iterationen überleben.


tst1:

(3 x + 1)/2 und x/2 wurden jeweils als ein Schritt gezählt.
Daten aus dem Bereich #87+.  

steps, remaining values
  25,      27.78%
  32,      15.71%
  50,      5.435%
  64,      2.451%
  75,      1.354%
 100,      0.393%
 128,      0.115%
 150,      0.042%






  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1826
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.195, eingetragen 2016-12-29 16:54


2016-12-29 16:12 - dlchnr in Beitrag No. 194 schreibt:

(3 x + 1)/2 und x/2 wurden jeweils als ein Schritt gezählt.
Daten aus dem Bereich #87+.  

steps, remaining values
  25,      27.78%
  32,      15.71%
  50,      5.435%
  64,      2.451%
  75,      1.354%
 100,      0.393%
 128,      0.115%
 150,      0.042%


Verstehe nicht Zusammenhang steps und remaining.


Das Programm, was ich eben nutze, ist erheblich verbesserungsfähig welch ein deutsch, aber verbesserbar klingt auch falsch, oder sagen wir verbesserungswürdig.
Dann wollte ich mal das 3072 Raster (fast 12 bit ) von gonz nutzen oder von wem,

#define base_step 3072
unsigned int reste[]={
27,31, 63, 91, 103, 111, 127, 159, 207, 231, 255, 283, 303, 319, 327, 411, 415, 447, 463, 487, 495, 511, 543, 559, 603, 615, 639, 667, 679, 703, 751, 763, 795, 799, 831, 859, 871, 879, 927, 1023, 1051, 1071, 1087, 1095, 1135, 1179, 1183, 1191, 1215, 1231, 1255, 1263, 1275, 1279, 1327, 1351, 1383, 1435, 1471, 1519, 1563, 1567, 1627, 1639, 1647, 1663, 1695, 1767, 1791, 1819, 1855, 1863, 1903, 1951, 1959, 1983, 2031, 2043, 2047, 2079, 2095, 2119, 2139, 2151, 2175, 2203, 2215, 2239, 2287, 2299, 2331, 2367, 2407, 2463, 2511, 2535, 2559, 2587, 2607, 2671, 2715, 2719, 2727, 2751, 2791, 2799, 2811, 2815, 2847, 2887, 2907, 2919, 2983, 3007, 3055, 3067};
#define reste_amount 116

oder rechne ein besseres 16 oder 32 bit Raster vor.

Trotzdem bleiben es noch viele Billionen Rechnungen.

Wie ja angedeutet ist eine Art 3fach "Vorrasterung" sinnig.  Die "Verläufe"  der Zahlen unter 2^64 sind nicht unbedingt bekannt, denn der höchste Startwert ist unter 2^64.
Abbruch wenn eine Folge unter 2^64 läuft, nachdem sie schon mal höher war? Nee.oder?
Abbruch, wenn eine Folge ungerader Zahlen kleiner wird, davon ausgehend wir wissen die Collatz-Richtigkeit aller vorhergehenden.
Und die wissen wir ja bis #87.
Parallelisierung und Verteilung auf FPGA s oder LUT s ist Klasse, aber ich hab da zu wenig Ahnung von noch.  
Oder das Forken auf  einem 8 Kern Prozessor mit  gcc oder c++ nutzen.
Ist alles nix neues ich wollte das mal für mich zusammen fassen.

Dass sich die Werte

__uint128_t    start =  1 038743 969413 717663;  // path_record #87   =      319391 343969 356241 864419 199325 107352
__uint128_t    start =  1 980976 057694 848447;  // path_record #88   = 64 024667 322193 133530 165877 294264 738020

ca. um Faktor 350 unterscheiden ist merkwürdig, auch deswegen weil sich die Startwerte nicht mal um Faktor 2 ändern aber möglich ist alles.

Jürgen




  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2470
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.196, vom Themenstarter, eingetragen 2016-12-29 17:04



oder rechne ein besseres 16 oder 32 bit Raster vor.

Das was ich habe ist in PHP geschrieben und einfach für Bitzahlen jenseits der 16 etwas zu langsam. Man könnte das aber auch einfach in C umschreiben dann ist es natürlich fixer.

Die 3027 resultiert daraus, dass ich 3*2^10 hergenommen habe, also 10 vorwärtsschritte und einen rückwärtsschritt mit dem Faktor 3. Der zweite Rückwärtsschritt bringt wenn ich mich nicht geirrt habe nichts, sodass der nächste Wert der hier sinn machen würden die 27 ist. Speichern kann man das bis zu recht hohen werten, man hat ja megabyteweise RAM zur Verfügung, sodass auch die 20 Millionen Reste die cyrix für 2^30 angegeben hat durchaus passen und vergleichsweise schnell abrufbar wären.


Abbruch wenn eine Folge unter 2^64 läuft, nachdem sie schon mal höher war? Nee.oder?
Naja, Abbruch, wenn man unter den Startwert kommt (vorausgesetzt man hat alle kleineren Werte ausgeschlossen oder/und durchgerechnet :) ich hatte auch probiert, wegen der schnelleren Prüfung auf unterschreiten einer 2-er potenz zu testen (die dann nur aus dem MSB des Startwerts besteht), aber das ist nach dem was ich ermittelt habe langsamer, dh das durchrechnen weiterer folgenglieder ist aufwendiger als es die einfachere stop-prüfung ausgleichen könnte...


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



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.197, eingetragen 2016-12-29 18:42


2016-12-29 16:54 - juergen007 in Beitrag No. 195 schreibt:
2016-12-29 16:12 - dlchnr in Beitrag No. 194 schreibt:

(3 x + 1)/2 und x/2 wurden jeweils als ein Schritt gezählt.
Daten aus dem Bereich #87+.  

steps, remaining values
  25,      27.78%
  32,      15.71%
  50,      5.435%
  64,      2.451%
  75,      1.354%
 100,      0.393%
 128,      0.115%
 150,      0.042%


Verstehe nicht Zusammenhang steps und remaining.

Ein Pool an Kernen auf einer Graka hat nur einen Instruktion-Pointer - d.h. alle Kerne müssen die gleichen Instruktion ausführen.
Ein einzelner Kern kann also nicht, wenn er seinen Startwert nach nur 5 Iterationen(== 5 Schritte/Steps) unter den Startwert iteriert hat mit der Bearbeitung der nächsten Folge/des nächsten Startwerts beginnen - er muss schön weiteriterieren - solange - nun ja, bis wir halt sagen, jetzt halten wir an, und schauen, welche Folgen noch nicht unter ihren Startwert gefallen sind und bearbeiten die eben mit 'ner richtigen CPU. Die Tabelle gibt nun an, wieviele Startwerte/Folgen übrig bleiben und von einer CPU untersucht werden müssen, wenn ich die Kerne 25, 32, 50, 64, ... Iterationen durchlaufen lasse.

Ich habe dazu einfach den Code, den ich für die Kerne einer Graka angedacht habe, auf einem PC simuliert.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2355
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.198, eingetragen 2016-12-29 19:26


@dlchnr: Deine Werte verwirren mich etwas. Was sind deine Startbedingungen, d.h., was wären 100%? Sicherlich nicht beliebige Startzahlen, sondern nur irgendwelche spezielle. (Ich tippe mal darauf, dass du nur solche Zahlen betrachtest, die in einer nicht-ausgesiebten Restklasse mod ??? liegen, diese aber wieder jeweils von Iteration 1 an berechnest?)

@Rückwärtsiterationen: Wir wissen ja, dass aus 2k+1 man in eine Schritt zu 3k+2 gelangt. Ein Rückwärtsschritt besteht also nun in der Erkenntnis, dass, sollte in der Collatz-Folge für einen Startwert x irgendwann ein Element y auftauchen, dass == 2 (mod 3) und < 3/2 * x ist, dessen weitere Berechnung abgebrochen werden kann: Es existiert dann nämlich ein Collatz-Vorgänger z von y, der kleiner als x ist. Die weitere Collatz-Folge von x haben wir also bei der Betrachtung von z schon früher einmal abgehandelt, müssen sie demnach nun nicht wiederholt berechnen.

Dieses Argument gilt für den Startwert x selbst, aber auch alle späteren Folgenglieder! (Allein nur die Kongruenz mod 3*2^k zu betrachten, schaut dabei nur auf den jeweiligen Startwert, nicht die weiteren Folgenglieder...)

Und so lohnen sich auch weitere Rückwärtsiterationen, wie sie in der Methode "corfactor" etwa in Beitrag #161 dieses Threads angewendet werden. Dabei wird dort der jeweilige Faktor ermittelt, um den ein entsprechender Vorgänger kleiner ist als der gerade betrachtete Wert; im Fall 3k+2 (Zeile 5 im dortigen Code) ist dies etwa der Faktor 2/3; für 9k+4 der Faktor 8/9 (wegen 8k+3-->9k+4).

Der Effekt scheint am Anfang sehr überschaubar zu sein, doch mit dem Sieben von größeren Bit-Tiefen zahlt sich diese Betrachtung deutlich aus. So überleben z.B. nur etwa halb so viele Restklassen beim Sieben bis 2^32, wenn man diese Rückwärtsiterationen betrachtet, als wenn man es nicht macht.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Monat
Dabei seit: 20.04.2013
Mitteilungen: 123
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.199, eingetragen 2016-12-29 22:00


2016-12-29 19:26 - cyrix in Beitrag No. 198 schreibt:
@dlchnr: Deine Werte verwirren mich etwas. Was sind deine Startbedingungen, d.h., was wären 100%? Sicherlich nicht beliebige Startzahlen, sondern nur irgendwelche spezielle. (Ich tippe mal darauf, dass du nur solche Zahlen betrachtest, die in einer nicht-ausgesiebten Restklasse mod ??? liegen, diese aber wieder jeweils von Iteration 1 an berechnest?)

100% ist das, was in den GPU-Simulations-Code reingeht, also das, was nach dem von gonz in seinem Assemblerprogramm eingesetzten Sieb noch übrig bleibt.  

In GPU(..) werden eine vorgegebene Anzahl von Iteration ausgeführt,
CPU(..) iteriert bis zum Startwert und gibt alles an CHK(..) weiter, was größer als der Pfadrekord von #87 ist. CHK(..) arbeitet mit GMP, ist also nicht auf 128bit beschränkt.




  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 5Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8  
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]