Schnellere Ganzzahldivision, wenn der Nenner bekannt ist?

Ich arbeite an GPU-Gerät, die sehr hohe Division ganzzahlige Latenz hat, mehrere hundert Zyklen. Ich möchte Divisionen optimieren.Schnellere Ganzzahldivision, wenn der Nenner bekannt ist?

Alle Divisionen nach Nenner, die in einer Menge {1,3,6,10}, aber Zähler ist eine Laufzeit positive Wert, etwa 32000 oder weniger. Aufgrund von Speichereinschränkungen ist die Nachschlagetabelle möglicherweise keine gute Option.

Können Sie an Alternativen denken? Ich habe gedacht, Float Point Inverses zu berechnen und diese zu verwenden, um Zähler zu multiplizieren.

Danke

PS. Danke Leute. Bit-Shift-Hack ist wirklich cool. von Abrundungs zu erholen, verwende ich folgenden C-Segment:

// q = m/n 
q += (n*(j +1)-1) < m;

Quelle

2010-04-11 Anycorn

a/b=a*(1/b) 
x=(1<<16)/b 
a/b=(a*x)>>16

Können Sie eine Nachschlagetabelle für die Nenner erstellen? da Sie 15-Bit-Zähler sagte, könnten Sie 17 für die Verschiebungen verwenden, wenn alles ohne Vorzeichen 32 Bit:

a/b=a*((1<<17)/b)>>17

Je größer die Verschiebung desto geringer ist der Rundungsfehler. Sie können einen Brute-Force-Check durchführen, um zu sehen, wie oft dies tatsächlich falsch ist.

Quelle

2010-04-11 04:54:33 drawnonward

ja, das ist klein genug. Danke – Anycorn

Ich bekomme Rundungsfehler, aber ich habe eine Möglichkeit, das korrekte Ergebnis wiederherzustellen. Vielen Dank – Anycorn

Für Rundungsfehler, könnten Sie versuchen, die klassische addieren Hälfte vor dividieren, die in diesem Fall wäre a/b = (a * ((1 << 16)/b) + (1 <<15))>> 16 – drawnonward

Der Standard eingebettete Systeme zerhacken hierfür ist, um 1/N eine ganze Zahl der Division durch N in einem Festkommamultiplikation zu konvertieren.

Unter der Annahme von 16 Bits kann 0.33333 als 21845 (dezimal) dargestellt werden. Multiplizieren Sie, geben Sie ein 32-Bit-Ganzzahlprodukt, und schieben Sie 16 Bit nach unten.

Sie werden fast sicher einige Abrundung (Trunkierung) Fehler auftreten. Dies kann oder kann nicht etwas sein, mit dem Sie leben können.

Es könnte sich lohnen, Ihre GPU scharf zu betrachten und zu prüfen, ob Sie eine schnellere Integer-Divisionsroutine handcodieren können, indem Sie Ihre Kenntnisse über den eingeschränkten Bereich des Zählers nutzen.

Quelle

2010-04-11 04:52:28

Abschneiden ein Problem wäre, ich brauche Istwerten. Jedoch denke ich, dass ich damit zurechtkommen kann, indem ich auf Rundung und inkrementierendes Ergebnis überprüfe, wenn es – Anycorn

danke gefunden wird. Das ist sehr nützlich für mich. – Anycorn

Man kann in den meisten Fällen Rundungsfehler vermeiden, indem man mit einem Wert multipliziert, der um eins größer ist als der abgerundete Reziprokwert (21846 bei 1/3 mit 16 Bits). – supercat

Das Buch "Hacker's Delight" by Henry Warren enthält ein ganzes Kapitel über die Ganzzahldivision durch Konstanten, einschließlich Techniken, die eine ganzzahlige Division in eine Multiply/Shift/Add-Reihe von Operationen umwandeln.

Diese Seite berechnet die magischen Zahlen für die Multiplikation/Shift/Operationen hinzufügen:

http://www.hackersdelight.org/magic.htm

Quelle

2010-04-11 06:16:43

Schnellere Ganzzahldivision, wenn der Nenner bekannt ist?

Antwort

Verwandte Themen