Tempo de leitura: 5 minutos
Olá, é um prazer inenarrável estar mais uma vez escrevendo este post. A NVIDIA apresentou uma nova evolução do cuOpt capaz de distribuir problemas enormes de programação linear entre várias GPUs. Com o mPDLP, modelos que ultrapassam 100 milhões de variáveis podem ser processados com menos pressão sobre a memória de cada dispositivo e, em alguns cenários, com ganhos expressivos de velocidade.
A proposta parece simples: colocar mais GPUs para trabalhar ao mesmo tempo. O desafio real, porém, está em fazer com que elas não passem mais tempo trocando dados do que resolvendo o problema. É justamente nessa comunicação entre dispositivos que o NVIDIA cuOpt mPDLP tenta avançar.
NVIDIA cuOpt mPDLP distribui problemas grandes entre GPUs
O mPDLP é uma implementação multi-GPU do método Primal-Dual Hybrid Gradient para programação linear. Esse tipo de problema aparece em tarefas como planejamento de cadeias de suprimentos, alocação de recursos e expansão de sistemas de energia, nas quais é necessário encontrar a melhor decisão respeitando uma grande quantidade de restrições.
Segundo a NVIDIA, o método distribui os modelos entre GPUs conectadas por NVLink. A abordagem pode reduzir o tempo de solução em problemas que seriam demorados demais em uma única GPU e diminuir em até seis vezes o uso máximo de memória por GPU em comparação com a versão PDLP de uma só GPU. Os problemas avaliados podem chegar a 2,1 bilhões de elementos não nulos na matriz de restrições.
O ganho não aparece automaticamente em qualquer modelo. Em problemas menores, o custo de sincronização e transferência de dados pode superar o benefício do processamento paralelo. A vantagem tende a crescer quando a matriz é suficientemente grande e o tempo gasto nos cálculos compensa a comunicação entre as GPUs.
Como o NVIDIA cuOpt mPDLP reduz a comunicação
O núcleo do PDLP envolve multiplicações esparsas de matriz por vetor, conhecidas como SpMV. Em termos práticos, cada cálculo usa apenas parte dos dados disponíveis, porque matrizes esparsas contêm muitos elementos iguais a zero.
O NVIDIA cuOpt mPDLP explora essa característica para organizar os dados em um grafo bipartido de dependências. De um lado ficam as variáveis primais e, do outro, as variáveis duais. As conexões representam quais dados são necessários para calcular cada resultado.
A matriz é então dividida entre as GPUs tentando manter no mesmo dispositivo as dependências mais próximas. As conexões que atravessam a divisão exigem comunicação entre GPUs, enquanto as demais podem ser processadas localmente. É uma ideia parecida com separar uma equipe em salas, mas mantendo juntas as pessoas que precisam conversar com frequência.
Para viabilizar esse fluxo, a solução utiliza a combinação de NVLink, NVSwitch e NCCL. Esses componentes permitem transferências e operações coletivas entre GPUs com alta largura de banda. Ainda assim, o desempenho depende do padrão de esparsidade da matriz: muitos cortes entre partições podem aumentar a comunicação e reduzir ou até eliminar o ganho esperado.
Resultados do NVIDIA cuOpt mPDLP em problemas de grande escala
Nos testes descritos pela NVIDIA, foram avaliadas mais de 100 instâncias de programação linear em GPUs NVIDIA DGX B200. A comparação envolveu a implementação PDLP em uma única GPU e o D-PDLP, uma abordagem multi-GPU anterior.
Os ganhos mais perceptíveis apareceram quando o número de elementos não nulos ultrapassou 10 milhões. Em um dos casos, o mPDLP alcançou aceleração de até 11,4 vezes considerando apenas as etapas do PDLP, embora o ganho final, incluindo operações como pré-processamento, particionamento e pós-processamento, tenha sido menor.
Na comparação com o D-PDLP, a NVIDIA relata ganhos entre 1,2 e 2,5 vezes na maioria das instâncias grandes. O resultado não foi uniforme: três problemas considerados ultragrandes tiveram desempenho inferior com o mPDLP. Isso reforça que a quantidade de variáveis não é o único fator determinante; a estrutura da matriz e a proporção de conexões entre GPUs também importam.
Aplicações de parceiros ilustram o tipo de cenário visado. A Kinaxis relatou aceleração de 3,3 vezes em um modelo de planejamento de cadeia de suprimentos com mais de 135 milhões de variáveis usando oito GPUs H100 conectadas por NVLink. Já a PSR informou ganho superior a cinco vezes em um modelo de expansão de sistemas de energia com 185 milhões de variáveis executado em oito GPUs B200.
O que vem depois do NVIDIA cuOpt mPDLP
A NVIDIA afirma que pretende aprimorar o particionamento para considerar não apenas as conexões, mas também a carga de trabalho de cada GPU. Outra frente é executar cálculos locais enquanto os dados remotos são transferidos, escondendo parte do custo de comunicação.
A empresa também trabalha em um mecanismo de feasibility polishing, voltado a encontrar soluções viáveis em menos iterações, mesmo quando a solução ainda não é a mais otimizada possível. Essa troca pode ser útil em ambientes de planejamento nos quais uma resposta viável dentro do prazo é mais valiosa do que uma resposta teoricamente perfeita que chega tarde demais.
O código do cuOpt está disponível no GitHub da NVIDIA, e a empresa publicou um tutorial de mPDLP para configurar o solver e comparar tempos de execução com diferentes quantidades de GPUs.
O ponto central do NVIDIA cuOpt mPDLP não é simplesmente usar mais hardware. A novidade está em organizar o problema para que as GPUs trabalhem de forma coordenada, reduzindo transferências desnecessárias. Se essa estratégia continuar evoluindo, modelos de otimização que antes ficavam limitados pelo tempo ou pela memória poderão entrar no intervalo prático de decisões empresariais e de planejamento energético.
