Beispiele für Allzweckalgorithmen, die von der Ausführung auf einer GPU profitiert haben? [geschlossen]

Ich suche nach Beispielen für Allzweckalgorithmen (dh nicht grafische Algorithmen), die nachweislich auf einer GPU eine Größenordnung schneller ausgeführt werden als auf einer CPU. Ich werde diese Beispiele verwenden, um kreativ über andere Algorithmen nachzudenken, die ich auf einer GPU implementieren könnte.

Ein paar Dinge fallen mir sofort ein:

Ein spezialisierter Bitcoin-Client wurde geschrieben, um die GPU zum Ausführen der kryptografischen Hashes zu verwenden. Der GPU-Client bietet auf einem typischen 4-Core-System im Allgemeinen eine mehr als 10-mal bessere Leistung als der SMP-CPU-Client. Bitcoin hängt von der Berechnung einer großen Anzahl nicht verwandter kryptografischer Hashes ab, die parallel berechnet werden können.

Das Folding @ Home-Projekt bietet einen GPU-Client für ihre molekulardynamischen Simulationen. Diese Berechnungen werden an den einzelnen Bindungen zwischen Atomen in verschiedenen Umgebungen und Bedingungen durchgeführt. Die Mathematik ist relativ einfach, muss jedoch milliardenfach für jede Bindung berechnet werden, um nur Nanosekunden Aktivität zu simulieren.

Das beliebte "Spielzeug" -Beispiel, das von Befürwortern des GPU-Computing verwendet wird, ist das N-Körper-Problem .

Gemeinsam ist diesen Dingen, dass sie peinlich parallel sind . Das heißt, das Problem kann in eine kleine Anzahl von diskreten Berechnungen zerlegt werden, die über einen großen Datensatz viele Male ausgeführt werden. Das ist die Art von Berechnung, in der die GPU gut ist.

Komplexe Berechnungen, die von den Ergebnissen früherer Berechnungen abhängen, sind für die GPU nicht gut geeignet.

Video- und Audio-Transcodierung ist ein gutes Beispiel. Es ist die Konvertierung von einem Dateiformat in ein anderes. Ein Beispiel ist MPEG-2 bis H.264.

_{Hinweis: Die Videotranscodierung bezieht sich nicht auf 3D-Grafiken. Sie können ein Video nicht mit einem Vertex- und Pixel-Shader codieren.}

Das Mining von Bitcoins mit einer GPU ist sehr beliebt geworden.

... Peer-to-Peer-E-Cash-System. Die Erstellung und Übertragung von Bitcoin basiert auf einem Open Source-Kryptografieprotokoll und wird von keiner zentralen Behörde verwaltet. Jedes Bitcoin ist in acht Dezimalstellen unterteilt und bildet 100 Millionen kleinere Einheiten, die als Satoshis bezeichnet werden. Bitcoins können ohne ein zwischengeschaltetes Finanzinstitut über einen Computer oder ein Smartphone übertragen werden.

Die Verarbeitung von Bitcoin-Transaktionen wird durch Server gesichert, die als Bitcoin-Miner bezeichnet werden. Diese Server kommunizieren über ein internetbasiertes Netzwerk und bestätigen Transaktionen, indem sie sie einem Hauptbuch hinzufügen, das regelmäßig aktualisiert und archiviert wird. Zusätzlich zur Archivierung von Transaktionen werden bei jedem neuen Ledger-Update einige neu geprägte Bitcoins erstellt ...

Eine weitere Anwendung sind Finanzmärkte für den Echtzeithandel mit Modellen wie Black-Scholes .

... Eine wichtige Voraussetzung für die Nutzung von Optionen ist die Berechnung ihres beizulegenden Zeitwerts. Die Suche nach Wegen zur effizienten Lösung dieses Preisproblems ist seit mehr als dreißig Jahren ein aktives Forschungsfeld und ein Schwerpunkt des modernen Finanzingenieurwesens. Da bei finanzbezogenen Problemen mehr Berechnungen durchgeführt wurden, ist es immer wichtiger geworden, effiziente Wege zur Implementierung dieser Algorithmen in modernen Architekturen zu finden.

In diesem Kapitel wird beschrieben, wie Optionen mit der GPU effizient bewertet werden können. Wir führen unsere Bewertungen mit zwei verschiedenen Preismodellen durch: dem Black-Scholes-Modell und den Gittermodellen. Beide Ansätze lassen sich gut auf die GPU übertragen, und beide sind auf der GPU wesentlich schneller als auf modernen CPUs. Obwohl beide auch einfache Zuordnungen zur GPU haben, erfordert die Implementierung von Gittermodellen aufgrund von Abhängigkeiten in den Berechnungen zusätzliche Arbeit ...

Conways Spiel des Lebens ist ein gutes akademisches Beispiel.

... Das Universum des Spiels des Lebens ist ein unendliches zweidimensionales orthogonales Gitter quadratischer Zellen, von denen sich jede in einem von zwei möglichen Zuständen befindet, lebendig oder tot. Jede Zelle interagiert mit ihren acht Nachbarn, dh den Zellen, die horizontal, vertikal oder diagonal benachbart sind. Zu jedem Zeitpunkt treten folgende Übergänge auf:

1. Jede lebende Zelle mit weniger als zwei lebenden Nachbarn stirbt, als ob sie durch eine Unterbevölkerung verursacht würde.
2. Jede lebende Zelle mit zwei oder drei lebenden Nachbarn lebt für die nächste Generation weiter.
3. Jede lebende Zelle mit mehr als drei lebenden Nachbarn stirbt wie durch Überfüllung.
4. Jede tote Zelle mit genau drei lebenden Nachbarn wird wie durch Reproduktion zu einer lebenden Zelle.

Das anfängliche Muster bildet den Keim des Systems. Die erste Generation wird erstellt, indem die obigen Regeln gleichzeitig auf jede Zelle im Samen angewendet werden - Geburten und Todesfälle treten gleichzeitig auf, und der diskrete Moment, in dem dies geschieht, wird manchmal als Zecke bezeichnet (mit anderen Worten, jede Generation ist eine reine Funktion der vorhergehende). Die Regeln werden weiterhin wiederholt angewendet, um weitere Generationen zu schaffen ...

Probleme, die viel Mathematik erfordern und gleichzeitig erledigt werden können. Wo ich früher gearbeitet habe, wollten wir mit GPUs spielen, um 2 Matrizen zu addieren / subtrahieren / multiplizieren, um die genetische Korrelation zu ermitteln. Das erste Mal, dass ich von GPUs hörte, war, dass sie von einem Finanzsoftwarehaus verwendet wurden, um einen Teil ihrer Modellierung durchzuführen (Monte Carlo und so weiter). Das wäre nützlich beim Code-Brechen.

GPUs helfen wahrscheinlich nicht viel bei Ihren regelmäßigeren Programmierproblemen, bei denen ein paar CPU-Kerne ausreichen, da die meisten regulären Programme nur wenige gleichzeitige Prozesse ausführen müssen. (Kann mit Speicher / Festplatte anders sein, die sehr viel schneller ist als wir derzeit haben)

Vielleicht bin ich sehr rechnerspezifisch in Mathematik / Naturwissenschaften / Ingenieurwesen, aber einer, der mir in den Sinn kommt, ist der FFT-Algorithmus.

Ich habe diesen FFT-Benchmark schon einmal gesehen, und obwohl er ein paar Jahre alt ist, denke ich, dass er für das, was er ist, gut gemacht wurde: http://www.sharcnet.ca/~merz/CUDA_benchFFT