= ALMO TP n°10 - Plateforme multi-processeur =

== Préambule ==

Le but principal de ce TP est d'analyser la dégradation de performance d'une plateforme multi-processeur résultant de la bande passante limitée du bus système, quand le nombre de processeurs augmente.

[[Image(wiki:Images:hard_almo_multi_icu_timer.png)]]

La plateforme considérée comporte un nombre variable de processeurs `MIPS32` (entre 1 et 8 processeurs). Il existe une seule instance physique de chaque périphérique (ICU, TIMER et TTY), mais ces derniers contiennent autant d'instances virtuelles que de processeurs (un processeur `P[i]` a accès à un concentrateur d'interruption `ICU[i]` qui lui est propre, ainsi qu'un contrôleur de terminaux `TTY[i]` et un contrôleur d'horloge `TIMER[i]`.

Le simulateur pour cette plateforme est toujours simul_almo_generic. Il faut cependant préciser au lancement du simulateur que la plateforme contient `N` processeurs. Vous utiliserez donc la commande suivante tout au long du TP  (où `N` doit être remplacé par le nombre de processeurs souhaité) :

{{{
$ simul_almo_generic -SYS sys.bin -APP app.bin -NPROCS N
}}}

Comme d'habitude, commencez par recopier dans votre répertoire de travail, les fichiers sources spécifiques à ce TP :

{{{
$ cd li312
$ cp -r /Infos/lmd/2014/licence/ue/li312-2014oct/sesi-almo/soft/tp10/sujet ./tp10
$ cd tp10
}}}

== 1. Différenciation des processeurs et partage de la mémoire ==

Jusqu'à présent, les plateformes étudiées ne comportaient qu'un unique processeur. Avec les plateformes multi-processeurs se pose un double problème :
1. Il faut différencier les processeurs, pour qu'ils exécutent des tâches différentes.
1. Il faut partager la mémoire entre les différentes applications s'exécutant sur les différents processeurs.

Les processeurs sont identiques, mais peuvent être identifiés par un numéro de processeur (cablé "en dur" lors de la fabrication), qui peut être accédé par le '''GIET''' grâce à la fonction `_procid()` (quand on est en mode noyau), ou par l'appel système `procid()` (quand on est en mode utilisateur).

Lorsque le système démarre, tous les processeurs se branchent à l'adresse `0xBFC0000` et exécutent (en parallèle) le même code de démarrage. Ce code effectue l'initialisation de quelques registres internes aux processeurs (dont `SR` et le pointeur de pile). Puisque tous les processeurs travaillent en parallèle, il faut autant de piles d'exécution que de processeurs. Il est donc nécessaire d'utiliser le numéro de processeur dans le code de démarrage, pour initialiser les pointeurs de pile des différents processeur à des adresses différentes.

Le code du démarrage se termine par un saut à la fonction `main()`, qui se trouve dans l'espace d'adressage utilisateur. Tous les processeurs exécutent donc la même fonction `main()`, mais - en fonction du numéro de processeur - chaque processeur peut effectuer un calcul différent.

* Ouvrez le fichier `main0.c` et complétez ce code pour que chaque processeur affiche un message différent dépendant du numéro de processeur.

* Complétez le fichier `reset.s` en y ajoutant les instructions assembleur nécessaires à la réservation  d'une pile séparée pour chaque processeur.

 ''On fixe à 64 Koctets  la taille de la pile pour chaque processeur.''

* Vérifiez le bon fonctionnement en compilant et en exécutant successivement l'application logicielle sur le simulateur `simul_almo_generic`, en spécifiant 1, 2 ou 4 processeurs.

 ''Attention : il faut modifier le fichier `'config.h'` pour préciser le nombre de processeurs utilisés dans la plateforme, et recompiler entièrement le logiciel embarqué chaque fois qu'on modifie le paramètre NPROCS : le système d'exploitation a besoin d'être informé du nombre de processeurs placés sous son contrôle.''

 Afin de refaire une compilation complète, lancez `make clean` suivi de `make`.

== 2. Application parallèle multi-tâches coopératives ==

On souhaite maintenant profiter de la présence des 8 processeurs pour accélérer une application logicielle capable de s'exécuter sur  plusieurs processeurs.

On s'intéresse à une application de traitement d'image, consistant à appliquer un filtre de convolution sur chaque ligne d'une image. On considère des images possédant 128 lignes de 128 pixels. La valeur de chaque pixel est codée en niveaux de gris. Le noyau de convolution a une largeur de 9 pixels, ce qui signifie que la nouvelle valeur d'un pixel `(p)` est une moyenne pondérée sur les valeurs des 9 plus proches voisins du pixel `(p)`. Comme le traitement d'un pixel ne dépend pas du traitement des autres pixels, on peut partager le travail entre plusieurs processeurs.

On suppose que l'image initiale `input[line][pixel]`, et l'image finale `output[line][pixel]` sont des variables globales stockées en mémoire dans le segment `seg_data`. Le code de la fonction `main()` et le code de la fonction `filter()` permettant de traiter une ligne sont contenus dans le fichier `main1.c`.

Si on utilise un seul processeur, le même processeur effectue 128 fois le même calcul sur les 128 lignes, en appelant 128 fois la fonction `filter()` pour chaque ligne, et affiche un message lorsqu'il a terminé. Lorsqu'on utilise plusieurs processeurs, on peut paralléliser le calcul, et chaque processeur (suivant son numéro de processeur) traite un sous-ensemble des pixels, et affiche un message lorsqu'il a terminé sa part du travail.

* Modifiez le fichier `Makefile` pour générer un exécutable `app.bin` à partir de `main1.c` et exécutez l'application sur une architecture mono-processeur.

* Modifiez le fichier `main1.c` de façon à ce que le calcul puisse être exécuté sur `1` processeur, ou sur `K` processeurs (K compris entre 1 et 8).
 L'idée générale est la suivante : si on utilise deux processeurs, le processeur `P[0]` traite les blocs d'index `(2n)`, et le processeur `P[1]` traite les blocs d'index `(2n+1)`. Si on utilise 3 processeurs, le processeur `P[0]` traite les blocs d'index `(3n)`, le processeur `P[1]` traite les blocs d'index `(3n+1)`, et le processeur `P[2]` traite les blocs d'index `(3n+2)`. Si on utilise `K` processeur le processeur `P[k]` traite les blocs d'index `(K*n + k)`, sachant que `k` est compris entre `0` et `(K-1)`.

* Lancez successivement les 8 exécutions correspondant aux 8 valeurs (`K=1` à `K=8`) (sans oublier de modifier le fichier `config.h` en conséquence, puis de recompilez entièrement) et mesurez les temps d'exécution.
 On prendra pour temps d'exécution la date affichée par le processeur qui termine le dernier.

On appelle `speedup[K]` (ou ''accélération'') la valeur obtenue en divisant le temps d'exécution avec un seul processeur par le temps d'exécution obtenu avec `K` processeurs.

* Tracez à l'aide de `gnuplot` la courbe représentant en abscisse le nombre de processeurs `K`, et en ordonnée l'accélération `speedup[K]`.

* Quelles conclusions peut-on tirer de cette courbe ?

{{{#!comment
vim:filetype=tracwiki:expandtab:shiftwidth=4:tabstop=4:softtabstop=4:spell:spelllang=fr
}}}