128 Bit Risc

[daybyter (Gast)]

Den Test könnte man in meine fpga Version oben wohl recht leicht 
einbauen.

Problem mit dem + 3072 Rechnen pro Kern ist halt, dass wir eine 
Abbruchbedingung für alle GPU Kerne brauchen. Der einzelne Kern weiss 
nicht, was sein Nachbar tut. Also ob er fertig ist. D.h. regelmäßige 
Zwischenstopps machen schon Sinn?

[dlchnr (Gast)]

Nein, alle GPUs laufen die gleiche Anzahl von Iterationen - die Anzahl 
der Iterationen muss man so auslegen, dass 99% oder 99,9% der GPUs 
(durch Simulationsläufe auf einem normalen PC) ihr 
"lower-limit-not-reached"-Bit gelöscht haben, wenn sie nicht das 
"upper-limit-reached"-Bit gesetzt haben.
Sie übergeben dann ihr Ergebnis in ein globales Array, berechnen ihren 
nächsten Startwert, initialisieren ihre Flags neu un legen mit dem 
nächsten Zyklus los.

[U.G. L. (dlchnr)]

gonzens schrieb:
> den entsprechenden "hart codierten" tests auf
> record und stopwert, die jeweils durch überschreiten oder unterschreiten
> bestimmter 2-er potenzen also entsprechender max und der min gesetzten
> Bits hinausläuft :) ggf. bekommt man auf die art auch deutlich mehr
> solcher "Collatz_Units" auf den FPGA :)

das hatte ich nie anders geplant und ist eigentlich Voraussetzung für 
ein "kleines" Design!

[U.G. L. (dlchnr)]

matthias schrieb:
> 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..

@mattias:
U.U. lassen sich die SSE Extensions nutzen, wenn Du statt einem INT128 
oder einem INT192 einen INT112 oder INT160 (56 +  48 + 56) entsprechend 
meinem Beitrag "Re: 128 Bit Risc" bastelst - 
ich meine, der Code müsste ohne Flags funktionieren (entsprechende Tests 
stehen allerdings noch aus).
Erfordert aber nat., dass man auf die einzelnen Bytes eines Registers 
zugreifen, und diese separat manipulieren kann!?

[dlchnr (Gast)]

U.G. L. schrieb:
> 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 :-).

Hatte dann doch gleich selber mal nachgefragt und zur Antwort bekommen,
dass es für ihre Boards keinen Support gibt, wenn sie über eine "3rd 
party" bezogen wurde. Die gebrauchten Boards kann man also ad acta legen 
und damit höchstwahrscheinlich auch eine FPGA-Lösung. Man wird sich wohl 
besser auf eine Grafikkarten/OpenCL-Variante konzentrieren.

[matthias (Gast)]

U.G. L. schrieb:
> @mattias:
> U.U. lassen sich die SSE Extensions nutzen, wenn Du statt einem INT128
> oder einem INT192 einen INT112 oder INT160 (56 +  48 + 56) entsprechend
> meinem Beitrag "Re: 128 Bit Risc" bastelst -

ja nett aber was ist das für eine Sprache und mit int160 meinst du einen 
Datentyp?

gnu c ist  es nicht oder g++
Tnx
merry xmax;)

[U.G. L. (dlchnr)]

matthias schrieb:
> ja nett aber was ist das für eine Sprache und mit int160 meinst du einen
> Datentyp?

Na es sollte dann doch C++ sein :-)
Aber wie schon oben geschrieben, noch nicht compiliert oder gar 
getestet, also nur eine Idee, noiert in C++.
Und ja, int112 oder int160 wären, aus int64 gebastelte, eigene Typen, in 
denen Platz für Überläufe und zu shiftende Bits vorhanden ist - weswegen 
für eine Implementierung keine Operationen mit Carry-Bit notwendig sein 
sollten.
Allerdings müsste man auf diverse, einzelne Bytes zugreifen und sie 
separat manipulieren können.

Nutzbits würden beim einem int112 im low-Part nur die Bytes 0 bis 6 und
im hgh-Part nur die Bytes 1-7 enthalten - low-Part-Byte7 und 
hgh-Part-Byte0 ersetzen sozusagen das Carry-Bit.

            hgh-Part                              low-Part
 _______________________________       _______________________________
|_7_|_6_|_5_|_4_|_3_|_2_|_1_|_0_|     |_7_|_6_|_5_|_4_|_3_|_2_|_1_|_0_|

 ___________________________   ___   ___   ___________________________
|_7_|_6_|_5_|_4_|_3_|_2_|_1_| |_0_| |_7_| |_6_|_5_|_4_|_3_|_2_|_1_|_0_|

[Andreas R. (daybyter)]

C++ geht auf GPU eigentlich nicht. Nur OpenCL (wenn es für ne grössere 
Auswahl an GPU Typen sein soll). Problem ist, dass es ziemlich bremsen 
dürfte, wenn man solch grosse Typen byteweise manipuliert. Wenn dem IP 
Problem, werd ja bei einem if else immer beide Zweige ausgeführt. Wird 
also nur 1 Kern ein Byte anfassen, müssen alle Kerne diesen Code 
ausführen. Also wird wohl jeder Kern jedes Byte anfassen müssen. Ganz 
schlecht. Es sollten idealerweise nur Datentypen benutzt werden, welche 
die GPU nativ unterstützt. Deshalb wäre halt long long cool, wenn eine 
GPU dann eine Addition z.B. mit einem einzigen Maschinenbefehl ausführen 
kann. Alternativ halt ein long2 Vektor, damit man nur 2 Elements 
anfassen muss, und nicht etwa 20 (160 Bit = 20 Byte).

Hat jetzt schonmal jemand so ein Streaming SDK installiert, damit man 
mal praktisch was probieren kann? Theoretisch soll das ja jetzt auch in 
einer virtuellen Maschine gehen, aber das hab ich noch nicht probiert.

[U.G. L. (dlchnr)]

Andreas R. schrieb:
> C++ geht auf GPU eigentlich nicht. Nur OpenCL (wenn es für ne grössere
> Auswahl an GPU Typen sein soll).

Es ist klar, dass das letztlich mit OpenCL gemacht werden muss.
Wie schon erwähnt, ist der gepostet Code nur 'n Vorschlag/Idee 
niedergeschrieben in C++, vielleicht die Basis einer Simulation.

> Problem ist, dass es ziemlich bremsen
> dürfte, wenn man solch grosse Typen byteweise manipuliert. Wenn dem IP
> Problem, werd ja bei einem if else immer beide Zweige ausgeführt. Wird
> also nur 1 Kern ein Byte anfassen, müssen alle Kerne diesen Code
> ausführen. Also wird wohl jeder Kern jedes Byte anfassen müssen. Ganz
> schlecht. Es sollten idealerweise nur Datentypen benutzt werden, welche
> die GPU nativ unterstützt. Deshalb wäre halt long long cool, wenn eine
> GPU dann eine Addition z.B. mit einem einzigen Maschinenbefehl ausführen
> kann. Alternativ halt ein long2 Vektor, damit man nur 2 Elements
> anfassen muss, und nicht etwa 20 (160 Bit = 20 Byte).

Erstmal - die 160 bit waren nur ein Einwurf, wie man die 112 Bit 
erweitern würde, wenn die mal nicht mehr reichen. Der aktuell 
interssante Bereich wird sich mit irgendwas zwischen 80 bis 128 bit 
erschlagen lassen.
Leider gibt es, soweit ich das sehe, in aktuell verfügbaren 
Implementierungen von OpenCL keine 128bit Typ, sonst würde man sich ganz 
klar darauf stürtzen. Und ein long2 ist halt alles andere als ein 128bit 
Typ - es ist ein Vektor aus zwei 64bit Typen, die eigentlich nix 
miteinander zu tun haben, insbesondere gibt es nix, in was ein 
Überlaufe/Unterlauf am oberen Ende der ersten Komponente bzw. an am 
unteren Ende der zweiten Komponente reinfallen würde (Carrry) - es ist 
also notwendig, vor jeder Operation zu bestimmen, ob ein 
Überlauf/Unterlauf entstehen wird und diesen separat zu behandeln, womit 
wir bei etwas wären, was so wie in 
www.mikrocontroller.net/topic/413678#4835838 gezeigt funktionieren 
müsste.
Die Idee hinter meinem Vorschlag war nun, dass bei einer GPU eigentlich 
Zugriffs-/Manipulationsmöglichkeiten auf einzelne Bytes vorhanden sein 
müssten, da Bytetypen nun ja alles andere als selten genutzte Datentypen 
auf einer Graka sind (8bit Pixel, 8bit Komponenten bei RGB und RGB32) 
und man dann jeweils ein Byte (unten oder oben) eines 64bit Integers als 
Raum für Uber- und Unterlauf verwenden könnte - und dann eben nicht nur 
für einen Uber-/Unterlauf, sondern gleich für mehrere, so dass z.B. die 
Überlaufbehandlung für eine 3 x + 1 Operation nur einmal, statt dreimal 
gemacht werden muss.
Ob mein Vorschlag funktioniert, muss aber jemand sagen, der sich mit 
Graka-Programmierung auskennt.

[Andreas R. (daybyter)]

Bei Cuda scheint es mit inline ASM zu gehen.

http://stackoverflow.com/questions/6162140/128-bit-integer-on-cuda

Bei OpenCL eher nicht.

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

[U.G. L. (dlchnr)]

Eukrott V. schrieb:
> 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)

Heute ist mir noch ein Gedanke gekommen, womit der höher als von mir
erwartete Faktor zwischen der GMP- und der Assembler-Version kommen 
könnte -
wie ich schon längere Zeit eruiert hatte und heute wieder von mir 
ausgebudelt wurde, unterscheidet sich der Typ "int" bei MinGW zwischen 
der 32Bit- und der 64bit-Version nicht! Ein unterschied findet sich nur 
beim Typ "long long", der auf 32bit immernoch 32bit breit ist, bei der 
64bit Version dann aber doch 64bit!

printf("\nsi=%u", sizeof(short int));
printf("\ni=%u", sizeof(int));
printf("\nli=%u", sizeof(long int));
printf("\nlli=%u", sizeof(long long int));
printf("\nf=%u", sizeof(float));
printf("\nd=%u", sizeof(double));
printf("\nld=%u", sizeof(long double)); 

mgw32:
si=2
i=4
li=4
lli=8
f=4
d=8
ld=12

mgw64:
si=2
i=4
li=4
lli=8
f=4
d=8
ld=16

Ich weiß jetzt nicht, wie das beim GCC unter Linux ausschaut, wenn der 
das aber ebenso handhabt, könnte ich mir vorstellen, dass GMP auch in 
einer 64bit Umgebung nut mit 32bit breiten "Stücken" arbeitet - man 
müsste feststellen, wie groß dort ein "limb" ist!?

Falls die limbs nur 32 bit breit sind, würde das natürlich den Faktor 3 
teilweise erklären.

[U.G. L. (dlchnr)]

Andreas R. schrieb:
> Bei Cuda scheint es mit inline ASM zu gehen.
>
> http://stackoverflow.com/questions/6162140/128-bit-integer-on-cuda
>
> Bei OpenCL eher nicht.
>
> https://community.amd.com/thread/188702

Cuda und Assembler würde ich aus dem weg gehen wollen - sicher wird man 
damit schnelleren Code hinbekommen, der läuft dann aber halt nur auf 
einer bestimmten Karte.

Mit OpenCL hat man den Vorteil, das der Code auf Grafikkarten von 
Nvidia, AMD und Intel laufen kann - entsprechend leichter sollte 
gegebenefalls es sein, Grafikkarten für das Projekt abzustellen.

Interessant erscheint mir dafür auch die Webseite, auf die im geposteten 
Link verwiesen wird 
(https://devtalk.nvidia.com/default/topic/491349/cuda-programming-and-performance/larger-than-64bit-integer-i-want-to-count-with-very-big-integers-larger-than-64bit/) 
- eine Methode, wie man das fehlende Carry ersetzen kann.

Ich habe mittlerweile zudem erkannt, dass bei einer 2x + x + 1 Operation 
nur zweimal ein Carry auftreten kann - für die Addition der 1 ist im 
low-Element immer Platz und eine Carry-Prüfung und Übertragung ist nicht 
notwendig.

[Markus K. (markus-)]

U.G. L. schrieb:
> Ein unterschied findet sich nur
> beim Typ "long long", der auf 32bit immernoch 32bit breit ist, bei der
> 64bit Version dann aber doch 64bit!

Das widerspricht meiner Erfahrung und insbesondere auch Deinen 
Testergebnissen.

[U.G. L. (dlchnr)]

Hab' auf Basis meines letzten Beitrags mal eine prakisch reine
C-Version geschrieben (GMP ist nur noch für die Ausgabe drinnen).

Sie ist fast um den Faktor zwei schneller wie meine GMP-Version,
obwohl sie ebenfalls mit 32bit arbeitet, d,h, mit 64bit wäre vermutlich
noch mehr drin.

Ich kann bei meiner Version weitere kanpp 8% gewinnen,
wenn ich nach der "Rechenstufe" eine zweite, optionale Teilung
einfüge, u.U. bringt das auch was bei Eurer Assemblerversion.

Kann aber auch sein, dass das bei mir nur was bringt, weil
ich noch vollkommen unnötige Vergleiche mit dem Startwert drin
habe (immer, wenn ich zuvor ein 3x+1 Schritt hatte und schon gegen
den Pfadrekord getestet habe).

Das Urige - wenn ich diesen "Schönheitsfehler" beseitige, profitiert
das Programm nicht etwas davon, sondern wird minimal langsamer -
und die zweite, optionale Teilung verschlechtert das Ergebnis deutlich!?
Keine Ahnung - vielleicht irgedwelche Cache-Effekte!?
Oder meine CPU hat gerade Hitzewallungen :-)

Hab' das aber nicht mehr weiter untersucht, weil ich eher in Richtung
GPU arbeite. Dafür ist auch die weitere Variante im Code gedacht - die
läuft auf der CPU zwar langsamer, könnte aber auf den GPUs von Vorteil
sein, weil das Abprüfen gegen den Pfadrekord und gegen den Startwert
nicht nacheinander passiert, stattdessen auf der einzelnen GPUs nur
gegen den gerade aktuellen Vergleichswert geprüft wird - mit dem
gleichen Code, aber ensprechend preparierten Daten.

für #45 n=8528817511 r=18144594937356598024 

  GMP  #if 1   #if 1   #if 1
              BSTAGE 
371sec 192sec 178sec  257sec
  \_1,93_/ \_8%_/

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

#include <ctime>
#include <stdio.h>
#include "..\..\gmp\include\gmp.h"

//[ typedefs ----------------------------------------------------
typedef unsigned       int ui32;
typedef unsigned long long ui64;
typedef struct u128 {ui64 l; ui64 h;} u128;
//] eof typedefs ------------------------------------------------

void u128_print(const char* str, u128* z) {                   //[
mpz_t x;
ui32* u = (ui32*) z;
  
      mpz_init2(x, 128);
      mpz_set_ui(x, u[3]);
      mpz_mul_2exp(x, x, 32);
      mpz_add_ui(x, x, u[2]);
      mpz_mul_2exp(x, x, 32);
      mpz_add_ui(x, x, u[1]);
      mpz_mul_2exp(x, x, 32);
      mpz_add_ui(x, x, u[0]);
      gmp_printf(str, x);
}//]

int main(int argc, char **argv) {                             //[
static char timstr[10];
static time_t stt, now; 
static double sec;
static const ui32 step = 3072;
static const ui32 lend =  116;
static       ui32 loop =    0;
static       ui64 base =    0;
static const ui32 rest[] = {
  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};
u128 r = {160 >> 1, 0};
u128 n = {0, 0}, x, w;
ui64 t64;
ui32 t32, flg, lim;
int cnt, c;

  stt = time(0);
  while (1) {    
    n.l = base + rest[loop++];
    if (loop >= lend) { 
      loop = 0;
      base += step;
    }
    x = n;
    lim = 2;
    cnt = 0;
    c = 0;
    do {    // 32bit implementation
      cnt++;
      flg = (*((ui32*) (&x.l))) & 1;
      // w = x/2;
      t32 = ((*((ui32*) (&x.h))) & 1) << 31;
      w.h = x.h >> 1;
      w.l = x.l >> 1;
      (*(((ui32*) (&w.l)) + 1)) |= t32;
      // if (even) x = {0, 0};
      t64 = -((signed long long) flg);
      x.l &= t64;
      x.h &= t64;
      // x = x + w + flg;
      x.h  = x.h + w.h;                
      x.l  = x.l + w.l;
      x.h += (x.l < w.l);  // carry
      x.l += flg;
#if 1
#define BSTAGE 0
      if (flg) {           // cmp r
        t64 = x.h + (x.l > r.l);
        // copy new record, if one found
        if (t64 > r.h) {
          r = x;
          c = cnt;
        }
      }
#if BSTAGE
      //[ extra x = x/2 stage
      if (!((*((ui32*) (&x.l))) & 1)) {
        // w = x/2;
        t32 = ((*((ui32*) (&x.h))) & 1) << 31;
        x.h >>= 1;
        x.l >>= 1;
        (*(((ui32*) (&x.l)) + 1)) |= t32;
      }//]
#endif       
    } while (x.h || (x.l > n.l));
#else
      // copy u128 to compare with x
      w = flg ? r : n;
      // compare
      t64 = x.h + (x.l > w.l);
      t32 = (t64 > w.h);
      // extract results
      t32 |= (flg << 1);
      lim &= 0x0000FFFD >> (t32 << 2);
      lim |= 0x00001000 >> (t32 << 2);
      // copy new record, if one found
      if (flg & t32) {    // cmp r
         r = x;
         c = cnt;
      }
    } while (lim & 2); 
#endif
    if (c) {
      now = time(0);
      sec = difftime(now, stt);
      printf("\n%.f:", sec);
      w = n;
      u128_print(" n=%Zd", &w);
      w.l = r.l << 1;
      w.h = r.h << 1;
      w.h |= ((signed long long) r.l) < 0 ? 1 : 0;
      u128_print(" r=%Zd", &w);      
      printf(" c=%u", c);
    }
  }                
  return 0;                           
}//]

[(prx) A. K. (prx)]

U.G. L. schrieb:
> Ein unterschied findet sich nur
> beim Typ "long long", der auf 32bit immernoch 32bit breit ist, bei der
> 64bit Version dann aber doch 64bit!

Das ist so in Windows, weil MS sich nicht traute, DWORD=long aufzugeben. 
Das LLP64 Typenmodell. In Linux findest du LP64, also 64 Bit long.

[U.G. L. (dlchnr)]

Markus K. schrieb:
> U.G. L. schrieb:
>> Ein unterschied findet sich nur
>> beim Typ "long long", der auf 32bit immernoch 32bit breit ist, bei der
>> 64bit Version dann aber doch 64bit!
>
> Das widerspricht meiner Erfahrung und insbesondere auch Deinen
> Testergebnissen.

LOL - da hab' ich vielleicht einen Stuss zusammengeschrieben - da
sind wohl ursprüngliche Annahmen, Messungen und Vergucker fröhlich 
durcheinander gewürfelt worden :-)

Es gibt, zumindest bei den Integertypen gerade keine Unterschiede,
insbesondere ist der "int", entgegen meiner Erwartung, auch in der 64bit 
Umgebung nur 32bit breit (bei MinGW). Und das könnte vielleicht dazu 
führen, dass eben auch bei der GMP in einer 64bit Umgebung ein "limb" 
nur 32bit breit ist (falls der GCC auf Linux sich wie MinGW auf Windows 
verhält) - und das war's, was ich eigentlich sagen wollte :-)

[Gustl B. (-gb-)]

Dieses Gestochere im Nebel ... es gibt doch int64_t und uint64_t.

[Andreas R. (daybyter)]

U.G. L. schrieb:

> Cuda und Assembler würde ich aus dem weg gehen wollen - sicher wird man
> damit schnelleren Code hinbekommen, der läuft dann aber halt nur auf
> einer bestimmten Karte.
>
> Mit OpenCL hat man den Vorteil, das der Code auf Grafikkarten von
> Nvidia, AMD und Intel laufen kann - entsprechend leichter sollte
> gegebenefalls es sein, Grafikkarten für das Projekt abzustellen.

Interessant ist, dass diese Inline Asm Lösung wohl nur mit NVidia Karten 
geht, welche aber nach meinen Erfahrungen im Integer Bereich immer 
langsamer als die AMD Karten waren (vielleicht bis auf die ganz neuen 
Karten). Deshalb wurde ja z.B. beim Bitcoin-Mining immer auf die AMD 
Karten gesetzt. Wenn ich mich recht entsinne, haben den NVidia 1,2 
wichtige Befehle für diese Encryption-Geschichten gefehlt. Ich glaub, es 
ging um Schiebe-Befehle.

Da steht was dazu:

https://www.extremetech.com/computing/153467-amd-destroys-nvidia-bitcoin-mining

Das hat jetzt wohl zur Folge, dass wir entweder guten Code auf ner 
schlechten Karte haben, oder schlechten Code auf ner guten Karte? ;-)

D.h. die freie Wahl zwischen Pest oder Cholera.

Ciao,
Andreas

[U.G. L. (dlchnr)]

Gustl B. schrieb:
> Dieses Gestochere im Nebel ... es gibt doch int64_t und uint64_t.

Es geht nicht darum, was man nehmen könnte, sondern darum, wie C's 
Standard-Typen implementiert sind!

[Michael W. (Gast)]

Geht es hier eigentlich noch um 128 bit risc?

[U.G. L. (dlchnr)]

Markus W. schrieb:
> Geht es hier eigentlich noch um 128 bit risc?

Ich denke, die Diskussion hat schnell gezeigt, dass das zu bearbeitende 
Problem, wenn überhaupt mit einem FPGA, dann nicht mittels einer 
klassichen 128bit RISC CPU, sondern mittels möglichst vieler, parallel 
arbeitender, spezieller Collatz-Maschinen anzugehen wäre.

[U.G. L. (dlchnr)]

Wie ich gestern abend entdeckt habe, sollte man bei Verwendung der 
GMP-Library für jeden Aufruf von mpz_init2(...) einen korrespondierenden 
mpz_clear(...)-Aufruf spendieren :-)

Wer also eines meiner Beispiele als Grundlage für eigene Programme 
benutzt, sollte auf die korrigierten Versionen im Anhang zurückgreifen.

Beitrag "Re: 128 Bit Risc"
collatz1.cpp
collatz1.exe

Beitrag "Re: 128 Bit Risc"
collatz2.cpp
collatz2.exe

Beitrag "Re: 128 Bit Risc"
collatz.cpp

Beitrag "Re: 128 Bit Risc"
collatz3.cpp
collatz4.cpp

Beitrag "Re: 128 Bit Risc"
c128.cpp

[matthias (Gast)]

Frohes neues Jaaa!

Bei dem o.a. Collatz Algorithmus tritt der Effekt auf, dass man bei 
Zahlen kongruent 2 modulo also Zahlen die durch 3 geteilt 2 Rest 
bleiben, abbrechen kann.
Also z.B. 2,5,8,11,.14,17,.....,254,257,250,,770,..3074,...,8192,.. 
16385,,,32768,..,49154,,  Beispiele bis ca, 2^16.

Eine Lösung isr gefunden z.b., wenn die Quersumme im Dezimalsystem Rest 
2 mod 3 ergibt.
Aber wir arbeiten mit 128 Bit Binär Maschinen.

Man müsste doch einen schnellen "modulo-3-Algorithus" in _86 Assembler 
oder mit LTU s implementieren können.
Das Standardverfahren ist der euklidische Algorithmus, der erscheint mir 
hier zu aufwendig.
Es gibt aber auch kein erkennbares Bitmuster in den unteren 16 bit.
Das gute ist, dass nur modulo 3 interessiert, keine generelle modulo 
funktion für 128/64  Bit Integer ist benötigt.
Ein mathematisches oder logistisches Problem /Lösung?
Schnell muss sie sein.

[U.G. L. (dlchnr)]

matthias schrieb:
> Ein mathematisches oder logistisches Problem /Lösung?

Auf den ersten Blick hin, eigentlich eine einfache Sache (vielleicht 
überseh' ich auf die Schnelle aber etwas?).

Ein gesetztes Even-Bit trägz mit einem Rest 1 zum Gesamtergebnis bei,
ein gesetztes Odd-Bit bringt einen Rest 2 ein.

Das Bild zeigt eine Schaltung für 16Bit, pro Bitbreitenverdopplung käme 
rechts eine weitere "Redzierstufe" hinzu.

Da 4er LUTs in FPGAs meist nur einen Ausgang haben, müsste man die LUTs 
aus der Schaltung mittels zweier FPGA-LUTs realisieren.

Im Prinzip eine Schaltung ähnlich einem Parity-Generator 
(https://de.wikipedia.org/wiki/Parit%C3%A4tsgenerator).

[U.G. L. (dlchnr)]

Und als Software wären es halt 4 Zugriffe in ein 4GB-LUT oder 8 Zugriffe 
in eine 64kB LUT plus Ergebnisse shiften und oderieren, dann ein 
weiterer LUT-Zugriff in eine 256Byte oder 64kB-LUT.

[U.G. L. (dlchnr)]

Andere Ideee wäre, durch Maskieren Odd- und Even-Bits zu trennen, und 
einen Algo mittels eines CountBits-Algo 
(http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive) 
stricken.

[U.G. L. (dlchnr)]

Aber vermutlich wir da die Modulo-3-Operation, jeweils angewandt auf die 
unteren und oberen 64Bit schneller sein!

[U.G. L. (dlchnr)]

U.G. L. schrieb:
> plus Ergebnisse shiften und oderieren, dann ein
> weiterer LUT-Zugriff in eine 256Byte oder 64kB-LUT.

Einfaches Addieren plus Griff in eine kleine LUT reicht eigentlich.

[U.G. L. (dlchnr)]

Gerade sehe ich, dass es unter SSE4 gibt es die POPCNT instruction.
Also wieder in odd- und even-bits trennen(maskieren) gesetzte Bits 
zählen und auswertem.
Und falls es interessiert - wie popcnt in hardware realisiert wird:
http://www.wseas.us/e-library/conferences/2006hangzhou/papers/531-262.pdf

[matthias (Gast)]

Dein Bildchen ist nett, aber die modulo 3 Bitmuster wiederholen sich 
nicht bei 2^16 leider:

65536 kongruent 1 mod 3

So lößt es gcc:

#include <stdio.h>
int main ()
{
// 998 mod 3 =2

unsigned int i= 998;
unsigned int j= i%3;

printf("\n i = %i",i);
printf("\n j = %i",j);
}

Auszug aus dem .S file, geht bis 32 bit denk ich...

Lade was Du willst in -8(%rbp)
Ergebnis in -4(%rbp)

  movq  %rsp, %rbp
  .cfi_def_cfa_register 6
  subq  $16, %rsp
  movl  $998, -8(%rbp)
  movl  -8(%rbp), %ecx
  movl  $-1431655765, %edx
  movl  %ecx, %eax
  mull  %edx
  shrl  %edx
  movl  %edx, %eax
  addl  %eax, %eax
  addl  %edx, %eax
  subl  %eax, %ecx
  movl  %ecx, %eax
  movl  %eax, -4(%rbp)


998 mod 3 =2

Happy New Year anyway ;)

M.J.

[matthias (Gast)]

Und wie kommt der Compiler auf das mysteriöse -1 431 655 765??


Also 2^32 = 4 294 967 296 -1 431 655 765 = 2 863 311 531. Aber wie 
entsteht dieses 1 431 655 765?
Bei anderen modulo quotienten macht der gcc compiler andere Weter an der 
Stelle, ja kla.

Main Ja Nuhr ;)
ciao

[Markus K. (markus-)]

matthias schrieb:
> Also 2^32 = 4 294 967 296 -1 431 655 765 = 2 863 311 531. Aber wie
> entsteht dieses 1 431 655 765?


10101010101010101010101010101011 ist 2863311531 als unsigned int und 
-1431655765 als signed int. Die Register selber sind nicht 
signed/unsigned, sondern die Befehle.

[U.G. L. (dlchnr)]

matthias schrieb:
> Dein Bildchen ist nett, aber die modulo 3 Bitmuster wiederholen sich
> nicht bei 2^16 leider:
>
> 65536 kongruent 1 mod 3

16 ist gerade, also ist 2^16 = 1 mod 3 -  passt doch!!!

2^n = 1 mod 3, wenn n gerade
2^n = 2 mod 3, wenn n ungerade

z.B.

  0x5201700A:

  0x5201700A 
& 0xAAAAAAAA 
= 0x0200200A  ==> 4  gerade  Bits gesetzt ==> 4 x 1 =  4 


  0x5201700A 
& 0x55555555
= 0x50015000  ==> 5 ungerade Bits gesetzt ==> 5 x 2 = 10 
--------------------------------------------------------
                                                Summe 14
14 = 2 mod 3

ergo:
0x5201700A = 2 mod 3

[U.G. L. (dlchnr)]

oder 998 == 0x3E6:

  0x000003E6 
& 0xAAAAAAAA 
= 0x000002A2  ==> 5  gerade  Bits gesetzt ==> 5 x 1 =  5 


  0x000003E6 
& 0x55555555
= 0x00000144  ==> 3 ungerade Bits gesetzt ==> 3 x 2 =  6 
--------------------------------------------------------
                                                Summe 11
11 = 2 mod 3

ergo:
0x000003E6 = 2 mod 3

[U.G. L. (dlchnr)]

matthias schrieb:
> Also 2^32 = 4 294 967 296 -1 431 655 765 = 2 863 311 531. Aber wie
> entsteht dieses 1 431 655 765?

https://en.wikipedia.org/wiki/Division_algorithm#Division_by_a_constant

[Michael W. (Gast)]

Liesse sich so eine Division nicht auf einem FPGA durch Parallelisieren 
etwas beschleunigen?

[matthias (Gast)]

namt
Mein Idee wäre auch eine Bruteforce Primzahlzerlegung von 128-Bit-Zahlen 
dadurch zu beschleunigen, dass man nicht wie üblich durch alle 
Primzahlen kleiner als die Wurzel der Zahl nacheinander teilt, etwa 
988651 durch 2,3,5,7,11,...995.
Sondern gleich durch die ersten 8 oder mehr auf einmal teilt, weil man 
z.B. eine 8 core AM3+ CPU hat.
Wobei 988651 selbst Prim ist. Die ersten Primes bis 1000000 oder so 
könnte man vorbereitet halten und erst nachsehen ob sie in dieser LUT 
ist, wenn nicht, dann die ersten 8 Divisionen parallel stzarten. Wenn 
eine aufgeht deren Divisionsergebnis als neuen Startwert, oder so..
Mj

[Jürgen S. (engineer)]

matthias schrieb:
> Mein Idee wäre auch eine Bruteforce Primzahlzerlegung ...
> dadurch zu beschleunigen, dass man ...
> ... die ersten 8 oder mehr auf einmal teilt
Wir haben das mal in den 90ern auf einem Linux-Cluster mit 256 und dann 
512 Rechnern laufen lassen. Das lief auch so, daß alte, bereits 
gefundene Zahlen gespeichert blieben und über einen Hash-Algo gesucht 
wurden, um sie zu nutzen.

Ich habe sowas mal für eine FPGA-Lösung auf einem anderen Gebiet 
gemacht. Das Problem: Die Chips heute sind schweineschnell, kriegen aber 
die Speicherbandbreite nicht hin, um alles zu speichern und zu laden. 
Selbst mit den schnellsten DDR4-Controllern ist mal limitiert, wenn es 
um den Vergleich mit FPGA-Applikationen geht, die auf Block-Rams 
arbeiten. Leider haben die FPGAs für solche APPs (noch) viel zu wenig 
Speicher.

Markus W. schrieb:
> Liesse sich so eine Division nicht auf einem FPGA durch Parallelisieren etwas 
beschleunigen?
Sicher, man kann beim Prüfen auf Teilbarkeit mehrere Annahmen machen und 
sich dann für die übernächste Stufe das Ergebnis heraussuchen, das durch 
die Stufe zuvor bestätigt wurde. Ich habe z.B. eine Wurzel, die 4 Wege 
macht und damit 2 Bits in einem Schritt ermittelt.

[matthias (Gast)]

Jürgen S. schrieb:
> Markus W. schrieb:
>> Liesse sich so eine Division nicht auf einem FPGA durch Parallelisieren etwas
> beschleunigen?
> Sicher, man kann beim Prüfen auf Teilbarkeit mehrere Annahmen machen und
> sich dann für die übernächste Stufe das Ergebnis heraussuchen, das durch
> die Stufe zuvor bestätigt wurde. Ich habe z.B. eine Wurzel, die 4 Wege
> macht und damit 2 Bits in einem Schritt ermittelt.

Was ich noch suche, ist ein Algorithmus bzw. einen schnelle asm x86 
Methode, 128 Bit Zahlen zu multipliziern bis hin zu  256 bit Grösse also 
Ymm Register: sagen wir ymm1:= ymm2*ymm3
Leider rechnen auch die ymm Register nur mit den Quadwords soweit ich 
das sehen kann.
Gute Seite ist http://www.felixcloutier.com/x86/ Vielleicht habe ich was 
übersehen..
Ich dachte an den Karazuba o.ä. Algorithmus.
Passt jetzt nicht 100% in den Thread aber immer noch sehe ich da 
vielleicht zu optimistisch Möglichkeiten.

Es gibt auch noch 
https://de.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen-Algorithmus, und 
andere.
Wie man eben 2 8 stellige Dezimalzahlen multipliziert: 12345678 * 
75312452,  Schulmethode, so müsste man halt ohne splitting der 256 
grossen Register auf 32 oder auch 64 Bit Teile der ymm Register 
zugreifen und etwa 0x098712BF * 0x13FD01A1 intelligent berechnen.
Jemand n Ansatz?
M.J.