Otimizar o código é a parte mais difícil e trabalhosa durante o desenvolvimento de um programa CUDA

1 I Escola Regional de Alto Desempenho de SP ERAD-2010 MINI-CURSO: Introdução à Programação em CUDA Prof. Raphael Y. de Camargo Centro de Matemática, Computação e Cognição Universidade Federal do ABC (UFABC) [email protected]

2 Parte I Introdução às GPUs

3 Placas Gráficas Jogos 3D evoluíram muito nos últimos anos e passaram a exigir um poder computacional gigantesco

4 Jogos modernos: Além de gerar o cenário 3D, é preciso aplicar texturas, iluminação, sombras, reflexões, etc. As folhas individuais das plantas são desenhadas Sombras são calculadas dinamicamente Para tal, as placas gráficas passaram a ser cada vez mais flexíveis e poderosas GPUs

5 NVIDIA GTX480: 480 núcleos preço US$ 500 Desempenho máximo: 0.5 TFLOP (double) e 1.3 TFLOP (float) Intel Core i7 980X: 6 núcleos preço US$ 1000 Desempenho máximo: 0.1 TFLOP (double)

6 NVIDIA GTX480: 480 núcleos preço US$ GB de Memória com acesso a 177 GB/s Intel Core i7 980X: 6 núcleos preço US$ 1000 Acesso à memória a 25.6 GB/s

7 Arquitetura da GPU GPUs utilizam um maior número de transistores para colocar mais ALUs (Arithmetic Logic Unit) simplificadas Permite fazer um maior número de cálculos ao mesmo tempo Controle de fluxo mais simples: - Feita para aplicações paralelas onde as mesmas operações são aplicadas sobre um grande conjunto de dados

8 Arquitetura da GPU Fermi 16 Multiprocessadores: 32 processadores 16 unidades Load/Store 4 unidades funções especiais 64 kb Memória compartilhada registradores Cache de constantes e textura

9 Arquitetura da GPU Os multiprocessadores compartilham uma memória global, onde são armazenados texturas ou dados de aplicações Host Memory CPU

10 TESLA S x 448 processadores

11 O que é CUDA É uma arquitetura paralela de propósito geral destinada a utilizar o poder computacional de GPUs nvidia Extensão da linguagem C, e permite controlar a execução de threads na GPU e gerenciar sua memória Arquitetura de uma GPU nvidia

12 Hierarquia de Memória Cada execução do kernel é composta por: Grade blocos threads Hierarquia de memória: - Registradores por thread - Memória compartilhada por bloco - Memória Global acessível a todas as threads

13 Execução de Aplicações Cada bloco é alocado a um multiprocessador da GPU, que pode executar 1 ou mais blocos simultaneamente Cada multiprocessador executa 16 threads no modelo SIMT: Single Intruction, Multiple Thread

14 Modelo de Execução Execução do programa controlada pela CPU que pode lançar kernels, que são trechos de código executados em paralelo por múltiplas threads na GPU A execução de programas CUDA é composta por ciclos CPU, GPU, CPU, GPU,, CPU, GPU, CPU.

15 Aplicações que rodam bem em GPUs Programas que conseguem bons speedups em GPUs: Podem ser subdivido em pequenos subproblemas, que são alocados a diferentes blocos e threads Cada thread mantém uma pequena quantidade de estado Alta razão (operações de ponto flutuante) / (memória) Os subproblemas são fracamente acoplados Acoplamento: quando um problema pode ser dividido em subproblemas menores, o acoplamento indica o quanto os subproblemas são dependentes entre si.

16 Retirado de

17 Retirado de

18 Retirado de

19 Retirado de

20 Retirado de

21 GPUs vs Supercomputadores Sistemas de multiprocessadores: Conjunto de unidades de processamento e memória conectados por uma rede de interconexão Sistemas classificados como: Memória compartilhada Troca de mensagens Exemplos: Supercomputadores Aglomerados (clusters)

22 Exemplos de Redes Estáticas Alta tolerância a falhas Ponto único de falha e gargalo No de conexões: O(N²) No de conexões: O(N)

23 Exemplos de Redes Estáticas k-cubo: nós: O (2k), Conexões: O (2k*k/2) Malha com k dimensões No de conexões: O(N*k/2) Hypercubo 10-dim Mais fácil de construir 1024 nós e 5120 conexões

24 Exemplos de Redes Estáticas Árvore Árvore Gorda Conexões: O(N) Atraso: O(log N) Nós mais altos com maior largura de banda Nó raiz é gargalo e ponto único de falha Normalmente implementadas com múltiplas conexões

25 Rede Dinâmica: Barramento Simples Todas os processadores ligados à memória por um barramento simples Fácil e barato de implementar Mas o barramento rapidamente se torna um gargalo

26 Múltiplos Barramentos

27 Exemplo: SGI Altix 4700 Fabricante: Silicon Graphics, Inc Memória: 272 GB Processadores: 68 Dual-Core Itanium 9000 (64 bits) Sistemas Operacionais: Linux (SUSE) e Enterprise Server 10 Capacidade de Disco: 30TB (InfiniteStorage 350 e 120) Custo: R$ 2 milhões Fonte:

28 Detalhes do Altix 4700 Projeto modular Placas blade com 2 sockets e 8 DIMM Memória de até 128TB e até centenas de processadores Software C/C++ e Fortran, Depuradores, ferramentas de análise MPI, OpenMP, Ferramentas de threading Rede de Interconexão SGI NUMAlink 4 Topologia árvore gorda (fat tree) 6.4GB/sec bidirectional bandwidth per link Fonte:

29 Fonte:

30 Supercomputador Moderno Jaguar: Oak Ridge National Laboratory

31 Supercomputador Moderno Extraído de

32 Aplicações para Supercomputadores Qualquer tipo de aplicação Quanto menor o acoplamento, maior o desempenho Mas normalmente são aplicações com alto grau acoplamento Justificam o alto preço da rede de interconexão Exemplos: - Previsão do tempo, evolução do clima - Mecânica dos Fluidos (projeto de carros e aviões) - Biologia Computacional: enovelamento de proteínas, redes de interação gênica, etc.

33 TESLA M processadores

34 TESLA S x 448 processadores

35 Barramento de GPUs Barramento de memória compartilhado Todos os processadores acessam a memória global utilizando o mesmo barramento Mecanismos primitivos de sincronização entre threads Acesso à memória do computador: PCI-Express (8 GB/s)

36 Aplicações que rodam bem em GPUs Programas que conseguem bons speedups em GPUs: Podem ser subdivido em pequenos subproblemas, que são alocados a diferentes blocos e threads Cada thread mantém uma pequena quantidade de estado Alta razão (operações de ponto flutuante) / (memória) Os subproblemas são fracamente acoplados Exemplos: Algoritmos genéticos, codificação de vídeo, processamento de imagens médicas, etc.

37 Parte II Introdução à Programação em CUDA

38 O que é CUDA É uma arquitetura paralela de propósito geral destinada a utilizar o poder computacional de GPUs nvidia Extensão da linguagem C, que permite o uso de GPUs: - Suporte a uma hierarquia de grupos de threads - Definição de kernels que são executados na GPU - API com funções, que permitem o gerenciamento da memória da GPU e outros tipos de controle

39 Obtendo o CUDA CUDA pode ser obtido gratuitamente no site da nvidia: Disponível para Windows (XP, Vista e 7), Linux e MacOS X, em versões de 32 e 64 bits. É composto por: CUDA Driver: Permite o acesso ao hardware CUDA Toolkit: Ferramentas e bibliotecas para programação em CUDA CUDA SKD: Exemplos de código

40 Exemplo de Instalação do CUDA Para instalar o toolkit, basta rodar o instalador: > chmod +x cudatoolkit_2.3_linux_64_ubuntu9.04.run.sh >./cudatoolkit_2.3_linux_64_ubuntu9.04.run.sh Digite os comandos para configurar a instalação: > export PATH=$PATH:/home/raphael/cuda/bin > export LD_LIBRARY_PATH= $LD_LIBRARY_PATH:/home/raphael/cuda/lib64 Agora o Toolkit está instalado e configurado! Vamos para o primeiro exemplo.

41 Modelo de Execução Execução do programa controlada pela CPU que pode lançar kernels, que são trechos de código executados em paralelo por múltiplas threads na GPU A execução de programas CUDA é composta por ciclos CPU, GPU, CPU, GPU,, CPU, GPU, CPU.

42 Hierarquia de Memória Cada execução do kernel é composta por: Grade blocos threads Hierarquia de memória: - Registradores por thread - Memória compartilhada por bloco - Memória Global acessível a todas as threads

43 Exemplo Simples Neste primeiro exemplo iremos aprender como criar um kernel simples, que realiza a soma de 2 vetores. Veremos as principais operações usadas em CUDA: Alocação e liberação de memória, transferência de dados, lançamento do kernel O código abaixo contém erros e limitações que iremos resolver na aula. // Device code global void VecAdd(float* A, float* B, float* C, int n) { int i = threadidx.x; if (i < n) C[i] = A[i] + B[i]; }

44 // Host code int main() { int n = 5; size_t size = n * sizeof(float); float *d_a, *d_b, *d_c; cudamalloc((void**)&d_a, size); cudamalloc((void**)&d_b, size); cudamalloc((void**)&d_c, size); float h_a[] = {1,2,3,4,5}; float h_b[] = {10,20,30,40,50}; float h_c[] = {0,0,0,0,0}; cudamemcpy(d_a, h_a, size, cudamemcpyhosttodevice); cudamemcpy(d_b, h_b, size, cudamemcpyhosttodevice); int nthreadsperblock = 256; int nblocks = n / nthreadsperblock; VecAdd<<>>(d_a, d_b, d_c); } cudamemcpy(h_c, d_c, size, cudamemcpydevicetohost); cudafree(d_a); cudafree(d_b); cudafree(d_c);

45 Avaliação do Exemplo I Para compilar o código, basta utilizar o comando: nvcc -o ex1 ex1.cu Perguntas: 1) O programa funciona corretamente? Teste seu funcionamento imprimindo o resultado obtido 2) Corrija o programa 3) Aumente o tamanho dos vetores para, por exemplo, Teste o resultado e, se não for o esperado, corrija o programa. Obs: Você deve manter o número de threads por bloco em 256. Dica: O valor de blockidx.x devolve o bloco ao qual a thread pertence

46 Arquitetura da GPU Multiprocessadores, com M processadores em cada Registradores Memória compartilhada Cache de constantes e textura Memória Global Host Memory CPU

47 Execução de Aplicações Cada bloco é alocado a um multiprocessador da GPU, que pode executar 1 ou mais blocos simultaneamente Cada multiprocessador executa 16 threads no modelo SIMT: Single Intruction, Multiple Thread

48 CUDA Runtime vs Driver API Programas em CUDA normalmente utilizam o CUDA Runtime, que fornece primitivas e funções de alto-nível Além disso, é possível utilizar também a API do driver, que permite um melhor controle da aplicação

49 CUDA 3.1 (Junho de 2010) Suporte a múltiplos (16) kernels simultâneos Melhorias no CUDA: - Suporte a printf no código do dispositivo - Suporte a ponteiros com endereços de funções - Suporte a funções recursivas Interoperabilidade entre API do driver e CUDA Runtime Melhorias em bibliotecas matemáticas

50 Arquitetura FERMI Melhoria no desempenho de dupla precisão Suporte a memória ECC Suporte a múltiplos kernels simultâneos

51 Modo de Emulação Neste tutorial, executaremos os códigos em modo emulação. Existem 2 motivos principais para utilizar o modo emulação: - Quando não temos uma placa gráfica compatível :-) - Para realizar debugging (GDB e printf) Mas existem grandes desvantagens: - Desempenho muito inferior - Difícil avaliar qualidade da implementação - Pode mascarar bugs no código (especialmente memória) Hoje é possível realizar debugging diretamente na GPU, de modo que a emulação está sendo descontinuada.

52 Exemplo 2: Multiplicação de Matrizes // M(row, col) = *(M.elements + row * M.width + col) typedef struct { int width, height; float *elements; } Matrix; global void MatMulKernel(Matrix A, Matrix B, Matrix C) { // Each thread computes one element of C float Cvalue = 0; int row = blockidx.y * blockdim.y + threadidx.y; int col = blockidx.x * blockdim.x + threadidx.x; C.elements[ } ] = Cvalue;

53 Exercício 1) O kernel está correto? Inspecionando o código, procure por erros que impeçam seu funcionamento e o corrija 2) Escreva o código da CPU que chama o kernel. Dica: Use os seguintes comandos para lançar o kernel dim3 dimblock(block_size_x, BLOCK_SIZE_Y); dim3 dimgrid(grid_size_x, GRID_SIZE_Y); MatMulKernel<<>>(d_a, d_b, d_c); 3) Escreva um teste para seu exemplo

54 Uso da Memória Compartilhada A otimização que traz o maior desempenho é o uso da memória compartilhada de cada multiprocessador - O acesso à memória global demora centenas de ciclos Host Memory CPU

55 Otimizações de código Multiplicação de matrizes com memória compartilhada Pedaços da matriz são colocados na memória de cada multiprocessador

56

57

58 Otimizando o código Otimizar o código é a parte mais difícil e trabalhosa durante o desenvolvimento de um programa CUDA. Hoje este processo ainda é artesanal, com a necessidade de tentarmos diferentes estratégias. Alguns pontos importantes a considerar são: - Divergência do controle de fluxo - Ocupação dos processadores - Acesso combinado (coalesced) à memória global - Conflitos de bancos da memória compartilhada - Sobrecarga da chamada do Kernel

59 Divergência do Controle de Fluxo As thread de cada bloco são divididas em warps, contendo 16 ou 32 threads GPUs permitem a execução simultânea de todas as threads do warp, desde que todas executem o mesmo código Quando threads executam códigos diferentes, dizemos que houve uma divergência na execução do código. Exemplos: comandos if, else, while, for, etc. global void VecAdd(float* A, float* B, float* C, int n) { int i = threadidx.x; if (i < n) C[i] = A[i] + B[i]; }

60 Ocupação dos Multiprocessadores O segredo para obter um bom desempenho é manter os processadores da GPU sempre ocupados. Para tal: - Os blocos devem ter tamanhos múltiplos de 32 Assim, coincidem com o tamanho dos warps - Usar o menor número possível de registradores por thread O número de blocos por multiprocessador será maior Com mais blocos por multiprocessador, haverão mais opções de threads para execução Especialmente quando as threads estiverem esperando por dados da memória global

61 Ocupação dos Multiprocessadores

62 Acesso Combinado (Coalesced) Quando 16 threads de um warp acessam a memória ao mesmo tempo, CUDA combina os acessos em uma única requisição Para tal, todas os endereços devem estar localizados em um único intervalo de 128 bytes

63 Acesso Combinado (Coalesced) É melhor que os dados a serem lidos sejam adjacentes No caso de dados com separações de 2 ou mais posições, o desempenho cai consideravelmente Dados com separação de 2

64 Acesso Combinado (Coalesced) Qual é a melhor opção? Um array de estruturas? Ou uma estrutura de arrays? struct Dados { int chave; int valor; }; Dados *vetordados; struct Dados { int *chave; int *valor; }; Dados estruturadados;

65 Bancos de Memória Compartilhada A memória compartilhada é dividida em 16 bancos, com palavras de 32 bits, que podem ser acessados simultaneamente

66 Bancos de Memória Compartilhada Quando ocorrem conflitos, a GPU serializa as requisições

67 Reduza as Chamadas do Kernel As chamadas ao Kernel causam um overhead Além disso, muitas vezes precisamos passar dados para o kernel ou obter resultados da execução Uma maneira de melhorar o desempenho é agrupar um maior número de tarefas em uma chamada Exemplo: Se for preciso resolver diversos sistemas lineares, é melhor resolver todos em uma única chamada do kernel

68 Parte III FireStream, OpenCL e Bibliotecas para CUDA

69 NVIDIA Performance Primitives (NPP) Biblioteca de funções utilizáveis em aplicações para GPUs No momento possui primariamente funções para processamento de imagem e vídeo. Exemplos: - Filtros - Redimensionamento - Histogramas - Aplicação de limiares - Detecção de bordas, etc.

70 GPU Accelerated Linear Algebra Biblioteca de funções para álgebra linear. Exemplos: - Solução de sistemas lineares - Rotinas para autovalores - Triangularizações - Decomposição em valores singulares, etc. Interfaces com C/C++, Fortran, Matlab, Python: - Chamadas realizadas diretamente da aplicação para CPU - Não é preciso programar em CUDA

71 Desempenho Aplicação de Fatorização com precisão simples e dupla

72 AMD FireStream As placas da AMD (antiga ATI) também fornecem suporte a GPGPU, através das placas da Série FireStream FireStream GPU com 800 núcleos - 2GB RAM, 108 GB/s TFlop (single), 240 GFlop (double) 3o trimestre/ FireStream 9370 e GB RAM TFlop (single), 528 GFlop (double)

73 Cyprus Architecture 10 SIMD units with 16 stream cores with 5 ALUs on each = 1600 ALUs - Difícil de usar as 5 ALUs - Relógio das ALUs é igual ao do chip

74 AMD Fusion Irá combinar em um chip: - Núcleos x86 - Núcleos SIMD para processamento paralelo

75 APU (Accelerated Processing Unit) Diferentes tipos de configurações poderão ser criadas a partir de blocos básicos.

76 ATI Stream SDK O acesso ao poder computacional é feito através do uso da ATI Stream SDK. Compatível com as arquiteturas FireStream e Fusion Programação através da linguagem OpenCL 1.0 Anteriormente utilizava o Brooks+

77 OpenCL Diferentes hardwares utilizam diferentes plataformas: - CUDA para nvidia e Brooks+ para AMD/ATI - OpenMP para programação de múltiplos processadores

78 OpenCL O objetivo é permitir que um mesmo programa possa ser executado em múltiplas plataformas de hardware. - Padrão aberto, totalmente livre de royalties. - Suporte da Apple, nvidia, AMD, Intel e outras. - Falta a Microsoft, que tem sua solução própria :-) - DirectCompute, que faz parte do DirectX 10 e 11 - Alguém lembra da disputa DirectX vs OpenGL?

79 OpenCL Apesar das vantagens, existe um certo ceticismos sobre a adoção do OpenCL - Diferentes arquiteturas tem características específicas, que precisam ser levadas em conta na otimização - Programas genéricos acabariam sendo nivelados por baixo - Quando comparado com CUDA, a sintaxe de OpenCL é mais complicada, dado que ela precisa trabalhar com múltiplas plataformas

80 Parte IV Aplicação: Simulação de Redes Neuronais

81 Neurociência Computacional Hoje temos a visão macro e micro do cérebro, mas ainda não somos capazes de ligar adequadamente estas visões Objetivo da neurociência computacional: Entender como um conjunto de neurônios e sua conectividade geram funções cognitivas complexas. Para tal, criamos modelos matemáticos de áreas cerebrais e simulamos estes modelos em computadores Modelos podem ser compostos por até milhões de neurônios Simulação exige um grande poder computacional provindos de grandes aglomerados ou supercomputadores

82 Modelagem de Neurônios Neurônios são um tipo altamente especializado de célula Possuem corpo celular, dendritos e axônio Mantém um potencial de membrana Se comunicam com outros neurônios Fonte: Dayan and Abbott. Theoretical Neuroscience. MITPress

83 Modelagem de Neurônios Cada compartimento é modelado por um circuito elétrico Capacitor - membrana Resistências - membrana - canais iônicos - ligações entre compartimentos

84 Canais Iônicos Ativos Canais iônicos ativos: Canais dependentes da voltagem que permitem a geração de potencias de ação São constituídos por portões que possuem uma dinâmica de abertura e fechamento dependente da voltagem: Fonte: N. Carlson, Physiology of Behavior Pearson Ed.

85 Integração Numérica É preciso integrar uma equação diferencial por neurônio Integração implícita gera melhor estabilidade [ A ] x [ V(t+dt) ] = [ C ] Através de uma cuidadosa numeração dos compartimentos e uma triangularização, a solução do sistema pode ser eficiente

86 Simulação utilizando GPUs Programas que conseguem bons speedups em GPUs: Subdivido em pequenos subproblemas, que são alocados a diferentes blocos e threads Cada thread mantém uma pequena quantidade de estado Alta razão (operações de ponto flutuante) / (memória) Os subproblemas são fracamente acoplados

87 Característica de nosso problema Dezenas de variáveis de estado por thread Cada thread deve representar um neurônio Limite no número de neurônios por bloco (entre 64 e 128) Acoplamento entre neurônios durante a comunicação Padrão de conexões pode ser irregular Atraso no tempo de comunicação entre neurônios Neurônios são diferentes entre si Mas podem ser categorizados em diferentes classes

88 Implementação do Simulador A simulação é divididas em rodadas controladas pela CPU: Inicialização da simulação Enquanto (tempoatual < tempototal) Lança execução do kernel Coleta de resultados da simulação Envio de dados à GPU Fim da simulação

89 Implementação do Kernel Cada neurônio é implementado por uma thread distinta Esta thread executa a diagonalização da matriz e faz substituição dos valores finais Código para a execução de cada neurônio é igual, de modo que não há divergência de execução Versão para CPU portada para GPU: Usava dados diretamente da memória global. O desempenho era ruim, inferior ao da CPU

90 Otimizações Uso da memória compartilhada Memória compartilhada é pequena para armazenar dados de todos os neurônios de um bloco Armazenamos os dados que são utilizados múltiplas vezes por passo de integração (leitura e escrita) Leituras conjunta (coalesced) Organização dos dados de modo que leitura de dados de múltiplos neurônios seja feita de modo simultâneo

91 Comunicação entre Neurônios Neurônios geram spikes, que são entregues a outros neuônios Cada neurônio se conecta a centenas ou milhares de neurônios

92 Comunicação entre Neurônios Hoje a comunicação é coordenada pela CPU Gera um grande gargalo no desempenho Desafio: Comunicação utilizando GPU 1 GPU: Comunicação entre threads de diferentes blocos Tem que ser feita pela memória global Uso de primitivas como AtomicAdd() 2 ou mais GPUs em 1 computador: É preciso passar necessariamente pela CPU 2 ou mais GPUs em múltiplos computadores: É preciso passar necessariamente pela rede

93 Hardware Utilizado Computador Intel Core i7 920, de 2.66GHz, 6 GB de memória RAM 2 duas placas gráficas nvidia GTX 295, com 2 GPUs e 1892 MB em cada Ubuntu 9.04 de 64 bits CUDA versão 2.2, com drivers Compilador g++, com opção -O3.

94 Resultados: Tempo de execução Cresce linearmente com o número de neurônios Mas quando incluímos conexões tempo 10 vezes maior Comunicação entre neurônios é coordenada pela CPU

95 Resultados: Speedup Sem conexões: ganho de 40x Com 100 conexões / neurônio: ganho de 10x

96 Resultados CPU: maior parte do tempo usada na integração numérica GPU: maior parte do tempo é usada para comunicação

97 Estado da Arte em Simulações Supercomputador IBM BlueGene com 4096 processadores Simulação de 4 milhões de neurônios de 6 compartimentos e 2 bilhões de sinapses Cluster com 60 processadores de 3GHz and 1.5 GB of RAM Simulação de 1 milhão de neurônios e meio bilhão de sinapses. 10 minutos para inicializar e 1 minuto para simular 1 segundo de funcionamento da rede

98 Modelos de Grande Escala Já estão sendo realizadas simulações de modelos com 22 milhões de neurônios e 11 bilhões de sinapse Supercomputadores com dezenas de milhares de processadores

99 Parte V Conclusões

100 Conclusões Vimos que as GPUs permitem a obtenção de um excelente desempenho a um baixo custo Composta por centenas processadores simples e um barramento compartilhado para acesso a memória Mas: Não fornecem bom desempenho para qualquer tipo de aplicação

101 Conclusões A plataforma CUDA permite o uso de GPUs para executar aplicações paralelas Extensão da linguagem C, sendo de fácil aprendizado Mas para rodar de modo eficiente, é essencial que o código seja otimizado! A linguagem OpenCL permite criar programas que rodam em múltiplas arquiteturas Mas é difícil fazer um programa genérico que seja eficiente em arquiteturas diferentes

102 Onde Aprender Mais Existem uma grande quantidade de material na Internet sobre CUDA. No site da nvidia existe links para diversos tutoriais e cursos online sobre a arquitetura CUDA - Para quem domina o inglês falado, neste site tem um curso em vídeo sobre CUDA dado por um engenheiro da nvidia na Universidade de Illinois - Outra opção é um curso online (texto) publicado no site Dr. Dobbs. - A distribuição do CUDA vem com 2 guias: CUDA Programming Guide e CUDA Best Practices