Systèmes Parallèles &

Répartis
(INE2)
Pr. Safae DAHMANI
@: dahmani@[Link]
Bureau 111

16/05/2022
 Plan du cours
Chapitre I: Architecture des systèmes HPC

Chapitre II: Systèmes parallèles

Chapitre III: Systèmes répartis

Caractéristiques des systèmes
parallèles
 Définitions, défis et contraintes
 Classification des systèmes parallèles

16/05/2022
Principes de la programmation parallèle
• Concurrence vs Parallélisme ?
• Programme séquentiel  Un seul fil d’exécution
• Programme concurrent  > 2 fils d’exécution qui coopèrent
• Applications multi-contextes: les fils d’exécution peuvent ou non s’exécuter en même
temps. Ils sont sont utilisés pour mieux organiser et structurer l’application. Ex. Interface
Homme-Machine.
• Applications parallèles: Chaque fils d’exécution est exécuté sur son propre ressource de
calcul (cœur). Ex. Prévisions météorologiques.
• Applications réparties (distribuées): Les fils d’exécution communiquent entre eux via un
réseau de communication (délai plus long). Le but est de répartir le calcul et les données
géographiquement. Ex. Banques de données.

16/05/2022
Principes de la programmation parallèle

Exécution
concurrente

Exécution
parallèle

16/05/2022
Caractéristiques des systèmes parallèles
• Définition: Calcul Parallèle/Système parallèle
Calcul Parallèle : La résolution d’un problème unique/grand en
utilisant plusieurs unités de calcul (CPUs, Nœuds de calcul ).
“ Parallel processing is the solution of a single problem by dividing it into a number of
sub-problems, each of which may be solved by a separate agent” Chalmers and Tidmus,
1996.

16/05/2022
Caractéristiques des systèmes parallèles
• Définition: Calcul Parallèle/Système parallèle
 Calcul Parallèle : La résolution d’un problème unique/grand en
utilisant plusieurs unités de calcul (CPUs, Nœuds de calcul ).
“ Parallel processing is the solution of a single problem by dividing it into a number of
sub-problems, each of which may be solved by a separate agent” Chalmers and Tidmus,
1996.
 Système parallèle : L’agrégation de plusieurs unités de calcul qui
collaborent pour effectuer un calcul parallèle.
“A large collection of processing elements that can communicate and cooperate to solve
large problems fast” Almasi and Gottlieb, 1989.

16/05/2022
Caractéristiques des systèmes parallèles
• Pourquoi le parallélisme ?

• Obtention des résultats dans des délais limités

• Libération des ressources de calcul dans les centres de calcul scientifique
• Manipulation de données de taille élevée; impossible de faire tourner le
calcul sur un seul nœud

 Le parallélisme n’est souvent pas un choix mais une nécessité !

16/05/2022
Caractéristiques des systèmes parallèles
• Contraintes et complexité :

• Ecrire un programme séquentiel est déjà une tache complexe

• Le programme séquentiel initial doit être bien optimisé avant de se lancer
dans la parallélisation
• Garantir la consistance des résultats entre programme séquentiel et
programme parallélisé
• Préserver la stabilité et la convergence de l’algorithme de calcul

 Paralléliser un programme séquentiel n’est pas une tâche facile

16/05/2022
Caractéristiques des systèmes
parallèles
 Définitions, défis et contraintes
 Classification des systèmes parallèles

16/05/2022
Caractéristiques des systèmes parallèles
• Programmation séquentielle :

• Un seul processus Mémoire

• Un seul processeur physique

• Toutes le variables du programme
sont allouées dans la mémoire du processus
Hello.c
CPU

16/05/2022
Caractéristiques des systèmes parallèles
• Taxonomie de Flynn (1972) est une classification basée sur les types
de processeurs :
• Nombre de données traitées
• Différentes/identiques opérations (instructions) appliquées

# Instructions
#Données
Single Multiple
Single SISD MISD

Multiple SIMD MIMD

16/05/2022
Caractéristiques des systèmes parallèles
• SISD: Un seul processeur de calcul et une seule donnée à la fois (exécution séquentielle).
C’est limité par la fréquence du processeur unique.
• SIMD: Une seule et même instruction est appliquée sur plusieurs données à la fois. Ce
type d’architecture est largement utilisé dans le traitement d’image ou calculs
scientifiques. Il s’agit de ce qu’on appelle : machine vectorielles. Exemple: v3 = v1 + v2.
• MISD: Une machine multiprocesseur exécutant plusieurs instructions sur un même
donnée. Exemple : X = sin(a) + cos(a) + tan(a). Ce type de machines n’est plus vraiment
utilisées à cause de son applicatif limité.
• MIMD: Une architecture basée sur plusieurs unités de calculs opérant sur différents sets
de données. Ce sont des machines puissantes prend en charge tout type d’applications.

 “Tout est MIMD” !

16/05/2022
Caractéristiques des systèmes parallèles
• Taxonomie de Flynn (1972) est une classification basée sur les types
des processeurs :
• Nombre de données traitées
• Différentes/identiques opérations (instructions) appliquées

# Instructions
#Données
Single Multiple
Single Von Neumann Processeur à pipeline

Multiple Processeur vectoriel Machines parallèles

(Multiprocesseurs)

16/05/2022
 Caractéristiques des systèmes parallèles
• Classification par nombre de cœurs:
Complexité de
programmation MPP-based clusters (1 MPP par nœud )
Massivelly Parallel Processors (MPP)
(plusieurs centaines/milliers de cœurs)

Highly Parallel Processors (HPP)

(< 256 cores)
Parallel Processors (PP)
(2-32 cores)
Monoprocesseur

Puissance
par cœur Nombre de
cœurs
16/05/2022
Principes de la programmation
parallèle
 Concepts et terminologie
 Paradigmes de la programmation parallèle
 Conception d’un programme parallèle
 Analyse des performances

16/05/2022
Principes de la programmation parallèle
Processus Thread

• Un programme en cours d’exécution • Une fonction en cours d’exécution

• Espace mémoire privé • Un processus peut contenir plusieurs threads qui
• Collaboration par échange de messages partagent la mémoire plus d’autres ressources
• Contexte lourd (code, registres, piles, fichiers, ..) • Contexte léger (registres, piles)

 Opérations couteuses: Création/activation;  Opérations peu couteuses: Création/activation;

changement de contexte, .. changement de contexte, ..

Processus Vs Thread

16/05/2022
Principes de la programmation parallèle
• Définitions :
« Canal de communication »: c’est le mécanisme qui assure le lien de
communication entre les tâches d’un programme. A chaque canal de
communication est associé un ensemble d’adresses correspondant à des
emplacements mémoire différents. Les accès à ces derniers sont gérés à
l’aide d’un système d’accès offrant des routines de lecture et d’écriture
que les tâches utilisent pour recevoir ou transmettre des données.

16/05/2022
Principes de la programmation parallèle
• Définitions :

« Modèle de programmation »: ensemble de mécanismes permettant

de mettre en place le parallélisme selon la plateforme d’exécution.

16/05/2022
Principes de la programmation parallèle
• Définitions :

« Synchronisation »: Permet de garantir la coordination entre les tâches qui

communiquent entre elles en introduisant des points de synchronisation indiquant
des mises en attentes de certaines tâches en fonction de l’exécution des autres.

16/05/2022
Principes de la programmation parallèle
• Comment programmer les systèmes parallèles ?
• Il existe plusieurs niveaux de parallélisme (granularité):
Granularité Objet Parallélisé par

Très fine Instruction Processeur

Fine Boucle/Bloc d’instruction Compilateur

Moyenne Fonction Programmeur

Large Processus Programmeur

 Cacher la latence générée par les opérations couteuses telles que les accès mémoire

16/05/2022
Principes de la programmation parallèle
• Comment programmer les systèmes parallèles ?
• Parallélisme implicite:
• A la compilation (langage séquentiel)
• Langage parallèle

16/05/2022
Principes de la programmation parallèle
• Comment programmer les systèmes parallèles ?
• Construction explicite du parallélisme : extension du langage
séquentiel permettant le contrôle de :
• Création du parallélisme :
• Création des tâches
• Répartition des tâches sur les unités de calcul (itération sur tous les processeurs de
calcul)
• Exécution des tâches parallèles :
• Synchronisation
• Passage de messages (Ex. synchrones/asynchrones )
• Sections critiques (Ex. gestion des données partagées)
• Terminaison d’une exécution parallèle

16/05/2022
Principes de la programmation
parallèle
 Concepts et terminologie
 Paradigmes de la programmation parallèle
 Conception d’un programme parallèle
 Analyse des performances

16/05/2022
Caractéristiques des systèmes parallèles
• Modèle à mémoire partagée:
P1 P2 • Tous les processeurs accèdent à une mémoire
physique partagée où chaque donnée a une
adresse unique.
Cache Cache
• Tout changement dans cette adresse mémoire par
un processeur est visible par tous les autres
processeurs (cohérence de données )
Réseau • Les processeurs ont leurs propres mémoires
locales (caches)
• Les paradigmes basés sur cette approche les plus
connus:
Mémoire partagée • POSIX (Pthreads)
• OpenMP
• Modèle à mémoire partagée
16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée:
• Accès mémoire:
• UMA (Unified Memory Access): les processeurs ont tous le même temps d’accès aux
données.
• NUMA (NON-Unified memory Access): conçu pour pallier à la problématique des accès
concurrents par le fait de répartir la mémoire en zones. Chaque zone est placée sur un
bus différent
Les des temps d’accès à la mémoire sont donc différents en fonction de la zone accédée.

On parle également de CC-UMA et CC-NUMA (CC: Cache Coherent) pour les
mémoires avec gestion de la cohérence des caches où les processeurs ont
toujours accès à la dernière version de la zone mémoire modifiée.

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée:

• POSIX (PThreads) : c’est un standard de la programmation multithreads.

L’interface PThreads définit les routines de gestion des tâches (create, detach,
join), d’exclusion mutuelle (create, destroy, lock, unlock), les variables de
condition et de synchronisation (verrous de lecture/écriture, barrières).

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée
• Exemple: POSIX Threads (PThreads)

• Inclusion de la bibliothèque :
# include <pthread.h> // include Pthread library

• Déclaration des attributs décrivant les threads

int threadnum=2;
pthread_t *thread; // thread identifier
pthread_attr_t attr;
int *startValue;
double *threadResults; // required type can be used

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée
• Exemple: POSIX Threads (PThreads)

• Définition de la fonction associée au thread: « void* func(*void) »

void *Calculate(void *args) { // code executed by threads started with pthread_create()
int start=*((int *)args); // start from this number
// perform computations
threadResults[start]=partialresult;
}

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée
• Exemple: POSIX Threads (PThreads)
• Lancement des threads:
int main(int argc, char **argv) {
int i;
pthread_attr_init(&attr); //initializes the attribute object with default value
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE); //Set the created thread to
joinable state
// Starting calculation threads
for (i=0;i<threadnum;i++) {
startValue[i]=i;
// launch a thread for calculations
..
pthread_create(&thread[i],&attr,Calculate,(void *)(&( startValue[i])));
}

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée
• Exemple: POSIX Threads (PThreads)

• Synchronisation des threads

for (i=0;i<threadnum;i++) {
pthread_join(thread[i] , &threadstatus);
//merge current result with threadResults[i]
}
• Détruire les threads
pthread_attr_destroy(&attr); // destroy thread

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée:

• OPENMP: Ce modèle offre des extensions de langages comme Fortran, C, C++

. Il consiste à ajouter des annotations dans le code séquentiel pour indiquer
comment le travail sera réparti entre les tâches d’exécution. Contrairement au
modèle PThreads, le modèle OpenMP offre une approche plus abstraite.

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée
• Exemple: OpenMP
#include <omp.h>
#include <stdio.h>
int main() {
// a serial region
printf(“\n This is executed by one thread only!”);
// a serial processing here parallel region with optional parameters […]

#pragma omp parallel [parameters..]

{
printf(“\n Parallel processing here”);
// parallel processing here
}
16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée
• Exemple: OpenMP
#include <omp.h>
#include <stdio.h>
int main() {
// a serial region
printf(“\n This is executed by one thread only!”);

// a serial processing here parallel region with optional parameters […]

#pragma omp parallel num_threads(32)
{
printf(“\n Hello from thread %d, nthreads %d\n”,
omp_get_thread_num(), omp_get_num_threads());
// parallel processing here
}
16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire partagée
• Exemple: OpenMP
#include <omp.h>
#include <stdio.h>
int main() {
// a serial region
printf(“\n This is executed by one thread only!”);

// a serial processing here parallel region with optional parameters […]

#pragma omp parallel private(variable0, variable1) shared( variable2)
{
// parallel processing here
}

16/05/2022
Principes de la programmation parallèle
Mémoire
• Modèle à mémoire répartie: locale
• Chaque processeur a sa propre mémoire;
pas de notion d’espace d’adressage partagé P1
• Les processeurs fonctionnent de façon
indépendante
• Le partage des données se fait par Mémoire Mémoire
communication explicite  pénalité d’accès locale P2 P4 locale
aux données non locales est très élevée
• Les performances de communications
dépendent fortement du réseau
d’interconnexion ainsi que le mécanisme qui P3
le gère
• Les paradigmes basés sur cette approche les Mémoire
plus connus: locale
• MPI (Message Passing Interface): CPU
• CUDA/OPENCL: GPU Modèle à mémoire répartie
16/05/2022
Principes de la programmation parallèle
• Modèle par passage de messages: Adapté aux architectures à
mémoire repartie. C’est un ensemble de bibliothèques fournissant les
routines nécessaires à l’initialisation et la configuration de
l’environnement de passage de messages aussi bien que les routines
de transmission et de réception des paquets de données.
• MPI (Message Passing Interface): Une application est constituée de plusieurs
processus qui interagissent par échange de messages. L’API caractérise un
processus par un identifiant unique(rank) au sein d’un groupe encapsulé dans
ce qu’on appelle un « MPI Communicator ».

16/05/2022
Principes de la programmation parallèle
• Modèle par passage de messages:
• MPI (Message Passing Interface): Une application est constituée de plusieurs
processus qui interagissent par échange de messages.
• MPI caractérise un processus par un identifiant unique(rank) au sein d’un groupe
encapsulé dans ce qu’on appelle un « MPI Communicator ».

Processus 0 5
MPI (rank =0)
2

4
1

3
16/05/2022
Principes de la programmation parallèle
• Modèle par passage de messages:
• MPI (Message Passing Interface):
• Le communicateur par défaut est appelé: MPI_COMM_WORLD
• Communicateurs « intra»: entre processus d’un même groupe
• Communicateurs « inter»: communication entre les groupes
• Il existe deux types de communications en MPI:
• P2P (Point-à-point): ça implique deux processeurs. Chacun peut soit envoyer ou recevoir un
message. Dans les deux cas un identifiant « rank » du processus destination est à spécifier
• Collective: plusieurs processus prennent part de cette communication soit pour
synchronisation ou partage de données.

16/05/2022
Principes de la programmation parallèle
• Modèle par passage de messages:
• MPI (Message Passing Interface):
• La communication peut être:
• Bloquante: fonction bloquée jusqu’à la fin d’une opération (envoie d’un message) ou jusqu’un
niveau de progression spécifique (copier dans un buffer pour un transfert de donnée)
• Non bloquante: la main est retournée immédiatement au processus appelant et la fonction
continue en arrière plan.

16/05/2022
Principes de la programmation parallèle
• Modèle par passage de messages:
• MPI (Message Passing Interface):
• P2P:
• MPI_Send(): bloquante  la fonction retourne si les données sont copiées à la destination ou
dans un buffer intermédiaire
• MPI-Recv(): bloquante
• Collective:
• MPI_Barrier: synchronisation entre les processus d’un groupe
• MPI_Scatter: un ou plusieurs processus envoient les données à un groupe de processus
• MPI_Gatter: un processus rassemble des données d’un groupe de processus
• MPI_Bcast: un processus diffuse des données à tous les processus d’un communicateur
• MPI_Reduce: permet d’exécuter une opération sur les données reçues (communication
+opération)
• MPI_All2all: de tous les processus vers tous les autres.
16/05/2022
Principes de la programmation parallèle
#include <mpi.h>
#include <stdio.h>

int main(int argc, char** argv) {

// Initialize the MPI environment
MPI_Init(NULL, NULL);

// Get the number of processes

int world_size;
MPI_Comm_size(MPI_COMM_WORLD, &world_size);

// Get the rank of the process

int world_rank;
MPI_Comm_rank(MPI_COMM_WORLD, &world_rank);

// Get the name of the processor

char processor_name[MPI_MAX_PROCESSOR_NAME];
int name_len;
MPI_Get_processor_name(processor_name, &name_len);

// Print off a hello world message

printf("Hello world from processor %s, rank %d out of %d processors\n",
processor_name, world_rank, world_size);

// Finalize the MPI environment.

MPI_Finalize();
16/05/2022
}
Principes de la programmation parallèle
Mémoire partagée Mémoire répartie
Principe • Multiplication d’unités de calcul simples • Facilite le passage à l’échelle
(architecture symétrique) • Implémentation hardware
• Programmation simple plus simple

Limitations • Accès couteux à la mémoire partagée • Gestion explicite du

• Synchronisation (ex. barrières, sémaphores, transfert des données
verrous..) • Coût élevé des
• Gestion de la cohérence des caches communications
(plusieurs copies d’une même donnée dans
les caches locales)
• Limitation des performances à partir d’un
certain nombre de cœurs

16/05/2022
Principes de la programmation parallèle
• Modèle à mémoire répartie virtuellement partagée (Distributed Shared
Memory ‘DSM’) :
• Plusieurs copies d’une
même données chargées
dans les mémoires locales afin d’accélérer le
parallélisme
• Chaque donnée a une référence
unique dans la mémoire virtuellement
partagée.
• Les processeurs ne voient que cette
Référence unique pour chaque accès
à une données.
• Ex. Memnet, Munin, Shiva, Ivy, etc

16/05/2022
Principes de la programmation parallèle
• Modèle hybride:
• Les supercalculateurs les plus puissants au monde sont un mixe des deux
modèles:
• Nœud multiprocesseurs à mémoire partagée
 brique de base à mémoire partagée
• Briques interconnectées via un réseau puissant à haute performance
 mémoire répartie

• Association des 2 modèles

Mémoire Mémoire de programmations:
partagée Passage de partagée • MPI + openMP
messages • MPI + Cuda/openCL

16/05/2022
Principes de la programmation parallèle

• Modèles flot de données: Le modèle orienté parallélisme de données

permet d’exploiter la concurrence dérivée de l’application d’une
même opération sur de multiples données SIMD (ou éléments d’une
structure de données). Les compilateurs exigent que l’utilisateur
fournisse des informations sur le placement des données.

16/05/2022
Principes de la programmation parallèle

• Méta-programmation par modèle: Offre un ensemble d’abstractions

haut niveau basées sur des modèles. Un modèle est une instanciation
d’un paradigme de programmation spécifique avec les primitives de
contrôle et de communication liée à l’application.

16/05/2022
Principes de la programmation parallèle
• CUDA (NVIDIA) : Un programme CUDA est constitué d'une partie qui
s'exécute sur l'hôte (CPU) et d'une partie qui s'exécute sur le
périphérique(GPU). Les phases peu parallèles sont exécutées sur
l'hôte. Les phases massivement parallèles sont exécutées sur le
périphérique.
• CUDA: « Compute Unified Device Architecture »
• Programmation massivement parallèle en C sur cartes NVIDIA

16/05/2022
Principes de la programmation parallèle
• Architecture matérielle NVIDIA:
• Nvidia GTX 560 :
• 336 Multiprocesseurs x 8 Processeurs (2688 cœurs)
• 1900 MHz
• 768 Threads max par multiprocesseur
• 16 Ko de mémoire partagée
• 8196 registres / MP

16/05/2022
Principes de la programmation parallèle
• Architecture matérielle NVIDIA:
Multiprocesseurs N
Multiprocesseurs N-1
Multiprocesseurs 2
Multiprocesseurs 1

Shared Memory
Registers Registers …… Registers Instruction
Unit
P P P
Constant Cache

Texture Cache

Device Memory
16/05/2022
Principes de la programmation parallèle
• Architecture matérielle NVIDIA:
• Mémoire globale : Cette mémoire est accessible à l'ensemble
des multiprocesseurs. Sa bande passante est très importante, environ 150 Go/s,
cependant sa latence est importante. Lorsque vous achetez une carte graphique,
la capacité de mémoire indiquée fait référence à ce type de mémoire.
• Mémoire partagée : Cette mémoire est propre à un multiprocesseur.
Sa latence est plus faible que la mémoire globale, au détriment de sa taille
qui est de environ 8Mo.
• Les registres : Cette mémoire est propre à un processeur,
son accès est rapide, environ 1 cycle, mais sa taille est réduite, environ 8 Ko.
• Les textures : Cette mémoire est propre à un multiprocesseur, et offre des
mécanismes d'accélération. Elle permet de stocker les textures, comme dans un jeux
et éviter certains accès au disque.

16/05/2022
Principes de la programmation parallèle
• Architecture logicielle NVIDIA:

• Une fonction calculée sur le GPU est appelée “kernel” (noyau)

• Le kernel est dupliqué sur le GPU comme un ensemble de threads
• Cet ensemble de threads est organisé de façon logique en une “grid” (grille)
• Chaque copie du kernel connaît sa position dans la grille et peut exécuter la
fonction définie par le kernel sur différentes données
• Cette grille est projetée « mappée » physiquement sur l’architecture de la
carte à l’exécution « runtime »

16/05/2022
Principes de la programmation parallèle
• Grille de calcul:

Kernel (1,0)

(1,0) Thread Thread Thread

(0,0) Block (0,0) (1,0) (2,0)

Grid
Thread Thread Thread
(0,1) (1,1) (2,1)
(0,1) (1,1)
Thread Thread Thread
Grille de calcul (0,2) (1, 2) (2,2)

16/05/2022
Principes de la programmation parallèle
• Architecture logicielle NVIDIA:
• La Runtime CUDA est une extension du langage C++. Elle permet de s’interfacer avec la partie
matérielle:
• Compiler
• Assurer les liens avec les kernels CUDA et les exécutables
• Mots clefs : Kernel
• __device__ : kernel exécuté sur le GPU mais appelé par le CPU
• __global__ : kernel exécuté et appelé par le GPU
• __host__ : fonction exécutée et appelée par le CPU.

• Variables : Thread (dim 3)

• blockIdx : index du bloc dans la grille
• threadIdx : index du thread dans le bloc
• blockDim : nombre de threads par bloc

16/05/2022
Principes de la programmation parallèle
• Lancement d’un kernel:
• Le lancement d'un kernel s'effectue de la maniére suivante :
kernel<<< dimGrid, dimBlock[, dimMem ]>>>(params);

• kernel : Nom de la fonction

• dimGrid : taille de la grille (en nombre de blocs)
• dimBlock : taille de chaque bloc (en nombre de threads)
• dimMem (optionel) : taille de la mémoire partagée allouée par bloc

 Le lancement d’un Kernel est non bloquant au thread qui l’exécute.

16/05/2022
Chapitre II : Caractéristiques des systèmes
parallèles
• Exemple programme CUDA:
// Définition de la function kernel
__global__ void incrementVectorGPU(int *a, int b, int n)
• // Ecrire la function de lancement du kernel
{
/* Calcul de la position dans la grille */
int idx = blockIdx.x * blockDim.x + threadIdx.x;

if (idx < n )
a[idx] = a[idx] + b;
}
int main(void)
{
}

 Ecrire la function de lancement du kernel.

16/05/2022
Chapitre II : Caractéristiques des systèmes
parallèles
• Exemple programme CUDA:
// Définition de la function kernel
__global__ void incrementVectorGPU(int *a, int b, int n)
{
/* Calcul de la position dans la grille */
int idx = blockIdx.x * blockDim.x + threadIdx.x;

if (idx < n ) // Condition ?

a[idx] = a[idx] + b;
}
int main(void)
{
dim3 dimBlock(blockSize);
dim3 dimGrid(N/(int)blockSize);
incrementVectorGPU<< dimGrid, dimBlock>>>(vector1, scalar, N);
}

16/05/2022
Chapitre II : Caractéristiques des systèmes
parallèles
• Exemple programme CUDA:
• Grâce aux différents indices calculés 'idx', nous pouvons voir que chaque case
du tableau est bien identifiée par un Thread qui exécutera le calcul sur un seul
indice du tableau.
• Vecteur de taille N=16, Block de taille : 4
Thread v1 v14
B13 B14 Thread 1
14
Thread 1 Thread 2 v1 v2
B1 BB3 B16
2
Thread 3
Thread v2
16 v16
B3 B4 Thread 3 Thread 4
v2
v2

• A quoi sert la condition dans le code ?

• Combien de cycle GPU faut-il afin d’exécuter le programme ?
16/05/2022
Chapitre II : Caractéristiques des systèmes
parallèles
• Exemple programme CUDA:
• Grâce aux différents indices calculés 'idx', nous pouvons voir que chaque case
du tableau est bien identifiée par un Thread qui exécutera le calcul sur un seul
indice du tableau.
• Vecteur de taille N=16, Block de taille : 4
Thread v1 v14
B13 B14 Thread 1
14
Thread 1 Thread 2 v1 v2
B1 BB3 B16
2
Thread 3
Thread v2
16 v16
B3 B4 Thread 3 Thread 4
v2
v2

• A quoi sert la condition dans le code ?

• Eviter le débordement de la taille du vecteur
16/05/2022 • Combien de cycle GPU faut-il afin d’exécuter le programme ?
• 1 cycle GPU
Principes de la programmation
parallèle
 Concepts et terminologie
 Paradigmes de la programmation parallèle
 Conception d’un programme parallèle
 Analyse des performances

16/05/2022
Principes de la programmation parallèle

Conception Théorie

Technologies

16/05/2022
 Principes de la programmation parallèle

• L’ensemble des concepts et

• L’étude des principes
termes utilisés pour définir le
fondamentaux et techniques de
parties parallèles d’un
composition pour la création des
programme et leurs interactions
programme parallèle et leur
description formelle ou informelle. Conception Théorie

Technologies

• Technologies d’implémentation:
• Logicielle et matérielle
• Middleware de contrôle
16/05/2022
Principes de la programmation parallèle
Conception:
• Définition: trouver une forme qui satisfait la fonction et ses exigences:
• Structurelles
• Comportementales

Objectifs :
• Réduction du temps d’exécution
• Coordination entre plusieurs ressources de calcul

16/05/2022
Principes de la programmation parallèle
Conception:
• Définition: représentation/description:
• Data set: données utilisées dans le calcul
• Algorithme: séquentiel  parallèle, parallèle

Solutions:
• Plusieurs solutions
• Evaluation des performances
• Efficacité
• Coût minimal

16/05/2022
Principes de la programmation parallèle
Conception:

• Propriétés  Exigences
Evaluation

• Propriétés Forme

• Exigences
Fonction

16/05/2022
Principes de la programmation parallèle
Conception:
1. Délimitation

2. Décomposition

3. Agrégation

4. Placement

16/05/2022
 Principes de la programmation parallèle
Conception:
1. Comprendre les limites de la
1. Délimitation solution.

2. Fournir une description détaillée de

la forme de la solution : 2. Décomposition 3. Analyser la qualité de l’agrégation des
• Composants composants qui forment la solution finale:
• Responsabilités • Définition des risques
• Connections • Itération entre partitionnement et
3. Agrégation agrégation jusqu’à satisfaction des
exigences de la fonction
• Affinement de la solution (propriété de la
4. Placement solution)

4. Allocation des tâches aux processeurs:

• Minimiser les communications
16/05/2022
• Equilibrer les charges
 Principes de la programmation parallèle
Conception:
1. Comprendre les limites de la
1. Délimitation solution.

2. Fournir une description détaillée de

la forme de la solution : 2. Décomposition 3. Analyser la qualité de l’agrégation des
• Composants composants qui forment la solution finale:
• Responsabilités • Définition des risques
• Connections • Itération entre partitionnement et
3. Agrégation agrégation jusqu’à satisfaction des
exigences de la fonction
• Affinement de la solution (propriété de la
4. Placement solution)

4. Allocation des tâches aux processeurs:

• Minimiser les communications
16/05/2022
• Equilibrer les charges
Principes de la programmation parallèle
Conception d’un programme parallèle:

Parallélisation Parallélisation
automatisée Manuelle
• Utilisation d’outils pour identifier et/ou • Le développeur est en charge d’identifier et
implémenter le parallélisme d’implémenter le parallélisme
• Conversion des programmes séquentiels en
programmes parallèles
• Compilateur

16/05/2022
Principes de la programmation parallèle
 Automatisation du parallélisme:

• Tout automatisé : le compilateur analyse le programme pour détecter

les sections parallélisables et éventuellement évaluer le gain en
performance. Ce type de parallélisation vise principalement les
boucles « for » dans le code.
• Dirigé par le code:
• Le développeur indique explicitement au compilateur comment paralléliser le code.
• Cela se fait à travers des directives ou flags du compilateur
• Intègre également un certain degré d’automatisation de parallélisation

16/05/2022
Principes de la programmation parallèle
• Automatisation du parallélisme:

Parallélisation
Parallélisation automatisée
dirigée par le code/manuelle
• Peut introduire des erreurs • Complexe
• Risque de dégradation des performances • Sujet aux erreurs
• Manque de flexibilité • Manquer des sections parallélisables
• Plus adapté lorsqu’un programme séquentiel • Itérative (coût élevé)
existe ou en cas de manque de temps/ressources

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle:
• Partir de :
• Programme séquentiel
• Description d’un problème

• Bien comprendre le problème/solution séquentielle :

 Peut-on paralléliser le problème ?

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle:
• Exemple de problème simplement parallélisable:
• Agrandir une image représentée par une matrice d’entiers de taille (n, n), en
doublant sa taille vers une matrice de (2n, 2n).
• Solution possible: Donner à chaque pixel la valeur de son voisin de gauche par exemple

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle:
• Exemple de problème non-parallélisable:
• Problème de l’évaluation d’un circuit (CIRCUIT VALUE PROBLEM): consiste à
calculer la sortie d'un circuit booléen sur des entrées données.
NOT Sortie

NOT
OR

AND
AND OR

X1 =0 X2 =1 X3=1 Entrées
16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Décomposition du problème
• Diviser le problème en plusieurs parties que l’on peut répartir sur
différentes ressources de calcul. On distingue deux types de
décomposition:
1. Décomposition de domaine
2. Décomposition fonctionnelle

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Décomposition du problème
1. Décomposition de domaine: ça consiste à diviser les données du
problème de façon à ce que chaque tâche parallèle s’exécute sur un
bout de ces données.

Data Set

Task1 Task2 Task3 Task4

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Décomposition du problème
1. Décomposition de domaine: ça consiste à diviser les données du
problème de façon à ce que chaque tâche parallèle s’exécute sur un
bout de ces données à chaque phase de la vie du porgramme.
• Ces données sont: Entrées, Sorties, Données intermédiaires
• La priorité est donnée aux structures de données de grande taille aussi
bien que les plus fréquemment utilisées
• L’échange des données entre tâches se fait par communications

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Décomposition du problème
2. Décomposition fonctionnelle: la décomposition se base sur le calcul à
faire plutôt que sur les données. Chaque tâche parallèle va donc exécuter
un bout du calcul

Instruction Set

Task1 Task2 Task3 Task4

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Décomposition du problème
2. Décomposition fonctionnelle: la décomposition se base sur le
calcul à faire plutôt que sur les données. Chaque tâche parallèle va
donc exécuter un bout du calcul
• A chaque tâche est associé l’ensemble des données sur lesquels
le calcul est effectué:
• Données disjointes: décomposition fonctionnelle est appropriée
• Données partagées: Beaucoup de communications; la décomposition de domaine
est à considérer

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Décomposition du problème
2. Décomposition fonctionnelle: la décomposition se base sur le calcul à
faire plutôt que sur les données. Chaque tâche parallèle va donc exécuter
un bout du calcul
• Exemple: Recherche de solutions Search (A):
dans un arbre begin
if (solution(A)) then
score = eval(A)
report solution and score
else
Nœud de recherche
foreach child A(i) of A
search(A(i))
endfor
endif
end
• Une nouvelle tâche est crées à
16/05/2022 chaque pas une nouvelle recherche.
Principes de la programmation parallèle
 Parallélisme manuelle: Décomposition du problème
• Validation de la décomposition: La décomposition d’un problème est une
solution possible parmi d’autres. Il est important de vérifier qu’il n’y a pas
de défauts évidents à cette étape de la conception:
1. La décomposition génère au moins autant de tâches que l’on a de ressources de calcul.
Cette condition est flexible et peut être améliorée dans les prochaines étapes de
conception.
2. Il n’y a pas de calculs ni d’accès en mémoire externe redondants  cela peut mettre en
péril le passage à l’échelle
3. Les tâches sont de tailles comparables => autrement il serait difficile de répartir
équitablement la charge de travail
4. Le nombre de tâches pourrait augmenter avec la taille du problème au lieu de la taille des
tâches  garantit la résolution de plus de complexité si on a plus de ressources de calcul
5. Identifier des solution alternatives à explorer dans les étapes suivantes  flexibilité

16/05/2022
Principes de la programmation parallèle
 Communications:
• Sans communications: Il n’y a pas
besoin de communications dans tout les
programmes parallèles. Il existent
certains cas où les tâches s’exécutent
indépendamment sans aucun partage
de données.
• Exemple: Traitement d’une image où l’on
souhaite inverser la couleur de chaque
pixel
• Le traitement de chaque pixel de l’image peut
se faire indépendamment de tous les autres
16/05/2022
Principes de la programmation parallèle
 Communications:
• Avec communications: dans la
majorité des programmes parallèles
les tâches échangent beaucoup de
données et ont besoin de
communications:
• Exemple: problème de diffusion de
chaleur
• Chaque point a besoin de connaitre la valeur
de donnée voisine afin d’évaluer sa propre
valeur

16/05/2022
Principes de la programmation parallèle
 Communications:
• Structure du canal de communication:
• Producteur: en possession des données
• Consommateur: en besoin des données
• Opérations de communication: messages à envoyer/recevoir

Canal de communication

Task1 Channel Task1

16/05/2022
Principes de la programmation parallèle
 Communications:
• Dans une décomposition fonctionnelle, il est plus facile de
conceptualiser les communications en suivant les le flot de données
entre tâches.
• Exemple: Représentation Modèle d’atmosphère

fonctionnelle du modèle
climatique Modèle
hydrologique
Modèle
Modèle de surface d’océan
terrestre

16/05/2022
Principes de la programmation parallèle
 Communications: On distingue plusieurs schémas de
communications:
• Locale/globale: chaque tâche communique avec un sous-ensemble de
tâches (tâches voisines). A l’opposé, dans une communication globale
une tâche communique avec plusieurs autres (tous les autres)

16/05/2022
Principes de la programmation parallèle
 Communications: On distingue plusieurs schémas de
communications:
• Locale/globale: chaque tâche communique avec un sous-ensemble de
tâches (tâches voisines). A l’opposé, dans une communication globale
une tâche communique avec plusieurs autres (tous les autres)
• Structurée/non structurée: La tâche et ses voisins communicants
forment une structure régulière (grille, arbre ). Dans une
communication non structurée le réseau de tâches est aléatoire.

16/05/2022
Principes de la programmation parallèle
 Communications: On distingue plusieurs schémas de
communications:
• Locale/globale: chaque tâche communique avec un sous-ensemble de
tâches (tâches voisines). A l’opposé, dans une communication globale
une tâche communique avec plusieurs autres (tous les autres)
• Structurée/non structurée: La tâche et ses voisins communicants
forment une structure régulière (grille, arbre ). Dans une
communication non structurée le réseau de tâches est aléatoire.
• Statique/dynamique: les partenaires de communication sont définis de
façon statique et ne changent pas dans le temps. Dans une
communication dynamiques, il peuvent être le résultat d’un calcul
intermédiaire et fréquemment varier.

16/05/2022
Principes de la programmation parallèle
 Communications: On distingue plusieurs schémas de communications:
• Locale/globale: chaque tâche communique avec un sous-ensemble de tâches
(tâches voisines). A l’opposé, dans une communication globale une tâche
communique avec plusieurs autres (tous les autres)
• Structurée/non structurée: La tâche et ses voisins communicants forment
une structure régulière (grille, arbre ). Dans une communication non
structurée le réseau de tâches est aléatoire.
• Statique/dynamique: les partenaires de communication sont définis de façon
statique et ne changent pas dans le temps. Dans une communication
dynamiques, il peuvent être le résultat d’un calcul intermédiaire et
fréquemment varier.
• Synchrones/asynchrones: le producteur et le consommateur coopèrent pour
toute opération de transfert/réception. En communication asynchrone, cette
coopération n’est pas nécessaire.

16/05/2022
Principes de la programmation parallèle
 Communications: On distingue plusieurs schémas de communications:
• Locale/globale: chaque tâche communique avec un sous-ensemble de tâches
(tâches voisines). A l’opposé, dans une communication globale une tâche
communique avec plusieurs autres (tous les autres).
• Un canal de communication est établi entre les éléments communicants de la
grille.

Exemple: Schémas de communication locale entre voisins de la grille 2D

16/05/2022
Principes de la programmation parallèle
 Communications: On distingue plusieurs schémas de communications:
• Locale/globale: chaque tâche communique avec un sous-ensemble de tâches
(tâches voisines). A l’opposé, dans une communication globale une tâche
communique avec plusieurs autres (tous les autres).
Exemple: S = σ𝒏𝒌=𝟎 𝒙𝒌
• Chaque tâche envoie communiquent indépendamment
S
avec la tâche principale
• Dégrade le parallélisme: complexité O(N), la somme
finale s’exécute en N x temps_addition.

x1 x2 x3 x4

Exemple: 4 tâches indépendantes

16/05/2022
Principes de la programmation parallèle
 Communications: On distingue plusieurs schémas de communications:
• Locale/globale: chaque tâche communique avec un sous-ensemble de tâches
(tâches voisines). A l’opposé, dans une communication globale une tâche
communique avec plusieurs autres (tous les autres).
Exemple: S = σ𝒏𝒌=𝟎 𝒙𝒌 S
∑
• Diviser le problème initial en plusieurs sous-problèmes de tailles Communication
équivalentes (Ex. sommes) s1 locale et s2
• Réitérer récursivement jusqu’à atteindre un problème de base que structurée
l’on peut diviser (Ex. somme de é nombres) ∑ ∑
• Parallélisme efficace lorsqu’un exécution concurrente des sous-
x1 x2 x3 x4
problèmes générés est possible
Exemple: Diviser pour régner
16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Conception des communications
• Validation du modèle des communications:
1. L’ensemble des tâches doit générer à peu près le même nombre de
communications. Autrement, il serait difficile de garantir un bon passage
à l’échelle.
2. Favoriser les communications locales (voisinage proche) plutôt que les
communications entre grand nombre de tâches.
3. Les tâches doivent s’exécuter en concurrence afin d’assurer une bonne
efficacité du parallélisme. Favoriser l’utilisation de la technique diviser
pour régner

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Problème de dépendance
• Définitions :
• Dépendance: il existe une dépendance entre les tâches d’un programme si l’ordre
d’exécution de ces tâches peut impacter le résultat final du programme
• La dépendance des données résulte du fait de l’utilisation multiple des mêmes
données par les plusieurs tâches différentes
• Le problème des dépendance est primordial dans le calcul parallèle car c’est un
principale obstacle à l’exécution concurrente

• Exemple: Dépendance des données

DO J = STARTVALUE,ENDVALUE
A(J) = A(J-1) ^ 2
END DO

16/05/2022
Principes de la programmation parallèle
 Parallélisme manuelle: Problème de dépendance
• Comment gérer les dépendances ?
• Mémoire partagée: Synchronisation des opérations de lecture et d’écriture
• Mémoire répartie: Echange des données et synchronisation

Figure: Visualisation des dépendances

16/05/2022
Principes de la programmation parallèle
 Agrégation:
• Il est parfois nécessaire de reconsidérer le résultat des phases
précédentes qui sont: décomposition + communication afin
d’améliorer les performance du programme et optimiser le
parallélisme au maximum.
• Nombre de tâche trop grand  processeurs non optimisé pour des petites
tâches à grand nombre
• Trop de communications
• L’agrégation consiste à recombiner des tâches afin de réduire le
nombre de tâches (taille plus grande) et de considérer la duplication
des données ou du calcul.

16/05/2022
Principes de la programmation parallèle
 Agrégation: Techniques d’agrégation
• Augmenter la granularité
• Décomposition  plusieurs tâches  coût élevé des communications 
Dégradation du parallélisme
• Réduire le coût des communications:
• Envoyer moins de données
• Envoyer moins de messages: manipulation de données de plus grande taille
• Coût de création des tâches  peut avoir un impact sur les performances du
programme si cette opération se produit fréquemment (Ex. recherche de
solution dans un arbre)

16/05/2022
Principes de la programmation parallèle
 Agrégation: Techniques d’agrégation
• Augmenter la granularité

Figure: 64 tâches, 1 point, 64x4 = 256 Figure: 4 tâches, 16 points, 4 x 4 = 16 communications,

communications/données 16x4 = 64 données

16/05/2022
Principes de la programmation parallèle
 Placement des tâches: Allouer les tâches aux ressources de calcul
• Objectif: Minimiser le temps global d’exécution
• Répartir les tâches concurrentes sur les différentes unités de calcul
• Placer les tâches communicantes sur le même processeur, pour minimiser le
coût des communications
• Répartir la charge de façon équilibrée entre différents processeurs
• Minimiser les accès extérieurs

16/05/2022
Principes de la programmation parallèle
 Placement des tâches: Allouer les tâches aux ressources de calcul
• Techniques de placements:
• Placement direct: Décomposition de domaine(tâches de taille égale) +
communication structurée (locale/globales). Les tâches sont placées en minimisant
les communications. On considère la possibilité d’agrégation des tâches associées à
un processeur (tâche gros grain/processeur)
• Algorithmes d’équilibrage de charge (Load Balancing Algorithms): en cas de tâches
avec des charges de calcul et de communication variable et non structuré, il est
possible d’utiliser des algorithme d’équilibrage de charge dynamiques.
• Algorithmes d’ordonnancement : en cas de décomposition fonctionnelle, les tâches
sont courtes et à durée limitée. Il est possible d’utiliser les techniques
d’ordonnancement permettant de maximiser l’utilisation des processeurs
• Associer les tâches aux processeurs libres
16/05/2022
Principes de la programmation parallèle
Algorithmes d’équilibrage de charge (Load Balancing Algorithms):
Algorithme Description

Méthode de dichotomie • Consiste à diviser récursivement les tâches jusqu’à atteindre le nombre de
(Recursive bisection) tâches souhaité (placement direct sur les processeurs)
• Approche: « diviser pour régner »
Algorithmes locaux • La charge d’un processeur est comparée (de façon régulière) avec se voisins
les plus proches; et une réorganisation du placement en résulte si
nécessaire
• Exemple: Processeurs organisés en grille/mesh
Méthodes probabilistes • Allocation aléatoire des tâches (choix aléatoire de processeurs)
• Ne marche que lorsque le nombre de tâches est largement supérieurs au
nombre de processeurs

16/05/2022
Placement cyclique • Chacun des P processeur est alloué à chaque P ième tâche (tâches
Principes de la programmation parallèle
 Placement des tâches: Algorithmes d’ordonnancement
• Structure : Worker/Manager
• Workers: le problème est réparti en tâche worker
• 1 worker par processeur
• Allouer les sous-problèmes (tâches) au workers
• Manager: Fournit la répartition du travail sur les différents workers

16/05/2022
Principes de la programmation parallèle
 Placement des tâches: Algorithmes d’ordonnancement
• Structure : Worker/Manager
• Schéma hiérarchique: chaque groupe de workers a son propre submanager
• Schéma décentralisé: les workers possèdent leur propre pile de tâches et
peuvent s’en approvisionner chez les voisins si nécessaire. Absence de
manager.

16/05/2022
Principes de la programmation parallèle
 Placement des tâches:
• Vérification de la stratégie de placement des tâches:
1. Pour les schémas de contrôle centralisé, il faut vérifier qu’il n’y a pas de
goulot d’étranglement (bottleneck)
2. Pour les stratégies de placement dynamique l’évaluation du coût du
placement est nécessaire. Les schémas probabilistes et cycliques ont des
coûts moindres.
3. Pour les méthodes probabilistes, il est important d’avoir un nombre de
minimal de tâche pour garantir l’efficacité de la méthode.

16/05/2022
Analyse des performances
 Définitions et objectifs
 Loi d’Amdhal
 Loi de Gustafson-Barsis
 Métrique de Karp-Flatt
 Métrique d’iso-efficacité

16/05/2022
Analyse des performances
• Que faire ?
• Analyse du temps d’exécution des algorithmes parallèles

• Pourquoi faire ?
• Déterminer si le programme mériterait l’effort de
parallélisation
• Mesurer le gain du programme parallèle versus séquentiel

16/05/2022
Analyse des performances
Métrique Type d’analyse

Loi d’Amdhal Déterminer si le programme mériterait l’effort de

parallélisation

Loi de Gustafson-Barsis Evalue les performances du programme parallèle

Métrique de Karp-Flatt Définir les limites du parallélisme

Métrique d’iso-efficacité Evalue la capacité d’un programme au passage à

l’échelle (scalabilité)

16/05/2022
Analyse des performances

Soient :
 n : Taille du problème
 p : Nombre de processeurs

• Un programme parallèle est constitué de:

• Partie parallèle
• Partie séquentielle Soient:
 σ(n) : portion séquentielle
• Surcoût lié au parallélisme
 ϕ(n): portion parallèle
• Communications  К(n, p) : Surcoût de parallélisme
• Calculs redondants
16/05/2022
Analyse des performances

Soient : Soient:
 n : Taille du problème  σ(n) : portion séquentielle
 p : Nombre de processeurs  ϕ(n): portion parallèle
 К(n, p) : Surcoût de parallélisme

𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒔é𝒒𝒖𝒆𝒏𝒕𝒊𝒆𝒍𝒍𝒆

• Accélération (Speed−up) =
𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒑𝒂𝒓𝒂𝒍𝒍é𝒍𝒆
𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒔é𝒒𝒖𝒆𝒏𝒕𝒊𝒆𝒍𝒍𝒆
• Efficacité (Efficiency) =
𝑵𝑩𝑷𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒖𝒓𝒔𝑼𝒕𝒊𝒍𝒊𝒔é𝒔 ∗ 𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒑𝒂𝒓𝒂𝒍𝒍é𝒍𝒆

16/05/2022
Analyse des performances

• Temps d′ exécution séquentielle (p =1 , un seul processeur):

𝑻(𝒏, 𝟏) = 𝝈 𝒏 + ϕ(n)

• En supposant que la portion parallèle se divise parfaitement sur les p

processeurs, on obtient:
ϕ𝒏
𝑻 𝒏, 𝒑 ≥ 𝝈 𝒏 + + К(n, p)
𝒑

16/05/2022
Analyse des performances
 Définitions et objectifs
 Loi d’Amdhal
 Loi de Gustafson-Barsis
 Métrique de Karp-Flatt
 Métrique d’iso-efficacité

16/05/2022
Analyse des performances
• Loi d’Amdhal:
• Si le surcoût du parallélisme est négligé (К(n, p) = 0), alors:
𝑻(𝒏,𝟏)
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏 𝒏, 𝒑 =
𝑻(𝒏,𝒑)

𝝈 𝒏 + ϕ(n)
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
ϕ(n)
𝝈 𝒏 +
𝒑
Portion séquentielle Portion parallèle
Nombre de processeurs
16/05/2022
Analyse des performances
• Loi d’Amdhal:
• Si le surcoût du parallélisme est négligé (К(n, p) = 0), alors:

𝝈 𝒏 + ϕ(n)
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
ϕ(n)
𝝈 𝒏 +
𝒑
• Soit S la proportion de la partie séquentielle intrinsèque :
𝝈 𝒏
𝑺=
𝝈 𝒏 + ϕ(n)

16/05/2022
Analyse des performances
• Loi d’Amdhal:
• Si le surcoût du parallélisme est négligé (К(n, p) = 0), alors:
𝟏
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
1
𝑺+ (𝟏 − 𝑺)
𝒑

Loi d’Amdhal : Si S est la fraction des opérations qui doivent absolument s’exécuter en parallèle (où 𝟎 ≤ 𝑺 ≤
𝟏), alors l’accélération maximale possible en exécution parallèle sur p processeurs est égale à :
𝟏
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏𝒎𝒂𝒙𝒊𝒎𝒂𝒍𝒆 𝒏, 𝒑 =
1
𝑺+ (𝟏 − 𝑺)
𝒑
On en déduit la borne maximale :
𝟏 𝟏
𝐥𝐢𝐦 =
1
𝑺 + (𝟏 − 𝑺) 𝑺
𝒑→∞
16/05/2022 𝒑
Analyse des performances
• Loi d’Amdhal:

16/05/2022
Analyse des performances
• Exercice 1:
• Quel est le maximum d’accélération que l’on peut obtenir avec :
• 10 processeurs
• 85 % du calcul est parallélisable

16/05/2022
Analyse des performances
• Exercice 1:
• Quel est le maximum d’accélération que l’on peut obtenir avec :
• 10 processeurs
• 85 % du calcul est parallélisable

• S = 15%
𝟏
• 𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏 𝒏, 𝒑 ≤ 1 ≈ 𝟒. 𝟐𝟓
𝟎.𝟏𝟓+ 𝟏𝟎
𝟏 −𝟎.𝟏𝟓

16/05/2022
Analyse des performances
• Discussion: « Loi d’Amdhal »
• La loi d’Amdhal donne une estimation optimiste du
parallélisme:
• Ignore le surcoût dû au parallélisme К(n, p)
• Pour un problème de taille fixe n:
• La loi d’Amdhal montre la diminution du temps de calcul lorsque p
augmente
• Pour un nombre de processeurs fixe p, l’accélération est une
fonction croissante de la taille du problème (n):
• Lorsque n augmente:
• S peut diminuer
ϕ𝒏
• 𝒑
devient beaucoup plus important que К(n, p)
 La loi d’Amdhal peut sous-estimer l’accélération pour des
problème large
16/05/2022
Analyse des performances
 Définitions et objectifs
 Loi d’Amdhal
 Loi de Gustafson-Barsis
 Métrique de Karp-Flatt
 Métrique d’iso-efficacité

16/05/2022
Analyse des performances
• Gustafson-Barsis:
• Admettons que la taille n du problème augmente avec le nombre de
processeurs p
• La loi d’Amdhal suppose que le taille du problème est fixe
• Soit S la proportion de temps dépensée par un calcul parallèle sur p
processeurs dans le traitement de la partie séquentielle intrinsèque:

𝝈 𝒏
𝑺=
ϕ(n)
𝝈 𝒏 +
𝒑

16/05/2022
Analyse des performances
• Gustafson-Barsis:
ϕ(n)
𝒑
• Alors: 1 – S =
ϕ(n)
𝝈 𝒏 +
𝒑

ϕ(n)
𝝈 𝒏 = (𝝈 𝒏 + )S
𝒑

ϕ(n)
 ϕ(n) = (𝝈 𝒏 + ) (1-S) p
𝒑

16/05/2022
Analyse des performances
• Gustafson-Barsis:
𝝈 𝒏 + ϕ(n)
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
ϕ(n)
𝝈 𝒏 +
𝒑
ϕ(n)
𝑺 + 𝟏 − 𝑺 𝒑 (𝝈 𝒏 +
𝒑
)
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
ϕ(n)
(𝝈 𝒏 +
𝒑
)

𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏 𝒏, 𝒑 ≤𝑺+ 𝟏−𝑺 𝒑 𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏 𝒏, 𝒑 ≤𝒑+ 𝟏−𝒑 𝑺

16/05/2022
Analyse des performances
• Loi de Gustafson-Barsis: étant donné un programme parallèle de
taille n exécuté sur p processeurs, si S est le temps d’exécution de la
partie séquentielle du calcul alors l’accélération maximale est égale à:

𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏𝒎𝒂𝒙𝒊𝒎𝒂𝒍𝒆 𝒏, 𝒑 = 𝒑 + 𝟏 − 𝒑 𝑺

16/05/2022
Analyse des performances
• Discussion: « Gustafson-Barsis »
• Traite les problèmes de plus grande taille en utilisant plus de
processeurs (scaled speed-up)
• Le surcoût du parallélisme est négligé
Surestimation de l’accélération
• La meilleure accélération possible est égale au nombre de
processeurs:
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏 ≤ 𝒑 + 𝟏 − 𝒑 𝑺 ⇒ 𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏 ≤ 𝒑
• Si S=1 c’est qu’il n’y a pas d’accélération

16/05/2022
Analyse des performances
• Exercice 2: « Gustafson-Barsis »

• Quelle l’accélération maximale d’une application qui

tourne sur 64 cœurs et passant 5 % de son temps dans la
partie séquentielle ?

16/05/2022
Analyse des performances
• Exercice 2: « Gustafson-Barsis »

• Quelle l’accélération maximale d’une application qui tourne sur

64 cœurs et passant 5 % de son temps dans la partie
séquentielle ?
• S = 0.05

 𝑺𝒑𝒆𝒆𝒅𝒖𝒑 ≤ 𝟔𝟒 + 𝟏 − 𝟔𝟒 𝒙 𝟎. 𝟎𝟓 ≈ 𝟔𝟎. 𝟖𝟓

16/05/2022
Analyse des performances
 Définitions et objectifs
 Loi d’Amdhal
 Loi de Gustafson-Barsis
 Métrique de Karp-Flatt
 Métrique d’iso-efficacité

16/05/2022
Analyse des performances
• Métrique de « Karp-Flatt »:
• Amdhal et Gustafson-Barsis surestime l’accélération du fait de
l’élimination du surcoût du parallélisme ( К(n, p) = 0 ) .
• La fraction séquentielle déterminée expérimentalement ℮ prend en
considération:
• Le surcoût du parallélisme
• En plus d’autres sources de surcoût:
• Temps de démarrage des processus
• Temps de synchronisation
• Mauvaise répartition de la charge
• Surcoût liée à l’architecture

16/05/2022
Analyse des performances
• Métrique de « Karp-Flatt »:
• La fraction séquentielle déterminée expérimentalement ℮ est
définie comme suit:
𝝈 𝒏 +К(n, p)
e (n,p) =
𝝈 𝒏 +ϕ(n)

• e(n,p) est calculée en exécutant le programme une fois sur un seul

processeur et une autre fois sur p processeurs et ensuite calculer la
fraction.

16/05/2022
Analyse des performances
• Métrique de « Karp-Flatt »:
• Soit A(n,p) l’accélération du programme parallèle mesurée
expérimentalement pour p processeurs:

𝑻(𝒏,𝟏)
A (n,p) =
𝑻(𝒏,𝒑)

16/05/2022
Analyse des performances
• Métrique de « Karp-Flatt »: Détermination de e en fonction d’une
accélération donnée ?
• Rappel:
• La fraction séquentielle intrinsèque (loi d’Amdhal):
𝝈 𝒏 𝝈 𝒏
𝑺= =
𝝈 𝒏 + ϕ(n) 𝑻(𝒏, 𝟏)

• 𝑶𝒏 𝒆𝒏 𝒅é𝒅𝒖𝒊𝒕: 𝝈 𝒏 = 𝑻 𝒏, 𝟏 𝑺 et ϕ(n) = 𝑻 𝒏, 𝟏 (𝟏 − 𝑺)

16/05/2022
Analyse des performances
• Métrique de « Karp-Flatt »: Détermination de e en fonction d’une
accélération donnée ?
• Si on ignore le surcoût du parallélisme on obtient:
ϕ(n)
𝑻 𝒏, 𝒑 = 𝝈 𝒏 + (NB: Nous supposons un équilibrage de charge parfait !!)
𝒑
𝑻 𝒏,𝟏 (𝟏 −𝑺)
 𝑻 𝒏, 𝒑 = 𝑻 𝒏, 𝟏 𝑺 +
𝒑
• On obtient finalement:
𝑻(𝒏,𝟏) 𝟏
A (n,p) = =
𝑻(𝒏,𝒑) 𝑺+(𝟏 −𝑺)/𝒑

16/05/2022
Analyse des performances
• Métrique de « Karp-Flatt »: Détermination de e en fonction d’une
accélération donnée ?
𝑻(𝒏,𝟏) 𝟏
A (n,p) = =
𝑻(𝒏,𝒑) 𝑺+(𝟏 −𝑺)/𝒑
• Soit e(n,p) la fraction séquentielle déterminée expérimentalement:
• Calculant e(n,p) en fonction de A(n,p) (mesurée expérimentalement):
𝟏 𝟏
−
𝑨(𝒏, 𝒑) 𝒑
e(n,p) =
𝟏
𝟏 −
𝒑

16/05/2022
Analyse des performances
• Exercice 3: Métrique de « Karp-Flatt »:
• L’analyse des performances d’un programme parallèle sur 1, 2, .. 8
processeurs donne les mesures suivantes:

#processeurs 2 3 4 5 6 7 8

Speedup 1.82 2.5 3.08 3.57 4.00 4.38 4.72

• Calculer la métrique de Karp-Flatt ? Que peut-on en déduire ?

16/05/2022
Analyse des performances
• Exercice 3: Métrique de « Karp-Flatt »:
• L’analyse des performances d’un programme parallèle sur 1, 2, .. 8
processeurs donne les mesures suivantes:
#processeurs 2 3 4 5 6 7 8

Speedup 1.82 2.5 3.08 3.57 4.00 4.38 4.72

e(n,p ) 0.1 0.1 0.1 0.1 0.1 0.1 0.1

• e(n,p) est constante, cela signifie que la fraction séquentielle de 10%

est la principale raison de la faible accélération à l’échelle de 8
processeurs.
16/05/2022
Analyse des performances
• Exercice 4: Métrique de « Karp-Flatt »:
• L’analyse des performances d’un programme parallèle sur 1, 2, .. 8
processeurs donne les mesures suivantes:

#processeurs 2 3 4 5 6 7 8

Speedup 1.87 2.61 3.23 3.73 4.14 4.46 4.71

• Calculer la métrique de Karp-Flatt ? Que peut-on en déduire ?

16/05/2022
Analyse des performances
• Exercice 4: Métrique de « Karp-Flatt »:
• L’analyse des performances d’un programme parallèle sur 1, 2, .. 8
processeurs donne les mesures suivantes:
#processeurs 2 3 4 5 6 7 8

Speedup 1.87 2.61 3.23 3.73 4.14 4.46 4.71

e(n,p) 0.07 0.075 0.08 0.085 0.09 0.095 0.1

• La croissance du e(n,p) en fonction du nombre de processeurs signifie

que le surcoût du parallélisme est la principale limitation de
l’accélération et non pas
16/05/2022
Analyse des performances
 Définitions et objectifs
 Loi d’Amdhal
 Loi de Gustafson-Barsis
 Métrique de Karp-Flatt
 Métrique d’iso-efficacité

16/05/2022
Analyse des performances
• Métrique d’iso-efficacité:
• Une bonne capacité au passage à l’échelle est la capacité d’un
programme parallèle à augmenter ses performances au fur et à
mesure que le nombre de processeurs augmente.
• L’iso-efficacité est la mesure de la capacité du programme parallèle à
évoluer (scalability).

16/05/2022
Analyse des performances
• Métrique d’iso-efficacité:
• Soit T0 (n,p) le temps total passé par l’ensemble des processus parallèles:
𝑻𝟎 𝒏, 𝒑 = 𝒑 𝒙 𝑻𝒆𝒎𝒑𝒔 𝒑𝒂𝒓𝒂𝒍𝒍è𝒍𝒆 − 𝑻𝒆𝒎𝒑𝒔 𝒔é𝒒𝒖𝒆𝒏𝒕𝒊𝒆𝒍
Soit:
𝑻𝟎 𝒏, 𝒑 = (p −𝟏)𝝈 𝒏 + p К(n, p)

• T0 (n,p) inclut :
• Le temps passé par p-1 processeurs a effectuer le calcul séquentiel intrinsèque
• Le temps passé par tous les processeurs dans les communications et les calculs
redondants

16/05/2022
Analyse des performances
• Métrique d’iso-efficacité:
• Soit T0 (n,p) le temps total passé par l’ensemble des processus parallèles:
𝝈 𝒏 + ϕ(n)
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
ϕ(n)
𝝈 𝒏 + + К(n, p)
𝒑
𝒑(𝝈 𝒏 +ϕ(n))
𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
𝝈 𝒏 + ϕ(n) +(𝒑−𝟏)𝝈 𝒏 +pК(n, p)

𝒑(𝝈 𝒏 +ϕ(n))
⇨ 𝑨𝒄𝒄é𝒍é𝒓𝒂𝒕𝒊𝒐𝒏(𝒏, 𝒑) ≤
𝝈 𝒏 + ϕ(n) + 𝑻𝟎 𝒏,𝒑

16/05/2022
Analyse des performances
• Métrique d’iso-efficacité:
• Soit T (n,1) le temps du calcul séquentiel pour résoudre le problème:
Rappel:
𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒔é𝒒𝒖𝒆𝒏𝒕𝒊𝒆𝒍𝒍𝒆
• Efficacité (Efficiency) =
𝑵𝑩𝑷𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒖𝒓𝒔𝑼𝒕𝒊𝒍𝒊𝒔é𝒔 ∗ 𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒑𝒂𝒓𝒂𝒍𝒍é𝒍𝒆
𝝈 𝒏 +ϕ(n)
• Efficacité 𝑛, 𝑝 ≤
𝒑(𝝈 𝒏 +
ϕ(n)+К(n, p))
𝒑

𝟏 𝟏
⇨ Efficacité 𝑛, 𝑝 ≤ ≤
𝟏+
T0 (n,p) 𝟏+
T0 (n,p)
𝝈 𝒏 + ϕ(n) T (n,1)

16/05/2022
Analyse des performances
• Métrique d’iso-efficacité:
• Soit T (n,1) le temps du calcul séquentiel pour résoudre le problème:
𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒔é𝒒𝒖𝒆𝒏𝒕𝒊𝒆𝒍𝒍𝒆
Rappel: Efficacité (Efficiency) = 𝑵𝑩 ∗ 𝑻𝒆𝒎𝒑𝒔 𝒅′ 𝒆𝒙é𝒄𝒖𝒕𝒊𝒐𝒏 𝒑𝒂𝒓𝒂𝒍𝒍é𝒍𝒆
𝑷𝒓𝒐𝒄𝒆𝒔𝒔𝒆𝒖𝒓𝒔𝑼𝒕𝒊𝒍𝒊𝒔é𝒔

𝟏 𝟏
Efficacité 𝑛, 𝑝 ≤ ≤
𝟏+
T0 (n,p) T
𝟏+ 0
(n,p)
𝝈 𝒏 + ϕ(n) T (n,1)

Efficacité 𝑛,𝑝
⇨ 𝑇 𝑛, 1 ≥ T (n,p)
1 −Efficacité 𝑛,𝑝 0

16/05/2022
Analyse des performances
• Métrique d’iso-efficacité:
• Notons:
• Ɛ(n,p) l’efficacité du programme
Ɛ(n,p)
• 𝑪= , constante d’efficacité (Ɛ(n,p) constante)
𝟏 − Ɛ(n,p)

• Définition: Afin de maintenir le même niveau d’efficacité avec

l’augmentation du nombre de processeurs, la taille n du problème doit
augmenter afin de satisfaire la condition:
𝑇 𝑛, 1 ≥ 𝐶 𝑇0(𝑛, 𝑝)
16/05/2022
Analyse des performances
• Discussion: Métrique d’iso-efficacité
• Relation d’iso-efficacité:
• Utilisée pour déterminer le nombre de processeurs pour lequel l’efficacité est
maintenue
• L’augmentation du nombre de processeurs  Surcoût du parallélisme
• Il faut augmenter la complexité du problème afin de maintenir l’efficacité
• Passage à l’échelle:
• La taille maximale atteignable d’un problème est limitée par la taille de la
mémoire primaire
• La taille mémoire est une fonction linéaire avec le nombre de processeurs
• La mémoire/processeur doit augmenter de M(n)/p, où M(n) est la quantité mémoire
nécessaire pour un problème de taille n et p est le nombre de processeurs.

16/05/2022
Analyse des performances
• Exercice 5: Métrique d’iso-efficacité
• Algorithme de réduction
• Définition: Un algorithme de réduction est un algorithme qui permet
de transformer un algorithme complexe en un ou plusieurs instances
d’un autre problème plus simple.
• Réduction séquentielle: O(n)
• Réduction parallèle: O(log(p))

• Quelle est la condition d’iso-efficacité ?

16/05/2022
Analyse des performances
• Exercice 5: Métrique d’iso-efficacité
• Algorithme de réduction
• Définition: Un algorithme de réduction est un algorithme qui permet
de transformer un algorithme complexe en un ou plusieurs instances
d’un autre problème plus simple.
• Réduction séquentielle: O(n)
• Réduction parallèle: O(log(p))
• Le temps séquentiel: T(n,1) = n
• Chacun des processeurs participe à ce calcul : 𝑻𝟎 𝒏, 𝒑 = O(plog(p))

𝒏 ≥ 𝑪 plog(p)
16/05/2022
Analyse des performances
• Exercice 6: Métrique d’iso-efficacité
• Méthode des différences finies: est une technique courante de recherche
de solutions approchées d’équations aux dérivées partielles qui consiste à
résoudre un système liant les valeurs des fonctions inconnues en certains
points suffisamment proches les uns des autres.
• Le problèmes est résolu en grille de taille : nxn
𝑛 𝑛
• Chaque processeur est responsable d’une sous grille de taille: x
𝑝 𝑝
• A chaque étape chaque processeur envoie à𝑛ses voisins des valeurs approximatives;
Une communication nécessite un temps: o( )
𝑝
• Quelle les la relation d’efficacité nécessaire pour une meilleure scalabilité
du problème?

16/05/2022
 Supplément
• Rappel sur le calcul de la complexité algorithmique

16/05/2022
Supplément: Complexité
 Complexité: La complexité d’un algorithme est le nombre
d’opérations élémentaires qu’il doit effectuer pour mener à bien un
calcul en fonction de la taille des données d’entrée.
Augmentation du temps de calcul d’un algorithme en fonction de la taille des
données

• Taille des données

• Temps de calcul

16/05/2022
Supplément: Complexité
 Complexité: Taille des données
• Nombre d’éléments
• Nombre de bits nécessaires à la représentation des données
• Polynômes : le degré, le nombre de coefficients non nuls
• Matrices m × n : max(m,n), m.n, m + n ;
• Graphes : nombre de sommets, nombre d’arcs, produit des deux
• Listes, tableaux, fichiers : nombre de cases, d’éléments ;
• Mots : leur longueur

16/05/2022
Supplément: Complexité
 Complexité: Temps de calcul
• Quantité de données
• Leur encodage : représentation
• Qualité du code engendré par le compilateur
• Nature et la rapidité des instructions du langage
• Qualité de la programmation
• Efficacité de l’algorithme (Augmentation du temps de calcul en fonction de la
taille des données )

16/05/2022
Supplément: Complexité
 Complexité: Temps de calcul
• Quantité de données
• Leur encodage : représentation
• Qualité du code engendré par le compilateur
• Nature et la rapidité des instructions du langage
• Qualité de la programmation
• Efficacité de l’algorithme (Augmentation du temps de calcul en fonction de la
taille des données )

16/05/2022
Supplément: Complexité
 Complexité: Temps de calcul:
Nombre d’opérations fondamentales à exécuter
• Opérations fondamentales

Problème Opération fondamentale

Recherche d’un élément dans une liste Comparaison
Multiplication de matrices Multiplication + Addition
Additions d’entiers binaires Opération binaire
Tri de liste Comparaison + déplacement

16/05/2022
Supplément: Complexité
 Complexité: Temps de calcul:
Complexité temporelle  coût de l’ensemble des opérations en temps
• Solution 1: Multiplier le nombre d’opérations par le coût moyen de toutes les
opérations
• Solution 2: pour un algorithme avec essentiellement des calculs numériques,
compter les opérations coûteuses (multiplications, racine, exponentielle, …)
• Solution 3: compter le nombre d’appels à l’opération la plus fréquente

16/05/2022
Supplément: Complexité
 Calcul de la complexité d’un algorithme:
 Complexité dans le meilleur cas
 Complexité en moyenne
 Complexité dans le pire cas: le plus utilisé

 Soit A un algorithme, n un entier, Dn l’ensemble des entrées de taille

n et une entrée d ∈ Dn. Posons : coût A (d ) le nombre d’opérations
fondamentales effectuées par A avec l’entrée d.

16/05/2022
Supplément: Complexité
 Calcul de la complexité d’un algorithme: Complexité dans le pire cas
Elle est donnée par :
MaxA (n) = max {coûtA (d ) / d∈ Dn } .

• C’est cette complexité qui est généralement calculée car c’est une
borne supérieure du temps d’exécution associé à une entrée
quelconque

16/05/2022
Supplément: Complexité
 Calcul de la complexité d’un algorithme: Complexité dans le pire cas
• Calcul du factoriel

FACTORIEL (n)
entrée : un entier n
sortie : n!
1. Si n = 0
2. alors résultat ← 1
3. sinon
4. résultat ← n × FACTORIEL(n−1)
5. fin si
6. retourne résultat

16/05/2022
Supplément: Complexité
 Calcul de la complexité d’un algorithme: Complexité dans le pire cas
• Calcul du factoriel
• Soit T(n) le temps d’exécution en fonction de l’argument n (c1: test, c2 :
multiplication).
FACTORIEL (n=1):
T(0) = c1
T(1) = c1 + c2
T(n) = c1 + c2 + T(n-1)
T(n) = c1 + c2 + (c1 + c2 + T(n-2))
…
T(n) = (n -1)c1 + (n-2)c2 + (T(n – (n-1)))
T(n) = n c1 + (n-1)c2

16/05/2022
Supplément: Complexité
 Calcul de la complexité d’un algorithme: Complexité dans le pire cas
• Calcul du factoriel
• Soit T(n) le temps d’exécution en fonction de l’argument n (c1: test, c2 :
multiplication).
FACTORIEL (n=1):
T(0) = c1
T(1) = c1 + c2
Supposons que: T(n) = c1 + c2 + (n-1) (c1 + c2 ) pour n>=1
On a:
T(n+1) = c1 + c2 + T(n)
T(n+1) = c1 + c2 + c1 + c2 + (n-1) (c1 + c2 )
T(n+1) = c1 + c2 + n(c1 + c2)

Récurrence: Comme c’est vrai pour n=1 et n+1  c’est vrai quelque soit n

16/05/2022
Supplément: Complexité
 Calcul de la complexité d’un algorithme: Complexité dans le pire cas
• Calcul du factoriel
• Soit T(n) le temps d’exécution en fonction de l’argument n (c1: test, c2 :
multiplication).
FACTORIEL (n=1):
T(0) = c1
T(1) = c1 + c2
Supposons que: T(n) = c1 + c2 + (n-1) (c1 + c2 ) pour n>=1
On a: Complexité = O(n)
T(n+1) = c1 + c2 + T(n)
T(n+1) = c1 + c2 + c1 + c2 + (n-1) (c1 + c2 )
T(n+1) = c1 + c2 + n(c1 + c2)

Récurrence: Comme c’est vrai pour n=1 et n+1  c’est vrai quelque soit n

16/05/2022
Supplément: Complexité
 Exercice: Calcul de la complexité
On considère, pour effectuer la recherche d’un élément dans un tableau, la
recherche séquentielle et la recherche dichotomique. On s’intéresse à leur
complexité temporelle.
Pour cela, considérer un tableau ayant mille éléments (version trié, et
version non trié).
1. Pour chaque algorithme, et pour chaque version du tableau, combien de
comparaisons sont à effectuer pour :
a) Trouver un élément qui y figure ?
b) Trouver un élément qui n'y figure pas ?
2. Quels sont les cas où le tableau est parcouru complètement et les cas où
un parcours partiel est suffisant ?
3. Conclure en donnant la complexité temporelle pour chaque algorithme
16/05/2022
Supplément: Complexité
 Exercice: Calcul de la complexité
Opérations élémentaires retenues: les comparaisons
1. Recherche séquentielle dans un tableau de 1000 éléments non trié
11. élément ne s’y trouvant pas (complexité au pire) : 1000 comparaisons (tableau est parcouru
complètement)
12. élément qui s’y trouve (complexité moyenne) : n/2=500 comparaisons (parcours partiel
suffisant)
• Algorithme en O(n)
2. Recherche séquentielle dans un tableau trié
13. élément ne s’y trouvant pas (complexité au pire) : 1000 comparaisons (parcours
partiel suffisant)
14. élément qui s’y trouve (complexité moyenne) : n/2=500 comparaisons (parcours
partiel suffisant)
• Algorithme en O(n)
3. Recherche dichotomique (dans un tableau non trié): impossible
16/05/2022
 Questions

16/05/2022