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 :(
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.
