Guten Morgen, da das Thema ja ein bisserl Mathe ist, hab ich es hier gepostet :) Ich hab einen Dividierer (im FPGA) und der ist langsam (ca 42 clock-zyklen @ 100MHz). Da immer nur durch 27 dividiert wird, könnte man auf die Idee kommen, mittels Festpunktarithmetik mit dem Kehrwert zu multiplizieren. Mich würde nun interessieren, ob jemand weiß, wieviele "Nachkommastellen" man benötigt, damit das Ergebnis vor'm Komma nach der Multiplikation immer korrekt ist. Beispiel 27/27: 27*2**16 * trunc((1/27 * 2**16)) / (2**32) = 0,9998931884765625 Sieht soweit nicht schlecht aus, aber runden müsste man wohl noch. Was denkt ihr? Reichen 16Bit? Viele Grüße, Mampf
:
Bearbeitet durch User
Wie ist dein Eingangswertebereich? (16 Bit? 0... 65535?) Wie die Ausgabe? Also auch wieviel Bits und was bedeutet 1lsb. Dann kannst du ausrechnen, wie du ohne Fehler hinkommst.
Uns nicht trunc, sondern aufrunden, zumindest bei Insignien. Sonst machst Du zweimal trunc
A. S. schrieb: > Wie ist dein Eingangswertebereich? (16 Bit? 0... 65535?) Das sind 32Bit. Also quasi 32+16Bit Nachkomma wären dann 48Bit. > Wie die Ausgabe? Also auch wieviel Bits und was bedeutet 1lsb. Die ist auch 32Bit. Den Nachkomma-Teil würde ich wegschneiden (nach dem Runden) und würde dann durch Subtraktion den Rest berechnen (brauch leider beides). Die Frage nach dem LSB verstehe ich nicht ganz. Im Prinzip soll ein 32Bit int reingehen und ein 32Bit int rauskommen mit 5bit Rest. A. S. schrieb: > Uns nicht trunc, sondern aufrunden, zumindest bei Insignien. Sonst > machst Du zweimal trunc Du meinst das trunc aus dem Beispiel? Das hab ich nur verwendet, damit es mir die Nachkomma-Stellen der Nachkomma-Stellen abschneidet. Sonst wär 1 rausgekommen. Vermutlich geht bei Fixpunkt runden genauso wie bei 32bit ints? Also 0,5 addieren und dann trunc?
Ah wieder was gelernt ... Der Nachkomma-Teil muss mindestens 32Bit haben, damit das klappt. leider scheint __uint128_t mit dem GCC nicht zu funktionieren, sodass ich das nicht mal testen kann :/
So jetzt hab ich es ... Also ... die Anzahl der Bits für den Divisor müssen 32 + 5 + 1 sein (32Bit Input, 6Bit Divisor (5 für 0-27 + 1Bit für das +0,5) mit einer Nachkommastelle) Man addiert nach der Multiplikation mit 2**30 (eben diese 0,5) und truncated. Dann kommt das richtige raus :-)
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | #include <stdint.h> |
4 | #include <math.h> |
5 | int main() { |
6 | __uint128_t shift2 = 36; |
7 | __uint128_t divisor = (__uint128_t) (((__uint128_t)1<<shift2) / 27.0); |
8 | // printf("%032llx\n", (long long unsigned int) divisor);
|
9 | |
10 | for (int i=0;i<100000;i++) { |
11 | __uint128_t dividend = rand(); |
12 | |
13 | __uint128_t result = dividend * divisor; |
14 | result += ((__uint128_t)1<<30); |
15 | result >>= (__uint128_t) (shift2); |
16 | |
17 | uint32_t cmpres = (uint32_t) dividend / 27; |
18 | |
19 | if ((uint32_t) result != cmpres) { |
20 | printf("error\n"); |
21 | printf("%d %d\n", (int) result, cmpres); |
22 | }
|
23 | }
|
24 | return 0; |
25 | }
|
Du kannst auch den GCC fragen, wie er das Problem lösen würde:
1 | y = x / 27; |
wird übersetzt zu:
1 | movl x(%rip), %ecx |
2 | movl $795364315, %edx |
3 | movl %ecx, %eax |
4 | mull %edx |
5 | subl %edx, %ecx |
6 | shrl %ecx |
7 | addl %ecx, %edx |
8 | shrl $4, %edx |
9 | movl %edx, y(%rip) |
Die magische Konstante 795364315 ist dabei gleich ceil(5 * 2**32 / 27). Rückübersetzt nach C entspricht dieser Code dem folgenden:
1 | uint32_t tmp = (uint64_t)x * 795364315 >> 32; |
2 | y = (tmp + ((x - tmp) >> 1)) >> 4; |
Im Vergleich zu deiner Lösung ist hier die magische Konstante nur 30 statt 32 Bit groß, dafür werden aber insgesamt mehr Rechenoperationen benötigt. Auf dem PC ist deine Lösung vermutlich die effizientere (die 128 Bit sind unnötig, 64 Bit für das Multiplikationsergebnis und 32 Bit für den Rest sollten genügen). Welche Lösung auf dem FPGA (wo die Shifts nichts kosten und die Addierer exakt auf die jeweils benötigte Bitzahl optimiert werden können) bzgl. der Anzahl der Logikblöcke die bessere ist, müsste noch untersucht werden. Wie kommst du eigentlich in
1 | result += ((__uint128_t)1<<30); |
auf die 1<<30? Damit kompensierst du wohl die Tatsache, dass divisor auf Grund der endlichen Bitzahl etwas zu klein ist, denn ohne diese Korrektur wären die Ergebnisse teilweise falsch. Dur erwähnst in deinen Beiträgen auch immer wieder das Thema Runden. Aber dein Verfahren liefert ja – genauso wie auch der C-Ausdruck dividend/27 – immer abgerundete Ergebnisse. Damit kann der Wert 1<<30 also nichts zu tun haben, zumal für klassisches Runden (d.h. Aufrunden bei einem Nachkommaanteil von ≥0.5) dieser Wert nicht 1<<30, sondern 1<<35 sein müsste.
Yalu X. schrieb: > Dur erwähnst in deinen Beiträgen auch immer wieder das Thema Runden. > Aber dein Verfahren liefert ja – genauso wie auch der C-Ausdruck > dividend/27 – immer abgerundete Ergebnisse. Damit kann der Wert 1<<30 > also nichts zu tun haben, zumal für klassisches Runden (d.h. Aufrunden > bei einem Nachkommaanteil von ≥0.5) dieser Wert nicht 1<<30, sondern > 1<<35 sein müsste. Glaube das ist nicht ganz richtig ... Da der Divisor ja schon ge-truncated wird, muss man runden, da 27/27 sonst zB 0.999999 geben könnte (und auch tut). Das 1<<30 kommt wohl daher: Divisor muss 36bit haben ... 32Bit Größe, weil der Dividend so groß ist, 5Bit Größe, weil der Divisor so groß ist und noch 1Bit Nachkomma des Divisors zum Runden. Dieses letzte Bit ist dann genau auf der Stelle 1<<30 und ohne das sind oft die Ergebnisse falsch. Mathematisch kann ich das nicht beweisen, aber es gibt ein konsistentes Muster. Aber geniale Idee, den GCC zu befragen, wie er das machen würde. In der Realität hat bei mir der Dividend 40Bit, der Fixpunkt-Divisor damit 46Bit und die +1 kommt auf das Bit 40. Da reichen dann leider die 64Bit nicht mehr aus - aber dem FPGA ist das eh fast egal :)
:
Bearbeitet durch User
Machen wir es einfacher: Schreib Du hin, welche Division du machen möchtest, und ich schreib das als Multiplikation.
A. S. schrieb: > Machen wir es einfacher: > > Schreib Du hin, welche Division du machen möchtest, und ich schreib das > als Multiplikation. Können wir probieren :) trunc(dividend / divisor). Der Dividend hat 40Bit, der Divisor 5Bit (fester Wert 27). Im FPGA läuft es schon. Allerdings schafft das FPGA 40*46Bit Multiplikation nicht ohne 1-stufige Pipeline @ 100MHz. Der eine Clock-Cycle ist nicht so wichtig, aber wenn es ohne geht, wäre natürlich besser :)
Mampf F. schrieb: > 40Bit Also Werte von 1 bis 1 Billionen? Und das Ergebnis dann Werte von 1 bis 30E6?
Mampf F. schrieb: > trunc(dividend / divisor). Der Dividend hat 40Bit, der Divisor 5Bit > (fester Wert 27). So gehts mit nur einer Multiplikation ohne zusätzliche Addition:
wobei
Der Faktor k ist 39 Bit lang. Folgendes Testprogramm sucht das kleinste x, für das der obige Ausdruck ein falsches Ergebnis liefert:
1 | #include <stdio.h> |
2 | #include <stdint.h> |
3 | |
4 | #define N 43
|
5 | #define K 325781223045 // = ⌈2⁴³/27⌉
|
6 | |
7 | int main(void) { |
8 | for(uint64_t x=0; ; x++) { |
9 | uint64_t y1 = x / 27; |
10 | uint64_t y2 = ((__uint128_t)x * K) >> N; |
11 | if(y1 != y2) { |
12 | printf("Fehler bei x=%lu y1=%lu y2=%lu\n", x, y1, y2); |
13 | break; |
14 | }
|
15 | }
|
16 | }
|
Ausgage (nach ca. 20 Minuten):
1 | Fehler bei x=1256584717466 y1=46540174720 y2=46540174721 |
Somit rechnet das Verfahren bis einschließlich x=1256584717465 korrekt, was oberhalb der gewünschten 2⁴³-1=1099511627775 liegt. > Im FPGA läuft es schon. Allerdings schafft das FPGA 40*46Bit > Multiplikation nicht ohne 1-stufige Pipeline @ 100MHz. Der eine > Clock-Cycle ist nicht so wichtig, aber wenn es ohne geht, wäre natürlich > besser :) Die obige Multiplikation lässt sich in 16 Additionen/Subtraktionen zerlegen, die in 4 sequentiell aufeinanderfolgenden Ebenen ausgeführt werden können. Die gesamte Multiplikation benötigt also ohne Pipelining das Vierfache der Zeit einer einzelnen Addition/Subtraktion.
Im Buch Hackers Delight ist der Algorithmus zum errechnen der Inversen für konstante Divisionen dokumentiert. Auf der Homepage kann man sich auch die Konstanten direkt errechnen lassen. https://www.hackersdelight.org/ https://www.hackersdelight.org/magic.htm
Beitrag #5703563 wurde vom Autor gelöscht.
Yalu X. schrieb: > wobei > k=⌈24327⌉=325781223045 > k=\left\lceil\frac{2^{43}}{27}\right\rceil=325781223045 > > Der Faktor k ist 39 Bit lang. Ahja, das Ceiling ist interessant! Wenn ich die Konstante um 1 erhöhe, dann muss ich später dieses 1<<40 addieren nicht mehr machen. Ansonsten sieht es schon ähnlich aus zu dem, was ich gemacht habe ... Größtenteils anders geschrieben :) Vielen Dank!
Mampf F. schrieb: > Da immer nur durch 27 dividiert wird, könnte man auf die Idee kommen, > mittels Festpunktarithmetik mit dem Kehrwert zu multiplizieren. Das ist aber jetzt nicht dein Ernst? Das ist das erste, was man tut, um sich Divisionsrechenleistung zu sparen. > Wenn ich die Konstante um 1 erhöhe, dann muss ich später dieses 1<<40 > addieren nicht mehr machen. Das tut indirekt der Compiler für dich und ob das die jeweils optimale Lösung fürs Runden in FPGAs ist, sei dahin gestellt. > Ansonsten sieht es schon ähnlich aus zu dem, was ich gemacht habe ... > Größtenteils anders geschrieben :) Nun ja.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.