IFT 1227 hiver 2006
Architecture des ordinateurs I

Devoir 2

Utilisation des outils Mic-1 (voir site du cours IFT1227)

1)      Soient les nouvelles instructions (en bytecode IJVM) d’accès à la mémoire suivantes:

IREAD et IWRITE qui ont le format : instruction numvar

L'instruction IREAD commence par lire la valeur contenue dans la variable locale numvar. Elle lui additionne ensuite la valeur contenue sur le dessus de la pile et fait une lecture en mémoire à l'adresse ainsi obtenue. Elle dépose cette valeur sur le dessus de la pile.

L’instruction IWRITE procède en 2 étapes :

a)      l'instruction IWRITE commence par lire la valeur contenue dans la variable local numvar et lui additionne la valeur sur le dessus de la pile.

b)      Elle va ensuite lire la donnée qui est en deuxième sur la pile et l'écrit à l'adresse mémoire obtenue en a)

 

Implémentez le micro-code de ces deux instructions et modifiez les fichiers mic1ijvm.mal et ijvm.conf en conséquence.

2) Soit l’algorithme de tri par bulle suivant:

void BubbleSort(int a[])
{
    int i,j;
 
    for (i=MAXLENGTH; --i >=0;) {
       swapped = 0;
       for (j=0; j<i;j++) {
          if (a[j]>a[j+1]) {
             Swap[a[j],a[j+1]);
             swapped=1;
          }
       }
       if (!swapped) return;
   }
}

 

Écrivez le bytecode IJVM de la méthode sans faire aucune modification à l’implémentation de l’algorithme. Pour vérifier votre code, utilisez le squelette « BubbleSort.jas ». Écrivez enfin le nombre total de cycles d’exécution de votre algorithme (sans compter la méthode de test).

3) En modifiant le microcode (fichiers mic1ijvm.mal. et ijvm.conf), optimise l’algorithme pour obtenir une réduction sensible du temps d’exécution. Écrivez le nombre total de cycles d’exécution de votre algorithme.

Consignes :

·        Remettez une seule version des fichiers mic1ijvm.mal et ijvm.conf sans modifier leurs noms.

·        Pour les points 2) et 3), nommez vos fichiers BubbleSort2.jas et BubbleSort3.jas.

·        Vérifiez toutes vos simulations sous LINUX au DIRO avant d’envoyer vos fichiers. Si un programme ne compile pas, il ne sera même pas regardé.

·        Chaque fichier doit commencer par un en-tête reprenant les noms et codes permanents des deux auteurs. 

·        Les travaux se font obligatoirement par équipes de deux. En cas d’empêchement majeur, prendre rendez-vous immédiatement pour expliquer la situation. N’avoir trouvé personne n’est pas un empêchement majeur. Toutes les personnes qui craignent de se retrouver dans cette situation doivent contacter le démonstrateur suffisamment tôt pour qu’il puisse lui-même constituer des équipes avec les personnes concernées.

·        Chaque auteur doit comprendre l’entièreté du travail et en remettre sa propre copie de manière électronique. Ce sera la preuve qu’il assume la responsabilité du contenu du travail. Une pénalité majeure sera appliquée si les deux copies remises sont différentes.

·        Si dans une équipe, une personne se retrouve forcée à réaliser la majeure partie du travail (parce que l’autre ne fait rien), elle doit en faire part avant la correction et la participation des deux personnes sera vérifiée.

·        Tout cas de plagiat détecté sera rapporté à la faculté.

 

Procédure de remise :

La remise doit se faire en deux étapes :

Vendredi 17 mars 2006 à 10h30 : remise du point 1 du devoir dans le répertoire TP2Inst

Vendredi 24 mars 2006 à 10h30 : remise des points 2 et 3 du devoir dans le répertoire TP2Bubble