Para quais métodos estatísticos as GPUs são mais rápidas que as CPUs?

Acabei de instalar uma placa de vídeo Nvidia GT660 na minha área de trabalho e, depois de algum esforço, consigo fazer a interface com R.

Eu tenho jogado com vários pacotes R que usam GPUs, especialmente gputools, e estava comparando o tempo gasto pela minha GPU e CPU para executar algumas operações básicas:

• invertendo matrizes (CPU mais rápido)
• decomposição qr (CPU mais rápido)
• grandes matrizes de correlação (CPU mais rápido)
• multiplicação de matrizes (GPU muito mais rápido!)

Observe que eu experimentei principalmente o gputools, então talvez outros pacotes tenham melhor desempenho.

Em termos gerais, minha pergunta é: quais operações estatísticas de rotina podem valer a pena ser executadas em uma GPU em vez de em uma CPU?

GPUs são bestas sensíveis. Embora a placa mais robusta da Nvidia possa teoricamente executar qualquer uma das operações listadas 100x mais rápido que a CPU mais rápida, cerca de um milhão de coisas podem atrapalhar essa aceleração. Todas as partes do algoritmo relevante e do programa que o executa precisam ser extensivamente aprimoradas e otimizadas, a fim de chegar a um ponto próximo à velocidade máxima teórica. Geralmente, o R não é conhecido por ser uma linguagem particularmente rápida e, portanto, não me surpreende que a implementação padrão da GPU não seja tão boa, pelo menos em termos de desempenho bruto. No entanto, as funções da GPU R podem ter configurações de otimização que você pode ajustar para recuperar parte desse desempenho ausente.

Se você está procurando GPUs porque descobriu que algum cálculo que você precisa executar levará semanas / meses para terminar, pode valer a pena migrar do R para um idioma mais favorável ao desempenho. O Python não é muito mais difícil de trabalhar do que o R. Os pacotes NumPy e SciPy têm a maioria das funções stat que o R, e o PyCuda pode ser usado para implementar suas próprias funções baseadas em GPU de maneira bastante direta.

Se você realmente deseja aumentar a velocidade com que suas funções são executadas em GPUs, eu consideraria implementar suas próprias funções em uma combinação de C ++ e CUDA. A biblioteca CUBLAS pode ser usada para lidar com todo o trabalho pesado relacionado à álgebra linear. No entanto, lembre-se de que pode demorar um pouco para escrever esse código (especialmente se for a primeira vez que você faz isso) e, portanto, essa abordagem deve ser reservada apenas para os cálculos que demoram muito tempo para serem executados (meses) e / ou você repetirá centenas de vezes.

Em termos gerais, os algoritmos executados mais rapidamente na GPU são aqueles em que você está executando o mesmo tipo de instrução em muitos pontos de dados diferentes.

Um exemplo fácil para ilustrar isso é com a multiplicação de matrizes.

Suponha que estejamos fazendo o cálculo matricial

$A \times B = C$

Um algoritmo simples da CPU pode parecer algo como

// começando com 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];
            }
        }
    }
}

O principal a ver aqui é que há muitos aninhados para loops e cada etapa deve ser executada uma após a outra.

Veja um diagrama deste

Observe que o cálculo de cada elemento de C não depende de nenhum dos outros elementos. Portanto, não importa em que ordem os cálculos são feitos.

Portanto, na GPU, essas operações podem ser realizadas simultaneamente.

Um núcleo de GPU para calcular uma multiplicação de matrizes seria algo como

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

Este kernel possui apenas os dois loops internos. Um programa que envia esse trabalho para a GPU instruirá a GPU a executar esse kernel para cada ponto de dados em C. A GPU executará cada uma dessas instruções simultaneamente em vários threads. Assim como o antigo ditado "GPU mais barato", as GPUs são projetadas para serem mais rápidas, fazendo a mesma coisa várias vezes.

No entanto, existem alguns algoritmos que desacelerarão a GPU. Alguns não são adequados para a GPU.

Se, por exemplo, houvesse dependências de dados, ou seja: imagine que o cálculo de cada elemento de C dependesse dos elementos anteriores. O programador teria que colocar uma barreira no kernel para aguardar a conclusão de cada cálculo anterior. Isso seria uma grande desaceleração.

Além disso, algoritmos que possuem muita lógica de ramificação, ou seja:

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

tendem a rodar mais devagar na GPU porque a GPU não está mais fazendo a mesma coisa em cada thread.

Esta é uma explicação simplificada, porque há muitos outros fatores a serem considerados. Por exemplo, o envio de dados entre a CPU e a GPU também consome tempo. Às vezes, vale a pena fazer um cálculo na GPU mesmo quando mais rápido na CPU, apenas para evitar o tempo extra de envio (e vice-versa).

Agora, muitas CPUs modernas também suportam simultaneidade com processadores multicore com hyperthread.

As GPUs também parecem não ser tão boas para recursão; veja aqui o que provavelmente explica alguns dos problemas com o algoritmo QR. Acredito que se tenha algumas dependências recursivas de dados.

$n = 2^{10}$$n,m \approx 2^{10}, k \approx 2^{14}$ . É uma surpresa especialmente grande para mim que grandes matrizes de correlação seriam mais rápidas na CPU usando R.

Mais amplamente, suspeito que a maioria das operações estatísticas que passam a maior parte do tempo em álgebra linear densa (funcionalidade BLAS, Lapack) pode ser implementada com eficiência na GPU.

Vários métodos de imputação para dados ausentes? Como aqueles em Alice-II (R).

Eu acho que esses tendem a ser muitas vezes embaraçosamente paralelos e, portanto, adequados a uma arquitetura de GPU. Mas nunca tentei.