Forum: FPGA, VHDL & Co. 128 Bit Risc


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hi!

Ich suche eine Möglichkeit, mit sehr großen Zahlen ca 2 ^128 einfache 
Rechnungen durchzuführen.
An sich brauche ich nur Integer-Operationen: Shl Shr, Rrc, Rlc und or, 
xor, and, Compare und add.
Das Bit 128 kann das sign bit sein. Muss nicht.
Multiplikationen und Divisionen kann ich wenn nötig selber schreiben bin 
Mathematiker. Kein Floating Point benötigt. Ich kann auch aus 32 bit 
words 128 bit Operationen simulieren. Das wäre aber nicht optimal.

Nach vielen Versuchen mit den sog. SSE Extensions der neuesten Intel und 
Xeon Prozessoren, glaub ich es geht damit nicht. Die Flags werden nicht 
richtig gesetzt oder gar nicht..
Kann man so was mit FPGA realisieren? evtl mehreren?
Gibt es einen default Befehlssatz?
Ich weiss auch nicht ob und wie ich z.b. dieses Gerät "easyFpga" s.u. an 
ein normalen PC anbinde und ins ddr3 ram schreibe und ob es Assembler 
gibt, die ja den Mikrocode erzeugen sollen.
Und wie realisiert man Ein und Ausgabe Routinen der Hex Zahlen?
Also an sich suche ich einen schnellen RisC Prozessor mit hoher interner 
Registerbreite.
Wer sich für mathe interessiert dem kann ich gern erzählen worauf ich 
hinaus will:)
Ist easyFpga zu empfehlen: recht preiswert.
https://www.os-cillation.de/easyfpga-kaufen-landing/?gclid=CjwKEAiA94nCBRDxismumrL83icSJAAeeETQtLfFeBenuLyPksiJ_tLtEiplCq2_lxIuQ3O1HLeYzxoCeVrw_wcB


Danke für jeden Hinweis
MM.

von Markus W. (elektrowagi78) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert

von Blechbieger (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Das hängt sehr von der Anwendung ab ob sich das überhaupt lohnt. Zum 
einen wird so eine riesige ALU im FPGA langsam sein im Vergleich zu 
einer 64- Bit ALU in einem aktuellen  PC-Prozessors. Zum anderen wird 
die Übertragung der Daten zwischen PC und FPGA schnell ein Flaschenhals.

Schau dir lieber Mal GMP an, ist eine Bibliothek für beliebig große 
Zahlen.

von --- (Gast)


Bewertung
0 lesenswert
nicht lesenswert
> Ich weiss auch nicht ob und wie ich z.b. dieses Gerät "easyFpga" s.u. an
> ein normalen PC anbinde

Das sieht nach einem (sehr) kleinen Spartan aus.
Nur die gaaanz kleinen gibt es in diesem Package.
Und mehr als freie IOs entdecke ich da auch nicht.
Gegenueber den internen SSE-Befehlen, die du schon entdeckt hast,
wird jede Anbindung an den PC(-Bus) grottenlangsam sein.
Wenn Mann nicht am PCIe-Bus herumfuhrwerken will,
wofuer der gezeigte FPGA auch nicht in der Lage waere,
bliebe eine parallele Anbindug z.B. ueber den USB-Bus
und z.B. einen CY7C68013A. Den muesstest du an dieses
Board dann noch anschliessen.

126 Eu fuer so ein Board ist auch nicht annaehernd preiswert.
Vergleichbares, mit etwas aelteren FPGA (Cyclone 2),
bekommst du aus Chine fuer < 15 Eu.

Wenn es schnell sein soll, such dir ein Board was per
PCIe an den Host anschliessbar ist.
Das wirst du fuer 126 Eu wohl nicht bekommen.

Die Instanziierung ueber ein Java-Interface ist auf
lange Sicht auch eher hinderlich, weil sie alles
was optimierbar waere hinter dem eigenen Mechanismus
verbirgt. Da kommt Mann um VHDL/Verilog nicht herum.
Fuer die Einbindung wirst du dann auch noch IPs fuer
die PCIe-Komponente erwerben wollen muessen, falls
du die nicht selber machen willst...

Wenn Geld keine Rollt spielt, gibt es bei Intel/Altera
sowas sicher auch fertig zu kaufen.

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
--- schrieb:
> Wenn Geld keine Rollt spielt, gibt es bei Intel/Altera
> sowas sicher auch fertig zu kaufen.

http://www.golem.de/news/broadwell-ep-intel-zeigt-xeon-e5-mit-arria-fpga-auf-einem-package-1603-119772.html

von Karl (Gast)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Ich kann auch aus 32 bit words 128 bit Operationen simulieren. Das wäre
> aber nicht optimal.

Nicht optimal inwiefern? Dann nimm zwei Mal 64 Bit. Ich sehe nicht wie 
du mit einer fpga Lösung schneller oder sonst was werden könntest.

Was du willst ist klar nur verstehe ich das Problem mit der 
offensichtlichen Lösung nicht.

von (prx) A. K. (prx)


Bewertung
2 lesenswert
nicht lesenswert
Er schreibt von Flags. Traditioneller Umgang mit Flags ist tatsächlich 
ein schwacher Punkt bei SSE. Aber das liegt massgeblich an Arbeitsweise 
und Ziel dieser Befehle, denn auch wenn sich SSE-128 vereinzelt auf eine 
geschlossene 128-Bit Operation bezieht geht es doch meist um mehrere 
parallel arbeitende Operationen auf kleinere Operanden. Und was könnte 
man dabei mit klassischen Flags schon viel anfangen?

SSE Optimierung arbeitet deshalb wenn möglich anders. Nicht mit massiv 
von bedingten Sprüngen durchsetztem Code, dessen Pipeline-Ausnutzung bei 
aller Qualität von Sprungvorhersage doch immer wieder auch klassischen 
Schweizer Käse an Löchern schlägt. Sondern indem weitestmöglich 
alternative Datenpfade durch bedingte Operationen (conditional move: 
results über and/or mit masks rekombiniert, ...) statt bedingten 
Programmablauf ersetzt werden. Die auch bei einfachen Operationen 
tieferen Pipelines von SSE Operationen werden es danken.

Seine Schilderung hingegen zielt auf klassische Integer-Befehle ab, nur 
dummerweise eben mit 128-Bit Operanden. Mit klassischem von bedingten 
Sprüngen dominiertem Code. In klassischem Integer-Code findet man oft 
eine bedingten Sprung auf 3-5 Befehle. Wenn es ihm nicht gelingt, seine 
Algorithmen auf eher Datenfluss-orientierte Arbeitsweise umzustellen, 
dann hilft ihm SSE nicht viel.

: Bearbeitet durch User
von Karl (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Immer sehr interessant deine Beiträge. Respekt.

Kenne mich mit sse jetzt nicht in dem Detail aus. Meine Frage nach dem 
Problem mit der offensichtlichen Lösung bezieht sich darauf, was gegen 
die ganz normalen integer Befehle spricht inkl carry etc.

Ich wage einfach zu bezweifeln dass ein fpga eine aktuelle cpu bei solch 
einfachen Operationen schlagen kann, insbesondere wenn man den Overhead 
berücksichtigt. (Von massiv parallel verarbeiteten Daten im fpga 
abgesehen)

Vielleicht kann der OP etwas Licht ins Dunkel bringen.

von Jürgen S. (engineer) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Ich sage mal, daß die Operationen in einem FPGA sehr leicht 
implementierbar sind, wenngleich da bei den Auflösungen die Datenraten 
doch gewaltig nach unten gehen. Die Problematik ist dann zudem, die 
Daten ein und raus zu bekommen. Wenn dort nur zu einem gewissen 
Prozentsatz gerechnet werden muss, ist eine manuelle Emulation in einem 
Intel-Core wohl zielführender.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Also an sich suche ich einen schnellen RisC Prozessor mit hoher interner
> Registerbreite.
Definiere "schnell".
Denn schnell wird ein FPGA nur, wenn du parallel arbeiten kannst. 
Ansonsten ist jeder "kreuzlahme" 600Mhz Rechner schneller als ein 
(Anfänger-)FPGA-Design. Und vor Allem: den kannst du fertig kaufen. Bis 
das mit dem FPGA läuft, dauert das sicher 1-2 Mannjahre...

von Nase (Gast)


Bewertung
-3 lesenswert
nicht lesenswert
matthias schrieb:
> Multiplikationen und Divisionen kann ich wenn nötig selber schreiben bin
> Mathematiker.
Bwahaha.

Seltsame Anforderungen hast du da.
Ich rechne z.Zt. aus anderen Gründen mit 1024 Bit (Mantisse) breiten 
Gleitkommazahlen.
Auf einem 8-Bit-AVR.

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Nase schrieb:
> Ich rechne z.Zt. aus anderen Gründen mit 1024 Bit (Mantisse) breiten
> Gleitkommazahlen. Auf einem 8-Bit-AVR.

Alles eine Frage der Zeit. ;-)

Du kannst auch einen High-Performance-Cluster durch einen SC/MP 
ersetzen, wenn du extern genug RAM dran hängst.

von Strubi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Moin,

>
> Nach vielen Versuchen mit den sog. SSE Extensions der neuesten Intel und
> Xeon Prozessoren, glaub ich es geht damit nicht. Die Flags werden nicht
> richtig gesetzt oder gar nicht..
> Kann man so was mit FPGA realisieren? evtl mehreren?

Schon. Die Frage stellt sich nach dem Durchsatz, und wo die Daten 
herkommen, wo sie hinsollen...

> Gibt es einen default Befehlssatz?

Den musst du selber definieren. Das FPGA ist ja von Haus aus wie 
"neugeboren" (ich hüte mich, zu sagen "dumm").

> Ich weiss auch nicht ob und wie ich z.b. dieses Gerät "easyFpga" s.u. an
> ein normalen PC anbinde und ins ddr3 ram schreibe und ob es Assembler
> gibt, die ja den Mikrocode erzeugen sollen.

Ich sehe da kein DDR-RAM. Da müsstest Du eher zum ähnlichen Papilio Pro 
greifen. Die Cores, die da per Hochsprache instanziert werden, lösen 
dein Problem sicher nicht.
Prinzipiell ist schon der LX9 ist etwas schwach für solche Bitbreiten: 
Die RAM-Primitiven sind gerade mal 18 Bit breit und über das Die 
verteilt. Da ergibt sich schon der erste Flaschenhals, wenn die Sache 
auf Geschwindigkeit optimiert werden soll und gleichzeitig Daten rein 
und raus müssen.
Genannter PCIe-Ansatz ist sicher flott, aber aufwendiger als eine 
klassische USB-FIFO-Lösung...

> Und wie realisiert man Ein und Ausgabe Routinen der Hex Zahlen?
> Also an sich suche ich einen schnellen RisC Prozessor mit hoher interner
> Registerbreite.
> Wer sich für mathe interessiert dem kann ich gern erzählen worauf ich
> hinaus will:)

Ich nehme mal an, dass es um Zahlentheorie geht...
Punkten kannst du mit dem FPGA gegenüber einer 2 GHz-CPU nur dort, wo du 
eine ALU-Pipeline bauen kannst, die eine aufwendige Operation per 
Taktzyklus durchspult oder Parallelisierung erlaubt.
Also was z.B. gut geht sind Matrizenmultiplikationen und entsprechende 
Transformationen (DCT, FFT, Wavelet...)

Ansonsten versuchen sich da immer alle Jahre wieder mal Leute daran, das 
Rad in 64 oder 128 bit neu zu erfinden, aber schlussendlich bleibt doch 
alles beim Alten: Du bist auf dich selbst gestellt, um deine 
Spezialanwendung effektiv zu erschlagen. So richtig generisch gibts kaum 
was, da fällt mir höchstens noch der HiCoVec ein (pfiffiges Konzept, 
aber nur 32 bit).
Ansonsten gibt es da ein paar HLS-Ansätze, aber das Fass will ich grade 
nicht aufmachen..

Aber zum Stichwort Mikrocode: das kannst du durchaus ohne Assembler 
sogar in VHDL direkt runterschreiben. Der Ansatz ist natürlich sehr 
mächtig, aber du musst deine parallelisierenden SIMD-Befehle 
entsprechend designen. Dafür kannst du relativ wilde Sachen machen, wie 
zur Laufzeit aus einer Host-CPU das Programm ändern.

Gruss,

- Strubi

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Ich hatte mir sowas ähnliches schon mal für Java BigDecimal Zahlen 
überlegt, aber das scheitert wohl am IO, was zu langsam ist.

Einfache Operationen mit grossen Zahlen findest Du z.B. in Cryptocoin 
Minern. Da gibt es ja inzwischen auch Opensource Code, in den Du mal 
schauen könntest. Musst aber hält eher den kompletten Algorithmus im 
fpga laufen haben, um IO zu minimieren.

von --- (Gast)


Bewertung
0 lesenswert
nicht lesenswert
> Du kannst auch einen High-Performance-Cluster durch einen SC/MP
> ersetzen, wenn du extern genug RAM dran hängst.

Du darfst gerne mal eine Genomanalyse auf einem SC/MP
mit 1 TB RAM implementieren.

Bis der fertig ist, wirst du dich mindestens 3x im Grab umdrehen.

von (prx) A. K. (prx)


Bewertung
2 lesenswert
nicht lesenswert
--- schrieb:
> Bis der fertig ist, wirst du dich mindestens 3x im Grab umdrehen.

Sagte ich doch: Alles eine Frage der Zeit. ;-)

von Weltbester FPGA-Pongo (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Habe gerade mal was probiert:

Eine einfache Multiplikation in einem Artix 7 mit 128 Bit läuft mit 
gerade mal noch 43MHz. Wer's braucht.

von (prx) A. K. (prx)


Bewertung
1 lesenswert
nicht lesenswert
Weltbester FPGA-Pongo schrieb im Beitrag #4818635:
> Eine einfache Multiplikation in einem Artix 7 mit 128 Bit läuft mit
> gerade mal noch 43MHz. Wer's braucht.

Wer es ernst meint, der macht es anders als du vermutlich getan hast. 
Aktuelle CPUs versuchen nicht erst, das in einem Takt zu erledigen. 
Sondern brauchen schon bei 64bit um die 4 Takte bis zum Ergebnis, dafür 
aber gepipelined.

von Peter II (Gast)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Ich suche eine Möglichkeit, mit sehr großen Zahlen ca 2 ^128 einfache
> Rechnungen durchzuführen.

kannst du etwas mehr über die Berechnung sagen? Wenn du die Aufgabe 
vollständig erklären kannst, finden sich eventuell Leute die es als 
Herausforderung sehen.

von Operator S. (smkr)


Bewertung
0 lesenswert
nicht lesenswert
Ich hatte jetzt spontan an GPGPU gedacht, die dafür nötige 
Speicherbandbreite wäre ja gegeben.

In OpenCL sind sogar 128 Bit variabeln in Planung. Die wirst du aber 
jetzt noch selbst implementieren müssen, sofern dies möglich ist.
https://de.wikipedia.org/wiki/OpenCL
> Folgende Datentypen wurden zudem für spätere Versionen von OpenCL
> reserviert:
> long long, long longn: Vorzeichenbehaftete 128-Bit-Ganzzahlen und
> -vektoren.
> unsigned long long, unsigned long longn: Vorzeichenlose 128-Bit
> Ganzzahlen und -vektoren.


Bei der Konkurrenz von Nvidia sieht das schon schlechter aus: 
https://de.wikipedia.org/wiki/CUDA
> ... daher kennen GPUs eher exotische Datentypen wie 9 Bit oder 12 Bit mit
> Festkommastelle, verzichten hingegen aber häufig auf die für
> Allzweck-CPUs und NPUs üblichen Registerbreiten von 32, 48, 64 oder 80
> Bit (usw.). Somit sind Berechnungen, beispielsweise mit den Genauigkeiten
> nach IEEE 754 (64 Bit für double precision), häufig nicht im Befehlssatz
> der GPU vorgesehen und müssen relativ aufwendig per Software emuliert
> werden.

Dies ist jedoch sehr generisch geschrieben. Ob dies nun alle GPU 
Lösungen betrifft, oder lediglich auf CUDA bezug nimmt, ist mir nicht 
ganz klar.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Peter II schrieb:
> matthias schrieb:
>> Ich suche eine Möglichkeit, mit sehr großen Zahlen ca 2 ^128 einfache
>> Rechnungen durchzuführen.
>
> kannst du etwas mehr über die Berechnung sagen? Wenn du die Aufgabe
> vollständig erklären kannst, finden sich eventuell Leute die es als
> Herausforderung sehen.


also es geht um die sogenannte Collatz Folge:

1 ) nimm irgendeine Zahl n
2 ) wenn ungerade multipliziere sie mit 3 und addiere 1.
3 ) wenn gerade halbiere sie.

Schleife 2-3-2-3-3-3-2-3...  bis 1 rauskommt oder eine andere schleife 
oder n gegen unendlich geht.

Die sog. Collatz Vermutung lautet nun:
Für alle startenden n endet die Kette IMMER mit 1, bzw 4,2,1,4,2,1..

siehe z.B.:

5,16,8,4,2,1
11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

27,82..........9232,..........1.


Bei gewissen Startwerten wie hier 27 laufen die Ketten sehr hoch.
Diese "Hochwerte" nennt man pathrecords.

Der  pathrecord von 8528817511 ist 18,144594,937356,598024 was die 
höchste in 64 bit darstellbare unsigned integer ist.

Und da scheitern z.b. Vpaddq xmm1,xmm2,xmm3 oder vpmuludq xmm1,xmm2,xmm3 
bzw. machen was anderes als erwünscht und setzen keine Flags.
Der Intel Prozessor muss über sse2 verfügen. besser sse4 wie manche 
Xeon.
Trotzdem failed ein shift left logical einer xmm128 Zahl an der 64 bit 
Grenze.

z.B. 6,345,568,321,109,753,349 shl 1 geht noch.
= 12,691,136,642,219,506,698  aber + 6,345,568,321,109,753,349 müsste 
19,036,704,963,329,260,047 ergeben, was mehr als 2^64 ist.
Tuts aber nicht.
Was aus der doku auch klar wird.
z.B.
http://www.felixcloutier.com/x86/PADDQ.html

Ausserdem ist der AVR-gcc assembler ziemlich ungeeignet für etwa

mov edi, [ebp+16]  oder umgekehrt.
oder
mov rax, qword ptr [rbp+rdx*4]

Wenn ich wüsste, wie man masm code in gcc einbindet, wäre ich schon 
weiter.

Bei Interesse kann ich den ganzen gcc mit eingebundenem asm () posten. 
bis Startzahl 8528,817511.
siehe
http://www.ericr.nl/wondrous/pathrecs.html

Und der neueste Xeon kann sogar angeblich ymm register bis 2^256, das 
wäre sehr interessant, wenn ich wüsste wie man es richtig einsetzt!
M

von Mw E. (Firma: fritzler-avr.de) (fritzler)


Bewertung
1 lesenswert
nicht lesenswert
Also die Collatz Folge ließe sich als Statemachine in einen FPGA 
einbauen. Da brauchts dann keine CPU mehr.
Ist nur die Frage ob das nur den Rekord ausgeben soll oder auch alle 
Zwischenwerte?

von Karl (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Wenn ich das Recht verstehe ist dein Problem nicht die Performance 
sondern überhaupt korrekte Ergebnisse zu erhalten?

Klingt ehrlich gesagt nach einem Fall für gmp. Falls das nicht schnell 
genug ist kann man immer noch weiter schauen. Das rechnen an einer Zahl 
scheint ja nicht sonderlich parallelisierbar zu sein, aber immerhin 
durch bitshift und Addition darstellbar.

Eine gpu könnte  viele viele folgen parallel berechnen. Ein fpga ist 
denke ich im bezahlbaren Rahmen weder aus Performance sicht noch aus 
Aufwandssicht die beste Lösung.

Natürlich lässt sich das auch in einem fpga umsetzen aber wozu, wenn ein 
"dreizeiler" auf dem PC das gleiche macht.

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Ok, Statemachine in ein FPGA ist wohl die naheliegendste Option.

Aber: was bringt das? Nimmt man ein 128 Bit Input Register und schaltet 
einen Counter vor, der alle Zahlen bis 128 Bit hochzählt und abbricht, 
wenn entweder die Statemachine bei 4 (oder 1) ankommt. Dann wird das 
Eingaberegister um 1 erhöht, Statemachine-Reset und der Test startet für 
die neue Zahl.
Im anderen Fall würde es wohl einen Overflow geben, oder kann die 
Statemachine in eine Endlosschleife geraten?

Aber sogar wenn das Ergebnis wäre, dass alle 128 Bit Zahlen irgendwann 
bei 1 ankommen, dann wäre ja noch nichts über 129 Bit Zahlen ausgesagt?

Also die Vermutung wäre weder bewiesen noch widerlegt?

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Die höchste berechnete Startzahl ist momentan 1,980976,057694,848447 
also unter 64 bit.
Der zugehörige pathrecord p(#88) ist 
64,024667,322193,133530,165877,294264,738020 also unter 2^126.

2^128 ist ca.  340,282366,920938,463463,374607,431770,000000.

Die nächste zu berechnende  Startzahl, die einen höheren  pathrecord als 
p(#88) liefert ist unbekannt.
Dieser könnte auch über 2^128 liegen.
Dazu bräuchte ich eine schnelle 2^128 Berechnung.
Bei overflow über 128 Bit müsste man sich was überlegen.

Schön wäre auch, wenn man auf Wunsch die korrekten präzisen 
Zwischenwerte der Collatz folge zur späteren Abfrage zwischenspeichern 
könnte.
Zum schnellrechnen diese Option halt abschalten.
Oder man lässt optional abbrechen nach n Schritten, oder bei overflow.

Ein 256 Bit-Rechner wäre genial, der nur shr, shl, add und inc $1,reg256 
kann, also eine echte 256 Bit Risc Maschine.
Nicht nur für dieses spezielle Problem.

Thx


M.

von daybyter (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Die paar Befehle erschlägst Du wohl eben besser mit paar Zeilen Verilog 
und lässt den Rest der CPU weg.

von Karl (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Sag mal, liest du die Antworten?
Hast du die gmp Bibliothek ausprobiert?
Wo liegt konkret dein Problem? Ist eine pc basierte Lösung zu langsam 
oder schaffst du nicht dass sie korrekt rechnet?

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
In der momentanen Implementation in 64 Bit avr-gcc Assembler dauern 
Startwerte von z.B.
start=23035,537407 record==68,838156,641548,227040 ca. 2 Minuten.
der letzte bekannte P(#88) mit
k = 1,980976,057694,848447 und (bekannte) P(k) = 
64,024667,322193,133530,165877,294264,738020 läuft seit einigen Wochen.

Ich glaube nicht, dass eine Implementierung mit der gmp library 
schneller sein kann als reine Assembler codierung, habs noch nicht 
probiert.
Das verilog DHL erscheint mir vielversprechend..
Ich habe aber noch zu wenig Ahnung ehrlich gar keine ;) von VDHL und wie 
man da überhaupt rangeht..
Wie ich schon sagte: ich strebe einen 256 Bit-Risc-Rechner an, also eine 
echte 256 Bit Risc Maschine.
Nicht nur für dieses spezielle Problem.
Von GPU und CUDA wurde mir abgeraten wg abweichender Registerbreiten 
etc.

486 Assembler behersche ich recht gut.
Auf welchen Prozessoren läuft denn VDHL? sorry microcode ist alles 
Neuland für mich, aber reizt mich zu lernen
M

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Es gibt Verilog und VHDL. 2 konkurrierende Sprachen.

Sie laufen u.a. auf CPLDs, FPGAs und ggf kann man sie sogar in ein Asic 
giessen. Hängt von Deinem Budget und Deinen Anforderungen ab.

https://www.mikrocontroller.net/articles/Verilog

Du kannst auch mit freien Tools wie Altera Quartus oder Xilinx ISE 
anfangen und alles komplett im Simulator machen. Günstige FPGAs bekommst 
schon für unter 15,- .

von Karl (Gast)


Bewertung
1 lesenswert
nicht lesenswert
matthias schrieb:
> In der momentanen Implementation in 64 Bit avr-gcc

Ist das ein Tippfehler? Avr?

Die gmp lib ist für die Performance kritischen Sachen in Assembler. Viel 
schneller wird es nicht.

Das Problem mit dem fpga ist, dass er keinen deut schneller rechnet als 
ein moderner Prozessor, solange du keinen Weg findest die Berechnungen 
zu parallelisieren. Wenn du dazu einen Ansatz hast: Go for it. Falls 
nicht kannst dir das sparen. Außer du willst was zum Spaß lernen.

von Operator S. (smkr)


Bewertung
-1 lesenswert
nicht lesenswert
matthias schrieb:
> Wie ich schon sagte: ich strebe einen 256 Bit-Risc-Rechner an, also eine
> echte 256 Bit Risc Maschine.

Ich dachte es sollte 128 Bit sein?

Wie dem auch sei, ich verstehe nicht warum du auf unterstem Level in 
Assembler rumdödeln möchstest, wenn dir geeignete Tools zur Verfügung 
stehen.

matthias schrieb:
> 486 Assembler behersche ich recht gut.

Um damit was zu machen? Auf einem 8 Kern, 16 Thread Prozessor parallel 
deinen Algorithmus laufen zu lassen, weil dir alles andere zu lange 
dauert?

Mit Python hättest du dies vermutlich schneller geschrieben und 
ausgerechnet, als dir ein Konstrukt überlegt um von 64Bit Registern auf 
128 (oder doch 256?) Bit in Assembler zu kommen.
GMP gibts auch für Python, die Zeit zum Ausrechnen ist nicht viel 
länger: https://jasonstitt.com/c-extension-n-choose-k

von Peter II (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Operator S. schrieb:
> Wie dem auch sei, ich verstehe nicht warum du auf unterstem Level in
> Assembler rumdödeln möchstest, wenn dir geeignete Tools zur Verfügung
> stehen.

ich denke schon das der Ansatz mit ASM richtig ist. Er hat ein korrektes 
Problem was er optimieren will. Die Berechnung ist so überschaubar das 
man es auch noch in ASM mache kann.

Wenn es nicht gerade eine fertige Bibliothek für genau diesen Problem 
gibt hilft das alles nicht weiter. Klar kann man mit jeder Sprache mit 
128bit rechnen - die Frage ist nur wie schnell.

Wenn ich es richtig verstehe, kann man das auch nicht wirklich 
Parallelisieren damit dürften auch Grafikkarten zu langsam für das 
Problem sein.

Ich würde auch versuchen, mit geschickter ASM programmieren das Problem 
auf einem PC zu lösen.

von Strubi (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Moin,

würde mich auch Vorpostern anschliessend und mal die Aussage treffen, 
dass die libgmp dem FPGA vorzuziehen wäre.
Der Rechenschritt ist sonst ansich einfach und dürfte auf einem FPGA 
direkt ohne Schmerzen als 1-cycle-pipeline bei min 150MHz z.B. auf einem 
Spartan6 ticken. Nur scheint die Folge nicht gerade per "divide et 
impera" zu beschleunigen, also müsstest du parallel mehrere Folgen in 
separaten Recheneinheiten durchnudeln. Da stellt sich dann die Frage, ob 
du die Startwerte und Iterationswerte im Vergleich zu einer schnellen 
CPU mit riesigem Speicher schnell genug rein bzw. rausbekommst. Dann 
kommt dazu, dass die parallelen Pipelines alle zu unterschiedlichen 
Zeiten fertig sind, wenn ich die Sache richtig kapiert habe. Das schreit 
nach Multithreading.. Und am Schluss willst Du noch alles in einer 
Datenbank... Freude herrscht, da kann man schon eine Diplo..ach nee, 
heute heisst das ja Bachelor.
Aber spannend wäre die Übung schon.

matthias schrieb:
> Auf welchen Prozessoren läuft denn VDHL? sorry microcode ist alles
> Neuland für mich, aber reizt mich zu lernen

Da müssen wir die Begriffe nochmal klären:
- VHDL: Die Sprache, in der du deinen "Prozessor" definierst/designst.
- Microcode: typischerweise für den User nicht sichtbare SIMD-Applets, 
die z.B. Berechnungen einer Pipeline-Stufen-Folge kontrollieren
- VHDL-Simulator: läuft auf nahezu jeder Plattform
- VHDL-Synthese: x86(-64) Linux/Windows only

Der Microcode-Ansatz macht nur Sinn, wenn du eine flexible Pipeline 
designen musst, die mehrere Arten von Rechnungen durchführt. Bestes 
Beispiel sind die nvidia shader units, die parallel Skalarprodukte, usw. 
rechnen. Intel nutzt ausgiebig Microcode-Tricks, um kompatibel zu sich 
selbst zu bleiben (d.h. den uralt-i86-opcodes) und trotzdem eine 
effiziente Architektur hinzukriegen...

Mal ne andere Frage: Wofür ist die Collatz-Folge gut? Kann man damit 
Primzahlen finden?

- Strubi

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
Hallo Matthias,

FPGAs sind Logikbausteine, d.h. da hat man zB UND- und ODER-Gatter mit 
denen man Digitalschaltungen bauen kann, z.B. eine CPU. Da ist aber 
keine CPU auf der das läuft, sondern die muss man sich halt (falls 
nötig) selber schreiben. Man muss da aber nicht mit den einzelnen 
Gattern hantieren, sondern kann da in einer Hochsprache (VHDL oder 
Verilog) zB eine Addition hinschreiben und der Compiler macht dann die 
konkrete Hardwarebeschreibung daraus. Meistens hat man im FPGA aber 
keine CPU.

Wie hier schon mehrfach erwähnt wurde sind FPGAs was den Takt angeht den 
modernen PC-CPUs deutlich unterlegen. Der Vorteil von FPGAs ist ihre 
Parallelität. Dazu fallen mir spontan zwei Lösungen ein:
1) Du rechnest einfach die Folgen für viele verschiedene Startwerte (zB 
100 oder 1000) parallel. Dann sind zwar die einzelnen Folgen langsamer 
als auf dem PC, aber Du kannst viel mehr Startwerte in der gleichen Zeit 
untersuchen.
2) Du rechnest mehrere potentielle Pfade parallel. Angenommen die 
aktuelle Zahl n sei gerade, dann rechnest Du parallel  a) n/2, b) 
(3(n/2)+1) und c) n/4. Danach entscheidest Du anhand des Ergebnisses von 
a), ob b) oder c) der richtige Weg ist. Du musst für die Berechnung von 
b) und c) nicht auf das Ergebnis von a) warten. Das lässt sich dann auch 
beliebig kaskadieren.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
>> Auf welchen Prozessoren läuft denn VDHL? sorry Microsoft ist alles
>> Neuland für mich, aber reizt mich zu lernen

> Da müssen wir die Begriffe nochmal klären:
> - VHDL: Die Sprache, in der du deinen "Prozessor" definierst/designst.
> - Mikrocode: typischerweise für den User nicht sichtbare SIMD-Applets,
> die z.B. Berechnungen einer Pipeline-Stufen-Folge kontrollieren
> - VHDL-Simulator: läuft auf nahezu jeder Plattform
> - VHDL-Synthese: x86(-64) Linux/Windows only
>
> Der Microcode-Ansatz macht nur Sinn, wenn du eine flexible Pipeline
> designen musst, die mehrere Arten von Rechnungen durchführt. Bestes
> Beispiel sind die nvidia shader units, die parallel Skalarprodukte, usw.
> rechnen. Intel nutzt ausgiebig Microcode-Tricks, um kompatibel zu sich
> selbst zu bleiben (d.h. den uralt-i86-opcodes) und trotzdem eine
> effiziente Architektur hinzukriegen...

> Mal ne andere Frage: Wofür ist die Collatz-Folge gut? Kann man damit
> Primzahlen finden?

Anm..: Der inline Assembler in gcc heißt tatsächlich AVR-gcc AFAIK.

Zur letzteren Frage:
Es gibt die mehr oder weniger bekannte Collatz Vermutung von 1920.
Eben dass alle Folgen startend mit n > 0 gefolgt von den Schritten 
n->3n+1 bei n Odd, n->n/2 be n Even alle irgendwann bei 1 enden.

Es wurde noch kein Gegenbeispiel gefunden.

Ob das für wirklich alle N gilt und Warum das so ist ist unbewiesen.

So entstehen Folgen der Art, wie ich sie im Beitrag vom 10.12. 16:13 
(warum haben die keine Nummern) andeutete, wie lange die werden wissen 
wir vorher nicht.
Nach Collatz endlich lang.
Die, die mit P(#5) = 27 anfängt und mit 1 endet ist ca. 70 Schritte 
lang, und hat als höchsten Zwischenwert M(#5) 9232 das nennt man den 
pathrecord von 27.
Mehr unter Wikipedia.de. Collatz-Vermutung

Die nächsten höheren Startwerte die höhere pathreords erzeugen sind 
255,447,639,...

Der höchste bis heute bekannte Startwert der einen höchstmöglichen 
pathrecord erzeugt ist p(#88) = 1,980976,057694,848447 und
endet nachgerechnet mit 1, bei einem pathrecord von M(#88) = 64 024667 
322193 133530 165877 294264 738020.
Nach erreichen dieses Wertes geht er runter auf 1. Das ist ja gerade die 
C Vermutung.
Vermutlich hörten Oliviera und Silva da auf weiter zu rechnen, eben weil 
die 2^128 Bit Grenze erreicht wird.
Schlicht und ergreifend suche/n ich (wir) die nächste höhere 
Collatz-Startzahl. P(#89) und den pathrecord M(#89)

siehe auch  http://www.ericr.nl/wondrous/pathrecs.html

Also starte bei der nächsten ungeraden n = 1,980976,057694,848449, bilde 
die Collatz-Folge bis 1 und schaue nach,
ob irgendwo mittendrin ein höherer Wert als  64 024667 322193 133530 
165877 294264 738020 auftaucht.

Dafür bietet sich natürlich multithreading an, also starte nicht 
nacheinander mit einer Zahl z.B. 1,980976,057694,848449 sondern gleich 
mit
sagen wir 12 aueinanderfolgenden ungeraden der Art von Rest 3 modulo 4, 
z.B.
60979,60983,60987,60991,60995,60999,61003,61007,61011,61015,61019,61023
und wenn eine fertig nimm die nächste 61027

Und die shift und add Befehle möchte ich auf einer schnellen Hardware 
mit einer "intelligenten" multithreading fähigen Sprache schreiben.

Welche Hardware brauche ich präzise?
Welche Software brauche ich präzise?

VDHL Simulator hört sich gut an.
Ist das eine Hard- oder Software?
Ich habe ein funktionierendes w7/64 System zu Hause, was brauche ich? 
Eine PCI Karte mit Prozessor oder ALU? Ein FPGA Programmiergerät?
Ich bräuchte mal ein Starter Kit oder so was ;)

Sorry ich hab echt keine Ahnung was worauf läuft und was ich alles 
brauche. Wie baue ich das zusammen? und programmiere es.
Mit einer geeigneten HW also eine Art 128 oder 256 Bit RISC prozessor 
könnte ich mir noch ganz andere wunderbare Dinge vorstellen,
wie parallelisierte Prime factorization.
Thx
M.

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> So entstehen Folgen der Art, wie ich sie im Beitrag vom 10.12. 16:13
> (warum haben die keine Nummern) andeutete

Die haben Nummern. Die Überschrift des Beitrages ist ein Link auf den 
Beitrag. Das da ist der Link zu Deinem Beitrag 
Beitrag "Re: 128 Bit Risc"

> Welche Hardware brauche ich präzise?
Etwas vereinfacht: Das größte FPGA-Board, das Du Dir leisten 
kannst/willst. Ab einer bestimmten Größe kostet allerdings die Software 
dazu auch noch Geld.

> Welche Software brauche ich präzise?
Die Hersteller haben IDEs für ihre FPGAs, bei Xilinx zB heißt die zZt 
Vivado. Bei den kleineren FPGAs ist die kostenlos, bei den größeren 
Modellen wollen sie Geld dafür.

> VDHL Simulator hört sich gut an.
> Ist das eine Hard- oder Software?

Eine Software.
Man baut im FPGA ja eine Digitalschaltung zusammen und da das ja kein 
Programm ist, in das man einfach reindebuggen kann simuliert man das 
vorher am PC.

Du könntest also durchaus das ganze erst mal NUR am PC simulieren und 
erst wenn Du weißt wie viele Ressourcen Du brauchst Dich für einen 
konkreten FPGA entscheiden.

> Ich habe ein funktionierendes w7/64 System zu Hause, was brauche ich?
> Eine PCI Karte mit Prozessor oder ALU? Ein FPGA Programmiergerät?
> Ich bräuchte mal ein Starter Kit oder so was ;)
FPGAs die auf einer PCIe-Karte sitzen sind eher teuer.
 Bei vielen Demo-Boards sind bereits Programmieradapter drauf, da reicht 
dann ein USB-Kabel.

> Sorry ich hab echt keine Ahnung was worauf läuft und was ich alles
> brauche. Wie baue ich das zusammen? und programmiere es.

Vielleicht solltest Du Dich einfach mal in VHDL einarbeiten, damit Du 
ein Gefühl dafür bekommst.

von Lattice User (Gast)


Bewertung
1 lesenswert
nicht lesenswert
matthias schrieb:
> Vermutlich hörten Oliviera und Silva da auf weiter zu rechnen, eben weil
> die 2^128 Bit Grenze erreicht wird.

Glaube ich nicht. Eher haben sie noch nichts gefunden.

> Schlicht und ergreifend suche/n ich (wir) die nächste höhere
> Collatz-Startzahl. P(#89) und den pathrecord M(#89)
>
> siehe auch  http://www.ericr.nl/wondrous/pathrecs.html
>
> Also starte bei der nächsten ungeraden n = 1,980976,057694,848449, bilde
> die Collatz-Folge bis 1 und schaue nach,
> ob irgendwo mittendrin ein höherer Wert als  64 024667 322193 133530
> 165877 294264 738020 auftaucht.
>

Das ist im Prinzip brute force. Hast du dir schon mal gedanken gemacht 
wie gross diese Zahlen sind und wieviel du testen musst?

Schreib mal ein Programm was von 2^63 bis auf 2^64-1 hochzählt und sonst 
nichts macht, und messe wie lange dein bester Rechner braucht.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich hab erst mal das Programm vivado von xilinx installiert und hoffe da 
ein paar einfache Aplikationen zu schreiben, zu finden und oder 
auszuprobieren.
Eine 8 bit addier maschine wäre schon was;)
Ich glaube fast, dass das was ich also will einen 128 Bit risc rechner 
auf FPGA Basis gibt es schon...

Hier ist übrigens das bestehende collatz-folgen-programm in gcc und dem 
eingebauten assembler.

Das ist sicher verbeseerungswürdig, wenn man an das pipelining beim xeon 
denkt, kann man sicher die vielen zeitfressenden  conditional jumps 
irgendwie "intelligent" übergehen, da ja so wie ich das verstand die 
Befehle vor-abgearbeitet werden, die mit oder ohne carry als nächstes 
dran sind.
Wer Lust hat mag etwas daran herumverbessern
Bei Startwerten um 10^12 dauert es etwa 70 Minuten, bis die 1 ereicht 
wird.
Wir arbeiten mit den 64 bit Registern r9,r13, bzw r10,r14

Danke

#include <stdio.h>

unsigned __int128 start;
unsigned __int128 start_base;
unsigned __int128 record;
unsigned __int128 merkrecord;
int roosendaal_number;
unsigned long starttime;

#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

unsigned int reste_loop = 0;

void printf_128(__int128 path) {
// Ausgabe int128 im Dezimalformat
// jeweils 6 Ziffern durch Kommata getrennt
int ziffer[42];
int cnt = 0;
int loops;

while (path > 0)
        {
        ziffer[cnt]=path%10;
        path=path/10;
        cnt++;
        }

for (loops = cnt-1; loops >= 0; loops--)
        {
        printf("%i",ziffer[loops]);
        if ( (loops%6==0) && (loops > 0) )
                printf(",");
        }
}

void printf_time() {
long nowtime = time(NULL)-starttime;
int now_min = nowtime/60;
int now_sec = nowtime%60;
if (now_min<1) printf("%is",now_sec);
        else printf("%i:%02is",now_min,now_sec);
}

// und hier beginnt das hauptprogramm :)
int main () {

printf("\nCollatz meets assembler - Version 1.0 by gonz\n");

starttime = (unsigned)time(NULL);
start_base = 0;
// da wir (3x+1)/2 schritte durchführen, sind die records halb so gross 
wie die bei Roosendaal gelisteten
record = 8;
roosendaal_number = 2;

while (1) {

// wir betrachten nur spezielle reste
start=start_base+reste[reste_loop];
reste_loop++;
if (reste_loop>=reste_amount) { 
reste_loop=0;start_base=start_base+base_step; }

// und los gehts :)
merkrecord = record;

asm(

// Vorab die Registerbelegung in der Assembler Routine:
// r8 : startwert (bleibt erhalten fuer stopp pruefung)
// r9,r13 : aktueller Folgewert (niederwertig...hoeherwertig)
// r10,r14 : dessen haelfte fuer (3x+1)/2 schritt
// r11,r15 : record (wird mitgefuehrt, ursprungs-record wert geht 
verloren)

// Startwert und bisherigen Record aus RAM in Register kopieren
  "MOV start(%rip),%r8 \n\t"
  "MOV %r8,%r9 \n\t"
  "MOV record(%rip),%r11 \n\t"
  "MOV $0,%r13 \n\t"
  "MOV record+8(%rip),%r15 \n\t"

// Register fuer aktuellen Wert auf Startwert setzen

// und hier beginnt die Rundreise
  "collatz_start: \n\t"
  "TEST $1,%r9 \n\t"
  "JZ gerade \n\t"
  "MOV %r13,%r14 \n\t"
  "MOV %r9,%r10 \n\t"

// hier: ungerade. fuehre den (3x+1)/2 Schritt durch.
  "SHR $1,%r14 \n\t"   // hoeherwertig - und ins carry
  "RCR $1,%r10 \n\t"   // niederwertiges uebernimmt carry

// beim addieren kann hier die 64bit Grenze erreicht werden.
  "STC \n\t"
  "ADC %r10,%r9 \n\t"  // niederwertig - und ins carry
  "ADC %r14,%r13 \n\t" // hoeherwert uebernimmt carry

// nach einem (3x+1)/2 Schritt koennte ein neuer Pass Record erreicht 
sein
  "CMP %r13,%r15 \n\t"
  "JA collatz_start \n\t"
  "JB do_record \n\t"
  "CMP %r9,%r11 \n\t"
  "JA collatz_start \n\t"

// wenn ja diesen aufs passende Register uebertragen
  "do_record: \n\t"
  "MOV %r9,%r11 \n\t"
  "MOV %r13,%r15 \n\t"
  "JMP collatz_start \n\t"

// hier: gerade. fuehre den x/2 Schritt durch
  "gerade: \n\t"
  "SHR $1,%r13 \n\t"
  "RCR $1,%r9 \n\t"

// so und damit... schauen, ob Stoppwert erreicht. Wenn nicht: naechste 
runde :)
  "CMP $0,%r13 \n\t"
  "JNZ collatz_start \n\t"
  "CMP %r8,%r9 \n\t"
  "JA collatz_start \n\t"

// habe fertig: Register wieder ins RAM kopieren.
  "fertig: \n\t"
  "MOV %r11, record(%rip) \n\t"
  "MOV %r15, record+8(%rip) \n\t"
);

if (record>merkrecord) {
printf_time();
roosendaal_number++;
printf(" #%i start=",roosendaal_number);
printf_128(start);
printf(" record==");
printf_128(record*2);
printf("\n");
}
}
}

von (prx) A. K. (prx)


Bewertung
1 lesenswert
nicht lesenswert
Da ist noch gut Luft nach oben. Die datenabhängigen gerade/ungerade 
Zweige führen zu erbärmlicher Sprungvorhersage. Statt dessen solltest du 
beide Varianten ineinander verzahnt berechnen und anschliessend per CMOV 
das Resultat abholen. Deine CPU kann 4 Befehle pro Takt ausführen, das 
macht die also nebenher. Aber ein falsch vorhergesagter Sprung frisst 
2stellige Takte.

von (prx) A. K. (prx)


Bewertung
1 lesenswert
nicht lesenswert
Ist viel Lesestoff, aber bei einer solchem Aufgabe lohnt sich das:
http://www.agner.org/optimize/
http://www.intel.de/content/www/de/de/architecture-and-technology/64-ia-32-architectures-optimization-manual.html

Es reicht heute nicht mehr, die Funktion der Befehle zu verstehen. Man 
muss auch verstehen, wie sie in der CPU zusammenwirken. Hier hilft Agner 
ganz erheblich.

: Bearbeitet durch User
von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Ich wäre übrigens nicht erstaunt, wenn so ein Code, mit CMOV optimiert, 
auf AMD CPUs viel schneller rennt als auf Intel. Intel tut sich mit 
ADC/RCR erheblich schwerer als AMD (z.B. stc/adc/adc 3 Takte, statt 5 
bei Haswell).

: Bearbeitet durch User
von Andreas R. (daybyter)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Damit es nicht gar so abstrakt bleibt, hab ich mal schnell was mit 
verilog zusammengetippt. Es compiliert in einer älteren Quartus Version 
und braucht so 569 Logikelemente. Allerdings komplett unoptimiert, 
ungetestet und überhaupt. Es fehlt auch die Speicherung des max Wertes, 
der Sequenz usw.

Hab als Ziel so ein cyclone 2 minimum dev board genommen, wie man es für 
unter 15,- bei ebay bekommt.

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Noch was, wenn man sich in Sachen CPU Design weiterbilden möchte:

http://j-core.org

Die Videos find ich recht interessant.

von U.G. L. (dlchnr)


Angehängte Dateien:

Bewertung
1 lesenswert
nicht lesenswert
matthias schrieb:
> In der momentanen Implementation in 64 Bit avr-gcc Assembler dauern
> Startwerte von z.B.
> start=23035,537407 record==68,838156,641548,227040 ca. 2 Minuten.

Also ich hab' das mal mit GMP implementiert.
Da das Programm mit dem "start"-Wert den "record" reproduziert, meine 
ich, den Algorithmus korrekt implementiert zu haben.
1
D:\_PRJ\src>collatz
2
3
n=23035537407
4
r=68838156641548227040
5
c=196
6
D:\_PRJ\src>

Auf einer popeligen logischen CPU eines i5 M540 dauert das unter 
Verwendung von 256bit-Werten - ääähhhmmmmmm - so ungefähr 0,nix Sekunden 
(bei gerade einmal 196 "Auf und Ab's" eigentlich auch kein Wunder)!!!

????????????? Irgendwas hab' ich da wohl missverstabden ?????????????

1
// g++ -Ofast collatz.cpp -o collatz -I ..\gmp\include\ -L ..\gmp\lib\ -lgmp 
2
3
#include <stdio.h>
4
#include "..\gmp\include\gmp.h"
5
6
void collatz(mpz_t n, mpz_t r) {                              //[
7
mpz_t C, c, R, x;
8
unsigned int u;
9
int i;
10
  
11
  mpz_init2(C, 256);
12
  mpz_init2(c, 256);
13
  mpz_init2(R, 256);
14
  mpz_init2(x, 256);
15
  mpz_set(R, n);
16
  mpz_set(x, n);
17
  
18
  do {
19
    mpz_mul_ui(x, x, 3);
20
    mpz_add_ui(x, x, 1);
21
    mpz_add_ui(c, c, 1);
22
    if ((i = mpz_cmp(x, R)) >= 0) {
23
      if (i == 0) {
24
        break;                         
25
      }
26
      mpz_set(R, x);
27
      mpz_set(C, c);
28
    }
29
    u = mpz_scan1(x, 0);
30
    mpz_tdiv_q_2exp (x, x, u);
31
    mpz_add_ui(c, c, u);
32
  } while ((i = mpz_cmp(x, n)) > 0);
33
  if (i == 0) {
34
    printf("\n!!!loop found!!!");
35
  }
36
  
37
  mpz_set(n, C);
38
  mpz_set(r, R);
39
}//]
40
41
int main(int argc, char **argv) {                             //[
42
static mpz_t n, r;
43
44
  mpz_init2(n, 256);
45
  mpz_init2(r, 256);
46
  mpz_set_str(n, "23035537407", 0);
47
  gmp_printf("\nn=%Zd", n);
48
  collatz(n, r);
49
  gmp_printf("\nr=%Zd", r);
50
  gmp_printf("\nc=%Zd", n);
51
  
52
  return 0;
53
}//]

von U.G. L. (dlchnr)


Angehängte Dateien:

Bewertung
1 lesenswert
nicht lesenswert
Und collatz(1980976057694848447, ..) dauert auch nicht messbar länger!!!
1
D:\_PRJ\src>collatz
2
3
n=1980976057694848447
4
r=64024667322193133530165877294264738020
5
c=690
6
D:\_PRJ\src>

???????????????????????????????????????????????????????????????????????

von Karl (Gast)


Bewertung
0 lesenswert
nicht lesenswert
U Made my Day ?
(Und irgendjemand wird schon ein paper draus machen...)

Vielleicht kann der OP die gleichen zahlen Mal gegentesten...

von Joe S. (joesch)


Bewertung
0 lesenswert
nicht lesenswert
Ich bin mit den gmp Funktionen nicht so vertraut, aber
mir scheint, daß die Implementierung von U.G.L. nur für
ungerade Startwerte richtig funktioniert. Oder habe ich da
was übersehen?

von Peter II (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Joe S. schrieb:
> Ich bin mit den gmp Funktionen nicht so vertraut, aber
> mir scheint, daß die Implementierung von U.G.L. nur für
> ungerade Startwerte richtig funktioniert.

gerade macht auch keinen sinn. Denn dann wird gleich halbiert und man 
ist bei einem "anderen" startwert.

von Joe S. (joesch)


Bewertung
0 lesenswert
nicht lesenswert
Ok.

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
tztztz "nur" -Ofast ;)

zumindest -march=native sollts schon sein... immerhin will man ja die 
ganzen schönen extentions nutzen :P

Btw in dem Zusammenhang ist der Artikel lesenswert... 
https://en.wikipedia.org/wiki/Intel_ADX

73

von U.G. L. (dlchnr)


Angehängte Dateien:

Bewertung
1 lesenswert
nicht lesenswert
Ich denke, ich weiß nun, wie die 2 Minuten zu interpretieren sind.
Ich habe das Programm jetzt so geändert, dass eine Liste bis zu z.B. 
P(#47) generieren werden kann. Die Berechnung einer Liste bis P(#47) 
dauert auf einer logischen CPU meinems "Couch"-Laptops (i5 M540) knapp 
1000 Sekunden, damit gut 8 mal länger als die angegebenen 2 Minuten.

Ich vermute mal, dass sich dieser Faktor weitestgehend mit einer 
schnelleren CPU und einer 64bit Implemetierung ausgleichen läßt und die 
GMP-Implemetierung kaum langsamer sein wird als eine 
Assembler-Implemetierung, die auch 256bit unterstützt. Dabei unterstützt 
die GMP-Implementierung letztlich nicht nur 256bit, sondern passt sich 
gegebenenfalls auftauchenden Anforderungen an, weitet die 256bit also, 
wenn es sein muss, auch auf 1000bit, 10000bit oder noch mehr Bits aus!
1
D:\_PRJ\src>collatz
2
3
0: n=27 r=9232 c=77
4
0: n=255 r=13120 c=15
5
0: n=447 r=39364 c=53
6
0: n=639 r=41524 c=25
7
0: n=703 r=250504 c=82
8
0: n=1819 r=1276936 c=50
9
0: n=4255 r=6810136 c=85
10
0: n=4591 r=8153620 c=59
11
0: n=9663 r=27114424 c=48
12
0: n=20895 r=50143264 c=87
13
0: n=26623 r=106358020 c=63
14
0: n=31911 r=121012864 c=76
15
0: n=60975 r=593279152 c=116
16
0: n=77671 r=1570824736 c=71
17
0: n=113383 r=2482111348 c=120
18
0: n=138367 r=2798323360 c=71
19
0: n=159487 r=17202377752 c=66
20
0: n=270271 r=24648077896 c=211
21
0: n=665215 r=52483285312 c=144
22
0: n=704511 r=56991483520 c=69
23
0: n=1042431 r=90239155648 c=224
24
0: n=1212415 r=139646736808 c=84
25
0: n=1441407 r=151629574372 c=141
26
0: n=1875711 r=155904349696 c=131
27
0: n=1988859 r=156914378224 c=144
28
0: n=2643183 r=190459818484 c=201
29
0: n=2684647 r=352617812944 c=120
30
0: n=3041127 r=622717901620 c=78
31
0: n=3873535 r=858555169576 c=127
32
0: n=4637979 r=1318802294932 c=168
33
0: n=5656191 r=2412493616608 c=170
34
0: n=6416623 r=4799996945368 c=133
35
0: n=6631675 r=60342610919632 c=163
36
1: n=19638399 r=306296925203752 c=338
37
2: n=38595583 r=474637698851092 c=191
38
3: n=80049391 r=2185143829170100 c=164
39
5: n=120080895 r=3277901576118580 c=164
40
8: n=210964383 r=6404797161121264 c=275
41
12: n=319804831 r=1414236446719942480 c=167
42
59: n=1410123943 r=7125885122794452160 c=340
43
375: n=8528817511 r=18144594937356598024 c=212
44
547: n=12327829503 r=20722398914405051728 c=202
45
992: n=23035537407 r=68838156641548227040 c=196^C
46
D:\_PRJ\src>


1
// g++ -Ofast collatz.cpp -o collatz -I ..\gmp\include\ -L ..\gmp\lib\ -lgmp 
2
3
#include <ctime>
4
#include <stdio.h>
5
#include "..\gmp\include\gmp.h"
6
7
int main(int argc, char **argv) {                             //[
8
static const unsigned int width = 256;
9
static const unsigned int base_step = 3072;
10
static const unsigned int reste_amount = 116;
11
static unsigned int reste_loop = 0;
12
static const unsigned int reste[] =
13
{27, 31, 63, 91, 103, 111, 127, 159, 207, 231, 255, 283, 303, 319, 327, 
14
411, 415, 447, 463, 487, 495, 511, 543, 559, 603, 615, 639, 667, 679, 
15
703, 751, 763, 795, 799, 831, 859, 871, 879, 927, 1023, 1051, 1071, 
16
1087, 1095, 1135, 1179, 1183, 1191, 1215, 1231, 1255, 1263, 1275, 1279, 
17
1327, 1351, 1383, 1435, 1471, 1519, 1563, 1567, 1627, 1639, 1647, 1663, 
18
1695, 1767, 1791, 1819, 1855, 1863, 1903, 1951, 1959, 1983, 2031, 2043, 
19
2047, 2079, 2095, 2119, 2139, 2151, 2175, 2203, 2215, 2239, 2287, 2299, 
20
2331, 2367, 2407, 2463, 2511, 2535, 2559, 2587, 2607, 2671, 2715, 2719, 
21
2727, 2751, 2791, 2799, 2811, 2815, 2847, 2887, 2907, 2919, 2983, 3007, 
22
3055, 3067};
23
static char timstr[10];
24
static mpz_t b, n, r, x;
25
time_t stt, now; 
26
double sec;
27
unsigned int cnt, c, u;
28
int i;
29
30
  mpz_init2(b, width); 
31
  mpz_init2(n, width);                          
32
  mpz_init2(r, width);
33
  mpz_init2(x, width);
34
  mpz_set_ui(n, 1);
35
  mpz_set_ui(r, 2);
36
  stt = time(0);
37
  
38
  while (1) {
39
    mpz_add_ui(n, b, reste[reste_loop++]);
40
    if (reste_loop >= reste_amount) { 
41
      reste_loop=0;
42
      mpz_add_ui(b, b, base_step);
43
    }
44
    mpz_set(x, n);
45
    cnt = 0;
46
    c = 0;
47
    do {
48
      mpz_mul_ui(x, x, 3);
49
      mpz_add_ui(x, x, 1);
50
      cnt++;
51
      if ((i = mpz_cmp(x, r)) >= 0) {
52
        if (i == 0) {
53
          break;                         
54
        }
55
        mpz_set(r, x);
56
        c = cnt;
57
      }
58
      u = mpz_scan1(x, 0);
59
      mpz_tdiv_q_2exp (x, x, u);
60
      cnt += u;
61
    } while ((i = mpz_cmp(x, n)) > 0);
62
    if (c) {
63
      now = time(0);
64
      sec = difftime(now, stt);
65
      printf("\n%.f:", sec);
66
      gmp_printf(" n=%Zd", n);
67
      gmp_printf(" r=%Zd", r);
68
      printf(" c=%u", c);
69
    }
70
  }                
71
  return 0;                           
72
}//]

von U.G. L. (dlchnr)


Bewertung
1 lesenswert
nicht lesenswert
Hans schrieb:
> tztztz "nur" -Ofast ;)
>
> zumindest -march=native sollts schon sein... immerhin will man ja die
> ganzen schönen extentions nutzen :P

Die Geschwindigkeit dürfte primär davon abhängen, wie GMP übersetzt 
wurde.
Ich verwende 
http://cs.nyu.edu/~exact/core/gmp/gmp-static-mingw-4.1.tar.gz -
dieses Compilat setzt einen Pentium III voraus.

Ein, auf einen aktuellen Prozessor beschränktes Compilat wird natürlich 
schneller sein, so dass sich auch hier noch Optimierungen auftun.

Ob der Rest mittels -Ofast oder etwas anderem übersetzt wird, dürfte 
unerheblich bleiben.

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Servus,

hätte natürlich ein "nativ" optimiertes gpm vorausgesetzt... bin nämlich 
über die ADX diskussionen auf der gpm mailinglist auf den wiki artikel 
gestoßen :)

nachdems anscheinend ums suchen/testen der nächst höheren geht, lässt 
sich das auf einer moderen cpu locker locker parallelisieren... also 
mehrere startwerte parallel meine ich damit....

Jedenfalls befürchte ich, dass das auf einem FPGA nicht schneller wird 
da zumindest einige intel CPUs genau für diese anwendung (riesige bzw 
beliebig große integer) eine befehlssatzerweiterung haben.

damit hat man hoch optimiertes silizium mit optimiertem befehlssatz und 
richtig böser speicheranbindung gegen einen fpga... ziemlich unfair aus 
meiner sicht...

73

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
ahhh noch zu früh... gmp natürlich :)

73

von Stampede (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Sehr interessant die Disskussion hier.
Sorry, die Frage ist etwas OT: Was ist die Anwendung dafür? Habe mir mal 
den Wiki-Artikel durchgelesen, sehe aber nicht was man damit "machen" 
kann. Oder geht es hier um das rein akademische rund um das 
Collartz-Problem?

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hab' über Nacht das Programm mal mit einer anfänglichen Variablenbreite 
von 32bit laufen lassen - die Variation der Zeiten dürften vermutlich 
darauf zurückzuführen sein, was man mit der Mühle sonst noch gerade 
macht und wie heiß sie sich gerade fühlt - die GMP-Implementierung 
dürfte fast vollkommen unabhängig von der verwendeten Breite der 
Variablen sein.
1
D:\_PRJ\src>collatz
2
3
0: n=27 r=9232 c=77
4
0: n=255 r=13120 c=15
5
0: n=447 r=39364 c=53
6
0: n=639 r=41524 c=25
7
0: n=703 r=250504 c=82
8
0: n=1819 r=1276936 c=50
9
0: n=4255 r=6810136 c=85
10
0: n=4591 r=8153620 c=59
11
0: n=9663 r=27114424 c=48
12
0: n=20895 r=50143264 c=87
13
0: n=26623 r=106358020 c=63
14
0: n=31911 r=121012864 c=76
15
0: n=60975 r=593279152 c=116
16
0: n=77671 r=1570824736 c=71
17
0: n=113383 r=2482111348 c=120
18
0: n=138367 r=2798323360 c=71
19
0: n=159487 r=17202377752 c=66
20
0: n=270271 r=24648077896 c=211
21
0: n=665215 r=52483285312 c=144
22
0: n=704511 r=56991483520 c=69
23
0: n=1042431 r=90239155648 c=224
24
0: n=1212415 r=139646736808 c=84
25
0: n=1441407 r=151629574372 c=141
26
0: n=1875711 r=155904349696 c=131
27
0: n=1988859 r=156914378224 c=144
28
0: n=2643183 r=190459818484 c=201
29
0: n=2684647 r=352617812944 c=120
30
0: n=3041127 r=622717901620 c=78
31
0: n=3873535 r=858555169576 c=127
32
0: n=4637979 r=1318802294932 c=168
33
0: n=5656191 r=2412493616608 c=170
34
0: n=6416623 r=4799996945368 c=133
35
0: n=6631675 r=60342610919632 c=163
36
0: n=19638399 r=306296925203752 c=338
37
1: n=38595583 r=474637698851092 c=191
38
3: n=80049391 r=2185143829170100 c=164
39
4: n=120080895 r=3277901576118580 c=164
40
8: n=210964383 r=6404797161121264 c=275
41
12: n=319804831 r=1414236446719942480 c=167
42
60: n=1410123943 r=7125885122794452160 c=340
43
377: n=8528817511 r=18144594937356598024 c=212
44
552: n=12327829503 r=20722398914405051728 c=202
45
985: n=23035537407 r=68838156641548227040 c=196
46
1901: n=45871962271 r=82341648902022834004 c=220
47
2134: n=51739336447 r=114639617141613998440 c=305
48
2434: n=59152641055 r=151499365062390201544 c=372
49
2446: n=59436135663 r=205736389371841852168 c=400
50
2872: n=70141259775 r=420967113788389829704 c=469
51
3169: n=77566362559 r=916613029076867799856 c=300
52
4475: n=110243094271 r=1372453649566268380360 c=287
53
8215: n=204430613247 r=1415260793009654991088 c=399
54
9306: n=231913730799 r=2190343823882874513556 c=184
55
10914: n=272025660543 r=21948483635670417963748 c=199
56
17887: n=446559217279 r=39533276910778060381072 c=279
57
22679: n=567839862631 r=100540173225585986235988 c=278^C
58
D:\_PRJ\src>

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hier noch 'n kurzer Run mit einer Variablenbreite von 4096bit.
1
D:\_PRJ\src>collatz
2
3
0: n=27 r=9232 c=77
4
0: n=255 r=13120 c=15
5
0: n=447 r=39364 c=53
6
0: n=639 r=41524 c=25
7
0: n=703 r=250504 c=82
8
0: n=1819 r=1276936 c=50
9
0: n=4255 r=6810136 c=85
10
0: n=4591 r=8153620 c=59
11
0: n=9663 r=27114424 c=48
12
0: n=20895 r=50143264 c=87
13
0: n=26623 r=106358020 c=63
14
0: n=31911 r=121012864 c=76
15
0: n=60975 r=593279152 c=116
16
0: n=77671 r=1570824736 c=71
17
0: n=113383 r=2482111348 c=120
18
0: n=138367 r=2798323360 c=71
19
0: n=159487 r=17202377752 c=66
20
0: n=270271 r=24648077896 c=211
21
0: n=665215 r=52483285312 c=144
22
0: n=704511 r=56991483520 c=69
23
0: n=1042431 r=90239155648 c=224
24
0: n=1212415 r=139646736808 c=84
25
0: n=1441407 r=151629574372 c=141
26
0: n=1875711 r=155904349696 c=131
27
0: n=1988859 r=156914378224 c=144
28
0: n=2643183 r=190459818484 c=201
29
0: n=2684647 r=352617812944 c=120
30
0: n=3041127 r=622717901620 c=78
31
0: n=3873535 r=858555169576 c=127
32
0: n=4637979 r=1318802294932 c=168
33
0: n=5656191 r=2412493616608 c=170
34
0: n=6416623 r=4799996945368 c=133
35
0: n=6631675 r=60342610919632 c=163
36
1: n=19638399 r=306296925203752 c=338
37
1: n=38595583 r=474637698851092 c=191
38
3: n=80049391 r=2185143829170100 c=164
39
4: n=120080895 r=3277901576118580 c=164
40
7: n=210964383 r=6404797161121264 c=275
41
12: n=319804831 r=1414236446719942480 c=167
42
54: n=1410123943 r=7125885122794452160 c=340
43
344: n=8528817511 r=18144594937356598024 c=212
44
502: n=12327829503 r=20722398914405051728 c=202
45
913: n=23035537407 r=68838156641548227040 c=196^C
46
D:\_PRJ\src>

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> hätte natürlich ein "nativ" optimiertes gpm vorausgesetzt...

Meine Erfahrungen bei derartigen Untersuchungen, zuletzt mit
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?rd2&topic=182808&start=80#p1538578 
haben immer gezeigt, das eine Investition in die Auswahl der zu 
testenden Fälle und in den Grund-Algorithmus jedwede Investition in die 
Laufzeitoptimierung um Längen schlägt - von daher juckt es mich nicht 
die Bohne, hier mit einer Pentium III Library zu arbeiten.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> nachdems anscheinend ums suchen/testen der nächst höheren geht, lässt
> sich das auf einer moderen cpu locker locker parallelisieren... also
> mehrere startwerte parallel meine ich damit....

ganz so einfach wird das nicht, da die Untersuchung für den 
Startwert(n+1) den Rekord(n) benötigt - das läßt sich aber mittels der 
Annahme Rekord(n) = Startwert(n+1) und einer "Nachbehandlung" der 
Resultate beheben.

Es wird aber vorallen Dingen nur gelingen, eine Parallelisierung auf 
Threadebene zu erreichen - eine Vektorisierung wird wohl nicht mögkich 
sein.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> Jedenfalls befürchte ich, dass das auf einem FPGA nicht schneller wird

So vermute ich das auch, zumindest, wenn man das unter ökonomischen 
Gesichtspunkten betrachtet - eine 100-Thread-Lösung mit sauteuren 
MegaFPGAs wird wohl von einer 10-Maschine-i7-Lösung unter diesem 
Gesichtspunkt geschlagen. Bestenfalls bei der energieeffizientesten 
Lösung sehe ich ein Chance für die FPGAs.

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Stampede schrieb:

> Was ist die Anwendung dafür?

Keine - wie der Link auf http://www.ericr.nl/wondrous/pathrecs.html 
zeigt, würde man sich als Finder von #89 lediglich Silva, Roosendaal & 
Co beigesellen.

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Hans schrieb:
>> nachdems anscheinend ums suchen/testen der nächst höheren geht, lässt
>> sich das auf einer moderen cpu locker locker parallelisieren... also
>> mehrere startwerte parallel meine ich damit....
>
> ganz so einfach wird das nicht, da die Untersuchung für den
> Startwert(n+1) den Rekord(n) benötigt - das läßt sich aber mittels der
> Annahme Rekord(n) = Startwert(n+1) und einer "Nachbehandlung" der
> Resultate beheben.
>
> Es wird aber vorallen Dingen nur gelingen, eine Parallelisierung auf
> Threadebene zu erreichen - eine Vektorisierung wird wohl nicht mögkich
> sein.

Im threading liegt ja der witz... ohne jetzt die interna genauer 
studiert zu haben nehme ich an, dass jede integer einheit eigene logik 
für ADX hat.

Nachdem anscheinend die Zyklenanzahl groß werden kann müsste man mit 
prediction und "nachbearbeitung" was machen können (so fakor 2)...

U.G. L. schrieb:
> Hans schrieb:
>> hätte natürlich ein "nativ" optimiertes gpm vorausgesetzt...
>
> Meine Erfahrungen bei derartigen Untersuchungen, zuletzt mit
> 
http://matheplanet.com/matheplanet/nuke/html/viewtopic.php?rd2&topic=182808&start=80#p1538578
> haben immer gezeigt, das eine Investition in die Auswahl der zu
> testenden Fälle und in den Grund-Algorithmus jedwede Investition in die
> Laufzeitoptimierung um Längen schlägt - von daher juckt es mich nicht
> die Bohne, hier mit einer Pentium III Library zu arbeiten.

ja schon, aber... :)

hab auf die schnelle jetzt nichts zu gmp direkt und den unterschied 
MMX+SSE (kann der P3) zu AVX2/...  gefunden aber interessant ists schon

http://www.numberworld.org/ymp/v1.0/benchmarks.html

SSE4.1 zu AVX2 macht im durchsatz einen faktor 2 bei riesigen 
multiplikationen ...

ein "normales" windows compilat nutzt normalerweise nichtmal mmx...

ich habe mal sowas wie spice für die uni nachgebaut für ein spezielles 
problem... am schluss war per compiler switch ein faktor 10 drinnen...

hängt halt davon ab was man macht... bei mir waren eben multiplikationen 
von doubles mit AVX (+ auto-vectorizing) einfach um eine größenordnung 
schneller.
aber dafür gibt es ja diese befehlsatzerweiterungen.


natürlich muss der algorithmus (+implementierung des selben!) auch 
passen... da habe ich mir nochmal einen faktor 10 geholt...

da es aber um die umsetzung des oben mit inline-asm gespickten code in 
einem fpga geht, sehe ich das als optimal an ... zu fragen der optimalen 
(=schnellsten) lösung von problemen der theorethischen elektrotechnik 
habe ich eine meinung, zu sowas.... ähhhh nein :)

ich werd' am abend mal meine arbeitsbox (i5 6600k) mit dem gmp code 
füttern... auf der rechne ich normal gekoppelte 3d-fem probleme... mal 
schaun was sie zur abwechslung zu integer arithmetik sagt :)

73

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:

> SSE4.1 zu AVX2 macht im durchsatz einen faktor 2 bei riesigen
> multiplikationen ...

Klar, AVX2 hat insgesamt 256Bit und SSE 128Bit. Man kann also doppelt so 
viele Multiplikationen in der gleichen Zeit machen.

> ein "normales" windows compilat nutzt normalerweise nichtmal mmx...

Was auch immer "normal" ist. So haben zB alle CPUs mit x86-64 auch 
mindestens Unterstützung für SSE2.

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Markus K. schrieb:
> Klar, AVX2 hat insgesamt 256Bit und SSE 128Bit. Man kann also doppelt so
> viele Multiplikationen in der gleichen Zeit machen.

Ab Haswell. In Sandy/Ivy Bridge waren zwar die Befehle für 256 Bits 
schon drin, die Execution Units waren aber noch 128 Bits breit.

: Bearbeitet durch User
von R. M. (n_a_n)


Bewertung
0 lesenswert
nicht lesenswert
1
# collatz.py
2
3
from random import randint
4
5
# A 64Kbit long number
6
n = randint(pow(2, 65534), pow(2, 65535))
7
8
print hex(n)
9
10
steps = 0
11
12
while n > 1 :
13
    #print n
14
    if n & 1 :
15
        n = (n << 1) + n + 1
16
    else :
17
        n = n >> 1
18
    steps += 1
19
20
print "Steps", steps

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Markus K. schrieb:
>> ein "normales" windows compilat nutzt normalerweise nichtmal mmx...
>
> Was auch immer "normal" ist. So haben zB alle CPUs mit x86-64 auch
> mindestens Unterstützung für SSE2.

Also ich habe da nur folgendes gefunden:

https://www.microsoft.com/en-us/windows/windows-10-specifications
1
-To install a 64-bit OS on a 64-bit PC, your processor needs to support CMPXCHG16b, PrefetchW, and LAHF/SAHF.

etwas weiter gesucht findet man jetzt das:
http://superuser.com/questions/931742/windows-10-64-bit-requirements-does-my-cpu-support-cmpxchg16b-prefetchw-and-la

Also darf Windows 8 und 10 maximal SSE2 verlangen.

Ob dem so ist... 3dNow! (CMPXCHG16b) und VT-x (LAHF/SAHF) müssen sie, 
aber CMPXCHG16b muss nicht notwendigerweise SSE2 bedeuten...

Im Grunde ist das ja egal aber in so einem speziellen Fall... mal 
sehen... soo jetzt wird kompiliert :)

73

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> Ob dem so ist... 3dNow! (CMPXCHG16b)

3Dnow! gibts mittlerweile nicht mehr. CMPXCHG16b hat damit allerdings 
auch nichts zu tun.

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ergebnis mit 256bit code von oben auf einem ziemlich vanilla slackware 
14.2

kompiliert mit:

g++ -Ofast collatz.cpp -o collatz -lgmp


bash-4.3$ ./collatz

0: n=27 r=9232 c=77
0: n=255 r=13120 c=15
0: n=447 r=39364 c=53
0: n=639 r=41524 c=25
0: n=703 r=250504 c=82
0: n=1819 r=1276936 c=50
0: n=4255 r=6810136 c=85
0: n=4591 r=8153620 c=59
0: n=9663 r=27114424 c=48
0: n=20895 r=50143264 c=87
0: n=26623 r=106358020 c=63
0: n=31911 r=121012864 c=76
0: n=60975 r=593279152 c=116
0: n=77671 r=1570824736 c=71
0: n=113383 r=2482111348 c=120
0: n=138367 r=2798323360 c=71
0: n=159487 r=17202377752 c=66
0: n=270271 r=24648077896 c=211
0: n=665215 r=52483285312 c=144
0: n=704511 r=56991483520 c=69
0: n=1042431 r=90239155648 c=224
0: n=1212415 r=139646736808 c=84
0: n=1441407 r=151629574372 c=141
0: n=1875711 r=155904349696 c=131
0: n=1988859 r=156914378224 c=144
0: n=2643183 r=190459818484 c=201
0: n=2684647 r=352617812944 c=120
0: n=3041127 r=622717901620 c=78
0: n=3873535 r=858555169576 c=127
0: n=4637979 r=1318802294932 c=168
0: n=5656191 r=2412493616608 c=170
0: n=6416623 r=4799996945368 c=133
0: n=6631675 r=60342610919632 c=163
1: n=19638399 r=306296925203752 c=338
1: n=38595583 r=474637698851092 c=191
1: n=80049391 r=2185143829170100 c=164
2: n=120080895 r=3277901576118580 c=164
3: n=210964383 r=6404797161121264 c=275
4: n=319804831 r=1414236446719942480 c=167
18: n=1410123943 r=7125885122794452160 c=340
108: n=8528817511 r=18144594937356598024 c=212
156: n=12327829503 r=20722398914405051728 c=202
283: n=23035537407 r=68838156641548227040 c=196
^C
bash-4.3$

von S. R. (svenska)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> Also ich habe da nur folgendes gefunden:
>
> https://www.microsoft.com/en-us/windows/windows-10-specifications-To
> install a 64-bit OS on a 64-bit PC, your processor needs to support
> CMPXCHG16b, PrefetchW, and LAHF/SAHF.

Das wird von Microsoft genau deswegen so angegeben, weil es CPUs mit 
x86-64 und ohne diese Befehle gab. Hingegen gab es keine CPUs mit x86-64 
und ohne SSE2 - selbst der VIA Nano kann das.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Namt,
Freut mich dass das Thema Interesse weckt!

Zur Info habe meine obigen Code 
Beitrag "Re: 128 Bit Risc"
an ener Stelle mit condional moves aufgepeppt.

aus

"collatz_start: \n\t"
      "TEST $1,%r9 \n\t"
// wenn bit 1 von r9 gesetzt ist, ist r9 ungerade.
      "JZ gerade \n\t"
      "MOV %r13,%r14 \n\t"
      "MOV %r9,%r10 \n\t"
// hier: ungerade. fuehre den (3x+1)/2 Schritt durch.
"ungerade: \n\t"
      "SHR $1,%r14 \n\t"   // hoeherwertig - und ins carry
      "RCR $1,%r10 \n\t"   // niederwertiges uebernimmt carry

Habe ich


"collatz_start: \n\t"
    "TEST $1,%r9 \n\t"
// if bit 1 von r9 gesetzt ist, ist r9 ungerade.
     "cmovnz %r13,%r14 \n\t"
     "cmovnz %r9,%r10 \n\t"
    "JZ gerade \n\t"
// hier: ungerade. fuehre den (3x+1)/2 Schritt durch.
"ungerade: \n\t"
    "SHR $1,%r14 \n\t"   // hoeherwertig - und ins carry
    "RCR $1,%r10 \n\t"   // niederwertiges uebernimmt carry



gemacht was ca 20% speed bringt.

Damit erreiche ich den (PR #61):
start=2,674309,547647 record==770419,949849,742373,052272  in 156:45s

also in reinem GCC inline assembler auf 1 core des xeon.
Sicher kann man die anderen CMP, mit anschliessendem JA, JB auch noch 
optimieren.
das Werk :
http://www.agner.org/optimize/ gibt noch mehr Tricks her, danke guter 
Tip!
Wie nutzt man das prefetching aus um dies Jmp entscheidungen zu 
minimieren. Also lässt die cpu einfach 2 Zweige oder mehr weiterechnen, 
egal ob above oder below? Sie macht das doch wowieso oder?
Und entscheidet später, was plausibel ist.

Der Wert (#88) von eric.nl ist noch nicht offiziell verifiziert!! er 
erscheint mir auch zu hoch.
Thx!

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Wie nutzt man das prefetching aus um dies Jmp entscheidungen zu
> minimieren. Also lässt die cpu einfach 2 Zweige oder mehr weiterechnen,
> egal ob above oder below? Sie macht das doch wowieso oder?
> Und entscheidet später, was plausibel ist.

Wenn Du an einen bedingten Sprung kommst, dann entscheidet sich die CPU 
anhand statistischer Daten für einen Zweig und macht mit dem Prefetching 
usw. dort weiter. Falls die Vorhersage falsch war, dann verwirft sie 
diese Ergebnisse und macht mit dem richtigen Zweig weiter. Das ist aber 
teuer. Die CPU führt aber nicht die beiden möglichen Pfade parallel aus.

Deine CPU hat wahrscheinlich 2 Integereinheiten, die sie auch parallel 
benutzen kann, aber natürlich nur, wenn es keine Abhängigkeiten gibt. 
Man kann 3n+1 also nicht parallel rechnen lassen, weil man für das +1 ja 
das Ergebnis vom 3n braucht. Man könnte vielleicht zwei Folgen (von 
verschiedenen Startwerten) parallel berechnen. Die wären dann ja in 
verschiedenen Registern und hätten damit keine Abhängigkeiten.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> 283: n=23035537407 r=68838156641548227040 c=196

ok - das sind knapp 10% mehr, als man durch den Sprung von i5 M540 auf 
i5-6600K erwarten durfte.

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Markus K. schrieb:
> Deine CPU hat wahrscheinlich 2 Integereinheiten,

Ab Haswell (i3/5/7-4xxx aufwärts) sind es 4, aber nicht jede kann alles.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:

> Der Wert (#88) von eric.nl ist noch nicht offiziell verifiziert!! er
> erscheint mir auch zu hoch.

Also das r für das n von #88 passt auf jeden Fall mal schon (siehe meine 
zweite Nachricht in diesem Thread). Es kann also höchstens noch sein, 
dass ein kleinerer Startwert ein höheres r erzielt!

: Bearbeitet durch User
von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Sicher kann man die anderen CMP, mit anschliessendem JA, JB auch noch
> optimieren.

Entscheidend wäre für diese Art der Optimierung, sowohl die gerade als 
auch die ungerade Version zu berechnen und dann das Ergebnis mit CMOV 
auszuwählen. Völlig ohne bedingtem Sprung für diese Abfrage.

Also sinngemäss statt:
  if (gerade)
    n = <A>;
  else
    n = <B>;
ohne Sprung:
  t1 = <A>;
  t2 = <B>;
  n = gerade ? t1 : t2; // mit CMOV statt Jxx

Durch die zusätzlich in den Datenpfad eingebrachten CMOV Befehle wächst 
zwar die Länge des Datenpfades, und damit die Mindestausführungszeit 
einer Iteration, aber die Laufzeit von CMOV ist konstant gering, weil 
keine Misprediction erfolgt.

Wieviel das bringt, oder ob überhaupt, hängt völlig davon ab, ob die 
Sprungvorhersage irgendwelche Muster findet, oder ob das weitgehend 
zufällig ist. Die ADC/RCR Befehle sind nicht zueinander 
parallelisierbar, da nur eine der Units dazu in der Lage ist. Der 
Datenpfad wächst also zunächst deutlich an, es entfallen aber mögliche 
Pipeline Flushes durch Misprediction.

Ablauftechnisch betrachtet ist ein CMOV kein bedingt ausgeführter MOV, 
sondern ein Auswahlbefehl. Also nicht
  if (condition)
    dst = src;
sondern
  dst = condition ? src : dst;

Bei bedingten Sprüngen, die meistens in die gleiche Richtung gehen, wird 
sich das jedoch nicht unbedingt lohnen.

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Entscheidend wäre für diese Art der Optimierung, sowohl die gerade als
> auch die ungerade Version zu berechnen und dann das Ergebnis mit CMOV
> auszuwählen. Völlig ohne bedingtem Sprung für diese Abfrage.

Noch besser wäre meines Erachtens, die Entscheidung gerade/ungerade 
komplett zu eliminieren, so wie das bei meiner Implementierung geschehen 
ist - den Code-Part immer mit ungeradem n anlaufen, dann einmal UP (3 x 
n + 1) und anschließend alle DOWNs in einem Aufwasch erledigen.
Die DOWNs erledige ich unter Verwendung einer 
COUNT_TRAILING_ZEROS-Funktion und shifte danach den Wert entsprechend.

Unter Visual sieht das so aus:
1
  uint CountTrailingZeros(ui64 mod64) { //[
2
  uint ctz = mod64 ? 0 : 64;
3
4
    if (ctz) {
5
      return ctz;
6
    } else {
7
    ui32* pui32 = (ui32*) &mod64;
8
      if        (pui32[0]) {
9
        _BitScanForward((DWORD*) &ctz, pui32[0]);
10
      } else if (pui32[1]) {
11
        _BitScanForward((DWORD*) &ctz, pui32[1]);
12
        ctz += 32;
13
      }
14
      return ctz;
15
    }
16
  }//]

Wie das unter GCC/MINGW ausschaut, hab' ich noch nicht eruiert.

Unter GMP gibt's dafür mpz_scan1(...).

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Noch besser wäre meines Erachtens, die Entscheidung gerade/ungerade
> komplett zu eliminieren,

Ein besserer Algorithmus schlägt meist jede Optimierung auf 
Befehlsebene.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
A. K. schrieb:
> Ein besserer Algorithmus schlägt meist jede Optimierung auf
> Befehlsebene.

Wie schon mal oben von mir erwähnt :-)

von Lattice User (Gast)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> matthias schrieb:
>
>> Der Wert (#88) von eric.nl ist noch nicht offiziell verifiziert!! er
>> erscheint mir auch zu hoch.
>
> Also das r für das n von #88 passt auf jeden Fall mal schon (siehe meine
> zweite Nachricht in diesem Thread). Es kann also höchstens noch sein,
> dass ein kleinerer Startwert ein höheres r erzielt!

Womit dann #88 ungültig wäre.
Genau darum geht es ja beim verifizieren.

Dazu muss man alle ungeraden Werte zwischen 1038743969413717663 und 
1980976057694848447 erst gegen den Sieb und was da durchfällt gegen die 
aktuelle Folge testen. Das sind 471116044140565391 Werte.

Wenn man es schafft 1000000000 Werte/Sekunde (d.h. alle 4 CPU Takte 
einer 4GHz Maschine) zu testen braucht man fast 15 Jahre.

#89 zu finden braucht vorrausichtlich bis zum doppelten der Zeit.

Empirisch habe ich gesehen dass der Abstand zwischen 2 Rekorden ausser 
am Anfang durch 4 teilbar ist (#2-#72 nachgeprüft). Das halbiert die 
Dauer der Suche.

von Tom W. (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Gibt es eigentlich eine sinnvoll Anwendung für 128 Bit Auflösung? Ausser 
jetzt mal mathematischen Spielchen.

Ich habe den Eindruck, dass wir hier in Regionen vorstossen, die mher in 
Richtung Esotherik gehen und sich von dem Notwendigen entfernen. 
Vielleicht passt das 128 Bit Rechensystem ja auch zu den 128 Bit ADCs 
mit denen neuerdings Audiosamples abgespielt werden:

http://ewms.scidata.eu/Typ-I

Man beachte den letzten Satz auf der Seite. Der ist aber kein 
Tippfehler. Der Autor erklärt das auf den weiteren Seiten sehr genau, 
wie das patentierte Verfahren funktioniert.

Hier gibt es mehr zu dem System:

https://www.musiker-board.de/threads/sehr-interessante-neue-workstation-keyboard-in-entwicklung.640227/

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Verschlüsselung fällt mir als erstes ein.

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Andreas R. schrieb:
> Verschlüsselung fällt mir als erstes ein.

Nur ungewöhnliche Verfahren. Normale macht man heute oft mit spezieller 
Hardwareunterstützung.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Das schnellerte Finden immer grösserer Werte die bis zu einen pathrecord 
hoch und dann runterlaufen, ist an sich eher eine
Programmier-Herausforderung.
Die Herausforderung der Mathematik ist Ob und Warum enden wirklich alle 
Folgen auf 1?
Und das seit 2009 keine grösseren Werte als o.a. p(#87) gefunden wurden, 
ist merkwürdig, bei den heute verfügbaren Ressourcen.
Wohl auch deswegen weil ein Finden solcher bessern Werte noch kein 
Beweis der Collatz-vermutung darstellt.
Jedoch neben Oliveira, Silva und Rosendaal in der Hall of fame zu landen 
ist doch nett oder?
Und einen wirklich guten schnellen bezahlbaren universell verwendbaren 
128- oder 256 Bit Risc Integer Rechner, sei es mit fpga, asics oder wie 
auch immer zu "bauen", fände sicher Interessenten. (Jedenfalls 2 kenne 
ich gg)

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Kleine Code-Änderung -  nun wieder mit Loop-Erkennung, da man sich ja 
eigentlich nicht darauf verlassen darf, dass die Collatz-Vermutung wahr 
ist :-)

1
// g++ -Ofast collatz.cpp -o collatz -I ..\gmp\include\ -L ..\gmp\lib\ -lgmp 
2
3
#include <ctime>
4
#include <stdio.h>
5
#include "..\gmp\include\gmp.h"
6
7
int main(int argc, char **argv) {                             //[
8
static const unsigned int width = 4096;
9
static const unsigned int base_step = 3072;
10
static const unsigned int reste_amount = 116;
11
static unsigned int reste_loop = 0;
12
static const unsigned int reste[] =
13
{27, 31, 63, 91, 103, 111, 127, 159, 207, 231, 255, 283, 303, 319, 327, 
14
411, 415, 447, 463, 487, 495, 511, 543, 559, 603, 615, 639, 667, 679, 
15
703, 751, 763, 795, 799, 831, 859, 871, 879, 927, 1023, 1051, 1071, 
16
1087, 1095, 1135, 1179, 1183, 1191, 1215, 1231, 1255, 1263, 1275, 1279, 
17
1327, 1351, 1383, 1435, 1471, 1519, 1563, 1567, 1627, 1639, 1647, 1663, 
18
1695, 1767, 1791, 1819, 1855, 1863, 1903, 1951, 1959, 1983, 2031, 2043, 
19
2047, 2079, 2095, 2119, 2139, 2151, 2175, 2203, 2215, 2239, 2287, 2299, 
20
2331, 2367, 2407, 2463, 2511, 2535, 2559, 2587, 2607, 2671, 2715, 2719, 
21
2727, 2751, 2791, 2799, 2811, 2815, 2847, 2887, 2907, 2919, 2983, 3007, 
22
3055, 3067};
23
static char timstr[10];
24
static mpz_t b, n, r, x;
25
time_t stt, now; 
26
double sec;
27
unsigned int cnt, c, u;
28
int i;
29
30
  mpz_init2(b, width); 
31
  mpz_init2(n, width);                          
32
  mpz_init2(r, width);
33
  mpz_init2(x, width);
34
  mpz_set_ui(n, 1);
35
  mpz_set_ui(r, 1);
36
  stt = time(0);
37
  
38
  while (1) {
39
    mpz_add_ui(n, b, reste[reste_loop++]);
40
    if (reste_loop >= reste_amount) { 
41
      reste_loop = 0;
42
      mpz_add_ui(b, b, base_step);
43
    }
44
    mpz_set(x, n);
45
    cnt = 0;
46
    c = 0;
47
    do {
48
      mpz_mul_ui(x, x, 3);
49
      mpz_add_ui(x, x, 1);
50
      cnt++;
51
      if ((i = mpz_cmp(x, r)) >= 0) {
52
        if (i == 0) {
53
          if (c == 0) {
54
            i = 1;
55
          }
56
          break;                         
57
        }
58
        mpz_set(r, x);
59
        c = cnt;
60
      }
61
      u = mpz_scan1(x, 0);
62
      mpz_tdiv_q_2exp (x, x, u);
63
      cnt += u;
64
    } while ((i = mpz_cmp(x, n)) > 0);
65
    if (i == 0) {
66
      printf("\n!!! loop found:");
67
      gmp_printf(" n=%Zd", n);
68
      gmp_printf(" x=%Zd", x);
69
      gmp_printf(" r=%Zd", r);
70
      printf(" c=%u", c);
71
    }
72
    if (c) {
73
      now = time(0);
74
      sec = difftime(now, stt);
75
      printf("\n%.f:", sec);
76
      gmp_printf(" n=%Zd", n);
77
      gmp_printf(" r=%Zd", r);
78
      printf(" c=%u", c);
79
    }
80
  }                
81
  return 0;                           
82
}//]

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Hans schrieb:
>> nachdems anscheinend ums suchen/testen der nächst höheren geht, lässt
>> sich das auf einer moderen cpu locker locker parallelisieren... also
>> mehrere startwerte parallel meine ich damit....
>
> ganz so einfach wird das nicht, da die Untersuchung für den
> Startwert(n+1) den Rekord(n) benötigt - das läßt sich aber mittels der
> Annahme Rekord(n) = Startwert(n+1) und einer "Nachbehandlung" der
> Resultate beheben.
>
> Es wird aber vorallen Dingen nur gelingen, eine Parallelisierung auf
> Threadebene zu erreichen - eine Vektorisierung wird wohl nicht mögkich
> sein.

Hallo miteinander :)

Doch, das geht sehr gut, zB einfach unter linux mit fork auf mehrere
Kerne oder indem man einfach nur bestimmte Reste auf einzelnen Maschinen
betrachtet. Die Abhängigkeit von den vorhergehenden Records wird dabei
erst einmal nicht berücksichtigt, dh jeder Kern / jede Maschine wirft
auch "Candidate Records" aus, die von anderen getoppt werden die von
anderen Kernen/Maschinen gefunden wurden. Die sind aber vergleichsweise
einfach auszusortieren, entweder durch manuelles "drübergucken" oder
indem sie an einen zentralen thread weitergegeben werden, der dann
vergleicht und nur die "echten" Records durchlässt. Da es
vergleichsweise wenige (Candiate) Records gibt im Vergleich zur Anzahl
der zu untersuchenden Folgen fällt das bezüglich der laufzeit kaum ins
gewicht. Wir haben aktuell knapp 50 Kerne am Start, was natürlich einen
sehr erwünschten Faktor zur Laufzeit beiträgt, und eine Überlegung wäre
tatsächlich es mit verteiltem Rechnen weiter anzugehen und dazu eine
Schnittstelle anzubieten, über die man ungenutzte Maschinen/Kerne an das
System anbinden kann.

have fun!
gonzens

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Und einen wirklich guten schnellen bezahlbaren universell verwendbaren
> 128- oder 256 Bit Risc Integer Rechner, sei es mit fpga, asics oder wie
> auch immer zu "bauen", fände sicher Interessenten. (Jedenfalls 2 kenne
> ich gg)

Das ist aber etwas völlig anderes und ein viel aufwändigeres Projekt 
als nur die Collatz-Folge zu berechnen. Wenn Du auch noch schneller als 
eine aktuelle Intel-CPU sein möchtest, die sich ihre 256bit 
zusammenstückeln muss, dann wird das auch noch richtig teuer.

Eukrott V. schrieb:
>> Es wird aber vorallen Dingen nur gelingen, eine Parallelisierung auf
>> Threadebene zu erreichen - eine Vektorisierung wird wohl nicht mögkich
>> sein.

> Doch, das geht sehr gut, zB einfach unter linux mit fork auf mehrere
> Kerne oder indem man einfach nur bestimmte Reste auf einzelnen Maschinen
> betrachtet.

Das ist aber keine Vektorisierung. Mit Vektorisierung ist gemeint, dass 
man die SIMD-Befehle der CPU benutzt um die Berechnungen zu machen. Aber 
wie Matthias schon ganz am Anfang geschrieben hat, fehlt den 
SIMD-Befehlen das Carry-Flag, d.h. man kann sich aus einer 
64Bit-Addition keine 256Bit Addition zusammenbasteln.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
ich habe gpp mit apt-get installiert, aber wie installiere ich die gmp 
library, so dass:

g++ -Ofast collatz.cpp -o collatz -I ..\gmp\include\ -L ..\gmp\lib\ 
-lgmp


nicht den Fehler "g++: error: ..gmplib -lgmp: Datei oder Verzeichnis 
nicht gefunden"
meldet?

Damke

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Markus K. schrieb:
> Das ist aber keine Vektorisierung. Mit Vektorisierung ist gemeint, dass
> man die SIMD-Befehle der CPU benutzt um die Berechnungen zu machen. Aber
> wie Matthias schon ganz am Anfang geschrieben hat, fehlt den
> SIMD-Befehlen das Carry-Flag, d.h. man kann sich aus einer
> 64Bit-Addition keine 256Bit Addition zusammenbasteln.

Ja klar, deshalb sprach ich auch erstmal von Parallelisierung. Die 
Vektoriesierung ist ein anderes Ding, klar, und da besteht bei mir auch 
erheblicher "Nachholbedarf"...

Mit den Registern R8..R15 bekommt man es hin, dort wird das Carry in 
klassischer Weise bedient, nx64 Werte "zusammenzubasteln", siehe den 
Code oben. Dort hab ich es mit 2x64 Bit Registern gemacht, es auf 3x64 
zu erweitern wäre kein Ding und damit auch alles abgedeckt was man 
brauchen wird. Welchen Laufzeitunterschied eine 64bit zu einer 128bit 
oder 192bit Version macht würde ich einfach nochmal austesten.

Ich poste dann einfach auch bei Gelegenheit nochmal die aktuellen Werte 
die wir mit einer auf dieser Basis zubereiteten x86-version erreichen.

von U.G. L. (dlchnr)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Entweder indem Du die Pfade "..\gmp\include\" und "..\gmp\lib\" an Deine 
Gegebenheiten anpasst oder indem Du meine Verzeichnisstruktur verwendest 
:-)

Vermutlich kannst Du "-I ..\gmp\include\ -L ..\gmp\lib\" auch weglassen 
und entsprechende Enviroment-Variablen setzen.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Ach ja - die Source-Code-Zeile "#include "..\gmp\include\gmp.h"" ist 
nat. egebenenfalls auch anzupassen!

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Seh' gerade, dass ich in meinem zuletzt geposteten Code noch "width" auf 
4096 gesetzt habe - also gegebenenfalls anpasssen!

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Vermutlich kannst Du "-I ..\gmp\include\ -L ..\gmp\lib\" auch weglassen
> und entsprechende Enviroment-Variablen setzen.

Also "Hans" hat auf seinem Linux lt. 
Beitrag "Re: 128 Bit Risc"
"g++ -Ofast collatz.cpp -o collatz -lgmp" zum Compilieren benutzt -
u.U. wird der Include-Suchpfad und der Library-Suchpfad schon bei der 
Installation von GMP korrekt ergänzt!?

: Bearbeitet durch User
von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Um mal ein paar Benchmarks zu haben...

Wir benutzen ein Programm nach einem Algorithmus, den "cyrix" vom MP 
optimiert hat, und das in C geschrieben ist. Der Algo besorgt im 
wesentlichen das Begrenzen auf einzelne Reste nach Zweierpotenzen und 
führt mehrere Schritte in einem durch, indem die Ergebnisse vorberechnet 
werden und die Faktoren/Summanden die zu verwenden sind aus einer 
Tabelle abgegriffen werden. Wir haben das auf ca. 50 Kernen laufen, die 
auf "handelsübliche" Server unter Linux verteilt sind. 12 davon habe ich 
beigesteuert. Wir erreichen damit

path #63 in ca. 1 min 20 sek und damit auf etwa 1 Stunde bezogen auf 
einen Kern.

Das ist ein 42 bit Startwert, dh die Maschinerie verarbeitet insgesamt 
etwas bei 5*10^43 pro Stunde oder 10^42 / (Kern*Stunde). Das Ganze läuft 
jetzt seit etwa 3 Wochen und wir sind damit bei #83 (immer nach dem 
Listing bei Roosendaal) angekommen. Spannend wird es also erst, wenn wir 
nach aktuellem stand die vierfache laufzeit erreichen, was leider dann 
schon in monaten rechnet und eigentlich keinen spass macht zu warten. dh 
es werden noch verbesserungen gesucht :)

Wir arbeiten parallel an einem Programm in x86 asembler (code oben von 
mathias gepostet), ziel war zu schauen ob man damit überhaupt eine 
merkliche verbesserung gegenüber dem c code erreicht. dieses erreicht 
auf einem kern und mit einem eher "brute force" vorgehen

#47 in 1 min 24s das ist bei 35 bit startwert

Dh unser Assembler Programm "Hinkt" um einen faktor von geschätzt < 4 
hinter der algorithmisch verbesserten, in C codierten Lösung her (was 
oben ja auch schon angedeutet wurde, dass man sich eher auf den 
algorithmus konzentrieren sollte).

(trotzdem hat es mich da erfasst und ich würde gerne hier noch 
optimierungspotiential ausschöpfen wo es sich anbietet, dh mehr darüber 
lernen, wie man assembler für aktuelle prozessoren optimiert).

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> Wir benutzen ein Programm nach einem Algorithmus, den "cyrix" vom MP
> optimiert hat, und das in C geschrieben ist.

Ah ja - der cyrix vom MP - der wird dann die in meiner Implementierung 
gemachten Optimierungen (Eliminierung der gerade/ungerade Entscheidung, 
Zusammenfassung der DOWNs, Abbruch der Berechung für einen Startwert, 
wenn ein vorhergehnerder Rekordwert erreicht wurde), vermutlich alle 
schon eingebaut haben!

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> Das Ganze läuft
> jetzt seit etwa 3 Wochen und wir sind damit bei #83 (immer nach dem
> Listing bei Roosendaal) angekommen. Spannend wird es also erst, wenn wir
> nach aktuellem stand die vierfache laufzeit erreichen, was leider dann
> schon in monaten rechnet und eigentlich keinen spass macht zu warten. dh
> es werden noch verbesserungen gesucht :)

Wieso setzt Ihr eigentlich nicht direkt in der Gegend von #87 auf (bis 
dahin scheinen die Ergebnisse doch verifiziert zu sein)?

: Bearbeitet durch User
von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
was dort gemacht wurde läuft (als eigentlich zentrale verbesserung) 
darauf hinaus, a) schritte zusammenzufassen und b) mit zwei werten zu 
rechnen, einem ungefähren der die grössenordnung angibt und der zum 
prüfen des Erreichen von path-record oder startwert benutzt wird, und 
dann den letzten stellen, also dem rest bzgl. irgendeiner 2^x basis, die 
genau berechnet werden, um eben die nächsten sprünge zu bestimmen.

http://matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=223140&post_id=1633918

hier um den post herum wird das da beschrieben.


warum wir uns die roosendaal liste entlangarbeiten ist glaube ich 
einfach historisch bedingt. natürlich könnte man auch bei #87 anfangen. 
das macht aber eigentlich erst sinn wenn man schnell genug ist dort auch 
nennenswerte bereiche abzugrasen. und wenn man schnell genug ist.. kann 
man auch bei eins anfangen * feix

von Hans (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
U.G. L. schrieb:
> U.G. L. schrieb:
>> Vermutlich kannst Du "-I ..\gmp\include\ -L ..\gmp\lib\" auch weglassen
>> und entsprechende Enviroment-Variablen setzen.
>
> Also "Hans" hat auf seinem Linux lt.
> Beitrag "Re: 128 Bit Risc"
> "g++ -Ofast collatz.cpp -o collatz -lgmp" zum Compilieren benutzt -
> u.U. wird der Include-Suchpfad und der Library-Suchpfad schon bei der
> Installation von GMP korrekt ergänzt!?

unter linux braucht man weniger denken... wenn die lib sauber 
installiert wurde, dann weiß der gcc wo sie ist (für gewöhnlich /usr/lib 
bzw /usr/lib64).

bei dem kurzen code bekomme ich ca +-10% unterschiedliche laufzeiten je 
nach compilereinstellungen auf meiner x86-64 maschine.

ob gmp mit assembler optimierungen compiliert wurde oder nicht ist da 
schon drinnen.

ich habe jetzt aber (noch) nicht gegen die Intel MKL gelinkt... gut 
möglich, dass da einiges drinnen ist... bei BLAS machts jedenfalls einen 
gewaltigen unterschied.

73

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Moin,
Ich wollte die gmp library auf einem ubuntu Derivat installieren.

sudo apt-get install libgmp3-dev

Finde aber nicht das Verzeichnis gmp/lib/" oder  gmp/include/" ...
die library müsste doch unter usr sein? oder sbin?
Aufruf von "find -name libgmp3-dev"
findet eine Datei ./usr/share/doc/libgmp3-dev.gz wohl eine doku.
Sry ich hab wenig Erfahrung mit linux, wie ruf ich gpp bzw g++ richtig 
auf?

Das collatz.cpp hab ich unter home/matthias
also bei
"g++ -Ofast collatz.cpp -o collatz -I ..\gmp\include\ -L ..\gmp\lib\ 
-lgmp"
stimmen die Pfade natürlich nicht.
Thx
M.

von rmu (Gast)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Moin,
> Ich wollte die gmp library auf einem ubuntu Derivat installieren.
>
> sudo apt-get install libgmp3-dev
>
> Finde aber nicht das Verzeichnis gmp/lib/" oder  gmp/include/" ...
> die library müsste doch unter usr sein? oder sbin?
> Aufruf von "find -name libgmp3-dev"
> findet eine Datei ./usr/share/doc/libgmp3-dev.gz wohl eine doku.
> Sry ich hab wenig Erfahrung mit linux, wie ruf ich gpp bzw g++ richtig
> auf?
>
> Das collatz.cpp hab ich unter home/matthias
> also bei
> "g++ -Ofast collatz.cpp -o collatz -I ..\gmp\include\ -L ..\gmp\lib\
> -lgmp"
> stimmen die Pfade natürlich nicht.
> Thx
> M.

* \ ist ein "escape"-zeichen, nicht als pfad-trenner verwenden
* / als pfad-trenner verwenden
* dpkg -L libgmp3-dev bzw. dpkg -s libgmp3-dev
* libgmp3-dev ist vermutlich eh das falsche paket --> apt-get install 
libgmp-dev
* man find

bei mir unter ubuntu 16.04 braucht die libgmp kein zusätzliches -I oder 
-L

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
#87  0e6a 5c22 fd7b de9f : 003d 8335 83fc b4f4 a0aa 0247 bd70 f498
#88  1b7d d73a 9374 85bf : 302a b3d0 52fb 87c0 6228 d249 581b e0e4

Mal angedacht - eine FPGA-Lösung mit reste_amount Maschinen.

Jede Maschine bearbeitet einen Startwert und liefert nur 1bit 
Information (=> wenig Outoutdaten) der Form 
uninteressanter/interessanter-Startwert. Uniteressant ist ein Startwert, 
wenn innerhalb einer gewissen Anzahl von Takten (250 oder 500 oder 1000 
/ noch zu bestimmen) keines der Bits X59 bis X117 gestetzt ist (die 
Maschine wird dann gestoppt, damit sie sich nicht zum falschen Zeitpunkt 
vielleicht doch noch kurz für interessant hält :-). "Interessant" wären 
alle anderen (und mit einer richtigen CPU zu überprüfen), also die, bei 
denen eines dieser Bits nach x-Takten gesetzt ist. Wenn der bisherige 
Rekord "angekratzt" wird, also X116 oder X117 gesetzt wird, wird die 
Maschine angehalten - sie (also derm entsprechende Startwert) ist auf 
jeden Fall interessant. Verzichten würden wir also auf 
Startwert-Register und Rekordwert-Register und zwei Vergleicher, sowie 
die ganze Logik darum herum, was den Aufwand pro Maschine grob 
verdoppeln, die Anzahl der Maschinen halbieren würde.

117 LUTs/FFs 117bit Arbeitsreg. X mit Input Multiplexer 
(ALU/Shifter/Load?)
118-? LUTs 118bit ALU zur Berechnung von UP (2X + X + Carry(1)) / 2
117-? LUTs 117bit Shifter zur Generierung der DOWNs X/2 (& ev. 
Load-Daten?)
10-50 LUTs Uninteressant/Interessant- und Ausgabe-Logik

Die Maschinen sind nur für das "Abgrasen" eines bestimmten Bereichs 
konfiguriert - ist der abgearbeitet oder ein neuer Rekordwert gefunden, 
muss das Design angepasst und neu compiliert werden!

Schön wäre es, wenn der Algorithmus dahingehend geändert werden könnte, 
dass base_step eine Potenz von 2 ist (also z.B. 2048 oder 4096), dann 
könnte start_base von einem einfachen Counter kommen und reste[Maschine] 
wäre fix.für jede Maschine. Falls das nicht möglich ist, müsste 
start_base von einer weiteren Register/ALU-Kombination kommen, der 
Startwert von jeder Maschine selbst berechnet werden - dazu müsste in 
den X-Operand-Pfad ein weiterer Multiplexer eingebaut werden (was die 
erreichbare Taktfrequenz senkt), mittels dem man 2 * reste[Maschine] an 
den X-Operand anlegen kann - außerdem  für diese Berechnung Carry(0). 
Wir haben also keine Inputdaten!

Die Fähigkeiten des Shifters würde man zunächst mal so wählen, dass er 
die erreichbare Taktfrequenz nicht verringert, seine Durchlaufzeit also 
kleiner/gleich der der ALU ist, in zweiter Linie, wieviele LUTs man 
dafür investieren möchte.

Insgesamt könnte man pro Maschine mit 500-1000 LUTs hinkommen, die 
gesamte FPGA-Lösung erforert also 100k LUTs aufwärts - lt. Mouser 
erfordert das FPGAs für 150 EUR aufwärts!

Fragen an die Mathematiker:
- hilft Euch das weiter?
- base_step == 2048?
- ???

Fragen an die FPGAler:
- wieviele LUTs für 128bit ALU?
- erreichbare Takt-Frequenz?
- verfügbare Boards mit PCIe-, USB- oder Ethernetanbindug zum PC?
- ???

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:

> ob gmp mit assembler optimierungen compiliert wurde oder nicht ist da
> schon drinnen.
>
> ich habe jetzt aber (noch) nicht gegen die Intel MKL gelinkt... gut
> möglich, dass da einiges drinnen ist... bei BLAS machts jedenfalls einen
> gewaltigen unterschied.

Ich denke, entscheident ist, für welche Targets GMP speziellen Code zur 
Verfügung stellt!

https://gmplib.org/manual/Build-Options.html => CPU types => x86 family

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
für den skylake ist gibts ein extra target in 6.1.0 ...

https://gmplib.org/list-archives/gmp-devel/2015-August/004101.html

möglicherweise wäre es sinnvoll statt mpz-funktionen die mpn varianten 
zu probieren.

73

von daybyter (Gast)


Bewertung
0 lesenswert
nicht lesenswert
@U.G. L. : man braucht ja keine komplette 128 Bit ALU. Die wenigen 
Funktionen (halbieren und *3+1) haben auf dem cyclone 2 ja nur paar 
hundert LEs belegt. Man sollte halt ein Array mit solchen Collatz 
Filtern haben, aber auch das ginge auf einem < 50,- FPGA vielleicht 
noch.

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Ja, das hilft weiter :)

ich fang mal mit den einfachen dingen an...

der wahl der "basis" von 3*2^n erlaubt es, etwa ein drittel der reste 
auszusondern, da man auch Zahlen der Form 3*x+2 nicht prüfen braucht 
(Grund wird gerne nachgeliefert). So dies natürlich einen Faktor von 3/2 
oder mehr durch probleme in der konkreten implementierung erzeugt, macht 
es keinen sinn und man kann stattdessen "basen" der form 2^n nutzen. Es 
erschien effizienter, die Zahl der Basen um Faktor 3 zu erhöhen und die 
entsprechenden Reste auszulassen, als zur laufzeit den rest mod 3 zu 
bestimmen. astrid schlug vor, den rest mod 3 mitlaufend zu berechnen, 
vielleicht geht das effizient zu programmieren, da habe ich mir keinen 
genaueren kopf drüber gemacht.

das sieb bzgl. der 2-er potenzen kann man simpel berechnen, ich mache es 
aktuell mit einem PHP Programm (igittttt) das mir eine datei reste.h 
erzeugt, die ich in den c code einbinde. Die Tabelle könnte man 
theoretisch beliebt erweitern, allerdings bringt es dann keine so 
riesigen faktoren mehr (klaro). Auch dazu ggf. gerne mehr oder mal auf 
dem mp gucken.

schön dass der thread hier auf dem mp verlinkt wurde :) das macht es 
ggf. einfacher. ich bin dort gonz (klar).

Den Rest des Beitrages  Autor: U.G. L. (dlchnr) Datum: 16.12.2016 13:24 
muss ich erstmal schritt für schritt verdauen, aber das scheint genau 
die richtung zu sein, die mir da im kopf herumschwebte. Das entspricht 
meinen vorstellungen das parallel zu bearbeiten, und ggf. kann eben so 
ein prozess auch einfach "kandidaten" herausfiltern, die man dann 
anderswo konkret einzeln prüft. zB könnte man das vergleichen mit dem 
Record erheblich vereinfachen, indem man auf das überschreibten 
bestimmter "höchsten bits" prüft und dann das ergebis auswirft, auf dass 
zB pc-seitig dann genau berechenet wird, ob das nun passt oder nicht.

ich werd mich da am we mal genauer mit beschäftigen - heute muss ich 
leider erstmal noch arbeitstechnisch was erledigen * feix


PS.: Cool wäre es zB, jedem FPGA genau einen (oder eine Anzahl von) 
Resten beizubringen, und dann eine Maschine zu haben, die zB Folgen der 
Form 4096*x+127 durchrechnet (nur um ein Beispiel zu geben). Wenn man 
von diesen 100 (oder whatever) auf einem FPGA unterbringt, könnte man 
dort dann entsprechend eben 100 Reste hinterlegen und, wenn das FPGA 
Array grösser wird, eben die 2-er Basis erhöhen.

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
daybyter schrieb:
> @U.G. L. : man braucht ja keine komplette 128 Bit ALU. Die wenigen
> Funktionen (halbieren und *3+1) haben auf dem cyclone 2 ja nur paar
> hundert LEs belegt. Man sollte halt ein Array mit solchen Collatz
> Filtern haben, aber auch das ginge auf einem < 50,- FPGA vielleicht
> noch.

OK - mit dem Begriff ALU hab' ich mich vertan, es genügt natürlich ein 
128Bit Adder - bei geschätzten Aufwand LUTs/LEs mit ein paar Hundert für 
Register und Adder stimmen wir ja überein. Für mehr als 100 solcher 
Maschinen kommen wir dann aber doch in den 100k LUT/LE-Bereich.

: Bearbeitet durch User
von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Jede Maschine bearbeitet einen Startwert und liefert nur 1bit
> Information (=> wenig Outoutdaten) der Form
> uninteressanter/interessanter-Startwert. Uniteressant ist ein Startwert,
> wenn innerhalb einer gewissen Anzahl von Takten (250 oder 500 oder 1000
> / noch zu bestimmen) keines der Bits X59 bis X117 gestetzt ist (die
> Maschine wird dann gestoppt,

wäre es möglich sich zusätzlich zum pathrecord auch die zyklen anzahl zu 
merken bei dem er erreicht wurde und in den folgenden berechnungen 
einfach abzubrechen wenn der höchstwert für den aktuellen startwert bei 
der gleichen zyklen anzahl noch unter dem bisherigen rekord liegt?

unter den 1. 10 gibt's 2 ausreißer.. die frage ist nun ob das nicht als 
"sieb" schon herhalten würde..

Sprich auf die Art die nächst höhere bestimmen und dann von oben nach 
unten genau runter suchen.

wenn man die bisher höchste zyklenzahl zum erreichen des Rekords 
heranzieht würden die 1. 10 problemlos funktionieren...

73

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
zu Basis 3*2^n:
Ich hab' den Thread mal auf MP überflogen, aber eigentlich keine Zeit, 
mich da einzuarbeiten, da ich eigentlich endlich mal mein 
VHDL-LErn-Projekt angehen will :-)
Ich vermute dann aber mal, das man das zusätzliche Register + Adder (da 
genügen 64bit) und einen gewissen Taktfrequenzverlust in Kauf nehmen 
wird (z.B. statt 150MHz nur 125MHz), wenn der Algorithmus dafür 
entsprechend effizienter wird.

ansonsten:
"kandidaten" ==> "Interessant"
überschreibten  bestimmter "höchsten bits" ==> X116 oder X117 gesetzt 
wird

> Cool wäre es zB, jedem FPGA genau einen (oder eine Anzahl von)
> Resten beizubringen

ich gehe eigentlich davon aus, dass das FPGA wenigstens reste_amount == 
116 Einheiten enthält!
1
die erste berechent pro Interval (z.B. 500 Takte)
2
3
start_base+3072*T+tab[0], im Interval T1 start_base+3072*1+ tab[0]
4
                          im Interval T2 start_base+3072*2+ tab[0]
5
                                       :
6
die zweite entsprechend
7
8
start_base+3072*T+tab[1], im Interval T1 start_base+3072*1+ tab[1]
9
                          im Interval T2 start_base+3072*2+ tab[1]
10
                                        :
11
:
12
:
13
:
14
15
die letzte
16
start_base+3072*T+tab[115], im Interval T1 start_base+3072*1+ tab[115]
17
                            im Interval T2 start_base+3072*2+ tab[115]
18
                                         :

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> wäre es möglich sich zusätzlich zum pathrecord auch die zyklen anzahl zu
> merken

Ich würde mir keinen pathrecord merken wollen, sonder nur durch gesetzte
Bits auf X116 und X117 feststellen wollen, das der pathrecord 
"angekratzt" wurde, schon gar nicht weitere Sachen merken, weil das in 
einem FPGA zu teuer ist.

Ich seh' das so - eine LUT / ein LE ist gut ausgeben, wenn's dort 
richtig "klappert" - wenn das LE nur alle 100000 oder 1000000 Takte 
schaltet, sollte man es vermutlich für was anderes verwenden - hier für 
eine weitere Maschinen.

Es könnte von daher durchaus sinnvoll sein, sich z.B. auf 80bit zu 
beschränken und den Startwert als "Interessant" zu markieren, wenn X78 
oder X79 gesetzt werden.

Wichtiger erscheint mir momentan die untere Grenze zu sein - wieviele 
Takte sind notwendig, um den Startwert in 99% oder 99m9% der Fälle unter 
0x0800.0000.0000.0000 zu bringen - oder dauert das zu lange und es musss 
doch in ein 64Bit-Startwert-Register und in einen 64plus-Vergleicher 
investiert werden (plus ==> sind X64 bis X117 müssen zusätzlich 0 sein).

Solche Fragen müssen von den MPlern mittels Simulationen/Runs im 
fraglichen Zahlenbereich klären.

Auf der anderen Seite müsste sich dann ein versierte VHDLler oder 
VERILOGer finden, der die Erkenntnisse umsetzt - ich kann dazu derzeit 
nichts betragen.

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
> ich gehe eigentlich davon aus, dass das FPGA wenigstens reste_amount ==
> 116 Einheiten enthält!

In mindestens dieser Größenordnung müssen wir uns bewegen!
Denn eine einzelne Kette berechnet der Syklake viel schneller.
Wenn nicht wenigstens diese Anzahl von Einheiten bei einer ordentliche 
Taktfrequnez (mindestens 100MHz) erreichbar ist, kaufst Du statt dem 
FPGA besser einen 1/8 Skylake :-)

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich bin mit diesen Pfaden in Linux nicht so vertraut..

Ich gebe an: g++ -Ofast collatz.cpp -o collatz -lgmp

Vorher hatte ich
apt-get install g++ und dann
apt-get install libgmp3-dev erfolgreich installiert.
Oder ist das das falsche gmp?

Wenn ich in meinem home/ich Verzeichnis angebe: g++ -Ofast collatz.cpp 
-o collatz -lgmp, dann kommt:

collatz.cpp:4:32: fatal error: ..\gmp\include\gmp.h: Datei oder 
Verzeichnis nicht gefunden
#include "..\gmp\include\gmp.h"
compilation terminated.

In line 4 des collatz.cpp steht #include "..\gmp\include\gmp.h"
Kann ja gar nich gehen, denn das waere ja unter \home\gmp und das gibts 
nicht.

Wenn ich das #include "..\gmp\include\gmp.h" rauslasse kommt :

collatz.cpp:6:14: error: variable or field ‘collatz’ declared void
 void collatz(mpz_t n, mpz_t r) {                              //[
              ^
collatz.cpp:6:14: error: ‘mpz_t’ was not declared in this scope
collatz.cpp:6:23: error: ‘mpz_t’ was not declared in this scope
 void collatz(mpz_t n, mpz_t r) {                              //[

k.A was da nicht stimmt oder fehlt?
Thx


                       ^

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> In line 4 des collatz.cpp steht #include "..\gmp\include\gmp.h"
> Kann ja gar nich gehen, denn das waere ja unter \home\gmp und das gibts
> nicht.

dass #include "..\gmp\include\gmp.h" anzupassen ist, hab' ich schon viel 
weiter oben angemerkt. Wo das apt-get die GMP hinplaziert, kann ich Dir 
nicht sagen - ich arbeite noch nicht auf Linux, sondern in diesem Fall 
mit MinGW/TDM-GCC.
Vermutlich kann Dir Hans 
Beitrag "Re: 128 Bit Risc" 
sagen, wie das #include abzuändern ist.

ohne das #include kennt der Compiler nat. schon mal den Typ mpz_t nicht!

Zu libgmp3-dev / libgmp-dev hatte sich rmu 
Beitrag "Re: 128 Bit Risc" 
geäußert - ich kann dazu, ohne Recherche nichts sagen.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Zusatz:
Ich sehe hier leider keine Möglichkeit, einen abgeschickten Thread zu 
ändern, oder habs übersehen.
Was ich hinzufügen wollte ist, dass ich gern Masm Befehle unter gcc 
verwenden würde, so dann man
mov rsi,ebp
mov rax,[rsi+rax*8] oder umgekehrt
mov qword ptr [rsi+rax*8],rdx etc. einfügen kann zum lesen 
schreiben/schreiben der Zwischenwerte in ein array of __int128.


M

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Zusatz:
> Ich sehe hier leider keine Möglichkeit, einen abgeschickten Thread zu
> ändern, oder habs übersehen.

Würd' ich auch oft gerne machen, um meine Schreibfehler, die ich gerne 
erst eine halbe Stunde später sehe, zu beseitigen.
Das Bearbeiten klapp aber leider nur für ein gewisse Zeit (halbe Stunde 
oder Stunde) und nur solange noch kein weiterer Beitrag ergänzt wurde.


> Was ich hinzufügen wollte ist, dass ich gern Masm Befehle unter gcc
> verwenden würde, so dann man
> mov rsi,ebp
> mov rax,[rsi+rax*8] oder umgekehrt
> mov qword ptr [rsi+rax*8],rdx etc. einfügen kann zum lesen
> schreiben/schreiben der Zwischenwerte in ein array of __int128.

Vermutlich wirst Du diebezüglich am Inlie-Asssembler nichts drehen 
können.
Mit separten Assembler-Dateien und GAS könne vielleicht was gehen:
https://en.wikibooks.org/wiki/X86_Assembly/GAS_Syntax
"The AT&T syntax is the standard on Unix-like systems but some 
assemblers use the Intel syntax, or can, like GAS itself, accept both."

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> für den skylake ist gibts ein extra target in 6.1.0 ...
>
> https://gmplib.org/list-archives/gmp-devel/2015-August/004101.html
>
> möglicherweise wäre es sinnvoll statt mpz-funktionen die mpn varianten
> zu probieren.

Wenn ich das ichtig verstehe, wurde dieMP aber nicht speziell fpr den 
skylake getunt, der Code funktioniert auf syklake nur gut.
Wenn ich mir die unterstützen x86 CPU-Typen anschaue, scheint mit AMD64 
das "schärfste zu sein, was man zum Optimieren einsetzen kann.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
OK,
Das korrekte include war #include <../../../usr/include/gmpxx.h> ;)
mit der Version aus 
Beitrag "Re: 128 Bit Risc"
habe ich in 18 minuten PR #52 erreicht!
Und der Ansatz mit dem verteilen auf mehrere cores/threads ist noch gar 
nicht eingesetzt.

An sich würde ich gern mit freepascal und masm arbeiten.
Dieses gas schau ich mal an.
thx

von rmu (Gast)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> OK,
> Das korrekte include war #include <../../../usr/include/gmpxx.h> ;)
> mit der Version aus
> Beitrag "Re: 128 Bit Risc"
> habe ich in 18 minuten PR #52 erreicht!
> Und der Ansatz mit dem verteilen auf mehrere cores/threads ist noch gar
> nicht eingesetzt.
>
> An sich würde ich gern mit freepascal und masm arbeiten.
> Dieses gas schau ich mal an.
> thx

was spricht gegen #include <gmpxx.h> ?

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Faktor 2,7 gegenüber meiner Mühle - war zu erwarten.
Wie schaut's im Vergleich zur Assembler-Version aus?

: Bearbeitet durch User
von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
wir haben grad gemessen
auf einem core #53 in 4 min 44

dh wir sind mit reinem asm um etwa faktor 3 schneller
(beides läuft auf derselben maschine)

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> matthias schrieb:
>> In line 4 des collatz.cpp steht #include "..\gmp\include\gmp.h"
>> Kann ja gar nich gehen, denn das waere ja unter \home\gmp und das gibts
>> nicht.
>
> dass #include "..\gmp\include\gmp.h" anzupassen ist, hab' ich schon viel
> weiter oben angemerkt. Wo das apt-get die GMP hinplaziert, kann ich Dir
> nicht sagen - ich arbeite noch nicht auf Linux, sondern in diesem Fall
> mit MinGW/TDM-GCC.

der include ist schlicht
1
#include<gmp.h>

debian ist nicht so mein, aber das packet das du da installiert hast 
sollte schon passen..

U.G. L. schrieb:
> Faktor 2,7 gegenüber meiner Mühle - war zu erwarten.
> Wie schaut's im Vergleich zur Assembler-Version aus?

nicht ganz ein faktor 2 wenn ich mich richtig erinnere...
wobei das gegen deine 1. version war...

73

matthias schrieb:
> An sich würde ich gern mit freepascal und masm arbeiten.
> Dieses gas schau ich mal an.
> thx

unter linux ist sonst noch nasm weit verbreitet...

ich würde bei c bleiben... der gcc mit allem drumrum ist drauf getrimmt 
c und asm zu mischen... (inline sowie externe asm files)

73

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Deutlich mehr, als ich erwartet hätte!

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
ich nehme an, dass das der overhead gegenüber den low-level funktion in 
der gmp ist von denen die docu spricht...

immerhin müssen die gmp funktionen das vorzeichen beachten... das ist in 
der asm version nicht so oder?

73

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
ja stimmt wir nehmen alle werte als unsigned

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Vermutlich wird die Verwaltung der notwendigen Variablenbreite 
aufwendiger sein, als von mir eingeschätzt.

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
ich habs aktuell so, dass ich den startwert auf 64bit gegrenze und die 
folgen bis 128bit laufen können genau wie die path records. ich werd mal 
sehen dass ich mal auf 3x64bit raufgehe und gucke was das bzgl. der 
lauftzeit ausmacht. mehr werden wir dann nicht brauchen denk ich.

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
rmu schrieb:
> was spricht gegen #include <gmpxx.h> ?

ja richtig geht auch. Ich kenn von php, dass man set_include_path 
explizit angibt.
Tx

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Markus K. schrieb:
> Das ist aber keine Vektorisierung. Mit Vektorisierung ist gemeint, dass
> man die SIMD-Befehle der CPU benutzt um die Berechnungen zu machen. Aber
> wie Matthias schon ganz am Anfang geschrieben hat, fehlt den
> SIMD-Befehlen das Carry-Flag, d.h. man kann sich aus einer
> 64Bit-Addition keine 256Bit Addition zusammenbasteln.

Man kann den 64 bit overflow bei addition ohne carry bit erkennen, wenn 
(unsigned) vpaddq a,b,c < max(a,b) ist. (add c,2^64 if c below a or b).
Wenn man nun weiter xmm register betrachten/benutzen will, die Simd 
funtionaltät ignorierend.

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Markus K. schrieb:
>> Das ist aber keine Vektorisierung. Mit Vektorisierung ist gemeint, dass
>> man die SIMD-Befehle der CPU benutzt um die Berechnungen zu machen. Aber
>> wie Matthias schon ganz am Anfang geschrieben hat, fehlt den
>> SIMD-Befehlen das Carry-Flag, d.h. man kann sich aus einer
>> 64Bit-Addition keine 256Bit Addition zusammenbasteln.
>
> Man kann den 64 bit overflow bei addition ohne carry bit erkennen, wenn
> (unsigned) vpaddq a,b,c < max(a,b) ist. (add c,2^64 if c below a or b).

Das kannte ich sogar, aber ich hatte es ignoriert, weil nicht glaube, 
dass das schneller ist. Man braucht dann ja zusätzlich zwei Vergleiche 
und die SSE/AVX-Vergleiche liefern als Ergebnis entweder alle Bits 1 
oder 0. Man muss dann noch jeweils ein AND 1 machen um daraus eine 1 
oder 0 zu machen. Dann die beiden Carry-Bits Verodern und dann als extra 
Addition zu den oben 64Bit dazuzählen. Sind 6 zusätzliche Befehle, damit 
man 4 Additionen parallel machen kann.

: Bearbeitet durch User
von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
eine Version mit 3x64 Arithmetik braucht ungefähr 25% mehr Rechenzeit - 
was grössenordnungsmässig der Erwartung entspricht.

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Ich würde mir keinen pathrecord merken wollen, sonder nur durch gesetzte
> Bits auf X116 und X117 feststellen wollen, das der pathrecord
> "angekratzt" wurde, schon gar nicht weitere Sachen merken, weil das in
> einem FPGA zu teuer ist.

Das denke ich ist der richtige Ansatz. Man baut eine FPGA Maschine, die 
Kandidaten ausspuckt, und sortiert mit einer CPU nach bzw. kann es sich 
dort dann leisten, die kandidaten ganz klassisch durchzurechnen. Wenn 
man spezielle Versionen für spezielle Bereiche macht, weiss man vorher, 
auf die Überschreitung welcher bitgrenze man triggern muss und kann dann 
aufhören.

Das würde sogar sinn machen für die jetztige ASM version, es würde dort 
die kaskaden von vergleichen sparen. ggf. kann man also einen Prototyp 
dessen auch für die CPU in assembler schreiben. vielleicht würde es auch 
sinn machen, den verleich mit dem stoppwert ähnlich simpel zu stricken, 
lieber mal ein paar folgeglieder mehr berechnen und erst stoppen, wenn 
eine bestimmte bitzahl unterschritten wird.

viel stoff zum nachdenken :)
einen schönen weg ins WE wünscht

gonz

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> ich gehe eigentlich davon aus, dass das FPGA wenigstens reste_amount ==
> 116 Einheiten enthält!

Ok, und das geht (ich kann die zahlen nicht beurteilen) in die richtung. 
Wir haben aktuell also mit CPU einen Faktor von gefühlt 20-30 mehr in 
der Taktrate, und schaffen einen parallelisierung auf 50 kerne (mehr 
wäre natürlich möglich, aber dazu müsste man ein projekt zum verteilten 
rechnen starten und dürfte nicht nur die server nehmen die wir eben so 
über haben). das würde heissen, dass das etwa der Rechenleistung von 10 
FPGA entspräche. Der Vorteil einer FPGA Lösung wäre dann nur, dass man 
diese einfacher und preisgünstiger clustern kann als ganze CPUs mit 
ihrem drumherum. Denkt man an ein Array von zB 64 FPGA (dh wir bräuchten 
einen Sponsor und es wäre ein Projekt das in Hardware aufzubauen) hätten 
wir mit Glück eine 10er Potenz gegenüber der CPU basierten Lösung 
gewonnen.

Liege ich da richtig? ich vergreife mich immer mal gerne bei so zahlen * 
schmunzel

Es würde aber m.E. dies rechtfertigen, mal genauer zu gucken wie weit 
man da kommt, also die zahlen in obiger abschätzung genauer zu wissen.

von matthias (Gast)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Andreas R. schrieb:
> Hab als Ziel so ein cyclone 2 minimum dev board genommen, wie man es für
> unter 15,- bei ebay bekommt.

ich fand das bei ebay:

Ebay-Artikel Nr. 172328261937

Hast du mit diesem oder so einem ähnlichen da echt deine collatz.v Code 
implementiert? Wie wird das angeschlossenen, mit parallel 
Schnittstelle?, usb sehe ich da nicht.
Ist es nur zum Programmieren oder läuft das auch als Simulation?
Und die Sprache ist Vdhl in deinem collatz.v? Sorry Anfänger Fragen, 
aber  wenn das so preiswert ist lege ich s mir zu.
Ist so ein Board für Anfänger nicht so geeignet sondern ein sog. 
eval-board besser? Welches?
Thx
M

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Wie wird das angeschlossenen, mit parallel
> Schnittstelle?,

wenn es sowas komfortables wie usb etc nicht gibt, wäre es vielleicht 
sinnig, ne art konzentrator zwischenzuschalten, also einfach nen board 
nach wahl zu nehmen, das auf der einen seite ethernet oder usb oder... 
unterstützt und am pc hängt, und auf der anderen seite via IO mit den 
FPGAs kommuniziert. Im Prinzip könnte man die Werte ja problemlos über 
sowas wie nen I2C morsen oder ne parallele schnittstelle und für jeden 
FPGA ne select leitung spendieren... an der stelle müssen wir ja nicht 
wirklich schnell sein. (wobei ich mich da an gute alte 
hardware-architekturen erinnere ggg)

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> vielleicht würde es auch
> sinn machen, den verleich mit dem stoppwert ähnlich simpel zu stricken,
> lieber mal ein paar folgeglieder mehr berechnen und erst stoppen, wenn
> eine bestimmte bitzahl unterschritten wird.

Das war das, was ich mit "keines der Bits X59 bis X117 gestetzt ist"
gemient habe 
Beitrag "Re: 128 Bit Risc"
Man müsste den Folgewert dann auf 0x0800.0000.0000.0000 bringen.
Man müsste mit einem C-Porgramm ermitteln, wieviele Takte im 
Durchschnitt mehr invesiert werden müssen - verdoppelt sich die 
Taktzahl, wird man besser doch den "64plus-Vergleicher" 
Beitrag "Re: 128 Bit Risc" 
einbauen, da der dann doch weniger kostet wie eine weitere Maschine

: Bearbeitet durch User
von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Ok, hier noch ein paar zahlen. verzichten wir auf den faktor 3 in der 
basis
bekommen wir:

58 aus 1024 gleich 5.664% (basis 2^10)
113 aus 2048 gleich 5.518%(basis 2^11)
195 aus 4096 gleich 4.761% (basis 2^12)
313 aus 8192 gleich 3.821% (basis 2^13)
619 aus 16384 gleich 3.778% (basis 2^14)
1086 aus 32768 gleich 3.314% (basis 2^15)

natürlich könnte man die Reste auch auf mehrere FPGA verteilen.

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Man müsste mit einem C-Porgramm ermitteln, wieviele Takte im
> Durchschnitt mehr invesiert werden müssen - verdoppelt sich die

ok das kann ich mir mal auf die fahnen schreiben. ich hab eh vor mal ne 
version zu schreiben die nen paar statische werte aufsummier (und 
entsprechend langsamer läuft - egal) damit könnte man sowas austesten. 
wenn jemand anders mag gerne - ich komme wahrscheinlich erst in den 
nächsten tagen dazu....

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> hätten
> wir mit Glück eine 10er Potenz gegenüber der CPU basierten Lösung
> gewonnen.

Faktor 10 war da auch das, was ich als machbar angesehen habe.
Angesichts der tollen Beiträge von cyrix ist das aber verdammt 
ambitioniert!
Wenn man so ein Projekt angeht, muss man durchaus einkalkulieren, dass 
vielleicht nur ein Faktor von eins, zwei oder drei rauskommt!

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Der einzige Vorteil wäre, dass man know-how und hardware hätte, die man 
prinzipiell an verbesserte algos anpassen könnte und die auch für andere 
zahlentheoretisch orientiere aufgabenstellungen brauchbar wäre. (ok, in 
begrenztem maße). also im prinzip müsste man damit rechnen, dass man es 
eigentlich macht, um es mal gemacht zu haben grins

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:

> 
Ebay-Artikel Nr. 172328261937

Das Board hat eine USB-Entwicklungsschnittstelle, vermutlich wird die 
aber keinen Kanal für die "Anwenderkommunikation" zur Verfügung stellen.

Die Anzahl der LUTs/LEs wird nur für ca. 10 Maschaschinen reichen.

Ich gehe davon aus, dass damit keine 100MHz zu erreichen sind, denn die 
300MHz werden wohl erreicht, wenn der Registerausgang direkt auf die 
eigene LUT zurückgeführt wird - bei dem anvisierten Design werden aber 
doch einige Stufen in der Loop mehr vorhanden sein.

Die LEs des Bausteins haben aber auf jeden Fall mal eine "Carry-Chain", 
ohne die das Erreichen einer brauchbaren Taktfrequenz bei einem 
80-128bittigem Adder wohl ilusorisch ist. Ob so eine "Carry-Chain" aber 
ausreicht, um eine brauchbare Taktfrequenz zu erreichen, kann ich Euch 
nicht sagen - dazu müssen sich andere FPGAler äußern, die Erfahrungen 
mit aktuellen Bausteinen haben (meine Erfahrungen mit FPGAs liegen lange 
zurück).

In meinen Augen braucht Ihr aber jetzt kein Board.
Man müsste nur wissen, welches Board man letztendlich einsetzen könnte,
falls das "Spielen" mit der zugehörigen Entwicklungsumgebung 
"ermunternd"
ist (der Zeit- und Kostenaufwand einer Eigenentwicklung kann man sich, 
glaub'ich, abschminken - da kauft ihr besser Skylakes und lasst sie 
sofort rechnen!).

Vielleicht findet Ihr ja kostengünstig auf ebay sowas
https://www.enterpoint.co.uk/shop/home/106-merrick-6.html
https://www.enterpoint.co.uk/shop/home/98-merrick-3.html
oder gar sowas :-)
https://www.enterpoint.co.uk/shop/home/13-merrick1.html

(wobei ich jetzt noch nicht geprüft habe, ob die verwendeten FPGAs für 
diese Anwendung tauglich sind)

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Man müsste nur wissen, welches Board man letztendlich einsetzen könnte,
> falls das "Spielen" mit der zugehörigen Entwicklungsumgebung
> "ermunternd" ist

nochmal an die mitlesend FPGAler - hat jemand ein passendes Board im 
Sinn, dass geeignet wäre - PCIe/USB/oder Ethernetanschluss, ein oder 
besser mehrere FPGAs mit 100k+ LUTs/LEs und Bausteinen mit 
"Carry-Chain"?

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Und vielleicht mal periodisch ebay nach "FPGA PCIe" und
"FPGA accelerator" absuchen :-)

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Ach ja - jetzt kommt mir noch ein wichtiger Gedanke - gerade für die für 
Euch interessanten größeren FPGAs gibt es nicht umgedingt auch 
kostenlose Entwicklungsumgebungen!!!

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Erste Ergebnisse aus der Statistik:

die werte konvergieren recht fix, es ist das verhältniss

(3x+1)/2 Schritte zu /2 Schritte: 1,45
Schritte insgesamt pro Folge im Mittel : 24,02

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Das lohnt vielleicht, mal näher betrachtet zu werden:
Ebay-Artikel Nr. 272417191446

mit PCIe-Anschluss!

Leider nicht im Text beschrieben, ob mit XC5VLX220T oder XC5VLX330T 
bestückt,
entsprechend wären knapp 35000 oder gut 50000 "Slices" verfügbar.
Ein Slice enthält "Four function generators, Four storage elements, 
Arithmetic logic gates, Large multiplexers, Fast carry look-ahead 
chain".
U.U. können auch die 128/196 DSP slices eingebaut werden.

Ein komplexes Teil (so wie es aussieht mit eigenem Stromanschluss!!!) - 
ein Teil, mit dem man gut 100 "Maschinen" u.U. realisieren kann!?

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
auch im interessanten Zahlenbereich?

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
also die 24 Schritte, waren die im #87-Zahlenbereich?

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Und eigentlich müssen wir nicht die durchschnittliche Schrittzahl 
wissen,
sondern die Schrittzahl, bei der 99% und 99,9% unter Startwert bzw. 
0x0800.0000.0000.0000 gelangen?

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Also ich hahe es  geschafft, eine 3x+1 Operationn über die 64 bit Grenze 
zu schreiben durch 2 additionen dann noch +1.
Leider gelingt es nicht, ein shift right eines ganzen 128 bit words um 1 
bit zu machen.
oder weiss jemnand wie man die das umgehen könnte?

VPSRLDQ xmm1, xmm2, imm8 denkt man würde das machen abert tuts nicht 
shifted nur quadwords.

also etwa 0x00.00.00.01.B2.A0.C1.00 1 oder 2 bit nach rechts shiften?
Hat herr intel nicht vorgesehn. Man kann höchstens das 128 bit xmm word 
splitten und die qword getrennt betrachten. dann wären wir aber bei der 
64 bit implementation von gonz.
Die xmm bzw ymm256 Bit  sind nicht geeignet für was ich/wir wollen.
Wie gesagt eine simple 128 bit addier machine würde reichen, wobei es 
mir anfänglich gar nicht so um Zeit geht.
M

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
Mittlerweile gibts auch schon FPGAs in der Wolke:
https://aws.amazon.com/de/ec2/instance-types/f1/

Von den Daten her sind es Xilinx Virtex Ultrascale+ XCVU9P (2.5 Mio 
System Logic Cells, 6840 DSP Slices, 345Mb RAM)

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Also das cyclone 2 Board hab ich hier (bekommst auch für die Hälfte vom 
obigen ebay Link) und dann noch ein de0 Nano Board:

http://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&No=593

Leider sind wir bei beiden recht weit weg von 100k+ LEs... ;-(

Wenn ihr Speicher zum Beschleunigen braucht, fallen mir noch die Mimas 
Boards ein:

http://numato.com/mimas-v2-spartan-6-fpga-development-board-with-ddr-sdram/

Das nehmen ja die J-Core Leute um den Linux Kernel drauf laufen zu 
lassen.

Aber braucht ihr echt 100k+ LEs? Wäre es ggf nicht günstiger z.B. 4 
Boards mit je 25k LEs zu verwenden und die Aufgaben auf diese Boards zu 
verteilen?

von Peter Schulz (Gast)


Bewertung
0 lesenswert
nicht lesenswert
unabhängig von der zu beschreitenden Lernkurve würde ich für diese 
Problemstellung das ZYBO-Board von Digilent vorschlagen: dort ist ein 
Xilinx Zynq verbaut. Dabei handelt es sich um einen dual-core ARM 
Prozessor mit "angebautem" FPGA-Teil.

So wie ich die Problematik verstanden habe, spielen bei der 
Datenübertragung Latenz und Bandbreite eine Rolle. Genau hier kann eine 
Zynq-basierte Lösung punkten. Das vorgeschlagene Konzept wäre also:

Auf dem ARM-Teil des Zynq läuft unter Linux ein Hauptprogramm von dem 
aus die 128-bit/256-bit-Operanden und -Ergebnisse ultraschnell (denn es 
läuft ja alles auf EINEM Chip) mit einem 128-bit/256-bit Co-Prozessor im 
FPGA-Teil ausgetauscht werden. Das Board hat Ethernet, so dass man von 
einem PC aus remote arbeiten kann.

Das ist alles nicht so einfach zu erlernen aber ich denke, das wäre die 
passende Plattform.

Gruss

Peter Schulz

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Andreas R. schrieb:
> Aber braucht ihr echt 100k+ LEs? Wäre es ggf nicht günstiger z.B. 4
> Boards mit je 25k LEs zu verwenden und die Aufgaben auf diese Boards zu
> verteilen?

Wenn man es als Kosten-Nutzen-Rechnung betrachtet, und wir eh mehr als 
einen FPGA einsetzen würden (zumindest perspektivisch), dann wäre das 
natürlich ein Rechenexemple. Wenn man nur die Kosten der Bauteile 
betrachtet wäre dann wahrscheinlich eine 4x25k Lösung günstiger als eine 
1x100k. Tatsächlich muss das dann aber auch jemand zusammenbauen etc...

Es gab ja auch schon den Vorschlag, einfach eine Farm an möglichst 
günstigen CPU Boards per Ethernet zusammenzuschalten. Wenn man nicht auf 
die Stromrechnung guckt wäre das wohl die günstigste Variante um an 
Rechenleistung zu kommen...

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
Peter Schulz schrieb:
> ZYBO-Board von Digilent

Dann könnte man dort mal anfragen was denn für eine "produktiv-version" 
16  solcher boards in "nackt" ohne das development kit drumrum kosten 
würden :) und einen Sponsor suchen (ernstgemeint). Wobei - wenn man die 
über ethernet koppelt, könnte man sie auch über WWW koppeln. Dh man 
könnte sich auch vorstellen, lauter kleine Boxen auf der Basis zu bauen, 
für die dann "Stellplätze" mit Strom- und Webanschluss gesucht werden * 
schmunzel

Was man ja dann auch für andere Berechnungen gut verwenden könnte (ich 
denke da immer noch an vormalige Aufgaben aus den Al-Zimmerman 
Contests...

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Korrektur Link zweites Board: 
Ebay-Artikel Nr. 272337657073


Dieses Board enthält ein zweites FPGA XC5VFX100T (vermutlich auch -1),
das primär zur Realisierung des PCIe Interfaces dient, läßt sich aber
u.U. dazu benutzen, weitere Maschinen zu realisieren. Bei dem Board
mit dem XC5VLX220T oder XC5VLX330T müsste das genauso sein.

aus ds202:
16-bit Adder 550/500/450MHz
32-bit Adder 550/500/447MHz
64-bit Adder 423/377/323MHz
die 150MHz für eine 80bit/128bit Maschine scheinen mir erreichbar



aus https://www.xilinx.com/support/documentation/user_guides/ug190.pdf
1
              LUTs     FFs
2
XC5VFX100T  64,000  64,000
3
XC5VLX220T 138,240 138,240
4
XC5VLX330T 207,360 207,360
und - das sind LUTs mit 6 Eingängen (statt der ältern LUTs mit nur
4 Eingängen)!!! statt einer LUT mit 6 Eingängen und einem Ausgang
kann man die LUT auch als zwei LUTs mit 5 Eingängen und 2 Ausgängen
 konfigurieren!!!

Damit ließe sich z.B. eine Maschine mit den Operationen (3X+1)/2,
SHR1, SHR2 und LOAD realisieren, ohne extra LUTs für den Shifter
auszugeben, der könnte in Multiplexer mit intergriert werden!

Da ergibt sich dann schon wieder eine Aufgabe für die MPler - wie
oft haben wir den Fall, das nach einer (3X+1)/2-Operation ein Shift1,
ein Shift2, ein Shift3, ein Shift4, ...ausgeführt wird - u.U. lohnt
es gar nicht, mehr als eine SHR2-Operation zu integrieren, weil
SHR3, SHR4 ... zu selten benötugt werden.

von Eukrott V. (gonzens)


Bewertung
1 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> wir haben grad gemessen
> auf einem core #53 in 4 min 44

ok also - nachdem ich verstanden habe dass gar nicht das rumrechnen 
"kostet" sondern das springen - hier eine version bei der (3x+1)/2 und 
/2 in demselben konstrukt behandelt werden:

// r9,r13 : aktueller Folgewert (niederwertig...hoeherwertig)
// r10,r14 : dessen haelfte fuer (3x+1)/2 schritt
// r11,r15 : record (wird mitgefuehrt, ursprungswert geht verloren)
// rax : null (da komischerweise cmovnc nicht mit konstante geht)

// auf gehts! lets do the collatz ...
  "collatz_start: \n\t"
// wir erzeugen auf r10,14 eine kopie des aktuellen wertes
  "MOV %r13,%r14 \n\t"
  "MOV %r9,%r10 \n\t"
// und halbieren diese schon einmal (brauchen wir fuer beide faelle)
  "SHR $1,%r14 \n\t"   // shr+rcr rotiert ueber und in das carry
  "RCR $1,%r10 \n\t"
// aus dem Carry kann man jetzt entnehmen ob gerade oder ungerade
// wenn der gerade fall loeschen wir den bisherigen Folgenwert
  "CMOVNC %rax,%r13 \n\t"
  "CMOVNC %rax,%r9 \n\t"
// fuer "ungerade": carry is set, auf r9,13 der bisherige wert
// fuer "gerade": carry clear und r9/13 geloescht :)
  "ADC %r10,%r9 \n\t"   addieren uebers/mit dem carry
  "ADC %r14,%r13 \n\t"
// habe fertig: auf 9,13 steht jetzt der neue folgewert.

das bringt ungefaehr 30%, ich komme jetzt auf einem kern zur #53 in 3 
min 21 und kann auf der 12-kern maschine das Leavens&Vermeulen Programm 
(bis #63 bei Roosendaal) in einer Stunde erledigen * smile

have fun!
gonz

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Anfrage beim ebay-Verkäufer, ob das Board XC5VLX220T oder XC5VLX330T
enthält, läuft - und auch, ob die Boards nackt kommen oder mit der
ursprünglich mitgelieferten  Doku und Software (z.B: dem notwendigen
PCIe-Core für den XC5VFX100T) geliefert werden.

Vielleicht kann einer von den MP-lern bei Nallatech nachfragen,
ob die für mehrere nackte Boards und für so ein Projekt
gegebenenfalls die Doku und Software zur Verfügung stellen
(aber nicht den Link verraten - die Kaufen sonst bei dem Preis
die Boards glatt selber zurück :-).

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Als Sponsoren kommen sicherlich nur Intel/Altera, Xilinx
Lattice, also die Anbieter von solchen FPGAs und deren
Distributoren infrage - dort könnt Ihr mal diesbezüglich
nachfragen.
U.U. stellen die sogar ein wenig Manpower/Knowhox für
die Implementierung der Maschinen zur Verfügung!?

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> ok also - nachdem ich verstanden habe dass gar nicht das rumrechnen
> "kostet" sondern das springen - hier eine version bei der (3x+1)/2 und
> /2 in demselben konstrukt behandelt werden:

Schon über die Realisierungsmöglichkeit einer Version
nachgedacht, die ohne diesbezügliche Entscheidungen
auskommt?
Also immer abwechselnd eine (3X+1)-Operation, dann ein
Count_Trailing_Zeros (bzw.BitScanForward1) und einem
entsprechenden ShiftRight um n Stellen (man kann wohl
darauf verzichten, hier mehr als 64 trailing zeros
einzukalkulieren).

Dann könnte man noch darüber nachdenken, ob sich ein
Unfold der Loop machen läßt - also in einer Schleife
gleiche mehrere UP/DOWNs realisiert.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Und berechnet Ihr eigentlich für jede Kette deren eigenen
Rekordwert und verfolgt sie bis zu einem Wert kleiner dem
Startwert oder vergleicht ihr wie bei meiner GMP-Implementierung
den aktuellen Wert auch mit dem aktuellen "globalen" Rekordwert?

Wenn eine Kette den bisherigen Rekordwert erreicht hat,
kann abgebrochen werden - das brachte, wenn ich mich recht
entsinne, auch wieder 25% - klar, die Kette muss dann
erst gar nicht mehr wieder bis unter den Startwert
verfolgt werden.
1
 
2
0: n=27 r=9232 c=77
3
:  n=31 x=9232 r=9232
4
:  n=63 x=9232 r=9232
5
:  n=91 x=9232 r=9232
6
:  n=103 x=9232 r=9232
7
:  n=111 x=9232 r=9232
8
:  n=159 x=9232 r=9232
9
0: n=255 r=13120 c=15
10
0: n=447 r=39364 c=53
11
:  n=511 x=39364 r=39364
12
0: n=639 r=41524 c=25
13
0: n=703 r=250504 c=82
14
0: n=1819 r=1276936 c=50
15
:  n=2047 x=1276936 r=1276936
16
:  n=4095 x=1276936 r=1276936
17
0: n=4255 r=6810136 c=85
18
0: n=4591 r=8153620 c=59
19
0: n=9663 r=27114424 c=48
20
:  n=17179 x=27114424 r=27114424
21
0: n=20895 r=50143264 c=87
22
0: n=26623 r=106358020 c=63
23
0: n=31911 r=121012864 c=76
24
:  n=50427 x=121012864 r=121012864
25
:  n=53851 x=121012864 r=121012864
26
:  n=56731 x=121012864 r=121012864
27
:  n=60583 x=121012864 r=121012864
28
0: n=60975 r=593279152 c=116
29
:  n=69535 x=593279152 r=593279152
30
0: n=77671 r=1570824736 c=71
31
0: n=113383 r=2482111348 c=120
32
0: n=138367 r=2798323360 c=71
33
0: n=159487 r=17202377752 c=66
34
0: n=270271 r=24648077896 c=211
35
:  n=288615 x=24648077896 r=24648077896
36
:  n=487039 x=24648077896 r=24648077896
37
0: n=665215 r=52483285312 c=144
38
0: n=704511 r=56991483520 c=69
39
0: n=1042431 r=90239155648 c=224
40
:  n=1126015 x=90239155648 r=90239155648
41
0: n=1212415 r=139646736808 c=84
42
0: n=1441407 r=151629574372 c=141
43
0: n=1875711 r=155904349696 c=131
44
0: n=1988859 r=156914378224 c=144
45
:  n=2237467 x=156914378224 r=156914378224
46
:  n=2517151 x=156914378224 r=156914378224
47
0: n=2643183 r=190459818484 c=201
48
0: n=2684647 r=352617812944 c=120
49
0: n=3041127 r=622717901620 c=78
50
0: n=3873535 r=858555169576 c=127
51
0: n=4637979 r=1318802294932 c=168
52
:  n=5217727 x=1318802294932 r=1318802294932
53
0: n=5656191 r=2412493616608 c=170
54
0: n=6416623 r=4799996945368 c=133
55
0: n=6631675 r=60342610919632 c=163
56
:  n=7460635 x=60342610919632 r=60342610919632
57
:  n=8393215 x=60342610919632 r=60342610919632
58
:  n=16786431 x=60342610919632 r=60342610919632
59
1: n=19638399 r=306296925203752 c=338
60
1: n=38595583 r=474637698851092 c=191
61
:  n=54213823 x=474637698851092 r=474637698851092
62
:  n=77191167 x=474637698851092 r=474637698851092
63
3: n=80049391 r=2185143829170100 c=164
64
:  n=93596391 x=2185143829170100 r=2185143829170100
65
:  n=101312511 x=2185143829170100 r=2185143829170100
66
5: n=120080895 r=3277901576118580 c=164
67
11: n=210964383 r=6404797161121264 c=275
68
:  n=219259131 x=6404797161121264 r=6404797161121264
69
:  n=222250543 x=6404797161121264 r=6404797161121264
70
:  n=246666523 x=6404797161121264 r=6404797161121264
71
:  n=277499839 x=6404797161121264 r=6404797161121264
72
:  n=300377023 x=6404797161121264 r=6404797161121264
73
19: n=319804831 r=1414236446719942480 c=167
74
:  n=639609663 x=1414236446719942480 r=1414236446719942480
75
:  n=1214258971 x=1414236446719942480 r=1414236446719942480
76
:  n=1366041343 x=1414236446719942480 r=1414236446719942480
77
89: n=1410123943 r=7125885122794452160 c=340
78
:  n=2379584155 x=7125885122794452160 r=7125885122794452160
79
:  n=2677032175 x=7125885122794452160 r=7125885122794452160^C

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
U.U. rechnet es sich sogar, zusätzlich auch auf den alten Rekordwert zu 
prüfen und ebenfalls abzubrechen?
Das Down bis zum Startwert dauert in diesen Fällen zwar nicht solange,
der alte Rekordwert wird dafür aber vermutlich wesentlich häufiger
erreicht.

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> Peter Schulz schrieb:
>> ZYBO-Board von Digilent
>
> Dann könnte man dort mal anfragen was denn für eine "produktiv-version"
> 16  solcher boards in "nackt" ohne das development kit drumrum kosten
> würden :)

mit "4,400 logic slices, each with four 6-input LUTs and 8 flip-flops"
kommt Ihr halt nicht weit!
Da dürften allein die kleinen 4 gebrauchten Boards 
(Ebay-Artikel Nr. 272337657073), 
grob zum Preis eines ZYBO-Boards, wesentlich mehr bringen!

Wenn sich nicht ein Sponsor unter den FPGA-Herstellern/Distributoren
auftut und sichergestellt werden kann, dass neben den nackten Boards
auch die nowendige Doku und Software zu bekommen ist, sehe ich
eigentlich die neun gebrauchen Boards als "alternativlos" an :-)

Auf den Boards sind FPGAs verbaut, die vor fünf Jahren vermutlich
mehr als 3000/4000EUR, u.U. sogar teilweise mehr als 10000EUR
gekostet haben!!!

: Bearbeitet durch User
von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
Falls es ein aktuelles neues Board sein soll:
https://shop.trenz-electronic.de/de/TE0725-03-100-2I9-Artix-7-100T-FPGA-Modul-mit-Xilinx-XC7A100T-2CSG324I-2-x-50-Pin-ind.temp.range?c=131

Das hat allerdings wieder kein Ethernet usw. Da müsste man das halt mit 
einem anderen Board (zB dem oben genannten Zybo) koppeln.

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Und berechnet Ihr eigentlich für jede Kette deren eigenen
> Rekordwert und verfolgt sie bis zu einem Wert kleiner dem
> Startwert oder vergleicht ihr wie bei meiner GMP-Implementierung
> den aktuellen Wert auch mit dem aktuellen "globalen" Rekordwert?

ich mach es so dass ich den globalen recordwert beim einstieg in die 
collatz routine, die eine Kette durchrechnet, mitgebe, und mit diesem 
nach jedem (up-schritt) vergleiche. Wenn man beim überschreiten gleich 
abbricht, dann muss man nachträglich prüfen, ob die folge nicht im 
weiteren verlauf noch einen höheren wert erzeugt, deshalb lasse ich sie 
weiterlaufen bis zum stopwert und überschreibe den globalen record ggf. 
mehrmals mit einem jeweils höheren wert. dass abbrechen hier 25% bringt 
glaube ich nicht, ggf. kann die folge ja auch erstmal wieder sinken, 
aber vor erreichen des stopwertes dann wieder ansteigen bis zu einem 
höheren wert, sodass man sie zumindest soweit durchrechnen muss bis sie 
auf einen schon betrachteten Startwert anlandet.

U.G. L. schrieb:
> Dann könnte man noch darüber nachdenken, ob sich ein
> Unfold der Loop machen läßt - also in einer Schleife
> gleiche mehrere UP/DOWNs realisiert.

das habe ich nicht, es wurde aber in C gemacht. man kann dann für eine 
bestimmte anzahl von schritten vorab berechnen, welchen faktor/summanden 
man erhält für jede mögliche folge von up/dn, und diese dann aus einer 
tabelle abgreifen. zu beachten ist dabei natürlich auch, dass ggf. in 
einem zwischenschritt der record überschritten und danach wieder 
unterschritten wird genauso mit dem stopwert, dh. man muss entsprechende 
"Sicherheitsabstände" einbauen, oder eben zB "Candidate Records" 
auswerfen, wenn man hinreichend dicht (aber weniger als der mögliche 
Überschwung in einem multistep) an den record herangekommen ist.

ich weiss noch nicht, ob es sinn macht, den algo der da in C realisiert 
wurde, in asm nachzubauen.

U.G. L. schrieb:
> Schon über die Realisierungsmöglichkeit einer Version
> nachgedacht, die ohne diesbezügliche Entscheidungen
> auskommt?

nachdenken ständig, siehe mein erster anlauf beide zweige ineinander zu 
verschachteln. das ist aber sicher noch nicht das optimum was ich da 
herausgeholt habe...

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Markus K. schrieb:
> Falls es ein aktuelles neues Board sein soll:
> 
https://shop.trenz-electronic.de/de/TE0725-03-100-2I9-Artix-7-100T-FPGA-Modul-mit-Xilinx-XC7A100T-2CSG324I-2-x-50-Pin-ind.temp.range?c=131
>
> Das hat allerdings wieder kein Ethernet usw. Da müsste man das halt mit
> einem anderen Board (zB dem oben genannten Zybo) koppeln.

101,440LCs / 15,850Slices - ohne jetzt die Details analysiert zu haben
könnte ich mir vorstellen, das damit was möglich ist, was gegen die
neun Boards "anstinken" kann - allerdings nicht vom Preis her.
Vorteil natürlich, dass diese Boards in beliebiger Stückzahl kaufbar
sind!

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Ethernet evtl selbst nachrüsten per Software?

http://fpga4fun.com/10BASE-T0.html

Dann mal hier die 1. Antwort anschauen:

http://electronics.stackexchange.com/questions/196914/verilog-synthesize-high-speed-leading-zero-count

Das könnte man auf trailing Zeros umbauen und im nächsten Schritt alle 
Nullen am Ende entfernen.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Andreas R. schrieb:
> Das könnte man auf trailing Zeros umbauen und im nächsten Schritt alle
> Nullen am Ende entfernen.

alle Nullen am Ende kannst Du nie in einem Takt entfernen, da das sehr 
viele werden können - um 50 Nullen entfernen zu können, muss der 
Multiplexer am Arbeitsregisterbiteingang 50 Eingänge breit sein - und 
dieses Features würde so gut wie nie benutzt - selbst ein 10bit Shift 
wird sehr, sehr selten sein. U.U. ist mit den, mit einer 6erLUT 
möglichen (und geschenkten) ShiftRight1- und ShiftRright2-Operationen 
schon das Optimum gefunden.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> Wenn man beim überschreiten gleich
> abbricht, dann muss man nachträglich prüfen, ob die folge nicht im
> weiteren verlauf noch einen höheren wert erzeugt

Ich prüfe, ob aktuellerWert >= bisherigerRekortwert ist, dann 
nachgeschaltet, ob aktuellerWert == bisherigerRekortwert - wenn dem
so ist, kann ich abbrechen (aus der Loop springen), weil ein bisheriger
Rekord keinen neuen Rekord ergeben kann - ist das nicht der Fall 
(aktuellerWert != bisherigerRekortwert), dann haben wir definitiv einen
neuen Rekord und können sofort den bisherigen überschreiben.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> dass abbrechen hier 25% bringt glaube ich nicht

ich bin mir ziemlich sicher, dass ich n=23035537407 dann statt in 913 
Sekunden erst nach mehr als 1300 Sekunden erreicht habe!
Der Laufzeitgewinn entsteht nicht bei der Berechnung der aktuellen 
Folge, sondern bei der Berechnung der Folgen von weiteren, höheren 
Startwerten,
die den neuen Rekord einstellen, aber nicht überbieten! Denn die alle 
müssen dann nicht zurück auf den jeweiligen Startwert iteriert werden.

Im Prinzip kann auf Gleichheit zu jedem bisher aufgetretenen Wert 
geprüft und abgebrochen werden, doch jeder Vergleich kostet natürlich 
auch und drum vermute ich schon, dass ein zusätzliches Prüfen auf den 
letzten Rekordwert sich nicht rechnet.

Der Vergleich aktuellerWert >= bisherigerRekortwert mit nachgeschaltetem
aktuellerWert == bisherigerRekortwert statt
aktuellerWert > bisherigerRekortwert rechnet sich aber immer,
da der ">="-Vergleich nicht länger dauert als der ">"-Vergleich und der 
nachgeschaltete Vergleich ja nur im Trefferfall Zeit kostet!

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
ich probiere es aus - klingt logisch :)

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> Im Prinzip kann auf Gleichheit zu jedem bisher aufgetretenen Wert
> geprüft und abgebrochen werden, doch jeder Vergleich kostet natürlich
> auch und drum vermute ich schon, dass ein zusätzliches Prüfen auf den
> letzten Rekordwert sich nicht rechnet.

aber man könnte es natürlich mal überprüfen.

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Und man könnte darüber nachdenken, ob es Werte gibt, bei denen sich 
Folgen gehäuft vereinigen und auf die dann eher ein zusätzliches 
Abprüfen sinnvoll ist.
Hab' nämlich den Eindruck, dass Silva damals nicht nur weitere Pfeile im 
Köcher hatte, sondern eine weitere Axt!
Substanzielle Verbesserung erscheinen mir nur möglich mit Techniken, die 
viele Folgen/Startwerte auf einmal tilgen.

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
matthias schrieb:
> Dieses gas schau ich mal an.

der GAS ist sicherlich der Assembler, der beim g++ bzw. gcc mit dabei 
ist!

von Eukrott V. (gonzens)


Bewertung
0 lesenswert
nicht lesenswert
U.G. L. schrieb:
> ich bin mir ziemlich sicher, dass ich n=23035537407 dann statt in 913
> Sekunden erst nach mehr als 1300 Sekunden erreicht habe!

ich habe folgendes probiert: ich zähle die fälle, in denen der bisherige 
pathrecord nochmal erreicht wird. das sind jedoch vergleichsweise sehr 
wenige fälle, zB. 6x zwischen Roosendaal #42 und #43. in diesem bereich 
werden jedoch mehrere millionen folgen durchgespielt. damit kann es 
eigentlich den von dir beschriebenen faktor durch diese prüfung nicht 
geben, kannst du das nochmal überprüfen?

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Eukrott V. schrieb:
> ich habe folgendes probiert: ich zähle die fälle, in denen der bisherige
> pathrecord nochmal erreicht wird. das sind jedoch vergleichsweise sehr
> wenige fälle, zB. 6x zwischen Roosendaal #42 und #43. in diesem bereich
> werden jedoch mehrere millionen folgen durchgespielt. damit kann es
> eigentlich den von dir beschriebenen faktor durch diese prüfung nicht
> geben, kannst du das nochmal überprüfen?

Ich hab' das Programm, im Prinzip eine inline-Version des Programms
von Beitrag "Re: 128 Bit Risc"
mit einer äußeren Loop, nochmal laufen lassen und es benötigt
tatsächlich wesentlich länger.

1
// g++ -Ofast coll.cpp -o coll -I ..\gmp\include\ -L ..\gmp\lib\ -lgmp 
2
3
#include <ctime>
4
#include <stdio.h>
5
#include "..\gmp\include\gmp.h"
6
7
int main(int argc, char **argv) {                             //[
8
static const unsigned int width = 4096;
9
static const unsigned int base_step = 3072;
10
static const unsigned int reste_amount = 116;
11
static unsigned int reste_loop = 0;
12
static const unsigned int reste[] =
13
{ 27,   31,   63,   91,  103,  111,  127,  159,  207,  231,  255,  283,
14
 303,  319,  327,  411,  415,  447,  463,  487,  495,  511,  543,  559, 
15
 603,  615,  639,  667,  679,  703,  751,  763,  795,  799,  831,  859, 
16
 871,  879,  927, 1023, 1051, 1071, 1087, 1095, 1135, 1179, 1183, 1191, 
17
1215, 1231, 1255, 1263, 1275, 1279, 1327, 1351, 1383, 1435, 1471, 1519, 
18
1563, 1567, 1627, 1639, 1647, 1663, 1695, 1767, 1791, 1819, 1855, 1863, 
19
1903, 1951, 1959, 1983, 2031, 2043, 2047, 2079, 2095, 2119, 2139, 2151, 
20
2175, 2203, 2215, 2239, 2287, 2299, 2331, 2367, 2407, 2463, 2511, 2535, 
21
2559, 2587, 2607, 2671, 2715, 2719, 2727, 2751, 2791, 2799, 2811, 2815, 
22
2847, 2887, 2907, 2919, 2983, 3007, 3055, 3067};
23
static char timstr[10];
24
static mpz_t b, n, r, x, l;
25
time_t stt, now; 
26
double sec;
27
unsigned int cnt, c, u;
28
int i;
29
30
  mpz_init2(b, width); 
31
  mpz_init2(n, width);                          
32
  mpz_init2(r, width);
33
  mpz_init2(x, width);
34
  mpz_init2(l, width);  
35
  mpz_set_ui(n, 1);
36
  mpz_set_ui(r, 1);
37
  stt = time(0);
38
  
39
  while (1) {
40
    mpz_add_ui(n, b, reste[reste_loop++]);
41
    if (reste_loop >= reste_amount) { 
42
      reste_loop = 0;
43
      mpz_add_ui(b, b, base_step);
44
    }
45
    mpz_set(x, n);
46
    mpz_set(l, n); 
47
    cnt = 0;
48
    c = 0;
49
    do {
50
      mpz_mul_ui(x, x, 3);
51
      mpz_add_ui(x, x, 1);
52
      cnt++;
53
      if ((i = mpz_cmp(x, l)) > 0) {
54
        mpz_set(l, x);
55
        c = cnt;
56
      }
57
      u = mpz_scan1(x, 0);
58
      mpz_tdiv_q_2exp (x, x, u);
59
      cnt += u;
60
    } while ((i = mpz_cmp(x, n)) > 0);
61
    if ((i = mpz_cmp(l, r)) > 0) {
62
      mpz_set(r, l);
63
      now = time(0);
64
      sec = difftime(now, stt);
65
      printf("\n%.f:", sec);
66
      gmp_printf(" n=%Zd", n);
67
      gmp_printf(" r=%Zd", r);
68
      printf(" c=%u", c);
69
    }
70
  }                
71
  return 0;                           
72
}//]
73
[code]
74
75
[code]
76
D:\_PRJ\src>coll
77
78
0: n=27 r=9232 c=77
79
0: n=255 r=13120 c=15
80
0: n=447 r=39364 c=53
81
0: n=639 r=41524 c=25
82
0: n=703 r=250504 c=82
83
0: n=1819 r=1276936 c=50
84
0: n=4255 r=6810136 c=85
85
0: n=4591 r=8153620 c=59
86
0: n=9663 r=27114424 c=48
87
0: n=20895 r=50143264 c=87
88
0: n=26623 r=106358020 c=63
89
0: n=31911 r=121012864 c=76
90
0: n=60975 r=593279152 c=116
91
0: n=77671 r=1570824736 c=71
92
0: n=113383 r=2482111348 c=120
93
0: n=138367 r=2798323360 c=71
94
0: n=159487 r=17202377752 c=66
95
0: n=270271 r=24648077896 c=211
96
0: n=665215 r=52483285312 c=144
97
0: n=704511 r=56991483520 c=69
98
0: n=1042431 r=90239155648 c=224
99
0: n=1212415 r=139646736808 c=84
100
0: n=1441407 r=151629574372 c=141
101
0: n=1875711 r=155904349696 c=131
102
0: n=1988859 r=156914378224 c=144
103
1: n=2643183 r=190459818484 c=201
104
1: n=2684647 r=352617812944 c=120
105
1: n=3041127 r=622717901620 c=78
106
1: n=3873535 r=858555169576 c=127
107
1: n=4637979 r=1318802294932 c=168
108
1: n=5656191 r=2412493616608 c=170
109
1: n=6416623 r=4799996945368 c=133
110
1: n=6631675 r=60342610919632 c=163
111
1: n=19638399 r=306296925203752 c=338
112
2: n=38595583 r=474637698851092 c=191
113
4: n=80049391 r=2185143829170100 c=164
114
7: n=120080895 r=3277901576118580 c=164
115
11: n=210964383 r=6404797161121264 c=275
116
17: n=319804831 r=1414236446719942480 c=167
117
78: n=1410123943 r=7125885122794452160 c=340
118
460: n=8528817511 r=18144594937356598024 c=212
119
661: n=12327829503 r=20722398914405051728 c=202
120
1227: n=23035537407 r=68838156641548227040 c=196^C
121
D:\_PRJ\src>

Du hast dennoch recht!!!
Denn für die Beschleunigung bei der nächsten  Version war nicht
die Idee mit dem ">=" verantwortlich, sondern das Rausschmeißen
der lokalen Varianlen l, wie ein Gegentest beweißt.
Ich rechnete die Beschleunigung dem ">=" zu, weil mir das Umkopieren
von l auf r nach der while-Schleife als zu wenig auswendig  vorkam -
das gleichzeitig nicht ständig x nach l umkopiert wird, hatte ich
übersehen :-)

1
// g++ -Ofast col.cpp -o col -I ..\gmp\include\ -L ..\gmp\lib\ -lgmp 
2
3
#include <ctime>
4
#include <stdio.h>
5
#include "..\gmp\include\gmp.h"
6
7
int main(int argc, char **argv) {                             //[
8
static const unsigned int width = 4096;
9
static const unsigned int base_step = 3072;
10
static const unsigned int reste_amount = 116;
11
static unsigned int reste_loop = 0;
12
static const unsigned int reste[] =
13
{ 27,   31,   63,   91,  103,  111,  127,  159,  207,  231,  255,  283,
14
 303,  319,  327,  411,  415,  447,  463,  487,  495,  511,  543,  559, 
15
 603,  615,  639,  667,  679,  703,  751,  763,  795,  799,  831,  859, 
16
 871,  879,  927, 1023, 1051, 1071, 1087, 1095, 1135, 1179, 1183, 1191, 
17
1215, 1231, 1255, 1263, 1275, 1279, 1327, 1351, 1383, 1435, 1471, 1519, 
18
1563, 1567, 1627, 1639, 1647, 1663, 1695, 1767, 1791, 1819, 1855, 1863, 
19
1903, 1951, 1959, 1983, 2031, 2043, 2047, 2079, 2095, 2119, 2139, 2151, 
20
2175, 2203, 2215, 2239, 2287, 2299, 2331, 2367, 2407, 2463, 2511, 2535, 
21
2559, 2587, 2607, 2671, 2715, 2719, 2727, 2751, 2791, 2799, 2811, 2815, 
22
2847, 2887, 2907, 2919, 2983, 3007, 3055, 3067};
23
static char timstr[10];
24
static mpz_t b, n, r, x;
25
time_t stt, now; 
26
double sec;
27
unsigned int cnt, c, u;
28
int i;
29
30
  mpz_init2(b, width); 
31
  mpz_init2(n, width);                          
32
  mpz_init2(r, width);
33
  mpz_init2(x, width);
34
  mpz_set_ui(n, 1);
35
  mpz_set_ui(r, 1);
36
  stt = time(0);
37
  
38
  while (1) {
39
    mpz_add_ui(n, b, reste[reste_loop++]);
40
    if (reste_loop >= reste_amount) { 
41
      reste_loop = 0;
42
      mpz_add_ui(b, b, base_step);
43
    }
44
    mpz_set(x, n);
45
    cnt = 0;
46
    c = 0;
47
    do {
48
      mpz_mul_ui(x, x, 3);
49
      mpz_add_ui(x, x, 1);
50
      cnt++;
51
      if ((i = mpz_cmp(x, r)) > 0) {
52
        mpz_set(r, x);
53
        c = cnt;
54
      }
55
      u = mpz_scan1(x, 0);
56
      mpz_tdiv_q_2exp (x, x, u);
57
      cnt += u;
58
    } while ((i = mpz_cmp(x, n)) > 0);
59
    if (c) {
60
      now = time(0);
61
      sec = difftime(now, stt);
62
      printf("\n%.f:", sec);
63
      gmp_printf(" n=%Zd", n);
64
      gmp_printf(" r=%Zd", r);
65
      printf(" c=%u", c);
66
    }
67
  }                
68
  return 0;                           
69
}//]
1
D:\_PRJ\src>col
2
3
0: n=27 r=9232 c=77
4
0: n=255 r=13120 c=15
5
0: n=447 r=39364 c=53
6
0: n=639 r=41524 c=25
7
0: n=703 r=250504 c=82
8
0: n=1819 r=1276936 c=50
9
0: n=4255 r=6810136 c=85
10
0: n=4591 r=8153620 c=59
11
0: n=9663 r=27114424 c=48
12
0: n=20895 r=50143264 c=87
13
0: n=26623 r=106358020 c=63
14
0: n=31911 r=121012864 c=76
15
0: n=60975 r=593279152 c=116
16
0: n=77671 r=1570824736 c=71
17
0: n=113383 r=2482111348 c=120
18
0: n=138367 r=2798323360 c=71
19
0: n=159487 r=17202377752 c=66
20
0: n=270271 r=24648077896 c=211
21
0: n=665215 r=52483285312 c=144
22
0: n=704511 r=56991483520 c=69
23
0: n=1042431 r=90239155648 c=224
24
0: n=1212415 r=139646736808 c=84
25
0: n=1441407 r=151629574372 c=141
26
0: n=1875711 r=155904349696 c=131
27
0: n=1988859 r=156914378224 c=144
28
0: n=2643183 r=190459818484 c=201
29
0: n=2684647 r=352617812944 c=120
30
0: n=3041127 r=622717901620 c=78
31
0: n=3873535 r=858555169576 c=127
32
0: n=4637979 r=1318802294932 c=168
33
0: n=5656191 r=2412493616608 c=170
34
0: n=6416623 r=4799996945368 c=133
35
0: n=6631675 r=60342610919632 c=163
36
1: n=19638399 r=306296925203752 c=338
37
1: n=38595583 r=474637698851092 c=191
38
3: n=80049391 r=2185143829170100 c=164
39
4: n=120080895 r=3277901576118580 c=164
40
7: n=210964383 r=6404797161121264 c=275
41
12: n=319804831 r=1414236446719942480 c=167
42
57: n=1410123943 r=7125885122794452160 c=340
43
357: n=8528817511 r=18144594937356598024 c=212
44
523: n=12327829503 r=20722398914405051728 c=202
45
952: n=23035537407 r=68838156641548227040 c=196^C
46
D:\_PRJ\\src>col

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Vermutlich ist aber zumindest die Differenz von 952 auf 913 Sekunden
zum größten Teil dem ">=" zuzuschreiben und nur zu einem kleineren Teil
den auch schon beobachteten temperaturanhängige 
Geschwindigkeitsunterschieden der CPU.

: Bearbeitet durch User
von Weltbester FPGA-Pongo (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ist das hier noch das Unterforum FPGA?

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Es gibt halt Themen, die sich für beides eignen.

von Markus K. (markus-)


Bewertung
0 lesenswert
nicht lesenswert
Weltbester FPGA-Pongo schrieb im Beitrag #4834192:
> Ist das hier noch das Unterforum FPGA?

Es ist durchaus üblich, dass man Algorithmen erst mal auf dem PC testet, 
bevor man sie auf einem FPGA implementiert. Das Thema FPGA ist ja auch 
noch nicht durch.

von daybyter (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Nachdem ihr nun so doll optimiert habt, frag ich mich ob da nicht noch 
was mit OpenCL ginge.

Also viele Folgen parallel auf jeweils einem GPU Kern rechnen.

Diese Schiene wurde bisher ja etwas stiefmütterlich behandelt.

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Also die neun gebrauchten ebay-Boards kämen "nackt".
Etwas seltsam die Meldung "the item is not coming with any equiped 
items".
Kann mir nicht vorstellen, dass die die FPGAs unter dem Kühlkörper
entfernt haben - vermute vielmehr, dass die glauben, es gehe um
Teile, die für die Steckplätzen vorgesehen sind. Die haben wohl
keine Ahnung, was sie da verscherbeln - eine entsprechende Rückfrage
läuft.

Falls Ihr Euch bei Nallatech keine Unterstützung sichern könnt
(Doku, Software), sind die Boards aber sowieso uninteressant.

von dlchnr (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
ok - wie vermutet :-)
"No
The fpga's are under the heatsing
We ment we are selling only the board without any attachment"

von matthias (Gast)


Bewertung
0 lesenswert
nicht lesenswert
sry das ist ein doppelpost auch in stackoverflow, deswegen denglisch:)

Split xmm128 register:

How to I split Intel xmm128 Bit register into 2 64 bit qwords?
If have a very large number in xmm1 and want to get the higher quadword 
to r9 and lower quadword to r10, or RAx and RDx.
Whats the correct instruction?
and other way around compose an xmm register from 2 quadwords?

movlpd or movhpd only works with reg to mem or vice versa.
Thx
M.

von gonzens (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Weltbester FPGA-Pongo schrieb im Beitrag #4834192:
> Ist das hier noch das Unterforum FPGA?

Klar. Ich denke zur Veranschaulichung dessen was in dem Projekt 
gebraucht wird reicht das massig.

daybyter schrieb:
> Nachdem ihr nun so doll optimiert habt, frag ich mich ob da nicht noch
> was mit OpenCL ginge.

Yep. Das ist eine der Richtungen in die man schauen sollte. Nach dem was 
ich bisher herausbekommen habe gibt es dort nicht von Haus aus breite 
Integertypen, dh man müsste dort irgendeine art von bigint-lib (wie auch 
immer es dann dort heisst) oder verkettete schmale register verwenden. 
Der Faktor, der nach Ansicht von Leuten, die sich eventuell auskennen, 
zu erreichen ist, liegt bei 100. Das würde man natürlich gerne 
mitnehmen. Aber auch das gehört nicht hierher * schmunzel

ich schreib nachher mal für den mp ne zusammenfassung wo meiner einer da 
stecken geblieben ist :)

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Also so ne Lib kann ich nicht. Bastel auch nur im Cryptocoin Bereich mit 
OpenCL rum. Da sollte man paar Grundlagen kennen.

Meine Idee wäre die Verwendung von Long Vektoren.

https://www.khronos.org/registry/cl/sdk/1.2/docs/man/xhtml/vectorDataTypes.html

Ein long2 Vektor könnte ja eine 128 Bit Int darstellen. Oder man nimmt 
gleich long4 (Sky is the limit :-) ).

http://stackoverflow.com/questions/18534845/opencl-gpu-vector-math-instruction-level-parallelism

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Les gerade opencl specs. Darin wird der Datentyp long long erwähnt. Ein 
128 bit long Typ. Wenn man ein sdk hätte, welches das unterstützt, würde 
es die Sache doch erstmal vereinfachen.

Bei den Vector Typen gibt es zwar die Shift und Add Operationen, aber 
sie funktionieren nur für die einzelnen Komponenten. Wenn also x ein 
long4 ist, dann werden bei x >> 1 die 4 longs nach rechts geschoben, 
aber der Übertrag dazwischen fehlt. Bit 0 von long 1 wird nicht in das 
msb von long 0 geschoben usw. Das muss man dann von Hand machen. Erst 
die 3 0 Bits der oberen longs mit & maskieren, dann wohl um 63 Bit nach 
links schieben, mit shuffle um eine Komponente verschieben und mit | 
wieder hinzufügen.

Beim Addieren müsste man analog den Übertrag von Hand hinzufügen.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Andreas R. schrieb:
> Bei den Vector Typen gibt es zwar die Shift und Add Operationen, aber
> sie funktionieren nur für die einzelnen Komponenten. Wenn also x ein
> long4 ist, dann werden bei x >> 1 die 4 longs nach rechts geschoben,
> aber der Übertrag dazwischen fehlt. Bit 0 von long 1 wird nicht in das
> msb von long 0 geschoben usw. Das muss man dann von Hand machen. Erst
> die 3 0 Bits der oberen longs mit & maskieren, dann wohl um 63 Bit nach
> links schieben, mit shuffle um eine Komponente verschieben und mit |
> wieder hinzufügen.

Meine Idee wäre, sich auf einen INT112 zu beschränken und das
obere Byte  des low-int64, sowie das unter Byte des hgh-int64
als Carry-Area zu verwenden.
Uncompiliert und ungetestet, nur mal so als Idee und als
C++ - Klasse, ausgeführt für den gerade interessanten Bereich!
1
//[ cINT112 ///////////////////////////////////////////////////////////////////
2
3
typedef unsigned char uchr;
4
typedef unsigned long ui64;
5
6
class cINT112 {
7
  union low {
8
    ui64 i;
9
    uchr c[8];
10
  }
11
  union hgh {
12
    ui64 i;
13
    uchr c[8];
14
  }
15
  union tmp {
16
    ui64 i;
17
    uchr c[8];
18
  }
19
20
  // privat member functions 
21
  uchr count_trailing_zeros(uchr byte) {
22
  static uchr tab[256] = {
23
  // 0 1 2 3 4 5 6 7 8  ... 0xFC 0xFD 0xFE 0xFF
24
     8,0,1,0,2,0,1,0,3, ...   2,   0,    1,   0};
25
     return tab[byte];  
26
  };
27
28
  // privat copy ctor and assignment operator, if these aren't defined
29
  cINT112 (const cINT112& obj);
30
  cINT112& operator=(const cINT112& obj);
31
32
public:
33
34
  // ctor
35
  cINT112() {
36
    low.i = 0;
37
    hgh.i = 0;
38
    tmp.i = 0;
39
  };
40
41
  // dtor
42
  virtual ~cINT112() {};
43
44
  // basic member functions
45
  void SET(ui64 i) {
46
    low.i = i;
47
    hgh.i = 0;
48
    tmp.i = 0;
49
    hgh.c[1] = low.c[7];
50
    low.c[7] = 0; 
51
  };
52
  void INC() {        // 3 * x + 1
53
    hgh.i += hgh.i << 1;
54
    low.i = (low.i << 1) + low.i + 1;
55
    tmp.c[1] = low.c[7];
56
    low.c[7] = 0;
57
    hgh.i += tmp.i;   
58
  }
59
  void DEC() {        // x / 2 ^ s
60
  uchr shft = count_trailing_zeros(low.c[0]);
61
  uchr work;
62
    do {
63
      hgh.i >>= shft;
64
      work = hgh.c[0];
65
      hgh.c[0] = 0;
66
      work >>= (8 - shft);
67
      low.c[7] = work;
68
      low.i >>= shft;
69
    } while ((shft = count_trailing_zeros(low.c[0])));
70
  }
71
  uchr HGH() {        // upper limit reached
72
    return hgh.c[7] ? 1 : 0; 
73
  }
74
  uchr LOW() {        // lower limit reached
75
    return hgh.i ? 0 : 1; 
76
  }
77
};
78
79
//] eof cINT112 ///////////////////////////////////////////////////////////////

: Bearbeitet durch User
von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Hab den Vorteil dieser Lösung nicht ganz verstanden, aber ok.

Was anderes: nicht jede GPU unterstützt ja jeden Datentyp. Welche GPUs 
habt ihr denn zum Rechnen?

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Andreas R. schrieb:
> Hab den Vorteil dieser Lösung nicht ganz verstanden, aber ok.

Das war zumächst einmal nur eine Idee - ob sie sich vorteilhaft umsetzen 
läßt, müssen die entscheiden, die das implementieren können. Mein 
Vorschlag setzt voraus, dass auf die einzelnen Bytes eines INT64 
zugegriffen werden kann, mehr wird eigentlich nicht benötigt.
Er ermöglicht, das Überträge "gesammelt" werden können (andernfalls muss 
für eine (2 x + x + 1)-Operation dies drei mal geschehen!) und kann auch 
mehrere Überträge gleichzeitig von einem INT64-Teil zum anderen bewegen, 
so also auch bis zu 8 Bits auf einmal nach rechts shiften (und mehr 
dürften seltenst gebraucht werden).
Der Vorschlag minimiert Entscheidungen und Sprünge und realisiert eine 
sehr einfache Upper- und Lower-Limit-Erkennung.

: Bearbeitet durch User
von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
Ich weiß jetzt nicht, ob OpenCL ein Carry-Bit in die Schnittstelle 
exportiert, wenn nicht, müsste die (2 x + x + 1)-Operation in etwa
so realisiert werden.
1
hgh <<= 1;
2
tmp = low >> 63;
3
hgh |= tmp;
4
tmp = low << 1;
5
if ((tmp & 0x80000000) && (low & 0x80000000)) {
6
  hgh += 1;
7
}
8
low += tmp;
9
if (low == 0xFFFFFFFF) {
10
  hgh += 1;
11
}
12
low +=1;

Statt einem fünf-Zeiler ein zehn-Zeiler, inklusive zweier 
Entscheidungen/Sprünge - und ich sehe nicht, wie man das auf einen 
fünf-Zeiler eindampfen könnte, schon gar nicht, wie die 
Entscheidungen/Sprünge zu eliminieren wären?

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Ich schmeiss mal zuerst ein Tutorial in den Raum für die Lesewilligen...

http://amd-dev.wpengine.netdna-cdn.com/wordpress/media/2013/01/Introduction_to_OpenCL_Programming-Training_Guide-201005.pdf

Die ganze Sache muss noch ein bischen umgebaut werden, weil u.a. das 
Problem besteht, dass alle GPU Kerne nur 1 Instructionpointer haben. 
D.h. alle Kerne laufen immer gleich lange. Man kann nicht einfach einen 
Kern anhalten, wenn er fertig ist, sich die Daten von ihm holen und ihm 
neue Daten geben und ihn neu starten.
Ich hab mir überlegt, dass das Programm immer x Iterationen machen 
müsste (sagen wir 100 oder auch 1000, je nachdem wie lange so ne 
durchschnittliche Folge ist). Dann stoppen alle Kerne. Jetzt wird 
abgefragt, welche Kerne fertig sind, und diese Kerne bekommen neue 
Daten. Dann wird das Programm weiterlaufen gelassen.
Wobei die Schleife in dem Sinn gar nicht erkennen muss, ob sie fertig 
ist. Man testet einfach, ob der aktuelle Wert 4,2 oder 1 ist?
Das mit den Sprüngen ist so ne Sache.

Zu dem Carry Flag: sowas hab ich auch schon gesucht, aber nicht 
gefunden.
Mit den Conditionals musst aufpassen U.G. L., da alle GPU Kerne immer 
den ganzen Code durchlaufen müssen. Ein einzelner GPU Kern kann nicht 
einfach springen, sondern er durchläuft auch den Code, wenn eine 
Bedingung nicht erfüllt ist, ignoriert aber die Befehle darin. Kostet 
aber Leistung.

https://community.amd.com/thread/180106

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Andreas R. schrieb:
> Ich schmeiss mal zuerst ein Tutorial in den Raum für die
> Lesewilligen...
>
> http://amd-dev.wpengine.netdna-cdn.com/wordpress/m...
>
>  weil u.a. das
> Problem besteht, dass alle GPU Kerne nur 1 Instructionpointer haben.

Das is' nat. schon mal übel - ich hab' mit GPU-Programmierung noch keine 
Erfahrungen gemacht, drum war mir das nicht klar, es leuchtet aber 
schnell ein, wenn man sich daran erinnert, dass man in Verbindung mit 
GPUs eigentlich (fast) immer auch von SIMD liest.

> Ich hab mir überlegt, dass das Programm immer x Iterationen machen
> müsste (sagen wir 100 oder auch 1000, je nachdem wie lange so ne
> durchschnittliche Folge ist). Dann stoppen alle Kerne. Jetzt wird
> abgefragt, welche Kerne fertig sind, und diese Kerne bekommen neue
> Daten. Dann wird das Programm weiterlaufen gelassen.
> Wobei die Schleife in dem Sinn gar nicht erkennen muss, ob sie fertig
> ist. Man testet einfach, ob der aktuelle Wert 4,2 oder 1 ist?
> Das mit den Sprüngen ist so ne Sache.

Auf eine Erkennung der Uberschreitung eines Upper-Limits wird man nicht
verzichten können, denn man will ja pathrecords finden - es muss also
wenigstens ein Upper-Flag gegebenenfalls gesetzt werden.
Auf eine Erkennung der Unterschreitung eines Lower-Limits wird man nicht 
verzichten wollen, weil das die Zahl der notwendigen Iterationen 
beträchtlich verringert - man wird also auch da gegebenenfalls ein
Lower-Flag setzen wollen.
Wenn man die Right-Shifts bündeln kann, werden dann vermutlich 50 
Iterationen ausreichen. Die Haupt-CPU wird dann all die Startwerte
genauer berechnen müssen, bei denen das Upper-Flag gesetzt ist und
all die, bei denen das Lower-Flag nicht gesetzt ist.

> Mit den Conditionals musst aufpassen U.G. L., da alle GPU Kerne immer
> den ganzen Code durchlaufen müssen.

Mit ein Grund, weshalb ich Entscheidungen/Sprünge schon mal so weit als 
möglich tilgen wollte.

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ein Problem stellen vermutlich dann auch alle Folgen dar, bei denen 
StiftRigth-Operation um mehr als sieben oder acht Stellen notwendig sind 
- die kann man aber vermutlich einfach aussortieren (indem man z.B. das 
Upper-Flag setzt) und von der Haupt-CPU berechnen lassen.

von Andreas R. (daybyter)


Bewertung
0 lesenswert
nicht lesenswert
Man kann ja grundsätzlich nach jedem Schritt auf das obere Limit testen 
und es ggf überschreiben. Da bräuchten wir kein extra Flag?

von dlchnr (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Bei meiner einfachen Implementierung betrachte ich das obere Limit als 
erreicht, wenn eins der Bits von hgh.c[7] gesetzt ist - so wie ich Dich 
verstanden habe, müssen die GPUs parallel laufen, eine einzelne GPU kann 
nicht angehalten werden - und da hgh..low einen sehr dynamischen Wert 
enthält, nützt es nichts, wenn ich in hgh.c[7] etwas "überschreibe" -
nach wenigen Iterationen und insbesondere zu dem Zeitpunkt, an dem alle 
GPUs angehalten werden, könnte jedwede Information in hgh.c[7] verloren 
gegangen sein?
Ein Lower-Flag könnte man sich zwar sparen, wenn man hgh..low in die 
4-2-1-Schleife schickt, ein schnelles Abfragen der Ergebnisse 
erleichtert das aber auch nicht?

von daybyter (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich würde einfach jedem Kern eine Variable fürs obere Limit geben und 
wenn der aktuelle Wert größer ist, den Wert überschreiben. Diesen Wert 
zusammen mit dem aktuellen Wert vom Host nach jedem Durchgang auslesen.

von daybyter (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ich denke, die einfachste Möglichkeit ginge wohl so:

Die Host-cpu erzeugt mit clCreateBuffer 2 Arrays.  Das 1. ist für den 
aktuellen Wert der Folge, das 2. für das obere Limit. Die Host CPU 
initialisiert jetzt beide Arrays mit den Startwerten der Folgen, da ja 
der maximal Wert am Anfang der Startwert ist.
Also könnten die Arrays z.B. die Werte 3,5,7,9,... enthalten.
Jeder GPU Kern kennt seine ID, was der Index der Array Elemente ist.
GPU Kern 11 nimmt also den 11. Wert des 1. Array, errechnet das 
Folge-Element und speichert es wieder in das 11. Element des 1. Array. 
Ist es grösser wie das 11. Element  des 2. Array, wird dieses ersetzt.
Stoppt der Durchgang kann die Host CPU durch die 2 Arrays gehen und 
beide Werte checken. Ist Wert im 1. Array 1,2 oder 4 kann dieses Element 
entfernt werden. Dabei wird auch gleich der Path Record entfernt und 
gecheckt, ob wir ihn aufheben. Dann wird der jeweilige Wert in den 2 
Arrays neu gesetzt, bevor neu gestartet wird.
Die Host CPU erzeugt dafür jeweils die neuen Startwerte, bis der 
Wertebereich abgesucht ist.

von gonzens (Gast)


Bewertung
0 lesenswert
nicht lesenswert
@daybyter:

eine vereinfachung hierzu: man kann einfach folgen aussortieren, die die 
bitlänge des vorgegebenen records erreichen. dann werden zwar 3-4 mal so 
viele folgen ausgeworfen, aber die kann die cpu ja aussortieren. damit 
vereinfacht sich die übergabe (ziel-bitlänge) und die prüfung ob der 
record erreicht ist erheblich.

von U.G. L. (dlchnr)


Bewertung
0 lesenswert
nicht lesenswert
1
#87  0e6a 5c22 fd7b de9f : 003d 8335 83fc b4f4 a0aa 0247 bd70 f498
2
#88  1b7d d73a 9374 85bf : 302a b3d0 52fb 87c0 6228 d249 581b e0e4

Es gilt eigentlich zunächst mal den Bereich zwischen #87 und #88 zu 
verifizieren, gegebenenfalls darin neue Rekordpfade zu finden.
D.h., ein sinnvoller Startwert, wenn man mal "ernstlich" zu rechnen 
anfängt, wird z.B. #87 - #87 % 3072 sein.
1
Startwert: 
2
     0e6a 5c22 fd7b d400 : xx## xxxx xxxx xxxx xxxx xxxx xxxx xxxx

Für die nächsten Jahre und auch für die nächste Grafikkarten-Generation 
werden Folgen "interessant" sein, wenn der Pfad einen Wert erreicht, bei 
dem ein Bit im  Bereich ## gesetzt ist (bei meiner Art, den BigInt zu 
realisieren, wäre das hgh.c[7]). Wir können dann ein Flag 
"upper-limit-reached" (vermutlich in einem Array) setzten, das zu Beginn 
eines Zykluses gelöscht wurde. Wir brauchen also kein Array mit 
Rekordwerten.
1
     $$xx xxxx xxxx xxxx : xx## xxxx xxxx xxxx xxxx xxxx xxxx xxxx

Bei derart großen Flogewerten dauert es viel zu lange, die Folge auf die 
Loop 4-2-1 zu iterieren. Wir begnügen uns damit, wenn der Pfad einen 
Wert erreicht, bei dem kein Bit im Bereich $$ aufwärts (oder besser noch
xxxxxx$$ & 0xFFFFFFFE) gesetzt ist (bei meiner Art, den BigInt zu 
realisieren, wäre das hgh.i oder hgh.i & 0xFFFFFFFE ). Wir können dann 
ein Flag "lower-limit-not-reached" (vermutlich in einem Array) löschen, 
das zu Beginn eines Zykluses gesetzt wurde.

Die richtigen Kerne müssen dann alle Folgen überprüfen, bei denen 
"upper-limit-reached" gesetzt wurde und alle Folgen, bei denen 
"lower-limit-not-reached" immer noch gesetzt ist.

Wenn möglich, würde man die beiden Falgs so plazieren, dass sie sich mit 
einem Zugriff abgefragen lassen (und auch zu Beginn eines Zykluses 
gemeinsam initialsieren lassen).

Wir müssen auch nicht laufend ein Array mit Startwerten übergeben, denn 
jede GPU kann sich den nächsten Startwert selber berechnen.

nächsterStartwert = alterStartwert + 3072

Falls die Zahl der GPUs für mehre 3072er-Sätze reicht würde sich der 
nächste Startwert entsprechend zu

nächsterStartwert = alterStartwert + (sets * 3072)

berechnen. Und mit etwas Gehirnschmaltz lassen sich sicherlich auch dann 
immer noch unbeschäftigte GPUs beschäftigen (andere Siebweiten als 3072
oder das unterschiedliche Reste-Sätze auf unterschiedliche 
Grafikkarten/Maschinen verteilt werden.

Die GPU-Maschinerie hat also nur Initialisierungsdaten (Array mit 
Startwert), keine Inputdaten und pro GPU nur zwei Flags Outputdaten.