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

 (github.com/trevorpogue)
3 pontos por GN⁺ 2024-03-17 | 1 comentários | Compartilhar no WhatsApp
  • Este repositório contém o código-fonte para validar uma arquitetura de systolic array para GEMM e aceleradores de hardware de deep learning que calcula o mesmo resultado de multiplicação de matrizes com menos recursos de hardware ou menos tempo de execução
  • A abordagem proposta substitui parte das multiplicações de matrizes por adições de baixa largura de bits mais baratas, com o objetivo de reduzir pela metade o número de multipliers necessários para o mesmo desempenho ou aumentar o desempenho por unidade MAC
  • Os resultados alcançam até 3× de aceleração na inferência de CNN, mais de 2× de throughput de multiplicação por multiplier/clock em relação a aceleradores de ponta em plataformas de computação similares, além de menor área e maior frequência de clock
  • O escopo de aplicação inclui dense matrix multiplication e as camadas que mais a utilizam, como fully-connected layer, CNN, RNN e attention layer/transformer model, gerando a mesma saída das abordagens existentes principalmente em inferência quantizada e de ponto fixo
  • A arquitetura foi projetada para manter a mesma funcionalidade e interface de systolic arrays existentes, permitindo integração por substituição da MXU em sistemas aceleradores já existentes sem pré-processamento ou pós-processamento adicional

Objetivo e resultados do projeto

  • Algebraic Enhancements for GEMM & AI Accelerators reúne código-fonte para sistemas de GEMM e aceleradores de hardware de deep learning
  • O sistema é usado para validar arquiteturas de systolic array que implementam em hardware algoritmos eficientes de multiplicação de matrizes que foram propostos ou ainda não foram suficientemente explorados
  • O objetivo é calcular a mesma saída com menos recursos de hardware ou em menos tempo de execução
  • O desempenho apresentado inclui:
    • Inferência de CNN até 3× mais rápida em comparação com aceleradores de ponta implementados no mesmo tipo de plataforma de computação
    • Mais de 2× em mults/multiplier/clock cycle, superando o limite convencional de 1
    • Menor área e maior frequência de clock

Arquiteturas validadas em artigos e tese de doutorado

Por que aumentar o desempenho por MAC·multiplier

  • A maior parte do trabalho computacional em modelos de deep learning geralmente pode ser mapeada para matrix multiplication, composta por uma sequência de operações de multiply-accumulate
  • Sem inovação algébrica adicional, o throughput de aceleradores de deep learning fica limitado ao número máximo de operações MAC que podem ser executadas por clock cycle
  • Como aceleradores de deep learning incluem muitas MAC units, multipliers e MAC units tendem a ocupar grande parte da área de hardware em aceleradores GEMM e de deep learning
  • O throughput do acelerador pode ser diretamente limitado pelo número de multipliers que o orçamento de hardware consegue comportar
    • Em implementações em FPGA, as DSP units usadas para instanciar MAC units podem se esgotar antes de LUTs e registers
  • Este projeto explora formas de superar esse limite aplicando algebraic enhancement a algoritmos de matrix multiplication e implementações de hardware customizado

Escopo de aplicação e restrições

  • A arquitetura de hardware systolic array proposta melhora a aceleração de dense matrix multiplication
  • Pode ser usada em modelos e camadas de DNN que são majoritariamente decompostos em matrix multiplication
    • fully-connected layer
    • CNN
    • RNN
    • attention layer e transformer model
  • A maior parte das contribuições foca em tipos de dados de ponto fixo e inferência de redes neurais quantizadas
    • Alguns conceitos de ponto fixo podem futuramente ser estendidos para floating point
    • Como usa tipos de dados de ponto fixo, os algoritmos e arquiteturas de hardware apresentados geram a mesma saída que algoritmos e arquiteturas existentes
    • Não há mudança na numerical stability
  • Os resultados foram validados em FPGA, mas a arquitetura proposta é geral, e a maioria das melhorias pode ser aplicada tanto a implementações em custom integrated circuit quanto em FPGA
  • A arquitetura é baseada em systolic array
    • Um tipo de projeto eficiente usado em aceleradores GEMM e de deep learning como o Google TPU
    • Alguns conceitos podem futuramente ser estendidos para projetos non-systolic array
    • Mantém a mesma funcionalidade e interface de systolic arrays existentes
    • O algebraic enhancement é totalmente self-contained dentro do systolic array, sem necessidade de etapas adicionais de pré-processamento ou pós-processamento

Prévia dos resultados de desempenho

  • Os resultados de síntese e desempenho que combinam as arquiteturas de [1] e [3] alcançam o seguinte em comparação com aceleradores de ponta em plataformas de computação similares

Estrutura do sistema acelerador

  • O sistema acelerador de deep learning implementado no código-fonte é usado para hospedar e validar os systolic arrays propostos em [1]-[4]
  • A implementação do sistema é especializada em inferência com entradas quantizadas e de ponto fixo de non-sparse DNN model
    • convolutional layer
    • fully-connected layer
    • pooling layer
  • Todas as camadas de DNN são totalmente aceleradas em hardware
  • Um único projeto de hardware pode acelerar modelos de ML com arbitrary layer dimensions e kernel sizes
  • A largura de bits de entrada e a dimensão do systolic array podem ser configuradas por parâmetro
  • Também é altamente otimizado como um acelerador GEMM genérico

Blocos principais

  • Matrix Multiply Unit / MXU

    • Inclui a arquitetura de systolic array que executa a multiplicação de matrizes
    • Em cada método de [1]-[4], diferentes systolic arrays/MXUs propostos substituem a posição de MXU no sistema

  • GEMM Unit

    • Inclui MXU, SRAM e lógica de adição
    • Acumula matrix tiles para permitir a execução de GEMM em matrizes de tamanho arbitrário

  • Post-GEMM Unit

    • Executa funções específicas de redes neurais sobre a saída da matrix multiplication
    • Inclui adição de bias, inter-layer rescaling para quantization, activation, padding e pooling

  • Memory Unit

    • Inclui SRAM on-chip para armazenar ativações de camada e lógica de controle de acesso à memória
    • Implementa algoritmos eficientes de hardware para cache e acesso à memória que mapeiam convolution para GEMM in-place sem duplicação de dados nem atraso
    • Usa um esquema de particionamento de memória que executa a SRAM e seu controle em half ou quarter clock rate enquanto produz novos dados em full clock rate, melhorando a frequência e o consumo de energia do sistema como um todo

  • Off-chip DDR DRAM

    • Usada para armazenar weights

  • RxTx Unit

    • Responsável pela interface PCIe conectada ao host

  • Instruction Unit

    • Faz o decoding das instruções do acelerador enviadas pelo host
    • Permite que um único projeto de hardware acelere modelos de ML com arbitrary layer dimensions e kernel sizes

Organização do código-fonte

  • compiler
    • Compiler que converte descrições de modelos de ML em Python para instruções do acelerador
    • Inclui código que faz interface com o driver PCIe para iniciar a execução do modelo no acelerador, ler resultados e performance counters e testar a correção
  • rtl
    • RTL de acelerador em SystemVerilog sintetizável
  • sim
    • Scripts de configuração do ambiente de simulation para validação
  • tests
    • Código-fonte do testbench UVM escrito em Python e cocotb
  • utils
    • Pacotes Python adicionais usados no projeto e scripts utilitários para desenvolvimento
  • rtl/top/define.svh e rtl/top/pkg.sv
    • Incluem vários parâmetros configuráveis
    • FIP_METHOD define o tipo de systolic array, com exemplos como baseline, FIP, FFIP [1]
    • SZI e SZJ definem a altura e a largura do systolic array
    • LAYERIO_WIDTH e WEIGHT_WIDTH definem a largura de bits de entrada
  • rtl/arith
    • Inclui mxu.sv e mac_array.sv
    • Contém o RTL do baseline e de algumas das arquiteturas systolic array propostas, como FIP e FFIP [1], de acordo com o valor de FIP_METHOD

Documentação adicional

Leituras relacionadas

1 comentários

 
GN⁺ 2024-03-17
Opiniões no Hacker News

  • Parece bem legal, mas qual é a pegadinha? Por exemplo, fico me perguntando por que isso ainda não foi implementado em aceleradores
    Fico curioso se é realmente só um algoritmo esquecido ou se há alguma restrição que afete o custo de fabricação de aceleradores etc.

    • Não é um simples algoritmo de software, mas uma otimização de arquitetura de hardware
      Para obter ganhos, é preciso criar hardware que corresponda às dimensões do algoritmo, e isso é uma decisão cara
    • Para um acelerador de multiplicação de matrizes em ponto fixo, não há nenhuma pegadinha especial; acho que é apenas um algoritmo que passou despercebido
      Ele se baseia no algoritmo de Winograd e, por coincidência, Winograd também propôs depois um algoritmo separado que ficou muito famoso na aceleração de CNNs, então talvez este tenha recebido menos atenção. Mas isso é só especulação
    • Existem muitos algoritmos de multiplicação de matrizes, cada um com grandes prós e contras
      É sempre um equilíbrio entre precisão, tempo de execução e escalabilidade, e este método provavelmente tem baixa precisão em ponto flutuante
    • Não foi totalmente esquecido
      Ele sobrevive, em certa medida, dentro de autenticadores Wegman-Carter baseados em pseudoproduto interno, como o UMAC. Para o contexto, veja o capítulo 3 de [1]
      [1] https://cr.yp.to/antiforgery/pema-20071022.pdf
    • Dei só uma olhada por cima, então me corrijam se eu estiver errado, mas entendi que isso não é um substituto para a multiplicação de matrizes, e sim uma abordagem aproximada que produz resultados bastante bons para o tipo de sistema linear visto em IA/ML
      Para esse uso, parece suficientemente bom, não?

  • Isso me lembrou algo parecido que tentei fazer em 2018, mas abandonei depois de ser rejeitado em todos os programas de doutorado a que me candidatei
    https://github.com/ixaxaar/pytorch-dni
    O conceito aqui vai um passo além: tenta replicar a retropropagação com uma rede externa e argumenta que o cérebro talvez faça isso de fato

    • Não vejo bem a conexão
      Este trabalho é uma otimização de baixo nível da multiplicação de matrizes, enquanto o repositório linkado parece tentar substituir gradientes retropropagados por estimativas mais baratas. Fico curioso sobre qual seria a semelhança entre os dois
    • Isso parece uma situação próxima de não existe almoço grátis
      O tempo economizado ao aproximar os gradientes desse jeito não acabaria desaparecendo porque a perda de precisão dos gradientes exigiria mais iterações de treinamento? Ou não?
    • Deixando a discussão técnica de lado, fiquei curioso para saber com que ferramenta fizeram aquele GIF da arquitetura. Ficou bonito

  • Realmente interessante e vale a leitura. Para quem ficou confuso nos comentários sobre por que isso é melhor: o artigo trata da síntese de um pipeline de multiplicação de matrizes em hardware como FPGA ou ASIC.
    Em CPUs ou GPUs, os tempos de adição e multiplicação em geral são parecidos, então é difícil perceber a diferença, mas uma unidade de multiplicação ocupa muito mais transistores. Reduzir a complexidade do circuito pode aumentar a velocidade e o throughput paralelo, além de diminuir o consumo de energia e a complexidade do roteamento. Essa abordagem pode ser especialmente útil para aceleradores eficientes de multiplicação de matrizes esparsas.
    Outra forma interessante de eliminar multiplicações na multiplicação de matrizes é usar outro semianel (semiring) [1]. Por exemplo, o Tropical Semiring [2] substitui a multiplicação por adição, e a adição por min ou max. Continua sendo multiplicação de matrizes, mas com as operações binárias alteradas. A pesquisa em Tropical Algebra [3], uma área relativamente nova, está bastante ativa e rica no momento, e é usada em diversos problemas de otimização e em pesquisas de otimização de redes neurais [4].
    Essa abordagem também se encaixa bem em síntese de hardware, porque a maioria dos blocos lógicos configuráveis de FPGA consegue fazer add/min/max em um clock, enquanto uma multiplicação eficiente exige multiplicadores de hardware dedicados e fixos no chip.
    Outro semianel relacionado que remove multiplicações de forma eficiente é o Log Semiring [5]. Se você precisa multiplicar probabilidades em cadeia, como em cadeias de Markov, os números ficam muito pequenos rapidamente e a precisão de ponto flutuante se degrada. Se primeiro você aplica logaritmo para reescalar, a multiplicação vira adição, e a adição vira x + log1p(exp(y - x)).
    [1] https://en.wikipedia.org/wiki/Semiring
    [2] https://en.wikipedia.org/wiki/Tropical_semiring
    [3] https://en.wikipedia.org/wiki/Tropical_geometry
    [4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf
    [5] https://en.wikipedia.org/wiki/Log_semiring

    • O artigo de [4] é realmente fascinante.
      Sou praticamente iniciante nessa área, mas ele parece mostrar que quase toda rede ReLU pode ser expressa como uma razão tropical de dois polinômios tropicais e, portanto, analisada por princípios geométricos, como visualização de superfícies. Também é citado em pesquisas mais recentes: https://scholar.google.com/scholar?cites=1003719112553620451... Fico curioso para saber se houve algum avanço significativo nisso.
    • Uau, é exatamente disso que a Unified Algebra trata.
      http://www.cs.toronto.edu/~hehner/UA.pdf
    • A parte em que, ao aplicar logaritmo para reescalar os números, a multiplicação vira adição e a adição vira x + log1p(exp(y - x)): em um sistema numérico logarítmico, a adição/subtração é muito mais cara que a multiplicação.
      Especialmente se você se preocupa com resultados corretamente arredondados, as tabelas de lookup necessárias em hardware ficam bem grandes.
    • Transformar multiplicação em adição aplicando logaritmo não é a mesma abordagem usada há décadas em GF(2^x)?
      A única limitação que me vem à cabeça é o tamanho do corpo.
    • Algo relativamente relacionado é a transformada número-teórica.
      https://ieeexplore.ieee.org/abstract/document/1451721

  • É surpreendente que isso realmente funcione.
    Normalmente, o custo de detectar se deve usar multiplicação ou adição é maior do que simplesmente fazer a multiplicação. Isso é especialmente verdade quando se executa uma quantidade enorme de trabalho em paralelo.

    • Fico curioso para saber como isso se compara ao OpenBLAS e ao cuBLAS.

  • É interessante que um procedimento inventado em 1968 não tenha sido usado para esse fim até agora.

    • GF(2^x) também foi algo que ninguém sabia para que usar até meados do século passado.
      Ah, pensando bem, a própria ciência da computação quase não existia até meados do século passado.

  • Se você tem interesse na teoria matemática por trás dos algoritmos subcúbicos de multiplicação de matrizes, pode começar por aqui: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
    Conjectura-se que, para todo real j > 0, existe algum n tal que duas matrizes arbitrárias n x n podem ser multiplicadas em O(n^(2+j)) passos.
    Atualmente, isso foi provado para 2+j = w = 2.3728596, ou seja, para j > 0.3728596.

    • Não sei se essa formulação está correta.
      Se começa com “para todo j existe algum n”, então n e j se tornam constantes nas frases seguintes. Aí isso só quer dizer que matrizes de tamanho constante podem ser multiplicadas em tempo constante. Tecnicamente está correto, mas parece que a intenção era fazer uma afirmação mais forte.
    • Parece que, com o tempo, fica cada vez mais difícil avançar.
      Talvez o piso seja j=1/e. Eu nem chamaria isso de conjectura; é só uma constante conveniente perto do valor atual. Seria bem engraçado se a matemática nos pregasse uma peça dessas.
    • Prever que isso vale para qualquer j > 0 é bem ousado.
      Você poderia compartilhar a intuição de por que alguém pensaria isso?

  • Este README explica muito mal qual é a melhoria e como reduz as multiplicações pela metade
    Qual é o tempo de execução em Big O? Ele muda algum limite ótimo conhecido?
    As figuras também são confusas e quase não explicam por que essa abordagem é mais rápida ou melhor. Por isso fico sem vontade de clicar até no PDF
    Se quiserem aumentar a credibilidade do projeto, seria bom explicar de forma honesta e clara o que realmente está acontecendo e fornecer explicações e diagramas claros, em vez de imagens que parecem atrair as pessoas com hype. É difícil distinguir se isso é uma grande ruptura ou algo irrelevante. Infelizmente, também dá a impressão de ser uma escolha deliberada para aproveitar a febre de IA. A alternativa em que eu preferiria acreditar é que o autor simplesmente precisa revisar e fornecer melhor contexto

    • Sobre “qual é o tempo de execução em Big O?”, como a alegação é reduzir as multiplicações pela metade, isso não afeta o Big O
      A matemática que reduz pela metade o número de multiplicações no artigo (https://arxiv.org/abs/2311.12224) não é difícil de entender. Basta ler a equação 2, que é a multiplicação tradicional de matrizes, e as equações 3 a 6
      Parece claro que, em troca de reduzir as multiplicações pela metade como anunciado, muitas adições/subtrações são acrescentadas. Depois disso, eles vetorizam melhor o algoritmo, e, como costuma acontecer com esse tipo de trabalho, ele rapidamente fica complexo
      A principal preocupação é a estabilidade numérica
    • O README não explica muita coisa, mas a introdução do artigo em si é bastante acessível
      Quanto a ser revolucionário, eu diria que é uma melhoria limpa de fator constante, imediatamente aplicável a aceleradores de ponto fixo com restrição de área. Não vai mudar tudo da noite para o dia, mas também não é nada. É um bom trabalho
    • Não quero soar elitista, mas não entendo nada do ponto deste comentário
      Se você não entende a notação Big O a ponto de não saber que “reduzir as multiplicações pela metade” não muda o Big O, não sei por que está perguntando isso