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)