🧠 MASTER NOTES — PARALLEL & MULTITHREADING
PROGRAMMING (EN/FR)
1️⃣ Thinking in Parallel / Penser en Parallèle
Source: Thinking_Parallel.pdf / Lecture1-PrinciplesofParallelism
🔹 Definition / Définition
Parallel computing = simultaneous execution of multiple calculations or processes. 🇫🇷 Exécution simultanée
de plusieurs calculs ou tâches en même temps, contrairement au modèle séquentiel.
🔹 Why Parallelism? / Pourquoi le parallélisme ?
• CPU clock speed no longer increases (Power, ILP, Memory Walls)
• Exploiting concurrency improves performance.
• Parallel architectures are now standard: multi-core, GPUs, clusters. 🇫🇷 Le parallélisme est devenu
essentiel à cause des limites physiques de la fréquence CPU.
🔹 Forms of Parallelism / Types de parallélisme
• Data Parallelism: same instruction → multiple data sets.
• Task Parallelism: different tasks → different processors.
• Pipeline Parallelism: sequence of tasks on different units. 🇫🇷 Parallélisme de données, de tâches ou
de pipeline selon le découpage du travail.
🔹 Flynn’s Taxonomy / Classification de Flynn
Type Instructions Données Exemple
SISD 1 1 Processeur classique
SIMD 1 Plusieurs GPU, SSE, AVX
MISD Plusieurs 1 Rare, pipeline
MIMD Plusieurs Plusieurs Multicoeurs, clusters
🇫🇷 Les systèmes modernes sont principalement MIMD (Multi Instruction, Multi Data).
🔹 Architectures
• Shared Memory: common RAM accessible by all threads.
• Distributed Memory: each node has its own memory → uses message passing (MPI).
• Hybrid: mix of both. 🇫🇷 Mémoires partagées pour les multicœurs, distribuées pour les clusters.
1
🔹 Moore’s Law & the Three Walls
• Power Wall: can’t increase frequency without overheating.
• Memory Wall: memory access slower than CPU.
• ILP Wall: limited parallelism per instruction. 🇫🇷 Ces limites ont forcé le passage du parallélisme
matériel au parallélisme logiciel.
🔹 Performance Metrics
• Speedup (Sp) = T(serial) / T(parallel)
• Efficiency (Ep) = Sp / N
• Amdahl’s Law: Speedup ≤ 1 / (f + (1−f)/N) 🇫🇷 La partie séquentielle du programme limite
le gain global.
2️⃣ Multithreading Concepts / Multithreading et Synchronisation
Source: [Link]
🔹 Thread vs Process
Process Thread
Shared
Own memory
memory
Heavy context switch Light switch
Independent Cooperative
🇫🇷 Les threads partagent le même espace mémoire alors que les processus sont
isolés.
🔹 Thread Lifecycle (pthread)
pthread_create(&thread, NULL, function, arg);
pthread_join(thread, NULL);
🇫🇷 Création et terminaison d’un thread avec la bibliothèque POSIX pthread.
🔹 Race Conditions / Conditions de course
When two or more threads access shared data simultaneously without synchronization. 🇫🇷 Accès
concurrent sans contrôle → résultats imprévisibles.
2
🔹 Synchronization Tools
• Mutex (mutual exclusion): lock/unlock a shared section.
• Semaphores: counters controlling access to shared resources.
• Barriers: force threads to synchronize at a point. 🇫🇷 Ces outils assurent l’intégrité des données
partagées.
🔹 Example: Mutex
pthread_mutex_lock(&lock);
shared_var++;
pthread_mutex_unlock(&lock);
🇫🇷 Le mutex garantit qu’un seul thread modifie la variable à la fois.
🔹 Deadlock & Solutions
• Deadlock = threads waiting on each other forever.
• Prevention: consistent lock ordering, timeout. 🇫🇷 Éviter les interblocages en ordonnant les verrous.
3️⃣ UPC — Unified Parallel C / Programmation PGAS
Source: [Link]
🔹 Concept
UPC extends C for parallel programming using a shared memory model. 🇫🇷 UPC étend le langage C pour
offrir un modèle à mémoire partagée répartie.
🔹 Main Features
• Shared Variables: accessible by all threads.
• Private Variables: local to each thread.
• MYTHREAD / THREADS: identify and count threads.
• upc_forall: distribute loop iterations among threads.
🔹 Example
shared int A[THREADS];
A[MYTHREAD] = MYTHREAD;
upc_barrier; // synchronize threads
🇫🇷 Chaque thread écrit son ID puis attend la synchronisation.
3
🔹 Synchronization
• upc_barrier() → wait for all threads.
• Locks: upc_lock_t, upc_lock, upc_unlock.
🔹 Memory Model
• Shared Memory: accessible by all, may be remote.
• Private Memory: only local thread.
🔹 Advantages
• Simplifies distributed shared-memory programming.
• Combines MPI scalability with shared memory simplicity.
4️⃣ TP1 — Practical Work / Travaux Pratiques
Source: [Link] / [Link]
🔹 Exercise 1 – Hello World UPC
SPMD model (Single Program, Multiple Data)
#include <upc.h>
#include <stdio.h>
int main() {
printf("Thread %d of %d: Hello World!\n", MYTHREAD, THREADS);
return 0;
}
🇫🇷 Tous les threads exécutent le même code mais avec des données distinctes.
🔹 Exercise 2 – Conversion Table
Parallel loop example:
upc_forall(i=0; i<N; i++; &A[i]) {
A[i] = f(i);
}
🇫🇷 Répartition automatique des itérations entre threads.
4
🔹 Exercise 3 – Matrix Multiplication
Parallelize nested loops:
upc_forall(i=0; i<N; i++; &C[i][0])
for (j=0; j<M; j++)
for (k=0; k<P; k++)
C[i][j] += A[i][k] * B[k][j];
🇫🇷 Chaque thread calcule un sous-ensemble de lignes de la matrice.
🔹 Performance Observation
Blocked distribution offers better cache locality than cyclic. 🇫🇷 Distribution en blocs → meilleures
performances mémoire.
5️⃣ Exam Tips / Astuces d’Examen
✅ Concepts clés
• Always check race conditions.
• Use barrier synchronization in parallel loops.
• Test performance scaling: N=1,2,4,8 threads.
• Compare Speedup and Efficiency. 🇫🇷 Toujours valider la synchronisation et l’efficacité parallèle.
⚠️ Common Mistakes
• Missing pthread_join → threads terminate early.
• Using local variables as shared → undefined behavior.
• Forgetting barriers → inconsistent output.
🧩 Optimization Advice
• Use blocked distribution for matrices.
• Avoid false sharing by aligning shared data.
• Limit synchronization overhead.
END OF MASTER NOTES
🇬🇧 Parallel & UPC Programming — Summary for UIR Engineering Cycle (2025)
🇫🇷 Résumé bilingue complet pour la révision et la préparation d’examen.