Für welche statistischen Methoden sind GPUs schneller als CPUs?

17

Ich habe gerade eine Nvidia GT660-Grafikkarte auf meinem Desktop installiert und kann sie nach einiger Anstrengung mit R verbinden.

Ich habe mit mehreren R-Paketen gespielt, die GPUs verwenden, insbesondere Gputools, und ich habe die Zeit verglichen, die GPU und CPU für einige grundlegende Vorgänge benötigt haben:

  • Matrizen invertieren (CPU schneller)
  • qr Zerlegung (CPU schneller)
  • große Korrelationsmatrizen (CPU schneller)
  • Matrixmultiplikation (GPU viel schneller!)

Beachten Sie, dass ich hauptsächlich mit gputools experimentiert habe, damit andere Pakete möglicherweise eine bessere Leistung erzielen.

In groben Zügen lautet meine Frage: Welche statistischen Routineoperationen sollten auf einer GPU und nicht auf einer CPU ausgeführt werden?

Jugurtha
quelle
1
Alles, was mit viel Matrixmultiplikation zu tun hat? :) GPUs sind in der Community der neuronalen Netze sehr beliebt.
Sie müssen die Größe der beteiligten Matrizen angeben. Das letzte Mal habe ich zum Beispiel (zugegebenermaßen vor 2 Jahren) überprüft, dass Inversion und Dekomposition auf der GPU ab großen Matrizen (2 ^ 9 mal 2 ^ 9 und höher) nur schneller waren
user189035
1
Ich habe Matrizen von ungefähr für Inversion, qr und Matrixmultiplikation verwendet, während ich für Korrelationen ungefähr 10 ^ 4 Beobachtungen von Vektoren der Größe 100 verwendet habe langsamer aber vergleichbar mit der CPU. 103×103
Jugurtha
2
Dies ist eine sehr gute Frage, aber ich denke, Sie werden bessere Antworten erhalten, wenn Sie sie auf stackoverflow migrieren lassen (ich denke, dass ähnliche Fragen dort schon einmal gestellt wurden)
user189035
2
Der Vorteil von GPUs gegenüber normalen CPUs ist die Tatsache, dass sie "massiv" parallel sein können und nicht, dass sie pro Kern schneller sind. Aus diesem Grund müssen Sie für Jobs, die viel "Housekeeping" erfordern, wie Cholesky-Faktorisierung usw., Blockalgorithmen usw. verwenden, um eine erhebliche Beschleunigung zu erzielen. Dies ist nicht trivial und ich gehe davon aus, dass es eine Weile dauern wird, bis die GPUs solche Vorgänge übernehmen. Was auf jeden Fall in Richtung GPU geht, ist MCMC (und die Erzeugung von Zufallszahlen). Das Abtasten von einem Posterior hat eine "Parallelisierung", die überall darauf geschrieben ist ... und spärliche Matrizenberechnungen; sie sind sowieso schon "gesperrt" ...
usεr11852 sagt Reinstate Monic

Antworten:

6

GPUs sind empfindliche Tiere. Obwohl die beste Nvidia-Karte theoretisch alle aufgeführten Vorgänge 100-mal schneller als die schnellste CPU ausführen kann, können etwa eine Million Dinge dieser Beschleunigung im Wege stehen. Jeder Teil des relevanten Algorithmus und des Programms, in dem er ausgeführt wird, muss ausgiebig optimiert und optimiert werden, um diese theoretische Höchstgeschwindigkeit zu erreichen. Es ist allgemein nicht bekannt, dass R eine besonders schnelle Sprache ist, und daher wundert es mich nicht, dass die Standard-GPU-Implementierung nicht so gut ist, zumindest was die Leistung angeht. Die R-GPU-Funktionen verfügen jedoch möglicherweise über Optimierungseinstellungen, die Sie optimieren können, um einen Teil der fehlenden Leistung wiederherzustellen.

Wenn Sie sich mit GPUs befassen, weil Sie festgestellt haben, dass einige Berechnungen, die Sie ausführen müssen, Wochen / Monate in Anspruch nehmen werden, lohnt es sich möglicherweise, von R auf eine leistungsfreundlichere Sprache zu migrieren. Die Arbeit mit Python ist nicht allzu schwierig als mit R. Die NumPy- und SciPy-Pakete haben die gleichen stat-Funktionen wie R, und PyCuda kann verwendet werden, um Ihre eigenen GPU-basierten Funktionen auf relativ einfache Weise zu implementieren.

Wenn Sie wirklich die Geschwindigkeit erhöhen möchten, mit der Ihre Funktionen auf GPUs ausgeführt werden, würde ich in Betracht ziehen, Ihre eigenen Funktionen in einer Kombination aus C ++ und CUDA zu implementieren. Die CUBLAS-Bibliothek kann verwendet werden, um alle mit der linearen Algebra zusammenhängenden schweren Lasten zu bewältigen. Bedenken Sie jedoch, dass das Schreiben eines solchen Codes eine Weile dauern kann (insbesondere, wenn Sie ihn zum ersten Mal ausführen). Daher sollte dieser Ansatz nur für die Berechnungen reserviert werden, deren Ausführung extrem lange dauert (Monate) und / oder dass du es hunderte Male wiederholen wirst.

tel
quelle
6

Allgemein ausgedrückt sind Algorithmen, die auf der GPU schneller ausgeführt werden, solche, bei denen Sie denselben Befehlstyp für viele verschiedene Datenpunkte ausführen.

Ein einfaches Beispiel, um dies zu veranschaulichen, ist die Matrixmultiplikation.

Angenommen, wir führen die Matrixberechnung durch

A×B=C

Ein einfacher CPU-Algorithmus könnte ungefähr so ​​aussehen

// beginnend mit C = 0

for (int i = 0; i < C_Width; i++)
{
    for (int j = 0; j < C_Height; j++)
    {
        for (int k = 0; k < A_Width; k++)
        {
            for (int l = 0; l < B_Height; l++)
            {
                C[j, i] += A[j, k] * B[l, i];
            }
        }
    }
}

Das Wichtigste dabei ist, dass es viele verschachtelte for-Schleifen gibt und jeder Schritt nach dem anderen ausgeführt werden muss.

Siehe ein Diagramm dazu

Beachten Sie, dass die Berechnung jedes Elements von C von keinem der anderen Elemente abhängt. Es spielt also keine Rolle, in welcher Reihenfolge die Berechnungen durchgeführt werden.

Auf der GPU können diese Vorgänge also gleichzeitig ausgeführt werden.

Ein GPU-Kernel zum Berechnen einer Matrixmultiplikation würde ungefähr so ​​aussehen

__kernel void Multiply
(
    __global float * A,
    __global float * B,
    __global float * C
)
{
     const int x = get_global_id(0);
     const int y = get_global_id(1);
     for (int k = 0; k < A_Width; k++)
     {
         for (int l = 0; l < B_Height; l++)
         {
             C[x, y] += A[x, k] * B[l, y];
         }
     }
}

Dieser Kernel hat nur die beiden inneren for-Schleifen. Ein Programm, das diesen Job an die GPU sendet, weist die GPU an, diesen Kernel für jeden Datenpunkt in C auszuführen. Die GPU führt diese Anweisungen für viele Threads gleichzeitig aus. Genau wie das alte Sprichwort "Billiger im Dutzend", sind GPUs so konzipiert, dass sie oft schneller das Gleiche tun.

Es gibt jedoch einige Algorithmen, die die GPU verlangsamen. Einige sind für die GPU nicht gut geeignet.

Wenn zum Beispiel Datenabhängigkeiten bestünden, dh: Stellen Sie sich die Berechnung jedes Elements von C in Abhängigkeit von den vorherigen Elementen vor. Der Programmierer müsste eine Barriere in den Kernel einbauen, um zu warten, bis die vorherige Berechnung abgeschlossen ist. Dies wäre eine erhebliche Verlangsamung.

Auch Algorithmen, die viel Verzweigungslogik haben, dh:

__kernel Foo()
{
    if (somecondition)
    {
        do something
    }
    else
    {
        do something completely different
    }
}

neigen dazu, langsamer auf der GPU zu laufen, da die GPU nicht mehr in jedem Thread dasselbe tut.

Dies ist eine vereinfachte Erklärung, da viele andere Faktoren zu berücksichtigen sind. Das Senden von Daten zwischen der CPU und der GPU ist beispielsweise auch zeitaufwändig. Manchmal lohnt es sich, eine Berechnung auf der GPU durchzuführen, auch wenn diese auf der CPU schneller ist, um die zusätzliche Sendezeit zu vermeiden (und umgekehrt).

Viele moderne CPUs unterstützen jetzt auch Parallelität mit Multicore-Prozessoren mit Hyperthreading.

GPUs scheinen auch nicht so gut für Rekursionen zu sein, siehe hier, was wahrscheinlich einige der Probleme mit dem QR-Algorithmus erklärt. Ich glaube, dass man einige rekursive Datenabhängigkeiten hat.

sav
quelle
2
Es ist offiziell SX-frech, eine Antwort zu kommentieren, nur um zu sagen, dass es eine großartige Antwort ist, aber ich gebe kein Perinæum einer Ratte über Negative: Dies ist eine entzückende und informative Antwort. Eine der größten Ungerechtigkeiten von SX ist das Fehlen von Anerkennung für Leute, die exquisit informative Antworten auf "alte" (in der Internetzeit) Fragen geben. (Außerdem gebe ich einer 'alten' (in der Internetzeit) Antwort einen Daumen nach oben: Ich weiß, richtig? META).
GT.
Eine wichtige Überlegung ist, ob es tatsächlich eine Bibliothek gibt, um die Berechnung durchzuführen: Meines Wissens gibt es beispielsweise keine spärlichen x dichten GPU-Implementierungen der Matrixmultiplikation, schon gar nicht über R-Pakete. Wenn Sie bereit sind, mit dem Schreiben von GPU C-Code zu arbeiten, dann viel Glück.
Jack Wasey
4

n=210n,m210,k214

Ich vermute, dass die meisten statistischen Operationen, die die meiste Zeit in der dichten linearen Algebra verbringen (BLAS, Lapack-Funktionalität), effizient auf der GPU implementiert werden können.

Max Hutchinson
quelle
0

Mehrere Imputationsmethoden für fehlende Daten? Wie bei Alice-II (R).

Ich denke, diese sind oft peinlich parallel und daher für eine GPU-Architektur geeignet. Ich habe es aber nie selbst ausprobiert.

curious_cat
quelle