GOMA: Geometrically Optimal Mapping via Analytical Modeling for Spatial Accelerators

O artigo apresenta o GOMA, um framework de mapeamento globalmente ótimo para multiplicação de matrizes em aceleradores espaciais que utiliza modelagem analítica e abstração geométrica para resolver o problema de busca de mapeamento de forma eficiente, garantindo otimidade e superando significativamente as soluções atuais em termos de eficiência energética e tempo de execução.

O essencial

Imagine que você é o gerente de uma fábrica gigante e super moderna (o Acelerador Espacial) que precisa produzir milhões de peças complexas (os cálculos de Inteligência Artificial). O seu trabalho é decidir exatamente como organizar os trabalhadores, as máquinas e o fluxo de materiais para que tudo saia o mais rápido possível e gastando o mínimo de energia.

Se você organizar mal, os trabalhadores ficam parados esperando material, as máquinas esquentam demais e a conta de luz explode. Se organizar bem, a fábrica voa.

O problema é que existem trilhões de formas diferentes de organizar essa fábrica. Tentar testar todas uma por uma levaria anos. Métodos antigos tentavam "adivinhar" ou testar aleatoriamente, mas muitas vezes falhavam em encontrar a melhor solução ou levavam muito tempo.

Aqui entra o GOMA, a nova "super-ferramenta" criada pelos autores deste artigo. Vamos entender como ela funciona com algumas analogias simples:

1. O Problema: O Labirinto de Trilhões de Caminhos

Pense no espaço de mapeamento (todas as formas de organizar a fábrica) como um labirinto gigante.

• Métodos antigos: Eram como alguém tentando achar a saída do labirinto andando de um lado para o outro, chutando caminhos. Às vezes, eles achavam uma saída rápida, mas raramente a melhor saída possível. E se o labirinto fosse enorme (como em modelos de IA modernos), eles ficavam presos ou demoravam uma eternidade.
• O desafio: Encontrar o caminho perfeito (o "Global Optimum") em tempo recorde.

2. A Solução do GOMA: O Mapa Geométrico Perfeito

O GOMA não chuta. Ele usa uma "lente mágica" chamada Abstração Geométrica.

• A Analogia da Sombra: Imagine que o cálculo da IA é um cubo de gelo 3D gigante. O GOMA olha para esse cubo e projeta suas "sombras" em três paredes (frente, lado e topo).
• Em vez de contar cada gota de água que derrete (cada cálculo individual), o GOMA conta apenas o tamanho dessas sombras e como elas mudam quando você move o cubo.
• Isso permite que ele calcule o custo de energia de qualquer organização em um piscar de olhos (matematicamente, é uma conta instantânea, O(1)), sem precisar simular toda a fábrica.

3. O "Pulo do Gato": O Caminho de Pedras (Level Bypass)

Na fábrica, às vezes é melhor não parar em um depósito intermediário.

• Imagine que você precisa levar um pacote do armazém principal (DRAM) até a linha de montagem (MACC).
• O GOMA decide: "E se pularmos o depósito do meio (SRAM) e mandarmos direto para a linha?" ou "E se guardarmos aqui para reutilizar depois?".
• O GOMA calcula matematicamente qual caminho (parar ou pular) economiza mais energia e tempo, ajustando isso automaticamente para cada tipo de dado.

4. A Busca pelo Perfeito: O Detetive Matemático

Depois de ter esse mapa geométrico perfeito e a fórmula de energia instantânea, o GOMA transforma o problema em um quebra-cabeça matemático.

• Ele usa um "detetive" (um solucionador de otimização) que prova matematicamente que a solução encontrada é a melhor de todas as possibilidades.
• Diferente dos outros métodos que dizem "acho que é essa", o GOMA entrega um certificado de garantia: "Esta é a solução ótima, ponto final".

5. Os Resultados: O Que Acontece na Prática?

Os autores testaram o GOMA em vários cenários, desde celulares (Edge) até supercomputadores de IA (Data Centers), usando modelos famosos como o Llama e o Qwen.

• Eficiência: O GOMA economizou entre 2,2 a 4,2 vezes mais energia (ou melhorou a relação entre energia e tempo) do que as melhores ferramentas atuais. É como se você fizesse o mesmo trabalho com a bateria de um celular durando o dobro.
• Velocidade: Enquanto os outros métodos levavam horas para decidir como organizar a fábrica, o GOMA fazia isso em segundos. Em alguns casos, foi 73 vezes mais rápido para encontrar a solução.

Resumo em Uma Frase

O GOMA é como ter um arquiteto genial que, em vez de construir maquetes e testar uma por uma, usa uma fórmula matemática inteligente para desenhar instantaneamente o projeto de fábrica perfeito, garantindo que seja o mais rápido e econômico possível, e provando que não existe nenhum projeto melhor.

Isso é crucial para o futuro, pois à medida que a Inteligência Artificial cresce, precisamos de formas de rodá-la sem gastar uma fortuna em energia e tempo. O GOMA oferece essa eficiência garantida.

Resumo técnico

Título: GOMA: Mapeamento Geometricamente Ótimo via Modelagem Analítica para Aceleradores Espaciais

1. O Problema

A multiplicação de matrizes gerais (GEMM) é a operação dominante em modelos de aprendizado profundo modernos, como Transformers e LLMs (Large Language Models). Em aceleradores espaciais (hardware dedicado para IA), a eficiência de execução e o consumo de energia dependem criticamente da escolha do mapeamento (mapping).

O mapeamento define estratégias como:

• Tiling (Blocagem): Como dividir os dados entre os níveis de memória (DRAM, SRAM, Registradores, PE).
• Permutação de Loops: A ordem de iteração para maximizar a reutilização de dados.
• Bypass de Níveis: Decidir se os dados devem residir em um nível de memória ou "pular" (bypass) para evitar leituras/escritas desnecessárias.

Desafios Principais:

• Explosão Combinatória: O espaço de mapeamento cresce exponencialmente (ex: > $10^{10}$ para GEMM), tornando a busca exaustiva computacionalmente inviável.
• Limitações das Abordagens Atuais:
  • Busca Heurística/Estocástica: (Ex: Timeloop, LOMA) Não garantem otimalidade global e podem ficar presas em ótimos locais.
  • Aproximação Diferenciável: Relaxa restrições inteiras, introduzindo erros de aproximação e exigindo correções que degradam a solução.
  • Programação Matemática Existente: (Ex: CoSA) Frequentemente falha em modelar com precisão os custos reais de hardware ou sofre de redundância na representação do espaço de busca, tornando a solução lenta.

O objetivo é encontrar um mapeamento globalmente ótimo (garantido matematicamente) dentro de um tempo de execução aceitável.

---

2. Metodologia: A Abordagem GOMA

O GOMA propõe um framework que transforma o problema de mapeamento em um problema de otimização inteira resolvido globalmente, utilizando uma abstração geométrica e modelagem analítica exata.

A. Abstração Geométrica (A Intuição)

O GOMA representa a computação GEMM como uma grade de computação 3D ($x, y, z$), onde cada ponto é uma operação MAC (Multiply-Accumulate).

• Projeções: As matrizes de entrada ($A, B$) e saída ($P$) são vistas como projeções ortogonais dessa grade 3D nos planos $x-z$, $y-z$ e $x-y$.
• Eixo de Caminhada (Walking Axis): A ordem dos loops (permutação) determina qual dimensão avança. Quando um bloco avança em um eixo, uma das projeções permanece inalterada (permitindo reutilização temporal), enquanto as outras duas são atualizadas.
• Contagem Analítica: O tráfego de dados é calculado contando quantas vezes essas projeções são atualizadas durante a travessia da grade. Isso permite derivar uma fórmula fechada para o volume de dados.

B. Modelagem de Energia Analítica ($O(1)$)

Diferente de simuladores que iteram passo a passo, o GOMA deriva uma função objetivo analítica exata para a energia:

• Custo Unitário: Multiplica o número de atualizações de projeção (tráfego) pelo custo de energia por palavra (leitura/escrita) de cada nível de memória.
• Mecanismo de Bypass: O modelo trata o "bypass" (pular níveis de memória) de forma centrada no receptor. Se um nível é pulado, o custo de acesso é zero, mas a origem do dado muda para um nível superior, alterando o custo de transferência.
• Complexidade Constante: A avaliação de energia para qualquer configuração de mapeamento é feita em tempo constante $O(1)$, independentemente do tamanho do problema.

C. Formulação de Otimização

O problema é formulado como um Programa Inteiro Linear (ILP):

• Variáveis de Decisão: Tamanhos de blocos (tiling) em cada nível, eixos de caminhada (permutação) e políticas de bypass.
• Restrições: Capacidade de memória (SRAM/Registradores), número de PEs (Processadores), e restrições de divisibilidade (os blocos devem caber perfeitamente).
• Objetivo: Minimizar a energia total (ou EDP - Energy-Delay Product).
• Solução: Utiliza um solver global (Gurobi com Branch-and-Bound) para encontrar a solução ótima global e gerar um certificado de otimalidade (gap de otimalidade = 0%).

---

3. Principais Contribuições

1. Abstração Geométrica Unificada: Introduz uma nova visão de grade de computação 3D que unifica tiling, permutação e bypass, resultando em um modelo de energia analítico exato com avaliação $O(1)$ e consistência de 99,9% com o modelo de referência Timeloop.
2. Formulação de Otimização Global: Transforma a busca de mapeamento em um problema de otimização inteira sob restrições de hardware, permitindo a automação da busca sem heurísticas.
3. Garantia de Otimalidade: Pela primeira vez no campo de exploração de espaço de mapeamento, o GOMA computa um mapeamento globalmente ótimo para qualquer par (carga de trabalho GEMM, hardware) em segundos, fornecendo um certificado verificável de que não existe solução melhor dentro do modelo.
4. Código Aberto: O framework foi disponibilizado publicamente no GitHub.

---

4. Resultados Experimentais

Os autores avaliaram o GOMA em 24 cenários combinando 4 templates de aceleradores (Edge: Eyeriss-like, Gemmini-like; Center: A100-like, TPU v1-like) e cargas de trabalho de LLMs (Qwen e LLaMA) com diferentes tamanhos de sequência.

• Eficiência (EDP - Energy-Delay Product):

  • O GOMA superou consistentemente os métodos mais avançados (SOTA) como CoSA, FactorFlow, LOMA, SALSA e Timeloop Hybrid.
  • Melhoria: Redução de 2,24x a 4,24x no EDP em comparação com os melhores mapeadores existentes.
  • A vantagem é mais pronunciada em cargas de trabalho grandes e matrizes complexas, onde métodos heurísticos falham em encontrar soluções de alta qualidade.

• Velocidade de Solução (Time-to-Solution):

  • O GOMA é drasticamente mais rápido na fase de busca/otimização.
  • Aceleração: Redução de 3,83x a 73,6x no tempo de execução da busca de mapeamento.
  • Enquanto outros métodos levam minutos ou horas para grandes cargas, o GOMA encontra a solução ótima em segundos (média de 0,65s por GEMM).

• Estabilidade:

  • Métodos heurísticos mostraram instabilidade significativa em grandes espaços de busca (EDP normalizado variando em ordens de magnitude).
  • O GOMA manteve desempenho consistente e ótimo em todos os casos.

---

5. Significado e Impacto

O GOMA representa um avanço fundamental no co-design hardware-software para aceleradores espaciais:

• Fim do Compromisso (Trade-off) entre Qualidade e Tempo: Demonstra que é possível obter a melhor solução possível (globalmente ótima) sem sacrificar o tempo de busca, algo que era considerado impossível devido à complexidade combinatória.
• Modelagem Precisa: A capacidade de modelar custos de hardware complexos (incluindo bypass e hierarquia de memória) de forma analítica e exata valida a abordagem de "primeiros princípios" (first principles) em vez de simulação ou aproximação.
• Escalabilidade: A abordagem é robusta para o crescimento de modelos de IA (de edge a data centers) e para arquiteturas de hardware futuras, oferecendo uma base reutilizável para exploração de mapeamento multicamadas e co-otimização.

Em resumo, o GOMA resolve o problema de "como encontrar a melhor configuração de hardware para um algoritmo" de forma matemática, rápida e garantida, eliminando a necessidade de buscas heurísticas incertas.