Parallel Cascaded Recursive Filtering on Multi-Core CPUs and GPUs

Stellen Sie sich vor, Sie versuchen, eine verrauschte Aufnahme Ihres Lieblingsliedes zu bereinigen, oder vielleicht bauen Sie einen Roboter, der sofort auf seine Umgebung reagieren muss. In beiden Fällen benötigen Sie einen digitalen „Filter“, um die guten Klänge von den schlechten zu trennen. Die leistungsfähigsten Werkzeuge für diese Aufgabe sind sogenannte rekursive Filter. Betrachten Sie diese wie eine magische Echokammer: Um zu bestimmen, wie der nächste Klang aussehen soll, schaut der Filter auf den aktuellen Klang und auf die Klänge, die er vor einem Moment selbst erzeugt hat. Dieses „Zurückschauen“ macht sie unglaublich effizient, da sie nur sehr wenig Rechenleistung für komplexe Aufgaben benötigen. Es gibt jedoch einen Haken: Da jeder neue Klang von dem vorherigen abhängt, muss der Filter Schritt für Schritt arbeiten, wie eine einzelne Person, die einen langen Flur entlangläuft. Dies erzeugt einen Engpass, der alles verlangsamt, wenn man riesige Mengen an Daten verarbeiten muss, wie etwa hochaudefinitionierte Videos oder das Radio in Echtzeit.

Jahrzehntelang haben Wissenschaftler versucht, dies zu beschleunigen, indem sie mehr Computer zur Hilfe nahmen. Die Herausforderung besteht darin, dass es schwierig ist, die Arbeit auf viele Computer aufzuteilen, da diese verwirrt sind, wenn sie alle darauf warten müssen, dass der Vorgänger seinen Schritt abschließt, bevor sie selbst weitermachen können. Es ist wie bei einem Staffellauf, bei dem die Läufer darauf warten müssen, den Stab zu erhalten, selbst wenn sie auf verschiedenen Bahnen stehen. Dieses Paper befasst sich genau mit diesem Problem. Es nutzt einen cleveren mathematischen Trick, der bereits auf einem einzelnen, superschnellen Computerchip bewiesen wurde, und skaliert diesen auf moderne Multi-Core-Computer und leistungsstarke Grafikkarten (GPUs). Den Autoren ist es gelungen, diese Computer zusammenarbeiten zu lassen, ohne dass sie aufeinander warten müssen, wodurch sie einen langsamen, einspurigen Pfad in eine Hochgeschwindigkeits-Autobahn mit vielen Spuren verwandeln und Geschwindigkeiten erreichen, die für diese Art von Mathematik bisher als unmöglich galten.

Das Staffellauf-Problem und der magische Trick

Um den Durchbruch zu verstehen, schauen wir uns an, wie diese Filter normalerweise funktionieren. Stellen Sie sich eine lange Reihe von Menschen vor, die eine Nachricht in einer Kette weitergeben. Jeder Mensch muss warten, bis die Person vor ihm ihm die Nachricht zugeflüstert hat, bevor er seinen eigenen Teil hinzufügen und sie weitergeben kann. Dies ist der „rekursive“ Teil. Wenn man eine lange Kette hat, dauert es lange, bis die Nachricht am Ende ankommt.

Die Autoren dieses Papers hatten bereits einen Weg gefunden, eine lange Kase in kleinere Stücke oder „Blöcke“ aufzuteilen, die schneller verarbeitet werden können. Doch als sie versuchten, diese Blöcke gleichzeitig an viele Computer (wie ein Team von Arbeitern) zu verteilen, trat ein neues Problem auf: Das Ende eines Blocks ist der Ausgangspunkt für den nächsten Block. Wenn man Block A an Arbeiter 1 und Block B an Arbeiter 2 gibt, steckt Arbeiter 2 fest und wartet darauf, dass Arbeiter 1 mit Block A fertig wird, bevor er mit Block B beginnen kann. Das Team arbeitet also am Ende doch wieder nacheinander, was den Zweck eines Teams zunichtemacht.

Die Hauptentdeckung des Papers ist ein mathematischer „magischer Trick“ namens Superposition. Anstatt auf die Antwort des vorherigen Blocks zu warten, raten die Arbeiter, wie die Antwort wäre, wenn sie mit Null starten würden (eine „Nullzustands“-Vermutung). Diese Berechnung führen sie sofort durch. Dann warten sie auf die tatsächliche Startzahl vom vorherigen Arbeiter. Sobald diese eintrifft, fügen sie einfach eine kleine „Korrektur“ zu ihrer Vermutung hinzu. Es ist wie ein Koch, der eine Suppe basierend auf einem Rezept kocht, unter der Annahme, dass er noch keine Zutaten hat. Wenn der Lieferwagen schließlich das tatsächliche Gemüse ablädt, fügt der Koch es einfach hinzu und rührt um. Die Suppe ist fast sofort fertig, weil die harte Arbeit des Kochens bereits parallel erledigt wurde.

Zwei verschiedene Arten, den Wettlauf zu bestreiten

Das Paper zeigt, dass dieser magische Trick auf zwei sehr unterschiedliche Arten verwendet werden kann, je nachdem, was man erreichen möchte.

1. Der Echtzeit-Stream (Das Fließband)
Wenn Sie Live-Daten verarbeiten, wie etwa eine Radiosendung, können Sie nicht warten, bis die gesamte Charge fertiggestellt ist, bevor Sie die nächste Sekunde Audio abspielen. Sie müssen die Daten in der exakt gleichen Reihenfolge ausgeben, in der sie reinkamen (First-In, First-Out).

• Die Lösung: Die Autoren haben eine „Wavefront-Pipeline“ für Multi-Core-CPUs gebaut. Stellen Sie sich ein Fließband vor, auf dem verschiedene Arbeiter gleichzeitig verschiedene Stadien desselben Liedes bearbeiten. Arbeiter 1 bereinigt den Bass, Arbeiter 2 korrigiert den Gesang und Arbeiter 3 fügt das Echo hinzu. Sobald Arbeiter 1 einen Block fertiggestellt hat, übergibt er ihn an Arbeiter 2, der ihn an Arbeiter 3 weitergibt.
• Das Ergebnis: Auf einem modernen Computer mit sechs leistungsstarken Kernen erreichte diese Methode eine Geschwindigkeit von 2,4 Gigasamples pro Sekunde für einen komplexen 16. Ordnung gefilterten Prozess. Das ist fast 4-mal schneller als die Verwendung eines einzelnen Kerns. Interessanterweise stellten sie fest, dass das Hinzufügen langsamerer „Effizienz“-Kerne zur Mischung die Linie tatsächlich verlangsamte, was beweist, dass für diese spezifische Aufgabe ein paar schnelle Arbeiter besser sind als viele langsame.

2. Die Batch-Verarbeitung (Die Fabrik)
Wenn Sie eine riesige Datei mit aufgezeichneten Daten verarbeiten (wie einen Film oder eine Datenbank), ist Ihnen die Reihenfolge weniger wichtig als die reine Geschwindigkeit. Sie können die gesamte Datei auf einmal verarbeiten.

• Die Lösung: Sie verwendeten leistungsstarke Grafikprozessoren (GPUs), die über Tausende von winzigen Arbeitern verfügen. Sie nutzten eine Technik namens Decoupled Lookback. Stellen Sie sich eine Fabrik vor, in der jeder Arbeiter seinen Teil des Produkts sofort berechnet. Wenn ein Arbeiter einen Teil aus der vorherigen Station benötigt, hält er nicht an; er schaut stats auf ein „Statusboard“, um zu sehen, ob die vorherige Station fertig ist. Wenn ja, nimmt er den Teil. Wenn nicht, arbeitet er an anderen Den, bis er bereit ist.
• Das Ergebnis: Dieser Ansatz war unglaublich schnell. Auf einer NVIDIA RTX 3060 Grafikkarte erreichte das System 38,2 Gigasamples pro Sekunde für einen einzelnen Filterabschnitt. Dies entspricht 85 % der absoluten maximalen Geschwindigkeit, die die Hardware theoretisch leisten kann (das „Memory Bandwidth Roof“).

Warum das wichtig ist und womit es konkurriert

Die Autoren haben die Dinge nicht nur schneller gemacht; sie haben auch bewiesen, dass ihre Methode zuverlässiger ist als ältere Wege.

• Das Versagen der „Direkten Form“: Es gibt eine ältere Methode namens „Direct Form“, die versucht, die Mathematik in einem einzigen riesigen Schritt zu erledigen. Das Paper zeigt, dass diese alte Methode bei komplexen Filtern (wie einem 16. Ordnung Filter) versagt. Die Zahlen werden so chaotisch, dass der Computer beginnt, Müll zu produzieren oder abstürzt. Die in diesem Paper verwendete neue „kaskadierte“ Methode bleibt selbst auf diesem hohen Niveau präzise.
• Den Wettbewerb schlagen: Sie verglichen ihren neuen GPU-Code mit den stärksten existierenden parallelen Filter-Engines. Ihre Methode war bei jeder getesteten Filterordnung schneller.
• Die Kosten der Geschwindigkeit: Das Paper hat auch sorgfältig den „Preis“ ihrer Geschwindigkeit gemessen. Sie fanden heraus, dass auf neueren, schnelleren Chips (wie dem RTX 3060) die „Barrieren“ (die Checks, die Arbeiter machen, um fortzufahren) günstig sind, sodass sie komplexere, schnellere Methoden verwenden können. Auf älteren Chips sind diese Checks teuer, weslich müssen sie einfachere Methoden verwenden. Dies hilft Ingenieuren zu wissen, wie sie ihre Software genau auf die jeweilige Hardware abstimmen können.

Das Fazit

Dieses Paper verwandelt ein schwieriges, sequenzielles Mathematikproblem in eine parallele Party. Durch eine clevere „Rate-und-Korrigiere“-Strategie haben sie es ermöglicht, dass Computer zusammenarbeiten, ohne aufeinander warten zu müssen.

• Für das Live-Streaming haben sie eine Pipeline gebaut, die 3,95-mal schneller läuft als ein Standardcomputer.
• Für die Batch-Verarbeitung haben sie eine GPU-Engine gebaut, die mit 38,2 Gigasamples pro Sekunde arbeitet, was ein massiver Sprung nach vorne ist.
• Entscheidend ist, dass sie bewiesen haben, dass diese Methode nicht nur schneller arbeitet, sondern auch besser ist, da sie dort präzise bleibt, wo ältere Methoden versagen.

Die Autoren haben ihren Code als Open-Source-Bibliothek zur Verfügung gestellt, was bedeutet, dass nun jeder diese superschnellen Filter nutzen kann, um bessere Audio-Tools, klarere Videos und intelligentere Roboter zu bauen. Sie haben effektiv einen „sequenziellen“ Engpass in eine „parallele“ Superhighway verwandelt und gezeigt, dass selbst die hartnäckigsten mathematischen Probleme gelöst werden können, indem man ein Team von Computern synchron zusammenarbeiten lässt.