Hallo allerseits, ich habe als Teil meiner Masterarbeit einen kleineren Bildregistrierungsalgorithmus in Matlab geschrieben (der vor allem aus einer Kreuz-Korrelation besteht). Jetzt soll ich abschätzen, wie sehr dieser Algorithmus parallelisierbar wäre mit dem Hintergrund der Verwendung auf einem FPGA. Es geht vor allem darum die Anzahl der einzelnen Rechenschritte abzuschätzen um ein grobes Bild davon zu haben, wie viel schneller man diesen Algorithmus auf einem FPGA umsetzen könnte. Nun werde ich aus der Literatur nicht wirklich schlau, denn FPGAs sind nun wirklich kein einfaches Thema, wenn man sich vorher noch nie richtig mit Hardware auseinandergesetzt hat. Wie könnte ich denn da ran gehen? Multiplikation braucht z.B. soweit ich weiß viel mehr Ressourcen als Addition. FFT wiederum wird wohl in der Regel auf IP Cores realisiert. Aber woher weiß ich, wie viele Clock Cycle z.B. ein Pixel bräuchte bzw. wie viele davon ich parallel berechnen lassen könnte? Oder denke ich komplett falsch? Ich bitte um ein paar Tipps, Beispiele oder vernünftige Quellen für FPGA-Laien. Danke schonmal!
Der Resourcenbedarf ist erstmal zweitrangig. Du sollst feststellen, welche Schritte parallel und welche sequenziell erfolgen. Beispiel: a*b ist ein Schritt; a*b+c sind zwei, erst Multiplikation, danach Addition; a*b+c*d sind immer noch zwei, die beiden Multiplikationen sind unabängig voneinander und können parallel ausgeführt werden. Stell es dir wie eine Fließbandproduktion vor. Du darfst beliebig viele Fließbänder mit jeweils beliebig vielen Stationen/Schritten einsetzen. Wie kurz kannst du die gesamte Kette machen? Die Softwarelösung entspräche einem einzelnen Fließband mit seeehr vielen Stationen. Bei Bildbearbeitung achtet man gerne darauf, dass der Algorithmus auf Teilbereiche angewandt werden kann (z.B. 16x16 Pixel) - das lässt sich dann schön parallelisieren. Wenn man allerdings Daten aus Nachbarbereichen braucht, wird das ganze schnell seriell.
Danke für die gute Erklärung! Nur, kommt das am Ende nicht auf die selbe Fragestellung raus, da die Stärke eines FPGAs ja in seiner Parallelisierbarkeit liegt? Außerdem stelle ich mir auch die Frage, wie viele Prozesse welcher Art ich z.B. auf einem bestimmten FPGA laufen lassen könnte, also wie viele LUTs, DSPs, Flip-Flops etc. ich für welche Operation brauche - zumindest grob abgeschätzt. In einem Artikel (Asano et. al., 2009) wird zum Beispiel gezeigt, dass ich bei einem rasternden Filter (also auch Faltung, Kreuzkorrelation etc.) für ein Pixel nur einen Taktzyklus brauche, weil alle Additionen und Multiplikationen bei entsprechendem Pipelining parallel ablaufen können. Die einzelnen Pixel müssten dann (eben wegen benötigter Nachbarbereiche) seriell ablaufen. Aber wie groß mein Filter hier dann sein kann hängt ja von den Ressourcen des FPGA ab? Ähnliches frage ich mich bei IP Cores bzw. Megafunctions, z.B. für FFT. Ich wüsste z.B. gern, ob die Korrelation über Fouriertransformation besser umzusetzen wäre als der "stumpfe" Rasteransatz. Und vor allem: Welche Lehren kann ich konkret daraus ziehen, wenn ich weiß, was seriell und was parallel ablaufen kann, wenn ich das nicht auf eine konkrete Implementierung anwenden bzw. mit dem "klassischen Fall" vergleichen kann? Zumal wohl auch GPUs und CPUs mit mehreren Prozessorkernen und SIMD-Erweiterungen eine gewisse Parallelisierbarkeit aufweisen.
Peter H. schrieb: > Außerdem stelle ich mir auch die Frage, wie viele Prozesse welcher Art > ich z.B. auf einem bestimmten FPGA laufen lassen könnte, also wie viele > LUTs, DSPs, Flip-Flops etc. ich für welche Operation brauche - zumindest > grob abgeschätzt. Dafür nimmt man sich die entsprechende Operation und implementiert sie auf der gewünschten Zielplattform. Die erreichbaren Ergebnisse (Ressourcenverbrauch, Geschwindigkeit) sind i.d.R. stark von der gewählten Bitbreite und der verwendeten Siliziumtechnologie abhängig. Duke
Duke Scarring schrieb: > Peter H. schrieb: >> Außerdem stelle ich mir auch die Frage, wie viele Prozesse welcher Art >> ich z.B. auf einem bestimmten FPGA laufen lassen könnte, also wie viele >> LUTs, DSPs, Flip-Flops etc. ich für welche Operation brauche - zumindest >> grob abgeschätzt. > Dafür nimmt man sich die entsprechende Operation und implementiert sie > auf der gewünschten Zielplattform. Die erreichbaren Ergebnisse > (Ressourcenverbrauch, Geschwindigkeit) sind i.d.R. stark von der > gewählten Bitbreite und der verwendeten Siliziumtechnologie abhängig. > > Duke Soetwas habe ich in Simulink bereits versucht - allerdings funktioniert der Algorithmus dort aus mir unbekannten Gründen nicht einmal, wenn ich ihn genau nach Tutorial aufbaue.
Peter H. schrieb: > Und vor allem: Welche Lehren kann ich konkret daraus ziehen, wenn ich > weiß, was seriell und was parallel ablaufen kann, wenn ich das nicht auf > eine konkrete Implementierung anwenden bzw. mit dem "klassischen Fall" > vergleichen kann? Du kannst vermeiden, dass jemand nicht richtig rechnet und mit aller Gewalt eine GPU-Unit in das System eindesigned, welche sich dann als Flaschenhals entpuppt und die sehr viel Verdruss in den benachbarten FPGAs aufwirft :(
Peter H. schrieb: > Jetzt soll ich abschätzen, wie sehr > dieser Algorithmus parallelisierbar wäre mit dem Hintergrund der > Verwendung auf einem FPGA. Es geht vor allem darum die Anzahl der > einzelnen Rechenschritte abzuschätzen um ein grobes Bild davon zu haben, > wie viel schneller man diesen Algorithmus auf einem FPGA umsetzen > könnte. Dazu stellt man einen CDFG auf und macht ein ASAP und ein ALAP scheduling und sucht daraus das Optimum hinsichtlich der Auslastung der Funktionsblöcke. https://www.tu-ilmenau.de/fileadmin/public/iks/files/lehre/ihs2/IHS2-7-x-Verhaltensmodellierung-DFG-CFG-Wrapup.pdf https://ls12-www.cs.tu-dortmund.de/daes/media/documents/teaching/courses/ss08/rem/skript/eda-marw-synth-02.pdf https://slideplayer.com/slide/5228479/
Fpgakuechle K. schrieb: > Dazu stellt man einen CDFG auf und macht ein ASAP und ein ALAP > scheduling Hm, also jetzt mal Hand-aufs-Herz: Wer bitte macht bei der täglichen Arbeit so einen Daten-Fluss-Graph? Die mathematischen Funktionen, die zu verwenden sind, können einfach hingeschrieben und durch-synthetisiert werden, gfs unter Verwendung von Cores. Des Einzigste, was es zu schauen gibt, sind die Divisionen und Wurzeln, die richtig ins Geld gehen und die man gfs umbaut. Wie lange eine Addition braucht und ob man eine Akkumulation noch in den Takt kriegt und beides 3 Takte braucht, lässt sich aus der Erfahrung ungefähr sagen und ganz genau geht es mit und ohne Graph in keinem Fall, weil die Optimierungen im Dunkeln liegen und von Vielem abhängen. Was es aber braucht, ist vor allem erst einmal eine Vorstellung, wie eine Schaltung aussehen könnte, welche Variationen es gibt und welche man wie einsetzt. Aus dem Datengraph lässt sich da wenig unternehmen, zumal der in Form der Formel eigentlich direkt sichtbar vorliegt. Wichtig wäre, die Rechnerei schon von vorn herein auf das Fpga abzustellen und es in MATLAB schon richtig anzusetzen. Solche Bildbearbeitungen laufen immer mit parallelen Feldern und da ist es von Interesse wieviele das sind und wie stark parallelisiert die Rechenpipeline ist. Ist das ein Core mit maxmimaler Bandbreite oder ein C++ pipeline auf mehren ARM-Cores oder gar beides. Man muss also wissen, was man tun kann und was zu tun wäre, um überhaupt ersteinmal zu einem solchen Grafen zu kommen. Da müssten von einem Anfänger, der keinen Plan hat, mehrere Alternativen aufgestellt und untersucht werden. Und bis der das alles in 5 Ansichten hat, hat der Profi schon die übernächte pipeline hingeschrieben.
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.