INF2171 - Notes de cours

Du concept à aujourd’hui : principes et évolution

La machine de Turing
La mémoire contient les instructions et les données. Un oracle
connaît la séquence d’instructions à exécuter, si une case n’est pas
touchée on ne sait si le contenu est une instruction ou une donnée.
oracle
Machine de von Neumann
Vers la fin de seconde guerre mondiale, les alliés ont besoin de gérer des inventaires énormes et adoptent
un calculateur pour faciliter cette tâche. Après plusieurs prototypes von Neumann propose ce modèle qui
peut être efficacement mis en œuvre avec les technologies du moment.
Le saut vers une machine concrète passe par la séquencialisation des instructions où le compteur ordinal
remplace l’oracle. Le traitement est confié à une unité dont les actions sont dictées par une unité de
contrôle, elle contrôle les étapes de l’exécution des instructions du début à la fin. Une horloge cadence
toutes les actions dictées par l’unité de contrôle. La mémoire et l’unité de traitement sont jointes par un
bus par lequel transitent données et instructions.

La mémoire est organisée en octets (8bits) puis en

mots de 2, 4 ou 8 octets. On parle alors d’une
architecture 16, 32 ou 64 bits, etc... Chaque octet
(byte) est individuellement adressable. Les
registres sont des mémoires très rapides qui
servent de temporaires.

Comment ça marche une machine?

Unité de traitement
Une unité de traitement de base est l’unité arithmétique et logique.
Les pattes A et B sont les entrées de la fonction, R le résultat, F la fonction désirée
et D des drapeaux d’état levés par l’exécution. Les fonctions disponibles sont filées
(portes logiques) : arithmétiques classiques, trigonométriques etc. puis booléennes.
Cadencée par l’horloge, l’unité de contrôle traite les instructions par étape :
l’instruction est lue de la mémoire, décodée en fonction et adresses (opération et
opérandes), les opérandes sont lus de la mémoire et acheminés à l’unité de
traitement, la fonction exécutée puis le résultat écrit en mémoire.
Par exemple, 3 + a, devient
charge constante 3 instruction→ ual_A
charge variable a mémoire→ ual_B
addition
stockage ual_R → mémoire

boot
Deux pointeurs dédiés sont chargés par la mise en tension (POR - Power On Reset), le compteur ordinal
(pc) qui pointe vers la première instruction et le sommet de pile (sp) qui pointe vers le début de la
mémoire de travail.

une machine à pile

Les pattes de l’ual réfèrent au sommet de pile, une opération avec N opérandes consomme les N derniers
éléments de la pile et pousse le résultat au sommet.
Le classique des calculatrices HP avec la notation polonaise inversée :
15 – 3 * 4 + 5 * 6 devient 15 3 4 * - 5 6 * +

la machine SAC (Support Académique à la Compréhension)

mnemoniques = {
"FIN" : "stop", sp
"CC" : "charger constante", pile
"CM" : "charger mémoire",
"ST" : "stocker",
données
"ADD" : "additionner",
pc code
"SOU" : "soustraire",
"MUL" : "multiplier",
"DIV" : "diviser"
}
0: 010.01000 50 CM 8 ; charger mémoire
1: 001.00011 23 CC 3 ; charger constante
2: 100.00000 80 ADD ; additionner
{'a': 8}

execution ['a', 3, '+'] avec a=4

PC=0, SP=15 MEM= 50 23 80 00 00 00 00 00 04 00 00 00 00 00 00 00 04
PC=1, SP=14 MEM= 50 23 80 00 00 00 00 00 04 00 00 00 00 00 00 03 04
PC=2, SP=15 MEM= 50 23 80 00 00 00 00 00 04 00 00 00 00 00 00 03 07
Un vrai programme – la magie
c - 4 * a + 3 * b

0: 010.10000 50 CM 16 ; charger mémoire

1: 001.00100 24 CC 4 ; charger constante

2: 010.10001 51 CM 17 ; charger mémoire

3: 110.00000 c0 MUL ; multiplier

4: 101.00000 a0 SOU ; soustraire

5: 001.00011 23 CC 3 ; charger constante

6: 010.10010 52 CM 18 ; charger mémoire

7: 110.00000 c0 MUL ; multiplier

8: 100.00000 80 ADD ; additionner

symboles: {'c': 16, 'a': 17, 'b': 18}

memoire code: 50 24 51 c0 a0 23 52 c0 80 00

execution ['c', 4, 'a', '*', '-', 3, 'b', '*', '+'] avec a=4, b=10, c=5

0: 010.10000 50 CM 16 ; charger mémoire

PC=0, SP=47

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 05

1: 001.00100 24 CC 4 ; charger constante

PC=1, SP=46

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 04 05

2: 010.10001 51 CM 17 ; charger mémoire

PC=2, SP=45

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 04 04 05
 3: 110.00000 c0 MUL ; multiplier

PC=3, SP=46

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 04 10 05

4: 101.00000 a0 SOU ; soustraire

PC=4, SP=47

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 04 10 -b

5: 001.00011 23 CC 3 ; charger constante

PC=5, SP=46

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 04 03 -b

6: 010.10010 52 CM 18 ; charger mémoire

PC=6, SP=45

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 0a 03 -b

7: 110.00000 c0 MUL ; multiplier

PC=7, SP=46

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 0a 1e -b

8: 100.00000 80 ADD ; additionner

PC=8, SP=47

00: 50 24 51 c0 a0 23 52 c0 80 00 00 00 00 00 00 00

10: 05 04 0a 00 00 00 00 00 00 00 00 00 00 00 00 00

20: 00 00 00 00 00 00 00 00 00 00 00 00 00 0a 1e 13
C’était pourtant tellement simple!
Imaginez que notre machine consomme 50 cycles par accès mémoire. Prenons comme exemple une
instruction à 2 opérandes, un résultat en mémoire et qui requiert 10 cycles pour le calcul. Nous attendrons
donc 150 cycles pour 10 cycles de travail, ce n’est pas très efficace! Afin d’accélérer l’exécution des
programmes, ne serait-ce pas plus simple de charger les opérandes directement dans les entrées des unités
de traitement?

C’est à ce moment-ci que tout se complique. Cette complexité est principalement liée à la micro-gestion
des résultats intermédiaires. On doit aussi se rappeler quel temporaire contient quoi puisque les
assembleurs ne supportent pas le calcul symbolique contrairement aux langages de haut niveau.

Prenons l’expression ‘c - 4 * a + 3 * b’, la notation post-fixe nous donne toujours ‘c 4 a * - 3 b * +’ mais

maintenant comme que nous n’écrivons plus sur la pile mais directement sur les entrées on doit s’assurer
que les opérandes soient insérés au bon moment, certains résultats intermédiaires doivent être conservés
dans des locations temporaires. L’expression est plus facilement représentée sous forme d’arbre pour
illustrer ce qui se passe.

En respectant la priorité des opérateurs on voit que la

soustraction doit être faite entre ‘c’ et le produit ‘4 * a’
puis que l’addition doit être faite entre cette différence
et le produit ‘3 * b’.

L’utilisation de temporaires respecte la sémantique

de la nouvelle machine.
 La décomposition de l’expression en
séquence d’instructions permet de
conserver la priorité des opérateurs.

Il est possible de démontrer que 2

temporaires sont suffisants pour
stocker les résultats intermédiaires de
toutes les opérations usuelles.

Il est commun d’avoir un temporaire

spécialisé appelé ‘accumulateur’ qui
sert de temporaire récurrent.

Le code pour cette saveur de la machine SAC ressemblera à ceci :

R = ((c - (4 * a)) + (3 * b))

0: 001.0000000000100 2004 CC #4 ; charger constante

2: 010.0000000110001 4031 CM 49 ; charger mémoire

4: 110.0000000000000 c000 MUL ; multiplier

6: 011.0000000110010 6032 ST 50 ; stocker

8: 010.0000000110011 4033 CM 51 ; charger mémoire

a: 010.0000000110010 4032 CM 50 ; charger mémoire

c: 101.0000000000000 a000 SOU ; soustraire

e: 011.0000000110100 6034 ST 52 ; stocker

10: 001.0000000000011 2003 CC #3 ; charger constante

12: 010.0000000110101 4035 CM 53 ; charger mémoire

14: 110.0000000000000 c000 MUL ; multiplier

16: 011.0000000110010 6032 ST 50 ; stocker

18: 010.0000000110100 4034 CM 52 ; charger mémoire

1a: 010.0000000110010 4032 CM 50 ; charger mémoire

1c: 100.0000000000000 8000 ADD ; additionner

1e: 011.0000000110000 6030 ST 48 ; stocker

symboles: {'R': 48, 'a': 49, '@': 50, 'c': 51, '#': 52, 'b': 53}

La taille du code est beaucoup plus élevée que la méthode à pile mais c’est plus rapide. On remarque
également qu’il y a beaucoup de bits qui ne sont pas utilisés dans les encodages des instructions. On
pourrait insérer les petites constantes directement dans les instructions. On pourrait également étendre
les encodages de manière à insérer les références mémoire dans les instructions. On dérive ainsi un jeu
d’instructions complexes qui densifie le code, on parle alors de machine CISC (Complex Instruction Set
Computer). Typiquement ces jeux d’instructions n’ont que 2 opérandes où l’une des sources est
également la destination.

Pour gagner en rapidité ces processeurs possèdent des registres dont le temps d’accès est souvent d’un
cycle et l’opérande source-destination est un registre. L’instruction contiendra maintenant le code
d’opération, le mode des opérandes et les opérandes. Les modes de base sont les couples : registre-
registre, registre-mémoire et registre-constante. Les registres sont préfixés d’un R ou $, les constantes
d’un #. Le choix de mode ajoute à la difficulté inhérente à l’utilisation du langage d’assemblage d’une
machine.

Le code pour cette saveur de la machine SAC ressemblera à ceci :

R =((c - (4 * a)) + (3 * b))

0: 001.01.1.0000000100 2c04 CH r1,#4 ; charger registre,constante

2: 101.00.1.0000100001 a421 MUL r1,33 ; multiplier registre,memoire

4: 001.00.0.0000100010 2022 CH r0,34 ; charger registre,memoire

6: 100.10.0.0000000001 9001 SOU r0,r1 ; soustraire registre,registre

8: 001.01.1.0000000011 2c03 CH r1,#3 ; charger registre,constante

10: 101.00.1.0000100011 a423 MUL r1,35 ; multiplier registre,memoire

12: 011.10.0.0000000001 7001 ADD r0,r1 ; additionner registre,registre

14: 010.00.0.0000100000 4020 ST r0,32 ; stocker registre,memoire

symboles: {'R': 32, 'a': 33, 'c': 34, 'b': 35}

Le code est maintenant plus succint. La complexité des instructions s’avère un défi pour la rapidité
d’exécution et la combinaison source-destination détruit une des sources qui ne peut être réutilisée sans
une copie. A la fin des années ‘80 les architectures RISC (Reduced Instruction Set Complexity) mettent
en branle 2 changements, les instructions compterons sur 2 sources et une destination puis les opérations
n’auront que des registres ou des constantes comme opérandes. Ces architectures ‘load-store’ permettront
d’intercaler opérations mémoire lentes et registre rapides. Les rapides exécutent durant les accès mémoire
afin d’augmenter la cadence de production de résultats. Le RISC-V est le dernier né de cette gamme
d’architecture, évidemment plus de registres et de contraintes rend l’utilisation de l’assembleur un peu
plus complexe.

Le code pour cette saveur de la machine SAC ressemblera à ceci :

R = ((c - (a * 4)) + (b * 3))

0: 001.1.000.000100001 3021 CH r0,33 ; charger registre,memoire

2: 001.1.001.000100010 3222 CH r1,34 ; charger registre,memoire

4: [Link].000100 a444 MUL r2,r1,#4 ; multiplier registre,constante

6: [Link].010.000 9610 SOU r3,r0,r2 ; soustraire registre,registre

8: 001.1.100.000100011 3823 CH r4,35 ; charger registre,memoire

10: [Link].000011 a503 MUL r2,r4,#3 ; multiplier registre,constante

12: [Link].010.000 76d0 ADD r3,r3,r2 ; additionner registre,registre

14: 010.1.011.000100000 5620 ST r3,32 ; stocker registre,mémoire

symboles: {'R': 32, 'c': 33, 'a': 34, 'b': 35}

Pour le cours nous n’utiliserons que l’assembleur RISC-V pour une architecture 32bits.

Voici le même calcul R = c - a * 4 + b * 3 pour cette machine :

la a5,c
lw a4,0(a5)
la a5,a
lw a5,0(a5)
slli a5,a5,0x2 # a * 4
sub a3,a4,a5 # c - a * 4
la a5,b
lw a4,0(a5)
mv a5,a4
slli a5,a5,0x1 # b * 2
add a5,a5,a4 # + b
add a5,a3,a5 # R = …
mv a0,a5
Support aux langages de programmation
Les langages de programmation offrent des structures de contrôle, les conditionnels et les boucles. Une
boucle peut être décrite comme une condition remplie qui se répète une ou plusieurs fois. Notre machine
doit ainsi pouvoir comparer 2 quantités.
Le signe de la différence entre 2 valeurs sert d’indicateur pour les branchements conditionnels qui
modifient le compteur ordinal avec la destination lorsque la condition est remplie.
Condition == != < <= > >=
A-B 0 !0 - - ou 0 + + ou 0
mnémonique be bne blt ble bgt bge
Le branchement inconditionnel complète le tout.
Voici un exemple si <condition> <énoncé > sinon <condition> <énoncé >
la a4,v1
lb a4,(a4)
la a5,v2
lb a5,(a5)
# if (v1 < v2)
bge a4,a5,else
addi a4,a4,1
j fin
else:
addi a4,a4,-1
fin:
et d’une boucle tant que <condition> <énoncé >:
la a4,v1
lb a4,(a4)
li a5,5
# while (v1 < 5)
debut:
bge a4, a5, fin
addi a4, a4, 1
j debut
fin:

Les routines reçoivent un support particulier : appel (call) et retour (ret). Chaque routine défini des
variables locales. Peu importe le nombre d’appels ces variables sont indépendantes d’un contexte à
l’autre. A l’exécution on crée, sur la pile, un cadre d’activation pour chaque appel qui contient les
variables locales, les paramètres sortants, les temporaires de calcul et une zone de sauvegarde pour
préserver les registres de l’appelant qui doivent être préservées afin d’être restituées pour poursuivre son
exécution au retour de cet appel.

proc A() : proc B() : - A A A A A A A -

B() D() B B B C
C() D

Les variables globales existent hors du contexte des routines, elles doivent être allouées en mémoire et
sont initialisées au départ de l’exécution du programme lorsqu’il est chargé en mémoire de travail. Ces
données, constantes (lecture seulement) et chaînes (strings) sont agglomérées dans des segments bien
définis de l’espace d’adressage du programme. Cet espace contient déjà la pile et le code.

Il nous reste à voir l’espace occupé dynamiquement par le programme au cours de l’exécution, le tas
(heap). Cet espace contient les objets alloués par la création de nouvelles instances de classes ainsi que
la mémoire allouée et associée à un pointeur. La gestion du tas est typiquement cachée (outre new, delete)
dans des bibliothèques système (standard runtime libraries).

Sommet pile pile

tas
Variable système
Espace non occupé

données

Compteur ordinal
code