Laboratoire

Ce laboratoire vise à mettre concrètement en pratique les notions étudiées au cours d’organisation des ordinateurs, en développant et en faisant tourner un programme simple rédigé en assembleur x86-64.

Outils informatiques

Pour réaliser ce projet, vous avez besoin d’un compte vous permettant d’accéder aux ordinateurs des laboratoires. Si vous n’en disposez pas encore, adressez-vous aux encadrants pour en obtenir un.

Si vous souhaitez utiliser votre propre ordinateur, il vous est fortement conseillé de d’abord tester vos programmes sur les ordinateurs du laboratoire. La programmation en assembleur n’est en effet pas universelle, et certains détails peuvent dépendre de l’environnement de programmation utilisé. Les exemples vus au cours supposent l’environnement suivant:

  • Un processeur d’architecture x86-64.
  • Le système d’exploitation Linux, en mode 64 bits.
  • Le compilateur GCC.

Note: Certains environnements nécessitent d’employer des options de compilation supplémentaires à celles indiquées dans le cours (notamment -no-pie ou -static).

Objectif

L’objectif consiste à programmer une fonction capable de trier un tableau de nombres. Cette fonction doit posséder l’interface suivante:

void trier(int *t, unsigned nb)

où

  • le paramètre t pointe vers un tableau d’entiers.
  • le paramètre nb donne le nombre d’entiers contenus dans ce tableau (ce nombre peut être nul).

L’effet de la fonction doit être de réordonner les éléments du tableau, de façon à les trier par ordre croissant de valeur.

Etape 1: Algorithme

La première étape consiste à écrire un algorithme permettant de résoudre le problème. Vous pouvez exprimer cet algorithme en pseudocode, sur une feuille de papier. Le choix de l’algorithme est libre. Voici quelques suggestions (n’en choisissez qu’une!):

  • Le tri par insertion, qui est simple, mais présente une complexité \(O(n^2)\) en fonction du nombre \(n\) de valeurs à trier.
  • Le tri par sélection, similaire au précédent.
  • Le tri à bulles, élégant mais moins efficace en pratique que les précédents.
  • Le tri par fusion, plus difficile à implémenter, mais de complexité \(O(n \log n)\).

(Cette liste n’est pas exhaustive. Vous pouvez utiliser une autre solution si vous le souhaitez.)

Etape 2: Programme C

Cette étape consiste à traduire l’algorithme obtenu au point 1 en un programme C. Les consignes sont les suivantes:

  • La fonction trier() doit être définie dans un fichier trier.c qui ne contient rien d’autre.

  • Le code de cette fonction doit inclure un commentaire indiquant le type d’algorithme employé (par insersion, par sélection, …).

  • La fonction principale main() du programme doit être définie dans un fichier séparé appelé test.c. Cette fonction doit:

    1. Creér un tableau contenant 20 nombres entiers, initialisés comme vous le souhaitez (soit avec des valeurs constantes, soit avec des valeurs aléatoires).

      Note: La fonction random() de la bibliothèque standard C permet de générer un entier aléatoire. La documentation de cette fonction peut être consultée via la commande man 3 random.

    2. Invoquer la fonction trier() afin de trier ce tableau.

    3. Afficher sur la console le tableau trié.

  • Votre programme doit pouvoir être compilé à l’aide de la commande:

    gcc -Wall -O3 -o test test.c trier.c

    qui produit un programme exécutable appelé test.

Prenez-le temps de bien vérifier que votre programme s’exécute correctement. (En cas de difficulté, n’hésitez-pas à demander de l’aide à un encadrant.)

Lorsque votre programme est au point, recopiez les deux fichiers test.c et trier.c dans le répertoire /home/boigelot/odo/, en les préfixant du nom des membres de votre groupe. (Par exemple: Dupont-Durant-test.c et Dupont-Durant-trier.c.) Utilisez ensuite la commande chmod 600 pour protéger ces fichiers contre la lecture. (Par exemple: chmod 600 /home/boigelot/odo/Dupont-Durant-test.c.)

Etape 3: Programme assembleur

L’objectif est maintenant de traduire la fonction trier() en assembleur, en utilisant les mécanismes vus au cours. Cette fonction sera placée dans un fichier trier.s destiné à remplacer trier.c. Le programme de test contenu dans test.c restera inchangé.

En d’autres termes, votre programme sera maintenant compilé grâce à la commande:

gcc -Wall -O3 -o test test.c trier.s

Note: Si vous avez choisi d’implémenter un tri par fusion (ou d’autres solutions telles que le tri rapide), vous aurez besoin d’une instruction assembleur capable de diviser un entier non signé par 2. Vous pouvez employer l’instruction SHR, dont les modes d’adressage sont identiques à ceux de NOT. Par exemple, l’instruction SHR EAX divise l’entier non signé de 32 bits contenu dans le registre EAX par 2.

Testez soigneusement votre programme. Lorsqu’il fonctionne, recopiez le fichier trier.s dans le répertoire centralisé, en utilisant le même préfixe que ceux que vous y avez déjà placés.

N’hésitez pas à expérimenter en observant l’effet de modifications apportées à votre programme, ou en l’exécutant avec un tableau de plus grande taille. Si vous rencontrez des difficultés de programmation ou d’utilisation des outils, les encadrants sont disponibles pour vous assister.