Fair and Square: Replacing One Real Multiplication with a Single Square and One Complex Multiplication with Three Squares When Performing Matrix Multiplication and Convolutions

Este artigo demonstra que é possível substituir multiplicações reais e complexas por operações de quadrado em multiplicações de matrizes e convoluções, resultando em reduções significativas de recursos de hardware e permitindo novas arquiteturas como arrays sistólicos e núcleos tensoriais baseados em quadrados.

O essencial

Imagine que você é um cozinheiro de elite tentando preparar milhões de pratos complexos (como pizzas, bolos e massas) ao mesmo tempo. No mundo da computação, esses "pratos" são cálculos matemáticos usados em Inteligência Artificial, processamento de imagens e reconhecimento de voz.

O problema é que a receita tradicional exige um ingrediente muito caro e pesado: a multiplicação. Pense na multiplicação como um "forno industrial" gigante. Ele faz o trabalho, mas ocupa muito espaço na cozinha (o chip do computador) e consome muita energia.

Este artigo, escrito por Vincenzo Liguori, propõe uma revolução na cozinha: e se pudéssemos substituir esse forno pesado por algo muito mais leve e barato, como um simples "forno de micro-ondas" (o quadrado)?

Aqui está a explicação simples de como isso funciona:

1. O Truque Matemático (A Mágica do Quadrado)

Normalmente, para multiplicar dois números, $A$ e $B$, você precisa de um multiplicador dedicado. Mas a matemática tem um segredo antigo:

$(A + B)^2 = A^2 + B^2 + 2 \times (A \times B)$

Se você rearranjar essa equação, descobre que pode encontrar o resultado da multiplicação ($A \times B$) apenas usando quadrados (elevar ao quadrado) e somas:

$A \times B = \frac{(A + B)^2 - A^2 - B^2}{2}$

A Analogia:
Imagine que você quer saber quanto custa comprar 3 maçãs e 4 laranjas juntos.

• Método Antigo: Você tem que ir à loja e perguntar o preço exato de "3 maçãs + 4 laranjas" (Multiplicação).
• Método Novo: Você calcula o preço de "7 frutas misturadas" ao quadrado, subtrai o preço de "3 maçãs ao quadrado" e "4 laranjas ao quadrado". O resultado é o mesmo, mas você só precisa de uma máquina que sabe "elevar ao quadrado", que é muito mais barata e pequena de construir.

2. Por que isso é um "Superpoder"?

O autor aponta um fato crucial de engenharia: um circuito de computador que faz "quadrados" (ex: $5 \times 5$) precisa de **metade do espaço** e consome **metade da energia** de um circuito que faz multiplicação completa (ex:$5 \times 7$).

Ao trocar multiplicações por quadrados, você está trocando um caminhão de carga por uma bicicleta elétrica para entregar a mesma encomenda. O resultado é o mesmo, mas o custo é muito menor.

3. Onde isso é aplicado?

O artigo mostra como aplicar essa ideia em três áreas principais:

• Multiplicação de Matrizes (O "Cérebro" da IA):
  Imagine que você tem duas listas gigantes de números que precisam ser cruzadas. O método tradicional exige bilhões de multiplicações. O novo método permite fazer isso usando quase a mesma quantidade de quadrados. Como os chips de IA (como os usados no seu celular ou no Google) fazem isso o tempo todo, economizar espaço aqui libera espaço para mais inteligência ou bateria que dura mais.

• Convoluções (O "Olho" da IA):
  Isso é usado para reconhecer rostos em fotos ou detectar objetos. É como passar um filtro sobre uma imagem. O autor mostra que, em vez de multiplicar cada pixel pelo filtro, podemos usar quadrados. Isso torna os filtros de imagem muito mais rápidos e eficientes.

• Números Complexos (O "Dificuldade Extra"):
  Às vezes, os números têm uma parte "real" e uma parte "imaginária" (como coordenadas em um mapa 3D).

  • Versão 1: O autor mostra que podemos fazer uma multiplicação complexa usando 4 quadrados.
  • Versão 2 (A mais genial): Ele descobre um jeito ainda mais inteligente de fazer isso usando apenas 3 quadrados. É como encontrar um atalho na estrada que economiza mais combustível.

4. Como isso funciona na prática? (Arquiteturas)

O artigo não é apenas teoria; ele desenha como seriam as "cozinhas" (chips) novas:

• Arrays Sistólicos: Imagine uma linha de montagem onde os ingredientes passam de uma estação para outra. Em vez de ter um multiplicador em cada estação, eles colocam um "quadrador".
• Tensor Cores: São os "super-cérebros" dos chips modernos de IA. O autor sugere redesenhar esses cérebros para usarem essa técnica de quadrados, tornando-os muito mais eficientes.

Resumo Final

Este paper é como um manual de "como fazer mais com menos". Ele diz: "Pare de usar o motor V8 pesado para dirigir na cidade. Use um motor híbrido inteligente que faz o mesmo trabalho, mas ocupa metade do espaço e gasta metade da gasolina."

Ao substituir multiplicações por quadrados, podemos criar computadores mais rápidos, que esquentam menos e duram mais, impulsionando o futuro da Inteligência Artificial de forma mais sustentável e barata.

Resumo técnico

Resumo Técnico: Fair and Square

1. O Problema

Operações como multiplicação de matrizes, convoluções e transformadas lineares são ubíquas e críticas em aplicações de Inteligência Artificial (IA), Processamento de Sinal Digital (DSP) e computação de alto desempenho. A implementação eficiente dessas operações é fundamental, pois elas consomem uma parcela significativa dos recursos de hardware (área de chip e energia).

O problema central abordado é o custo computacional e de hardware das multiplicações. Em circuitos digitais, um multiplicador de $n$ bits requer aproximadamente o dobro do número de portas lógicas (gate count) em comparação com um circuito de quadrado (squaring) de $n$ bits. Portanto, substituir multiplicações por operações de quadrado pode levar a reduções substanciais no uso de recursos e no consumo de energia.

2. Metodologia

O artigo propõe uma abordagem algébrica baseada na identidade fundamental:
$$ab = \frac{1}{2} \left( (a+b)^2 - a^2 - b^2 \right)$$
ou, alternativamente, usando a diferença:
$$-ab = \frac{1}{2} \left( (a-b)^2 - a^2 - b^2 \right)$$

A metodologia consiste em redefinir operações de multiplicação em termos de somas de quadrados. O processo geral envolve:

1. Substituição: Trocar cada produto $a \cdot b$ na equação original pela expressão envolvendo quadrados.
2. Pré-cálculo e Reutilização: Identificar termos que dependem apenas de um dos operandos (ex: $a^2$ ou $b^2$) e que podem ser pré-calculados ou reutilizados para múltiplas saídas, reduzindo o custo amortizado.
3. Correção de Escala: Como a identidade introduz um fator de $1/2$, os resultados finais das arquiteturas propostas requerem um simples deslocamento de bits à direita (divisão por 2) para obter o valor correto.

3. Principais Contribuições e Resultados

O artigo detalha a aplicação dessa técnica em diversas operações matemáticas e propõe arquiteturas de hardware específicas:

A. Multiplicação de Matrizes Reais

• Mecanismo: Substitui a multiplicação $a_{ik}b_{kj}$ por $\frac{1}{2}((a_{ik}+b_{kj})^2 - a_{ik}^2 - b_{kj}^2)$.
• Otimização: Os termos $a_{ik}^2$ e $b_{kj}^2$ são somas de quadrados de linhas e colunas, respectivamente. Eles podem ser calculados uma vez e reutilizados para todos os elementos da matriz de resultado.
• Resultado: Para matrizes de tamanho $M \times N$ e $N \times P$, o número total de operações de quadrado é $MNP + MN + NP$. A razão entre quadrados e multiplicações tende a 1 conforme $M$ e $P$ aumentam.
• Hardware: Propõe Arrays Systólicos e Tensor Cores onde os multiplicadores são substituídos por "acumuladores de multiplicação parcial" (Partial Multipliers) que realizam somas e quadrados.

B. Transformadas Lineares e Convoluções Reais

• A mesma lógica é aplicada a transformadas (ex: DCT, FFT real) e filtros FIR/IIR.
• Se os coeficientes (pesos) forem constantes, os termos de quadrado dos coeficientes podem ser pré-calculados.
• Resultado: Substitui $N$ multiplicadores por $N+1$ operações de quadrado por etapa de processamento.

C. Multiplicação de Matrizes Complexas (Abordagem com 4 Quadrados)

• Utiliza a expansão padrão de multiplicação complexa: $(a+jb)(c+js) = (ac-bs) + j(bc+as)$.
• Cada produto real ($ac$, $bs$, etc.) é convertido em quadrados.
• Resultado: Requer 4 operações de quadrado por multiplicação complexa (mais termos de correção reutilizáveis). A razão tende a 4 para matrizes grandes.

D. Multiplicação de Matrizes Complexas (Abordagem com 3 Quadrados)

• O autor refina a técnica usando uma identidade de 3 multiplicadores reais para números complexos (semelhante ao algoritmo de Gauss para multiplicação complexa), adaptada para quadrados.
• Mecanismo: Reescreve o produto complexo para compartilhar termos comuns entre as partes real e imaginária.
• Resultado: Reduz a necessidade para 3 operações de quadrado por multiplicação complexa. A razão tende a 3 para matrizes grandes.
• Hardware: Introduz o conceito de CPM3 (Complex Partial Multiplier com 3 quadrados), que pode substituir multiplicadores complexos em MACs (Multiply-Accumulate Units).

E. Convoluções Complexas e Transformadas

• As técnicas de 4 e 3 quadrados são estendidas para convoluções 2D e transformadas lineares complexas (como DFT complexa), mantendo a eficiência de recursos.

4. Arquiteturas de Hardware Propostas

O artigo descreve várias implementações em hardware para viabilizar essas ideias:

• Arrays Systólicos Baseados em Quadrados: Modificação de células de processamento (PEs) para substituir multiplicadores por somadores e circuitos de quadrado, com injeção de termos de correção ($S_a$, $S_b$) nas bordas do array.
• Tensor Cores Baseados em Quadrados: Adaptação de núcleos de tensor existentes (como os da NVIDIA) para inicializar acumuladores com os termos de correção e realizar "produtos parciais" via quadrados.
• Módulos de Convolução: Arquiteturas para filtros FIR e IIR que utilizam a técnica de quadrados para reduzir a área do chip.

5. Significado e Impacto

• Eficiência de Recursos: Dado que um circuito de quadrado de $n$ bits possui aproximadamente metade do número de portas lógicas de um multiplicador $n \times n$, a substituição resulta em economias massivas de área de silício e consumo de energia.
• Escalabilidade: A técnica é assintoticamente eficiente. Para matrizes grandes (comuns em IA moderna), o custo adicional de calcular os termos de correção torna-se negligenciável, aproximando a contagem de operações de quadrado de 1:1 (para reais) ou 3:1 (para complexos) em relação às multiplicações originais.
• Versatilidade: A abordagem transcende a implementação específica do circuito de quadrado, sendo aplicável inclusive a aproximações de quadrado, o que abre caminho para otimizações adicionais em hardware.
• Relevância para IA e DSP: Oferece uma nova via para acelerar operações fundamentais em redes neurais e processamento de sinais, potencialmente permitindo chips mais rápidos, menores e mais eficientes energeticamente.

Em conclusão, o artigo "Fair and Square" demonstra que, ao reestruturar algoritmos de multiplicação matricial e convolução para explorar a eficiência de circuitos de quadrado, é possível alcançar reduções drásticas na complexidade de hardware sem sacrificar a precisão numérica (exceto pela escala de 2, que é trivialmente corrigida).