Nossa experiência no uso de um cluster de computação de 480 GPUs AMD RX 480 para resolver problemas matemáticos. Como problema, pegamos a prova do teorema de um artigo do professor A. Chudnov "
Decomposições cíclicas de conjuntos que separam dígrafos e classes cíclicas de jogos com recompensa garantida ". A tarefa é encontrar o número mínimo de participantes em uma coalizão nos jogos de coalizão do tipo Nim, o que garante a vitória de uma das partes.
Desenvolvimento de CPU
O primeiro processador que realmente obteve distribuição em massa é o 8086 da Intel, desenvolvido em 1978. A velocidade do clock de 8086 era de apenas 8 MHz. Alguns anos depois, os primeiros processadores apareceram dentro dos quais havia 2, 4 e até 8 núcleos. Cada núcleo permitiu que seu código fosse executado independentemente dos outros. Para comparação, o moderno processador Intel Core i9-7980XE opera com uma frequência de 2,6 GHz e contém 18 núcleos. Como você pode ver, o progresso não pára!
Desenvolvimento de GPU
Simultaneamente ao desenvolvimento de processadores centrais, também foram desenvolvidas placas de vídeo. Basicamente, suas características são importantes para jogos de computador, onde as novas tecnologias são especialmente coloridas e a renderização de imagens em 3D está gradualmente se aproximando da qualidade fotográfica. No início do desenvolvimento de jogos de computador, o cálculo da imagem foi realizado na CPU, mas logo foi alcançada a inventividade dos desenvolvedores de gráficos 3D, que conseguiram otimizar até as coisas óbvias (
InvSqrt () é um bom exemplo). Portanto, coprocessadores com um conjunto especial de instruções para executar cálculos 3D começaram a aparecer nas placas de vídeo. Com o tempo, o número de equipes cresceu, o que, por um lado, permitiu trabalhar de forma mais flexível e eficiente com a imagem e, por outro, complicou o processo de desenvolvimento.
Desde 1996, os aceleradores gráficos S3 ViRGE, 3dfx Voodoo, Diamond Monster e outros começaram a ser produzidos. Em 1999, a nVidia lançou o processador GeForce 256, introduzindo o termo GPU - um processador gráfico. Já é universal, pode lidar com cálculos geométricos, transformação de coordenadas, posicionamento de pontos de iluminação e trabalhar com polígonos. A diferença entre a GPU e outros chips gráficos era que, além de comandos especializados, havia um conjunto de comandos padrão com os quais você podia implementar seu próprio algoritmo de renderização. Isso deu uma vantagem significativa, pois permitiu adicionar efeitos especiais, e não apenas aqueles que já estão programados na placa de vídeo. Começando com a GeForce 8000/9000, os processadores de stream apareceram na GPU - computadores já desenvolvidos. Seu número variou de 16 a 128, dependendo do modelo.Na terminologia moderna, eles são chamados de unidades de sombreamento unificadas ou simplesmente unidades de sombreamento. As GPUs AMD Vega 64 fabricadas hoje contêm 4096 unidades de shader e a frequência do relógio pode chegar a 1536 MHz!
O que contém uma GPU?
A arquitetura da GPU difere da CPU em um grande número de núcleos e em um conjunto minimalista de instruções destinadas principalmente à computação vetorial. No nível da arquitetura, foram resolvidos problemas de operação paralela de um grande número de núcleos e acesso simultâneo à memória. As GPUs modernas contêm de 2 a 4 mil unidades de shader, que são combinadas em unidades de computação (Compute Unit). Na computação paralela, o problema do acesso simultâneo à memória é especialmente grave. Se cada um dos processadores de fluxo tentar gravar na célula de memória, esses comandos terminarão no bloqueio e precisarão ser enfileirados, o que reduzirá bastante o desempenho. Portanto, os processadores de fluxo executam instruções em pequenos grupos: enquanto um grupo executa os cálculos, o outro carrega os registros, etc. Você também pode combinar os núcleos em grupos de trabalho com memória compartilhada e mecanismos internos de sincronização.
Outra característica importante da GPU é a presença de registradores de vetores e ALUs de vetores, que podem executar operações simultaneamente para vários componentes do vetor. Isso é principalmente necessário para gráficos 3D, mas como nosso mundo é tridimensional, nada nos impede de usá-lo para muitos cálculos físicos. Na presença de ALUs de vetor livre, elas também podem ser usadas para calcular quantidades escalares.
Eles são tão diferentes, CPU e GPU
Para a operação completa do sistema de computação, os dois tipos de dispositivos são importantes. Por exemplo, estamos executando um programa passo a passo, um determinado algoritmo seqüencial. Não há como executar a quinta etapa do algoritmo, portanto os dados para ele são calculados na etapa quatro. Nesse caso, é mais eficiente usar uma CPU com um cache grande e alta velocidade de clock. Mas existem classes inteiras de tarefas que se prestam bem à paralelização. Nesse caso, a eficácia da GPU é óbvia. O exemplo mais comum é calcular os pixels de uma imagem renderizada. O procedimento para cada pixel é quase o mesmo, os dados sobre objetos e texturas 3D estão localizados na RAM da placa de vídeo e cada processador de fluxo pode calcular independentemente sua própria parte da imagem.
Aqui está um exemplo de uma tarefa moderna - treinar uma rede neural. Um grande número de neurônios idênticos precisa ser treinado, ou seja, para alterar os coeficientes de peso de cada neurônio. Após essas alterações, é necessário passar as seqüências de teste pela rede neural para treinamento e obter vetores de erro. Tais cálculos são adequados para a GPU. Cada processador de fluxo pode se comportar como um neurônio e, durante o cálculo, não será necessário criar a solução de maneira sequencial, todos os nossos cálculos ocorrerão simultaneamente. Outro exemplo é o cálculo dos fluxos aerodinâmicos. É necessário descobrir o possível comportamento da ponte projetada sob a influência do vento, simular sua estabilidade aerodinâmica, encontrar os locais ideais de instalação para as carenagens ajustar o fluxo de ar ou calcular a resistência à ressonância do vento. Lembra-se da famosa "ponte da dança" em Volgogrado? Eu acho que ninguém iria querer estar naquele momento na ponte ...
O comportamento do fluxo de ar em cada ponto pode ser descrito pelas mesmas equações matemáticas e resolver essas equações em paralelo em um grande número de núcleos.
GPU nas mãos dos programadores
Para realizar cálculos na GPU, um idioma e compilador especiais são usados. Existem várias estruturas para executar a computação geral da GPU: OpenCL, CUDA, C ++ AMP, OpenACC. Os dois primeiros foram amplamente utilizados, mas o uso do CUDA é limitado apenas pelas GPUs da nVidia.
O OpenCL foi lançado em 2009 pela Apple. Mais tarde, Intel, IBM, AMD, Google e nVidia ingressaram no Khronos Group e anunciaram seu suporte ao padrão comum. Desde então, uma nova versão do padrão aparece a cada um ano e meio ou dois e cada um traz melhorias cada vez mais sérias.
Até o momento, a linguagem OpenCL C ++ versão 2.2 está em conformidade com o padrão C ++ 14, suporta a execução simultânea de vários programas no dispositivo, a interação entre eles através de filas e pipelines internos e permite o gerenciamento flexível de buffers e memória virtual.
Tarefas reais
Um problema interessante da teoria dos jogos, em cuja solução participamos, é a prova do teorema de um artigo do professor A. Chudnov "
Decomposições cíclicas de conjuntos que separam dígrafos e classes cíclicas de jogos com recompensa garantida ". A tarefa é encontrar o número mínimo de participantes em uma coalizão nos jogos de coalizão do tipo Nim, o que garante a vitória de uma das partes.
Do ponto de vista matemático, é uma busca por uma sequência cíclica de suporte. Se você representar a sequência na forma de uma lista de zeros e uns, a verificação de suporte poderá ser implementada por operações lógicas bit a bit. Do ponto de vista da programação, essa sequência é um registro longo, por exemplo, 256 bits. A maneira mais confiável de resolver esse problema é classificar todas as opções, exceto a impossível por razões óbvias.
Os objetivos da solução do problema são questões de processamento de sinal eficaz (detecção, sincronização, medição de coordenadas, codificação, etc.).
A complexidade de resolver esse problema é resolver um grande número de opções. Por exemplo, se estamos procurando uma solução para n = 25, então são 25 bits e, se n = 100, já são 100 bits. Se tomarmos o número de todas as combinações possíveis, então para n = 25 é 2 ^ 25 = 33 554 432, e para n = 100 já é 2 ^ 100 = 1 267 650 600 228 229 401 496 703 205 376 combinações. O aumento da complexidade é simplesmente colossal!
Essa tarefa é bem paralela, o que significa que é ideal para o cluster de GPU.
Programmers vs Maths
Inicialmente, os matemáticos resolveram esse problema no Visual Basic no Excel, de modo que conseguiram obter soluções primárias, mas o baixo desempenho das linguagens de script não nos permitiu avançar muito. A decisão de n = 80 levou um mês e meio ... Inclinamos a cabeça na frente dessas pessoas pacientes.
Na primeira etapa, implementamos o algoritmo de tarefa em C e o lançamos na CPU. No processo, descobriu-se que muito pode ser otimizado ao trabalhar com sequências de bits.
Em seguida, otimizamos a área de pesquisa e eliminamos a duplicação. Além disso, uma análise do código do assembler gerado pelo compilador e a otimização do código para os recursos do compilador deram um bom resultado. Tudo isso possibilitou um aumento significativo na velocidade dos cálculos.
O próximo estágio de otimização foi o perfil. A medição do tempo de execução de várias seções do código mostrou que em algumas ramificações do algoritmo a carga na memória aumentou significativamente, assim como a ramificação excessiva do programa foi revelada. Devido a essa falha "pequena", quase um terço da energia da CPU não foi usada.
Um aspecto muito importante da solução de tais problemas é a precisão da escrita do código. Ninguém sabe as respostas corretas para esse problema e, portanto, não há vetores de teste. Existe apenas a primeira parte da gama de soluções que os matemáticos encontraram. A confiabilidade de novas soluções só pode ser garantida pela precisão da escrita do código.
Portanto, chegou a etapa de preparar o programa para a solução na GPU e o código foi modificado para funcionar em vários segmentos. O programa de controle agora está envolvido no envio de tarefas entre threads. Em um ambiente multithread, a velocidade de cálculo aumentou 5 vezes! Isso foi alcançado devido à operação simultânea de 4 threads e à combinação de funções.
Nesta fase, a decisão fez os cálculos corretos até n = 80 em 10 minutos, enquanto no Excel, esses cálculos levaram um mês e meio! Pouca vitória!
GPU e OpenCL
Foi decidido usar o OpenCL versão 1.2 para garantir a máxima compatibilidade entre diferentes plataformas. A depuração inicial foi feita na CPU da Intel e depois na GPU da Intel. Então eles mudaram para a GPU da AMD.
O padrão OpenCL 1.2 suporta variáveis inteiras de 64 bits. A dimensão de 128 bits é limitada pela AMD, mas é compilada em dois números de 64 bits. Por motivos de compatibilidade e para otimizar o desempenho, decidiu-se apresentar um número de 256 bits como um grupo de números de 32 bits, operações lógicas bit a bit nas quais são executadas na GPU ALU interna o mais rápido possível.
Um programa OpenCL contém um kernel - uma função que é o ponto de entrada de um programa. Os dados para processamento são baixados da CPU para a RAM da placa de vídeo e transferidos para o kernel na forma de buffers - ponteiros para uma matriz de dados de entrada e saída. Por que uma matriz? Executamos computação de alto desempenho, precisamos de muitas tarefas que são executadas simultaneamente. O kernel é executado no dispositivo em várias instâncias. Cada núcleo conhece seu identificador e recebe sua própria parte de um buffer compartilhado. O caso em que a solução mais simples é a mais eficaz. O OpenCL não é apenas uma linguagem, mas também uma estrutura abrangente na qual todos os detalhes da computação científica e da computação de jogos são cuidadosamente pensados. Isso facilita a vida do desenvolvedor. Por exemplo, você pode iniciar muitos threads, o gerenciador de tarefas os colocará no próprio dispositivo. As tarefas que não iniciaram a execução imediata serão colocadas em fila e iniciadas à medida que as unidades de computação se tornarem livres. Cada instância do kernel possui seu próprio espaço no buffer de saída, onde coloca a resposta após a conclusão do trabalho.
A principal tarefa do gerenciador OpenCL é garantir a execução paralela de várias instâncias do kernel. A experiência científica e prática acumulada ao longo de décadas é aplicada aqui. Enquanto alguns núcleos carregam dados nos registradores, outra parte atualmente trabalha com memória ou realiza cálculos - como resultado, o núcleo da GPU sempre está totalmente carregado.
O compilador OpenCL faz um bom trabalho de otimização, mas é mais fácil para um desenvolvedor influenciar o desempenho. A otimização da GPU segue em duas direções - acelerando a execução do código e a possibilidade de paralelizar. A qualidade do paralelismo do código pelo compilador depende de várias coisas: o número de registros de rascunho ocupados (localizados na memória mais lenta da GPU - global), o tamanho do código compilado (é necessário ajustar em 32 kb de cache), o número de registros vetoriais e escalares usados.
GPU ComBox A-480 ou um milhão de núcleos
Essa é a parte mais interessante do projeto, quando mudamos do Excel para um cluster de computação que consiste em placas gráficas AMD RX 480 480. Grande, rápido e eficiente. Completamente pronto para cumprir a tarefa e obter os resultados que o mundo nunca viu antes.
Gostaria de observar que, em todas as etapas de melhoria e otimização do código, iniciamos a busca por uma solução desde o início e comparamos as respostas da nova versão com as anteriores. Isso nos permitiu ter certeza de que a otimização e as melhorias do código não introduziram erros nas soluções. Aqui você precisa entender que não há respostas corretas no final do livro e ninguém no mundo as conhece.
O lançamento no cluster confirmou nossas suposições sobre a velocidade das soluções: a busca por seqüências para n> 100 levou cerca de uma hora. Foi incrível ver como as novas soluções estavam no cluster ComBox A-480 em minutos, enquanto no CPU demorava muitas horas.
Em apenas duas horas do cluster de computação, obtivemos todas as soluções até n = 127. Uma verificação das soluções mostrou que as respostas obtidas são confiáveis e correspondem aos teoremas do professor A. Chudnov mencionados no artigo
Evolução da velocidade
Se você observar o ganho de desempenho no curso da solução do problema, os resultados foram aproximadamente os seguintes:
- meses e meio para n = 80 no Excel;
- uma hora para n = 80 no Core i5 com um programa C ++ otimizado;
- 10 minutos para n = 80 no Core i5 usando multithreading;
- 10 minutos para n = 100 em uma GPU AMD RX 480;
- 120 minutos para n = 127 no ComBox A-480.
Perspectivas e futuro
Muitas tarefas na interseção entre ciência e prática estão pendentes para melhorar nossa vida. O mercado de aluguel de energia para computação está apenas emergindo e a necessidade de computação paralela continua a crescer.
Possíveis aplicações da computação paralela:
- tarefas de controle automático de veículos e drones;
- cálculos de características aerodinâmicas e hidrodinâmicas;
- reconhecimento de fala e imagens visuais;
- treinamento em redes neurais;
- tarefas de astronomia e astronáutica;
- análise estatística e correlação de dados;
- dobrar compostos proteína-proteína;
- diagnóstico precoce de doenças usando IA.
Uma direção separada é a computação em nuvem na GPU. Por exemplo, gigantes como Amazon, IBM e Google alugam seu poder de computação na GPU. Hoje, podemos dizer com confiança que o futuro da computação paralela de alto desempenho pertencerá aos clusters de GPU.