2025-05-31: Feuille de route 2024-2025 (3A)¶

Main Web Site : https://sdpython.github.io/
Material : https://sdpython.github.io/doc/teachcompute/dev/

Plan¶

Les cours et séances se déroulent sur 4 séances de 3h au second semestre.

Evaluation¶

Utilisation de vos compétences statistiques pour fabriquer un benchmark adaptatif où l’on trouve la meilleure option de parallélisation pour un algorithme parallélisé avec moins d’essais qu’une grille.

Séance 1 - 9/04: pararalléliser comment?¶

Part 1

stratégies de parallélisation (big data, deep learning, calcul matriciel…)
coût, calcul, communication, caches
CPU vs GPU
conflits, synchronisation, mutex
L1: 32 Ko, 3/4 Go/s, 1/2 cycles d’horloge, L2: 1Mo, 20 Go/s, 3/5 cycles d’horloge, L3: 8Mo, 40 Go/s, 10/20 cycles d’horloge
thread / process
AVX
branching
cas du produit vectoriel
produit matriciel

Part 2

Environnement

C++ syntax
Python
présentation d’un package, C++
Outils de développement : cmake, git, pull request
Python : setup.py, sphinx, pybind11, cython
style : black, ruff
github et intégration continue
Copy/Pasting is your friend.
LLMs
VSCode

Séance 2 - 16/04: python, pybind11, cython¶

introduction à cython, numba, pybind11
voir _tutoriels et tutorials.yml

Séance 3 - 23/04: alorithmes parallélisés¶

Partie 1

Ecriture d’un benchmark.

Comparaison d’une multiplication de matrice sparse et dense, évolution en fonction du nombre des dimensions, du taux de « sparsité ».

Vaut-il mieux calculer (XA, XB) séparément ou X(A,B) où (A,B) désigne une matrice où A et B sont concaténées selon les colonnes.

AB est-il plus ou moins rapide que AB” si les matrices sont carrées ?

Profiling

Lecture de benchmark.

Parallelization of a vector sum with C++
Parallelization of a dot product
Compares filtering implementations (numpy, cython)
Parallelization with processes
écrire un programme pour plusieurs processeurs
CI, intégration continue
cmake

Pour aller plus loin

blas, lapack, Eigen, xtensor, simd
OpenMP

Partie 2

Algorithme de Strassen
HOGWILD !: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
problème de convergence
quantization
réseau de neurones
parallélisation mémoire contrainte ou presque
A quantum-inspired classical algorithm for recommendation systems
utilisation de plusieurs processeurs, CPUs, GPUs…, NPU, intel-npu
qui fait quoi ? data scientist, développeur

Séance 4 - 30/04: fusion d’opérations et projets¶

Benchmark à partir de cython_mat
Profiling
fusion d’opérations : cas de l”attention:

$Attention(Q,K,V)=softmax\left(\frac{QK'}{\sqrt{d_k}}\right)V$

avec

$Q \in \mathbb{R}^{m \times d_q}$ , $K \in \mathbb{R}^{m \times d_k}$ , $V \in \mathbb{R}^{m \times d_V}$ et :

$softmax(z_1,...z_n)_i = \frac{e_i}{\sum_{i=1}^{n} e_i}$

Sujets connexes¶

hacking (attaque), Spectre, Meltdown
https://fr.wikipedia.org/wiki/DO-178, PowerPC, RISC
MAIA
TPU
Un tri ?
Le calcul de la médiane ? (BJKST) Propriétés statistiques ?
Pourquoi est-ce si difficile de paralléliser un tri ?
scatter_nd, Que faire quand les indices sont dupliqués ?
Paralléliser une forêt aléatoire sur CPU, sur GPU ?
La recherche de doublons dans une liste de coordonnées géographiques (longitude, latitude) ?
An Efficient Matrix Transpose in CUDA C/C++, notion de Bank Conflicts (voir CUDA C++ Programming Guide) CUDA, Cartes graphiques, Warp…

Installation de ce module¶

Il ensuite exécuter les instuctions suivantes en ligne de commande.

git clone https://github.com/sdpython/teachcompute.git
cd teachcompute
pip install -e . -v --no-build-isolation

Si ça ne marche, installer cmake. Puis :

export PYTHONPATH=<this folder>
python _doc/examples/plot_bench_cpu_vector_sum.py

2025-05-31: Feuille de route 2024-2025 (3A)¶

Plan¶

Evaluation¶

Séance 1 - 9/04: pararalléliser comment?¶

Séance 2 - 16/04: python, pybind11, cython¶

Séance 3 - 23/04: alorithmes parallélisés¶

Séance 4 - 30/04: fusion d’opérations et projets¶

Sujets connexes¶

Installation de ce module¶

Lectures¶

Points particuliers¶

Livres¶

Autres¶