Resumo Técnico: PackSELL – Um Formato de Matriz Esparsa para SpMV de Alta Performance e Agnóstico à Precisão

1. Problema e Motivação

A multiplicação matriz-vetor esparsa (SpMV) é um kernel fundamental em aplicações científicas e em métodos de subespaço de Krylov para resolver sistemas lineares. Com o avanço das unidades de aritmética de baixa precisão (como FP16 e formatos não-IEEE) e o aumento da lacuna entre a largura de banda de memória e a capacidade de computação em GPUs, a redução do movimento de dados tornou-se crítica para kernels limitados por memória.

Os desafios principais identificados pelos autores são:

• Limitação dos Formatos Atuais: A maioria dos kernels de SpMV de alta performance é projetada para formatos IEEE 754 clássicos (FP32, FP64) e assume alinhamento de dados em limites de bytes.
• Rigidez de Representação: Formatos personalizados existentes frequentemente exigem alinhamento de bytes ou tratam índices e valores separadamente, limitando a flexibilidade para usar formatos de baixa precisão não-IEEE (como inteiros de poucos bits ou floats personalizados) e impedindo a compressão conjunta eficiente.
• Ineficiência em Baixa Precisão: Embora técnicas de precisão mista sejam promissoras, a falta de formatos de matriz esparsa que suportem nativamente a compressão de índices e valores em um único bloco de dados impede a maximização da largura de banda de memória em GPUs.

2. Metodologia: O Formato PackSELL

O artigo propõe o PackSELL, um novo formato de matriz esparsa baseado no formato Sliced ELLPACK (SELL), projetado para suportar diversas representações de dados e reduzir o footprint de memória.

Principais Características Técnicas:

1. Codificação Delta de Índices:

   • Em vez de armazenar os índices das colunas absolutos, o PackSELL armazena a diferença (delta) entre o índice da coluna atual e o do elemento não nulo anterior na mesma linha.
   • Para matrizes com estrutura de banda (comum em ordenações Cuthill-McKee), esses deltas são pequenos, permitindo compressão significativa.

2. Empacotamento Delta-Valor (Delta-Value Packing):

   • Esta é a inovação central. Cada par de "delta de índice" e "valor não nulo" é empacotado em uma única palavra de $W$ bits (ex: 32 bits).
   • A palavra é dividida em:
     • $D$ bits: Para o delta (inteiro sem sinal).
     • $V$ bits: Para o valor da matriz (pode ser qualquer formato, IEEE ou não).
     • 1 bit de Flag: Para indicar se o valor está presente ou se o delta é muito grande.
   • Mecanismo de Flag:
     • Se o delta couber em $D$ bits, o flag é 1. O valor ocupa os $V$ bits superiores e o delta é deslocado.
     • Se o delta for muito grande (estourar $D$ bits), o flag é 0. Todos os bits restantes ($W-1$) são usados para armazenar o delta (tratando o valor como um elemento "dummy" ou nulo). Isso evita overflow sem aumentar o tamanho da palavra.

3. Flexibilidade de Precisão:

   • Ao ajustar a alocação de bits entre $D$ e $V$, o PackSELL suporta formatos personalizados. Por exemplo, pode-se usar um formato de ponto flutuante personalizado (como E8MY, com 8 bits de expoente e $Y$ bits de mantissa) que não segue o padrão IEEE 754, otimizando o equilíbrio entre faixa dinâmica e precisão para uma aplicação específica.

4. Alinhamento Estilo-SELL:

   • Mantém a estrutura de "fatias" (slices) de $C$ linhas para garantir carga de trabalho uniforme e acesso à memória coalescido em GPUs.
   • Utiliza permutação de linhas (explícita ou implícita) dentro de blocos de $\sigma$ linhas para minimizar o preenchimento (padding) e o número de elementos dummy.

5. Decodificação On-the-Fly:

   • O unpacking (desempacotamento) é realizado durante a execução do kernel SpMV usando operações de bit-shift e máscaras lógicas, evitando ramificações (branch-free), o que é crucial para o desempenho em arquiteturas SIMT de GPUs.

3. Contribuições Principais

• Novo Formato de Matriz: Proposta do PackSELL, que integra codificação de índices e valores em uma única estrutura de dados, permitindo representações de dados agnósticas à precisão.
• Análise de Desempenho: Avaliação abrangente de kernels SpMV e métodos de subespaço de Krylov usando PackSELL em GPUs NVIDIA A100.
• Demonstração de Cenários Não-IEEE: Identificação de casos onde representações não-IEEE (como E8MY) superam formatos padrão (FP16/BF16) em termos de equilíbrio entre precisão e desempenho, especialmente em solvers iterativos.

4. Resultados Experimentais

Os experimentos foram realizados em uma GPU NVIDIA A100 (80GB) utilizando uma coleção de 435 matrizes reais do SuiteSparse.

Desempenho em SpMV Isolado (FP16):

• O PackSELL (configurado com $W=32, D=15, V=16$ para FP16) superou o kernel baseado em SELL da biblioteca cuSPARSE em até 1,63x em 201 de 292 matrizes consideradas "adequadas para SELL" (padrões de esparsidade regulares).
• A melhoria deve-se à redução do footprint de memória (comprimindo índices e valores) e à melhoria nos padrões de acesso à memória (um único array para dados).
• Em matrizes com muitos elementos não nulos e baixa variância de não zeros por linha, o ganho foi consistente (~1,5x).

Desempenho com Formatos Não-IEEE:

• Ao variar a alocação de bits (ex: $D=1$ a $12$) e usar o formato E8MY, o PackSELL demonstrou que é possível atingir precisão nível FP32 com desempenho superior ao FP16 padrão.
• Para matrizes com grande faixa dinâmica, formatos com mais bits de expoente (mas menos de mantissa) evitaram underflow severo observado no FP16 padrão, mantendo a precisão.

Aplicação em Solvers Iterativos (Krylov):

• Solver F3R (FP16): A integração do PackSELL no solver F3R (que usa SpMV em FP16) resultou em um speedup global de até 1,32x em comparação com a versão baseada em SELL padrão, e até 2,64x em relação a um solver FP64 puro.
• Método Inner-Outer CG: Em um esquema de Conjugate Gradient com precisão mista (inner FP32/FP16 customizado, outer FP64), o uso de PackSELL com formato E8MY permitiu atingir precisão de FP32 com desempenho superior a FP16.
  • O solver baseado em PackSELL superou o solver PCG padrão em FP64 em até 2,09x.
  • Isso demonstra que a capacidade de ajustar finamente a mantissa e o expoente permite superar as limitações de convergência do FP16 puro e o custo de dados do FP32 puro.

5. Significado e Conclusão

O PackSELL representa um avanço significativo na otimização de kernels esparsos para GPUs, especialmente na era da computação de precisão mista.

• Quebra de Paradigma: O trabalho demonstra que tratar a representação de dados como uma variável de projeto conjunta com o layout de memória e a codificação de índices permite otimizações que formatos rígidos (como CSR ou SELL padrão) não conseguem alcançar.
• Viabilidade de Formatos Personalizados: O formato valida a utilidade prática de formatos de ponto flutuante não-IEEE em kernels de alta performance, oferecendo uma ferramenta para pesquisadores explorarem o espaço de design de precisão sem sacrificar o desempenho de memória.
• Impacto Futuro: O PackSELL fornece uma base para o desenvolvimento de solvers lineares esparsos mais avançados e eficientes, permitindo que algoritmos de precisão mista operem próximo ao limite teórico de desempenho (roofline) em hardware moderno, superando as limitações de formatos padrão como FP16 e BF16 em cenários específicos de aplicação.

Em resumo, o PackSELL não apenas acelera a multiplicação matriz-vetor, mas também habilita uma nova classe de algoritmos numéricos que podem adaptar sua representação de dados dinamicamente para maximizar a eficiência energética e computacional.