Resumo Técnico: AI-PROPELLER

Declaração do Problema

Otimizadores de pós-linkagem (PLOs) como o Propeller e o BOLT melhoraram com sucesso o desempenho de aplicações de larga escala em armazéns através de um layout de código intraprocedural guiado por perfil de forma precisa. Essas ferramentas reordenam blocos básicos dentro de funções e dividem regiões de código quente/frio para otimizar a utilização do cache de instruções e do TLB. No entanto, elas deixam amplamente inexplorado o layout de código interprocedural.

O layout interprocedural — reordenar blocos básicos através de fronteiras de funções — é historicamente difícil devido a:

1. Explosão Combinatória: O espaço de busca é vários ordens de magnitude maior do que a exploração intraprocedural (por exemplo, uma aplicação de escala de armazém pode ter ~1,4 milhão de funções e ~40 milhões de blocos básicos).
2. Semântica Complexa: Diferente do layout intraprocedural, onde saltos de continuidade (fall-through) podem ser eliminados, o layout interprocedural deve aderir estritamente às semânticas de chamada-retorno (call-return). Posicionar blocos de diferentes funções adjacentes não elimina a contagem dinâmica de instruções da mesma forma, tornando a modelagem de custo complexa.
3. Falta de Valor Comprovado: Tentativas anteriores de layout interprocedural resultaram em tempos de compilação longos (3x–10x) com ganhos de desempenho marginais ou não comprovados, levando a comunidade a tratar isso como "trabalho futuro".

Consequentemente, o potencial de desempenho de um layout interprocedural fino em configurações industriais de escala de armazém permanece não comprovado.

Metodologia

O artigo apresenta o AI-PROPELLER, um framework que utiliza o fluxo de trabalho de agente Magellan para evoluir heurísticas de compilador para o layout de código interprocedural.

1. O Framework Magellan

O AI-PROPELLER integra dois componentes para otimizar a política de layout de código do Propeller:

• AlphaEvolve (Agente de LLM): Evolui o código-fonte da heurística de layout (especificamente code_layout.cc). Ele recebe uma política inicial e um prompt, gerando edições de código inovadoras (adições, modificações, remoções) para melhorar a heurística.
• Vizier (Otimizador de Caixa Preta): Ajusta finamente os hiperparâmetros numéricos (flags do compilador) expostos pela política evoluída.

2. Sinal de Recompensa de Alta Fidelidade

Uma inovação crítica é a mudança de modelos de custo estáticos aproximados. Para garantir que o loop evolutivo receba um sinal de recompensa preciso e livre de ruído:

• Execução em Hardware: O sistema compila múltiplas variantes de layout e as executa em hardware real (sistemas Intel Skylake).
• Redução de Ruído: O ambiente é estritamente controlado (Turbo Boost, SMT e ASLR desativados; frequência da CPU travada em 75% do pico).
• Estabilidade Estatística: Cada binário é executado 10 vezes para garantir que a variância entre execuções seja inferior a 0,05%.
• Cálculo de Recompensa: A recompensa é derivada de contadores de desempenho reais (contagem de ciclos), calculada como $1 - (\text{ciclos} / \text{referência})$.

3. A Política Evoluída

O framework evolui uma política que governa três fatores principais do reordenamento interprocedural:

1. Limiar de Divisão de Cadeia (Chain Split Threshold): Determina quando dividir sequências de blocos básicos. O AI-PROPELLER aumentou este limiar (de 0 para 213), permitindo que mais sequências fossem divididas e reinseridas entre funções.
2. Offsets de Memória (Frente/Trás): Define a distância máxima entre blocos para que uma aresta seja considerada lucrativa. A política evoluída expandiu esses limites significativamente (ex: de 1024 para 3059 bytes à frente) para capturar relações chamador-chamado de longo alcance.
3. Lógica de Ordenação Global: Substituiu a ordenação de ID de bloco específica de função por um índice de layout global para garantir que o binário final preserve a ordem interprocedural pretendida.

Principais Contribuições

1. Primeira Demonstração de Ganhos Interprocedurais: Este é o primeiro estudo a demonstrar melhorias claras de desempenho usando layout de código interprocedural fino em binários reais de escala de armazém.
2. Otimização Escalável: O framework otimiza aplicações de escala industrial (ex: LLVM Clang, Search) sem degradação perceptível no tempo de compilação ou uso de memória, superando a barreira histórica de engenharia da otimização interprocedural.
3. Descoberta de Heurísticas Inovadoras: O sistema descobriu autonomamente políticas de layout não intuitivas que superam heurísticas estáticas de estado da arte (Ext-TSP) e reordenamento ao nível de função (CDSort).

Resultados Experimentais

O framework foi avaliado em cargas de trabalho limitadas pelo frontend (LLVM Clang, LevelDB, Redis e uma aplicação de Search proprietária de escala de armazém).

• Melhorias de Desempenho:

  • LLVM Clang: Alcançou uma redução de 1,6% no tempo de execução sobre o baseline (FDO + ThinLTO + Ext-TSP). Isso representa extrair cerca de ~20% de desempenho adicional de um binário já altamente otimizado.
  • Warehouse-Scale Search: Alcançou uma melhoria de 0,23% sobre o baseline de implementação do Ext-TSP. Embora pareça pequena, os autores observam que isso é significativo para custos operacionais nesta escala.
  • Outros Benchmarks: LevelDB e Redis também mostraram melhorias estatisticamente significativas (p-valor ~0).

• Impacto Microarquitetural:

  • Stalls de Frontend: O AI-PROPELLER reduziu significativamente os stalls de frontend (atrasos de busca/decodificação de instrução). Por exemplo, no Clang, os stalls caíram de 45% para 39%; no Redis, de 49% para 34,2%.
  • Retiro de Instruções (Instruction Retirement): Melhorou a porcentagem de slots do pipeline da CPU gastos retirando instruções (trabalho útil), ex: o Clang melhorou de 27% para 30%.

• Estudo de Ablação (Inter vs. Intra):

  • Quando as transformações interprocedurais foram desativadas (forçando os blocos a permanecerem contíguos dentro das funções), o ganho de desempenho caiu de 1,6% para ~0,3%.
  • Isso indica que aproximadamente 80% do ganho de velocidade deriva especificamente da capacidade de intercalar blocos entre as fronteiras das funções, confirmando que o reordenamento interprocedural global é o principal motor do sucesso.

Significância e Alegações

O artigo afirma que o AI-PROPELLER é o primeiro framework a aplicar com sucesso o layout de código interprocedural fino a grandes binários em ambientes industriais. Sua significância reside em:

• Validar o Potencial: Provar que o potencial "não explorado" do layout interprocedural é real e mensurável, mesmo em ambientes hiper-otimizados.
• Superar o Espaço de Busca: Demonstrar que fluxos de trabalho de agentes baseados em IA podem navegar no espaço de busca exponencialmente maior do layout interprocedural, onde a sintonia manual e as heurísticas estáticas falham.
• Praticidade: Mostrar que essas otimizações podem ser alcançadas sem comprometer a escalabilidade de sistemas de compilação distribuídos, tornando-as viáveis para uso em produção.

Os autores enfatizam que, embora as porcentagens de ganho (0,23%–1,6%) possam parecer modestas, elas são operacionalmente significativas para aplicações de escala de armazém, onde melhorias marginais se traduzem em valor de negócio substancial, e são excepcionalmente difíceis de alcançar dado o estado da arte atual de técnicas de otimização.