Parallel and distributed computing · Calcul parallèle et distribué
Doing work in order
- Most simple programs are sequential: they do one step, then the next, then the next.
- The computer finishes step 1 before it starts step 2.
- This is easy to understand, but it can be slow for big jobs.
Exécution séquentielle
- La plupart des programmes simples sont séquentiels : ils exécutent une étape, puis la suivante, puis encore la suivante.
- L'ordinateur termine l'étape 1 avant de commencer l'étape 2.
- C'est facile à comprendre, mais cela peut être lent pour de gros traitements.
Sequential (one worker):
task A -> task B -> task C -> task D
|-------|--------|--------|--------|
total time = A + B + C + D
Parallel computing
- Parallel computing splits work so several parts run at the same time.
- A modern computer has several processors (also called cores) that can each do work.
- If four workers each take one task, four tasks can finish in about the time of one.
Calcul parallèle
- Le calcul parallèle divise le travail afin que plusieurs parties s'exécutent en même temps.
- Un ordinateur moderne possède plusieurs processeurs (aussi appelés cœurs) capables chacun de traiter des tâches.
- Si quatre travailleurs effectuent chacun une tâche, quatre tâches peuvent se terminer en environ le temps nécessaire à une seule.
Parallel (four workers at once):
worker 1: task A
worker 2: task B
worker 3: task C
worker 4: task D
|--------|
total time ≈ the longest single task
Speedup
- Speedup asks: how many times faster is the parallel version?
- speedup = (sequential time) / (parallel time).
- Example: a job takes 8 seconds in order, but 2 seconds split up. Speedup = 8 / 2 = 4 times.
Gain de performance
- Le gain de performance demande : la version parallèle est-elle combien de fois plus rapide ?
- gain = (temps séquentiel) / (temps parallèle).
- Exemple : une tâche dure 8 secondes en séquentiel, mais seulement 2 secondes en parallèle. Gain = 8 / 2 = 4 fois.
Not always N times faster
- More processors does not always mean N times faster.
- Some parts of a job cannot be split — they must happen in order.
- Also, splitting work and joining results back together takes some extra time.
Pas toujours N fois plus rapide
- Avoir plus de processeurs ne signifie pas toujours N fois plus de rapidité.
- Certaines parties d'une tâche ne peuvent pas être divisées ; elles doivent s'exécuter séquentiellement.
- De plus, la division du travail et la fusion des résultats prennent un certain temps supplémentaire.
Job = setup (must be in order) + main work (can split)
setup main work (split over 4)
|-----| |--------------------------------|
|--------| <- this part gets 4x
The setup part stays the same length.
Distributed computing
- Distributed computing uses many separate computers that cooperate over a network.
- They may sit in different rooms, cities, or countries.
- Examples: the web (many servers), big data jobs split over thousands of machines, and large science projects.
Calcul distribué
- Le calcul distribué utilise plusieurs ordinateurs distincts qui coopèrent via un réseau.
- Ils peuvent se trouver dans différentes pièces, villes ou pays.
- Exemples : le Web (plusieurs serveurs), les tâches de big data réparties sur des milliers de machines, et les grands projets scientifiques.
Distributed (computers cooperate over a network):
[computer 1] [computer 2] [computer 3]
\ | /
\ | /
shared network / job
Each computer does part of the work.
Trade-offs
- Good: parallel and distributed systems can be much faster, and can handle huge jobs.
- Harder: the code is more complex; parts must be coordinated; results must be combined.
- Limits: speedup is capped by the parts that cannot be split, and by network delays between computers.
Compromis
- Avantages : les systèmes parallèles et distribués peuvent être beaucoup plus rapides et gérer de très gros traitements.
- Complexité : le code est plus complexe ; les différentes parties doivent être coordonnées ; les résultats doivent être combinés.
- Limites : le gain de performance est plafonné par les parties non divisibles et par les délais de communication entre ordinateurs.
Key words
- Sequential: steps run one after another, in order.
- Parallel: parts run at the same time on several processors.
- Speedup: sequential time divided by parallel time.
- Distributed: many separate computers cooperate over a network.
Mots clés
- Séquentiel : les étapes s'exécutent l'une après l'autre, dans l'ordre.
- Parallèle : les parties s'exécutent simultanément sur plusieurs processeurs.
- Gain de performance : temps séquentiel divisé par le temps parallèle.
- Distribué : plusieurs ordinateurs distincts coopèrent via un réseau.
Common mistakes
- Parallel speed-up only helps work that can be split into independent parts.
- Each extra processor adds less and less speed.
Erreurs courantes
- Le gain de performance parallèle ne sert que le travail pouvant être divisé en parties indépendantes.
- Chaque processeur supplémentaire apporte un gain de vitesse de moins en moins important.
Now you try
- Put the speedup formulas to work as small functions.
- Model a job that is part fixed setup and part splittable work. Press Check answer.
À vous maintenant
- Mettez les formules de gain de performance en pratique sous forme de petites fonctions.
- Modélisez une tâche comportant une partie de configuration fixe et une partie de travail divisible. Appuyez sur Vérifier la réponse.
A job has a setup part that must run in order, and a splittable part that workers can share at the same time. Write parallel_time(setup, splittable, workers) that returns the total time: the setup, plus the splittable part divided among the workers. Example: parallel_time(2, 8, 4) → 4.0 (2 + 8/4). · Un travail possède une partie setup qui doit s'exécuter séquentiellement, et une partie splittable que workers peut partager simultanément. Écrivez parallel_time(setup, splittable, workers) retournant le temps total : la configuration plus la partie partageable divisée par le nombre de travailleurs. Exemple : parallel_time(2, 8, 4) → 4.0 (2 + 8/4).
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write speedup(sequential, parallel) that returns how many times faster the parallel version is: the sequential time divided by the parallel time. Example: speedup(8, 2) → 4.0. · Écrivez speedup(sequential, parallel) retournant combien de fois plus rapide est la version parallèle : le temps séquentiel divisé par le temps parallèle. Exemple : speedup(8, 2) → 4.0.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Even with unlimited workers, the setup part still cannot be split. Write max_speedup(setup, splittable) for the best possible speedup: the whole job time divided by the setup time (endless workers shrink the splittable part to almost nothing, leaving only the setup). Example: max_speedup(2, 6) → 4.0 ((2+6)/2). · Même avec un nombre illimité de travailleurs, la partie setup ne peut toujours pas être partagée. Écrivez max_speedup(setup, splittable) pour le meilleur accélération possible : le temps total du travail divisé par le temps de configuration (des travailleurs sans fin réduisent la partie partageable presque à zéro, laissant uniquement la configuration). Exemple : max_speedup(2, 6) → 4.0 ((2+6)/2).
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.