Sobre o Projeto

Este repositório contém a evolução de um algoritmo de multiplicação de matrizes (GEMM - General Matrix Multiply), partindo de uma implementação ingênua $O(N^3)$ até atingir uma arquitetura altamente sintonizada. O projeto explora a hierarquia de caches, orquestração multinúcleo em arquiteturas NUMA e vetorização ao nível de hardware.

Este trabalho serve como prova de conceito e núcleo fundacional para implementação futura utilizando bloqueamento assimétrico, intrinsecas SIMD e algoritmo recursivo de strassen com o paradigma de tasks do OpenMP, foi extensivamente testado no supercomputador Santos Dumont.

Arquitetura e inspiração

A modelagem final do algoritmo (V9) tenta se aproximar dos conceitos estabelecidos por Kazushige Goto (2008) e pela arquitetura de instanciamento do projeto BLIS:

• Macro-Kernel: Particionamento simétrico via blocagem (Symmetric Block Tiling), garantindo que a matriz de maior reutilização permaneça retida na cache L1, enquanto fluxos controlados são enviados da cache L2. (Kazushige Goto (2008), utiliza bloqueamento assimétrico).
• Empacotamento de Dados (Data Packing): Cópia contígua de sub-blocos com alinhamento em 64 bytes (aligned_alloc), mitigando penalidades de conflict misses (esgotamento do TLB).
• Multithreading: Paralelização baseada em tarefas via #pragma omp taskloop, distribuindo dinamicamente a carga sobre o macro-kernel, entre as threads ativas, com grainsize ajustável.

Evolução das versões

O desenvolvimento foi escalonado iterativamente para quantificar o impacto de cada otimização:

• V0 - Sequencial Canônica (laços i-j-k).
• V1 - Uso de Acumulador Local em registrador.
• V2 - Transposição prévia da matriz B para acesso contíguo.
• V3 - Reordenação de laços (i-k-j) e Içamento Lógico (Hoisting).
• V4 - Blocagem de Cache Simétrica (Tiling).
• V5 - Empacotamento de Blocos com alinhamento de memória.
• V6 / V7 - Implementações base otimizadas + vetorização sugerida ao compilador e ajuste fino de limites de bloco.
• V8 / V9 - Orquestração em múltiplos níveis de laços via OpenMP taskloop.

Compilação e execução

Pré-requisitos

• Compilador GCC compatível com C11 ou superior e OpenMP 4.5+
• Processador com suporte a AVX2 ou AVX-512 (Intel Xeon recomendado para experimentação NUMA completa).

Compilação

Para compilar basta utilizaar o make para executar o Makefile.

    make

Executando com políticas NUMA

A configuração correta das variáveis de ambiente do OpenMP é vital para evitar migração de threads e garantir localidade de cache:

export OMP_NUM_THREADS=<número de threads>
export OMP_PLACES=cores
export OMP_PROC_BIND=close

make

./bin/V9 4096 1

./bin/V9 4096

OBS: Os argumentos representam o tamanho $N$ da matriz quadrada e o modo de execução: 0 ou nada para benchmark, 1 para geração das matrizes base, para teste realizar o teste de Norma de Frobenius.

Validação numérica

Todos os resultados paralelos são estritamente validados contra a versão paralela simples de V0 de referência utilizando a Norma de Frobenius, garantindo uma tolerância máxima de flutuação configurada para $\varepsilon = 1 \times 10^{-9}$ (precisão dupla).

Trabalhos futuros

• Reestruturação do Macro-Kernel: Desacoplar os limites dimensionais de blocagem simétrica em favor de recortes assimétricos estritos (Panelling e Micropanels).
• micro-kernel em intrinsecas: Implementação de micro-kernel em intrinsecas SIMD do C.
• Algoritmo de Strassen: Implementação recursiva orientada a tarefas para redução da complexidade assintótica.
• MPI + OpenMP: Utilização dos modelos de paralelização em inicialmente dois nós com paralelização interna ao nó em OpenMP.
• Offloading em GPU: Transição do esforço computacional vetorial para aceleradores gráficos via OpenMP Offloading e OpenACC.

---

Desenvolvido por Eduardo Tuler e Gabriel P. Silva – Instituto de Computação, UFRJ.