Projet environnements de programmation

Licence 3 Informatique - 2007-2008

PhilippeCollet, NicolasNobelis

URL de cette page : http://deptinfo.unice.fr/twiki/bin/view/Linfo/GLEnvtProg0708Projet
URL de l'enseignement : http://deptinfo.unice.fr/twiki/bin/view/Linfo/GLEnvtProg0708

Avant propos

Où ? Quand ?

Le projet doit être rendu par mail à nobelis@polytech.unice.fr avant le jeudi 13 mars 2008, minuit. Le mail doit avoir pour sujet Projet GLEnvtProg - Nom du binôme. Pour être sûr que j'ai bien reçu votre projet, vous pouvez m'envoyer le mail avec une demande d'accusé de réception (je répondrai à toutes ces demandes).
N'oubliez pas d'attacher votre projet au mail (!)

Comment ?

• Le projet est à faire en binôme.

• Le projet sera rendu dans une archive tgz ou tbz nommée projetnom1nom2.{tgz,tbz}.

• Les questions marquées ajoutez signifient que vous devez joindre le fichier précisé à cette archive.

• Les questions marquées rédigez signifient que vous devez écrire la réponse à cette question dans un fichier texte simple nommé reponses_nom1nom2.txt en précisant le numéro de la question concernée. Vous joindrez bien sûr ce fichier à votre archive de rendu.

• Vous pouvez ajouter vos commentaires ou remarques dans ce fichier.

• Ne copiez pas : un logiciel de comparaison avancée sera utilisé sur tous vos fichiers de rendu. Toute similarité sera sanctionnée.

Fournitures

L'archive FournitureProjet.tbz contient les fichiers donc vous allez avoir besoin pour ce projet :

• tableau.h, contient les prototypes de toutes les fonctions de manipulation de tableau.
• tableau.c, contient les implémentations de certaines fonctions de manipulation de tableau (i.e. toutes sauf les fonctions de tri et celles de piles).
• tableau_stack.c, contient les implémentations de certaines fonctions de manipulation de tableau (i.e. les fonctions de piles).
• tri_bulles.c, contient l'implémentation d'un tri à bulles.
• tri_insertion.c, contient l'implémentation d'un tri par insertion.
• tri_quicksort.c, contient un appel à l'implémentation d'un tri rapide ("quicksort') contenue dans la libc.
• test_tableau.c, programme de test des algorithmes de tri.
• test_tableau_stack.c, programme de test de toutes les fonctions de manipulation de tableau.
• Makefile, voir ci-dessous.
• kprof, déjà utilisé dans le TP4.

La cible all du Makefile construit quatre binaires nommés test_bulles, test_insertion, test_quicksort (à partir de test_tableau.c) et test_stack (à partir de test_tableau_stack.c). Les trois premiers binaires ont deux paramètres obligatoires et un troisième optionnel:

• Le première paramètre est la longueur des tableaux à générer.
• Le second paramètre est le nombre de tableaux à générer
• Si le troisième paramètre est positionné à 0, les tableaux seront générés déjà triés.

L'algorithme de tri est déterminé par l'implémentation ayant été liée au binaire. Exemples de cas d'utilisation :

• test_bulles  500 4000 => génère 4000 tableaux de taille 500 initialisés aléatoirement, et les tri au fur et à mesure à l'aide d'un tri à bulles.
• test_insertion 15 1 0 => génère un tableau de taille 15 déjà trié, et le tri à l'aide d'un tri par insertion. Comme il n'y a qu'un seul tableau de taille modeste, celui-ci est affiché à l'exécution.

Le binaire test_stack quant à lui génère aléatoirement un seul tableau et effectue diverses opérations issues de tableau.h, dont un tri déterminé par l'implémentation ayant été liée au binaire. Celui-ci n'a qu'un paramètre obligatoire et un second optionnel:

• Le première paramètre est la longueur du tableau à générer.
• Si le second paramètre est positionné à 0, le tableau sera généré déjà trié.

Exemple de cas d'utilisation :

• test_stack  15 0 => génère un tableau de taille 15 déjà trié, et effectue plusieurs opérations sur celui-ci.

test_bulles, test_insertion et test_quicksort sont utilisés dans les questions 3. et 4.
test_stack est utilisé dans les questions 5. et 6.

1. Fin du TP5

• Finissez le TP5.
• ajoutez à votre archive le fichier checkFile1.c de la question 5. du TP5.

2. Makefile

• Copiez le Makefile fourni dans un fichier Makefile.1.
• Améliorez Makefile.1 pour utiliser :
  
  • les variables de make et autres variables (CFLAGS,...),
  • au maximum les variables automatiques ($@, $^, $<, ...),
  • les règles implicites.
• ajoutez à votre archive ce fichier Makefile.1.

3. Optimisation

Dans cette question, nous utilisons le terme de données conséquentes pour des paramètres de test élevés non triés : par exemple longueur de tableau = 500 et nombre de tableaux = 4000. Adaptez ces valeurs suivant la puissance de votre machine de test.

1. Utilisez la commande time pour tester la vitesse des différents algorithmes de tri (test_bulles, test_insertion et test_quicksort) avec des données conséquentes.
   • rédigez en ajoutant ces temps à votre rapport. Qu'en déduisez-vous sur ces algorithmes et la qualité de leur implémentation ?
2. Utilisez la commande time pour tester la vitesse des différents algorithmes avec des données conséquentes mais déjà triées (c'est-à-dire que le troisième paramètre vaut 0).
   • rédigez en ajoutant ces temps à votre rapport. Analysez et identifiez (ou supposez dans le cas du quicksort) d'où proviennent ces différences.
3. Créez trois binaires pour le tri à bulles test_bulles0, test_bulles2, et test_bulles3, optimisés avec les paramètres respectifs -O0, -O2, -O3. Mesurez la vitesse de chaque binaire avec time et des données conséquentes. Observez également la taille des binaires produits.
   • rédigez en ajoutant ces temps et ces tailles à votre rapport. Qu'en déduisez-vous sur ces optimisations ?
4. Regardez tri_quicksort.c. Si on utilisait les mêmes optimisations, mais avec un binaire lié au tri quicksort, qu'obtiendrait-on comme résultats ?
   • rédigez, en la justifiant, votre réponse (il ne vous est pas demandé de faire ces compilations ni ces mesures).
5. Prenez à présent un binaire non optimisé effectuant le tri à bulles, i.e. test_bulles. Utilisez des données conséquentes et faites variez la longueur des tableaux à trier. Faites une demi-douzaine de mesures.
   • rédigez en ajoutant ces temps à votre rapport. Qu'en déduisez-vous ? Arrivez-vous à retrouver la complexité de l'algorithme ?

4. Profiling

1. Obtenez, à l'aide de gprof, deux profiles pour test_insertion et test_bulles (sur des données conséquentes). Analysez ces profiles à la main ou avec kprof.
   • rédigez en présentant (et justifiant) les fonctions utilisant le plus de ressource. Quelles sont les fonctions qu'il faudrait optimiser ? (aidez-vous du code source de ces fonctions).
2. Étudiez le taux des temps d'éxecution des deux algorithmes de tri (en le calculant à la main ou en utilisant l'option "comparer" de kprof). Générez deux nouveaux profiles en changeant adéquatement la taille des données triées, puis observez l'évolution (ou la non évolution) de ce taux.
   • rédigez en ajoutant ces taux (et vos paramètres de test) à votre rapport. Qu'en déduisez-vous ?

5. Bibliothèque...et encore un peu de Makefile !

• Construisez une bibliothèque dynamique libtableau.so à partir de tableau.o et de tableau_stack.o comme vu en TP.
• Construisez un binaire test_stack_dyn en un appel à gcc qui :
  • compile test_tableau_stack.c,
  • se relie au fichier tri_quicksort.o,
  • se relie dynamiquement à la bibliothèque libtableau.so.
• Exécutez le binaire produit.
• Copiez Makefile.1 dans Makefile.2. Modifiez Makefile.2 en y ajoutant les trois commandes précédentes.
• ajoutez à votre archive ce fichier Makefile.2.

6. Tests

• Observez les spécifications contenues dans tableau.h pour les fonctions implémentées dans tableau_stack.o.
• Identifiez les cas critiques et rédigez un plan de test. Il ne vous est pas demandé d'implémenter ce plan de test.
• rédigez en présentant les cas critiques et votre plan de test.
  

• (Super bonus - optionnel) Finalement, écrivez dans test_tableau_stack.c le plan de test de la question précédente en utilisant l'infrastructure check.
• (Super bonus - optionnel) Copiez Makefile.2 dans Makefile.3. Modifiez le Makefile.3 pour pouvoir compiler et exécuter un binaire test_stack_dyn_check (vous aurez donc une ligne de compilation contenant -ltableau et -lcheck).
• (Super bonus - optionnel) ajoutez à votre archive le fichier Makefile.3 et le fichier test_tableau_stack.c modifié.

---

-- NicolasNobelis - 09 Mar 2008
to top