Forum: FPGA, VHDL & Co. Kubikwurzel bilden


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 BiBi (Gast)


Lesenswert?

Für die Quadratwurzel gibt es Cores und das Heronverfahren (siehe auch 
Quake-code), das im allgemeinen Fall ein Newtonverfahren ist und im 
Prinzip für jede Wurzel taugt.

Leider muss man je nach Güte des Schätzwertes mehrere mal iterieren, bis 
man zu einer guten Wurzel kommt. Da bei jeder Iteration eine Division 
auftaucht, taugt das nicht un bedingt für eine Implementierung in VHDL.

Wie berechnet man am schnellsten eine Kubikwurzel?

von Matthias N. (nippey)


Lesenswert?

Da man das alles als Potenz sehen kann..
(Die 2. Wurzel aus x ist x hoch 1/2)
.. könntest du das alles mit Reihenentwicklungen machen.
Die Methode funktioniert in C gut, aber ich vermute, dass sie nicht 
wirklich für HDL geeignet ist..

[Ge-Guttenbergt von Wikipedia: 
http://de.wikipedia.org/wiki/Potenz_(Mathematik); 
http://de.wikipedia.org/wiki/Logarithmus]

Damit hättest du NUR noch Divisionen durch gerade Zahlen ;)
Viel Erfolg noch!

von BiBi (Gast)


Lesenswert?

Das mit der Potenz und Logarithmus hatte ich auch schon angedacht, 
allerdings hatte ich nicht an eine Reihenentwicklung gedacht. Das geht 
in VHDL durchaus einfach, aber die Nenner steigen nicht sonderlich 
schnell, weswegen das nicht gut konvergiert.

von Lothar M. (lkmiller) (Moderator) Benutzerseite


Lesenswert?

BiBi schrieb:
> Wie berechnet man am schnellsten eine Kubikwurzel?
Weil du nur nach der Geschwindigkeit und nicht nach dem 
Ressourcenverbrauch gefragt hast: über eine Tabelle.

von Lustiger Denkermolch (Gast)


Lesenswert?

Mach doch einfach eine binäre Suche, oder auch eine "intelligente" 
interpolierende Suche. Gerade bei Ganzzahlen geht das schön flott; je 
höher die Ordnung der Wurzel, desto flotter...

von BiBi (Gast)


Lesenswert?

Ich würde gerne Kubikwurzeln aus Zahl ziehen, die wenigsten 32 Bit 
Breite haben - eher wahrscheinlich 48. Da wird es mit den Tabellen etwas 
schwer.

von D. I. (Gast)


Lesenswert?

und wie genau brauchst du die wurzel? Also nur Ganzzahlanteil oder 
wieviele Nachkommastellen?

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

In VHDL als tempoorientierte Lösung geht das am Besten über exp/log im 
Binärformat, also ld = logarithmus dualis, statt mit dem natürlichen ln.

Wenn es per SW sein soll, dann würde ich lieber gleich eine 
Potenzreihenentwicklung der dritten Wurzel nehmen.

von Dr. Mathematicus (Gast)


Lesenswert?

Hast Du vlt. auch Mathematica oder Maple? Dann könntest du über ein 
Funtionswindow auch Berechnungen dieser Programme durch führen lassen, 
da gibt es auch für C, Pascal, VDHL, Cobol, Fortran... fertige Patches. 
Was für ein Basisbetriebssystem hast Du?

von BaBa (Gast)


Lesenswert?

Ich programmiere mit CAN-Bus, geht dass damit auch?

von Dr. Mathematicus (Gast)


Lesenswert?

BaBa schrieb:
> Ich programmiere mit CAN-Bus, geht dass damit auch?

Ja klar, darum heisst es ja cann-bus, weil man damit alles machen "can".

Damit kannst Du sogar Lichterketten mit ansteuern und aus der Anzahl der 
verwendeten Leuchtmittel die Kubikwurzel ziehen, dass ist doch toll, 
oder?

von ... (Gast)


Lesenswert?

Das Hauptproblem bei der Reihenentwicklung ist die Geschwidnigkeit, mit 
der der Wert gegen das Ergebnis konvergiert. Aus dem Grund normiert man 
den Wert und berechnet davon dann die eigentliche Funktion. Das ist 
alles sehr gut hier beschrieben:

yacas.sourceforge.net/Algo.book.pdf

Meistens funktioniert auch die Newton-Iteration sehr gut. Also einfach 
mit Newton-Iteration die Nullstelle von x^(1/3)-y berechnen. Einen guten 
Startwert kann man mit einem Polynom berechnen.

von Dr. Mathematicus (Gast)


Lesenswert?

... schrieb:
> Meistens funktioniert auch die Newton-Iteration sehr gut. Also einfach
>
> mit Newton-Iteration die Nullstelle von x^(1/3)-y berechnen. Einen guten
>
> Startwert kann man mit einem Polynom berechnen.

Da muss ich Dir recht geben. Ich sehe das auch so. Gut gemacht.

von Yalu X. (yalu) (Moderator)


Lesenswert?

Ich habe hier mal einen Algorithmus zusammengebastelt, der aus einer
ganzen Zahl x den ganzzahligen Anteil von x**(1/3) berechnet. Er ver-
wendet nur Additionen und Schiebeoperation mit konstanter Schiebeweite
<= 3, so dass er gut in Hardware implementierbar sein sollte. Da ich
kein VHDL kann und in Verilog nicht besonders fit bin, habe ich den
Algorithmus in Python aufgeschrieben:
1
n = 16
2
3
def cbrt(x):
4
  y3 = y2 = y1 = 0
5
  y0 = 1 << 3*(n-1)
6
  while True:
7
    s = y3 + (y2+y1 << 1) + y2 + y1 + y0
8
    if s <= x:
9
      y3 = s
10
      y2 += (y1<<1) + y0
11
      y1 += y0
12
    y0 >>= 3
13
    if y0 == 0:
14
      return y1
15
    y1 >>= 2
16
    y2 >>= 1
17
18
print(cbrt(280137072301568))
19
# Ergebnis: 65432

n ist ein konstanter Parameter und gibt die Bitbreite des Ergebnisses
an. Der Radikand x hat somit 3·n Bits. y0, y1, y2 und y3 sind Register,
die ebenfalls 3·n Bits breit sind. Die Schleife wird n-mal durchlaufen.
Ordnet man die Rechenoperationen innerhalb der Schleife geeignet an, so
dass pro Durchlauf die vier Register genau einmal beschrieben werden,
sollte das Ergebnis also in n Taktzyklen verfügbar sein.

Der Algorithmus dürfte in ähnlicher Form auch für Festkommazahlen imple-
mentierbar sein.

Edit: Für die Register y0, y1 und y2 genügen 3·n-2 Bits.

von Detlef _. (detlef_a)


Lesenswert?

Interessantes Verfahren. Kannst Du noch einen Satz dazu sagen, woher das 
stammt und worauf das beruht?

Ansonsten liefert Newton für die Kubikwurzel die Iteration
x(n+1)=2/3*x(n)+S/(3*x(n)^2)

Das benötigt ne integer-Division, das will man nicht.

Cheers
Detlef

von Uwe Bonnes (Gast)


Lesenswert?

Mit aktueller Hardware wie Cortex M4 braucht man die Divisionen auch 
nicht mehr so zu fuerchten...

von BiBi (Gast)


Lesenswert?

Uwe Bonnes schrieb:
> Mit aktueller Hardware wie Cortex M4
Der cortex ist aber keine Lösung für das Thema (VHDL) - oder meinst Du 
mit dem Vorschlag einen Core im FPGA?

von Yalu X. (yalu) (Moderator)


Lesenswert?

Detlef _a schrieb:
> Interessantes Verfahren. Kannst Du noch einen Satz dazu sagen, woher das
> stammt

Das habe ich mir selber ausgedacht, ist aber garantiert nicht neu.

> und worauf das beruht?

Die Grundidee ist ganz einfach: Im Ergebniswort werden — beginnend mit
dem höchstwertigen — nacheinander die einzelnen Bits testweise auf 1
gesetzt und geprüft, ob die dritte Potenz des Ergebnisses kleiner oder
gleich dem Radikanden ist. Ist dies der Fall, wird das 1-Bit in das
Ergebnis übernommen, ansonsten bleibt das Bit 0. So wird das Ergebnis
schrittweise verbessert, bis nach dem Bearbeiten des letzten Bits der
Fehler kleiner als 1 ist.

Für die Berechnung der dritten Potenz braucht man normalerweise 2
Multiplikationen. Wenn man schnelle Multiplizierer zur Verfügung hat,
kann man die Potenz direkt berechnen, sonst geht es auch mit Additionen
und Schiebeoperationen, wenn man immer die zuletzt berechnete Potenz
mitbenutzt. Folgende Variablen werden dazu verwendet:

  y  = aktuelles Ergebnis
  z  = die dem aktuell gesetzten Bit entsprechende Zweierpotenz
  y₃ = y³
  y₂ = y²z
  y₁ = yz²
  y₀ = z³

Dabei tauchen y und z im Programm nicht explizit auf.

Wird nun ein zusätzliche Bit im Ergebnis y gesetzt, ist das neue Ergeb-
nis y+z. Die dritte Potenz davon ist

  s = (y + z)³ = y³ + 3(y²z + yz²) + z³ = y₃ + 3(y₂ + y₁) + y₀

Das ist die Formel in der ersten Zeile der While-Schleife. Die Werte y₃,
y₂, y₁ und y₀ stammen aus dem letzten Schleifendurchlauf bzw. der Initi-
alisierung vor der Schleife.

Ist s>x, d.h. das Ergebnis ist zu groß, wird das alte y beibehalten,
ansonsten wird z zu y addiert und die davon abhängigen Variablen wie
folgt aktualisiert:

  y₃ := (y + z)³  = s
  y₂ := (y + z)²z = y²z + 2yz² + z³ = y₂ + 2y₁ + y₀
  y₁ := (y + z)z² = yz² + z³ = y₁ + y₀


Das gleiche Spiel setzt sich nun mit dem nächsten Bit fort. Die Zweier-
potenz z wird also durch 2 dividiert und die Variablen abhängig davon,
wie oft der Faktor z darin enthalten ist, ebenfalls dividiert:

  y₀ := y₀ / 2³
  y₁ := y₁ / 2²
  y₂ := y₂ / 2

Bevor y₁ und y₂ dividiert werden, wird aber noch die Abbruchbedingung
z=0 bzw. y₀=0 überprüft. Ist diese erfüllt, sind alle Bits bearbeitet
worden, und das Gesamtergebnis steht in y₁.

Im Programm sind die Multiplikationen mit 2 und 3 und die Divisionen
durch 2, 4 und 8 mit Schiebeoperationen realisiert.

von MJF (Gast)


Lesenswert?

Hallo BiBi,

es gibt eine einfache Möglichkeit, die dritte Wurzel zu berechnen:

Zunächst eine Annahme, damit es sich leichter erklärt:

y = x^1/3   mit 0<=x<1

Der Eingangswert x kann auch wie folgt beschrieben werden:

x = 2^(-3*n) * x'   mit  1/8 <= x' < 1  und  n \in IN

In HW kann "n" leicht ermittelt werden, indem die Anzahl der führenden 
Nullen detektiert und "weggeshiftet" werden (Multiplexer). Die Anzahl 
der
entfernten führenden Nullen muss ein Vielfaches von 3 sein.

Für die Wurzel gilt dann:

y = x^1/3 = ( 2^(-3*n)*x' )^1/3 = 2^-n * x'^1/3

Nun muss die Wurzel nur noch für einen Eingangswertebereich zwischen 1/8 
und 1 berechnet werden. in diesem Bereich ist die Wurzel recht gutmütig,
d. h. sie kann mit einer liniearen Interpolation sehr gut genähert 
werden.
Für die Lineare Interpolation benötigt man ein RAM für Stützstellen, ein
RAM für die Steigungen einen Multiplizierer und einen Addierer.

Die Multiplikation mit 2^-n ist wieder eine Shift-Operation 
(Multiplexer).

Durch das fehlerfreie Shiften entstehen Fehler nur durch die Lineare
Interpolation. Dieser Fehler tritt immer nur relativ zum Eingangwert
auf, d.h.

\Delta y / y

ist ungefähr konstant.

Man kann die Dimension des Fehlers auch grob abschätzen. Bei einer 
Linearen Interpolation ist Fehler bei N Stützstellen ungefähr 1/N^2
(grobe Daumenregel).

Verwendest du z. B. 1024 Stützstellen, erreichst du einen relativen 
Fehler
von ca. 1/1.000.000.

Um die tatsächlichen Fehler zu bestimmen, muss man schon etwas länger
rechnen.

Dies ist keine iterative Methode, d. h. mit jedem Takt kann ein 
Ausgangswert berechnet werden.

Man kann es mit etwas mehr Aufwand auch für beliebige Wurzeln erweitern.

Gruss

Markus

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Ich komme mit dem Python Konstrukt nicht ganz klar:
s = y3 + (y2+y1 << 1) + y2 + y1 + y0

Bezieht sich der Schiebeoperator (y2+y1 << 1) auf y2 und Y1 oder nur Y1?

Ich habe mal etwas gekramt: Mit Newton geht es in der Tat recht gut, 
wenn man einen guten Startwert. Den kann man zur Basis 2 einfach 
bestimmen, wenn man die Bits etwas schiebt. Das höchstwertige einfach 
auf ein Drittel der Position, den Rest als Multiplikator oben drauf. 
Dann kann man für ein eventuell existentes Bit eines darunter noch 
feststellen, dass der Wert im Bereich von 50% liegen muss und daher die 
dritte Wurzel aus 1,5 aufmultiplizieren -> rund 1+1/8

von Yalu X. (yalu) (Moderator)


Lesenswert?

J. S. schrieb:
> Ich komme mit dem Python Konstrukt nicht ganz klar:
> s = y3 + (y2+y1 << 1) + y2 + y1 + y0

Der Vorrang der Operatoren ist gleich wie in C:

s = y3 + ((y2+y1) << 1) + y2 + y1 + y0

Das ist wiederum das Gleiche wie

s = y3 + 3 * (y2 + y1) + y0

Ich wollte mit der Aktion nur die Multiplikation wegoptimieren. Es kann
aber gut sein, dass das der VHDL-/Verilog-Compiler schon tut.

von Detlef _. (detlef_a)


Lesenswert?

Hallo,

ich habe Routinen für Quadrat- und Kubikwurzel für Integerrechnung 
implementiert und in die Codesammlung eingestellt.

Beitrag "square root and cubic root for integer and FPGA implementation"

Diese Routinen benötigen nur Shift und Addition und eignen sich damit 
gut für die Implementierung in Hardware.

Yalu, Dein Verfahren habe ich in ähnlicher Form für Quadratwurzeln bei
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
und
http://www.cc.utah.edu/~nahaj/factoring/isqrt.legalize.c.html
gefunden.

Für Kubikwurzeln habe ich es in C implementiert und auch in eine Form 
modifiziert, die mehr Richtung der genannten Referenzen geht: mit einem 
remainder anstelle der eigentlichen Werte.

War großer Spaß gewesen, ordentlich was bei gelernt, danke für die 
Anregung. Die Idee, was 'Bit für Bit' zu iterieren hat auch woanders 
Potential, glaube ich.

Cheers
Detlef

von Jan (Gast)


Lesenswert?

Hast Du das so gedacht, dass dann in HW eine FSM laufen soll oder ein 
soft core soll das so in der Synthese aufgezogen werden?

von Detlef _. (detlef_a)


Lesenswert?

Das kann man im FPGA auf verschiedene Weisen ausführen, ich bin da nicht 
besonders kundig. Kubikwurzel dauert für 30Bit Zahl 10 Runden, schneller 
kann man nicht werden. Ansonsten läßt sich die Verarbeitung beliebig 
serialisieren, parallelisieren und pipelinen.

Cheers
Detlef

von Mohan (Gast)


Lesenswert?

Kannst Du mir helfen mit Matlab Simulink schematic fur die dritten 
wurzel in  FPGA, sogar mit einem Beischpiel zu bilden ?

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Ich glaube, an der Stelle ist Simulink Kanonen auf Spatzen. Das geht mit 
einer einfachen Ausgleichsrechnung oder händischen Potenz mit "hoch 
1/3", im Zweifel über Logarithmus und CORDIC. Kommt drauf an, ob es 
schnell, schnell programmiert oder einfach oder einfach programmiert 
oder klein sein soll. Am kleinsten und Stromsparendsten ist sicher ein 
iterativer Schätzer, mit Newton und der ersten Ableitung.

von frk (Gast)


Angehängte Dateien:

Lesenswert?

Ich habe heute mal fix das ganze in VHDL gehackt. Es wird wohl keinen 
Schönheitspreis gewinnen. Auf dem FPGA habe ich es nicht getestet und 
auch in ModelSim nur ganz rudimentär getestet.

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Da müsste noch pipelining rein, meine ich.

von Markus F. (mfro)


Lesenswert?

Jürgen S. schrieb:
> Da müsste noch pipelining rein, meine ich.

Ist doch schon drin?

von frk (Gast)


Angehängte Dateien:

Lesenswert?

Jürgen S. schrieb:
> Da müsste noch pipelining rein, meine ich.

Ja, das sollte gehen. Bzw.: Ja, das geht (siehe Anhang).

Ich hatte noch ein Problem mit dem cubedbit, weil Integer in VHDL auf 32 
Bit begrenzt sind und ich das Bit als Integer berechne bevor ich es in 
ein unsigned umwandele. Ich habe das jetzt nachgebessert und noch eine 
Rundung des Ergebnisses hinzugefügt.

Bitte entschuldigt, wenn ich Fragen nur mit großer Verzögerung 
beantworte. Ich bin aktuell sehr beschäftigt und wollte eigentlich nur 
schnell den Code hier zur Verfügung stellen, den ich sowieso schon für 
mich geschrieben habe, um Leuten zu helfen, denen VHDL nicht so schnell 
von der Hand geht.

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Markus F. schrieb:
> Jürgen S. schrieb:
>> Da müsste noch pipelining rein, meine ich.
>
> Ist doch schon drin?
Nicht so, wie ich mir das denke :-)

frk schrieb:
> Ja, das sollte gehen.
Die Art des Rundens würde ich mir nochmal ansehen.

Warum wird das überhaupt gemacht? Ich würde noch die Nachkommastellen 
prozessieren.

: Bearbeitet durch User
von frk (Gast)


Lesenswert?

Jürgen S. schrieb:
>>> Da müsste noch pipelining rein, meine ich.
>>
>> Ist doch schon drin?
> Nicht so, wie ich mir das denke :-)
Wie denkst du dir das denn? Du kannst in jedem Takt einen Wert am 
Eingang reingeben und nach x Zyklen fällt das Ergebnis hinten raus. 
Während das eine verrechnet wird kannst du aber bereits die nächsten 
Werte reingeben. Dafür braucht man natürlich viel "parallele" Logik bzw. 
hintereinandergeschaltet mehrfach die gleiche Logik, aber dafür musst du 
nicht die komplette Datenverarbeitungs-Pipeline auf dem FPGA anhalten, 
um auf das Ergebnis hier zur warten, sondern kannst einfach in jedem 
Takt ein Datum verarbeiten. Performance-technisch ist das das Optimum.

Jürgen S. schrieb:
> Die Art des Rundens würde ich mir nochmal ansehen.
>
> Warum wird das überhaupt gemacht? Ich würde noch die Nachkommastellen
> prozessieren.
Gemacht wird das, weil ich für meine Anwendung vorher eine 
Software-Implementierung gemacht habe, um zu sehen, ob ich die 
notwendige Genauigkeit erreiche. Nur mit Rundung war das möglich. (Ja, 
man hätte das auch in Matlab machen können, aber mir geht C(++) einfach 
schneller von der Hand.)

Und was der Fehler sein soll, erschließt sich mir nicht. Dadurch, dass 
am Anfang drei Nullen hinzugefügt werden, erschafft man eine 
Festkommazahl, die 3 binäre Nachkommastellen hat (Präzision in dezimal = 
0,125).
Wenn du das jetzt nicht als Festkommazahl, sondern einfach als Ganzzahl 
betrachtest, entspricht das Hinzufügen von drei Nullen einer 
Multiplikation mit 8. Da aber
, gilt auch
. Um auf das korrekte Ergebnis zu kommen, müsste man also noch einmal 
durch 2 teilen. Daraus folgt, dass wir jetzt noch eine binäre 
Nachkommastelle haben. Als Festkommazahl können also Werte y.0 und y.5 
abgebildet werden. Das Ergebnis runde ich jetzt mit "Rounding to Nearest 
Integer, Half up": https://en.wikipedia.org/wiki/Rounding#Round_half_up. 
Das ist eigentlich die Standard-Methode zum Runden. Beispiel:
Um die Addition mit 0,5 zu erreichen, addiere ich einfach ein Bit hinzu, 
denn wie vorher beschrieben hat das Ergebnis der CubeRoot-Berechnung 
genau eine binäre Nachkommastelle. Das heißt das LSB entspricht 0,5.
Flooring passiert dann beim runtershiften automatisch, weil einfach das 
LSB abgeschnitten wird.

von frk (Gast)


Lesenswert?

frk schrieb:
> Wenn du das jetzt nicht als Festkommazahl, sondern einfach als Ganzzahl
> betrachtest, entspricht das Hinzufügen von drei Nullen einer
> Multiplikation mit 8.

Was eigentlich unnötig kompliziert ist, denn
 ist natürlich auch 0,5. Warum einfach denken, wenn es auch kompliziert 
geht?

von frk (Gast)


Angehängte Dateien:

Lesenswert?

Es war übrigens nicht zu erwarten, dass das Timing besonders gut ist, 
wenn man die ganze Berechnung in einen riesigen Block klatscht. Da ich 
das mittlerweile auch in mein Design integriert und synthetisiert habe, 
musste ich das Timing-Problem lösen und jetzt läuft das auf einem Arria 
10 mit mindestens 266 MHz. Code: Siehe Anhang.

von Was habt ihr eigentlich gelernt? (Gast)


Lesenswert?

Warum so kompliziert?

Als ich noch zur Schule ging haben wir das Quadrat-Wurzelziehen per Hand 
gelernt.

Danach kam die Kubikwurzel. Das ging auch moch von Hand und war nicht 
schwierig. Ohne Tabellen und Computer. Ungelogen.

Das heisst es muss dann mit Computer noch schneller gehen.

von frk (Gast)


Lesenswert?

Ich muss 798 Millionen Mal pro Sekunde (3 x 266 MHz) die Kubikwurzel aus 
einer Zahl zwischen 0 bis ca. einer viertel Billiarde (48 Bit Zahl) 
ziehen. Das ganze per Hand auszurechnen ist einfach keine sinnvolle 
Option. Hier kommst du nicht einmal mit einer Software-Lösung weiter 
(was ja der Grund ist warum ich das im FPGA implementiere). Der Spaß 
geht sogar noch weiter, weil die Performance noch lange nicht reicht. 
Deswegen werde ich die ganze Pipeline im FPGA noch parallelisieren, um 
dann hoffentlich (wenn das auf den FPGA drauf passt) 39,9 Milliarden Mal 
pro Sekunde die Kubikwurzel ziehen zu können (50 x 3 x 266 MHz). Wenn du 
einen Vorschlag hast wie das effizienter geht als mit dem VHDL-Code, den 
ich hier gepostet habe, bin ich für Vorschläge offen.

Beitrag #6422036 wurde von einem Moderator gelöscht.
von frk (Gast)


Lesenswert?

Faktisch Galaktisch schrieb im Beitrag #6422036:
> "798 Millionen Mal pro Sekunde (3 x 266 MHz) die Kubikwurzel aus" da
> kann etwas nicht stimmen

Wir kommen hier nicht weiter, wenn du immer so schwammige Sachen 
schreibst. Du musst schon konkret sagen warum du glaubst, dass das nicht 
stimmen kann.

Ich habe so ein bisschen den Verdacht, dass du dich nicht wirklich mit 
Datenverarbeitung auskennst. Deswegen hier ein Beispiel, das zwar nicht 
mein Anwendungsfall ist, aber mit dem man das Problem ausreichend gut 
illustrieren kann: Wenn du ein Video in 8k (4320x8192) für die 
Darstellung auf einem Display mit 100Hz verarbeiten willst, dann musst 
du 4320x8192x100=3.538.944.000 (ca. 3,5 Mrd.) Pixel pro Sekunde 
verarbeiten. Wenn dein Datenverarbeitungssystem nicht in der Lage ist so 
schnell die notwendige Farbraumtransformation auszuführen (für die die 
Berechnung der Kubikwurzel notwendig ist), dann stottert das Bild. Dem 
Zuschauer wird das überhaupt gar nicht gefallen. Die Anforderung in dem 
Fall ist also 3,5 Mrd. Berechnungen pro Sekunde durchführen zu können.

Wenn man jetzt ein Video deutlich schneller als in Echtzeit analysieren 
möchte (was eher meinem Anwendungsfall entspricht), dann muss man 
natürlich noch schneller sein. Wenn dein 8k Video aus dem Beispiel 60 
Minuten lang ist und du willst das Video in 6 Minuten analysieren 
können, dann musst du schon 10 * 3,5Mrd. = 35Mrd. Berechnungen pro 
Sekunde durchführen. Wie gesagt: Händische Berechnung kannst du hier 
vergessen.

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

frk schrieb:
>> Nicht so, wie ich mir das denke :-)
> Wie denkst du dir das denn?
Mit einer look-ahead pipeline und doppelt selektivem Verwurf

> Du kannst in jedem Takt einen Wert am
> Eingang reingeben und nach x Zyklen fällt das Ergebnis hinten raus.
Ja, bei dem inzwischen geposteten Code scheint das so zu sein, es wäre 
aber zu klären, wie schnell der Core das das dann kann.

Man muss ja nicht zwingend nur ein Bit pro Takt ausrechnen lassen.

Was habt ihr eigentlich gelernt? schrieb:
> Als ich noch zur Schule ging haben wir das Quadrat-Wurzelziehen per Hand
> gelernt.

Willkommen im Club! Und der Einwirf ist auch so schlecht nicht, denn in 
der Tat kann man mit dem schriftlichen Dividieren und Multiplizieren 
sehr weit kommen. Das ist geradezu prädestiniert, um es in FPGAs zu 
gießen - macht nur heute keiner mehr.

Gleichwohl ist frk's code schon die richtige Richtung. Ich denke nur, 
dass man das noch optimieren muss, es sei denn, er hat Zeit, bis zu 48/2 
= 24 Takte auf das Ergebnis zu warten.

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

frk schrieb:
> Ich muss 798 Millionen Mal pro Sekunde (3 x 266 MHz) die Kubikwurzel aus
> einer Zahl zwischen 0 bis ca. einer viertel Billiarde (48 Bit Zahl)
> ziehen.
Das ist grundsätzlich kein Problem. Alles, was man in Echzeit in einen 
FPGA reinbekommt, läasst sich innen auch verarbeiten. Wie schon oben 
gesagt und gefragt, kommt es einzig auf die Latenz an, die du dir 
erlauben kannst. Wie hoch darf die sein?

Dein Beispiel aus der Bildverarbeitung / Farbraumkonversion riecht 
schwer nach RBG / YUV-Umwandlung. Üblicherweise darf da schon eine 
gewisse Latenz auftauchen, es sei denn, dein System soll im loop als 
CoPro arbeiten. (?)

> Das ganze per Hand auszurechnen ist einfach keine sinnvolle
> Option.
Sein Einwurf war als zu implementierende Methode zu verstehen, nehme ich 
an. Siehe meinen Beitrag oben. Einen solchen Core gab es mal von Altera 
zum download, lief als Square_Root und Cubic_Root. Die arbeiteten genau 
so. Der Square hatte nur ein signed-Problem, das man leicht korrigieren 
konnte. Selbigen Code habe ich bei einem Kunden eingebaut, weil er 
schneller und kleiner war, als der CORDIC aus Simulink/Xilinx. Als ich 
das im Altera Forum diskutierte, nahm Altera ihn von der Seite :-) Den 
Cubic habe ich noch wo rumliegen, allerdings nicht verwendet, als ich 
ihn später mal begraucht hatte, weil zu langsam.

> Hier kommst du nicht einmal mit einer Software-Lösung weiter
> (was ja der Grund ist warum ich das im FPGA implementiere).
Die Intel-Phreaks werden die nun vorrechnen, dass das sehr wohl mit 
einem I7 der aktuellen Generation geht, da 4GHz x 16 Cores und die 
GraKa-Freunde werden dir vorhalten, dass es mit CUDA am Schnellsten geht 
:-)

von Jürgen S. (engineer) Benutzerseite


Lesenswert?

Jetzt nochmals zum Problem: Ich habe mir den o.g. Core von Yalu mal 
angesehen - der rechnet richtig und braucht auch keine Verrenkungen, um 
266 MHz zu packen. Auf einem Artix 7 läuft es jedenfalls direkt durch. 3 
davon passen in auch den Allerkleinsten dieser Serie rein.

Dann noch die ganz alte Frage nach dem Runden: Ja, man kann Rechenpower 
verschwenden, wenn man das Ergebnis anhand der Umkehrfunktion aufpoppt, 
also in Deinem Fall mit 8 erweitert. Je nach Core könnte das sogar das 
Schnellste sein, weil es nur 3 Bits sind. Wenn es aber darauf hinaus 
läuft, dass die Latenz zu hoch ist und du das Ergebnis schneller 
brauchst, musst du eh mehr pipelinen und kannst auch unterwegs die 
Rundungsfrage lösen.

Dazu wären die Abfrage-Zeige, die entscheiden, wie jeweils 
weitergerechnet wird, zu parallelisieren und auf 2x2 = 4 Fragestellungen 
mit den entsprechenden vorausschauenden Annahmen wirken lassen (beim 
Cubic wohl am besten auf 8, habe ich noch nicht probiert). Dann wäre 
grundsätlzich die halbe Latenz möglich. Man hätte also 2 Bit Ergebnis (6 
Bit-Eingang je Takt). Also 8 Takte+

Möglicherweise kann man aber auch noch die Rechnung vereinfachen, was 
die Auflösung anbelangt. Braucht man wirklich 48Bit+3 Bit am Eingang und 
16.5 Bit am Ausgang?

von frk (Gast)


Lesenswert?

Jürgen S. schrieb:
> Mit einer look-ahead pipeline und doppelt selektivem Verwurf

Äh, was? Eigentlich kenne ich mich recht gut im Bereich FPGA aus, aber 
mir ist nicht klar was look-ahead hier helfen sollte. Ich baue eine 
Datenverarbeitungs-Pipeline und keinen Co-Prozessor. Außerdem habe ich 
keinen Schimmer was doppelt selektiver Verwurf sein soll. Google gibt 
dazu auch überhaupt gar nichts raus (was komisch ist, weil man 
eigentlich immer Links zu irgendwelchen Vorlesungs-Unterlagen, o.ä. 
findet). Vielleicht kenne ich das Konzept, aber unter einem anderen 
Namen??

Jürgen S. schrieb:
> Gleichwohl ist frk's code schon die richtige Richtung. Ich denke nur,
> dass man das noch optimieren muss, es sei denn, er hat Zeit, bis zu 48/2
> = 24 Takte auf das Ergebnis zu warten.

Ich bin an Durchsatz interessiert. Latenz ist mir so ziemlich egal. Im 
Idealfall sollte aber auch der Ressourcen-Verbrauch nicht zu groß sein, 
damit ich viele parallele Instanzen auf den FPGA bekomme. Das Hinzufügen 
von Control-Overhead wird es an der Stelle sicher nicht besser machen.

Jürgen S. schrieb:
> Dein Beispiel aus der Bildverarbeitung / Farbraumkonversion riecht
> schwer nach RBG / YUV-Umwandlung.

So ähnlich.

Jürgen S. schrieb:
> Ich habe mir den o.g. Core von Yalu mal
> angesehen - der rechnet richtig und braucht auch keine Verrenkungen, um
> 266 MHz zu packen. Auf einem Artix 7 läuft es jedenfalls direkt durch.

Ich weiß nicht wie das gehen soll ohne die einzelnen Stages noch einmal 
zu zerlegen. Wie du sehen kannst, hat das bei mir nicht direkt 
funktioniert, sondern ich musste in jedem Berechnungsschritt 3 
Pipeline-Stufen spendieren, um 266 MHz auf einem Arria 10 zu erreichen.

Jürgen S. schrieb:
> Braucht man wirklich 48Bit+3 Bit am Eingang und
> 16.5 Bit am Ausgang?

Man braucht auf jeden Fall 16.5 Bit am Ausgang, um (annähernd) keine 
Präzision zu verlieren. Dadurch ergibt sich die Anzahl der Bits am 
Eingang quasi automatisch.

von frk (Gast)


Lesenswert?

Jürgen S. schrieb:
>> Du kannst in jedem Takt einen Wert am
>> Eingang reingeben und nach x Zyklen fällt das Ergebnis hinten raus.
> Ja, bei dem inzwischen geposteten Code scheint das so zu sein

Das konnte bereits der allererste Code, den ich gepostet habe.

von galaktischer FPGA-Pongo (Gast)


Lesenswert?

frk schrieb:
> Das konnte bereits der allererste Code, den ich gepostet habe.

Kleine Zwischenfrage zum Verständnis:

Bist du nun der Frager, der Hilfe braucht oder Antworter?

Weiter oben hattest du geschrieben, dass du den Code einfach nur zur 
Verfügung stellen wolltest, als Antwort quasi auf den Fragenden davor 
aus dem Mai 2020:
Beitrag "Re: Kubikwurzel bilden"
(Der Thread wurde vor 8 Jahren gestartet und eigentlich hinreichend 
geklärt.)

Nun hat der Code aber deiner Aussage nach, noch Probleme, das timing zu 
treffen. Dabei ist aber doch das Auskippen von einigen FFs kein 
Hexenwerk. Wie verträgt sich das mit deinen FPGA-Kenntnissen?

frk schrieb:
> Es war übrigens nicht zu erwarten, dass das Timing besonders gut ist,
> wenn man die ganze Berechnung in einen riesigen Block klatscht.

so z.B. macht man das schon mal nicht ...

von frk (Gast)


Lesenswert?

galaktischer FPGA-Pongo schrieb im Beitrag #6424560:
> Bist du nun der Frager, der Hilfe braucht oder Antworter?

Eigentlich habe ich geantwortet. Ich nehme aber gerne noch Informationen 
mit, wenn ich dabei etwas lernen kann.

galaktischer FPGA-Pongo schrieb im Beitrag #6424560:
> Nun hat der Code aber deiner Aussage nach, noch Probleme, das timing zu
> treffen. Dabei ist aber doch das Auskippen von einigen FFs kein
> Hexenwerk. Wie verträgt sich das mit deinen FPGA-Kenntnissen?

Gut verträgt sich das. Ich habe nicht erwartet, dass das von Anfang an 
gut funktioniert und das hat es dann ja auch nicht. Die erste 
Implementierung war eigentlich nur eine funktionale Implementierung als 
Startpunkt für eine Implementierung, die dann auch wirklich integriert 
werden kann. Natürlich ist das Hinzufügen von FFs kein Hexenwerk, 
besonders in Forward-only-Pipelines, aber es funktioniert und ich sehe 
auch nicht wie man es großartig anders hätte machen sollen, um weniger 
Ressourcen zu brauchen. Wenn du eine Idee hast, dann bin ich offen 
dafür.

galaktischer FPGA-Pongo schrieb im Beitrag #6424560:
> frk schrieb:
>> Es war übrigens nicht zu erwarten, dass das Timing besonders gut ist,
>> wenn man die ganze Berechnung in einen riesigen Block klatscht.
>
> so z.B. macht man das schon mal nicht ...

Ja, das ist jetzt wenig überraschend. An irgendeinem Punkt muss man aber 
mal ansetzen. Es ist nicht sinnvoll auf blauen Dunst zu optimieren, wenn 
man keine Referenz hat. Inkrementell erst die Funktion zu implementieren 
und dann zu optimieren ist noch immer einer der besten Ansätze, außer 
wenn man schon vorher weiß, dass man zum Erreichen der Timings einen 
komplett anderen Ansatz braucht. Du hast ja selber gesagt, dass das 
Hinzufügen von FFs kein Hexenwerk ist. Dementsprechend schnell geht das 
halt auch. Wenn ich aber oben sehe, dass manche Leute nicht mal eben so 
ein bisschen Python-Code in VHDL übersetzen können, dann muss ich auch 
annehmen, dass eben den selben Leuten auch das Hinzufügen von 
Register-Stufen schwer fällt. Deswegen habe ich dann noch einmal den 
Code gepostet, den man dann auch so integrieren kann.

Es war auch ursprünglich gar nicht gedacht, dass hier eine neue 
Diskussion entsteht. Eigentlich wollte ich nur diesen Effekt vermeiden: 
https://xkcd.com/979/ und damit diesen Thread, dem noch immer die 
VHDL-Implementierung gefehlt hat, zu einer Conclusion bringen.
Jetzt ist aber doch eine Diskussion losgebrochen und dann nehme ich halt 
mit was ich dabei noch lernen kann.

von Herbert (Gast)


Lesenswert?

Lustiger Denkermolch schrieb:
> Mach doch einfach eine binäre Suche, oder auch eine "intelligente"
> interpolierende Suche. Gerade bei Ganzzahlen geht das schön flott; je
> höher die Ordnung der Wurzel, desto flotter...

Diese Art der schlauen Suche nennt sich CORDIC. Das müsste auch mit der 
dritten Wurzel gehen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [vhdl]VHDL-Code[/vhdl]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.