DuaLip-GPU Technical Report

Este relatório técnico apresenta uma reestruturação do solver DuaLip para execução em GPU, que desacopla a especificação do problema do motor de otimização e utiliza técnicas de paralelismo massivo para resolver programas lineares em larga escala, alcançando um aceleramento de 10 vezes em comparação com a versão anterior baseada em CPU.

O essencial

Imagine que você é o gerente de um grande parque de diversões (o LinkedIn) e precisa distribuir milhões de ingressos (oportunidades de conteúdo) para milhões de visitantes (usuários) todos os dias.

O problema é que você tem regras complexas:

1. Cada visitante só pode entrar em algumas atrações específicas.
2. Cada atração tem um limite de capacidade (não pode lotar).
3. Você quer garantir que os ingressos sejam distribuídos de forma justa e eficiente para todos.

Isso é um Programa Linear (LP): um quebra-cabeça matemático gigante para tomar a melhor decisão possível.

O artigo que você leu descreve como a equipe do LinkedIn reconstruiu o "motor" que resolve esse quebra-cabeça. Eles chamam de DuaLip-GPU. Aqui está a explicação simples, usando analogias do dia a dia:

1. O Problema do "Motor Antigo" (O Sistema Scala/Spark)

Antes, eles usavam um sistema antigo (feito em Scala/Spark) que funcionava como um caminhão de entrega lento e pesado.

• Era rígido: Se você quisesse mudar uma regra (ex: adicionar um limite de frequência de visitas), tinha que reescrever todo o manual do caminhão.
• Era lento: O caminhão usava apenas motores a gasolina (processadores de CPU comuns). Para problemas gigantes, ele demorava horas para entregar a carga.
• Não era flexível: Era difícil adaptar o caminhão para novas rotas sem contratar uma equipe inteira de mecânicos.

2. A Nova Solução: O "Fórmula 1" no Circuito (DuaLip-GPU)

Eles trocaram o caminhão por um carro de Fórmula 1 (o novo sistema Python com GPUs).

• Velocidade: O carro de F1 é 10 vezes mais rápido. O que levava horas agora leva minutos.
• Flexibilidade: O carro foi projetado para ser modular. Se você quiser mudar a rota, basta trocar o pneu ou o aerofólio (o código), sem precisar reconstruir o chassi inteiro.
• Potência: Eles usam GPUs (placas de vídeo). Pense nas GPUs como uma equipe de 100 corredores trabalhando juntos em sincronia, em vez de um único corredor fazendo tudo sozinho.

3. Como eles conseguiram essa velocidade? (As 3 Mágicas)

O artigo explica três truques principais que tornaram isso possível:

A. O "Kit de Ferramentas Universal" (Programação Orientada a Operadores)

No sistema antigo, o motor era feito de peças de madeira fixas. No novo, eles criaram um kit de ferramentas de Lego.

• Em vez de ter um "botão mágico" para resolver tudo, eles separaram o problema em três peças básicas:
  1. O Objetivo: O que queremos maximizar?
  2. As Regras Simples: O que cada visitante pode ou não fazer (ex: "só 1 ingresso por pessoa").
  3. O Algoritmo: O motor que empurra a solução para frente.
• Analogia: É como se você pudesse trocar o motor do carro sem precisar trocar as rodas ou o volante. Isso permite que os engenheiros criem novas regras de negócio rapidamente, apenas "conectando" novas peças de Lego.

B. O "Treinador de Corrida" (Melhorias no Algoritmo)

Mesmo com um carro rápido, se o piloto (o algoritmo) não souber dirigir, ele vai bater. Eles deram um "treinador" ao algoritmo com três técnicas:

1. Normalização (Ajuste de Marcha): Imagine que algumas pistas têm buracos enormes e outras são lisas. O algoritmo antigo tentava andar na mesma velocidade em todas. O novo sistema ajusta a velocidade (normalização) para que ele não bata nos buracos nem fique lento demais nas retas.
2. Aquecimento e Resfriamento (Continuação): No começo da corrida, o carro precisa de mais estabilidade (um "amortecedor" forte). Depois, para ganhar velocidade, o amortecedor é removido gradualmente. O sistema começa com uma versão "amortecida" do problema para encontrar o caminho rápido e depois afina para a precisão final.
3. Escala (Ajuste de Peso): Se um passageiro pesa 100kg e outro 50kg, o carro precisa ser balanceado. O novo sistema equilibra os pesos (escala) para que o carro não puxe para um lado só.

C. A "Corrida em Equipe" (Execução em GPU)

Aqui está a parte mais brilhante da engenharia.

• O Problema: Em um problema gigante, você não pode enviar todos os dados para uma única GPU, ou ela vai explodir (falta de memória).
• A Solução: Eles dividiram o problema como se fosse uma pizza gigante.
  • Cada GPU recebe um pedaço da pizza (uma parte dos dados).
  • Elas calculam suas fatias sozinhas (muito rápido).
  • No final de cada rodada, elas só trocam um bilhete pequeno entre si (os resultados parciais), em vez de trocar a pizza inteira.
• Analogia: Imagine 100 pessoas tentando montar um quebra-cabeça. Em vez de passarem todas as peças de um lado para o outro o tempo todo (o que seria lento), cada pessoa monta sua seção e só avisa as vizinhas: "Aqui está a borda da minha parte". Isso economiza tempo de comunicação e deixa todos trabalhando.

4. O Resultado Final

Com essa nova arquitetura:

• Velocidade: O sistema é 10 vezes mais rápido que o antigo.
• Precisão: Ele chega na mesma resposta correta que o sistema antigo (os números batem perfeitamente).
• Escalabilidade: Se o problema dobrar de tamanho, eles só precisam adicionar mais GPUs, e o tempo de resposta continua baixo.

Resumo em uma frase

O LinkedIn pegou um sistema de otimização antigo, lento e rígido, e o transformou em uma máquina moderna, flexível e ultra-rápida, capaz de rodar em placas de vídeo poderosas, permitindo que eles tomem decisões melhores e mais rápidas para milhões de usuários todos os dias.

Resumo técnico

Resumo Técnico: DuaLip-GPU – Um Solver de Programação Linear em GPU para Escala Extrema

1. O Problema

Muitos sistemas de decisão em grande escala na indústria (como ranqueamento, alocação e problemas de correspondência/matching) dependem da resolução recorrente de Programas Lineares (LPs). O sistema anterior da LinkedIn, chamado DuaLip, utilizava métodos de primeira ordem (ascensão dual regularizada por ridge) implementados em uma pilha Scala/Spark centrada em CPU.

As principais limitações desse sistema legado eram:

• Acoplamento Rígido: A interface estava presa a dois esquemas fixos (otimização multi-objetivo e matching em bloco único), dificultando a expressão de novas formulações ou restrições complexas.
• Ineficiência de Hardware: A arquitetura era centrada em CPU, não aproveitando o paralelismo massivo e a velocidade dos aceleradores modernos (GPUs).
• Escalabilidade: Dificuldade em lidar com problemas de escala extrema (centenas de milhões de variáveis) com baixa latência e alta precisão.

O objetivo deste trabalho foi re-arquitetar o solver para ser reutilizável, flexível e nativo para GPU, mantendo a capacidade de resolver LPs de escala extrema com restrições de correspondência (matching).

2. Metodologia e Arquitetura

A solução proposta, DuaLip-GPU, é uma biblioteca em Python (baseada em PyTorch) que co-designa três componentes principais:

A. Modelo de Programação Baseado em Operadores

Em vez de uma API declarativa rígida ("chamar o solver"), o sistema adota um modelo imperativo de nível de operador, inspirado no PyTorch ("define-by-run"). A lógica do problema é decomposta em três primitivas desacopladas:

1. Objetivos (objective/): Encapsula os dados e o cálculo do gradiente dual.
2. Projeções (projections/): Realiza projeções em blocos sobre politopos de restrições "simples" (ex: simplex, caixas).
3. Otimizador (optimizer/): Executa a ascensão dual usando o gradiente calculado.

Isso permite que novas formulações de LP sejam adicionadas localmente sem alterar o loop de resolução ou os diagnósticos.

B. Melhorias Algorítmicas na Ascensão Dual Regularizada

O sistema utiliza a formulação dual regularizada por ridge (introduzida por Basu et al. e ECLIPSE), mas introduz três melhorias críticas para estabilidade e convergência:

1. Normalização de Linhas (Pré-condicionamento Jacobi): As restrições complexas são reescaladas para melhorar o condicionamento da matriz Hessiana dual ($AA^T$), estabilizando os passos de gradiente.
2. Continuação de Regularização: O parâmetro de regularização ($\gamma$) começa alto para garantir estabilidade inicial e decai gradualmente conforme o algoritmo converge, equilibrando velocidade e fidelidade à solução do LP original.
3. Escala Primal: Introdução de fatores de escala nas coordenadas primais para lidar com variáveis de magnitudes muito diferentes, evitando que o termo regularizador domine ou se torne ineficaz.

C. Implementação em GPU e Layout Esparsos

Para explorar o hardware moderno, o sistema adota estratégias específicas:

• Layout de Tensor Esparsos (CSC): A matriz de restrições é armazenada em formato Compressed Sparse Column, ordenada por destino, explorando a estrutura de blocos diagonais típica de problemas de matching.
• Operadores de Projeção em Lote (Batching): Em vez de lançar kernels pequenos para cada coluna, as projeções são agrupadas em lotes densos (usando "buckets" logarítmicos) para amortizar o custo de lançamento de kernels e aumentar a ocupação da GPU.
• Comunicação Distribuída: Utiliza torch.distributed (NCCL). Apenas as variáveis duais ($\lambda$) e vetores de escalar são sincronizados entre as GPUs. A comunicação é independente do número de não-zeros na matriz, permitindo escalabilidade quase linear.

3. Principais Contribuições

1. Modelo de Programação Flexível: Substituição da interface baseada em esquemas rígidos por um modelo orientado a operadores, permitindo a composição local de novas famílias de restrições com esforço mínimo de código.
2. Otimizações Algorítmicas Robustas: Integração de pré-condicionamento Jacobi, escalonamento de regularização e escala primal, tornando o solver robusto para uma ampla gama de problemas de matching sem necessidade de ajuste fino de hiperparâmetros por instância.
3. Aceleração em GPU para Escala Extrema: Demonstração de como realizar paralelismo massivo em GPUs para LPs estruturados, alcançando ganhos de ordem de magnitude em tempo de execução comparado a soluções distribuídas em CPU.

4. Resultados Experimentais

Os experimentos foram realizados em dados sintéticos de matching (de 25M a 100M de fontes/origens) e comparados com a implementação original em Scala/Spark.

• Paridade Numérica: A implementação em PyTorch reproduz com precisão a dinâmica de otimização do sistema Scala, com erro relativo abaixo de 1% nas primeiras 100 iterações.
• Desempenho de Tempo:
  • Para problemas moderados (25M de fontes), uma única GPU é ~10x mais rápida que a implementação distribuída em CPU (Scala).
  • Para problemas maiores (100M de fontes), o uso de múltiplas GPUs (sharding) mantém a aceleração, com ganhos superiores a 10x em relação ao sistema legado.
• Escalabilidade: O sistema exibe escalabilidade quase linear ao adicionar GPUs (ex: 3,86x de aceleração em 4 GPUs, próximo ao ideal de 4x).
• Impacto das Melhorias: O pré-condicionamento acelerou significativamente a convergência inicial, e a estratégia de decaimento de $\gamma$ garantiu que a solução final fosse de alta qualidade, aproximando-se do ótimo do LP não regularizado.

5. Significado e Conclusão

O DuaLip-GPU representa uma evolução significativa na resolução de problemas de otimização em escala industrial. Ao transformar um solver especializado e acoplado a CPU em uma arquitetura flexível e nativa para GPU, o trabalho permite:

• Agilidade: Novas formulações de problemas de alocação e matching podem ser implementadas e testadas rapidamente.
• Eficiência: Redução drástica no tempo de resolução (wall-clock time), permitindo ciclos de decisão mais frequentes e reativos.
• Futuro: A arquitetura serve como base para resolver não apenas problemas de matching, mas uma classe mais ampla de LPs com restrições decomponíveis, superando as limitações de solvers genéricos que não exploram a estrutura específica dos dados industriais.

Este relatório estabelece um novo padrão para a implementação de solvers de primeira ordem em ambientes de produção modernos, combinando teoria de otimização robusta com engenharia de sistemas de alto desempenho.