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?
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!
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.
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.
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...
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.
und wie genau brauchst du die wurzel? Also nur Ganzzahlanteil oder wieviele Nachkommastellen?
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.
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?
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?
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.
... 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.
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.
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
Mit aktueller Hardware wie Cortex M4 braucht man die Divisionen auch nicht mehr so zu fuerchten...
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?
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.
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
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
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.
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
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?
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
Kannst Du mir helfen mit Matlab Simulink schematic fur die dritten wurzel in FPGA, sogar mit einem Beischpiel zu bilden ?
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.
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.
Angehängte Dateien:
-
modelsim.png
7,3 KB
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.
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
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.
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?
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.
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.
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.
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.
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.
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 :-)
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?
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.
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.
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 ...
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.
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.
Thread beobachten
Seitenaufteilung abschaltenBitte 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.