You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
garonne df7539c0df mise a jour readme 6 months ago
Makefile premier commit 7 months ago
PR2-SE201-21.pdf premier commit 7 months ago
README.md mise a jour readme 6 months ago
insertion-sort.c premier commit 7 months ago

README.md

SE201 - Projet 1

Contributeurs:

  • Mathias COULAIS
  • Pascal ROUPPERT
  • Quentin AUDINET

2 RISC-V Tool Chain

2.1 RISC-V Tools

make -B force la recompilation pour toutes les cibles, tandis que make -clean est une cible particulière, qui permet en général de supprimer certains fichiers, mais dont le comportement est déterminé par le programmeur.
La comande -nostdlib indique au compilateur de ne pas utiliser les libraires Arm standardes pour C et C++. La commande -nostartfiles indique au compilateur de ne pas prendre en compte les fichiers système standards au moment de l'édition de liens.
La première itération de la première boucle a lieu dans les lignes suivantes, de l'instruction à 0x10150 à 0x10160 :

0x10150:	0007a683          	lw	a3,0(a5)
0x10154:	00d72023          	sw	a3,0(a4)
0x10158:	00478793          	addi	a5,a5,4
0x1015c:	00470713          	addi	a4,a4,4
0x10160:	fec798e3          	bne	a5,a2,10150 <main+0x2c>

Cette boucle :

  • copie dans a3 la valeur contenue à l'adresse contenue dans a5 + 0.
  • copie la valeur de a3 à l'adresse contenue dans a4 + 0.
  • (des deux instructions reviennent à copier la donnée contenue à l'adresse a4 à l'adresse a5)
  • on incrémente a5 et a4 de 4, ce qui revient à parcourir la mémoire quatre octets par quatre octets à partir de deux adresses données.
  • la boucle s'arrête lorsque a5 est égal à a2, qui est initialisée avant la boucle.

Ainsi, cette boucle copie une zone de la mémoire dans une autre rone de taille équivalente.

En exécutant la commande donnée, on trouve 0x000111e8 comme adresse pour input.

On fait ensuite riscv64-linux-gnu-objdump -d insertion-sort.elf | grep input pour trouver une instruction utilisant input. On trouve par exemple :

1013c:	    lui	    a5,0x11
0x10140:	addi	a5,a5,488 # 111e8 <input>

Ces deux instructions permettent de copier la valeur 0x111e8. Cependant, comme cette valeur est trop grande pour être intégrée dans une seule instruction, on doit le faire en deux étapes. Tout d'abord, on copie les bits de poids fort de a5 grâce à lui (a5 = 0b10001000000000000 à cette étape). Ensuite, on ajoute les douze bits de poids faible grâce au addi (a5 = a5 + 0x1e8).


Un PIC est un programme s'exécutant sans erreur quelle que soit la zone de mémoire RAM à partir de laquelle il est lancé. Les PIC sont utiles par exemple pour les librairies partagées, dont le code est intégré par le compilateur dans les exécutables, et qui seront donc exécutées à divers endroits de la mémoire. L'instruction auipc permet de faire de grands déplacements dans la mémoire (bien plus rapidement que grâce à des sauts), ce qui peut par exemple permettre à un programme d'utiliser une instruction définie dans une librairie ailleurs en mémoire.


Le binaire compilé n'est pas PIC. En effet, le code PIC ajoute de la redirection : il faut d'abord charger l'adresse d'une fonction avant de pouvoir l'appeler.


2.2 Ripes

Le registre x14 contient l'adresse du buffer lors du premier tour de boucle (sw x13 0 x14). Au moment du MEM, x14 contient l'adresse 0x7ffffe34.


Stat name Value
Nombre de cycles 58998
Instructions executées 42770
CPI 1.38
IPC 0.725

Avec un Single Cycle RISC-V Processor :


Stat name Value
Nombre de cycles 42770
Instructions executées 42770
CPI 1
IPC 1

Avec un 6-Stage dual-issue RISC-V Processor :


Stat name Value
Nombre de cycles 53943
Instructions executées 42770
CPI 1.26
IPC 0.793


3 Single pipelining

A partir du pipeline diagram, on peut voir que le processeur supporte le forwarding. En effet, entre l'instruction load et l'instruction store dans la boucle, le registre x14 est passé du state WB à EX au même step, donc il y a forwading. On le voit aussi sur le schéma du processeur, il y a une connexion qui sort la partie WB et rentre dans la partie EX du processeur, et qui symbolise le fonctionnement du forwarding.

Le processeur fait du forwarding, mais implémente toujouors du stalling pour résoudre les possibles problèmes dans le déroulement des instructions (notamment avec les accès mémoires).

Le programme sait que simulateur a terminé quand on execute l'intruction ecall, qui jump en rendant la main au système d'exploitation.


4 Branches and Multiple-Issue

Dans le pipeline diagram, il y a plusieurs exemple d'instruction qui sont chargées dans la partie IF et ID mais qui ne sont pas exécutée entièrement. C'est parce que le programme exécute un branchement : on insert des bulles dans la partie EX MEM et WB pour éviter d'exécuter des instructions involontairement.

Le processeur ne possède pas de branch predictor, car la perte d'instructions pour un branchement est toujours de deux : on ne prédit jamais le branchement. De plus, les branchement non pris ne sont jamais prédit pris, ce qui donne une situation caractéristique que l'on repère facilement normalement.

Le processeur optimal a un CPI de 1, mais ce n'est pas le cas ici. En effet, les branchements pris prennent 3 instructions et le stalling entre les instructions load et store prennent 2 instructions pour s'exécuter au lieu de une. Au final, on perd quelques instructions pour arriver à un CPI de 1.38.

Ce processeur effectue deux instructions en même temps : il load deux instructions par cycle. Plusieurs exemples sont intéressants : quand on a les instructions load word et store word à la suite, on effectue deux cycles de stalling et un forwarding pour s'assurer que le valeur du registre contentieux est bien écrite par la première instruction avant d'être lue par la deuxième.

5 Caches

Accès cache données : 1 Adresse de retour dans _start 5 Sauvegarde sur la pile SIZEx2 Copie dans le buffer 0x Lors de minIndex les adresses ont déjà été utilisées =204

Accès cache instructions : (0x101dc - 0x100d8) / 4 + 1 = 66

  1. Il ne faut pas mettre de blocks (perturberait le compte de hit et miss) Il faut mettre plusieurs ways pour éviter que des données soient réécrites par Miss Conflict (2²) Il faut que la taille totale du cache soit supérieure au nombre d'accès distincts que l'on a calculé. Il devrait alors y avoir exactement autant de miss que d'accès distincts (ceux de la première fois), soit 204 accès distincts pour le cache de données.

Pour les datas : 2^6 lines et 2^2 ways ==> 204 misses YEP Pour les instructions : 2^4 lines et 2^2 ways ==> 64 misses O_o : deux instructions à la fin de min index ne sont jamais exécutées.

  1. Pour les données, on n'accède globalement qu'au tableau de 99 données. Cela est suffisamment petit pour stocker l'ensemble des données dans le cache. On utilise donc un cache à 128 entrées, qu'on divise en deux ways et une ligne, avec des blocks de taille 2⁶. Au total, on a donc un cache de 4kB. Avec cette configuration, on a un total de 7 misses.

Pour les instructions, on veut que le cache puisse contenir toutes les instructions d'une boucle. On fait des boucles de 10 instructions consécutives au maximum. Il faut donc 2^4 blocks utiles et ensuite 2^2 lines ==> 6 misses B) ==> 6 misses pour une taille de 2^6 = 2kb

  1. Pour le cache de données, on choisit un cache dont la taille est donnée par min(1Mb, 10% de la taille totale des données). On borne la taille à 1Mb, car cette valeur correspond à l'ordre de grandeur de la taille des caches utilisés sur les processeurs classiques de PC portables. De plus, sur un programme courant (un peu plus volumineux qu'un programme copiant simplement un tableau dans un autre), il semble improbable qu'on utilise plus de 10% des données pour une même zone du programme, cette valeur nous laissant même un peu de marge. Par ailleurs, dans chaque entrée du cache, on souhaite pouvoir stocker des données stockées à des adresses proches. Mettons que l'on parcoure à plusieurs reprises un tableau, alors on souhaite pouvoir stocker toutes ses données dans une même entrée du cache, pour minimiser le nombre de miss. La taille d'un block est donc donnée par min(la moitié de la taille du plus grand tableau , 1kb). On utilise autant de ways que l'on souhaite pouvoir lire de données en même temps (par exemple si on lit deux tableaux en parallèle), et on déduit le nombre de lignes des informations précédentes.

Pour le cache d'instructions, on lui donne une taille de 256kB. Chacun des blocs est taille min(la plus grande boucle, 1kb). En effet, on souhaite pouvoir stocker toute une boucle d'un coup, puisqu'on accédera de manière répétée à chacune de ses instructions. Comme plusieurs boucles ne s'exécuteront à priori pas en parallèle, on met une seule way, et on met suffisamment de lines pour atteindre la taille maximale.

  1. Les données ne sont pas toujours accédées de la même manière. Pour un tableau, on accède à des données consécutives sur une grande plage (locality) alors que pour un compteur on accède régulièrement à la même adresse. Si le programme inclue de grands parcours de tableaux, augementer le nombre de blocs est une bonne idée car augmente la spatialité. Cependant, s'il s'agit d'accès répétés à une même adresse, cela impliquerait la sauvegarde en cache de beaucoup de données inutiles. Il vaut mieux préférer la temporality avec des ways. On rencontre alors des problèmes quand on mélange les deux concepts. Il faut bien prévoir le nombre de blocs et ways.

**Les boucles peuvent poser des gros soucis. Si une boucle fait 17 instructions et que les blocs utilsés ne font que 16, alors il y aura un miss à chauque fois. Il faut choisir entre doubler la taille pour seulement une instruction ou accepter un miss à chaque tour, qui entraine aussi la réécriture de 15 instructions inutiles. **

  1. Pour illustrer les différents types d'erreurs, on part d'un grand cache (2¹⁰ entrées). On a alors uniquement des compulsory misses, puisque le cache est assez grand pour stocker toutes les données. On diminue alors la taille du cache (2⁸ entrées), et des conflict misses commencent à apparaître, car le cache ne peut plus stocker toutes les données. Enfin, lorsqu'on passe à 2⁶ entrés, on a aussi des capacity misses.

Par ailleurs, on écrit souvent à la même adresse, celle de buf[minIndex], qui naturellement change peu. Une politique write-allocate évite donc beaucoup de write misses. On le voit bien avec les chiffres, puisque avec une politque write-no-allocate on a 110 misses, contre seulement 7 avec write-allocate.