Pour quelles méthodes statistiques les GPU sont-ils plus rapides que les CPU?

Je viens d'installer une carte graphique Nvidia GT660 sur mon bureau et, après quelques difficultés, j'ai réussi à l'interfacer avec R.

J'ai joué avec plusieurs packages R qui utilisent des GPU, en particulier gputools, et je comparais le temps pris par mon GPU et mon processeur pour effectuer certaines opérations de base:

• inverser les matrices (CPU plus rapide)
• décomposition qr (CPU plus rapide)
• grandes matrices de corrélation (CPU plus rapide)
• multiplication matricielle (GPU beaucoup plus rapide!)

Notez que j'ai principalement expérimenté avec gputools, alors peut-être que d'autres packages fonctionnent mieux.

En termes généraux, ma question est la suivante: quelles opérations statistiques de routine pourraient valoir la peine d'être exécutées sur un GPU plutôt que sur un processeur?

Les GPU sont des bêtes sensibles. Bien que la carte la plus puissante de Nvidia puisse théoriquement exécuter l'une des opérations que vous avez répertoriées 100 fois plus rapidement que le processeur le plus rapide, environ un million de choses peuvent entraver cette accélération. Chaque partie de l'algorithme pertinent et du programme qui l'exécute doit être largement ajustée et optimisée afin de se rapprocher de cette accélération maximale théorique. R n'est généralement pas connu pour être un langage particulièrement rapide, et cela ne m'étonne donc pas que son implémentation par défaut du GPU ne soit pas géniale, du moins en termes de performances brutes. Cependant, les fonctions R GPU peuvent avoir des paramètres d'optimisation que vous pouvez modifier afin de retrouver une partie de ces performances manquantes.

Si vous cherchez des GPU parce que vous avez constaté que certains calculs que vous devez exécuter vont prendre des semaines / mois pour terminer, cela peut valoir la peine de migrer de R vers un langage plus convivial. Python n'est pas beaucoup plus difficile à travailler que R. Les packages NumPy et SciPy ont la plupart des mêmes fonctions statistiques que R, et PyCuda peut être utilisé pour implémenter vos propres fonctions basées sur le GPU d'une manière assez simple.

Si vous voulez vraiment augmenter la vitesse à laquelle vos fonctions s'exécutent sur des GPU, j'envisagerais d'implémenter vos propres fonctions dans une combinaison de C ++ et CUDA. La bibliothèque CUBLAS peut être utilisée pour gérer tous les travaux lourds liés à l'algèbre linéaire. Cependant, gardez à l'esprit que l'écriture d'un tel code peut prendre un certain temps (surtout si c'est la première fois que vous le faites), et donc cette approche ne devrait être réservée qu'aux calculs qui prennent un temps extrêmement long à s'exécuter (mois) et / ou que vous allez répéter des centaines de fois.

En termes généraux, les algorithmes qui s'exécutent plus rapidement sur le GPU sont ceux où vous effectuez le même type d'instruction sur de nombreux points de données différents.

Un exemple simple pour illustrer cela est la multiplication matricielle.

Supposons que nous faisons le calcul matriciel

$A \times B = C$

Un algorithme CPU simple pourrait ressembler à quelque chose

// commençant par 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];
            }
        }
    }
}

L'essentiel à voir ici est qu'il y a beaucoup de boucles imbriquées pour et chaque étape doit être exécutée l'une après l'autre.

Voir un schéma de ceci

Notez que le calcul de chaque élément de C ne dépend d'aucun des autres éléments. Peu importe donc l'ordre dans lequel les calculs sont effectués.

Ainsi, sur le GPU, ces opérations peuvent être effectuées simultanément.

Un noyau GPU pour calculer une multiplication matricielle ressemblerait à quelque chose

__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];
         }
     }
}

Ce noyau n'a que les deux boucles for internes. Un programme envoyant ce travail au GPU indiquera au GPU d'exécuter ce noyau pour chaque point de données en C. Le GPU exécutera chacune de ces instructions simultanément sur de nombreux threads. Tout comme le vieil adage "GPU moins cher par la douzaine", les GPU sont conçus pour être plus rapides à faire la même chose de nombreuses fois.

Il existe cependant certains algorithmes qui ralentiront le GPU. Certains ne sont pas bien adaptés au GPU.

Si par exemple, il y avait des dépendances de données, c'est-à-dire: imaginez que le calcul de chaque élément de C dépendait des éléments précédents. Le programmeur devrait mettre une barrière dans le noyau pour attendre la fin de chaque calcul précédent. Ce serait un ralentissement majeur.

En outre, les algorithmes qui ont beaucoup de logique de branchement, à savoir:

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

ont tendance à fonctionner plus lentement sur le GPU car le GPU ne fait plus la même chose dans chaque thread.

Il s'agit d'une explication simplifiée car il existe de nombreux autres facteurs à considérer. Par exemple, l'envoi de données entre le CPU et le GPU prend également beaucoup de temps. Parfois, cela vaut la peine de faire un calcul sur le GPU, même quand c'est plus rapide sur le CPU, juste pour éviter le temps d'envoi supplémentaire (Et vice versa).

De nombreux processeurs modernes prennent également en charge la concurrence simultanée avec les processeurs multicœurs hyperthreadés.

Les GPU semblent également ne pas être aussi bons pour la récursivité, voir ici qui explique probablement certains des problèmes avec l'algorithme QR. Je crois que l'on a des dépendances de données récursives.

$n = 2^{10}$$n,m \approx 2^{10}, k \approx 2^{14}$

Plus largement, je soupçonne que la plupart des opérations statistiques qui passent la plupart de leur temps en algèbre linéaire dense (BLAS, fonctionnalité Lapack) peuvent être efficacement implémentées sur le GPU.

Plusieurs méthodes d'imputation pour les données manquantes? Comme ceux d'Alice-II (R).

Je pense que ceux-ci ont tendance à être souvent embarrassants en parallèle et donc adaptés à une architecture GPU. Je ne l'ai jamais essayé moi-même.