Architecture Et Organisation Des Ordinateurs

IPGP .

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Architecture et organisation des ordinateurs une introduction J. P. Vilotte et P. Favreau

Page d’accueil

[email protected]

Page de Titre

November 8, 2002

Sommaire

JJ

II

J

I

Page 1 de 37 Retour Full Screen Fermer Quitter

R´ esum´ e Ce cours est une introduction succinte aux concepts de base de l’architecture et de l’organisation des ordinateurs. Elle a pour but de mieux en comprendre le fonctionnement. L’attention est port´ee sur les structures communes essentielles sans entrer dans les details des diverses architectures. Ces notions doivent premettre de mieux analyser les performances d’un programme et d’aider `a son optimisation.

IPGP .

Quelques r´ ef´ erences

Introduction ´ ements de base . . . El´ Processeurs M´ emoires

Voici quelques r´ef´erences disponibles dans les biblioth`eques de Jussieu :

Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil

Technologie d’ordinateurs et des r´ eseaux, P.A. Goupille, Ed. Masson Computer Organization & Design The Hardware/Software Interface, D.A. Patterson, J.L. Henessy, Ed. Morgan Kaufmann.

Page de Titre Sommaire

JJ

II

J

I

Page 2 de 37 Retour Full Screen Fermer Quitter

Computer Architecture. A quantitative approach, J.L. Henessy, D.A. Patterson, Ed. Morgan Kaufman. Architecture de l’ordinateur A. Tanenbaum, Ed. Dunod. Vous pouvez ´egalement consulter les divers documents sur le Web .... a vous de jouer avec votre moteur de recherche pr´ef´er´e !

IPGP .

1. Introduction Un language de programmation ´evolu´e (F90, C, C++, Java)

Introduction ´ ements de base . . . El´

❒

abstraction

Processeurs

❒

portabilit´e

M´ emoires

Un Compilateur :

Bus Syst` eme d’exploitation

❒

un programme qui traduit en assembleur

❒

en g´en´eral efficace

Repr´ esentation des . . .

Page d’accueil

Il y a des situations o` u le programmeur doit utiliser la connaissance de l’architecture de l’ordinateur de mani`ere `a optimiser son application :

Page de Titre

1. optimisation du temps de calcul ; Sommaire

JJ

II

J

I

Page 3 de 37 Retour Full Screen Fermer Quitter

2. ordinateurs trop complexes pour le compilateur ; 3. ordinateurs trop r´ecents pour le compilateur. Le but de cette introduction : fournir les concepts de base pour comprendre • quand les performances du programme ne correspondent pas aux capacit´es de l’ordinateur ; • les techniques d’optimisation des performances ; • quand il est n´ecessaire de sacrifier au niveau d’abstraction et de portabilit´e.

IPGP .

´ ements de base de l’architecture d’un ordinateur 2. El´

Introduction

Les composants de base d’un ordinateur sont :

´ ements de base . . . El´ Processeurs

✒

le processeur ;

✒

la m´emoire ;

✒

les entr´ees/sorties ;

✒

le bus ou r´eseau d’interconnexion

M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre CPU clavier

Sommaire

JJ

II

J

I

écran

BUS

Page 4 de 37 disque dur

Retour Full Screen Fermer Quitter

mémoire (RAM)

CD-ROM

IPGP .

´ ements de base de l’architecture d’un ordinateur El´ ❒

Introduction

Le Processeur c’est le moteur et le “cerveau” du syst`eme :

´ ements de base . . . El´

. ex´ecute un programme : instructions arithm´etiques et logiques ;

Processeurs

. seul composant qui cr`ee de l’information ;

M´ emoires

. avant un seul processeur unique Central processing unit ou CPU ;

Bus Syst` eme d’exploitation

❒

Repr´ esentation des . . .

La m´ emoire est un composant passif qui stocke de l’information : . fournit instructions et donn´ees aux processeurs ; . source ou destination des transferts de type E/S ; . informations acc´ed´ees par leur adresse ;

Page d’accueil

. vue comme un tableau M [x] :

Page de Titre

→ envoyer instruction `a l’adresse M [1000] ; → stocker le bloc de donn´ees entre M [0] et M [255] ;

Sommaire

JJ

II

J

I

❒

. vers l’ext´erieur ou d’autres composants . n’alt`erent pas l’information . peuvent regrouper des m´emoires secondaires (disques, bandes ...) ou des composants d’interaction type ´ecran, souris, clavier ....

Page 5 de 37 Retour Full Screen Fermer Quitter

Les entr´ ees/sorties trasnf`erent l’information

❒

Les r´ eseaux d’interconnexion entre les composants . simples liens ou commutateurs complexes

IPGP .

Diagramme PMS du Macintosh Dans un diagramme PMS, chaque composant est represent´e par une simple lettre

Introduction ´ ements de base . . . El´ Processeurs

✑

P pour processeur ;

✑

M pour m´emoire ;

✑

S pour commutateur.

M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

Page 6 de 37 Retour Full Screen Fermer Quitter

IPGP .

3. Processeurs Les principales composantes structurelles sont :

Introduction ´ ements de base . . . El´

❒

les registres : de la m´emoire interne au CPU. Certains registres ne sont pas accessibles au programmeur.

❒

l’unit´ e arithm´ etique et logique (ALU) : c’est l’unit´e qui r´ealise les diff´erentes op´erations sur les donn´ees.

Repr´ esentation des . . .

❒

l’unit´ e de contrˆ ole : elle contrˆole le fonctionnement du CPU et par cons´equent de l’ordinateur.

Page d’accueil

❒

l’interconnexion interne du CPU : les m´ecanismes n´ecessaires pour faire communiquer entre eux le CPU, l’ALU et les registres.

Processeurs M´ emoires Bus Syst` eme d’exploitation

Page de Titre Sommaire

JJ

II

J

I

Page 7 de 37 Retour Full Screen Fermer Quitter

IPGP .

3.1. L’unit´ e de contrˆ ole registres (mémoire) registre 0

Introduction ´ ements de base . . . El´

registre 1

Processeurs

unité arithmétique et logique

registre 2

M´ emoires registre 3

Bus Syst` eme d’exploitation Repr´ esentation des . . .

registre d’instruction (IR)

unité de contrôle (machine à états)

pointeur d’instruction (PC)

Page d’accueil Page de Titre Sommaire

L’op´eration d’un processeur est caract´eris´ee par un cycle fetch-decode-execute Slide 1

JJ

II

J

I

Page 8 de 37

1. fetch : demander `a la m´emoire une instruction dont l’adresse est stock´ee dans un registre interne, le program counter ou PC ; 2. decode : stocker et d´ecoder l’information retourn´ee par la m´emoire dans le registre d’instruction, instruction register ou IR : une seule instruction machine, cod´ee comme un nombre binaire. Le processeur d´ecode la valeur dans l’IR afin de d´eterminer les op´erations `a effectuer.

Retour

3. execution : r´ealiser l’instruction → d’autres op´erations m´emoire. Full Screen Fermer Quitter

4. r´ep´etition : incr´ementer s´equentiellement l’adresse contenue dans le PC.

IPGP .

3.2. Les instructions Les instructions sont class´ees en 3 types :

Introduction ´ ements de base . . . El´

Arithm´etiques/Logiques :

Processeurs M´ emoires

✑

fonctions primitives de 1 `a 2 arguments : addition, multiplication, ou logique (AND, OR, ..) ;

✑

arguments demand´es `a la m´emoire centrale ou le plus souvent stock´es dans les registres du CPU (plusieurs registres disponibles).

Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil

Transfert de donn´ees : ✑

Page de Titre

instructions pour d´eplacer des donn´ees d’une location `a une autre : entre les registres, de la m´emoire centrale aux registres, entre diff´erents endroits de la m´emoire, initialisation des E/S.

Sommaire

Instructions de contrˆole :

JJ

II

J

I

✑

DO 10 I=1,5 ... 10 CONTINUE

Page 9 de 37 Retour Full Screen Fermer Quitter

modifient l’ordre dans lequel les instructions sont execut´ees

✑

CONTINUE implique une instruction arithm´etique (I = I + 1) et un test de branchement (I ≤ 5). Le branchement est r´ealiser en assignant au PC l’adresse de l’instruction du d´ebut de la boucle.

IPGP .

3.3. Le temps d’execution Le temps d’ex´ ecution du cycle fetch-decode-execute d´epend de :

Introduction ´ ements de base . . . El´ Processeurs

❒

la construction interne du processeur ;

❒

la complexit´e de l’instruction `a ex´ecuter.

M´ emoires

L’unit´e quantique de temps est le cycle d’horloge :

Bus Syst` eme d’exploitation Repr´ esentation des . . .

✑

op´erations au sein d’un processeur control´ees par une horloge externe : circuit g´en´erant une onde cr´eneau de p´eriode fix´ee ;

Page d’accueil

✑

le nombre de cycles d’horloge pour effectuer une op´eration d´etermine le temps.

Page de Titre Sommaire

JJ

II

J

I

☞

Si une multiplication est effectu´ee en tm nanosecondes, ne pas en d´eduire que n multiplications prendont n · tm . Si un branchement d’instruction prend tb nanosecondes, ne pas en d´eduire que l’instruction suivante d´ebutera tb nanosecondes apres le branchement.

☞

Le temps r´ eel d´ epend de l’organisation du syst` eme de m´ emoire et des r´ eseaux de communication

Page 10 de 37 Retour Full Screen Fermer Quitter

IPGP .

Les diverses communications

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

Page 11 de 37 Retour Full Screen Fermer Quitter

IPGP .

4. M´ emoires syst`emes de stockage des donn´ees et des instructions

Introduction ´ ements de base . . . El´ Processeurs

Le composant le plus divers d’un ordinateur en termes de technologie, organisation, performance et coˆ ut.

M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

On abordera simplement : ❒

l’organisation g´en´erale et performances

❒

la m´emoire “interne” : RAM, registres, cˆaches

❒

la m´emoire “externe” : p´eriph´eriques de stockage, disques magn´etiques ....

Page d’accueil Page de Titre

Les m´emoires sont caract´eris´ees par leur : Sommaire

JJ

II

J

I

Page 12 de 37 Retour Full Screen Fermer Quitter

✑

fonction ;

✑

capacit´e ;

✑

temps de r´eponse.

Les op´erations sur les m´emoires sont : 1. lecture 2. ´ecriture

IPGP .

Les m´ emoires internes sur la carte m` ere

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

Page 13 de 37 Retour Full Screen Fermer Quitter

IPGP .

4.1. Unit´ e et Capacit´ e

Introduction ´ ements de base . . . El´

Un peu de terminologie

Processeurs M´ emoires Bus

❒

unit´ e d’information : l’unit´e d’information est le bit (b).

Repr´ esentation des . . .

❒

le mot : l’unit´e ”naturelle” d’organisation de la m´emoire mots de 16, 32 ou 64 bits.

Page d’accueil

❒

unit´ e adressable : la taille de l’unit´e adressable en m´emoire est soit le mot soit l’octet (O). L’octet est une information de 8 bits.

❒

capacit´ e : quantit´e d’information pouvant ˆetre stock´ee dans la m’emoire : en bit (b) ou kilobit (kb). Aujourd’hui, la capacit´e est g´en´eralement exprim´ee en octet, megaoctet (Mo) ou gigaoctet (Go).

❒

unit´ e de transfert : le quantit´e d’information qui peut ˆetre lue ou ´ecrite en m´emoire en une seule fois (octet, bloc).

❒

taux de transfert : d´ebit (bits/sec) de transfert depuis/vers la m´emoire.

Syst` eme d’exploitation

Page de Titre Sommaire

JJ

II

J

I

Page 14 de 37 Retour Full Screen Fermer Quitter

IPGP .

4.2. Performance

Introduction ´ ements de base . . . El´ Processeurs M´ emoires

La performance d’un syst`eme de m´emoire est d´efinie par :

Bus Syst` eme d’exploitation Repr´ esentation des . . .

1. Le temps de latence, ou temps d’acc`es • rapidit´e de la r´eponse `a une demande de lecture ou d’´ecriture

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

Page 15 de 37 Retour Full Screen Fermer Quitter

. d´epend de plusieurs facteurs : organisation de l’information en m´emoire, latence du bus . typiquement de 80 ns `a 10 ns pour le cˆache ou les registres 2. Le temps de cycle • temps minimum entre deux requˆetes successives . un syst`eme avec une latence de 80 ns ne peut avoir un temps de cycle inf´erieur `a 80 ns !

IPGP .

4.3. Localit´ e de r´ ef´ erence La structure des r´ef´erences n’est pas al´eatoire mais clusteris´ee

Introduction ´ ements de base . . . El´

• source de r´egularit´e ←- instructions stock´ees s´equentiellement en m´emoire, instructions en boucle, tableaux et arrangements des donn´ees

Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

• si le processeur requiert au temps t une instruction en x, forte probabilit´e pour qu’au temps t+δt, il requiert une instruction en x+1 idem pour les donn´ees : op´erations sur les vecteurs Localit´e de r´ef´erence sugg`ere une hi´erarchie de m´emoires ❒

Au sommet, une m´emoire tr`es rapide prˆoche du processeur le cˆache. Capacit´e assez faible, temps d’acc`es tr`es rapide (≤ 0.1µs). Certains syst`emes ont plusieurs niveaux de cˆaches et des buffers d’instructions.

❒

Au milieu, la m´emoire centrale, ou primaire : plus grande capacit´e mais temps d’acc`es plus faible (≤ 1µs)

❒

A la base, la m´emoire secondaire, souvent sur le disque. Forte capacit´e mais latence importante.

❒

L’unit´e de transfert entre les niveaux de m´emoires : le bloc ou lignes de cˆaches ; les pages entre les m´emoires primaires et secondaires.

❒

Une requˆete satisfaite est un succ`es ou hit. Une requˆete qui implique un transfert entre niveaux de m´emoire est un ´echec. Taux de succ`es ≈ 97% !

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

Page 16 de 37 Retour Full Screen Fermer Quitter

teff = 0.97 · tcache + 0.03 · tmain

IPGP .

Hi´ erarchie de m´ emoires

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

mémoire principale

cache du disque

Sommaire

JJ

II

J

I

disque magnétique

disque optique

bande magnétique

Page 17 de 37 Slide 1

Retour Full Screen Fermer Quitter

coût par bit croissant

Page de Titre

cache

vitesse croissante

Page d’accueil

taille croissante

registres

IPGP .

4.4. Acc` es al´ eatoire : m´ emoires principales ❒

m´emoires `a base de semiconducteurs

Introduction ´ ements de base . . . El´

• chaque information adressable a une adresse physique unique

Processeurs

• adressable dans n’importe quel ordre

M´ emoires

• temps d’acc`es uniforme aux diff´erents objets

Bus Syst` eme d’exploitation

❒

Repr´ esentation des . . .

• DRAM : RAM dynamique . cellule de stockage : condensateur `a rafraˆıchissement p´eriodique . tr`es haute densit´e (m´emoire principale)

Page d’accueil

• SRAM : RAM statique

Page de Titre

. arrangement de type bascules (flip→flop) . plus rapide que la DRAM, plus ch`ere et limit´ee en taille (m´emoire cˆache)

Sommaire

JJ

II

J

I

❒

Page 18 de 37 Retour Full Screen Fermer Quitter

´ RAM (Random Access Memories) : en Lecture/Ecriture

ROM (Read Only Memories) : en Lecture seulement • ROM : stockage permanent • PROM : programmable une fois par l’utilisateur • EPROM : PROM effa¸cable ´electriquement ou par UV . octets programmables individuellements . ´ecriture tr`es longue

IPGP .

Am´ eliorations de la DRAM ❒

Introduction

SDRAM (Synchroneous DRAM) • ´echanges synchronises avec le processeur (synchronis´es `a la vitesse de transfert du bus via horloge externe)

´ ements de base . . . El´ Processeurs ❒

M´ emoires Bus

• ajoˆ ut de 2kb de SDRAM interne • am´elioration dans les m´ecanismes de rafraiˆıchissement

Syst` eme d’exploitation Repr´ esentation des . . . ❒

❒

II

J

I

Page 19 de 37 Retour Full Screen Fermer Quitter

RDRAM (Rambus DRAM) . am´elioration de la structure physique interne de la DRAM . exemple : ajoˆ ut d’un bus 500 Mb/s

Sommaire

JJ

CDRAM (Cache DRAM) . sorte de DRAM mais avec 16 kb de cˆache en multi-lignes

Page d’accueil Page de Titre

EDRAM (Enhanced DRAM)

Les performances de la DRAM am´elior´ees par l’ajoˆ ut de niveaux de cˆache SRAM entre la m´emoire principale et le processeur. ◆

Acc`es associatif . . . .

variante de l’acc`es al´eatoire pour certaines m´emoires cˆaches acc` es selon le contenu et non selon l’ adresse recherche du motif (pattern) en parall` ele sur toute la m´ emoire acc`es tr`es rapide pour de grands volumes, coˆ ut ´elev´e

IPGP .

4.5. M´ emoire cˆ ache

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus

CPU

Syst` eme d’exploitation

mots

Cache

M´emoire

bloc

Repr´ esentation des . . .

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

❒

Un composant essentiel • taille r´eduite • op`ere presque `a la vitesse du processeur

Page 20 de 37

• tr`es ch`ere compar´ee `a la m´emoire primaire • contient des copies de sections de la m´emoire primaire • strat´egies de remplacement : al´eatoire, FIFO, LRU, ...

Retour Full Screen Fermer Quitter

Slide 1

IPGP .

4.6. Interface cˆ ache – m´ emoire principale adresses étiquette

Introduction ´ ements de base . . . El´

bloc

ligne 0 1 2

Processeurs

•

M´ emoires

mémoire 0 1 2 3

bloc 0 (K mots)

•

Bus •

Syst` eme d’exploitation

C

Repr´ esentation des . . . taille du bloc K mots

Page d’accueil

2n -1 taille du mot

Page de Titre Sommaire

JJ

II

J

I

❒

acc`es `a la m´emoire : un bloc transf´er´e en cˆache

❒

stock´e en ligne de cˆache (slot, line, page)

❒

gestion du transfert par le hardware directement

❒

1 emoire, algorithme de remplaceel´ements du dessin du cˆache : Slide cˆache/m´ ment, taille des blocs

❒

la m´emoire : 2n mots adressables pour une adresse unique de n bits divis´ee (logiquement) en blocs de K mots chacun (M = 2n /K nb de blocs) m´emoire cˆache : C lignes de K blocs chacune avec c  M

Page 21 de 37 Retour Full Screen Fermer Quitter

IPGP .

4.7. Interactions CPU-cˆ ache-m´ emoire START

Introduction ´ ements de base . . . El´ Processeurs

Receive address RA from CPU

M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre

Is block containing RA in cache?

Access main memory for block containing RA

No

Yes Allocate cache slot for main memory block

Fetch RA word and deliver to CPU

Sommaire

JJ

II

J

I

Load main memory block into cache slot

Deliver RA word to CPU

Page 22 de 37 Retour DONE

Full Screen Fermer

Figure 4.15 Cache Read Operation Quitter

IPGP .

4.8. Acc` es s´ equentiel et direct : m´ emoires secondaires ou externes

Introduction ´ ements de base . . . El´

1. Acc` es s´ equentiel

Processeurs M´ emoires Bus Syst` eme d’exploitation

❒

la m´emoire est organis´ee en enregistrements (records)

❒

acc`es lin´eaire : • m´ecanisme partag´e de lecture/´ecriture • doit ˆetre positionn´e sur le d´ebut de l’enregistrement • lit l’information stock´ee en m´emoire jusqu’`a l’enregistrement d´esir´e

Repr´ esentation des . . .

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

❒

temps d’acc`es tr`es variable

❒

exemple : unit´es de bande magn´etique ....

2. Acc` es direct ❒

. m´ecanisme de lecture/´ecriture partag´e ❒

temps d’acc`es variable

❒

exemple : disques magn´etiques

Page 23 de 37 Retour Full Screen Fermer Quitter

acc`es al´eatoire `a un bloc de m´emoire et acc`es s´equentiel sur le bloc

IPGP .

5. Bus

Introduction ´ ements de base . . . El´

Un bus permet de transf´erer l’information entre diff´erents modules.

Processeurs ❒

M´ emoires

interconnexion pour r´ealiser les transfert suivants

Bus

• m´ emoires ↔ CPU

Syst` eme d’exploitation

• E/S ↔ CPU

Repr´ esentation des . . . ❒

On repr´esente souvent s´epar´ement les diff´erentes composantes du bus

Page d’accueil

• bus de donn´ees : transfert des donn´ees entre modules

Page de Titre

• bus d’adresses : source et destination de la donn´ee sur le bus • bus de contrˆ ole : contrˆole l’acc`es et l’utilisation des bus

Sommaire

JJ

II

J

CPU

M´emoire

• • •

M´emoire

I/O

• • •

I/O

I lignes de contrˆole

Page 24 de 37 lignes de donn´ee

Retour lignes d’adresse

Full Screen Fermer Quitter

BUS

IPGP .

Bus (suite et fin)

Introduction ´ ements de base . . . El´ Processeurs

❒

interconnexions complexes impliquant plusieurs bus internes.

❒

communications sur un bus : transactions discr`etes avec un sender et un receiver

❒

A l’initiation de la transaction, le module devient maˆıtre du bus protocole d’administration du bus

❒

protocole de communication pour transf´erer l’information

M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre

. mode asynchrone, d´emarre n’importe quand ; . mode synchrone, d´emarre `a temps fixes contrˆol´es par l’horloge interne

Sommaire

JJ

II

J

I

Page 25 de 37 Retour Full Screen Fermer Quitter

❒

performance du bus d´epend de deux param`etres ; • temps de transfert ou latence ; • bande passante (bps) : un bus avec 32 cannaux de donn´ees et qui peut d´elivrer 1,000,000 paquets par seconde a une bande bassante de 32 Mbps.

IPGP .

6. Syst` eme d’exploitation l’ordinateur est un ensemble complexe de services r´esultant de la combinaison entre hardware (architecture et organisation) et logiciel (syst`eme d’exploitation).

Introduction ´ ements de base . . . El´ Processeurs

Les syst`emes d’exploitation sont multi-tˆaches

M´ emoires

• un programme est une description statique d’un algorithme

Bus Syst` eme d’exploitation Repr´ esentation des . . .

• ex´ecuter un programme : syst`eme d´etermine la demande en m´emoire et d´emarre une tˆ ache, ou process, qui est une copie dynamique du programme.

Page d’accueil ✍

Page de Titre Sommaire

exemple : le compilateur C est un programme. Plusieurs utilisateurs compileront leur code en mˆeme temps → plusieures tˆaches en mˆeme temps.

un process peut ˆetre dans 3 ´etats :

JJ

II

1. actif si le CPU ex´ecute le programme correspondant.

J

I

2. suspendu si le process est en attente. Pour r´epartir le temps CPU, chaque process tourne sur une p´eriode de temps (≈ 20ms), puis est mis dans une queue.

Page 26 de 37 Retour Full Screen Fermer Quitter

3. bloqu´ e lorsque le process attend un ´ev`enement externe : E/S ... ! Le temps CPU n’est pas le temps machine : outils de mesure sp´ecifique

IPGP .

7. Repr´ esentation des donn´ ees

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus

Interaction entre programmes et architecture : la repr´esentation des nombres

Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre Sommaire

JJ

II

J

I

Page 27 de 37 Retour Full Screen Fermer Quitter

Le mode de repr´esentation des nombres : ✑

affecte peu les performances ;

✑

affecte fortement la portabilit´e

✍

Attention ! lorsque l’on porte des programmes et/ou des fichiers de donn´ ees d’un syst` eme ` a l’autre

✍

Les nombre et les donn´ees ne sont pas toujours repr´esent´ees de la mˆeme fa¸con

IPGP .

7.1. Syst` eme Binaire

Introduction ´ ements de base . . . El´ Processeurs

❒

Le syst`eme binaire : point de d´epart pour repr´esenter l’information

❒

Chaque objet de la m´emoire (nombres, caract`eres, instructions, ...) est repr´esent´e par une chaˆıne de 1 et de 0

❒

Deux ´etats possibles du syst`eme physique sous-jacent de la m´emoire

M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre

✒

m´ emoire ´ electronique : le 1 correspond `a une r´egion du semiconducteur charg´ee positivement, et le 0 `a une r´egion neutre

✒

support magn´ etique : le 1 correspond `a une portion de la surface avec un flux dans une direction, et le 0 une r´egion avec un flux de sens oppos´e

Sommaire

JJ

II

J

I

Page 28 de 37 Retour Full Screen Fermer Quitter

❒

Syst`emes g`erent des chaˆınes de taille fix´ee de digits binaires ✐

le bit : la plus petite unit´e correspondant `a un digit binaire

✐

l’octet : correspond `a un objet de 8 bits

✐

le mot : correspond `a un objet de 32 bits (ou 64 bits)

IPGP .

7.2. Repr´ esentation d’un entier positif ❒

stocker un entier positif : simplement l’entier en binaire

❒

un nombre stock´e par mot et compl´et´e par des 0 en tˆete de chaˆıne. le mot de 16-bits 0000000000110100 repr´esente 52

❒

une chaˆıne s de n-bits est interpr´et´ee comme :

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation

x=

Repr´ esentation des . . .

Page d’accueil

n X

si × 2n−i

i=1 ❒

compilateurs et codes assembleurs tirent profit du syst`eme binaire ✑

Shift gauche = multiplication par 2 pour un syst`eme de 8-bits: 00000110 (6) → 00001100 (12) un shift `a gauche de n-bits : multiplication par 2n

✑

shift `a droite, division enti`ere par une puissance de 2

Page de Titre Sommaire

JJ

II

❒

op´erations faites en un cycle machine

J

I

❒

2n chaˆınes de n-bits distincts. le plus grand entier repr´esent´e par un mot de n-bits est 2n − 1 les 2n chaˆınes repr´esentent 2n entiers dans [0, · · · 2n − 1] un overflow : valeur plus grande que le plus grand entier repr´esentable pour un syst`eme de 32-bits c’est 232 − 1 = 4, 294, 976, 295

Page 29 de 37 Retour Full Screen Fermer Quitter

IPGP .

7.3. Repr´ esentation d’un entier n´ egatif

Introduction ´ ements de base . . . El´ Processeurs

deux techniques diff´erentes

M´ emoires Bus Syst` eme d’exploitation

❒

Repr´ esentation des . . .

repr´esentation en 2 champs : un pour le signe et un pour la valeur ✑

❒

1-bit (le plus `a gauche) pour le signe avec 1 pour le le signe n´egatif

compl´ementaire `a 2, universellement utilis´e aujourd’hui

Page d’accueil ✑

arithm´etique binaire sur des mots de taille fix´ee : une arithm´etique sur un groupe fini cyclique

✑

si on ajoute 1 au nombre le plus grand (on ignore le pb d’overflow)

Page de Titre Sommaire

JJ

II

J

I

Page 30 de 37 Retour Full Screen Fermer Quitter

1111

...

10000

...

+

✑

1111 1 0000

syst`eme `a n-bits : seuls n premiers bits sont sauv´es → 10000 · · · 0000 ≡ 0

IPGP .

✑

Introduction

arithm´etique modulo 2 : 2n − x ≡ −x, ∀x ∈ [0, 2n − 1] ✍

obtenir - x : inverser chaque bit du nombre x et ajouter 1

✍

un syst`eme de 8-bits : 00000101 = (5) et 11111011 = (251) dans une arithm´etique modulo 28 : 11111011 ≡ -5

´ ements de base . . . El´ Processeurs ✑

M´ emoires

en pratique : on divise les chaˆınes de n-bit en 2 groupes :

Bus Syst` eme d’exploitation

1. les chaˆınes commen¸cant par 0 repr´esentent les entiers positifs

Repr´ esentation des . . .

0 ≤ x ≤ 2n−1 − 1 Page d’accueil

2. les chaˆınes commen¸cant par 1 repr´esentent les entiers n´egatifs

Page de Titre Sommaire

−2n−1 + 1 ≤ x ≤ 0 ✑

Pour d´eterminer l’entier repr´esent´e par une chaˆıne d´ebutant par un 1

JJ

II

✍

Calculer son compl´ement : inversion de chaque bit, ajouter 1

J

I

✍

arithm´etique 8-bits : 11100001

Page 31 de 37 Retour Full Screen Fermer Quitter

. . . .

premier bit est `a 1, ⇒ nombre n´egatif 11100001 → 00011110 + 1 = 000111112 = 3110 donc 11100001 ≡ - 3110 N.B. : si syst`eme ` a 2 champs : 11100001 = - 9710

IPGP .

7.4. Repr´ esentation en point fixe d’un nombre r´ eel

Introduction ´ ements de base . . . El´ Processeurs M´ emoires

❒

notation binaire extensible aux puissances n´egatives de 2

Bus ✍

Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre

la chaˆıne 110.101 interpr´et´ee comme 1 × 22 + 1 × 21 + 0 × 20 + 1 × 2−1 + 0 × 2−2 + 1 × 2−3 = 6.625

❒

Repr´esentation en point fixe : position du point sp´ecifi´ee dans la chaˆıne ✑

les bits ` a gauche ont des poids en puissances positives de 2

✑

les bits ` a droite ont des poids en puissances n´egatives de 2

✍

un mot de 16-bits avec 5-bits `a droite et 11-bits `a gauche du point

Sommaire

JJ

II

J

I

Page 32 de 37 Retour Full Screen Fermer Quitter

0000000011010100 = 6.625 noter que l’on compl`ete par des 0 `a gauche et `a droite

IPGP .

Repr´ esentation en point fixe d’un nombre r´ eel (suite)

Introduction ´ ements de base . . . El´ Processeurs

❒

compromis entre pr´ecision et ´etendu de la repr´esentation

M´ emoires Bus

✑

n-bits pour la fraction : 2n nombres entre deux entiers successifs

Syst` eme d’exploitation

✍

pour des fraction de 5 bits : 32 nombres entre deux entiers successifs

Repr´ esentation des . . .

5<5 Page d’accueil Page de Titre Sommaire

JJ

II

J

I

Page 33 de 37 Retour Full Screen Fermer Quitter

1 2 31 (5.03125) < 5 (5.06250) < . . . < 5 (5.96875) < 6 32 32 32

✑

plus de pr´ecision ⇒ plus de bits dans la partie fractionaire

✑

nombre de bits dans la partie non fractionaire fixe le plus grand nombre positif repr´esentable dans ce syst`eme

✍

avec 11 et 5 bits pour un mot de 16-bits : 11111111111.111112 = 2047.9687510

✍

avec 10 et 6 bits pour un mot de 16-bits : 1111111111.1111112 = 1023.98437510

IPGP .

7.5. Repr´ esentation en virgule flottante d’un nombre r´ eel ❒

bas´ee sur ”la notation scientifique” : 6.022 × 1023

❒

repr´esentation en virgule flottante :

Introduction ´ ements de base . . . El´ Processeurs

1. une base : dans l’exemple 10, pour les ordinateurs 2 ou 16

M´ emoires

2. un exposant : dans l’exemple 23

Bus

3. une mantisse : dans l’exemple 6.022

Syst` eme d’exploitation Repr´ esentation des . . .

❒

la base est fix´ee pour les ordinateurs : 2 champs seulement `a sp´ecifier 110.101 × 20 = 1.10101 × 22 = 6.62510

Page d’accueil ✑

pour un syst`eme de 16-bit : si 10-bits de mantisse et 6-bits d’exposant

Page de Titre

1101010000 000010

Sommaire

JJ

II

J

I

mantisse sur les 10 premiers bits (compl´et´ee par des z´eros) exposant sur les 6 derniers bits ✑

Page 34 de 37 Retour

❒

normalisation la mantisse : 1.000 . . . <  < 1.111 . . . ou 0.1000 . . . <  < 0.1111 . . .

Pour les nombres r´eels (positifs ou n´egatifs) : 3 champs 1. le signe, sur 1-bit 2. la mantisse, sur un nombre fix´e de bits

Full Screen Fermer Quitter

3. l’exposant, sur le reste des bits (entier positif ou n´egatif)

IPGP .

Repr´ esentation en virgule flottante d’un nombre r´ eel (suite)

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . . ❒

Page d’accueil

standard IEEE adopt´e par tous les ordinateurs ✑

Page de Titre Sommaire ✍

JJ

II

J

I ❒

exemple : architectures 32-bits 1. signe : 1-bit 2. mantisse : 23-bits 3. exposant : 8-bit le plus grand nombre : ω = 2126 ≈ 1038 , le plus petit nombre positif :  = 2−150 ≈ 10−47

3 r´egions dans le standard IEE

Page 35 de 37 Retour Full Screen Fermer Quitter

1. nombres positifs : x ∈ [, ω] 2. z´ero 3. nombres n´egatifs : x ∈ [−ω, −]

IPGP .

Repr´ esentation en virgule flottante d’un nombre r´ eel (suite)

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil ❒

Plusieurs points importants pour les programmeurs :

Page de Titre ◆

Sommaire

JJ

II

J

I

Page 36 de 37 Retour Full Screen Fermer Quitter

taille de l’intervalle [−ω, ω] ✍

✍

environ 1038 entiers mais seulement 232 = 109 chaˆınes de 32-bits distinctes ⇒ il y a dans cet intervalle des nombres sans repr´esentation erreur d’arrondi : chaˆıne binaire prˆoche du nombre mais pas une repr´esentation exacte exemple : 1 n’a pas de repr´esentation binaire exacte 1 ≈ 0.0001100110011 . . .

IPGP .

◆

´ecart entre  et z´ero ✑ une erreur d’arrondi qui, au lieu de produire une valeur tr` es faible mais non nulle, produit z´ero s’appelle un underflow ✑ IEE joue sur la d´ enormalisation de la mantisse pour les tr`es petits nombres ✍ la d´ enormalisation autorise une asym´etrie entre l’exposant le plus fort et le plus faible (- 47 au lieu de - 38).

◆

repr´esentation non uniforme des nombres sur [−ω, ω] ✑ tr` es dense au voisinage de z´ero ✑ densit´ e d´ecroit rapidement avec la magnitude

Introduction ´ ements de base . . . El´ Processeurs M´ emoires Bus Syst` eme d’exploitation Repr´ esentation des . . .

Page d’accueil Page de Titre

✍

exemple : syst`eme 16-bits avec 7-bits mantisse et 8-bits exposant. 0.11100002 − 0.11100012 = 0.00000012 ≈ 0.007810

Sommaire

Pour des nombres proches de z´ero, l’exposant est n´egatif : - 100

JJ

II

J

I

Page 37 de 37 Retour Full Screen Fermer Quitter

∆ = 0.00000012 × 2100 ≈ 0.0078 × 10−30 = 7.8 × 10−33 Pour des grands nombres, les exposants sont de l’ordre de 100 ∆ = 0.00000012 × 2100 ≈ 7.8 × 1027