Apresentação no HN: multiplicação de matrizes com metade do número de multiplicações

Nova arquitetura de hardware para machine learning

• Este repositório contém o código-fonte de uma arquitetura de hardware de ML que alcança o mesmo desempenho das operações tradicionais de produto interno (inner product), exigindo quase metade das operações de multiplicação.
• Ele aumenta os limites teóricos de throughput e eficiência computacional de aceleradores de ML ao executar um algoritmo alternativo de produto interno que substitui quase metade das multiplicações por somas de baixa largura de bits (low-bitwidth).
• Mais detalhes podem ser encontrados no artigo publicado na revista IEEE Transactions on Computers.

Novo algoritmo e arquitetura de hardware

• Apresenta um novo algoritmo e arquitetura de hardware chamados Free-pipeline Fast Inner Product (FFIP).
• Melhora o algoritmo Fast Inner Product (FIP), proposto por Winograd em 1968.
• O FIP não tem relação com o algoritmo de filtragem mínima de Winograd aplicado a camadas convolucionais (convolutional) e pode ser aplicado a qualquer camada de modelos de ML que possa ser majoritariamente decomposta em multiplicação de matrizes.
• Implementa o FIP pela primeira vez em um acelerador de ML e apresenta o algoritmo FFIP e uma arquitetura generalizada que melhoram a frequência de clock do FIP e, consequentemente, seu throughput.
• Traz otimizações específicas para ML nos algoritmos e arquiteturas FIP e FFIP.
• O FFIP pode ser integrado de forma transparente a aceleradores de ML com systolic array de ponto fixo (fixed-point), alcançando o mesmo throughput com metade das unidades de multiplicação-acumulação (MAC) ou permitindo implementar um tamanho máximo maior de systolic array com um orçamento de hardware fixo.
• Uma implementação de FFIP para modelos de ML não esparsos (non-sparse) com entradas de ponto fixo de 8 a 16 bits atinge throughput e eficiência computacional superiores aos das melhores soluções da mesma categoria de plataforma computacional.

Estrutura do código-fonte

• compiler: inclui um compilador que converte descrições de modelos em Python em comandos para o acelerador, além do código de interface com o driver PCIe que inicia a execução do modelo no acelerador, lê resultados e contadores de desempenho e testa a precisão dos resultados.
• rtl: inclui RTL sintetizável em SystemVerilog.
• sim: inclui scripts para configurar o ambiente de simulação para testes.
• tests: inclui o código-fonte de um testbench baseado em UVM que valida o acelerador em simulação usando Cocotb.
• utils: inclui pacotes e scripts adicionais em Python usados no projeto, criados pelo autor para utilitários gerais de desenvolvimento e suporte.

Opinião do GN⁺

• Este artigo apresenta um avanço inovador em arquiteturas de hardware para ML, explicando especialmente um novo algoritmo e arquitetura que reduzem operações de multiplicação sem perder desempenho. Trata-se de um progresso importante que pode melhorar significativamente a eficiência das operações de ML.
• O algoritmo FFIP adiciona uma nova dimensão ao design de aceleradores de ML existentes, oferecendo uma forma de usar recursos de hardware com mais eficiência. Isso é muito importante no ambiente computacional moderno, que valoriza eficiência energética e de custos.
• No entanto, para que essa tecnologia seja amplamente adotada, é preciso considerar sua compatibilidade com aceleradores de ML existentes, o nível de compreensão dos desenvolvedores sobre a nova arquitetura e questões de desempenho e custo na implementação em hardware real.
• Outros projetos ou produtos com funções semelhantes incluem o TPU (Tensor Processing Unit) do Google e os núcleos CUDA da NVIDIA, que já são soluções de aceleradores de ML validadas pelo mercado.
• Ao adotar uma nova tecnologia ou open source, é preciso considerar a compatibilidade com sistemas existentes, o aumento de custo em relação ao ganho de desempenho e a complexidade de desenvolvimento e manutenção. As vantagens de escolher o FFIP podem ser o aumento de throughput e eficiência computacional, enquanto possíveis desvantagens incluem a curva de aprendizado dos desenvolvedores para o novo sistema e o custo inicial de implementação.

[GN⁺]

Comentários do Hacker News

• Essa técnica parece interessante, mas fico me perguntando por que ela ainda não foi implementada em aceleradores: se é simplesmente um algoritmo esquecido ou se há custos e outros impactos na construção do acelerador.
• Este artigo fala sobre sintetizar pipelines de multiplicação de matrizes em hardware, o que pode ser útil em hardwares como FPGA ou ASIC. Em CPUs e GPUs, multiplicação e soma geralmente levam o mesmo tempo, mas as unidades de multiplicação ocupam mais transistores, então reduzir a complexidade do circuito pode aumentar a velocidade e a taxa de paralelismo, além de reduzir o consumo de energia e a complexidade de roteamento.
• Outra forma de eliminar multiplicações na multiplicação de matrizes é usar vários semirings. Por exemplo, o Tropical Semiring usa adição no lugar da multiplicação e mínimo (ou máximo) no lugar da adição. Isso ainda é multiplicação de matrizes, mas com as operações binárias substituídas. As pesquisas na área de Tropical Algebra são usadas em problemas de otimização e em estudos de otimização de redes neurais, e atualmente a área é ativa e rica.
• Usar o Log Semiring também é uma maneira eficiente de eliminar multiplicações. Quando é preciso multiplicar uma cadeia de probabilidades (por exemplo, em uma cadeia de Markov), os números ficam tão pequenos que ponto flutuante perde precisão. Ao escalar os números em log, a multiplicação vira adição, e a adição vira x + log1p(exp(y - x)).
• É surpreendente que esse método realmente funcione, porque decidir entre usar multiplicação e adição pode ser mais lento do que simplesmente usar multiplicação, especialmente quando uma grande quantidade de trabalho é feita em paralelo.
• É muito interessante que esse processo tenha sido inventado em 1968 e ainda não tenha sido usado para esse propósito até hoje.
• Tentei uma ideia parecida em 2018, mas desisti porque todas as minhas candidaturas ao doutorado foram rejeitadas. O conceito aqui tenta replicar a retropropagação com uma rede externa, argumentando que provavelmente é isso que o cérebro realmente faz.
• Se você tem interesse na teoria matemática dos algoritmos subcúbicos para multiplicação de matrizes, pode começar por aqui. Supõe-se que exista um número ( n ) tal que todas as matrizes ( n \times n ) possam ser multiplicadas em ( O(n^{2+j}) ) etapas (agora provado para ( 2+j = w = 2.3728596 ) ou ( j > 0.3728596 )).
• Este readme deixa muito a desejar ao explicar quais são as melhorias ou como reduz as multiplicações pela metade. Não fica claro qual é o tempo de execução em Big O, nem se isso altera os melhores limites conhecidos. O diagrama é confuso e não explica por que essa abordagem é rápida ou boa. Como resultado, dá até relutância de clicar no PDF. Para aumentar a credibilidade do projeto, seria bom oferecer uma explicação e ilustrações honestas e claras sobre o que realmente está acontecendo.