Le model Von Neumann
INF101Introduction aux algorithms et à la programmation
©Guillaume VigeantTraduction de la présentation originale écrite par Greg Phillips
Collège militaire royal du CanadaUne utilisation sans restriction est permise au seins du gouvernement du Canada. Tout autre
utilisation est sujette aux conditions d’unecreative commons license
ORGANISATION D’UN ORDINATEUR
Processeur MémoireVive
MémoireCache
Carte graphique
Périphériques
Processeur (CPU)
Intel pentium 4
UN ARRANGEMENT COMPLEXE DE LOGIQUE COMBINATOIRE ET
SÉQUENTIELLE
EXÉCUTE DESINSTRUCTIONS
INSTRUCTION = OPÉRATION BINAIRE SIMPLE
EXEMPLE:ADDITIONNER DEUX NOMBRES
EXEMPLE:LIRE UNE VALEUR EN MÉMOIRE
/ QUÉRIR
/ Décode
/ Exécute
M
Bus d’Interconnections
Bus des données de la mémoire
Bus des adresses de la mémoire
UALUnité Arithmétique et Logique
Section des registres
SECTION DES REGISTRES:MÉMOIRE LOCALE DU PROCESSEUR
UAL:OPÈRE SUR LES DONNÉES (ADDITION, ET, OU, ETC.)
BUS D’INTERCONNECTIONS :INTERCONNECTE LES REGISTRES,
L’UAL, LA MÉMOIRE
UNITÉ DE CONTRÔLE:GÈRE LE BON FONCTIONNEMENT
DU PROCESSEUR EN ENVOYANT DES SIGNAUX DE CONTRÔLE POUR
CHAQUE ÉTATS DU PROCESSEUR.
COMMENT INTERPRÉTER?
MÉMOIREAdresse en mémoire Contenu
1 000000002 010010103 101111014 101010015 111100116 001001007 000100108 111111119 10101101
Machine à états
• Ne fait qu’une seule chose dans chaque état• Le prochain état est déterminé par l’unité de
contrôle– Se base sur l’état actuel et le contenu des registres
• L’état change à chaque impulsion de l’horloge « clock tick »
/ QUÉRIR
/ Décode
/ Exécute
Acquiers l’instruction de la mémoire et l’inscrit dans le registre d’instruction (IR).
Acquiers la prochaine instruction
Détermine quelle séquence exécuter selon l’instruction
Exécute l’instruction approprié en activant une séquence d’étapes spécifiques.
UN PROCESSEUR RIDICULEMENT SIMPLE:
SUPPOSONS QUE NOUS VOULONS CONSTRUIRE UN PROCESSEUR
QUI…
TRAVAIL AVEC DES VALEUR ENTRE 0 ET
255
Combien de bits?
QUI DOIT ACCÉDER À 64 EMPLACEMENTS
EN MÉMOIRE(POUR LES PROGRAMMES ET LES DONNÉES)
Combien de bits?
• Toute conception de processeur passe par la définition d’un jeux d’instruction– Le vocabulaire d’opérations que le processeur peut exécuter– Chaque instruction nécessite différent circuit logique de
contrôle et d’exécution à même le processeur• L’architecture du jeux d’instruction doit inclure la
définition de certains registres– Emplacements où le processeur peut temporairement
emmagasiner et manipuler les données– Les instructions sont souvent définie comme des opérations
sur le contenu des registres.
Le Intel 8086 (1978) avait été conçu dans le but d’occuper un vide a court terme dans la chaine de production jusqu’à ce que l’ambitieux processeur i432 soit enfin prêt pour la production. Vue que
ce n’était qu’une architecture temporaire, la direction d’Intel n’a donné que trois semaines à l’équipe de design pour définir le jeux d’instruction. Le processeur i432 fût un échec et tous les
processeurs Intel modernes sont basés sur l’architecture du 8086.
• Inclus des instructions pour–(ADD) Additionner deux valeurs–Déterminer le et (AND) logique de
deux valeurs–Incrémenter (INC) une valeur–Sauter (JMP) à une autre adresse
(instruction)
Combien de bits?
• Registre accessible par l’utilisateur:– AC (accumulateur de 8-bits) pour les opérations
mathématique et logiques• Registre système:– PC (compteur du programme 6-bits) contient
l’adresse de la prochaine instruction à être exécuté• Jeux d’instruction– ADD 00aaaaaa ACAC+M[aaaaaa]– AND 01aaaaaa ACAC AND M[aaaaaa]– JMP 10aaaaaa PCaaaaaa– INC 11aaaaaa ACAC+1
M
Bus d’Interconnections
UAL
AR
PC
DR
AC
IR
AR: registre d’adresse– Contient les bits
d’adresse qui sont véhiculé sur le bus d’adresse mémoire.
DR: registre de donné– Contient les données
recueillit du bus de données de la mémoire
IR: registre d’instruction– Contient l’opérateur de
l’instruction
M: mémoire vive
Bus adresseBus données
ARPC
DRMPCPC+1
DRM
IRDR[7..6]ARDR[5..0]
DRM
ACAC+DR ACAC and DR
PCDR[5..0] ACAC +1
Chaque bulle représente un état dans lequel le processeur
exécute une fonction spécifique. Le processeur avance d’un état à
l’autre à chaque impulsion de l’horloge sous la direction de l’unité de contrôle. Combien
d’impulsions de l’horloge est-ce que chaque instruction à
besoin?
UAL
Signal de contrôle(provenant de l’unité de contrôle)
Vers l’AC
AC
DR(provenant du bus)
Additionneur parallèle
Le MUX est un multiplexeur qui a pour tâche de sélectionner lequel des deux entrés de huit bits sera envoyé vers le registre
AC selon le signal de contrôle UALSEL.
PERFORMANCE
HORLOGE PLUS RAPIDE = MEILLEURE
PERFORMANCE
PLUS DE TRAVAIL PAR INSTRUCTION = MEILLEURE PERFORMANCE
MOINS D’ÉTATS PAS INSTRUCTIONS = MEILLEURE PERFORMANCE
ON NE PEUT NORMALEMENT PAS FAIRE LES DEUX…
MICROPROCESSEUR À JEUX D’INSTRUCTION ÉTENDU, OU
CISC (COMPLEX INSTRUCTION SET COMPUTER)
METS L’EMPHASE SUR D’AVANTAGE DE TRAVAIL PAR INSTRUCTIONS
(EXEMPLE.: PENTIUM, CORE I5/I7)
MICROPROCESSEUR À JEUX D’INSTRUCTION RÉDUIT, OU
RISC (REDUCED INSTRUCTION SET COMPUTER)
METS L’EMPHASE SUR LA LIMITATION DES ÉTATS PAR
INSTRUCTIONS(EXEMPLE.: ARM)
• Langage machine– Les programmes sont ultimement stocké en mémoire sous forme de
groupes de bits (instructions) encodant à la fois les opérateurs et les opérandes
– Ces instruction binaires s’appellent « langage machine »• Par exemple.: pour signifier « additionner le contenu de l’emplacement
mémoire 22 à l’accumulateur » on écrit 00010110– 00 signifie « additionner à l’accumulateur » et 010110 signifie 22
• Nos ancêtre ont réellement codé du logiciel de cette manière!
• Langage assembleur– Mémoriser les séquences de bits et les adresses est plutôt difficile
pour un humain.– Un niveau d’abstraction plus haut: les mnémoniques
• Des codes alphabétiques facile à se rappeler (?)• Un mnémonique par opérateur• Généralement écrit en commençant par l’opérateur suivit de l’opérande
– Exemple.: ADD 22 au lieu de 00010110
• Un assembleur est un program qui– Lit un fichier contenant un program écrit en langage
assembleur• Parfois appelé code source
– Produit un fichier contenant le langage machine équivalent• Parfois appelé code objet
• On peut ainsi– Charger le code objet en mémoire
• En utilisant un chargeur de program soit interne ou externe• À partant d’une adresse en mémoire quelconque
– Initialiser le compteur de programme (registre PC) afin qu’il pointe vers notre première instruction
– Démarrer le processeur et voila! Notre program s’exécute.
UN PROCESSEUR UN PEU PLUS COMPLEXE
• Du livre Carpinelli chapitre 6 (suivre le lien sur le site web du cours)
• Quatre registres:PC compteur de programme (16 bits)
• Indique la prochaine instruction à être exécuté• Est la destination des instructions d’embranchement et saut
AC accumulateur (8 bits)• Est la destination de toutes les opérations arithmétiques et logiques
R un registre multifonction (8 bits)• Sert d’opérande pour toutes les opérations arithmétiques et logiques
Z registre zéro (1 bit)• Contient un 1 si le résultat d’une opération arithmétique ou logique
est zéro dans l’accumulateur• N’est pas affecté par les autres opérations• Sert généralement aux décisions d’embranchement.
• Seize instructions, code d’opérateur de 8 bits (opcode)• Γ est une opérande de 16 bits qui représente un emplacement en mémoire
NOP aucune opération (rien faire)LDAC Γ charger AC de l’emplacement en mémoire ΓSTAC Γ stock le contenu de AC à l’emplacement en mémoire ΓMVACtransfert le contenu de AC vers RMOVR transfert le contenu de R vers ACJUMP Γ écrit Γ dans le PCJMPZ Γ si Z = 0, écrit Γ dans le PCJPNZ Γ si Z != 0, écrit Γ dans le PCADD écrit le résultat de AC+R dans AC et met a jour ZSUB écrit le résultat de AC-R dans AC et met a jour ZINAC écrit le résultat de AC+1 dans AC et met a jour ZCLAC écrit 0 dans AC et met a jour ZAND écrit le résultat de AC AND R (bit par bit) dans AC et met a jour ZOR écrit le résultat de AC OR R (bit par bit) dans AC et met a jour ZXOR écrit le résultat de AC XOR R (bit par bit) dans AC et met a jour ZNOT écrit le résultat de NOT AC (bit par bit) dans AC et met a jour Z
• En plus des instructions, la majorité des assembleurs comprennent certaines directives qui affectent leur fonctionnement
• L’assembleur du simulateur de Carpinelli accepte les directives suivantes:– ORG Γ
• Commence à assembler les instructions à l’emplacement Γ
– DB β• Écrit un octet de valeur β en mémoire
– DB Ѡ• Écrit un mot de 16 bits de valeur Ѡ en mémoire
• On peut également ajouter des commentaires en les précédant de point-virgule (;)– Les commentaires n’ont aucun effet sur l’assembleur; Ils sont
uniquement destinés aux humains
But: additionner le contenu des emplacements mémoire 20 et 21 et inscrire le résultat à l’adresse 22• Afin d’écrire votre programme, veillez considérer que:
– On ne peut qu’additionner des nombres qui sont dans les registres AC et R; Le résultat se retrouve dans l’AC
– Le contenu de la mémoire ne peut qu’être transféré dans l’AC mais on peut bouger les valeurs de l’AC vers R et vice versa.
– Seul une valeur contenue dans l’AC peut être transféré vers la mémoire.- On peut donc écrire notre
programme comme suitLDAC 20MVACLDAC 21ADD ; m[20]+m[21]STAC 22JUMP 65535 ; stop!
- On peut aussi initialiser des valeurs en mémoire comme suit:
ORG 20DB 6DB 9
But: Écrire un programme qui calcul le factoriel d’un nombre• Exemple.: pour le nombre 4, calculer 4+3+2+1
Conception initiale de l’algorithme
1. Somme = 02. Compteur = 43. Somme = somme + compteur4. Compteur = compteur – 15. Si compteur != 0 : aller à la ligne 36. stop
ORG 36 ; Les donnés sont stockées à l’emplacement 36DB 4 ; compteur (emplacement 36)DB 1 ; décrément de 1 (emplacement 37)DB 0 ; somme (emplacement 38)ORG 0 ; Le programme commence à l’emplacement 0LDAC 36 ; charger AC avec le compteurMVAC ; copie AC dans R (début de la boucle, emplacement 3)LDAC 38 ; charger AC avec la sommeADD ; AC somme + compteurSTAC 38 ; sauver AC dans la sommeLDAC 37 ; charger AC avec le décrémentMVAC ; copie AC dans RLDAC 36 ; charger AC avec le compteurSUB ; ACcompteur – décrémentSTAC 36 ; Sauver AC dans le compteurJPNZ 3 ; Si AC !=0, sauter à l’emplacement 3 (PC3)JUMP 65535 ; Si non, stop.
• On pourrait simplifier ce programme si– On avait plus de registres
• Spécifiquement, des registres accessible par l’UAL
– On pouvait faire des opérations avec plusieurs registres• Exemple: ADD A, B, C ; (CA+B)
– Le jeux d’instruction contenait une instruction pour décrémenter
– Le jeux d’instruction permettait des opérations directement de la mémoire aux registres
• Le programme serait plus facile à écrire si– Le langage assembleur nous permettait d’inscrire un
« label » et de pouvoir y référer comme une adresse• Très utile pour les sauts (JUMP) et les boucles
• Notre programme doit être stocké à une adresse mémoire particulière pour fonctionner – pourquoi?
• On pourrait éliminer cette limitation avec un adressage relatif– L’opérateur est traité comme un décalage par
rapport au compteur de programme– Exemple: au lieu de dire « sauter à l’adresse 3 »
JUMP 3, on dirait « sauter en arrière de 7 » JUMP *-7 (où * veut dire relatif)