cs208.md

CS208

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Fall 2014: Architecture des Ordinateurs

[TOC]

Systèmes logiques

Introduction: Digital versus analogique

• définitions
  • les fils ont un voltage haut (1) ou bas (0)
  • 4 grandes parties dans un ordinateur (dispositifs d'entrées et de sorties, processeur, mémoire)
  • un bus est un ensemble de fils électriques interconnectant les différents composants
  • l'information est codé en bit, 8 bits forme un byte
  • analogique : les valeurs ne sont pas séparées par des sauts: entre deux valeurs A et B il existe un nombre infini d'autres valeurs
  • digitale (numérique) : une valeur est représentée par une chaîne finie de symboles appelés digits, pas possible de représentée toutes les valeurs par rapport à l'analogique, pas perturbé par un bruit externe
  • information = bits + contexte
  • représentation du nombre $X$ sur un base $\beta$ est donné par l'équation $X=\sum_{i=0}^{N-1}\beta^ix_i$
  • $x_0$ est le chiffre de poids faile, ${x_N}_1$ celui de poids fort
  • les mots ont généralement une longueur de 32 ou 64 bits
  • les adresses de la mémoire ont une unique adresse par mot et dépend de leur premier byte
  • les bytes d'un mot peut être ordonnés de différentes façons
    • big endian : byte de poids fort est mis à l'adresse inférieur
    • little endian : l'inverse

Logique: Principes et opérateurs

• système combinatoire
  • la valeur de la sortie dépend uniquement des entrées
  • table de vérité
  • pour $n$ entrée, la table compte $2^n$ entrées
• système séquentiel
  • dépend des variations dans le temps
  • mémoire
• fonctions logiques de base
  • not (triangle)
  • and (barre droit et arrondi de l'autre côté)
  • or (fer de lance arrondi)
  • xor (même chose mais avec une barre coupant les fils entrant)
• algèbre de Boole pour $+$ et $\cdot$
  • commutativité $a\cdot b=b\cdot a$
  • idempotence $a\cdot a=a$
  • distributivité $a\cdot(b+c)=(a\cdot b)+(a\cdot c)$
  • associativité (parenthèses)
  • consensus $(a\cdot \bar x)+(b\cdot x)+(a\cdot b)=(a\cdot \bar x)+(b\cdot x)$
  • de Morgan $\bar{a\cdot b}=\bar a + \bar b$
• fonctions complètes
  • nand $a\Uparrow b=\bar{a\cdot b}=\bar a + \bar b$
  • nor $a\Downarrow b=\bar{a+ b}=\bar a \cdot \bar b$
• forme algébrique
  • minterme de $n$ variables est un monôme possédant les $n$ variables sous forme vraie ou inversée par état d'entrée
  • la forme canonique algérbrique est la somme des mintermes égal à $1$
  • forme canonique décimale est le numéro des entrées de la table pour lesquelles le minterme est égal à $1$

Synthèse combinatoire

• méthodologie
  1. cahier des charges
  2. table de vérité
  3. équation logique
  4. logigramme
• table de Karnaugh
  • impliquants d'une fonction : produit des variables de la fonction, en un nombre égal à une puissance de 2
  • impliquants premiers : non compris dans un impliquant plus grand
  • impliquants premiers essentiels : impliquant non inclus dans un autre premier et qui contient au moins un minterme

Technologie digitale

• circuits
• portes de circuits
• semiconducteurs
  • silicium pur est isolant
  • silicium avec du bore devient récepteur d'électron (P)
  • silicium avec du phosphore devient donneur d'électron (N)
  • diode = P et N
  • transistor est comme une double diode à l'exception qu'il a besoin de courant pour en faire une porte
• portes
  • NMOS : porte fermée (courant passe) quand courant appliqué (NPN)
  • PMOS : inverse (symbole avec un 0 inverteur) (PNP)
• limitations
  • limite du nombres de connexion entré/sortie
  • retard de propagation
  • interdit de connecter deux sorties ensemble
  • interdit de faire de la rétroaction (feedback)
• porte tri-state : état tri-state lorsqu'il n'y a aucune valeur de tension
• circuit intégré : les composants sont fabriqués séparement et connectés ensuite
• circuit imprimé

Dispositifs combinatoires

• décodeur $n\to m$ ($n$ entrées et $m<2^n$ sorties) : au maximum un seul bit de sortie est $1$ à un moment donné
• démultiplexeur $n\to m$ est un décodeur où chaque sortie réalise un minterme des $n$ variables d'entrée
• multiplexeur $n\to 1$ est un dispositif combinatoire avec $m$ entrée de contrôle ($m=\log_2(n)$) : la valeur de la sortie est égale à l'entrée choisie par le contrôle
• encodeur : inverse du décodeur avec $m\lceil\log_2(n)\rceil$
• comparateur de deux entrées à $n$ bits : produit une sortie si les $n$ bits sont égaux entre eux
• hasards (glitch) : problème de timing
  • glitch à 0 : si deux entrées se suivent et une seule change ou si deux entrées produisent une sortie 1
  • glitch à 1 : si deux entrées se suivent et une seule change ou si deux entrées produisent une sortie 0
  • on peut éviter les glitch en utilisant une réalisation avec tous les impliquants premiers

VHDL : introduction

• entité (comme une boite noire, on ignore l’intérieur et on connait l’interface publique)

• architecture (implémentation de la boite)

• structure basique d’un programme VHDL library ieee; use ieee.std_logic_1164.all;

  entity toto is port( interface : déclaration des entrées sorties ); end toto;

  architecture test of toto is déclaration de l’architecture (par exemple signaux) begin **déclaration du corps de l’architecture (processus) end test;

• les entrées/sorties sont les ports de l’entité

• les processus s’exécutent en parallèle

• les processus de l’architecture sont connectés entre eux grâce aux signaux

• VHDL : pas de casse, format libre, tout phrase se termine par « ; », double trait pour un commentaire de ligne library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all;

  entity exemple is port( a,b : in std_logic_vector(3 downto 0); op, clk, reset : in std_logic; c : out std_logic_vector(3 downto 0); ); end exemple;

  architecture test of exemple is signal moinsb, opb, aopb : std_logic_vector(3 downto 0); begin moinsb <= not b + « 0001 »; — processus implicite opb <= b when op=‹ 0 › else moinsb; nomProcesus : process (reset, clk) — liste de sensibilité d’un processus explicite begin — le nom est optionnel if reset=‹ 1 › then c <= « 0000 » elseif rising_edge(clk) then c <= aopb; endif; endif; end process; end test;

• constant constant pi : réal := 3.1416;

• variable variable stop : CodeDEtat := STO; (ne pas utiliser de variable)

• signaux

• types

  • scalaire (integer, real, enumerated, physical)
  • composé (array, record)
  • pointeur (acces)
  • I/O (file)
  • définir des types type CodeDEtat is (init, ST1, ST2, exit); ou type word is array (0 to 31) of bit;

• on doit déclarer les deux libraires pour utiliser les deux std_logic

  • std_logic a plusieurs valeurs
    • U uninitialied
    • X forcing unknown
    • 0 forcing 0
    • 1 forcing 1
    • Z impedance?
    • W/L/H/- etc

• opérateur

  • logique (and or nand nor xor xnor)
  • comparaison (= /= < <= > >=)
  • décalage (sll srl sla sra rol ror)
  • concaténation (&)
  • opération (+ - * / mod rem)
  • divers (not abs **)

• évitez les initialisations (:=) lors d’une synthèse

Eléments de mémoire

• introduction de l'horloge (séquentiel)
  • flanc montant de l'horloge
  • durée de l'horloge
• latch : dispositif de mémoire combinatoire
  • D : entrée
  • LD : contrôle, si 1 load, sinon hold
  • Q : sortie
• bascule bistable D (flip-flop)
  • CK : la sortie de la bascule peut changer seulement pendant la montée du signal CK
  • entrées asyncrhones PR (preset, sortie à 1) et CLR (clear, sortie à 0)
• registre
  • ensemble de bascule partageant le même signal d'horloge
  • bit de contrôle L
• registre à décalage
  • permet de décaler vers la droite ou la gauche selon les bits de contrôle

VHDL : processus

• ordre des processus n’est pas important

• implicite (concurrent) vs explicite (bloc de code impératif en boucle infinie)

• la liste de sensibilité redémarre la boucle à chaque changement

• structure if condition then phrases { elsif condition then phrases } [ else phrases ] end if;

  case opcode is when X"00" => add; when X"01" => subtract; when others => illegal_opcode; end case;

  loop faire; end loop;

  while toto < tata loop toto := toto + 1; end loop;

  for item in 1 to last_item loop table(item) := 0; end loop;

  next [ label ] [ when condition ]; exit [ label ] [ when condition ];

• conception d’un programme

  • architecture comportementale (algorithme)
  • architecture structurelle (assemblage de sous-bloc)
  • architecture dataflow (équation logique)
  • déclaration d’entité + corps de l’architecture => entité de conception

• port (in/out/inout)

• l’assemblage de sous-bloc C1 : entity work.XNOR2(toto_arch) port map (0=> s3, I1 => A(3));

Représentation des nombres entiers

• représentation signe-magnitude
  • bit de poids fort porte le signe : 0 si positif
  • le reste les bits de nombre
  • complément à 2 : inverse du nombre + 1 (on change tous les bits à gauche du bit blocher, le 1 le plus à droite)
  • permet de traiter l'addition de nombre négatif
  • attention aux overflows lors du même signe
• extension de signe
  • on répète le bit de signe le nombre de fois qu'on veut

Représentation des nombres réels

• en binaire, on ne peut représenter que les nombres fractionnaires de la forme $X/2^k$
• codage binaire des nombres réels
  • bit de signe
  • mantisse
  • exposant
  • calcul arrondi (attention à la perte de précision)
  • on normalise la mantisse (notation scientifique)
  • $\text{signe }1.\text{mantisse}\cdot2^{\text{exposant}}$
  • 0 est représenté avec des 0 partout
  • par extension les nombres avec un exposant égal à 0 ne sont pas normalisé (pas de 1, mais un 0) $0\le x &lt; 1$
  • l'expost est biaisé (on lui ajoute toujours une constante $2^{k-1}-1$ ou $k$ est le nombre de bits du champ de l'exposant
  • les valeurs extrêmes de l'exposant sont spécifiques (0..0 non normalisé et 1..1 pour infini positif négatif et NaN not a number)
• standard IEEE 754
  • simple
    • nombre de bits : 32
    • mantisse sur 23 bits
    • exposant sur 8 bits (biais de 127)
  • double
    • nombre de bits : 64
    • mantisse sur 52 bits
    • exposant sur 11 bits (biais de 1023)
  • valeurs particulières
    • deux valeurs pour 0, les deux signes avec exposant et mantisse à 0
    • infini positif/negatif, signe, exposant = 1..1 et mantisse = 0..0
    • NaN, signe indifférent, expostant = 1..1 et mantisse différent de 0..0

Méthodologie et exercices

• passage d'une base à l'autre
  • 2 à 10 : $0101=0\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0$
  • 16 à 10 : $A8CE=10\cdot16^3+8\cdot16^2+12\cdot16^1+14\cdot16^0$
  • 10 à 2 : division par 2, 1 s'il y a reste, 0 sinon, lecture dans le sens inverse
  • 10 à 16 : pareil même par 16
  • 2 à 16 : groupement par 4
• passage à virgule
  • 10 à 2 : on multiplie à chaque fois, si ça dépasse 1, sinon 0

Modes de représentation et d'analyse des systèmes séquentiels

• système séquentiel
  • l'état futur est le résultat de l'état présent et des variables d'entrées
  • au maximum $2^n$ états ou $n$ est le nombre de variable
  • la mémoire est nécessaire pour stocker l'état
• machine de Mealy
  • l'état futur dépend de l'état présent et des variables d'entrée
  • changement des sorties n'est pas synchrone
• machine de Moore
  • les variables de sortie dépendent uniquement de l'état présent
  • changements de sorties synchrone
  • demande généralement plus d'états qu'une machine de Mealy
• analyse des machines séquentielles
  • déterminer les fonctions d'état futur et sortie et prévoir le comportement de la machine
  • équations du système (sorties, bascules)
  • table des états
    • chaque ligne représente un etat présent
    • chaque colonne représente une combinaison des entrées
    • a chaque case on introduit l'état futur et la sortie correspondante
  • graphe des états
    • chaque état est représenté par le sommet d'un graphe orienté
    • les changements d'état sont représentés par des arcs
    • sur les arcs, on indique les valeurs des entrées qui produisent le changement et les valeurs de sorties
  • chronogramme
    • les états changent au flanc montant de l'horloge
    • les sorties peuvent changer à tout moment

VHDL : écriture des systèmes logiques

• élément de mémoire
  • process (en, d) begin if en='1' then q <= d; end if; end process genere un latch (plus lent et mauvais)
  • attention à spécifier toutes les branches d'une condition (else)
  • toutes les branches d'un cases doivent être définie
  • il est préférable de dresser une liste des valeurs par défaut au début du cases
  • process (clk) begin if rising_edge(clk) then q <= d; end if; end process; génère une bascule
  • reset
    • asynchrone process (clk, reset) begin if reset='1' then q <= '0'; elsif rising_edge(clk) then q <= d; end if; end process;
    • synchrone process (clk) begin if rising_edge(clk) then if reset='1' then q <= '0'; else q <= d; end if; end if; end process;
• synthèse d'une machine séquentiel
  • processus qui gère les variables d'entrées et les changements d'états qui en découlent
  • processus de reset et d'état (state <= nextstate)
• package (pour une réutilisation des fonctions)
  • bibliothèque std et work incluses par défaut
  • le package doit être compilé avant l'utilisation de ses fonctions (et ajouté à la bibliothèque de travail)
  • déclaration des composants package toto is ici end toto;

Synthèse des systèmes séquentiels

1. cahier des charges
2. représentation formelle
3. graphe des états (facultatif)
4. table d'tats
5. réduction de la table d'états
6. codage de la table d'états
7. calcul des fonctions d'excitation des bascules et des fonctions de sortie
8. logigramme

Les mémoires

• bits organisés en forme de matrice
• chaque ligne de la mémoire est appelée mot identifié par une adresse
• nombre de ligne est une puissance de 2
• opération sur le mot complet (read/write)
• mémoire RAM (random-access memory) : volatile
  • statique (SRAM) : information conservé tant qu'il y a de la tension (latch)
  • dynamique (DRAM) : rafraîchissement des données pour les conservés (8-16ms, condensateur, adresse = séquence de bit)
    • RAS : row address strobe
    • CAS : column address strobe
    • burst refresh : par lignes consécutives à chaque période (impossible d'écrire ou de lire)
    • distributed refresh : chaque ligne à son intervalle
• mémoire ROM (read-only memory) : non volatile
  • mask : contenu initialisé non modifiable (par le fabriquant)
  • PROM (programmable ROM) : modifiable une fois à l'aide d'équipement spécialisé (fusible)
  • EPROM (erasable PROM) : modifiable
    • UV / électrique / flash (électrique mais plus rapide)
• FIFO (first in first out) : non addressable (curseur qui bouge)
• LIFO : non addressable (curseur qui bouge)

Les circuits programmables

• ASIC : application-specific integrated circuits (demande particulière)
  • full custom / gate array (matrice) / standard cell (bibliothèque de gate) / structured (pré-fabriqué, plus grand, demande plus de puissance)
• ASSP : application-specific standard products (demande générale)
• PLD : programmable logic devices (assemblage de AND et OR, fusible)
  • somme d'impliquants = 1 matrice AND puis 1 matrice OR
  • PROM : matrice AND fixe, OR programmable
  • PAL : matrice AND programmable, OR fixe (plus courant)
  • PLA : matrice AND et OR programmable
  • SPLD : simple PLD
  • CPLD : complex PLD (matrice d'interconnexion entre des SPLD)
  • caractérisé par nombre entrées/sorties/termes par sortie, vitesse, retard, consommation et technologie
• FPGA : field programmable gate array (modification chez soi)
  • fonction LUT : stocke la table de vérité
  • configuration par stream

Organisation d’un processeur : synthèse en VHDL

• processeur : machine réalisant un traitement d'information
• besoin d'un algo et des ressources pour l'executer (éléments de stockage)
• décomposer en deux parties : unité de contrôle (chargée du séquencement de l'algorithme, machine séquentielle chargée de la génération des bits de contrôles des ressources à chaque coup d'horloge) et unité de traitement (ensemble d'éléments de stockage et de traitement

Introduction à l’architecture de von Neumann

• les données traitées sont stockées dans la mémoire
• le CPU (central processing unit) réalise les opérations de traitement
• le CPU possède son stockage plus rapide, mais plus petit : les registres
• le transfert des données entre processeur et mémoire se fait par le bus
• l'architecture de von Neumann a permis de stocker les instructions dans la mémoire principale en utilisant aucune connexion spécifique (les mémoires d'instruction et de données ne font qu'une)
• deux complexités de machine : processeurs CISC (complex instruction set computer) : pentium et processeurs RISC (reduced instruction set computer) : powerPC
• 3 types d'instruction :
  • transfert de données
  • opérations arithmétiques/logiques
  • contrôle
• le format d'instruction varie (LOAD, STORE, JUMP, DIV, STOP etc.)
• processeur superscalaires peuvent chercher plusieurs instructions à la fois
• le parallélisme utilise plusieurs unité de traitement

Introduction to processors

• information technology (IT)
• exponential growth with Moore’s Law
  • logic capacity 30%/year
  • clock rate 20%/year until 00's
  • DRAM (Dynamic Random Access Memory) capacity 40%/year
  • memory speed 10%/year
  • cost per bit 25%/year
  • HD capcity 40%/year
  • SSD capacity 60%/year
• use abstraction to simplify design
• make common case fast

ISA

• design abstraction between hardware/software
  • application > operating system/compiler
  • microarchitecture/iosystem > digital design > circuit design
  • architecture : what's visible to the program about the machine
  • microarchitecture : what's invisible in the deep implementation
• ISA : interface HW/SW specifies control and data flow
• processor :
  • real time system
  • CPU split into control logic and datapath
  • datapath include register file, ALU (arthimetic and logic unit), PC (program counter), memory register
• Iron law (processor performance : $\text{processor performance}=\frac{\text{time}}{\text{program}}=\frac{\text{instructions}}{\text{program}}\frac{\text{cycles}}{\text{instruction}}\frac{\text{time}}{\text{cycle}}$
  • CPI (Cycles Per Instruction)
• Amdahl's law : $\text{Speedup}=\frac{1}{\frac{\text{fraction enhanced}}{\text{speedup enhanced}}+(1-\text{fraction enhanced})}$
  • if you speed up only a small fraction of theexecution time of a program or a computation, the speedup you achieve on the whole application is limited
• assembly language is interface
  • low level instruction for datapath, memory and basic type of operations
  • arithmetic, logical, data transfer, conditional branch
  • compiler translate high-level languages
• architectural registers
  • memory is slow and big
  • registers are faster and smaller (fewer bit, better code density)
  • allow to reduce traffic memory and speed up execution
• MIPS (microprocessor without interlocked pipeline stages) is RISC (Reduced instruction set computer, opposed to x86 CISC) and NIOS II
• instruction set definition
  • objects : registers, memory locations
  • operations : data operation, data transfer, instruction sequencing
• registers
  • zero (r0) hard-wired to zero
  • v0-v1 values return (no preservation)
  • a0-a3 arguments
  • t0-t7 temporaries (no preservation)
  • s0-s7 saved
  • t8-t9 temporaries (no preservation)
  • gp global pointer
  • sp (r29) stackpointer
  • fp frame pointer
  • ra (r31) return adress
• memory organization
  • byte adressing grouped by words
  • 2^32 bytes
  • words aligned
  • big endian : adress of most significant byte = word adress
  • little endian adress of least significant byte = word adress
• instruction cycle (sequential model)
  • instruction fetch
  • instruction decode
  • operand fetch
  • execute
  • result store
  • next instruction
• stored program concept : program and data share memory
  • program counter hold instructiona adress
  • sequencer (FSM) fetches instruction into instruction register
  • memory addressed : memory address register
  • memory accessed : memory data register
• instruction format
  • fixed width (easier) vs variable (compact)
  • R-format : 6 op | 5 rs | 5 rt | 5 rd | 5 shamt (shift amout) | 6 funct
  • I-format : 6 op | 5 rs | 5 rt | 16 value/adress
  • J-format : 6 op | 26 adress (limited to 256M)
• adressing modes
  • register : R5
  • immediate : #3
  • displacement : 100(R5) = Mem[100 +R5]
  • register indirect : (R5) = Mem[R5]
  • indexed / base : (R4+R5) = Mem[R4 + R5]
  • direct / absolute : (1001) = Mem[1001]
  • memory indirect : @R3 = Mem[Mem[R3]]
  • auto-increment : (R2)+ = Mem[R2] + d
  • auto-decrement : -(R2) = Mem[R2 - 1]
  • scaled : 100(R2)[R3] = Mem[100+R2+R3 * d]
• procedure calls (subroutines)
  • stack : save registers grows up/down (pointer to last saved element)
  • calling registers use : a0-a3, v0-v1, ra
  • addi sp, zero, 0x2000 ; Initialising stack pointer adress to 2000 addi sp, sp, -4 ; Decreasing stack stw ra, 0(sp) ; Store return adress call display_score ; Display 0 - 0
• starting and running a program
  • C program
  • compiler : orthogonality, completeness, regularity, streamlined (resource easily determined)
  • assembly language
  • assembler : convert assembly to machine language (pseudoinstruction to full instruction)
  • machine language module + libraries
  • linker : avoid recompiling (minor), treats references, determine label address
  • machine language program
  • loader : reserve memory, copies instructions and paramaters, intializes registers
  • memory for execution

Computer Arithmetic : Adders

• microachitecture : application depend on fast computation
• 2's complement : invert all bits and add 1 with sign extension !
• MIPS convert 16 bit immediate values into 32 bits 2's complement
• addiu is used to add constants to signed integers when we don't care about overflow
• binary addition/substraction : like in elementary school
• overflow :
  • cannot happen when adding positive and negative, nor if sign are the same for substraction
  • exception (interrupt) occurs (control jumps predefined address for exception and interrupted adress is saved)
• 1 bit half adder (2 gates): carry $AB=C$, result $A\oplus B=S$
• 1 bit full adder (6 gates can be reduce to 5) : carry $C_i(A+B)+AB=C_o$, result $A\oplus B\oplus C_i=S$
• add/sub : xor all $B$ and start carry $C1_1=1$ when $add/sub=1$
• FO4 delay model (delay through one inverter driven by an inverter loaded to 4 inverters) : $0.5ns / micron * size$
  • CMOS $0.5micron \to 250ps$
  • leading edge $22nm\to 11ps$
• medium-speed modern processor (2GHz, $clk=0.5$ns) : ~45 gate delays in 1 clock tick
• ripple-carray adder : 2 gate delay times 64 bits is more than 2 ticks
• carry select : every stage has 2 full-adders, calculation done twice but hardware intensive
• carry save : delay carry resolution until the end but not constant yet
• carry lookahead : small chuck of adder (4 bits) and compute all intermediate carries directly
  • generate or propagate $C_o=g+pC_i=AB+C_in(A\oplus B)$ and $C2=g1+p1C1=g1+p1g0+p1p0C0$
  • 4 gate thourgh 4 bit adder

Computer Arithmetic : Shifters, Multipliers, Dividers

• fast alu 2x32 bits input / 32 bits output, 1 bit carry, 1 overflow : divide and conquer
  • logic operation
  • set less than : 2's complement adder with inverter
  • operation result selected in a mux
  • overflow : xor of carry out of the last two 1 bit alu
• shifters
  • logical shift : always 0
  • arithmetic shift : right shift sign extend
  • instruction might request 0 to 32 bit shift
  • logartihmic shifter structure : programable layers of mux ($2^M$ bit shift in a direction) of shifters
  • can define needed input
• multiplication : shift and addition (like in school)
  • multiplicand and multiplier (N-bit) give partial product
  • final result can be twice as long as the input
  • 2N bits alu : each round, multiplicand shift 1 left and multiplier 1 right
  • N bits alu : each round, result shit right, multiplier shift right
  • we can put multiplier in left-side of the result to gain space
  • overflow is not tested
• Booth's algorithm : replace long runs of 1s with one add and on subtract $0011110=0100000-0000001$
  • $a(i+1)=0$ and $a(i)=0$ : do nothing
  • $a(i+1)=0$ and $a(i)=1$ : end of 1's run add
  • $a(i+1)=1$ and $a(i)=0$ : begining of 1's run substract
  • $a(i+1)=1$ and $a(i)=1$ : do nothing
  • $a_{i-1}-a_i$ : 0 do nothing, +1 add, -1 subtract
• division : dividend / divisor = quotient
  • complex (guess) : each round, divisor shift right, quotient shift left
  • if remainder < 0 : restore remainder, shit quotient with 0
  • if remainder >= 0 : shift quotient left with 1
• special register
  • Hi : contains remainder or high-side multiplication
  • Lo : contains quotient or low-side multpilcation

Computer Arithmetic : Combinational Multipliers, Floating Point

• multiplier shift and add : costly performance (1 result every 32 cycles)
• combinational multiplier : faster
  • array multipliers : generate all partial product (and gate) and reduce with half and full adders the columns (with eventually a fast lookahead for the last row)
  • tree multipliers (not see details) : analogy to carry-lookahead adders and use some tricks to compress rows called Wallace trees
• floating point numbers
  • sign | 1. | mantissa | x implied base (2) | ^exponent
  • 31 1 bit sign | 30-23 8 bit exponent | 22-0 23 bit mantisse
  • $(-1)^S\cdot (1.f)\cdot 2^{e-127}$
  • sign S : 0 positive, 1 negative (no 2's complement)
  • fraction f : less that 1 unsigned
  • exponent e : 8 bit integer biased ($2^{N-1}-1=127$ here)
  • normalization : only one representation (the 1 is implied)
  • not symmetric (e goes from -126 to +127) but can use comparison on raw format
  • if f is zero and e is min, then number is 0
  • if f is zero and e is max, then inifinity
  • if f is non zero and e is max, then NaN
  • if f is non zero and e is min, then denormalized numbers
  • denormalized numbers : $(-1)^S\cdot (0.f)\cdot 2^{-126}$
• floating point addition
  • compare exponents of two numbers (and shift)
  • add significands
  • normalized by shifting and add/subtract from exponent
  • overflow or underflow ?
  • round significant
  • still normalized ?
• floating point multiplication
  • add biased exponents (subtract 1 bias)
  • multiply significants
  • normalized
  • overflow or underflow ?
  • round significant
  • still normalized
  • set sign bit of result appropriately
• floating point division
  • to see

Single-Cycle Implementation

• typical instruction exceution
  • instruction fetch : access instruction memory
  • instruction decode : identifiy opcode, generate control signals
  • operand fetch : read register, route immediate field
  • execute : perform operation, access data memory
  • result store : write register, write memory
  • next instruction : update PC with new target
• major instruction types : arithmetic, logical, read, write, instruction flow operations
• instruction fetch unit
  • memory
  • program counter to generate address of instruction
  • adder ton increment the PC
  • input : write PC
  • output : instruction
• ALU instruction
  • Register file (RF)
  • ALU
  • intput : instruction (register numbers and alu operation), write RF
• accessing Memory (read, write)
  • RF
  • ALU
  • memory
  • sign extender
  • input : instruction, write RF, ALU add
• branch
  • RF
  • ALU
  • another adder (to compute target)
  • sign extender
  • input : instruction
  • output : branch target, branch logic control
• everything glued together by muxes
• control signals : RegWrite, RegDst, ALUSrc, ALU control, MemWrite, MemRead, ALU/Load, PCSrc
• optimizing op-code and control logic : identify bits pattern, use don't care signals
• single-cycle misconception : everything does not only last 1 cycle, clock has to run a slowest instruction speed
• critical path : path that limits system performance
• multi-cycles solution : clock is determined by the fastest instruction
• jump (fastest intruction) vs multiplication floating point (longest)

Multicycle Implementation

• multi-cycle reality : break every instruction into phases
• nota bene
  • instruction decode and register read must be done for all classes of instructions
  • PC+4 can be done right after fetch
  • adress generation for jump can be performed during the decode step
  • same adder can be shared among : instruction fetch logic, address generation logic, branch target calculation, ALU operations
  • same meory port can be used to access instruction and data
• cannot improve speed : transistor would have to be more powerful (burn)
• execution
  • instruction fetch : PC+4
  • execution step 2 : instruction decode, register fetch, compute ALUOut in advance
  • execution step 3 : memory reference, arithmetic/logical operation, branch, jump
  • execution step 4 : memory reference, arithmetic/logical instruction
  • execution step 5 : memory read completion (load only)
• finite state machine : instruction fetch/decode and register fetch span memory access, R-type instruction, branch instruction and jump instruction
• performance : average cycles per instruction (CPI) time cycle time
• microcode : logic programmed in memory
• exception events : interrupts signal (interraction with OS)

Memory

• basically memory is a 2d array with decoder
• aspect ratio : equal rectangular size wanted
• **RAM technology **: denser and faster than a bunch of flip-flops
  • SRAM static random access memories : low density, high power, expensive, fast, no refresh
  • DRAM dynamic : high density, low power, cheap, slow and need regular refresh
• SRAM
  • organized in 16-word times 4-bit
  • need output enable signal (input/output using same bus)
  • 6 transistors
• DRAM
  • use little capacity
  • slow and complex to improve
  • +40% capacity/year
  • -25% cost/year
  • signaling convention : each row accesses a lot of data, ask for burst
  • emering technoligies (not yet ready, latencies, active energy not enough for scaling and low idle power) : change material phase (PCM), magnet polarity (STT-MRAM)
• memory hierarchy : illusion of a fast, large, cheap memory system
• principle of locality : program accesses a relatively small portion of the address space at any instant of time
  • spatial locality : items nearby tend to be referenced soon
  • temporal locality : same item tends to be referenced again soon
  • block (or line) : minimum unit of data between 2 levels
• registers - cache (SRAM) - main memory (DRAM) - disk
• hit, hit rate, hit time (access time + hit determinition time) : data appears in some block in the upper level
• miss, miss rate, miss penalty (replacement of the block in the upper level time + delivery time)
• cache only holds a portion of program : most recently accessed references
• cache tag : hold main memory address of the data in the block

Memory Hierarchies : Basic Cache

• ABC's of caches
  • block placement : where can a block be place in a cache ?
  • block identifiation : how is a block found if it is in a cache ?
  • block replacement : which block should be replaced on a miss ?
  • write strategy : what happens on a write ?
• block placement
  • direct mapped (block number modulo)
  • fully associative (can go anywhere, full search)
  • 2-way (n-way) associative (block can go anywhere in a block number modulo set)
• valid bit : tell if the content is valid
• block identification : address tag compared and valid bit must be active
• block replacement
  • direct mapped : only one block can be replaced
  • set-associative : N blocks can be replaced (N is the degree of associativity)
  • random replacement (require random number generator)
  • least-recently used (must resort)
• write strategy : is the data also written in main memory when written in the cache ? should you cache block if write-miss ?
  • write-through cache
  • write-back cache (need to remember which has been written)
  • write allocate
  • write no-allocate
• average time to access memory (AMAT) = hit time + miss rate * miss penalty (#number of hit * hit time + #number of miss * miss penalty)
• CPI = CPIexec (instruction without memory access) + memory stall cycles per instructions ( = memory accesses per instruction ( = instruction fetch 1 + load/store instruction ratio ) * stall cycles per access)

Advanced Cache

• cache design issues : size, block size, associativity, bandwidth, write through vs write back, cache partitioning (split vs unified intruction), access time, power
• reducing cache miss rate
  • realist cache miss rates today
    • I-cache (instruction) : under 1-5%
    • D-cache (data) : as high as 25%
  • sources
    • compulsory (no reduction possible) : start, first access
    • conflict : similar map location (increase associativity or cache size)
    • capacity : cannot contain every block
    • coherence : other process (I/O), multiproc
  • possible techniques
    • larger blocks : more data brought on each miss (spatial locality) but create cache pollution (more eviction), increase miss penalty (more cycles) and is limited by the bus
    • higher degrees of associativity : reduce conflict miss (8-way is as good as full) but increase access time
    • victim caches : small cache that contains most recently discarded cache blocks (1-5), very effective for direct-mapped
    • hardware prefetching : hard to predict (what and when) but great result with array element accesses and consecutive instruction fetches (prefetched in a separate small cache)
    • compiler prefetch : allow compiler to insert prefetch instruction
• reducing cache miss penalty
  • sub-block placement : divide cache into sub-blocks and use 1-bit validity per sub-block (reduce refill on misses and write-back)
  • early restart : request the critical word first and the earliest
  • 2nd-level caches : muliple levels of cache (first level single-cycle, second level less than 10-cycles, third level less than 100-cycles)
  • AMAT 2-level = hit time L1 + miss rate L1 * (hit time L2 + miss rate L2 * miss penality L2)
• reducing hit time (cache access time)
  • small caches to fit on-chip (shorter wires)
  • avoid address translation (virtual memory)

Virtual memory

• when more memory is needed as offered : big program, mutiple jobs, jobs fragmentation (not enough contiguous place free)
• virtual memory : allows execution of program that can reside in non-contiguous by faking a large and contigues memory space (larger than physical one)
• divided into pages (4-8KB) : brougth to memory one at a time (can have multiple size on modern processors)
• two spaces : virtual memory space (what the program sees) and physical memory space (what the program runs in)
• OS is the head : copy pages into RAM when needed and copy old dirty (changed) pages back
• page table : translation virtual address (VA) to physical address (PA)
• page offset (# bit = log2 page size) : location in the physical page (not translated)
• physical address (# bit = log2 #RAM bytes) : translated
• page table entry (PTE)
• valid bit PTE to know if not into RAM
• page default : hardware asks OS to fetch the page from disk
• victim page : page evicted (if dirty copy before eviction)
  • the one that will not be used for the longest period of time
  • least recently used
  • first-in, first-out (FIFO keeping track of pages first reference in a list)
• protect memory of each process
  • simplest approach : use memory bounds
  • system mode : privileged mode that can overpass bounds (not possible with user mode)
  • page-level protection
• page tables are mapped into kernel memory (only OS accessible)
• TLB translation lookaside buffer : cache most recently referenced PTE (less than a cycle)
  • 4 cases
    • page in physical memory, PTE in TLB (fastest)
    • page in physical memory, PTE not in TLB : TLB miss, go to translation page
    • page not in physical memory, PTE in TLB : page fault
    • page not in physical memory, PTE not in TLB : TLB miss, page fault
  • 1-bit valid PTE
  • 32 to 1024 entires (slots)
  • can be direct mapped, set associate or fully associative (best)
  • miss cost : 20 to 500 cycles (hardware/software based)
  • miss rate : 4-8% (Linux)
  • page size : 4-8K Bytes
  • protection : append a PID (process ID) to each TLB entry (OS has a Process ID Register updated when context switch)
• virtual memory and caches
  • simplest but slowest : CPU > TLB > cache > memory
  • overlapp cache and TLB
    • PO contains BO at lowest bits
    • PO contains cache index (IDX) at indermediate bits : which block in the cache we check
    • PO contains cache tag (TAG) at highest bits
    • simple for small caches (IDX + BO less PO) : cache size / associativity less than page size
    • virtual synonyms : must use bits from VPN to index the cache (by either forcing fever lower bits VPN to be identical to PPN managed by OS or hardware search all cache sets for unknow bits)