Dépasser la multiplication de matrices de NumPy avec 150 lignes de code C

Résumé

Introduction

• La multiplication de matrices est un élément essentiel des réseaux neuronaux modernes
• NumPy atteint de hautes performances en utilisant des bibliothèques BLAS externes
• Cet article explique comment implémenter une multiplication de matrices haute performance simple, portable et évolutive

Performances de NumPy

• NumPy utilise OpenBLAS sur les CPU AMD
• Les performances sont mesurées en FLOP/s
• Les performances mono-thread et multithread de NumPy ont été mesurées sur un CPU Ryzen 7 7700

Limites théoriques

• Explication de la hiérarchie mémoire du CPU et des extensions SIMD
• En théorie, il est possible d’atteindre 163 GFLOPS en mono-thread et 1203 GFLOPS en multithread

Implémentation simple

• Présentation de l’algorithme de base de multiplication de matrices et mesure des performances d’une implémentation simple
• L’implémentation simple atteint 2,7 GFLOPS

Kernel

• Explication de la méthode consistant à diviser la multiplication de matrices en petits sous-problèmes
• Optimisation du kernel à l’aide des instructions SIMD
• Un kernel 16x6 atteint 147 GFLOPS

Masquage et empaquetage

• Explication de la manière de gérer les cas limites pour traiter des matrices de taille arbitraire
• Optimisation des performances à l’aide du masquage et de l’empaquetage
• La nouvelle implémentation atteint 56 GFLOPS

Caching

• Explication du système mémoire du cache CPU
• Utilisation du cache pour optimiser la réutilisation des données et la gestion du cache

L’avis de GN⁺

• Cet article est très pédagogique, car il explique étape par étape comment implémenter une multiplication de matrices haute performance
• Il permet d’apprendre des méthodes d’optimisation exploitant les instructions SIMD et le cache CPU
• Il aide à comprendre le fonctionnement interne de bibliothèques comme NumPy
• Parmi les autres projets aux fonctionnalités similaires, on peut citer Intel MKL, OpenBLAS, etc.
• Lors de l’adoption de nouvelles technologies ou de l’open source, il faut prendre en compte les performances et la portabilité

[GN⁺]

Avis Hacker News

• La plupart des logiciels ne sont pas optimisés, donc il reste une grande marge de progression en performances

  • Le choix de l’algorithme est le plus important
  • Il faut vérifier s’il est possible de réduire les opérations coûteuses comme les appels au noyau
  • La vectorisation peut améliorer les performances
  • Il faut vérifier s’il est possible d’optimiser l’efficacité du cache
  • Il faut examiner les possibilités d’optimisation spécifiques au matériel

• Les articles cités dans le dépôt BLIS sont des références faisant autorité pour comprendre ce sujet

  • Je ne comprends pas pourquoi on pense qu’un BLAS optimisé a de mauvaises performances
  • Il faut utiliser le BLAS d’AMD au lieu de numpy
  • BLIS est mieux parallélisé qu’OpenBLAS

• Les instructions SIMD ne sont pas nécessaires pour vectoriser le micro-kernel

  • Avec une taille de bloc appropriée, le micro-kernel pur C de BLIS atteint plus de 80 % des performances d’une implémentation optimisée à la main

• La plupart des patterns de code ne sont pas entièrement spécialisés pour le matériel, ce qui laisse échapper beaucoup de performances

  • L’article classique d’informatique "There's plenty of room at the top" vaut le détour

• Le fait d’avoir rendu le benchmark facilement reproductible est appréciable

  • Sur un CPU Xeon 16 cœurs, matmul.c prend 1,41 s lorsqu’il est compilé avec gcc -O3, 1,47 s avec clang -O2, tandis que NumPy prend 1,07 s
  • On pense qu’un kernel avx512 serait plus rapide
  • Utiliser pthreads au lieu de omp et gérer explicitement un pool de threads pourrait réduire l’overhead

• On se demande si l’implémentation de numpy utilise réellement le multithreading

• Curiosité sur la raison pour laquelle les performances dépassent celles d’OpenBLAS

  • Des détails comme le caching sont pris en compte
  • On se demande si c’est davantage optimisé pour un processeur spécifique

• Comparer Python d’un côté et C de l’autre n’est pas équitable

  • Il vaudrait mieux écrire les deux en C pour comparer

• L’inefficacité de la génération du masque dérange

  • Il existe des méthodes plus efficaces, comme générer un tableau global constant ou comparer avec un vecteur constant
  • Mais c’est un point mineur, et en pratique cela ne devrait pas faire une grande différence

• On doute de l’intérêt pratique de multithreader la multiplication de matrices elle-même

  • Le multithreading serait plus utile au niveau des algorithmes qui utilisent la multiplication de matrices

• Mention de tinyBLAS de jart

  • Lien connexe fourni