Code-Optimierung Implementierung eines schnellen FIR-Filters mit dem Atom-Prozessor

Hochsprachen-Entwicklungswerkzeuge ermöglichen in der Regel die zügige Erstellung von effizientem Programmcode. Es gibt aber in der digitalen Signalverarbeitung Szenarien, bei denen die automatische Codegenerierung nicht ausreicht, um extremen Geschwindigkeitsanforderungen gerecht zu werden. Dieser Artikel beschreibt exemplarisch an der Implementierung eines FIR-Filters, wie rechenzeit-kritische Routinen mit Hilfe der Atom-Architektur bis auf wenige Prozent an das theoretisch mögliche Maximum heranzuführen sind.

FIR-Filter (Finite Impulse Response) sind eine der gebräuchlichsten Filterformen in der digitalen Signalverarbeitung. In der Programmiersprache C ausformuliert, liest sich z.B. die Berechnung von 640 Werten bei Anwendung eines Filters 63. Ordnung (die 64 Filterkoeffizienten sind, wie im weiteren Verlauf, gespiegelt) wie in Listing 1 dargestellt. Die Erhaltung des Filterzustands über mehrere Aufrufe hinweg muss dabei (wie generell im Folgenden) außerhalb der dargestellten Codebeispiele geregelt werden, z.B. durch Voranstellen der m vorhergehenden Eingangswerte vor x[]. Für eine schnellstmögliche Software- Implementierung von FIR-Filtern und anderen Signalverarbeitungs- Aufgaben auf der Atom-Architektur ist die Verwendung des SIMD-Befehlssatzes unabdingbar, wobei der Atom-Prozessor alle Instruktionen bis SSSE3 unterstützt (Supplemental Streaming SIMD Extensions). Die 128 bit Datenbreite dieser Instruktionen können dem gewünschten Datentyp entsprechend unterteilt werden.


Bei 16-bit-Integer-Daten (bzw. durch Umdeutung 16-bit-Fixpoint) können so in einer Instruktion acht Operationen ausgeführt werden. Die Atom- Architektur kann bis zu zwei SIMDAdditionsbefehle pro Prozessor- Taktzyklus ausführen, womit theoretisch auf einer 1-GHz-CPU 16 Milliarden 16-bit-Additionen pro Sekunde ablaufen können. Multiplikationen dauern etwas länger (ein SIMD-Integer-Multiplikationsbefehl jeden zweiten Prozessor-Taktzyklus). Für Gleitkomma- Operationen gelten wiederum andere Durchsatzzahlen. Das Herzstück einer SSE-basierenden 16-bit-FIR-Filter-Implemetierung ist die SSE-Instruktion pmaddwd, die parallel acht 16x16-bit-Multiplikationen ausführt. Die resultierenden acht 32-bit-Ergebnisse werden sofort paarweise summiert und passen in ein 128- bit-Ergebnisregister (Bild 1).

Listing 2 zeigt Assembler-Code, der die oben gelistete FIR-Filterroutine mit 16-bit-Datentypen implementiert. Da die Multiplikationen voneinander unabhängig sind und die Reihenfolge der Additionen unerheblich ist, kann die Berechnung gut parallelisiert werden. Jeder Durchlauf der inneren Schleife berechnet eine Filterantwort für ein Filter 63. Ordnung. Die vier Teilwerte werden dann außerhalb der Schleife aufsummiert. Die äußere Schleife wiederholt den Vorgang für alle zu berechnenden Samples. Als Randbedingungen sind dabei zu beachten, dass die Filter-Ordnung um 1 unter einem Vielfachen von 8 sein muss und die Filter-Koeffizienten auf einer durch 16 teilbaren Speicheradresse liegen müssen (16-byte- Alignment, wie die meisten Speicherzugriffe durch SSE-Befehle). Durch SSE-Instruktionen liegt die Ausführungszeit bereits deutlich unter der einer C-Referenzimplementierung. Für 640 Werte wurden ca. 70 480 CPU-Taktzyklen gemessen. Die Atom-Architektur ist freilich prinzipiell in der Lage, jeden zweiten CPU-Taktzyklus acht „Multiply-Accumulate“-Operationen anzustoßen, könnte also die 640 x 64 = 40 960 Multiplikationen in 10 240 Taktzyklen berechnen, also fast sieben Mal so schnell. Wie erklärt sich diese Diskrepanz, und vor allem: Wie lässt sich die Leistung des Filters weiter verbessern?