Algorithmen FPGAs dominieren CPUs auf

Question

Die meiste Zeit meines Lebens habe ich CPUs programmiert; und obwohl für die meisten Algorithmen die Big-Oh-Laufzeit auf CPUs/FPGAs gleich bleibt, sind die Konstanten ziemlich verschieden (zum Beispiel wird viel CPU-Leistung verschwendet, um Daten umzuschleifen; während für FPGAs oft compute-gebunden ist).

Ich mag würde mehr darüber erfahren - weiß jemand gute Bücher/Referenzpapiere/Tutorials, die von mit dem Thema befasst:

welche Aufgaben FPGAs beherrschen Sie CPUs auf (in Bezug auf die reine Geschwindigkeit) welche Aufgaben zu tun FPGAs CPUs auf (in Bezug auf die Arbeit pro jule) dominieren

Hinweis: markierte Community Wiki

Answer 1

[keine Links, nur meine überlegungen]

FPGAs sind im Wesentlichen Dolmetscher für Hardware! Die Architektur ist wie dedizierte ASICs, aber um eine schnelle Entwicklung zu bekommen, und Sie bezahlen einen Faktor von ~ 10 in der Frequenz und einen [nicht wissen, mindestens 10?] Faktor in der Energieeffizienz.

Also nehmen Sie jede Aufgabe, wo dedizierte HW kann massiv CPUs übertreffen, durch die FPGA 10/[?] Faktoren zu teilen, und Sie werden wahrscheinlich immer noch einen Gewinner haben. Typische Eigenschaften solcher Aufgaben:

• Massive Möglichkeiten für feinkörnige Parallelität.
  (Doing 4 Operationen auf einmal zählt nicht; 128 tut.)
• Gelegenheit für tiefe Pipelining.
  Dies ist auch eine Art von Parallelität, aber es ist schwierig, es auf eine Einzelaufgabe anzuwenden, so dass es hilft, wenn Sie viele bis parallel arbeiten können.
• (Meistens) Feste Datenfluss Pfade.
  Einige Muxes sind in Ordnung, aber massive zufällige Zugriffe sind schlecht, weil Sie nicht parallelisieren können. Aber siehe unten über Erinnerungen.
• Hohe Gesamtbandbreite zu viele kleine Erinnerungen.
  FPGAs haben Hunderte von kleinen (O (1KB)) internen Speichern (BlockRAMs im Xilinx-Sprachgebrauch). Wenn Sie also die Speicherauslastung in viele unabhängige Puffer aufteilen können, können Sie eine Bandbreite von CPUs genießen.
• Kleine externe Bandbreite (im Vergleich zu internen Arbeiten). Die ideale FPGA-Task hat kleine Ein- und Ausgänge, erfordert aber eine Menge interner Arbeit. Auf diese Weise wird Ihr FPGA nicht warten, bis es auf I/O wartet. (CPUs leiden bereits unter dem Verhungern, und sie lindern es mit sehr hoch entwickelten (und großen) Caches, die in FPGAs unkompatibel sind.) Es perfekt möglich ist eine große I/O-Bandbreite zu einem FPGA (~ 1000 Pins nowdays, einige mit hohen Rate SERDESes) zu verbinden - aber das tun erfordert ein eigenes Board für solche Bandbreite architected; In den meisten Fällen ist Ihr externer E/A ein Engpass.
• Einfach genug für HW (aka gut SW/HW Partitionierung).
  Viele Aufgaben bestehen zu 90% aus unregelmäßigen Kleberlogik und nur 10% harte Arbeit ("Kernel" im Sinne von DSP). Wenn Sie all das auf ein FPGA setzen, verschwenden Sie kostbare Bereich auf Logik, die die meiste Zeit nicht arbeitet . Idealerweise wollen Sie, dass alle Muck in SW behandelt werden und die HW für den Kernel voll nutzen. („Soft-Core“ CPUs innerhalb FPGAs sind eine beliebte Art und Weise viele langsam unregelmäßiger Logik auf mittleren Bereich zu packen, wenn Sie es nicht zu einem realen CPU-Offload können.)
• Weird-Bit-Manipulationen sind ein Plus.
  Dinge, die nicht gut auf herkömmliche CPU-Befehlssätze Karte wie unaligned Zugriff auf gepackten Bits, Hash-Funktionen, Kodierung & Kompression ... jedoch nicht überschätzen den Faktor ergibt dies Sie - die meisten Datenformate und Algorithmen, die Sie erfüllen werden, sind bereits wurden entworfen, um CPU-Befehlssätze leicht zu gehen, und CPUs halten hinzufügen spezialisierte Anweisungen für Multimedia.
  Viele Fließkomma ist speziell ein Minus, weil sowohl CPUs und GPUs sie auf extrem optimierten dedizierten Silizium knirschen. (Sogenannte „DSP“ FPGAs haben auch viele engagierte mul/add Einheiten, aber AFAIK diese nur ganze Zahlen tun?)
• Niedrige Latenz/Echtzeitanforderungen sind ein Plus.
  Hardware kann wirklich unter solchen Anforderungen glänzen.

EDIT: Mehrere dieser Bedingungen - esp. feste Datenflüsse und viele separate Aufgaben zu bearbeiten - auch aktivieren bit slicing auf CPUs, die das Feld etwas Ebenen.

Answer 2

Für reine Geschwindigkeit: - Paralizable diejenigen - DSP, zB Videofilter - Bewegliche Daten, z.B. DMA

Answer 3

Nun, die neueste Generation der Xilinx-Teile, die gerade mit 4.7TMACS und Allzwecklogik bei 600MHz angepriesen werden. (Dies sind im Grunde Virtex 6s fabbed in einem kleineren Prozess.) Auf einem Tier wie diesem, wenn Sie Ihre Algorithmen in Festkommaoperationen implementieren können, hauptsächlich multiplizieren, addieren und subtrahieren, und profitieren Sie sowohl von Wide-Parallelismus und Pipeline-Parallelität Sie können die meisten PCs lebend essen, sowohl in Bezug auf die Leistung als auch auf die Verarbeitung.

Sie können auf diesen schweben, aber es wird einen Leistungseinbruch geben. Die DSP-Blöcke enthalten einen 25x18-Bit-MACC mit einer 48-Bit-Summe. Wenn Sie mit Oddball-Formaten durchkommen und einen Teil der Gleitkomma-Normalisierung, die normalerweise auftritt, umgehen, können Sie trotzdem eine Lastwagenleistung aus diesen herausholen. (d. h. Verwenden Sie den 18Bit-Eingang als Strait-Fixpunkt oder Float mit einer 17-Bit-Mantisie anstelle des normalen 24-Bit.) Doubles Floats werden eine Menge Ressourcen verbrauchen. Wenn Sie das brauchen, werden Sie wahrscheinlich besser auf einem PC arbeiten.

Wenn Ihre Algorithmen als Add-und Subtract-Operationen ausgedrückt werden können, dann kann die allgemeine Logik in diesen verwendet werden, um Gazillion Addierer zu implementieren. Dinge wie Bresenhams Linie/Kreis/Yadda/Yadda/Yadda-Algorithmen sind sehr gute Anpassungen für FPGA-Designs.

Wenn Sie Division ... EH ... es ist schmerzhaft, und wahrscheinlich wird relativ langsam, es sei denn, Sie können Ihre Divisionen als Multiplikationen implementieren.

Wenn Sie viele hohe Percision-Trigger-Funktionen brauchen, nicht so viel ... Wieder kann es getan werden, aber es wird nicht schön oder schnell sein. (So ​​wie es bei einem 6502 möglich ist.) Wenn Sie nur mit einer Nachschlagetabelle über einen begrenzten Bereich umgehen können, dann ist Ihr golden!

Apropos 6502, ein 6502 Demo Coder könnte eines dieser Dinge zum Singen bringen. Jeder, der mit all den alten mathematischen Tricks vertraut ist, die Programmierer auf der alten Schulmaschine benutzten, wird immer noch gelten. Alle Tricks, die der moderne Programmierer Ihnen sagt, "lassen Sie die Bibliothek für Sie tun" sind die Arten von Dingen, die Sie wissen müssen, um Mathematik auf diesen zu implementieren. Wenn Sie ein Buch finden, in dem es darum geht, 3d auf einem 68000 basierten Atari oder Amiga zu schreiben, werden Sie viel darüber diskutieren, wie man Zeug nur in ganzen Zahlen implementiert.

TATSÄCHLICH sind alle Algorithmen, die mit Hilfe von Nachschlagetabellen implementiert werden können, SEHR gut geeignet für FPGAs. Sie haben nicht nur Blockrams, die durch das Teil verteilt sind, sondern die Logikzellen selbst können auch als verschieden große LUTS und Mini-Rams konfiguriert werden.

Sie können Dinge wie feste Bitmanipulationen als GRATIS anzeigen! Es ist einfach zu handhaben durch Routing. Fixed Shifts oder Bit Reversals kosten nichts. Dynamische Bitoperationen, wie die Verschiebung um einen variablen Betrag, kosten eine minimale Menge an Logik und können ausgeführt werden, bis die Kühe nach Hause kommen!

Der größte Teil hat 3960 Multiplikatoren! Und 142.200 Scheiben, JEDER kann ein 8-Bit-Addierer sein. (4 6Bit Luts pro Scheibe oder 8 5Bit Luts pro Scheibe je nach Konfiguration.)

Answer 4

Wählen Sie einen gnarly SW-Algorithmus. Unsere Firma macht HW-Beschleunigung von SW Algo für ihren Lebensunterhalt.

Wir haben HW-Implementierungen von regulären Ausdrücken gemacht, die 1000er Regel-Sets parallel mit Geschwindigkeiten von bis zu 10 Gb/Sek. Der Zielmarkt dafür sind Router, bei denen Anti-Virus und ips/ids in Echtzeit laufen können, während die Daten streamen, ohne dass der Router verlangsamt wird.

Wir haben HD-Videokodierung in HW getan. Für die Konvertierung in HD benötigte man pro Sekunde mehrere Stunden Verarbeitungszeit. Jetzt können wir es fast in Echtzeit machen ... es dauert fast 2 Sekunden Verarbeitung, um 1 Sekunde Film zu konvertieren. Netflix verwendete unsere HW fast ausschließlich für ihr Video-on-Demand-Produkt.

Wir haben sogar einfache Dinge wie RSA, 3DES und AES-Verschlüsselung und Entschlüsselung in HW gemacht. Wir haben einfach Zip/Unzip in HW gemacht. Der Zielmarkt dafür ist für Sicherheitsvideokameras. Die Regierung hat einige riesige Videokameras, die riesige Ströme von Echtzeitdaten erzeugen. Sie zippen es in Echtzeit herunter, bevor sie es über ihr Netzwerk senden, und entpacken es dann am anderen Ende in Echtzeit.

Heck, eine andere Firma, für die ich gearbeitet habe, benutzte früher Radarempfänger mit FPGAs. Sie würden die digitalisierten feindlichen Radardaten direkt mit mehreren verschiedenen Antennen abtasten und aus dem Zeitdelta der Ankunft herausfinden, in welche Richtung und wie weit der gegnerische Sender entfernt ist. Verdammt, wir konnten sogar die unbeabsichtigte Pulsmodulation der Signale in den FPGAs überprüfen, um den Fingerabdruck bestimmter Sender herauszufinden, damit wir wissen, dass dieses Signal von einer bestimmten russischen SAM-Seite kommt, die an einer anderen Grenze stationiert war damit wir Waffenbewegungen und Verkäufe verfolgen können.

Versuchen Sie das in Software zu tun !! :-)