Vitor Pamplona

Innovation on Vision: Imaging , Enhancement and Simulation

Análise de Performance: C vs Cuda

Este post apresenta uma comparação de poder computacional entre CPU e GPU utilizando soluções do N-Rainhas. Foram implementadas 3 soluções em C + + e 3 soluções em Cuda. Os testes foram feitos em um Intel Quad-core de 2.4 Ghz e uma nVidia GeForce 9600GT com 64 processadores. O tempo de execução em função do tamanho do tabuleiro destas seis soluções foi comparado e analisado em diferentes contextos. Exceto por alguns casos pontuais, a CPU permaneceu superior a GPU.

1. Introdução

As unidades de processamento gráfico (Graphics Processing Units - GPUs) atuais estão organizadas de forma a facilitar a implementação e maximizar o processamento de algoritmos paralelos que interagem sobre grandes volumes de dados. As placas gráficas foram criadas, adaptadas e otimizadas para processamento de primitivas gráficas (pontos, triângulos e pixels) mas, recentemente, receberam melhorias e novas linguagens para facilitar a implementação de técnicas de propósito geral (GPGPU). Uma das linguagens criadas foi a CUDA (Compute Unified Device Architecture). Uma linguagem baseada em C + + com anotações e palavras-chave específicas para soluções paralelas. O compilador da linguagem gera código para CPU e para GPU, de acordo com as anotações do desenvolvedor.    

Figura 1: N-Rainhas: 3 possíveis soluções para o problema.
Para um tabuleiro 8x8 existem 92 soluções em 16.777 milhões de possibilidades. Fonte da Imagem: Wikipedia.

O problema N-Rainhas é definido como: Dado um tabuleiro de xadrez NxN, encontre todas as configurações possíveis onde N rainhas são posicionadas de maneira que não se ataquem (Figura 1). No xadrez, a rainha se move na vertical, horizontal e nas diagonais, quantas casas quiser. Todas as soluções implementadas neste trabalho são de força bruta, sem heurísticas, onde todas as configurações do tabuleiro são testadas.

Este post compara tempos de execução de soluções para GPU e CPU do problema N-Rainhas com o objetivo de avaliar a performance e a facilidade de uso da plataforma CUDA. 3 soluções foram implementadas em CPU usando C + + e outras 3 em GPU usando CUDA. Os testes foram feitos em um Intel Quad-core 2.4Ghz e com uma nVidia GeForce 9600 GT. Entre as versões mais otimizadas para CPU e GPU, a CPU mantém uma vantagem de 25%. Na seção de conclusões são apresentados os problemas que ocorreram durante o desenvolvimento do trabalho e as considerações do autor.

Cuda

Cuda é uma linguagem para programação paralela de propósito geral desenvolvido pela nVidia para placas gráficas da nVidia (Séries 8 ou superior, Tesla e Quadro). Fortemente baseada em C, a linguagem não requer conhecimento do hardware gráfico, do pipeline da OpenGL ou sequer do uso de texturas, a forma convencional de trafegar informação entre CPU e GPU. Está disponível gratuitamente, é multi-plataforma (Windows / Linux / Mac), já possui versão estável, é bem documentada em termos de linguagem e funções e é suportada comercialmente pela nVidia.

Cuda pode ser considerada uma API de baixo nível, pois expõe os tipos diferentes de memória da placa gráfica e exige que o desenvolvedor configure seus acessos a memória global, a cache e a quantidade e disposição das threads para atingir a melhor performance. Nada é automático. A placa gráfica é vista como um simples dispositivo operando como um co-processador, e aguardando instruções da aplicação cliente. O desenvolvedor é o responsável pelo escalonamento de atividades entre a CPU (Host) e a GPU.

O código que rodará na placa de vídeo é chamado de kernel, um único código que será executado sobre um grande conjunto de informações. As funções de um programa convencional, que são chamadas muitas vezes com entradas e saídas independentes, são as primeiras a se transformarem em kernels. Por exemplo, uma operação que soma 1 em cada valor de um vetor com 1 GB de dados, pode facilmente ser transformada em um kernel, onde várias threads irão somar 1 e armazenar o valor na mesma posição. Nesse caso, não é necessário sincronia, nem comunicação entre as threads. Perfeito para a GPU.

A distribuição das threads em Cuda é feita através da definição de blocos no grid da placa gráfica (Figura 2). Grid é a configuração da placa para a execução de um kernel. Não é possível executar grids em paralelo. Um bloco é um conjunto de threads que serão executadas sincronamente e terão memória compartilhada entre elas. A comunicação entre blocos é feita através da memória global, que é mais lenta que a memória compartilhada entre as threads de um bloco. Blocos e threads possuem identificadores tridimensionais. É através deles que o desenvolvedor saberá em que thread está e que parte da memória esta thread deve processar.

 Figura 2: Especificação de grids e blocos no Cuda. O usuário deve configurar o hardware gráfico, informando a quantidade e a disposições de blocos em um grid de processamento. Os blocos são homogêneos e o usuário deve indicar o número e a disposição das threads dentro do bloco. O processamento dentro de cada bloco é síncrono e cada bloco possui um espaço de memória compartilhada para suas threads.

Na Figura 2, o Grid 1 foi criado com 2 linhas e 3 colunas (3,2,1) e cada bloco contém 15 threads (5,3,1). Em tempo de execução, os identificadores - mostrados entre os parênteses - definirão a posição na memória global para a busca das informações do processamento. Por exemplo: O nosso vetor de 1 GB de dados é dividido em 6 partes, uma para cada bloco. Por um cálculo simples (blockId.x * 2 + blockId.y), os blocos sabem qual parte do vetor lhes pertence. Em seguida, divide-se esta parte da memória entre todas as threads do mesmo bloco. Da mesma forma que foi com o bloco, as threads utilizarão um cálculo sobre seus índices para identificarem qual parte da memória do bloco devem processar. Como os endereços no vetor de entrada são os mesmos dos de saída, a paralelização está completa. Neste caso não é necessário sincronização entre as threads, mas caso necessário, a sincronização é feita através de funções atomicas testAndSet.

Cuda possui 6 tipos diferentes de memória como mostrado na Figura 3. Cada thread possui sua memória local (pequenos quadrados em amarelo), que são as variáveis declaradas dentro do kernel e os registradores, que tem a mesma função dos registradores de CPU e não são definidos pelo programador. Cada multiprocessador, um conjunto síncrono de processadores, possui uma memória compartilhada entre suas threads. A mesma informação está disponível para todas as threads daquele bloco. Há ainda a memória global, a memória de constantes, e a memória de texturas. As duas últimas são somente leitura e a memória de texturas e de constantes possui um cache automático. O programa hospedeiro (Host) se comunica com as threads através das memórias constante, textura e global. Para atingir a máxima performance, o desenvolvedor deve conhecer esta arquitetura, que sofre variações placa para placa, e projetar a sua solução orientado a ela.

 Figura 3: Memórias da Placa de Vídeo usando Cuda. Cada thread (quadrado pequeno verde escuro) possui uma memória local (quadrado amarelo L). Cada multiprocessador (retângulo verde claro abaixo das threads) possui uma memória compartilhada que as threads daquele multiprocessador tem acesso. As threads tem acesso de leitura as memórias constante e de textura com recurso de cache, e acesso de leitura e escrita na memória global que não possui cache e por isso o acesso é muito mais lento.

Enquanto a memória local, a compartilhada e a memória de constantes tem acesso rápido (cerca de 4 flops), a memória global e a memória de textura são muito lentas (cerca de 700 flops). Por esse motivo é comum, no início do processamento, levar os trechos mais acessados da memória global para a memória compartilhada e só então executar o algoritmo. O desenvolvedor deve planejar minuciosamente a sua solução, agrupando em blocos as threads que atuam em posições de memória próximas. Cuda não possui stack e a recursão é limitada.

3. Soluções do N-Rainhas Implementadas

As soluções implementadas para o problema das N-Rainhas são todas categorizadas como força bruta. Em todas elas o tabuleiro é modelado como um array de N bytes representando as N colunas do tabuleiro. O valor de cada byte representa a linha em que a rainha se encontra. Como só é válido uma rainha por linha e uma por coluna, esta representação é viável.

Para a CPU, implementamos 3 soluções em C + +:

  1. CPU-Recursive : solução de busca em profundidade usando N recursões em monothread. A função recursiva coloca uma rainha na primeira coluna vazia do tabuleiro, valida o mesmo e chama novamente a função. Caso o tabuleiro for inválido, tenta colocar a rainha numa linha superior até que todas as linhas sejam testadas. Caso encontre uma solução completa e válida, salva o tabuleiro em um vetor e retorna a função.

  2. CPU-Plain : solução de busca em profundidade sem recursão e monothread. O algoritmo é o mesmo da solução anterior, mas o código está totalmente otimizado e praticamente ilegível. Nesta versão, utilizamos alguns buffers para evitar a criação e a destruição de variáveis e a recursão é simulada por um loop e um buffer para a stack.

  3. GPU-Plain-Threads : solução de busca em profundidade sem recursão com N threads. Semelhante a solução anterior, mas são criadas N threads onde cada thread possui um ID que define a posição da rainha da primeira coluna do tabuleiro. Cada thread busca o seu conjunto de soluções e as envia para um vetor em memória global dentro de uma seção crítica.

Para GPU, implementamos 3 soluções com algumas variações em código:

  1. GPU-Breadth-first static : busca em largura, coluna a coluna, com acesso estático a memória global. A entrada do kernel é um ponteiro para um array de memória em GPU com soluções válidas até a coluna X do tabuleiro. O kernel processará todas as soluções da coluna X + 1. O número de threads é igual ao número de soluções válidas computadas até o momento vezes o tamanho do tabuleiro. Desta forma, cada thread da GPU testa uma única solução: tenta colocar uma rainha no tabuleiro, se a solução for válida salva, caso contrário, descarta. Nesta implementação, as soluções são salvas em uma posição de memória definida estaticamente. Como várias soluções são inválidas, em cada passo criam-se espaços em branco no buffer de soluções devido ao ponteiro estático. Estes espaços são removidos com um algoritmo de ordenação de memória desenvolvido para GPU e executado após a computação de cada passo.

  2. GPU-Breadth-first dynamic : busca em largura, coluna a coluna, com acesso dinâmico a memória global. Solução semelhante a anterior mais, como a posição de memória para salvar uma solução válida é computada dinamicamente, não há mais espaços em branco na memória entre os passos, evitando assim a chamada do algoritmo de ordenação. Em contra partida, esta solução possui uma seção crítica para buscar e incrementar o índice do próximo espaço de disponível no buffer de soluções.

  3. GPU-Depth-first : busca em profundidade com acesso dinâmico a memória global. Solução semelhante a versão 2 da CPU, mas rodando em várias configurações de blocos e grids. Assim como a solução anterior, as threads possuem uma seção crítica para buscar e incrementar o próximo espaço disponível no buffer de soluções na memória global.

As buscas em largura foram implementadas com o objetivo de minimizar o tempo de processamento por thread, que é longo na terceira solução para GPU e maximizar o paralelismo - a GPU, ao contrário da CPU, gosta de threads. Além disso, o driver da placa de vídeo pode parar a execução de kernels muito longos. Não sabíamos de início se a GPU iria suportar uma execução do terceiro item em um tabuleiro muito grande. É interessante notar que, enquanto um kernel está processando, a placa não envia informação ao monitor, ou seja, o micro fica travado.

A terceira solução para GPU, GPU-depth-first, ao contrário das três soluções para CPU e das duas primeiras para GPU, foi testada com diferentes configurações de grid: (i) com 1 bloco e uma thread; (ii) com 1 bloco e N threads; (iii) com N blocos e 1 thread por bloco; (iv) N * N blocos com 1 thread; (v) com N * N blocos e cada bloco com N threads; (vi) com N * N blocos e cada bloco com N * N threads; (vii) com N ^ N blocos. A Tabela 1 compara o número de threads gerado para experimento.

O uso de acesso estático a memória global é interessante pois permite ao compilador otimizar o código e criar cache de dados para threads que irão executar sobre regiões próximas da memória global. No entanto, no problema em questão, o acesso estático se mostrou desvantajoso pela ordenação necessária após cada passo. A tabela 1 mostra o volume de threads para cada uma das soluções. A terceira solução para GPU foi implementada com diversas configurações de grids e blocos.

Tabela 1: Comparação do volume de threads entre as soluções desenvolvidas.
Sol é o número de configurações válidas geradas até o momento.

4. Resultados

Os testes foram realizados em um Intel Quad-core 2.4Ghz com 4GB de memória RAM com Ubuntu linux e uma nVidia GeForce 9600 GT. A 9600 GT possui 64 processadores em 650Mhz e 500MB de memória RAM. O objetivo é comparar o poder computacional de uma CPU com 4 núcleos com uma GPU com 64 processadores e analisar a performance da placa e do cuda. Os programas em CPU foram compilados com g + + - O3 e os programas em Cuda com nvcc - O3.

Todos os gráficos mostrados a seguir medem o tempo de processamento (milissegundos) em função do tamanho do tabuleiro N. Em cada gráfico, apenas os dados significativos são mostrados de acordo com o objetivo da comparação.

Comparando apenas as soluções em CPU, pode-se identificar a diferença entre as três soluções:

Comparando as duas soluções de busca em largura na GPU: (i) a versão de acesso a memória estática com o algoritmo de ordenação em cada passada contra (ii) a versão de acesso a memória dinâmica com a região crítica. Podemos concluir que é vantagem utilizarmos a seção crítica, mas que ela ainda não é melhor que a versão monothread em CPU.

Comparando três versões de busca em profundidade com o mesmo número de threads, duas em GPU e uma em CPU, concluímos que a performance da CPU é superior, mesmo com a CPU processando e escalonando entre todos os outros aplicativos abertos durante a simulação. A GPU não possui outros processos para escalonar.
Comparando as soluções de busca em profundidade com apenas uma thread, podemos ver a diferença do poder computacional entre as arquiteturas. Mesmo a versão mais lenta da CPU ganha da GPU se apenas um processador é utilizado.
Comparando a solução de busca em largura na GPU com acesso dinâmico a memória, com as buscas em profundidade que usam N threads, tanto em CPU quanto em GPU, podemos ver que a busca em largura tem uma performance superior, provavelmente pelo número de threads ser maior.
Comparando apenas as buscas em profundidade tanto em CPU quanto em GPU, mas variando a quantidade de threads configuradas para a GPU, podemos ver o ganho do aumento do paralelismo em GPU. É possível também notar um aumento de performance usando N-grids (N-blocos) com uma thread cada bloco ao invés de um único bloco com N-threads.
Como a performance aumentou proporcional ao número de threads, e note que o número de threads é superior ao número de processadores, criamos também uma solução com o número de threads igual ao de combinações de resultados, válidos e inválidos. Ou seja, N N threads. Veja a comparação desta solução com a CPU.
Comparando a melhor busca em largura em GPU, a melhor busca em profundidade em GPU e as soluções em CPU, temos pela primeira vez, uma performance da GPU próxima a CPU.
E, por fim, comparando a melhor solução para a GPU com as soluções em CPU temos um bom ganho, mas a CPU continua sendo mais rápida.

A Tabela 2 mostra os dados brutos em milissegundos para tabuleiros de até 9 colunas. Sol é o número de soluções e N o número de colunas no tabuleiro. Nas duas primeiras soluções, o valor da coluna Threads é dado por passo do algoritmo. Pode-se notar que o Cuda possui um tempo alto para inicializar, que é independente do número de chamadas a GPU. Nota-se também que a solução busca em profundidade N ^ N threads mostrou-se a mais lenta até em tabuleiros pequenos.

Tabela 2: Dados brutos da comparação com tabuleiros com número de colunas menor que 9.

A tabela 3 mostra os dados brutos de cada técnica para tabuleiros com tamanho maior que 9. A palavra Mem significa que a técnica estourou a memória da GPU. A palavra Cont significa que o índice de 32 bits que armazena o local para salvar a próxima solução válida estourou. As células em branco significam que não houve execução. Os valores são dados em milisegundos. Nota-se que a melhor solução para GPU, N * N blocos de N * N threads, acompanha a técnica em CPU com N-threads, e chega a vencer em alguns casos.


Tabela 3: Dados brutos da comparação com tabuleiros com número de colunas maior que 9.

5. Conclusões

Apresentamos neste trabalho, um comparativo da performance de soluções do N-Rainhas implementadas em C + + e em Cuda: 3 soluções em C + + e 3 soluções, com diferentes configurações de execução, em Cuda. Os testes foram realizados em um Intel Quad-core 2.4Ghz com 4GB de memória RAM rodando Ubuntu linux com uma nVidia GeForce 9600 GT que possui com 64 processadores a 650Mhz cada.

Os gráficos mostram que, apesar do maior número de processadores e da exclusividade no processamento das soluções na placa gráfica, a CPU continua com uma performance superior. Os gráficos também mostram que a performance da GPU é fortemente dependente da configuração de execução: blocos e threads. A performance também é muito sensível a implementação. Em um caso, por exemplo, o tempo de execução de um algoritmo que acessa N vezes a mesma posição da memória global é menor do que um que faz processa em memória local e envia uma única vez para a memória global. Os operadores de multiplicação, divisão e módulo para variáveis de ponto flutuante são muito lentos.

Informalmente, notamos que a linguagem Cuda não utiliza algumas otimizações que a placa gráfica proporciona, como cache de memória, por exemplo. Testes realizados com o # pragma unroll para que o compilador expanda um loop também não surtiram efeito prático, mesmo quando o número de interações do for era definido estaticamente. Algumas vezes o programa era morto pelo driver sem nenhuma mensagem e não há maneira de parar a execução de um kernel em loop infinito, apenas reiniciando o micro. Configurações incorretas de blocos e threads não geram mensagem de erro. A função que rodaria na GPU simplesmente não executa, mas o programa continua normalmente sem nenhuma mensagem de erro. Por várias vezes, após a execução de um teste, o monitor apresentava pixels incorretos em outros programas que sequer utilizavam a aceleração gráfica, como se a placa gráfica incluísse um erro Salt and Pepper sem coerência temporal. A documentação sobre as otimizações feitas pelo compilador do cuda é pouca e imprecisa.

Atualmente, podemos considerar Cuda uma boa solução quando se utiliza o poder computacional da CPU em paralelo com o da GPU. A linguagem ainda vai evoluir e esperamos que as otimizações do compilador também. Cuda, por exemplo, ainda não suporta a tecnologia SLI – duas placas de vídeo ligadas no mesmo computador.

6. Trabalhos futuros

Aparentemente - não fizemos testes para comprovar - a performance de um shader GLSL no pipeline gráfico é superior a performance de um kernel do Cuda. Vários alunos da computação gráfica tem essa intuição. Seria interessante criar soluções do N-Rainhas em OpenGL + GLSL e comparar com as versões em Cuda para comprovar essa hipótese.

 


 

Posted in Jan 10, 2009 by Vitor Pamplona - Edit - History

Showing Comments

Que programas você usa para tirar esses resultados (gráficos e tabelas da seção 4)?

Estive procurando algo semelhante comparando C + + e Java para computação científica. Achei o artigo " A comparasion of Java, C / C + +, and Fortran for Numerical Computing " (autor John L. Volakis) publicado numa revista do IEEE. No entanto, é muito antigo, se não me engano de 1998. Obviamente muita coisa mudou de lá pra cá e por isso queria refazer os testes, porém usando as versões atuais da linguagem, claro.

Vi num post antigo seu uma comparação C + + / Java, no entanto visando mais a criação / destruição de objetos. Para o tipo de coisa que eu uso isso é o que menos importa, sendo o principal a manipulação de matrizes. Daí a necessidade de tentar repetir os testes.

Até,
Demônio de Maxwell
http://demoniodemaxwell.wordpress.com /

- - Demônio de Maxwell

- - Posted in Jan 12, 2009 by 189.27.24.243

Oi, erhm... carinha do Demônio de Maxwell:) hehe

Os gráficos são do OpenOffice mesmo e os números são comparações das versões que eu tinha do n-rainhas.

Sempre que se compara tecnologias, deve-se definir bem o objetivo da comparação. Por exemplo, eu testei neste post a solução completa. Você poderia fazer testes menores separados para acesso a memória, alocação, loops, otimização de assembly, etc. Você conseguiria, neste caso, saber qual linguagem é melhor em que feature.

Minha sugestão é que você reimplemente métodos numéricos nestas linguagens dando ênfase a performance e depois compare os tempos. As bibliotecas disponíveis, mesmo aquelas que se vendem com performance, podem não estar otimizadas ao máximo devido a " generalidade " da implementação.

Mãos a massa!: D

- - Vitor Pamplona

- - Posted in Jan 12, 2009 by 143.54.13.191

Ola,

Parabens pelo trabalho, gostei muito mesmo.
Pelo visto quem fala em utilizacao do
CUDA como a ultima moda em computacao de alta performance deve tomar cuidado. A boa e velha CPU esta longe de ser batida!



- - Williams

- - Posted in Feb 25, 2009 by 189.82.73.116

nossa, que teste mais mal feito. Seu programa em cuda deve te ficado muito pouco otimizado para que a cpu seja mais rapido fazendo permutações, com certeza vc fez algo errado. Todos os testes que ja rodei com cuda se mostraram muitas vezes mais eficientes do que os programas normais em C, talvez vc nao tenha usado o paralelismo corretamente. Alias, ate um brute force feito no cuda mostra a diferença para a criaçao de permutaçoes, o cuda consegue ate ser mais rapido que um ps3 as vezes, vc deveria postar os codigos que usou para quem ver confirmar.

- - eu

- - Posted in Mar 10, 2009 by 164.41.49.25

Oi eu.

De acordo com a experiência aqui do grupo, Cuda é muito lento, mesmo na 9800 GX2. Comparado com GLSL, Cuda perde feio.

Nos meus testes, os programas em C + + estavam * ultra * otimizados. A versão mais rápida deles estava praticamente ilegível. Por isso que o C + + sempre ganhou. Não tem graça fazer uma comparação entre uma versão normal em C e outra otimizada em Cuda.

PS: Como você pode dizer que o meu teste foi mal feito se você nem viu as implementações?

[] s

- - Vitor Pamplona

- - Posted in Mar 10, 2009 by 143.54.13.191

Ola vitor,

ótimo post....
e ótimas comparações...
comvenhamos que vc está usando um bruto de um cpu né....
estou iniciando um meu tcc, e o tema é: computação de propósito geral em placas gráficas, este post abriu muito minha mente em relação as tecnologias existêntes
nesse ambito.
Gostaria de algumas dicas sobre o que pesquisar...

Abraços e parabéns pelo trabalho.

- - Filipe Portes - filipegyn2@hotmail.com

- - Posted in Mar 31, 2009 by 189.74.25.188

Add New Comment

Your Name:


Write the code showed above on the text below.