wiki:SujetTD3

ALMO TD n°3 - Programmation assembleur : programme de tri

Préambule

Le but de ce TD est de coder, en assembleur MIPS32, un algorithme de tri spécifié en langage C. Il est indispensable de se référer au document MIPS32 : Langage d'assemblage pour faire les exercices proposés.

Principe du tri

On suppose que les valeurs à trier sont contenues dans un tableau, que ces valeurs sont représentées par des entiers non signés et que tous les éléments du tableau ont des valeurs différentes.

Pour traiter un tableau de N éléments, on commence par rechercher le plus grand élément Tab[i] parmi les N éléments du tableau. Quand on l'a trouvé, on échange les positions de l'élément Tab[i] et du dernier élément Tab[N-1]. Après cet échange, le dernier élément Tab[N-1] est correctement placé, et il reste à trier les (N-1) premiers éléments du tableau, et il faut donc recommencer la procédure précédente pour un tableau de (N-1) éléments.

Cet algorithme peut être réalisé par deux boucles imbriquées ou par une fonction récursive. Le programme étudié ici utilise une fonction récursive.

Programme C

Le programme principal commence par afficher le contenu du tableau initial, effectue le tri, puis affiche le contenu du tableau trié.

#include <stdio.h>

int tab[10] = {3, 33, 49, 4, 23, 12, 46, 21, 48, 2};

/* cette fonction affiche les elements du tableau tab */
void affiche(int * tab, int taille) {
    int i;
    for (i = 0; i < taille; i++) {
        printf("%d", tab[i]);
        printf("\n");
    }
}

/* cette fonction échange les éléments i et j du tableau tab */
void echange(int * tab, int i, int j) {
    int tmp;
    tmp = tab[i];
    tab[i] = tab[j];
    tab[j] = tmp;
}

/* cette fonction effectue le tri des éléments du tableau tab */
void tri(int * tab, int taille) {
    int valmax;
    int i, imax;

    /* cas terminal : fin de recursivite */
    if (taille < 2) {
        return;
    }

    /* cas général : taille > 1 */
    valmax = 0;
    for (i = 0; i < taille; i += 1) {
        if (tab[i] > valmax) 
        {
            valmax = tab[i];
            imax = i;
        }
    }
    /* échange et récursion */
    echange(tab, imax, taille - 1);
    tri(tab, taille - 1);
}

/* le main affiche le tableau avant le tri, effectue le tri, et affiche le tableau trié */
int main(void) {
    int taille;
    taille = 10;
    affiche(tab, taille);
    tri(tab, taille);
    affiche(tab, taille);
    return 0;
}

1. Structure du programme assembleur

  • Représenter graphiquement l'arbre représentant les appels de fonctions dans ce programme. La racine de l'arbre est la fonction main().
  • Quels sont les 3 segments composant le programme assembleur, et quel est le rôle de chacun de ces segments ?
  • Écrire la directive assembleur permettant de déclarer et d'initialiser le tableau de nom 'tab' dans le segment .data, ainsi que la chaîne de caractère de nom 'retour' (représentant un retour chariot : "\n"). Combien d'octets occupent en mémoire ces différentes variable globales?

2. Fonction affiche(int * tab, int taille)

Cette fonction affiche chaque élément du tableau suivi d'un retour chariot.

2.1. Corps de la fonction

  • Écrire la boucle constituant le corps de la fonction affiche().

L'adresse du tableau a été rangée par la fonction appelante dans le registre $4 et la taille du tableau a été rangée dans le registre $5. Pour cette fonction, on utilisera les registres $8 et $9 comme registres de travail, et on ne s'autorisera pas à utiliser de registre persistant. Il faut donc sauvegarder les valeurs des registres $4 et $5 en pile dans le prologue et aller les lire en pile quand on en a besoin. De même, il faut lire (écrire) 'i' en pile à chaque lecture (écriture) car les fonctions appelées peuvent écraser les valeurs de $8 et $9.

Il faut évidemment utiliser l'appel système permettant l'affichage d'un entier, ainsi que l'appel système permettant l'affichage d'une chaîne de caractères (pour le saut de ligne). Remarque : Les positions des arguments et de la variable locale i dans la pile ne sont connues précisément que lorsque le prologue est écrit.

2.2. Prologue

  • Donner le nombre maximum d'argument 'na', le nombre de variables locales 'nv' et le nombre de registres persistants 'nr' utilisés dans la fonction affiche().

Attention: 'na' n'est pas le nombre d'arguments de la fonction affiche(), mais le nombre maximum des arguments que la fonction affiche() devra passer aux fonctions qu'elle appelle.

  • Écrire le prologue de la fonction affiche() qui permet de sauvegarder en pile l'adresse de retour, les registres de travail et les arguments de la fonction.

2.3. Épilogue

  • Écrire l'épilogue de la fonction affiche() qui permet de restaurer l'adresse de retour, les registres de travail et réalise le retour à la fonction appelante.

3. Fonction echange(int * tab, int i, int j)

Cette fonction échange les valeurs d'indice i et j du tableau tab.

3.1. Corps de la fonction

  • Écrire le corps de la fonction echange(). On supposera que l'adresse du tableau a été rangée dans le registre $4 par la fonction appelante, et que les arguments i et j ont été rangés dans les registres $5 et $6. On utilisera les registres $8 à $11 pour stocker des résultats intermédiaires.

3.2. Prologue

  • Donner le nombre maximum d'argument 'na', le nombre de variables locales 'nv' et le nombre de registres persistants 'nr' utilisés dans la fonction echange().
  • Écrire le prologue de la fonction échange() qui permet de sauvegarder l'adresse de retour, les registres de travail et de récupérer les arguments de la fonction dans les registres du processeur.

3.3. Épilogue

  • Écrire l'épilogue de la fonction echange() qui permet de restaurer l'adresse de retour, les registres de travail et réalise le retour à la fonction appelante.

4. Fonction tri(int * tab, int taille)

Cette fonction récursive effectue le tri des éléments du tableau tab.

4.1. Corps de la fonction

  • En suivant le code C, écrivez le corps de la fonction tri(). On supposera que l'adresse du tableau a été rangée par la fonction appelante dans le registre $4 et la taille dans le registre $5.

Commencez par copier les deux arguments tabet taille dans les registres persistants $16 et $17. On utilisera les registres $8, $9 et $10 stocker les variables locales valmax, i et imax. On pourra utiliser les deux registres $11 et $12 pour stocker des résultats intermédiaires.

Attention : les registres $16 et $17 sont des registres persistants.

4.2. Prologue

  • Donner le nombre d'argument 'na', le nombre de variables locales 'nv' et le nombre de registres persistants 'nr' utilisés dans la fonction tri().
  • Écrire le prologue de la fonction tri().

4.3. Epilogue

  • Écrivez l'épilogue de la fonction tri(). Il sera identifié par le label 'tri_epilogue'.

5. Fonction main()

  • Écrire en assembleur la fonction main, dont la première instruction porte le label 'main'. Cette fonction commence par déplacer le pointeur de pile pour réserver la place correspondant aux arguments des deux fonctions appelées. On n'utilisera pas de registres persistants hormis $31.

Déterminer les valeurs de nr, nvet na

Last modified 4 years ago Last modified on Oct 7, 2019, 6:54:12 PM