JSimVEM et JSimCache: des outils pédagogiques pour appréhender les hiérarchies mémoires

Résumé

Nous présentons dans ce document deux outils à but pédagogique dont l'objectif principal est d'illustrer le principe de fonctionnement d'une hiérarchie mémoire à un ou plusieurs niveaux. La simulation d'une hiérarchie mémoire particulière s'appuie sur une configuration mémoire mais aussi et surtout sur une exécution de programme. En effet, pour montrer le fonctionnement d'un système constitué de mémoires caches, il est nécessaire de se donner une application et d'observer comment le système met à profit les caches afin d'exécuter l'application plus rapidement. Il est donc nécessaire de disposer d'un outil permettant d'extraire les accès mémoires réalisés par le processeur lors de l'exécution de l'application. durant son exécution. Pour cela nous allons utiliser un simulateur de processeurs. Le simulateur de processeurs dont nous avons besoin est un outil simple permettant l'exécution d'une application écrite en assembleur et indiquant, pour chaque instruction, s'il y a, ou non, un accès à la mémoire. Si c'est le cas, alors le simulateur doit indiquer quel type d'accès mémoire est réalisé (lecture d'une donnée, écriture d'une donnée, lecture d'une instruction) et à quelle adresse.

Ce document illustre l'utilisation de deux simulateurs, le premier (JSimVEM) permet de simuler le comportement d'un processeur de type Von Neumann, le second (JSimCache) permet la simulation d'une hiéarchie mémoire. L'étude que nous allons mener porte sur une application simple de type calcul numérique, il s'agit du produit de matrices.

Introduction

L'enseignement des architectures des processeurs est un aspect important de la formation des ingénieurs de la filière Electronique et Informatique Industrielle de l'ENSSAT (Ecole Nationale Supérieure des Sciences Appliquées et de Technologie). Nous pensons que ces futurs ingénieurs seront, au cours de leur carrière, confrontés aux développements de codes sur des processeurs de type traitement du signal (DSP). Or, il est évident que dans ce contexte, les algorithmes à implémenter sont toujours assujetis à une contrainte de temps d'exécution qui conduit globalement à ce que les développeurs soient amenés à écrire, ou à retoucher, le code assembleur à hauteur de 80 % du code total de l'application. Partant de cette constatation, il est alors important que nos futurs ingénieurs aient des connaissances assez précises concernant les techniques qui sont mises en oeuvre dans les processeurs récents, techniques qui migrent petit à petit vers les processeurs de traitement du signal.

Les étudiants abordent le thème des architectures de processeurs en première année par une immersion en douceur via le modèle de processeur Von Neumann. L'évolution des processeurs est commentée et l'on montre, notamment, l'accroissement important de la complexité des jeux d'instructions. La famille des processeurs Intel sert de base à l'illustration de cette évolution pour des raisons évidentes de notoriété de ce constructeur. Le concept de machine RISC (Reduced Instruction Set Computer) est ensuite présenté en montrant que l'évolution des jeux d'instructions a conduit à une utilisation très disparate des instructions d'un processeur complexe et en indiquant que certaines instructions sont finalement très peu utilisées par les programmes classiques. La règle des 90-10 est énoncée, indiquant que le processeur passe 90 % de son temps à exécuter seulement 10 % de son jeu d'instructions.

Vient ensuite la présentation du concept de fonctionnement à la chaîne, appelé fonctionnement pipeline. Ce principe étant posé, on montre tout l'intérêt d'un tel fonctionnement et on insiste sur le fait que celui-ci n'est vraiment intéressant que dans le cas où le pipeline est alimenté de façon permanente. On montre ensuite comment les processeurs implémentent ce concept en découpant le contrôleur d'exécution des instructions en étapes de base (classiquement, les étapes de Lecture d'Instruction, de Décodage d'Instruction, d'Exécution d'Instruction et de Rangement de Résultat).


Un autre point important concernant l'organisation mémoire est aussi traité. Il s'agit ici de montrer comment on peut tirer parti de la mise en place d'une hiérarchie mémoire afin d'augmenter les performances d'un système à base de processeur. Le fonctionnement des mémoires caches est présenté sur une structure à un seul niveau de hiérarchie. Les techniques classiques de remplacement de blocs (LRU, FIFO, Random), d'associativité, d'écriture des données (write back, write through) sont discutées. Une séance de travaux dirigés est consacrée à l'étude sous l'aspect coût et performances de la mise en place d'une hiérarchie mémoire. Lors de cette séance de travaux dirigés, les étudiants observent que l'étude de performances, pour une application complexe, est longue et fastidieuse. Une séance de travaux pratiques est ensuite planifiée afin que les étudiants manipulent un outil de simulation de mémoires caches. Il s'agit alors de reprendre l'étude effectuée en séance de travaux dirigés, mais en approfondissant l'ensemble des configurations de mémoire cache possible afin d'étudier les effets des paramètres tels que : la taille des blocs, la politique de remplacement de blocs, la politique d'écriture dans le cache, l'associativité, etc.

La suite de ce document présente les deux outils qui seront manipulés pour cette séance de travaux pratiques. Nous présentons ensuite l'exemple du produit de matrices servant de base à l'étude du système de mémoire cache.

Infrastructure logicielle développée

Ce TP s'appuie donc sur deux outils :

Ces deux outils étant développés sur le même principe et sur les mêmes objectifs, nous ne développons ci-dessous que la structure du simulateur de processeurs.

Lors de l'étude de conception du simulateur de processeurs, nous avons souhaité avoir une organisation facilitant le développement et la maintenance de l'outil. De plus, nous souhaitions pouvoir réutiliser des composants développés dans ce simulateur, pour d'autres outils de la même famille. Nous avons aussi souhaité que ce simulateur de processeurs puisse être manipulé de deux manières différentes : par l'intermédiaire d'un terminal, ou par l'intermédiaire d'une interface graphique conviviale.

Cet ensemble d'objectifs nous a conduit à organiser notre outil en quatre niveaux (voir figure ci-dessous) :

Exemples

L'exemple que nous détaillons ici est le produit de matrices dont le code C est donné ci-dessous : 

      for (i = 0 ; i < N ; i++) {
          for (j = 0 ; j < N ; j++) {
              tmp = 0 ;
              for (k = 0 ; k < N ; k++) {
                  tmp = tmp + A[i][k] * B[k][j] ;
              }
              C[i][j] = tmp;
          }
      }

Le simulateur de processeur que nous utilisons travaille sur du code assembleur. Nous donnons ci-dessous ce code assembleur pour ce modèle de processeur. 

.data 	0
.global a
	1 1 1 1 1 1 1 1
	2 2 2 2 2 2 2 2
	3 3 3 3 3 3 3 3
	4 4 4 4 4 4 4 4
	5 5 5 5 5 5 5 5
	6 6 6 6 6 6 6 6
	7 7 7 7 7 7 7 7
	8 8 8 8 8 8 8 8
.global b
	1 1 1 1 1 1 1 1
	2 2 2 2 2 2 2 2
	3 3 3 3 3 3 3 3
	4 4 4 4 4 4 4 4
	5 5 5 5 5 5 5 5
	6 6 6 6 6 6 6 6
	7 7 7 7 7 7 7 7
	8 8 8 8 8 8 8 8
.global c
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 0
	0 0 0 0 0 0 0 0
.alias n 8
.alias n2 64
.program 100
	li R1, a
	li R2, b
	li R3, c
	li R4, n
	li R10, n
	li R11, n2
.boucle1
	li R5, n
.boucle2
	li R6, n
	li R7, 0
.boucle3
	li R8, (R1)
	li R9, (R2)
	mult R9, R9, R8
	add R7, R7, R9
	add R1, R1, 1
	add R2, R2, 1
	sub R6, R6, 1
	brnz R6, boucle3
	si (R3), R7
	add R3, R3, 1
	sub R1, R1, R10
	sub R5, R5, 1
	brnz R5, boucle2
	add R1, R1, R10
	sub R2, R2, R11
	sub R4, R4, 1
	brnz R4, boucle1
	exit
.end

Ce code se décompose en deux parties :

Pour simuler ce code, nous devons tout d'abord lancer l'outil JSimVEM.

Une fois la liste des accès mémoire obtenue, nous allons nous intéresser au comportement de la hiérarchie mémoire. Pour cela nous allons utiliser l'outil JSimCache qui permet la simulation de hiérarchies mémoires allant jusqu'à 3 niveaux de mémoires cache.

Questions

Informations techniques concernant JSimVEM

JSimVEM a été développé avec pour principal objectif, l'illustration du cours d'architecture des processeurs de type Von Neumann. Le nom de ce simulateur correspond aux initiales des personnes qui ont défini l'architecture de ce que l'on appelle couramment les processeurs Von Neumann, ces trois personnes sont J.Von Neumann, J.P.Eckert et J.Mauchly.

Quelques détails techniques :

Liste des instructions supportées :

1) Instructions de transferts
li, si chargement/rangement mot vers/depuis des registres entiers
lf, sf chargement/rangement mot vers/depuis des registres flottants
move transfert entre registres
cmovz, cmovnz, cmovp, cmovp transfert conditionnel entre registres
2) Instructions arithmétiques et logiques
add, addf addition sur des entiers et flottants
sub, subf soustraction sur des entiers et flottants
mult, multf multiplication sur des entiers et flottants
and, nand et, non et
or, nor, xor ou, non ou, ou exclusif
3) Instructions de contrôle
br branchement inconditionnel
brz, brnz branchement si registre égal/non égal à zéro
brp, brn branchement si registre positif/négatif
nop opération qui ne fait rien
exit fin du programme


Informations techniques concernant JSimCache

JSimCache a été développé avec pour principal objectif l'illustration du concept de hiérarchie mémoire étudié dans le cours d'architecture des processeurs.

Ce simulateur a été développé dans le cadre du projet technologique de 3eme année par une étudiante de la filière informatique de l'ENSSAT. Ce travail a débuté en septembre 2002 pour se terminer en juin 2003. Le développement a été réalisé en Java et s'appuie sur une modélisation de la hiérarchie mémoire, la mise en place d'un moteur de simulation et enfin l'ajout d'une interface graphique pour configurer et solliciter le système.