Superar la multiplicación de matrices de NumPy con 150 líneas de código C

Resumen

Introducción

• La multiplicación de matrices es un elemento esencial en las redes neuronales modernas
• NumPy logra alto rendimiento usando bibliotecas BLAS externas
• Este artículo explica cómo implementar una multiplicación de matrices de alto rendimiento que sea simple, portable y escalable

Rendimiento de NumPy

• NumPy usa OpenBLAS en CPUs AMD
• El rendimiento se mide en FLOP/s
• Se mide el rendimiento de NumPy en un CPU Ryzen 7 7700 con un solo hilo y con múltiples hilos

Límites teóricos

• Se explica la jerarquía de memoria del CPU y las extensiones SIMD
• En teoría, se pueden alcanzar 163 GFLOPS con un solo hilo y 1203 GFLOPS con múltiples hilos

Implementación simple

• Se explica el algoritmo básico de multiplicación de matrices y se mide el rendimiento de una implementación simple
• La implementación simple alcanza 2.7 GFLOPS

Kernel

• Se explica cómo resolver la multiplicación de matrices dividiéndola en subproblemas pequeños
• Se optimiza el kernel usando instrucciones SIMD
• Con un kernel de 16x6 se alcanzan 147 GFLOPS

Enmascarado y empaquetado

• Se explica cómo manejar casos límite para procesar tamaños de matriz arbitrarios
• Se optimiza el rendimiento usando enmascarado y empaquetado
• La nueva implementación alcanza 56 GFLOPS

Caché

• Se explica el sistema de memoria caché del CPU
• Se aprovecha la caché para optimizar la reutilización de datos y la gestión de caché

Opinión de GN⁺

• Este artículo es muy didáctico porque explica paso a paso cómo implementar una multiplicación de matrices de alto rendimiento
• Permite aprender métodos de optimización usando instrucciones SIMD y caché de CPU
• Ayuda a entender el funcionamiento interno de bibliotecas como NumPy
• Otros proyectos con funciones similares incluyen Intel MKL y OpenBLAS
• Al adoptar nuevas tecnologías u open source, conviene considerar el rendimiento y la portabilidad

[GN⁺]

Comentarios en Hacker News

• La mayor parte del software no está optimizado, así que hay mucho margen para mejorar el rendimiento

  • La elección del algoritmo es lo más importante
  • Hay que revisar si se pueden reducir operaciones costosas como las llamadas al kernel
  • Se puede mejorar el rendimiento mediante vectorización
  • Hay que verificar si se puede optimizar la eficiencia de caché
  • Hay que evaluar la posibilidad de optimizaciones específicas para el hardware

• Los artículos citados en el repositorio de BLIS son materiales autorizados para entender este tema

  • No entienden por qué alguien pensaría que un BLAS optimizado tiene mal rendimiento
  • En lugar de numpy, habría que usar el BLAS de AMD
  • BLIS tiene mejor paralelización que OpenBLAS

• Las instrucciones SIMD no son necesarias para vectorizar el microkernel

  • Si se usan tamaños de bloque adecuados, el microkernel en C puro de BLIS logra más del 80% del rendimiento de una implementación optimizada a mano

• La mayoría de los patrones de código no están completamente especializados para el hardware, así que se pierde mucho rendimiento

  • Vale la pena consultar el clásico artículo de CS "There's plenty of room at the top"

• Se valora que hayan facilitado repetir el benchmark

  • En una CPU Xeon de 16 núcleos, matmul.c tarda 1.41 s al compilarse con gcc -O3, 1.47 s con clang -O2, y NumPy tarda 1.07 s
  • Creen que un kernel avx512 sería más rápido
  • Si se usa pthreads en vez de omp para gestionar explícitamente el pool de hilos, se puede reducir la sobrecarga

• Se cuestiona si la implementación de numpy realmente usa multihilo

• Hay curiosidad por saber por qué rinde mejor que OpenBLAS

  • Está manejando detalles como el caché
  • Se preguntan si está más optimizado para un procesador específico

• Comparar Python de un lado y C del otro no es justo

  • Sería mejor comparar ambos escritos en C

• Les preocupa la ineficiencia en la generación de máscaras

  • Hay formas más eficientes, como generar un arreglo constante global o comparar con un vector constante
  • Pero esto es un tema menor y probablemente no haga una gran diferencia en la práctica

• Cuestionan la utilidad práctica de aplicar multihilo a la multiplicación de matrices en sí

  • El multihilo sería más útil en los algoritmos que usan multiplicación de matrices

• Mención de tinyBLAS de jart

  • Se proporciona un enlace relacionado