Annexe C — Estimer un temps de calcul
La notation décrit comment le temps de calcul évolue avec la taille du problème, mais elle ne fournit pas directement un temps en secondes. Comment passer d'une complexité théorique à une estimation concrète du temps d'exécution ?
Cette annexe présente une méthode systématique en trois étapes, illustrée par un exemple concret.
Objectif
Étant donné :
- un algorithme de complexité connue,
- une taille de problème ,
estimer le temps d'exécution sur un ordinateur réel.
Exemple fil rouge : Résoudre un système linéaire de taille par factorisation LU.
Étape 1 : Compter les opérations
La première étape consiste à déterminer le nombre total d'opérations à effectuer.
La factorisation LU d'une matrice nécessite environ :
Pour :
Pour simplifier les calculs, on retient opérations.
Étape 2 : Estimer la vitesse du processeur
La deuxième étape consiste à estimer combien d'opérations le processeur peut effectuer par seconde.
Fréquence vs performance réelle
Un processeur moderne fonctionne à environ 3 GHz, soit 3 milliards de cycles par seconde. Cependant, la performance réelle dépend de nombreux facteurs :
| Facteur | Impact |
|---|---|
| Latence mémoire | Les accès RAM prennent 100+ cycles |
| Dépendances | Les instructions qui dépendent du résultat précédent bloquent le pipeline |
| Surcoût logiciel | Python, NumPy et les appels de fonctions ajoutent du temps |
Hypothèse de travail
Pour du code scientifique standard (non optimisé à la main), une estimation réaliste est :
Pourquoi 1 GHz et non 3 GHz ?
Cette valeur conservative tient compte des réalités pratiques. Un code optimisé avec des bibliothèques BLAS peut atteindre des performances 10 à 100 fois supérieures, mais pour une estimation « pire cas », ops/s est raisonnable.
Étape 3 : Calculer le temps
La formule fondamentale est simple :
Pour notre exemple :
Conversion en unités usuelles
Le résultat en secondes n'est pas très parlant. Convertissons-le étape par étape :
| Conversion | Calcul | Résultat |
|---|---|---|
| Secondes → Minutes | minutes | |
| Minutes → Heures | heures | |
| Heures → Jours | ~6 944 jours | |
| Jours → Années | ~19 ans |
Conclusion : sur un seul cœur CPU, la factorisation LU d'une matrice prendrait environ 19 ans.
Un raccourci utile
Pour éviter de refaire ces conversions à chaque fois, retenez cette approximation :
Règle pratique
(Valeur exacte : 365.25 × 24 × 3600 = 31 557 600 s)
Cette règle permet de convertir rapidement :
- s ≈ 4 mois
- s ≈ 3 ans
- s ≈ 30 ans
Vérification : s = 6 × 3 ans = 18 ans ✓
Accélération par parallélisation
Les 19 ans calculés supposent un seul cœur. Que se passe-t-il avec du matériel plus puissant ?
Avec 8 cœurs CPU
En théorie, 8 cœurs divisent le temps par 8 :
En pratique, le gain est moindre à cause de :
- Synchronisation : les cœurs doivent se coordonner
- Contention mémoire : tous les cœurs accèdent à la même RAM
- Loi d'Amdahl : certaines parties du code restent séquentielles
Estimation réaliste : 3-4 ans.
Avec un GPU
Les GPU modernes (NVIDIA A100, RTX 4090) possèdent des milliers de cœurs spécialisés dans le calcul matriciel. Les bibliothèques optimisées comme cuBLAS atteignent à ops/s.
Avec ops/s :
Avec ops/s (GPU haut de gamme) :
Limitations des GPU
Ces estimations sont théoriques. En pratique, plusieurs obstacles se posent :
| Limitation | Explication |
|---|---|
| Mémoire limitée | Un GPU dispose de 16-80 Go. Notre matrice en double précision nécessite 8 To. Elle ne tient pas en mémoire GPU. |
| Transferts CPU ↔ GPU | Copier les données vers le GPU prend du temps et peut devenir le goulot d'étranglement. |
| Algorithmes séquentiels | Tous les algorithmes ne se parallélisent pas efficacement sur GPU. |
Pour une matrice de cette taille, il faudrait utiliser des techniques avancées : décomposition par blocs, calcul distribué sur plusieurs GPU, ou clusters de calcul.
Tableau récapitulatif
| Configuration | Performance | Temps estimé |
|---|---|---|
| 1 cœur CPU | ops/s | ~19 ans |
| 8 cœurs CPU (théorique) | ops/s | ~2.4 ans |
| 8 cœurs CPU (réaliste) | ops/s | ~3-4 ans |
| GPU standard | ops/s | ~17 heures* |
| GPU haut de gamme | ops/s | ~2 heures* |
*Si la mémoire le permet — ce qui n'est pas le cas pour notre exemple.
Observation
Le facteur d'accélération entre un cœur CPU et un GPU optimisé est de l'ordre de . Cette différence explique pourquoi les GPU sont devenus incontournables en calcul scientifique et en apprentissage automatique.
Applications pratiques
Savoir estimer un temps de calcul permet de :
-
Détecter les erreurs de raisonnement : « Mon algorithme avec prendra 1 seconde » est impossible — cela représente opérations, soit environ 30 ans.
-
Choisir le bon algorithme : si un prend 19 ans et qu'un prend 1 minute, le choix s'impose.
-
Planifier les ressources : faut-il un GPU ? Un cluster ? Ou un simple laptop suffit-il ?
-
Communiquer avec rigueur : « c'est faisable » doit reposer sur des chiffres, pas sur l'intuition.
Exercice
Énoncé : Vous devez multiplier deux matrices avec . La multiplication matricielle naïve a une complexité .
- Combien d'opérations cela représente-t-il ?
- Quel est le temps estimé sur 1 cœur à ops/s ?
- Ce calcul est-il réalisable en pratique ?
Solution
-
Nombre d'opérations :
-
Temps : secondes ≈ 17 minutes
-
Oui, ce calcul est tout à fait réalisable sur un ordinateur standard.
Avec une bibliothèque optimisée (NumPy/BLAS), le temps réel serait de l'ordre de quelques secondes seulement.
Résumé
La méthode d'estimation en trois étapes :
| Étape | Action | Exemple |
|---|---|---|
| 1 | Compter les opérations | |
| 2 | Estimer la vitesse | ops/s (1 cœur) |
| 3 | Diviser et convertir | s ≈ 19 ans |
Raccourci : secondes.
Cette compétence est fondamentale pour tout informaticien confronté à des questions de passage à l'échelle.