A Lock-Free, Fully GPU-Resident Architecture for the Verification of Goldbach's Conjecture

Este artigo apresenta uma arquitetura totalmente residente em GPU e sem bloqueios para a verificação em larga escala da conjectura de Goldbach, que migra todo o pipeline de geração de segmentos para o dispositivo e utiliza um pool de roubo de trabalho assíncrono para alcançar eficiência paralela superior a 98% e uma aceleração de 45,6 vezes em comparação com abordagens anteriores acopladas ao host.

O essencial

Imagine que você está tentando provar uma regra matemática antiga e misteriosa chamada Conjectura de Goldbach. A regra diz: "Todo número par maior que 2 pode ser formado somando dois números primos". É como dizer que qualquer número par é uma "receita" feita de apenas dois ingredientes especiais (os primos).

Por séculos, matemáticos tentaram provar isso para todos os números. Como não conseguem provar com papel e caneta, eles usam computadores para testar milhões e bilhões de números, um por um, até encontrar um que quebre a regra (o que nunca aconteceu até hoje).

Este artigo descreve uma nova máquina super-rápida feita para testar essa regra, usando placas de vídeo (GPUs) de última geração. Aqui está a explicação simplificada:

1. O Problema Antigo: O "Engarrafamento" na Estrada

Antes, os pesquisadores usavam uma abordagem onde o "cérebro" do computador (o processador principal, ou CPU) preparava os números e os enviava para as "músculos" (as placas de vídeo, ou GPUs) para fazerem o trabalho pesado.

• A Analogia: Imagine que a CPU é um cozinheiro e as GPUs são 400 garçons. O cozinheiro prepara um prato, corre até a mesa, entrega ao garçom e volta para a cozinha.
• O Erro: O cozinheiro era muito lento comparado aos garçons. Os garçons ficavam parados, esperando o próximo prato. Mesmo que você tivesse 4 garçons, eles não trabalhavam mais rápido porque o cozinheiro não conseguia entregar comida rápido o suficiente. O computador ficava "preso" na transferência de dados.

2. A Solução: A Cozinha Autônoma

Os autores deste artigo criaram uma arquitetura onde cada garçom (GPU) tem sua própria cozinha completa.

• O que mudou: Em vez de o cozinheiro (CPU) preparar a comida e enviar, cada garçom agora tem ingredientes e ferramentas dentro da própria mesa (na memória rápida da placa de vídeo).
• A Técnica: Eles usaram uma técnica chamada "memória compartilhada L1". É como se cada garçom tivesse um pequeno armário ao lado dele com tudo o que precisa. Eles não precisam mais correr até a cozinha principal para pegar os ingredientes. Eles preparam, verificam e descartam tudo ali mesmo, na velocidade da luz.

3. O Sistema de "Roubo de Trabalho" (Lock-Free)

Para garantir que todos os garçons trabalhem juntos sem brigar, eles criaram um sistema inteligente de distribuição de tarefas.

• O Problema: Se você dividir o trabalho igualmente (ex: 100 pratos para cada um), e um garçom for mais lento que o outro, todos os outros ficam esperando o mais lento terminar.
• A Solução: Eles criaram uma "pilha de pedidos" onde cada garçom pega um prato assim que termina o anterior. Se um garçom for super-rápido, ele pega mais pratos. Se for lento, ele pega menos. Ninguém fica esperando ninguém. Isso é chamado de "pool de trabalho sem travas" (lock-free).
• Resultado: Com 4 placas de vídeo, o sistema funciona quase como 4 vezes mais rápido que uma só (98,6% de eficiência). É como ter 4 times de corrida onde ninguém perde tempo esperando o outro.

4. A Segurança Matemática (O Guarda-Costas)

Como eles estão lidando com números gigantescos (até 10 quintilhões!), existe o risco de o computador "quebrar" os números (estouro de memória) e dar um resultado errado sem ninguém perceber.

• O Guarda-Costas: Eles instalaram "guardas" matemáticos rigorosos. Antes de qualquer cálculo, o sistema verifica se o número não vai ficar grande demais para a memória. Se o número for muito grande, o sistema para com segurança em vez de dar um resultado falso. Isso garante que, se eles disserem "a regra funciona até aqui", é verdade absoluta.

5. Os Resultados: Velocidade Insana

Os testes foram feitos em uma placa de vídeo nova (RTX 5090, que ainda é futura no momento da escrita, mas o artigo a trata como presente).

• Comparação: A versão antiga (com o "cozinheiro" lento) levava cerca de 18 segundos para testar 10 bilhões de números. A nova versão fez isso em 0,4 segundos. É um aumento de velocidade de 45 vezes.
• O Recorde: Com 4 placas de vídeo trabalhando juntas, eles conseguiram verificar todos os números pares até 10 trilhões em apenas 2 minutos e 13 segundos. E não encontraram nenhum erro na regra de Goldbach.

Resumo Final

Este artigo é sobre transformar uma corrida de carros onde todos esperam no sinal vermelho (o computador antigo) em uma corrida onde cada carro tem seu próprio combustível e pista, e ninguém precisa esperar pelo outro.

Eles conseguiram fazer o computador "pensar" e "verificar" tudo dentro da própria placa de vídeo, sem depender do processador principal. O resultado é uma máquina capaz de testar a matemática em uma velocidade que antes parecia impossível, abrindo caminho para testar números ainda maiores no futuro.

Em suma: Eles tiraram o "gargalo" que segurava a velocidade, deram autonomia total às placas de vídeo e criaram um sistema que escala perfeitamente, provando que a Conjectura de Goldbach é verdadeira para números que a humanidade mal consegue imaginar.

Resumo técnico

Resumo Técnico: Arquitetura GoldbachGPU v2.0

1. O Problema

A Conjectura de Goldbach afirma que todo número inteiro par maior que 2 pode ser expresso como a soma de dois números primos. Embora existam avanços teóricos (como o Teorema de Chen), a conjectura binária permanece não provada. A verificação computacional é essencial para estabelecer limites empíricos.

O trabalho anterior dos autores (GoldbachGPU v1) resolveu o gargalo de memória (VRAM) utilizando uma peneira segmentada, permitindo verificar até $10^{12}$ em uma única GPU. No entanto, essa arquitetura introduziu um novo gargalo crítico:

• Dependência Host-Device: A construção da peneira (bitset de primos) e a transferência dos dados para a GPU ocorriam na CPU via barramento PCIe.
• Latência de I/O: Em GPUs modernas de alta velocidade, os kernels de verificação eram executados em frações de milissegundos, ficando ociosos enquanto aguardavam a CPU para fornecer o próximo segmento.
• Escalabilidade Limitada: Adicionar mais GPUs não resultava em aceleração significativa, pois o sistema estava saturado pela capacidade de processamento da CPU, não pela GPU.

2. Metodologia e Arquitetura Proposta

O artigo apresenta a GoldbachGPU v2.0, uma arquitetura totalmente descentralizada e residente no dispositivo (GPU), eliminando a dependência da CPU durante o caminho crítico de verificação.

Principais Componentes Técnicos:

• Peneira Segmentada Nativa em GPU (L1 Shared Memory):

  • A geração da peneira de Eratóstenes foi migrada inteiramente para a GPU.
  • Utiliza tiling (azulejamento) na memória compartilhada L1 (48 KB por SM em arquiteturas Ada Lovelace/Blackwell). Cada segmento é dividido em blocos de 32.768 números ímpares (4 KB), permitindo que os threads da GPU co-sielem (peneirem cooperativamente) os dados sem acesso à memória global ou transferência PCIe.
  • Isso elimina a transferência do bitset de 14 MB por segmento, reduzindo a comunicação Host-Device para apenas um índice atômico de 8 bytes e um resultado de 4 bytes.

• Pool de Trabalho Assíncrono Livre de Bloqueio (Lock-Free Work-Stealing):

  • Substitui a partição estática de carga por um contador atômico de 64 bits (std::atomic<uint64_t>) na memória do host.
  • Cada thread da CPU (uma por GPU) busca o próximo segmento a processar usando fetch_add atômico.
  • Isso garante que GPUs mais rápidas não fiquem ociosas esperando por GPUs mais lentas, permitindo um balanceamento de carga dinâmico e eficiência próxima de 100%.

• Fallback Otimizado em CPU (Fase 2):

  • Se a verificação na GPU (Fase 1) falhar (o que é estatisticamente raro para $N \le 10^{13}$), o sistema aciona uma rotina de fallback na CPU.
  • A CPU utiliza uma busca binária em uma lista pré-computada de primos até $10^8$ e, se necessário, um teste de primalidade Miller-Rabin determinístico de 128 bits.

• Garantias de Corretude e Segurança:

  • Implementação rigorosa de guardas contra overflow de inteiros de 64 bits.
  • Uso de aritmética de 128 bits (uint128_t) para o teste Miller-Rabin, garantindo que a verificação seja matematicamente sólida até o limite teórico de $1,84 \times 10^{19}$.
  • Tratamento de erros robusto que libera recursos de VRAM e bloqueios antes de encerrar, evitando corrupção de estado.

3. Principais Contribuições

1. Eliminação do Gargalo de I/O: A migração completa da geração de segmentos para a GPU removeu a latência de PCIe do caminho crítico, transformando o sistema de I/O-bound para compute-bound.
2. Escalabilidade Multi-GPU Eficiente: A introdução do pool de trabalho atômico permitiu escalar para múltiplas GPUs com eficiência de paralelismo quase ideal, superando as limitações de partição estática.
3. Limite de Verificação Estendido: O sistema foi projetado e validado para operar com segurança até $1,84 \times 10^{19}$, superando os limites anteriores de verificação em hardware de consumo.
4. Interface de Linha de Comando Flexível: Novos flags (--start, --gpus, --progress) permitem a divisão de tarefas em grandes clusters e o monitoramento em tempo real sem bloquear os workers da GPU.

4. Resultados e Desempenho

Os testes foram realizados em estações de trabalho com GPUs NVIDIA RTX 5090 (arquitetura Blackwell) e CUDA 12.8.1.

• Aceleração Algorítmica:

  • Comparado à versão anterior (v1) no mesmo hardware, a v2.0 alcançou um speedup de 45,6x para $N = 10^{10}$.
  • O speedup cresce com $N$, pois a sobrecarga de I/O da versão antiga se acumulava proporcionalmente ao número de segmentos.

• Eficiência de Paralelismo (Multi-GPU):

  • 2 GPUs: Eficiência de 99,7%.
  • 4 GPUs: Eficiência de 98,6%.
  • O tempo de inicialização e o esvaziamento do último segmento representam a única perda de eficiência, que diminui à medida que o tamanho do problema aumenta.

• Tempos de Execução (Wall-clock):

  • Verificação até $10^{12}$: 36,5 segundos em uma única RTX 5090.
  • Verificação até $10^{13}$: 133,5 segundos em um sistema de 4 GPUs.
  • Nenhum contraexemplo foi encontrado, confirmando a conjectura até esses limites.

• Otimização de Memória:

  • A transferência de dados Host-Device foi reduzida drasticamente: de ~14 MB por segmento (v1) para apenas ~628 KB (lista de primos pequenos) + 4 bytes (resultado) por segmento.
  • O tráfego total de Device-to-Host para uma execução completa de $10^{13}$ foi de apenas 20 KB.

5. Significado e Impacto

Este trabalho representa um marco na verificação computacional de conjecturas matemáticas em hardware heterogêneo. Ao demonstrar que é possível eliminar completamente a dependência da CPU para a geração de dados de peneira, o artigo estabelece um novo padrão para arquiteturas de verificação em GPU.

• Reprodutibilidade: Todo o código é de código aberto, permitindo que a comunidade científica reproduza os resultados em hardware comercial.
• Futuro: A arquitetura abre caminho para a verificação de limites ainda maiores (acima de $10^{19}$) através de técnicas de aritmética de precisão arbitrária (256 bits) e distribuição em clusters MPI, além de sugerir otimizações futuras como o uso de "bitwise bulk-marking" para aumentar ainda mais a taxa de transferência de memória.

Em suma, a GoldbachGPU v2.0 transforma a verificação da Conjectura de Goldbach de um processo limitado por I/O e memória em um processo altamente escalável e eficiente, aproveitando ao máximo o poder de processamento das GPUs modernas.