Annexe C — Estimer un temps de calcul

La notation $O(n^3)$ 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 $n$ ,

estimer le temps d'exécution sur un ordinateur réel.

Exemple : Résoudre un système linéaire de taille $n = 10^6$ 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 \times n$ nécessite environ :

\frac{2n^3}{3} \text{ opérations flottantes}

Pour $n = 10^6$ :

\frac{2 \times (10^6)^3}{3} = \frac{2 \times 10^{18}}{3} \approx 6.7 \times 10^{17} \text{ opérations}

Pour simplifier les calculs, on retient $6 \times 10^{17}$ 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 :

\text{Performance effective} \approx 10^9 \text{ ops/s par cœur}

💡

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 », $10^9$ ops/s est raisonnable.

Étape 3 : Calculer le temps

La formule fondamentale est simple :

\text{Temps} = \frac{\text{Nombre d'opérations}}{\text{Opérations par seconde}}

Pour notre exemple :

\text{Temps} = \frac{6 \times 10^{17}}{10^9} = 6 \times 10^{8} \text{ secondes}

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	$6 \times 10^8 \div 60$	$10^7$ minutes
Minutes → Heures	$10^7 \div 60$	$1.67 \times 10^5$ heures
Heures → Jours	$1.67 \times 10^5 \div 24$	~6 944 jours
Jours → Années	$6944 \div 365$	~19 ans

Conclusion : sur un seul cœur CPU, la factorisation LU d'une matrice $10^6 \times 10^6$ prendrait environ 19 ans.

Un raccourci utile

Pour éviter de refaire ces conversions à chaque fois, retenez cette approximation :

💡

Règle pratique

1 \text{ an} \approx \pi \times 10^7 \text{ secondes} \approx 3 \times 10^7 \text{ s}

(Valeur exacte : 365.25 × 24 × 3600 = 31 557 600 s)

Cette règle permet de convertir rapidement :

$10^7$ s ≈ 4 mois
$10^8$ s ≈ 3 ans
$10^9$ s ≈ 30 ans

Vérification : $6 \times 10^8$ 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 :

\text{Temps}_{8 \text{ cœurs}} = \frac{19 \text{ ans}}{8} \approx 2.4 \text{ ans}

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 $10^{13}$ à $10^{14}$ ops/s.

Avec $10^{13}$ ops/s :

\text{Temps} = \frac{6 \times 10^{17}}{10^{13}} = 6 \times 10^{4} \text{ s} \approx 17 \text{ heures}

Avec $10^{14}$ ops/s (GPU haut de gamme) :

\text{Temps} = \frac{6 \times 10^{17}}{10^{14}} = 6 \times 10^{3} \text{ s} \approx 1.7 \text{ heures}

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 $10^6 \times 10^6$ 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	$10^9$ ops/s	~19 ans
8 cœurs CPU (théorique)	$8 \times 10^9$ ops/s	~2.4 ans
8 cœurs CPU (réaliste)	$\sim 5 \times 10^9$ ops/s	~3-4 ans
GPU standard	$10^{13}$ ops/s	~17 heures*
GPU haut de gamme	$10^{14}$ 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 $10^5$ . 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 $O(n^2)$ avec $n = 10^9$ prendra 1 seconde » est impossible — cela représente $10^{18}$ opérations, soit environ 30 ans.
Choisir le bon algorithme : si un $O(n^3)$ prend 19 ans et qu'un $O(n \log n)$ 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 $n \times n$ avec $n = 10^4$ . La multiplication matricielle naïve a une complexité $O(n^3)$ .

Combien d'opérations cela représente-t-il ?
Quel est le temps estimé sur 1 cœur à $10^9$ ops/s ?
Ce calcul est-il réalisable en pratique ?

Solution

Nombre d'opérations : $(10^4)^3 = 10^{12}$
Temps : $\frac{10^{12}}{10^9} = 10^3$ 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	$\frac{2n^3}{3} = 6 \times 10^{17}$
2	Estimer la vitesse	$10^9$ ops/s (1 cœur)
3	Diviser et convertir	$6 \times 10^8$ s ≈ 19 ans

Raccourci : $1 \text{ an} \approx 3 \times 10^7$ secondes.

Cette compétence est fondamentale pour tout informaticien confronté à des questions de passage à l'échelle.