Notwendigkeit für schnelles Demultiplexen von Daten in C # durch Verwendung von Multithreading, AVX, GPU oder was auch immer
Ich habe eine ziemlich einfache Funktion, die von einer Karte erfasste Daten demultiplext. Die Daten kommen also durch Rahmen, jeder Rahmen, der aus mehreren Signalen besteht, als ein 1-dim-Array und ich muss in gezackte Arrays konvertieren, eines für jedes Signal. Grundsätzlich folgendes:
Ich arbeite in C #, aber ich habe eine Kernfunktion in C, die die Arbeit für ein einzelnes Signal erledigt:
%Vor% und dann rufe ich es über C ++ / CLI (mit pin_ptr<short> , also keine Kopie) von C # und mit parallel für:
Die muxed Daten stammen aus 16k Signalen (16bit Auflösung), jedes Signal hat 20k Samples / s, was eine Datenrate von 16k * 20k * 2 = 640MB / s ergibt. Wenn der Code auf einer Workstation mit 2 Xeon E5-2620 v4 (insgesamt 16 Kerne bei 2,1 GHz) ausgeführt wird, dauert es etwa 115% zu demuxen (für 10s von Daten dauert es 11,5s).
Ich muss mindestens die Hälfte der Zeit runtergehen. Kennt jemand irgendeinen Weg, vielleicht mit AVX-Technologie oder besser einer Hochleistungsbibliothek dafür? Oder gibt es einen Weg, GPU zu verwenden? Ich würde es vorziehen, die CPU-Hardware nicht zu verbessern, weil das wahrscheinlich mehr kostet.
Bearbeiten
Bitte beachten Sie, dass sich nSignals und nValuesPerSignal ändern können und dass das verschachtelte Array in nSignals separate Arrays aufgeteilt werden muss, um in C # weiterverarbeitet zu werden.
Bearbeiten: weitere Tests
In der Zwischenzeit habe ich nach der Bemerkung von Cody Gray mit einem einzigen Kern getestet:
%Vor%aus C ++ / CLI aufgerufen:
%Vor%und ich erhalte eine Rechenzeit von ca. 105%, das ist zu viel aber zeigt deutlich, dass Parallel.For nicht die richtige Wahl ist. Von Ihren Antworten denke ich, dass die einzige brauchbare Lösung SSE / AVX ist. Ich habe nie Code dafür geschrieben. Könnten einige von Ihnen mich in die richtige Richtung weisen? Ich denke, wir können annehmen, dass der Prozessor immer AVX2 unterstützt.
Edit: mein ursprünglicher Code vs Matt Timmermans Lösung
Auf meinem Rechner habe ich meinen ursprünglichen Code (wo ich einfach Parallel.For verwendet habe und eine C-Funktion für das Deinterlacing eines einzelnen Signals anruft) mit dem von Matt Timmermans vorgeschlagenen Code verglichen (immer noch mit Parallel.For , aber auf eine cleverere Art und Weise) ). Siehe Ergebnisse (in ms) gegen die Anzahl der Aufgaben in Parallel.For (ich habe 32 Threads):
So sind die Leistungen sehr verbessert. Ich werde jedoch noch einige Tests mit der AVX-Idee machen.
2 Antworten
Wie ich in einem Kommentar erwähnt habe, schießt du dir sehr wahrscheinlich hier in den Fuß, indem du Parallel.For benutzt. Der Overhead von mehreren Threads ist viel zu groß für die Kosten dieser einfachen Operation. Wenn Sie die rohe Geschwindigkeit so sehr benötigen, dass Sie herunterfahren, um dies in C ++ zu implementieren, sollten Sie C # überhaupt nicht für etwas verwenden, das für die Performance kritisch ist.
Stattdessen sollten Sie zulassen, dass der C ++ - Code mehrere Signale gleichzeitig verarbeitet. Ein guter C ++ - Compiler verfügt über einen weitaus leistungsfähigeren Optimierer als der C # JIT-Compiler. Daher sollte er in der Lage sein, den Code automatisch zu vektorisieren, sodass Sie etwas lesbares und dennoch schnelles schreiben können. Mit den Compiler-Switches können Sie auf einfache Weise angeben, welche Befehlssätze auf Ihren Zielmaschinen verfügbar sind: SSE2, SSSE3, AVX, AVX2 usw. Der Compiler gibt automatisch die entsprechenden Anweisungen aus.
Wenn dies immer noch nicht schnell genug ist, könnten Sie in Betracht ziehen, den Code manuell mit intrinsischen Mitteln zu schreiben, damit die gewünschten SIMD-Befehle ausgegeben werden. Es ist unklar, wie variabel die Eingabe ist. Ist die Anzahl der Frames konstant? Was ist mit der Anzahl der Werte pro Signal?
Wenn Sie annehmen, dass Ihre Eingabe genau wie das Diagramm aussieht, könnten Sie die folgende Implementierung in C ++ schreiben, wobei Sie die Vorteile ausnutzen der Anweisung PSHUFB (unterstützt von SSSE3 und höher):
In einem 128-Bit-SSE-Register können wir 8 verschiedene 16-Bit short Werte einpacken. Daher lädt dieser Code innerhalb der Schleife die nächsten 8 short s aus dem Eingabearray, mischt sie neu, so dass sie in der gewünschten Reihenfolge sind, und speichert dann die resultierende Sequenz zurück in das Ausgabearray. Es muss genug Schleifen durchlaufen, um dies für alle Mengen von 8 short s im Eingabe-Array zu tun, also machen wir es count % 8 mal.
Der resultierende Assembler-Code sieht ungefähr wie folgt aus:
%Vor% (Ich schrieb diesen Code unter der Annahme, dass die Eingabe- und Ausgabe-Arrays beide auf 16-Byte-Grenzen ausgerichtet sind, wodurch ausgerichtete Lasten und Speicher verwendet werden können. Bei älteren Prozessoren ist dies schneller als bei nicht ausgerichteten Ladevorgängen; Bei Prozessoren ist die Strafe für nicht ausgerichtete Lasten praktisch nicht existent. Dies ist in C / C ++ einfach zu gewährleisten und zu erzwingen, aber ich bin mir nicht sicher, wie Sie den Speicher für diese Arrays im C # -Anrufer zuweisen. Dann sollten Sie in der Lage sein, die Ausrichtung zu steuern.Wenn dies nicht der Fall ist oder Sie nur auf späte Generationen von Prozessoren abzielen, die nicht ausgerichtete Lasten nicht benachteiligen, können Sie stattdessen den Code so ändern, dass nicht ausgerichtete Lasten verwendet werden.Verwenden Sie die _mm_storeu_si128 und _mm_loadu_si128 intrinsics , wodurch MOVDQU -Anweisungen anstelle von MOVDQA ausgegeben werden.)
Es gibt nur 3 SIMD-Anweisungen innerhalb der Schleife, und der erforderliche Schleifenoverhead ist minimal. Dies sollte relativ schnell sein, obwohl es fast sicher Möglichkeiten gibt, es noch schneller zu machen.
Eine wichtige Optimierung wäre, das wiederholte Laden und Speichern der Daten zu vermeiden. Insbesondere, um das Speichern der Ausgabe in einem Ausgabearray zu vermeiden. Je nachdem, was Sie mit der demuxierten Ausgabe tun tun möchten, wäre es effizienter, sie einfach in einem SSE-Register zu belassen und dort zu arbeiten. Dies wird jedoch (wenn überhaupt) nicht gut mit verwaltetem Code interagiert, so dass Sie sehr eingeschränkt sind, wenn Sie die Ergebnisse an einen C # -Aufrufer übergeben müssen.
Um wirklich effizienten SIMD-Code zu schreiben, möchten Sie ein hohes Verhältnis zwischen Berechnung und Laden / Speichern haben. Mit anderen Worten, Sie möchten die Daten zwischen den Ladungen und den Speichern sehr manipulieren. Hier führen Sie nur einen Vorgang (den Shuffle) für die Daten zwischen Laden und Laden aus. Leider gibt es keinen anderen Weg, es sei denn, Sie können den nachfolgenden "Verarbeitungs" -Code verschachteln. Demuxing erfordert nur eine Operation, was bedeutet, dass Ihr Flaschenhals unweigerlich die Zeit sein wird, die zum Lesen der Eingabe und Schreiben der Ausgabe benötigt wird.
Eine andere mögliche Optimierung wäre das manuelle Abrollen der Schleife. Dies führt jedoch zu einer Reihe möglicher Komplikationen und erfordert, dass Sie etwas über die Art Ihrer Eingabe wissen. Wenn die Eingabearrays im Allgemeinen kurz sind, ist das Abrollen nicht sinnvoll. Wenn sie manchmal kurz und manchmal lang sind, ist das Abrollen immer noch nicht sinnvoll, weil Sie sich explizit mit dem Fall befassen müssen, in dem das Eingangsarray kurz ist und früh aus der Schleife ausbricht. Wenn die Eingabe-Arrays immer ziemlich lang sind, kann das Abrollen ein Performance-Gewinn sein. Nicht unbedingt, obwohl; Wie oben erwähnt, ist der Schleifenoverhead hier minimal.
Wenn Sie basierend auf der Anzahl der Frames und der Anzahl der Werte pro Signal parametrieren müssen, werden Sie höchstwahrscheinlich mehrere Routinen schreiben müssen. Oder zumindest eine Vielzahl verschiedener mask s.Dies erhöht die Komplexität des Codes und damit die Wartungskosten (und möglicherweise auch die Leistung, da die benötigten Anweisungen und Daten weniger wahrscheinlich im Cache enthalten sind), es sei denn, Sie können wirklich etwas tun, das wesentlich mehr ist Optimaler als ein C ++ - Compiler sollten Sie in Erwägung ziehen, den Compiler den Code generieren zu lassen.
Gute Nachrichten! Sie benötigen nicht mehrere Kerne, SIMD oder ausgefallene Pakete, um dieses Problem zu lösen. Sie müssen wahrscheinlich nicht einmal nach C rufen.
Ihr Engpass ist die Speicherbandbreite, weil Sie sie ineffizient verwenden.
Mit dieser CPU ist Ihr Speicher wahrscheinlich schnell genug zum Demuxen & gt; 3 GB / s mit einem Kern, aber jedes Mal, wenn Sie eine Probe aus dem RAM benötigen, holt die CPU 64 Bytes, um eine Cache-Zeile zu füllen, und Sie verwenden nur 2 davon. Diese 64 Bytes bleiben eine Weile im Cache und einige andere Threads werden wahrscheinlich einige von ihnen verwenden, aber das Zugriffsmuster ist immer noch sehr schlecht.
Alles, was Sie wirklich tun müssen, ist, diese 64 Bytes gut zu nutzen. Es gibt viele Wege. Zum Beispiel:
1) Versuchen Sie eine einfache Schleife in C #. Führen Sie den Eingabepuffer von Anfang bis Ende durch, und stellen Sie jedes Sample dort auf, wo es hingehört. Dies verwendet alle 64 Bytes jedes Mal, wenn Sie eine Cache-Zeile beim Lesen füllen, und Ihre 16K-Ausgabekanäle sind so wenig, dass die Blöcke, in die Sie schreiben, größtenteils zwischengespeichert werden. Dies wird wahrscheinlich schnell genug sein.
2) Fahren Sie fort, die C-Funktion aufzurufen, aber verarbeiten Sie den Eingangspuffer in 2MB-Blöcken, und kümmern Sie sich nicht um mehrere Kerne. Jeder dieser 2MB-Chunks ist klein genug, um zwischengespeichert zu bleiben, bis Sie damit fertig sind. Dies wird wahrscheinlich ein bisschen schneller als (1) sein.
3) Wenn das obige nicht schnell genug ist (es kann nah sein), dann können Sie Multithread gehen. Verwenden Sie Methode (2), aber tun Sie eine parallele For über die Brocken. Auf diese Weise kann jeder Kern einen ganzen 2MB-Chunk erstellen, der seinen Cache gut ausnutzt, und sie werden nicht miteinander konkurrieren. Verwenden Sie höchstens 4 Threads, oder Sie können Ihren Cache erneut beanspruchen. Wenn Sie wirklich mehr als 4 Threads verwenden müssen, dann teilen Sie die Arbeit feiner in Gruppen von 1024 Kanälen innerhalb jedes 2MB Blocks oder so ... aber Sie müssen das nicht tun.
BEARBEITEN:
Oh, tut mir leid - die Option (1) ist in unsicheren C # ziemlich schwierig zu implementieren, weil jede fixed -Anweisung nur ein paar Zeiger behebt und verwaltete Arrays zu langsam ist. Option (2) ist jedoch leicht in unsicheren C # und funktioniert immer noch gut. Ich habe einen Test geschrieben:
Das sind eine Sekunde Daten und auf meiner Box steht:
%Vor%Hmmm .. das ist besser als Echtzeit, aber nicht doppelt so schnell wie in Echtzeit. Deine Kiste scheint etwas schneller zu sein als meine, also ist es vielleicht in Ordnung. Lasst uns die parallele Version ausprobieren (3). Die Hauptfunktion ist dieselbe:
%Vor%Das ist besser:
%Vor%Die Menge der Daten, die in diesem Fall gelesen und geschrieben werden, liegt bei ~ 4,6 GB / s, was etwas von meinem theoretischen Maximum von 6,4 GB / s abweicht, und ich habe nur 4 echte Kerne, also könnte ich es bekommen das ein wenig nach unten, indem man nach C ruft, aber es gibt nicht viel Raum für Verbesserungen.
Tags und Links algorithm c# multithreading performance avx