Hallo zusammen Folgende Aufgabe: Ich habe eine Laufvariable x. Diese wird hochgezählt von 0..899 (Pixel). Der Bereich 0..899 bzw. 1-900 wird nun in 16 Teile unterteilt. Somit 56.25 Pixel pro Bereich. nun soll möglichst effizient geprüft werden, in welchem Abschnitt sich die Laufvariable befindet. Also im Wertebereich von 0..55 soll eine 1 resultieren. im Bereich von 55..111 eine zwei usw. Wie könnte ein solcher Vergleich möglichst schnell durchgeführt werden, ohne hardkodierte Werte zu verwenden? Der Wert 900 kann abweichen und wird dynamisch im FPGA ermittelt. Vielen Dank schonmal.
John schrieb: > Wie könnte ein solcher Vergleich möglichst schnell durchgeführt werden Definiere den Begriff "schneller Vergleich". > ohne hardkodierte Werte zu verwenden? Mit ein paar Komparatoren. Aber das macht doch sowieso der Synthesizer für dich. Wo liegt das Problem? Ich könnte mir aber auch vorstellen, den Wert mit einer einzigen geschickten Multiplikation so zurechtzurechnen, dass gleich der gewünschte Wert herauskommt...
:
Bearbeitet durch Moderator
Danke für deine Antwort. Lothar M. schrieb: >> ohne hardkodierte Werte zu verwenden? > Mit ein paar Komparatoren. Aber das macht doch sowieso der Synthesizer > für dich. Wo liegt das Problem? Ich habe erst wenige Erfahrungen mit FPGAs gesammelt. Ich kann daher noch nicht wirklich abschätzen, wie gut die Synthesizer meinen unoptimierten code optimieren können... Lothar M. schrieb: > Ich könnte mir aber auch vorstellen, den Wert mit einer einzigen > geschickten Multiplikation so zurechtzurechnen, dass gleich der > gewünschte Wert herauskommt... An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die richtige Idee gehabt, wie diese Berechnung aussehen könnte. Lässt sich über den Daumen in etwa abschätzen, wie länge Berechnungen in einem FPGA in etwa dauern? Ist es z.B. ähnlich wie beim uC, wo man möglichst wenig dividieren soll dafür addieren?
Kann sich der Wertebereich (900) zu jeder neuen Laufvariable x ändern? Oder evtl nur wenn für jeden Durchgang? Einmalig bei der initaliserung?
Bzgl. der Multiplikationslösung: 900/16 = a x / a = Bereich. -> Hier ganzahl division mit Rest. Aber ob das schneller ist, als die 16 Grenzen zu berechnen, und dann zu vergleichen, keine Ahnung.
John schrieb: > Lässt sich über den Daumen in etwa abschätzen, wie länge Berechnungen in > einem FPGA in etwa dauern? Ist es z.B. ähnlich wie beim uC, wo man > möglichst wenig dividieren soll dafür addieren? Das laesst sich nicht nur abschaetzen sondern exakt ermitteln per Simulation. Wenn mans ordentlich macht dann pro Berechnung genau ein Takt, wobei durch Pipelining nur entsprechende Latenzen aufgebaut werden und man pro Takt jeweils ein Ergebnis erhaelt (sofern pro Takt auch entsprechend Daten zur Verarbeitung zur Verfuegung stehen).
mukel schrieb: > Kann sich der Wertebereich (900) zu jeder neuen Laufvariable x > ändern? > Oder evtl nur wenn für jeden Durchgang? Einmalig bei der initaliserung? Nur zu jedem Durchgang. Das heisst, es wird mit einem Bereich x in die Berechnung eingestiegen. Wie z.B. oben mit 900. Daher liessen sich die Grenzen zuvor berechnen und dann vergleichen mit einem Vector. Dann müssten jedoch einfach sehr vielene grösser kleiner vergleiche durchgeführt werden. Braucht dann vermutlich einige LUTs dafür.
John schrieb: > An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die > richtige Idee gehabt, wie diese Berechnung aussehen könnte. Im Fall hier müsste nur der Eingangswert 0..899 mit der "Magic Number" 18641 multipliziert und dann die Bits 23..20 des Ergebnisses für ein Ergebnis 0..15 verwendet werden. Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit (2^24-1)/900 John schrieb: > Also im Wertebereich von 0..55 soll eine 1 resultieren. Den obigen 4-Bit-Vektor auf 5 aufgebohrt und eins draufaddiert und fertig ist der Wert 1..16. Wobei ich mir diesen Wertebereich 1..16 angesichts des unnötigen zusätzlichen Bits noch einmal sehr durch den Kopf gehen lassen würde...
:
Bearbeitet durch Moderator
Lothar M. schrieb: > John schrieb: >> An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die >> richtige Idee gehabt, wie diese Berechnung aussehen könnte. > Im Fall hier müsste nur der Eingangswert 0..899 mit der "Magic Number" > 18641 multipliziert und dann die Bits 23..20 des Ergebnisses für ein > Ergebnis 0..15 verwendet werden. > > Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit > (2^24-1)/900 > > John schrieb: >> Also im Wertebereich von 0..55 soll eine 1 resultieren. > Den obigen 4-Bit-Vektor auf 5 aufgebohrt und eins draufaddiert und > fertig ist der Wert 1..16. Wobei ich mir diesen Wertebereich 1..16 > angesichts des unnötigen zusätzlichen Bits noch einmal sehr durch den > Kopf gehen lassen würde... Cool. Vielen Dank für diesen eleganten Weg der Herleitung! Diesen kannte ich noch nicht. Natürlich ist 1..16 nur dezimal dargestellt. Intern kann ich natürlich 0..15 verwenden.
John schrieb: > Lothar M. schrieb: >> John schrieb: >>> An sowas habe ich auch gedacht. Aber irgendwie habe ich noch nicht die >>> richtige Idee gehabt, wie diese Berechnung aussehen könnte. >> Im Fall hier müsste nur der Eingangswert 0..899 mit der "Magic Number" >> 18641 multipliziert und dann die Bits 23..20 des Ergebnisses für ein >> Ergebnis 0..15 verwendet werden. >> >> Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit >> (2^24-1)/900 >> >> John schrieb: >>> Also im Wertebereich von 0..55 soll eine 1 resultieren. >> Den obigen 4-Bit-Vektor auf 5 aufgebohrt und eins draufaddiert und >> fertig ist der Wert 1..16. Wobei ich mir diesen Wertebereich 1..16 >> angesichts des unnötigen zusätzlichen Bits noch einmal sehr durch den >> Kopf gehen lassen würde... > > Cool. Vielen Dank für diesen eleganten Weg der Herleitung! > Diesen kannte ich noch nicht. > > Natürlich ist 1..16 nur dezimal dargestellt. Intern kann ich natürlich > 0..15 verwenden. Lothar M. schrieb: > Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit > (2^24-1)/900 Wie kommst du auf die 24-1?
John schrieb: > Lothar M. schrieb: >> Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit >> (2^24-1)/900 > Wie kommst du auf die 24-1? Obacht: Punkt vor Strich... ;-) Dort steht: ((2^24)-1)/900 2 hoch 24 ist eins zuviel für einen 24-Bit-Vektor, von dem die vordersten 4 Bits verwendet werden sollen. So wie in einen 8-Bit-Vektor eben nicht der Wert 2^8 (=256) rein passt, sondern nur Werte von 0..255. Du musst dir einfach mal die Bits auf einem Blatt Papier aufzeichnen, einen Tag drüber grübeln und eine Nacht drüber schlafen, um auf den Trick zu kommen...
:
Bearbeitet durch Moderator
Lothar M. schrieb: > Du musst dir einfach mal die Bits auf einem Blatt Papier aufzeichnen, > einen Tag drüber grübeln und eine Nacht drüber schlafen, um auf den > Trick zu kommen... Ok werde ich tun! Danke :)
Lothar M. schrieb: > John schrieb: >> [...] > Die "Magic Number" habe ich (wie schon aufgezeigt) berechnet mit > (2^24-1)/900 > > [...] Magst Du bitte verlinken, wo Die Berechnung der "Magic Number" aufgezeigt hast? Ich würde das gerne nachvollziehen.
Theor schrieb: > wo Die Berechnung der "Magic Number" aufgezeigt hast? Ok, ich habe mich verguckt... > Ich würde das gerne nachvollziehen. Ich sage mir: die Multiplier können 18x18 => 36 Bit auf einmal ausrechnen. Dann muss ich eine Magic Number finden, die kleiner als 2^18 ist. Das ist die erste Randbedingung. Die zweite ist der Wert von 900-1, der 10 Bits braucht. Also wäre das "genaueste", wenn ich vom Ergebnis die Bits 27..24 nehme. Um von diesen Grenzen geräumig wegzubleiben, nehme ich die Bits 23..20 und habe als Ziel, dort die Ergebnisse 0x0..0xF für den Eingangswert 0..899 zu bekommen. Ergo teile ich den Maximalwert 0xFF_FFFF (=2^24-1) durch den maximalen Eingangswert (korrekterweise hier eigentlich 899). Damit kommt dann eine (neue und bessere ;-) Wert von 16777215/899 = 18662,0856 heraus. Ergo ergibt ein Eingangswert von 0 ein Ergebnis von 0x0000000. Ein Eingangswert von 100 ergibt 100*Magic Number = 1866200 = 0x1C79D8 => Bits 23..20 = 1. Ein Eingangswert von 450 ergibt 8397900 = 0x80244C => Bits 23..20 = 8. Und der Maximalwert mit 899 resultiert wie zu erwarten (Abschneiden der Nachkommastellen beim Berechnen der Magic Number) knapp vor dem "oberen Anschlag" 0xFFFFB2 => Bits 23..20 = F
Vielen Dank für deine Erläuterung. Ein wirklich guter Trick!
Lothar M. schrieb: > Theor schrieb: >> wo Die Berechnung der "Magic Number" aufgezeigt hast? > Ok, ich habe mich verguckt... > >> Ich würde das gerne nachvollziehen. > Ich sage mir: [...] Danke für die Antwort, Lothar. ;-)
Nimm einen BRAM und fülle die Adressen 0 bis 900 mit deinen gewünschten Werten. Spart LUTs.
Könnte man machen, aber der Wert von 900 ist nicht fest.
Simon schrieb: > Ein wirklich guter Trick! Letztendlich ist die allgemeine Aufgabe hier: "Dividieren per Multiplikation mit Kehrwert" Denn es soll ja eigentlich der Eingangswert e=0..899 durch den Divisor d=56,25 geteilt werden, um ein Resultat r im Bereich 0..15 zu bekommen:
Umgestellt sieht das dann so aus:
Das kann man jetzt erweitern durch eine Zweierpotenz:
Umgestellt sieht das dann so aus:
Das 1/2^n ist eine Division durch eine Zweierpotenz und damit in Hardware nur ein "Ignorieren" der unteren Bits, also nur ein Umverdrahten. Bleibt also leztlich wieder nur die Aufgabe den mittleren Term 2^n/d zu optimieren. Mit ein wenig probieren oder Erfahrung kommt man da dann recht schnell auf eine "Magic Number", die die Eigenheiten der Hardware (z.B. Breite der zur Verfügung stehenden Multiplizierer) berücksichtigt. Und so komme ich im Fall hier mit einer Divivson durch 2^20 also dem Abschneiden der unteren 20 Bits auf den Wert 2^20/56.25 = 18641. Dieser Wert war dann auch der erste, den ich intuitiv ins Rennen geworfen hatte. Der zweite im Beitrag "Re: Effizienter Weg gesucht um zu prüfen, ob Variable im Bereich liegt" aufgezeigte Weg ist eigentlich mathematisch falsch, weil er nicht wie gewünscht durch 56,25 teilt, sondern die Bereichsendwerte 0 und 899 auf die Bereichsendwerte 0 und 2^24-1 zueinander skaliert. Das resultiert in einer geringfügig anderen Steigung der Zuordnung (im Promillebereich). Es entspricht quasi dem Fehler, den ich mache, wenn ich einen 10-Bit-AD-Wandler mit 0..5V so umrechne: U = 5.0*adw/1023 oder so U = 5.0*adw/1024. Im ersten 1023er-Fall kommt bei einer Eingangsspannung von 5.0V eben auch 5.00V auf die Anzeige, im eigentlich korrekten 1024er-Fall steht auf der Anzeige nur 4,99V.
:
Bearbeitet durch Moderator
Binärer Baum, bei dem die zu überprüfenden Grenzen in die Knoten als Werte eingetragen werden. Hat den Vorteil, dass egal wo der aktuelle Wert liegt immer die selbe Anzahl von Vergleichen notwendig ist.
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.