Introduction à la Programmation Parallèle et Distribuée - Exercices ...

Introduction à la Programmation Concurrente, Distribuée et Parallèle

Ingénieur 3 ère année

Denivaldo LOPES

Liste d'exercices

1. Notions de Programmation Séquentielle et Parallèle

a. Donnez une définition précise des thèmes suivants:

. parallélisme physique

. parallélisme logique

b. Pour chacun des paradigmes suivants, proposez un exemple d'algorithme
simple :

. séquentiel

. parallèle physique

. parallèle logique




Note: utilisez l'exemple du tutoriel comme base.

c. Quelles sont les paramètres utilisés par la classification de Flynn?

d. Définissez et expliquez les architectures suivantes en utilisant la
classification de Flynn:

. SISD (Single Instruction stream, Single Data stream)

. SIMD (Single Instruction stream, Multiple Data stream)

. MISD (Multiple Instruction stream, Single Data stream)

. MIMD (Multiple Instruction stream, Multiple Data stream)

e. Définissez et expliquez les concepts suivants:

. La granularité

. Le Facteur d'accélération ou Speedup

. L'efficacité ou efficiency

f. Un problème donné prend 1s quand il est exécuté sur une machine
monoprocesseur, et prend 300 ms quand il est exécuté sur une machine
parallèle réelle avec 4 processeurs. Répondez aux questions suivantes:

. Quel est le facteur d'accélération et l'efficacité?

. Pourquoi la machine parallèle réelle avec 4 processeurs est incapable
de résoudre le problème en 250 ms (c'est à dire, Tp= Ts / n, où Tp est
le temps pris par le programme parallèle, Ts est le temps pris par le
programme séquentiel, et n est le nombre de processeurs de la machine
parallèle)?



g. Donnez les différentes classifications du parallélisme par rapport au
modèle de programmation adopté pour paralléliser un algorithme. Utilisez le
polynôme suivant pour expliquer les différents cas:
p[i]=a+b*x^2+c*x^4+d*x^6+e*x^8+f*x^10

h. Donnez des exemples d'utilisations de la programmation parallèle
(physique ou logique) et distribuée.



2. Paradigmes de la programmation Concurrente: Synchronisation et
Communication

a. Définissez les concepts de processus et de thread. Expliquez quelles
sont les différences entre eux.

b. Quelles sont les ressources partagées entre threads d'un même processus
et quelles sont les ressources privées à chaque threads?

c. Quels sont les différents états d'un processus? Expliquez chaque état.

d. Donnez et expliquez les différents types de processus.

e. Qu'est-ce que c'est la multitâche de préemption et de non-préemption?
Linux est un système d'exploitation qui utilise la préemption ou non
préemption (Note: considère les processus d'utilisateurs et du noyau
«kernel»)?

f. Définissez les notions d'action atomique, de section critique, de l'état
de course (race condition)? Expliquez chaque cas.

g. Quelles sont les propriétés à assurer dans une section critique?

h. Expliquez les notions suivantes:

. Busy waiting

. Barrier

. Sémaphore

. Monitors

i. Expliquez les primitives send et receive . Quelles sont les modalités
de synchronisation de ces primitives?

j. Donnez votre définition personnelle de RPC et Rendez-vous? Vous pouvez
utiliser une figure pour expliquer.



3. La Programmation concurrente en Java: Threads

a. Expliquez les méthodes suivantes de la classe Thread: run, start,
join, sleep et yield.

b. Écrivez un programme en Java qui utilise deux threads et un buffer
limité et circulaire avec les comportements suivants (vous pouvez utiliser
un sémaphore ou un moniteur pour implémenter la section critique):

. Un premier thread va lire au clavier un message et va l'écrire dans
un buffer limité et circulaire.

. Le second thread va lire à partir du buffer limité et circulaire son
contenu. Après, le thread va l 'écrire dans un fichier.

c. Utiliser une barrier et plusieurs threads pour implémenter un programme
en Java qui réalise l'addition de tous les éléments d'un tableau A[m, n].

Suggestion:

. La manière plus simple de résoudre ce problème est d'utiliser un
programme séquentiel.
program addition_elements
{
int sum, a[m,n];
...
sum = 0 ;
for (int i=0; i < m; i++)
for (int j=0; j < n; j++)
sum= sum + a[i, j];
...
print(sum);
}



. Quand on utilise plusieurs threads et une barrier, on peut diviser le
tableau en régions et donner chaque région par un thread différent. La
barrier est utilisée pour assurer que l'addition de tous les résultats
partiaux sera exécutée, seulement après que le dernier thread est
finis l'addition de sa région.

program addition
{
int number_workers=m;
int sum_total, sum[m], a[m,n]; // sum_total=0; sum[0...m-1]=0; a[0...m,
0...n]=?
barrier b(m);
...
read_all_elements(a); // read m*n values and put them into the array 'a'
...
for(int i=0; i < m; i++)
create_thread( worker(b, sum, i, a, i, n) );
...
while(get(barrier) > 0) yield();
for(int i=0; i < m; i++)
sum_total= sum_total + sum[i];
print(sum_total);
}

worker(barrier b, int sum[],int index_sum, int a[ ], int m, int n )
{
for (int j=0; j < n; j++)
sum[index_sum]= sum[index_sum] + a[m, j];
decrease(barrier);
}

4. Passage de message en Java

a. Écrivez un programme en Java qui implémente un buffer limité et
circulaire et est appelé à distance. Quand un message arrive au serveur du
buffer, il va créer un thread. Ce thread accède au buffer pour lire ou
écrire un élément. Attention: le buffer peut accepter à plusieurs demandes,
mais seulement un thread à la fois peut accéder à la région critique.

Note: écrivez un programme avec passage de message asynchrone et autre avec
passage de message synchrone.

b. Implémenter un simple serveur ( et client) de fichiers qui utilise le
passage de message asynchrone et synchrone.

Note: dans le cas de passage de message asynchrone vous devez assurer que
les données seront bien transmises. Soyez créative pour donner des
solutions.



5. XML-RPC (Remote Procedure Call) en Java

a. Quelles sont les technologies utilisées pour XML-RPC? Expliquez
chacunes.

b. Comment une requête est faite en XML-RPC?

c. Écrivez un programme en Java avec XML-RPC qui implémente un serveur et
un client de fichiers.



6. Middleware

a. Définissez ce que c'est middleware? Donnez des exemples de middleware.

b. Comment une requête est faite en RMI (Remote Method Invocation)?

c. Implémentez un programme en Java avec RMI qui implémente un serveur et
un client de fichiers.

d. Qu'est-ce que c'est CORBA? Quelles sont les avantages de CORBA?

e. Implémentez un programme en Java avec CORBA permettant de faire:
l'addition, la soustraction et la multiplication de tableaux
bidimensionnels.

Note: Utilisez les séquences pour implémenter le programme.



Autres questions

a. Expliquez les notions de: SMP (Symmetric MultiProcessing),
MPP(Massively Parallel Processing or Massively Parallel Processor).

b. Définissez la notion de HyperThreading? Quels sont ses avantages?

Note: (consulter le site Web de l'Intel).



Etude de Cas

a. Implémentez un programme en Java permettant la multiplication parallèle
(physique) de tableaux bidimensionnels. Le programme doit être exécuter par
«n» différents processeurs connectés en réseau. Note: Utilisez Java RMI.

b. Implémentez un programme en Java avec CORBA qui crée le fractal
Mandelbrot. Le fractal doit être généré de façon parallèle physique. Note:
Utilisez les séquences pour transmettre les données.

c. Implémentez un programme qui utilise le concept « Evolution Strategies »
pour résoudre les fonctions n-dimensionnels, non-différentiables, non-
continues et limités.

d. Implémentez un serveur Web multithreaded qui utilise une liste FIFO pour
stocker les connections du demandeur. Le nombre de threads doit être limité
à «n». Les threads consultent suivant la liste FIFO pour prendre des
connections et attendre les requêtes que le demandeur à envoyer par elles.








-----------------------