FPGA Firmware Design: Wie groß ist zu groß?

12

Ich habe eine besonders große Signalverarbeitungstransformation, die von Matlab nach VHDL portiert werden muss. Es erfordert definitiv eine Art von Ressourcenteilung. Ein bisschen Berechnung gab mir Folgendes:

  • 512 Fuß von 64 Punkten
  • 41210 Multiplikations-Additions-Operationen

Wenn man bedenkt, dass das größte Virtex 6-FPGA ~ 2000 DSP48E-Blöcke hat, weiß ich, dass ich Ressourcen gemeinsam nutzen kann, um die Ressourcen mehrmals zu verwenden. Die Ausführungszeit ist eigentlich kein Problem, die Verarbeitungszeit kann im FPGA relativ lang sein.

Wenn ich mir die Ressourcennutzung anschaue, bekomme ich mit der Radix-2-Lite-Architektur 4 dsp-Blöcke / FFT-Operation = 2048 DSP-Blöcke, insgesamt ~ 43.000. Das größte Virtex-FPGA hat 2k-Blöcke oder 20 Operationen / Mux.

Offensichtlich wird das Einbeziehen solch großer Multiplexer in den Stoff auch Scheiben aufnehmen. Wo finde ich das obere Ende dieser Grenze? Ich kann die FPGA-Ressourcen nicht unendlich teilen. Ist der 41210-Multiplikator zu groß? Wie berechne ich, was zu groß ist?

Ich habe mir auch andere Ressourcen angesehen (Slices, Brams usw.). Radix-2 Lite bietet außerdem 4 x 18.000 Brams / fft = 2048 Brams. Das größte Xilinx-FPGA enthält 2128 Brams. sehr grenzwertig. Ich mache mir Sorgen, dass mein Design einfach zu groß ist.


AKTUALISIEREN:

Weitere Informationen zum Design. Ich kann nicht ins Detail gehen, aber hier ist, was ich geben kann:

Initial conditions -> 512 ffts -> 40k multipliers ---------|----> output data to host 

                 ^------re-calculate initial conditions----|

Ausgabedatenratenspezifikation: "schneller als die Matlab-Simulation"

Nach Berechnungen bin ich hier:

FFT-Phase: einfach. Ich kann 1/2/4/8 FFTs implementieren, die Ergebnisse im SDRAM speichern und später darauf zugreifen. Relativ klein, auch wenn es lange dauert, ist es in Ordnung. Mit Radix-2 Lite kann ich 2 DSP48Es und 2 18k BRAMS / FFT erhalten. Streaming ergibt 6 DSP48Es 0BRAMS / FFT. In beiden Fällen ist die 64-Punkt-FFT in Bezug auf die FPGA-Ressourcen klein.

Multiplikatoren : Das ist mein Problem. Die Multiplikationseingaben stammen entweder aus Nachschlagetabellen oder FFT-Daten. Es ist wirklich nur eine ganze Reihe von Multiplikatoren. Es gibt nicht viel zu optimieren. Kein Filter, hat aber ähnliche Eigenschaften wie ein Filter.

In Anbetracht der gemeinsamen Nutzung von Ressourcen auf dem FPGA funktioniert die Mathematik folgendermaßen: Eine LUT-6 kann als 4-Wege-Mux verwendet werden. Die Formel für einen N-Wege-M-Bit-Multiplexer lautet wie folgt:

N*M/3 = number of luts, or N*M/12 = slices (4 LUTS/slice).

Wenn Sie die Zahlen für meine Implementierung eingeben, erhalten Sie keine guten Ergebnisse. 90% der virtix-6-Familie verfügen nicht über genügend Slices, um ihre DSPs auf Ressourcen zu verteilen und 40.000 Vorgänge auszuführen.

Stanri
quelle
Die effizienteste Form der gemeinsamen Ressourcennutzung ist die teilweise Serialisierung, bei der Sie durch Adressierung des Speichers auf Daten zugreifen können. Im Extremfall handelt es sich natürlich wieder um einen herkömmlichen Prozessor für gespeicherte Programme. Die mangelnden Leistungsanforderungen deuten auf die Flexibilität einer Softwareimplementierung hin, die möglicherweise in einer Compute-Cloud ausgeführt wird.
Chris Stratton
1
Dies ist nicht Teil Ihrer Frage, aber Sie haben in Ihrer Ressourcenberechnung nicht angegeben, welcher Größenoperand vorliegt. 512 FFTs x 64 Punkte x wie viele Bits? In einem FPGA liegt die Operandengröße ganz bei Ihnen, daher müssen Sie sie berücksichtigen, wenn Sie die Größe Ihres Problems ermitteln.
Das Photon
Ich weiß nicht, ob Sie es bemerkt haben, aber diese großen FPGAs sind ziemlich teuer. Einige können über $ 5k liegen. Vielleicht sollten Sie auch darüber nachdenken, es sei denn, die Kosten spielen keine Rolle.
Gustavo Litovsky
1
Abgesehen von den alternativen Lösungsvorschlägen, die Sie bisher in den Antworten erhalten haben, bezweifle ich, dass wir noch viel mehr für Sie tun können. Ich meine, Sie könnten nur einen FFT-Kern herstellen und Ihre 512 Eingänge nacheinander durchlaufen lassen, und das würde natürlich auch in ein ziemlich kleines FPGA passen. Irgendwo dazwischen und alles parallel zu machen, ist das richtige Gleichgewicht zwischen Geschwindigkeit und Ressourcen für Ihre Anwendung ... aber es ist für niemanden außer Ihnen schwer zu sagen, wo dieses Gleichgewicht sein sollte.
Das Photon
1
Haben Sie eine Budgetnummer dafür? Wie Gustavo betonte, sind High-End-FPGAs teuer, ebenso wie die Entwicklung einer Platine, auf der sie installiert werden können. Während nur die Verdoppelung (oder Vervierfachung oder ...) der Menge an Computerhardware und die weitere Verwendung des vorhandenen, bewährten (?) Matlab-Codes wahrscheinlich die angegebene Geschwindigkeitsspezifikation erfüllen könnten.
Das Photon

Antworten:

8

Ich frage mich, ob es eine andere Sichtweise auf das Problem gibt.

Spielen Sie Ihre Schätzung von 512 FFT-Operationen (jeweils 64 Punkte) und 42.000 MAC-Operationen ab ... Ich nehme an, dass Sie dies für einen Durchgang durch den Algorithmus benötigen?

Jetzt haben Sie einen FFT-Kern mit 4 DSP-Einheiten gefunden ... aber wie viele Taktzyklen dauert es pro FFT? (Durchsatz, nicht Latenz)? Sagen wir 64 oder 1 Zyklus pro Punkt. Dann müssen Sie diese 42.000 Mac-Vorgänge in 64 Zyklen abschließen - möglicherweise 1.000 MACs pro Zyklus, wobei jeder MAC 42 Vorgänge handhabt.

Nun ist es an der Zeit, den Rest des Algorithmus genauer zu betrachten: Identifizieren Sie keine MACs, sondern Operationen höherer Ebenen (Filterung, Korrelation, was auch immer), die wiederverwendet werden können. Erstellen Sie für jede dieser Operationen Kerne, die wiederverwendbar sind (z. B. Filter mit verschiedenen auswählbaren Koeffizientensätzen), und bald werden möglicherweise relativ wenige Multiplexer zwischen relativ großen Kernen benötigt ...

Ist auch eine Festigkeitsreduzierung möglich? Ich hatte einige Fälle, in denen Multiplikationen in Schleifen erforderlich waren, um Quadratics (und höher) zu erzeugen. Wenn ich sie ausrollte, konnte ich sie iterativ ohne Multiplikation generieren: Ich war an dem Tag, als ich eine Difference Engine auf FPGA baute, ziemlich zufrieden mit mir!

Ohne die Anwendung zu kennen, kann ich keine näheren Angaben machen, aber eine solche Analyse wird wahrscheinlich einige wesentliche Vereinfachungen ermöglichen.

Auch - da es klingt , als ob Sie nicht eine bestimmte Plattform im Sinn haben - prüfen , ob Sie über mehrere FPGAs partitionieren können ... einen Blick auf dieses Brett oder diese ein , die mehrere FPGAs in einer bequemen Plattform bieten. Sie haben auch eine Platine mit 100 Spartan-3-Geräten ...

(ps Ich war enttäuscht, als die Software-Jungs diese andere Frage geschlossen haben - ich denke, es ist dort mindestens so angemessen)

Edit: Du bist dran - ich glaube, du fängst an, dorthin zu gelangen. Wenn alle Multiplikator-Eingänge entweder FFT-Ausgänge oder "Nicht-Filter" -Koeffizienten sind, erkennen Sie allmählich die Art von Regelmäßigkeit, die Sie ausnutzen müssen. Ein Eingang zu jedem Multiplizierer ist mit einem FFT-Ausgang verbunden, der andere Eingang mit einem Koeffizienten-ROM (BlockRam als konstantes Array implementiert).

Durch die Sequenzierung verschiedener FFT-Operationen mit derselben FFT-Einheit werden die FFT-Ausgaben nach diesem Multiplikator automatisch sequenziert. Das Sequenzieren der korrekten Koeffizienten in den anderen MPY-Eingang ist jetzt "nur" eine Frage der Organisation der korrekten ROM-Adressen zum richtigen Zeitpunkt: ein organisatorisches Problem, statt eines großen MUX-Aufwands.

Leistung: Ich denke, Dave Tweed war unnötig pessimistisch - die FFT führte n * log (n) Operationen durch, aber Sie können O (n) Butterfly-Einheiten und O (logN) Zyklen oder O (logN) Einheiten und O ( n) Zyklen oder eine andere Kombination, die Ihren Ressourcen- und Geschwindigkeitszielen entspricht. Eine solche Kombination kann die Post-FFT-Multiplikationsstruktur viel einfacher machen als andere ...

Brian Drummond
quelle
Für eine FFT, die mit einem einzigen Hardware-Butterfly implementiert wurde, sind NlogN-Taktzyklen erforderlich. für 512 Punkte wären das 256 * 8 Schmetterlinge oder 2048 Uhren. Das bedeutet, dass die 41210 (oder 32768?) MACs nur 8-10 Hardware-Multiplikatoren benötigen, um in der gleichen Zeit fertig zu werden.
Dave Tweed
Ich meine, 16-20 Multiplikatoren.
Dave Tweed
Entschuldigung, mir ist gerade aufgefallen, dass ich das falsch verstanden habe. Die einzelnen FFTs haben 64 Punkte, sodass für die Implementierung mit einem einzelnen Butterfly 32 * 5 = 160 Takte erforderlich sind. Die MACs können dann mit 200-250 Hardware-Multiplikatoren ausgeführt werden.
Dave Tweed
das ist es, was mich stumpf macht. Wie kann xilinx einen Core entwerfen, der 16k / 32k ffts ausführen kann, die 400k Multiplikation-Addition-Operationen (NlogN) erfordern, und trotzdem habe ich mit meinen 41k zu kämpfen? es muss einen Weg geben!
Stanri
@ Dave: Ich glaube du meinst 160 Multiplikationen, nicht 160 Zyklen, sicher? In einer FFT ist nichts so inhärent serialisiert ...
Brian Drummond
2

Wenn für dieses Problem keine harten Echtzeitbeschränkungen gelten und es sich nicht so anhört - Sie möchten lediglich, dass es "schneller" ausgeführt wird, scheint es für die Beschleunigung auf einer oder mehreren GPUs durchaus geeignet zu sein. Es gibt mehrere Softwarebibliotheken, die dies zu einer relativ einfachen Angelegenheit machen, und dies wäre um eine Größenordnung einfacher, als direkt auf benutzerdefinierte FPGA-Hardware umzusteigen.

Nur Google für "GPU-fähige Bibliothek" oder "GPU-beschleunigte Bibliothek", um loszulegen.

Dave Tweed
quelle
Interessanterweise erwähnte ich GPUs gegenüber dem Kunden, als ich von diesem Projekt hörte, und er war nicht interessiert.
Stanri
@StaceyAnneRieck: Hat er gesagt warum?
Dave Tweed
Er sagte nicht wirklich warum, nur dass er es sich vor der Verwendung eines FPGAs angeschaut hatte, schien anscheinend weniger Arbeit zu sein. Ich muss es noch einmal ansprechen.
Stanri
@stanri: Auch wenn Sie letztendlich in einer FPGA-Implementierung landen, scheint mir die GPU ein guter Weg zu sein, um die gesamte Systemarchitektur zu "panieren". Haben Sie (und könnten Sie es teilen?) Eine Art übergeordnetes Datenflussdiagramm für den Algorithmus und können Sie uns eine Vorstellung von der Menge der beteiligten Daten geben? Ohne die Beantwortung solcher Fragen wird es wirklich schwierig sein, Ihnen etwas anderes als nur sehr allgemeine Ratschläge zu geben.
Dave Tweed
Es ist eigentlich ein sehr sehr einfacher Algorithmus, es ist nur die Skala, die es so kompliziert macht. Grundsätzlich wie folgt: Anfangsbedingungen -> 512 ffts parallel -> 32768 Multiplikationsoperationen am FFT-Ausgang -> Anfangsbedingungen anpassen -> spülen und wiederholen
1.
1

Es ist möglich, eine spezielle Hardware oder ein FPGA (oder sogar eine CPLD) zu verwenden, um bestimmte Arten von Rechenoperationen erheblich zu beschleunigen. Wenn Sie versuchen, Hardware (Schaltkreise oder FPGA-Logik) zur Beschleunigung von Rechenoperationen zu entwerfen, müssen Sie vor allem herausfinden, welche Auftragsdaten in Ihr Gerät eingegeben und aus diesem entfernt werden müssen. Ein Gerät mit einem effizienten E / A-Layout bietet möglicherweise eine viel bessere Leistung als ein Gerät mit einem ineffizienten Layout, selbst wenn das letztgenannte Gerät viel mehr Schaltkreise benötigt.

Ich habe nicht versucht, ein Hardware-Assist-Design für eine FFT zu entwickeln, aber eines, das ich mir angesehen habe, ist die Hardware-Unterstützung für große Multiplikationsoperationen (wie sie für die RSA-Verschlüsselung verwendet werden könnten). Viele Mikrocontroller, selbst solche mit spezieller Hardware für die schnelle Multiplikation, sind bei solchen Operationen nicht besonders effizient, da sie viel Register-Shuffling erfordern. Hardware, die entwickelt wurde, um das Austauschen von Registern zu minimieren, könnte mit Multiplikationsoperationen mit Mehrfachgenauigkeit eine viel bessere Leistung erzielen, selbst wenn die Hardware selbst nicht so hoch entwickelt wäre. Beispielsweise kann Hardware, die eine 16 × N-Pipeline-Multiplikation mit zwei Bits gleichzeitig durchführen kann (Verschieben von zwei unteren Bits des Multiplikators und Herausschieben von zwei oberen Bits des Ergebnisses), eine bessere Leistung erzielen als Hardware, die eine 8 × 8-Multiplikation in einem Zyklus durchführen kann. obwohl erstere möglicherweise weniger Schaltkreise benötigen (und aufgrund von Pipelining einen kürzeren kritischen Datenpfad haben). Der Schlüssel besteht darin, herauszufinden, wie die "innere Schleife" des erforderlichen Codes aussehen wird, und herauszufinden, ob es irgendwelche Ineffizienzen gibt, die leicht beseitigt werden können.

Superkatze
quelle
Welche Operationen eignen sich besonders für diese Form der Optimierung? Ich habe die Frage oben bearbeitet, um ein bisschen mehr über die Art der Multiplikationsoperation zu erfahren. Hardware-Assist-Design klingt wirklich interessant!
Stanri
0

Wie wenig Zeit kostet uns die Ausführung?

Dies scheint wirklich eine Situation zu sein, in der Sie eine Soft-MCU, ein FPGA mit integrierter Hard-MCU oder sogar ein separates MCU-Gerät implementieren und alle Ihre Vorgänge serialisieren sollten.

Vorausgesetzt, Sie haben die Ausführungszeit, ist das Ausführen Ihrer FFTs in Software sowohl viel einfacher zu debuggen als auch wahrscheinlich viel einfacher zu entwerfen.

Connor Wolf
quelle
1
Starke Berechnungen in einer Softcore-CPU auf einem FPGA sind dumm. Wenn Sie die Berechnung in einer gespeicherten Programmarchitektur durchführen möchten (etwas, das berücksichtigt werden sollte), liegt dies an Hochleistungs-CPU (s) in US-Dollar, bei denen Sie nicht die Geschwindigkeitsstrafe einer flexiblen Logik gegenüber einer vergleichbaren Architektur zahlen müssen. Generation harte Logik.
Chris Stratton
@ ChrisStratton - Guter Punkt. Fügte eine zusätzliche Anmerkung zu diesem Effekt hinzu.
Connor Wolf
1
Sogar die eingebauten Festplatten-CPUs werden herkömmlichen Prozessoren / GPUs für softwarebasierte Aufgaben keine Ehre machen und werden drastisch mehr kosten.
Chris Stratton
@ ChrisStratton - Ich dachte, die gebräuchlichste integrierte Hard-CPU-Architektur wäre entweder ARM oder POWER? In diesem Fall handelt es sich im Grunde genommen um eine Commodity-CPU.
Connor Wolf
1
In Anbetracht Ihrer anderen FPGA-Frage wird der Bau des FPGA-Boards wahrscheinlich eine Lernerfahrung sein, die einiges mehr kostet als angenommen. Ich denke, die Sache, die zu diesem Zeitpunkt zu tun wäre, wäre, dem Client einige harte Preis- / Leistungszahlen aus Test-Compute-Cloud-Läufen (die schließlich zu gekaufter Hardware werden könnten) gegenüber einer Vorstellung von dem höheren Preis und dem viel höheren Risiko des FPGA-Aufwands zu geben .
Chris Stratton