Die Effizienz und Leistungsfähigkeit von Gleitkomma-FPGAs wurden bisher durch lange Latenzen und Routing-Engpässe eingeschränkt. Darüber hinaus ist der traditionelle FPGA-Designprozess, der auf der Erstellung von Hardwarebeschreibungen auf Registerebene in Verilog oder VHDL basiert, für die Implementierung komplexer Gleitkomma-Algorithmen nicht optimal geeignet.
Altera hat einen neuen Design-Workflow für Gleitkommaarithmetik entwickelt, der die Implementierung von digitalen Gleitkomma-Signalverarbeitungsalgorithmen auf Altera-FPGAs vereinfacht und so die bisher höchste Leistungsfähigkeit und Effizienz dieser Designs ermöglicht. Anstatt einen Datenpfad aus elementaren Gleitkommaoperatoren (z. B. Multiplikation, Addition, Quadrieren) zu erstellen, generiert der Gleitkomma-Compiler einen Datenpfad, der elementare Operatoren zu einer einzigen Funktion oder einem einzigen Datenpfad kombiniert. Dadurch werden die in herkömmlichen Gleitkomma-FPGA-Designs vorhandenen Redundanzen eliminiert. Der Design-Workflow von Altera ist ein modellbasierter High-Level-Ansatz, der das Altera DSP Builder Advanced Blockset mit MATLAB und MathWorks Simulink nutzt. Altera erwartet, dass FPGA-Designer mit diesem High-Level-Ansatz komplexe Gleitkomma-Algorithmen schneller implementieren und verifizieren können als mit herkömmlichem HDL-basiertem Design.
BDTI hat eine unabhängige Analyse des Designprozesses für Gleitkomma-DSPs von Altera durchgeführt. Ziel von BDTI war es, die mit Altera-FPGAs erzielbare Leistung für anspruchsvolle Gleitkomma-DSP-Anwendungen zu ermitteln und die Benutzerfreundlichkeit des Designprozesses zu bewerten. Dieser Artikel präsentiert die Ergebnisse von BDTI sowie Hintergrundinformationen und Details zur verwendeten Methodik.
1. Einleitung
Zwei Beispiele für Gleitkomma-Design
Fortschritte bei digitalen Chips ermöglichen es, komplexe Algorithmen, die bisher der Forschung vorbehalten waren, in gängigen eingebetteten Computeranwendungen einzusetzen. Beispielsweise wird die lineare Algebra (insbesondere die Lösung von Systemen mit großen Mengen linearer Gleichungen) seit vielen Jahren hauptsächlich in der Forschung verwendet, wo umfangreiche Rechenressourcen zur Verfügung stehen und Echtzeitberechnungen im Allgemeinen nicht erforderlich sind. Die Lösung großer Systeme erfordert Matrixinversion oder eine Matrixzerlegung. Zusätzlich zu den Anforderungen an die Rechenkapazität können diese Verfahren unter numerischer Instabilität leiden, wenn kein ausreichender Dynamikbereich genutzt wird. Daher ist die effiziente und genaue Implementierung dieser Algorithmen nur auf Gleitkomma-Bausteinen praktikabel.
Altera hat kürzlich Gleitkomma-Berechnungsfunktionen in sein DSP Builder Advanced Blockset Toolkit integriert, um die Implementierung von Gleitkomma-DSP-Algorithmen auf Altera-FPGAs zu vereinfachen und die Leistung und Effizienz von Gleitkomma-Designs im Vergleich zu traditionellen FPGA-Designtechniken zu verbessern. In einem früheren Artikel [1] analysierte und bewertete BDTI die Leistung und Effizienz des Altera Quartus II v11.0 Software-Toolkits anhand einer Beispielimplementierung des Einkanal-Gleitkomma-Cholesky-Solvers, der für die 40 nm Stratix IV und Arria IV FPGAs synthetisiert wurde.
In diesem Artikel evaluieren wir die Effektivität der von Altera vorgeschlagenen Lösung mithilfe der neuen Version 12.0 des Softwaretools Quartus II und untersuchen die Leistungsfähigkeit der 28-nm-FPGAs Stratix V und Arria V von Altera. Für diese Evaluierung konzentrierte sich BDTI auf die Lösung einer großen Anzahl simultaner linearer Gleichungssysteme mithilfe zweier Zerlegungsverfahren: einer Mehrkanal-Cholesky-Matrixzerlegung und einer QR-Zerlegung mit dem Gram-Schmidt-Verfahren. Diese Zerlegungen liefern zusammen mit Vorwärts- und Rückwärtssubstitution eine Lösung für den Vektor x in einem simultanen System linearer Gleichungen der Form Ax = B.
Die Matrixzerlegung findet in zahlreichen militärischen Radaranwendungen, wie beispielsweise der raumzeitlichen adaptiven Signalverarbeitung (STAP), sowie bei verschiedenen Schätzproblemen in der digitalen Kommunikation Verwendung. Die QR-Zerlegung wird üblicherweise auf beliebige m x n-Matrizen A angewendet, während die Cholesky-Zerlegung aufgrund ihrer hohen Recheneffizienz der am weitesten verbreitete Algorithmus für quadratische, symmetrische, positiv definite Matrizen ist. Beide Zerlegungen verwenden rechenintensive Algorithmen, die eine hohe Datengenauigkeit erfordern und daher Gleitkommaoperationen notwendig machen. Darüber hinaus nutzen die beiden in diesem Artikel diskutierten Beispiele Skalarprodukte und verschachtelte Schleifen innerhalb des Algorithmus – Operationen, die in einer Vielzahl von Anwendungen der digitalen Signalverarbeitung im Zusammenhang mit linearer Algebra und FIR-Filtern (Finite Impulse Response) häufig vorkommen.
Die in diesem Artikel beschriebenen Beispiele lösen simultane Systeme linearer Gleichungen komplexer Daten mithilfe beider Methoden und präsentieren die Ergebnisse. Mit dem in Abschnitt 4 erläuterten QR-Solver kann ein Altera Stratix V FPGA 315 Matrixzerlegungen pro Sekunde der Größe 400x400 bei einer Geschwindigkeit von 203 MHz durchführen und erreicht dabei 162x10⁹ Gleitkommaoperationen pro Sekunde (GFLOPS).
Die beiden in diesem Artikel evaluierten Designbeispiele sind Bestandteil des Softwaretools DSP Builder v12.0 oder können über [Quelle fehlt] bestellt werden
Entwurfsablauf für Gleitkommaarithmetik:
FPGAs waren bisher nicht die bevorzugte Plattform für anspruchsvolle Gleitkommaanwendungen. Obwohl FPGA-Hersteller Bibliotheken mit Gleitkomma-Primitiven bereitstellen, war die Leistung von FPGAs in solchen Anwendungen stark eingeschränkt. Die Ineffizienz herkömmlicher Gleitkomma-FPGA-Designs ist teilweise auf die stark segmentierte Natur und die arithmetischen Strukturen der Gleitkommaoperatoren zurückzuführen, die hohe Datenpfadlatenzen und Routing-Engpässe verursachen. Diese Latenzen wiederum führen zu schwer zu handhabenden Problemen in datenabhängigen Designs. Das Endergebnis ist oft ein Design mit niedriger Betriebsfrequenz.
Der DSP Builder Advanced Blockset-Toolflow von Altera adressiert diese Hindernisse sowohl auf Architektur- als auch auf Systemebene. Der Gleitkomma-Compiler von Altera kombiniert große Abschnitte des Datenpfads zu einer einzigen Gleitkommafunktion, anstatt sie durch Komposition elementarer Gleitkommaoperatoren zu generieren. Dies wird durch die Analyse des Bitwachstums im Datenpfad und die Wahl der optimalen Eingangsnormalisierung erreicht, um entlang des Datenpfads ausreichende Präzision zu gewährleisten und so viele Normalisierungs- und Denormalisierungsschritte wie möglich zu eliminieren (siehe Abbildung 1). Das IEEE-754-Format wird nur an den Datenpfadgrenzen verwendet; im Datenpfad selbst werden größere Mantissenbreiten eingesetzt, um den Dynamikbereich zu erhöhen und den Bedarf an Normalisierungs- und Denormalisierungsschritten zwischen aufeinanderfolgenden Operatoren zu verringern. Normalisierungs- und Denormalisierungsfunktionen verwenden schnelle Barrel-Shifter mit einer Breite von bis zu 48 Bit für eine Gleitkommazahl einfacher Genauigkeit. Dies beansprucht erhebliche Logik- und Routing-Ressourcen und ist der Hauptgrund für die bisherige Ineffizienz von FPGA-basierten Gleitkomma-Implementierungen. Die kombinierte Datenpfad-Methodik eliminiert eine signifikante Anzahl schneller Barrel-Shifter. Höherpräzise Mantissenmultiplikationen nutzen den 27-Bit-x-27-Bit-Multiplizierermodus von Altera auf den Stratix-V- und Arria-V-Bausteinen. Abbildung 1(b) vergleicht die kombinierte Datenpfad-Methodik am Beispiel eines einfachen Strings mit zwei Addierern mit der herkömmlichen Implementierung aus Abbildung 1(a). Der kombinierte Datenpfad in Abbildung 1(b) eliminiert Interoperator-Redundanz, indem er die Denormalisierung des Ausgangs des ersten Addierers und die Normalisierung des Eingangs des zweiten Addierers unterdrückt. Durch den Wegfall zusätzlicher Logik und Routing-Maßnahmen sowie die Verwendung von Hardware-Multiplizierern werden Timing und Latenz auch für komplexe Datenpfade vorhersagbar. IEEE-754-Gleitkomma-Algorithmen mit einfacher und doppelter Genauigkeit werden mit weniger Logikressourcen und höherer Leistung implementiert. Altera gibt an, dass ein kombinierter Datenpfad die Logikressourcen und die Latenz im Vergleich zum äquivalenten Datenpfad mit elementaren Operatoren um 50 % reduziert [2]. Aufgrund der breiteren Darstellung interner Daten ist die Datengenauigkeit zudem in der Regel höher als bei einer Bibliothek, die elementare IEEE-754-Gleitkommaoperatoren verwendet.
Der Workflow für die Entwicklung von Gleitkomma-DSPs von Altera integriert das Altera DSP Builder Advanced Blockset und das Softwaretool Quartus II sowie MATLAB und MathWorks Simulink. Die Simulink-Umgebung ermöglicht es dem Entwickler, auf der Ebene des algorithmischen Verhaltens zu arbeiten, um komplexe Systeme zu beschreiben, zu debuggen und zu verifizieren. Simulink-Funktionen wie Datentypweitergabe und Vektordatenverarbeitung sind in das DSP Builder Advanced Blockset integriert und erlauben dem Entwickler, den algorithmischen Designraum schnell zu erkunden.
Um die Effizienz und Leistungsfähigkeit des Gleitkomma-Designprozesses von Altera zu evaluieren, validierte BDTI mithilfe des DSP Builder Advanced Blockset-Tools zwei Beispiele. Beide Beispiele beinhalteten die Lösung eines Systems simultaner linearer Gleichungen mit komplexen Datentypen in einer einfachgenauen Gleitkommadarstellung. Eine Lösung wurde mittels Cholesky-Zerlegung, die andere mittels QR-Zerlegung über das Gram-Schmidt-Verfahren erzielt. Abschnitt 2 dieses Artikels beschreibt die Implementierung der beiden Gleitkommabeispiele. Abschnitt 3 erläutert die Erfahrungen von BDTI mit dem Designprozess und dem Toolkit. Abschnitt 4 präsentiert die Leistungsfähigkeit der Implementierung auf zwei Altera-FPGAs: dem High-End-FPGA Stratix V 5SGSMD5K2F40C2n (mittlere Größe) und dem Arria V 5AGTFD7K3F40I3N (mittlere Größe). Abschließend präsentiert Abschnitt 5 die Schlussfolgerungen von BDTI.
2.
Hintergrundinformationen
Zahlreiche Anwendungen beinhalten Systeme linearer Gleichungen der Form Ax = b. Ob es sich um ein Optimierungsproblem mit linearen Ausgleichsrechnungen, einen Kalman-Filter zur Vorhersage eines Problems oder die Schätzung in einem MIMO-Kommunikationskanal handelt – das Problem besteht stets darin, eine numerische Lösung für ein System linearer Gleichungen der Form Ax = b zu finden. Für eine allgemeine Matrix der Größe m × n, wobei m die Höhe und n die Breite der Matrix ist, kann die QR-Zerlegung verwendet werden, um den Vektor x zu bestimmen. Der Algorithmus zerlegt A in eine orthonormale Matrix Q der Größe m × n und eine obere Dreiecksmatrix R der Größe n × n. Da Q orthonormal ist, gilt QTQ = I und Rx = QTb. Da R eine obere Dreiecksmatrix ist, kann x einfach durch Rückwärtseinsetzen berechnet werden, ohne dass die ursprüngliche Matrix A invertiert werden muss. Im QR-Beispiel dieses Artikels arbeiten wir mit überbestimmten Matrizen, für die m ≠ n gilt.
Wenn die Matrix A symmetrisch und positiv definit ist, wie beispielsweise bei den in vielen Problemen auftretenden Kovarianzmatrizen, werden üblicherweise die Cholesky-Zerlegung und ein Cholesky-Löser verwendet. Der Algorithmus berechnet die Inverse der Matrix A und löst somit den Vektor x als x = A⁻¹b. Die Cholesky-Zerlegung ist, abhängig vom verwendeten Zerlegungsalgorithmus, mindestens doppelt so effizient wie die QR-Zerlegung. Da diese Zerlegungsalgorithmen rekursiv sind und Divisionen beinhalten, ist mit zunehmender Matrixgröße ein großer numerischer Dynamikbereich erforderlich. In den meisten Fällen werden selbst bei so kleinen Matrizen wie 4x4, beispielsweise bei der MIMO-Kanalabschätzung, Gleitkommaoperationen durchgeführt. Für größere Systeme mit höheren Leistungsanforderungen, wie etwa in militärischen Anwendungen, ist die Gleitkomma-Geschwindigkeit für eingebettete Systeme oft nicht ausreichend. Entwickler verzichten daher häufig ganz auf den Algorithmus und suchen nach einer weniger optimalen Lösung oder greifen auf Hochleistungsprozessoren für Gleitkommaoperationen zurück, was zu höheren Kosten und einem größeren Entwicklungsaufwand führt.
Autor:
Vom Team von Berkeley Design Technology, Inc. Oktober 2012
(Fortsetzung im Februar)
