Énoncé projet 2

Architecture des microprocesseurs (GIF-3000)
D´epartement de g´enie e´ lectrique et de g´enie informatique
Automne 2014
Projet 2
Instructions : – Le projet est r´ealis´e en e´ quipe de deux a` trois e´ tudiants.
– Remise du code source : par Pixel.
– Remise du rapport : copie papier du rapport durant les p´eriodes de cours.
– Date limite : le mardi 9 d´ecembre, a` 10h30.
Pond´eration : Ce laboratoire compte pour 10% de la note finale.
1
Pr´esentation
Pour ce laboratoire, nous vous demandons d’exp´erimenter avec un programme informatique effectuant une simulation conceptuelle de l’implantation de l’algorithme de Tomasulo avec sp´eculation sur
une architecture MIPS. Ce programme fait une interpr´etation de code assembleur MIPS, en ex´ecutant les
instructions selon l’algorithme de Tomasulo avec sp´eculation utilisant un tampon de r´eordonnancement
(ROB), tel que pr´esent´e a` la section 3.6 du livre de Hennessy et Patterson [1]. Ce simulateur supporte un sous-ensemble d’instructions de MIPS, en utilisant un e´ tat initial des registres et de l’espace
m´emoire d´efinis pour l’ex´ecution du programme. De plus, nous vous demandons de modifier ce simulateur pour supporter le lancement multiple et d’ajouter l’implantation d’un pr´edicteur de branchement de
corr´elation.
2
Simulateur
Le simulateur est un programme en Python (version 2.7 ou sup´erieure) dont le code source est disponible a` l’adresse suivante.
https://bitbucket.org/ulaval-gif-3000/mipssim
Le simulateur est un programme ex´ecutable sur la ligne de commande, nomm´e mipssim ayant
l’interface suivante :
mipssim.py config.xml source.mips [trace.txt]
o`u :
— config.xml correspond au nom du fichier de configuration a` utiliser (obligatoire) ;
— source.mips correspond au nom du fichier source contenant le code assembleur MIPS a`
ex´ecuter (obligatoire) ;
1
Unit´es fonctionnelles Load
LD
L.D
Unit´es fonctionnelles Store
SD
S.D
Unit´es fonctionnelles Add
ADD.D SUB.D
Unit´es fonctionnelles Mult
MUL.D DIV.D
Unit´es fonctionnelles ALU
DADD
DMUL
DADDU DMULU DADDI DADDIU
DDIV
DSUB
DDIVU DSUBU AND
Instructions de branchements et de sauts
BEQZ
BEQ
BNEZ
BNE
J
TABLE 1 – Instructions en assembleur MIPS support´ees par le simulateur.
— trace.txt correspond au nom du fichier contenant la trace d’ex´ecution du programme (optionnel).
Le fichier de configuration donne la configuration du processeur (nombre et latence des diff´erentes
unit´es fonctionnelles), configuration de la pr´ediction de branchements, les valeurs initiales des registres
ainsi que la taille et les valeurs initiales de l’espace m´emoire. Le fichier source MIPS est un fichier
de code assembleur (non compil´e) ex´ecut´e par le simulateur. Finalement, le fichier de trace est optionnel, et donne l’´etat du processeur a` chaque coup d’horloge. Le programme mipssim effectue donc
l’ex´ecution du programme MIPS donn´e dans le fichier source.mips selon la configuration donn´ee
par config.xml, avec optionnellement une e´ criture du d´etail de l’ex´ecution du programme dans le
fichier trace.txt.
Le programme effectue une simulation de haut niveau de l’application de l’algorithme de Tomasulo
avec sp´eculation et tampon de r´eordonnancement pour processeur MIPS, tel que pr´esent´e a` la section 3.6
de Hennessy et Patterson [1]. En particulier, il consid`ere que les instructions arithm´etiques et logiques
de nombres entiers et les instructions de contrˆole sont ex´ecut´ees dans des unit´es fonctionnelles particuli`eres, g´er´ees par l’algorithme de Tomasulo avec sp´eculation. Les unit´es fonctionnelles support´ees par
le simulateur sont donn´ees au tableau 1. Chaque instruction comporte une latence d’ex´ecution diff´erente,
donn´ee dans le fichier de configuration. Le processeur poss`ede e´ galement 16 registres a` valeurs enti`eres
(R0 a` R15), avec le cas particulier du registre R0 qui poss`ede une valeur constante de 0, ainsi que 16
registres de nombres a` virgule flottante (F0 a` F15). Ces 32 registres repr´esentent les donn´ees sur 64 bits.
L’ex´ecution du programme dans le simulateur d´ebute a` la premi`ere ligne de code du fichier source,
en utilisant l’´etat initial sp´ecifi´e dans le fichier de configuration. L’ex´ecution se termine lorsque toutes
les instructions du programme ont compl´et´e leur ex´ecution de sorte que toutes les unit´es fonctionnelles
sont lib´er´ees.
2.1
Fichier de configuration
Les fichiers de configuration sont faits en XML et comportent les e´ l´ements suivants.
— Balise MIPSSim : racine du document XML (obligatoire).
— Balise FunctUnits : description des unit´es fonctionnelles (optionnel).
2
— Balise Load : unit´es fonctionnelles de lecture en m´emoire (optionnel).
— Attribut number : nombre d’unit´es fonctionnelles de lecture (optionnel, valeur par
d´efaut : 1).
— Attribut latency : latence d’ex´ecution des instructions de lecture, en nombre de
cycles d’horloge (optionnel, valeur par d´efaut : 1).
— Balise Store : unit´es fonctionnelles d’´ecriture en m´emoire (optionnel).
— Attribut number : nombre d’unit´es fonctionnelles d’´ecriture (optionnel, valeur par
d´efaut : 1).
— Attribut latency : latence d’ex´ecution des instructions d’´ecriture, en nombre de
cycles d’horloge (optionnel, valeur par d´efaut : 1).
— Balise Add : unit´es fonctionnelles d’addition et soustraction de nombres a` virgule flottante
(optionnel).
— Attribut number : nombre d’unit´es fonctionnelles d’addition et soustraction (optionnel, valeur par d´efaut : 1).
— Attribut latency : latence d’ex´ecution des instructions d’addition et soustraction,
en nombre de cycles d’horloge (optionnel, valeur par d´efaut : 1).
— Balise Mult : unit´es fonctionnelles de multiplication et division de nombres a` virgule
flottante (optionnel).
— Attribut number : nombre d’unit´es fonctionnelles de multiplication et division (optionnel).
— Attribut latency mul : latence d’ex´ecution des instructions de multiplication (MUL.D),
en nombre de cycles d’horloge (optionnel, valeur par d´efaut : 1).
— Attribut latency div : latence d’ex´ecution des instructions de division (DIV.D),
en nombre de cycles d’horloge (optionnel, valeur par d´efaut : 1).
— Balise ALU : unit´es fonctionnelles d’op´erations arithm´etiques et logiques sur nombres
entiers (optionnel).
— Attribut number : nombre d’unit´es fonctionnelles d’op´erations arithm´etiques et logiques (optionnel, valeur par d´efaut : 1).
— Attribut latency : latence d’ex´ecution des instructions d’op´eration arithm´etiques et
logiques, en nombre de cycles d’horloge (optionnel, valeur par d´efaut : 1).
— Balise Branch : configuration des branchements conditionnels (optionnel).
— Attribut latency : latence d’ex´ecution des instructions de branchements conditionnels
et de sauts, en nombre de cycles d’horloge (optionnel, valeur par d´efaut : 1).
— Attribut class : nom de la classe pour l’unit´e de branchement. Permet de d´efinir des
unit´es de branchement diff´erentes (optinnel, valeur par d´efaut : BranchUnit).
— Attribut forward branch : attribut pour l’unit´e de branchement par d´efaut. Il s’agit
d’une indication sur le type de sp´eculation effectu´ee pour un branchement vers l’avant,
a` savoir si le branchement est pris (valeur de l’attribut taken) ou non (valeur de l’attribut nottaken). Cette pr´ediction s’applique si l’adresse destination est plus grande que
l’adresse actuelle du compteur de programme (dest>PC) (optionnel, valeur par d´efaut :
nottaken).
— Attribut backward branch : attribut pour l’unit´e de branchement par d´efaut. Il s’agit
d’une indication sur le type de sp´eculation effectu´ee pour un branchement vers l’arri`ere,
a` savoir si le branchement est pris (valeur de l’attribut taken) ou non (valeur de l’attribut nottaken). Cette pr´ediction s’applique si l’adresse destination est plus inf´erieure a`
l’adresse actuelle du compteur de programme (dest<PC) (optionnel, valeur par d´efaut :
nottaken).
— Balise Registers : valeurs initiales des registres du processeur (optionnel).
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<MIPSSim>
<FunctUnits>
<Load number="3" latency="4"/>
<Store number="2" latency="8"/>
<Add
number="2" latency="2"/>
<Mult number="3" latency_mul="5" latency_div="20"/>
<ALU
number="2" latency="1"/>
<Branch latency="1" class="BranchUnit" forward_branch="nottaken" backward_branch="taken"/>
</FunctUnits>
<Registers>
<R1 value="64"/>
<R2 value="32"/>
<R3 value="1"/>
<F0 value="0.5"/>
<F2 value="-3.1416"/>
<F4 value="2.718"/>
</Registers>
<Memory size="32" >
64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33
</Memory>
</MIPSSim>
F IGURE 1 – Exemple de fichier de configuration en XML pouvant eˆ tre lu par le simulateur.
— Balises R1 a` R15 : valeur d’un registre a` valeur enti`ere (optionnel, valeur par d´efaut : 0)
— Attribut value : valeur du registre en question (obligatoire)
— Balises F0 a` F15 : valeur d’un registre de nombre a` virgule flottante (optionnel, valeur
par d´efaut : 0,0)
— Attribut value : valeur du registre en question (obligatoire)
— Balise Memory : taille et valeurs initiales de la m´emoire (obligatoire).
— Attribut size : taille de la m´emoire, en multiples de 8 octets, allou´ee au programme
(obligatoire).
— Valeurs initiales de la m´emoire, donn´ees comme du contenu, avec chaque valeur s´epar´ee
par un espace blanc. Le nombre de valeurs donn´e doit pouvoir eˆ tre contenu dans l’espace
m´emoire allou´e par l’attribut size (optionnel, par d´efaut les valeurs initiales sont 0).
La figure 1 pr´esente un fichier de configuration typique suivant cette syntaxe.
3
Exp´erimentations avec le simulateur
Dans un premier temps, nous vous demandons de faire des exp´erimentations avec le simulateur, afin
de bien caract´eriser ses performances sur diff´erents programmes simples.
3.1
fibo.mips
Le premier exemple de code est donn´e dans le fichier source asm/fibo.mips et le fichier de
configuration associ´e conf/fibo.xml. Pour ce programme, e´ tudiez l’effet associ´e a` l’ajout d’unit´es
fonctionnelles pour la lecture et l’´ecriture de donn´ees en m´emoire sur le nombre de cycles n´ecessaires
a` l’ex´ecution du programme et le nombre de d´elais. Faites e´ galement varier la valeur initiale du registre
R2 dans votre e´ tude, afin de changer le nombre d’it´erations n´ecessaires a` l’ex´ecution du programme.
4
3.2
loop.mips
Le deuxi`eme exemple de code est donn´e dans le fichier source asm/loop.mips et le fichier de
configuration associ´e conf/loop.xml. Pour cet exemple, modifiez le code source pour e´ tudier l’effet
du d´eroulement des boucles. Faites varier le nombre de d´eroulements de boucle pour en e´ valuer l’effet
sur les temps d’ex´ecution.
3.3
dot prod.mips
Le troisi`eme exemple de code est donn´e dans le fichier source asm/dot prod.mips et le fichier
de configuration associ´e conf/dot prod.xml.
Il s’agit d’un programme qui effectue le produit scalaire de n paires de vecteurs ui = [ui,1 , . . . , ui,m ]T
et vi = [vi,1 , . . . , vi,m ]T comprenant chacun m e´ l´ements, enregistre le produit de chaque paire, tout en
accumulant la somme de ces produits scalaires. Math´ematiquement, voici ce que le programme calcule :
n
X
i=1
ui · vi =
n X
m
X
ui,j vi,j ,
i=1 j=1
o`u · repr´esente le produit scalaire. Ce sont des op´erations courantes sur des microprocesseurs, surtout
pour des calculs scientifiques et/ou graphiques. Le programme lit ses entr´ees sur les registres suivants :
— R1 : Adresse de base en m´emoire pour les vecteurs. Les vecteurs sont contigus en m´emoire et
organis´es de la fac¸on suivante : [u1,1 , u1,2 , . . . , u1,m , v1,1 , v1,2 , . . . , v1,m , u2,1 , . . . , vn,m ].
— R2 : Nombre d’´el´ements dans chaque vecteur, soit la valeur de m.
— R3 : Nombre de vecteurs dans le calcul, soit la valeur de n.
— R4 : Adresse de base en m´emoire pour le stockage du r´esultat de chaque produit scalaire. Chacun
des produits scalaires sera stock´e dans cette plage m´emoire d´ebutant a` cette valeur, suivis par la
somme de ces produits.
Pour cet exemple, faites varier le nombre d’unit´es fonctionnelles des unit´es de calcul a` virgule flottante et e´ tudiez l’effet sur le nombre de cycles n´ecessaires a` l’ex´ecution du programme et le nombre de
d´elais. ? Justifiez votre r´eponse par des r´esultats exp´erimentaux.
3.4
count vowels.mips
Le quatri`eme et dernier programme sert a` compter les voyelles dans une chaˆıne de caract`eres plac´ee
en m´emoire (encod´ee en ASCII, doit se terminer par un caract`ere nul). Le programme est donn´e dans le
fichier source asm/count vowels.mips et le fichier de configuration associ´e conf/count vowels.xml.
Les param`etres du programme sont les suivants :
— R3 : Adresse m´emoire correspondant au d´ebut de la chaˆıne de caract`eres.
— R5 : Adresse m´emoire o`u e´ crire le r´esultat, soit le nombre de voyelles dans la chaˆıne.
Pour ce cas-ci, mesurez le nombre de cycles n´ecessaires a` l’ex´ecution du programme (pas besoin de
changer les nombres de stations de r´eservations ou leurs d´elais). Ce nombre de cycles vous servira pour
comparer avec les am´eliorations demand´ees dans les sections suivantes.
5
4
Lancement multiple
Dans un deuxi`eme temps, modifiez le code du simulateur afin de permettre le lancement multiple
`
d’instructions dans l’algorithme de Tomasulo, ainsi que la sanction de plusieurs instructions par cycle. A
cette fin, vous devez adapter le format du fichier de configuration et le module en faisant sa lecture dans
le simulateur, afin de permettre le changement du nombre d’instructions qui peuvent eˆ tre lanc´ees et sanctionn´ees a` chaque cycle d’horloge. Utilisez deux param`etres distincts dans la configuration, un pour le
nombre maximum de lancements possibles par cycle et un pour le nombre maximum de sanctionnements
possibles par cycle.
Exp´erimentez avec cette nouvelle version du simulateur sur les quatre programmes de la section
´
3. Etudiez l’effet du lancement multiple en variant le nombre d’instructions pouvant eˆ tre lanc´ees et
sanctionn´ees a` chaque cycle d’horloge. Est-ce que le nombre maximum d’instructions sanctionn´ees a`
chaque cycle peut eˆ tre inf´erieur au nombre maximum d’instructions lanc´ees a` chaque cycle sans affecter
les performances ? Justifiez votre r´eponse par des r´esultats exp´erimentaux.
5
Pr´edicteur de corr´elation
Finalement, nous vous demandons d’impl´ementer un pr´edicteur de corr´elation g´en´eral (m,n) pour
` cette fin, modifiez le code du simulateur ainsi que
la pr´ediction des branchements dans le simulateur. A
le format du fichier de configuration, afin de sp´ecifier les valeurs de m et n du pr´edicteur, ainsi que le
nombre d’entr´ees dans les tables de pr´ediction des pr´edicteurs a` n bits.
Exp´erimentez avec ce nouveau pr´edicteur de branchement sur les quatre programmes de la section
3. Faites varier la valeur des trois param`etres du pr´edicteur de corr´elation, afin de donner les configurations permettant d’obtenir les meilleures performances avec une configuration minimale du pr´edicteur
de corr´elation. Pour les diff´erentes configurations test´ees et les diff´erents programmes test´es, rapportez le nombre de branchements correctement et incorrectement pr´edits. Comparez les r´esultats avec le
pr´edicteur de base propos´e dans le simulateur.
6
Rapport et remise
Pour ce laboratoire, vous devez transmettre le code source modifi´e du simulateur impl´ementant le
lancement multiple et les nouveaux pr´edicteurs de branchements dans un fichier zip d´epos´e dans Pixel,
avant 10h30, le 9 d´ecembre 2014.
Vous devez e´ galement fournir un rapport papier qui doit eˆ tre remis en classe au professeur, au plus
tard au cours du 9 d´ecembre 2014. Ce rapport devra pr´esenter clairement et en d´etail les r´esultats de
vos exp´erimentations avec le simulateur de code MIPS sur les quatre programmes pr´esent´es a` la section
´
3. Egalement,
le rapport doit pr´esenter les modifications effectu´ees au simulateur pour le lancement
multiple et le pr´edicteur de corr´elation, ainsi que le r´esultat des exp´erimentations qui ont e´ t´e effectu´ees
sur les quatre programmes MIPS avec ces modifications.
Le projet est e´ valu´e sur 20 points :
— Exp´erimentations avec le simulateur (6 points) ;
— Lancement multiple (6 points) ;
— Pr´edicteur de corr´elation (6 points) ;
6
— Qualit´e de la langue et de la pr´esentation (2 points).
R´ef´erences
[1] John L. Hennessy et David A. Patterson, Computer Architecture : A Quantitative Approach, 5e
e´ dition, Morgan Kaufmann, 2011.
28/10/2014
JCL & RB
7

Download Report