De Turing à Von Neumann :
I – Comment fonctionne une machine de Turing ?
Pour refaire des tests et mieux comprendre : https://interstices.info/comment-fonctionne-une-machine-de-turing/
Pour expliquer la notion de « procédure mécanique » (= algorithme), Alan Turing invente une machine abstraite, la plus élémentaire possible, destinée à mettre en œuvre ces mécanismes de calcul, numériques ou symboliques comme le font les ordinateurs. Or, ce dernier n’existait pas encore lorsqu’Alan Turing décrit sa machine dans un article en 1936.
La machine imaginée par Turing comporte un ruban divisé en cases, dans lesquelles elle peut écrire des symboles. La machine ne peut lire qu’une seule case à la fois, de même elle écrit dans une seule case et décale le ruban d’une seule case vers la gauche ou vers la droite. Les symboles sont en nombre fini. Pour que sa machine fonctionne comme une machine à calculer en binaire, Turing envisage le cas particulier où les symboles utilisés sont 0 et 1.
–> Il existe donc six « programmes » différents :
–> table d’actions pour ajouter 1 :
–> table d’actions pour soustraire 1 :
–> table d’actions pour multiplier par 2 :
–> table d’actions pour inverser les 0 et 1 :
–> table d’actions pour doubler la longueur d’une suite de 1 :
–> table d’actions pour détecter des palindromes :
–> Tous ces programmes sont rudimentaires mais très instructifs : ils montrent que l’on peut faire des opérations numériques (les 0 et les 1 correspondent au codage binaire de nombres) ou symboliques (les 0 ou les 1 codent des symboles).
En combinant ces briques de base, ce sont tous les algorithmes qui peuvent s’implémenter.
Par exemple, si l’on ajoute plusieurs fois 1, il est possible d’additionner plusieurs nombres ;
puis en combinant les additions faire des multiplications, et par extension tous les calculs numériques.
Grâce aux travaux de Turing Von Neumann a défini en 1944 l’architecture d’un ordinateur.
II – Le modèle d’architecture de von Neumann
Peu connu du grand public, le mathématicien hongrois John von Neumann (1903-1957) a pourtant élaboré des théories dont les applications ont définitivement changé le cours de l’humanité, de la bombe atomique à la révolution numérique. Pour en savoir plus : https://www.youtube.com/watch?v=JKG2yhTrndw&t=4s
_____________________________________________________________________________________
Un emplacement de mémoire peut contenir indifféremment des instructions et des données, et une conséquence majeure (dont toute la portée n’avait probablement pas été perçue à l’époque) est qu’un programme peut être traité comme une donnée par d’autres programmes. Cette idée, présente en germe dans la machine de Turing, trouvait ici sa concrétisation.
Plus de soixante ans après son invention, le modèle d’architecture de von Neumann régit toujours l’architecture des ordinateurs. Par rapport au schéma initial, on peut noter deux évolutions :
- Les entrées-sorties, initialement commandées par l’unité centrale, sont depuis le début des années 1960 sous le contrôle de processeurs autonomes (canaux d’entrée-sortie et mécanismes assimilés). Associée à la multiprogrammation (partage de la mémoire entre plusieurs programmes), cette organisation a notamment permis le développement des systèmes en temps partagé.
- Les ordinateurs comportent maintenant des processeurs multiples, qu’il s’agisse d’unités séparées ou de « cœurs » multiples à l’intérieur d’une même puce. Cette organisation permet d’atteindre une puissance globale de calcul élevée sans augmenter la vitesse des processeurs individuels, limitée par les capacités d’évacuation de la chaleur dans des circuits de plus en plus denses.
Les conséquences de ces deux évolutions :
- mettre la mémoire, plutôt que l’unité centrale, au centre de l’ordinateur
- augmenter le degré de parallélisme dans le traitement et la circulation de l’information.
Mais elles ne remettent pas en cause les principes de base que sont la séparation entre traitement et commande et la notion de programme enregistré.
III – Le transistor
Le transistor a été inventé en 1947 par les Américains John Bardeen, William Shockley et Walter Brattain, chercheurs des Laboratoires Bell. Ces chercheurs ont reçu pour cette invention le prix Nobel de physique en 1956.
Ainsi, qu’est-ce qu’un transistor ?
- Le transistor est un composant électrique, notamment dans les microprocesseurs
- c’est donc un interrupteur qui laisse passer ou non l’électricité (1 ou 0) –> langage binaire
- la puissance d’un microprocesseur s’exprime en nombre d’opérations par seconde, c’est pourquoi le nombre de transistors dans un microprocesseur détermine sa puissance
–> Le transistor est l’élément de base des circuits logiques.
Activité : Une porte logique avec des transistors
Le circuit ci dessus permet de simuler sur logisim une porte logique à l’aide de deux transistors.
Vous pouvez télécharger le fichier et l’ouvrir avec logisim ou réaliser le circuit sur directement.
Écrire la table de vérité pour déterminer la fonction logique obtenue.
……….
_____________________________________________________________________
IV – La loi de Moore
Toutes les opérations logiques sont réalisées avec des circuits logiques.
La loi de Moore : https://www.journaldunet.fr/web-tech/dictionnaire-du-webmastering/1203331-loi-de-moore-definition-traduction/
En 1965, celui qui fut l’un des cofondateurs de la société Intel trace une courbe d’évolution de la taille et du prix des microprocesseurs. Il s’aperçoit alors que à coût égal, leur complexité doublait tous les ans.
En 1975, il précise que c’est le nombre de transistors qui double tous les deux ans.
Il a prédit que cette croissance allait se poursuivre à ce rythme jusqu’en 2015, où elle serait limitée par la taille des atomes.
L’Histoire lui a donné raison puisque entre 1971 et 2001 la densité des transistors a effectivement doublé 1,96 fois par an.
Depuis 2014, on commence à voir le ralentissement annoncé dans les ajustements de la loi de Moore en 1997.
Les acteurs du secteur informatique l’utilisent encore pour anticiper la puissance des ordinateurs du futur. Toutefois, les évolutions n’arrivent plus à suivre la même cadence, et sont désormais plus lentes.
V – Le processeur
Qu’est ce qu’un processeur ?
- les processeurs représentent tout d’abord les cœurs des ordinateurs que l’on a aujourd’hui
- ils évoluent rapidement et de façon importante au fil du temps
- –> un processeur est donc un circuit électronique universel
- son but : exécuter tout algorithme (avec calculs, expressions logiques, stockage de données pour exécuter un algorithme)
- on a donc besoin de : quelques portes logiques élémentaires
Architecture de Von Neumann (voir plus haut dans le blog) :
L’unité de commande ou de contrôle récupère les informations dans la mémoire et donne les ordres à l’UAL.
L’unité arithmétique et logique ALU (ou UAL) exécute les instructions du programme une par une en commençant par la première (calculs , les opérations logiques les comparaisons.)
L’accumulateur est un registre spécial ou sont versés les résultats intermédiaires.
Les entrés et sorties permettent de communiquer avec le monde extérieur.
La mémoire stocke le programme ( données et instructions) en binaire.
Dans les ordinateurs actuels on trouve plusieurs processeurs séparés ou plusieurs cœurs intégrés dans une même puce.
Pour apprendre à déterminer le nombre de cœurs de votre pc : https://support.microsoft.com/fr-fr/windows/d%C3%A9terminer-le-nombre-de-c%C5%93urs-de-votre-processeur-3126ef99-0247-33b3-81fc-065e9fb0c35b
VI – Programmation en assembleur
L’assembleur est un langage permettant une lecture plus lisible que le binaire.
Un exemple de code en assembleur simplifié y86 : irmovl 9,%eax
Résultat de l’assemblage en langage machine : 1100001111000000001001000000000000000000000000
Cette écriture présente bien des inconvénients pour un humain et justifie l’utilisation de l’assembleur qui remplace les séquences de bits par des symboles plus faciles à retenir.
Chaque processeur a son jeu d’instructions et ne peut exécuter que le langage machine. L’assembleur chargé d’obtenir ce langage machine est donc propre à chaque processeur (ou famille de processeur).
Dans les activités qui suivent nous allons utiliser le simulateur y86 :
y86 propose alors un jeu d’instruction réduit :
Architecture x86 :
https://fr.wikipedia.org/wiki/X86
Architecture y86 :
https://aurelien-esnard.emi.u-bordeaux.fr/teaching/doku.php?id=archi:y86
Simulateur y86 :
https://dept-info.labri.fr/ENSEIGNEMENT/archi/y86js_v2/index.html
Activité 1 : assembleur :
assembler : « convertir en langage machine pour que l’ordinateur le comprenne »
https://dept-info.labri.fr/ENSEIGNEMENT/archi/y86js_v2/index.html
–> le programme stocke la valeur « immédiate » 9 dans le registre %eax.
Le registre est une mémoire interne très rapide du processeur.
La dernière instruction qui marque la fin du programme se trouve à l’adresse 0x0006
Le processeur exécute les instructions de façon séquentielle et un compteur ordinal PC lui donne l’adresse de l’instruction suivante : ici 0x0007
Activité 2 : addition
Enregistrons la valeur « immédiate » 9 dans le registre %eax
Enregistrons la valeur « immédiate » 6 dans le registre %ebx
Effectuons l’addition et enregistrons le résultat dans le registre %ebx
Fin du programme
L’implémentation de cette séquence d’instructions en assembleur « y86 » donne :
9 est stocké en %eax, et l’addition de 9+6 est stockée en %ebx.
halt signifie la fin du programme.
Modifions le programme pour effectuer la soustraction 6-9 dans %ebx :
9 est stocké en %eax, et la soustraction de 6-9 est stockée en %ebx.
–> La valeur hexadécimale (fffffffd) stockée en %ebx est le résultat de la soustraction précédente.
Ce nombre correspond il à -3 ?
première méthode: complément à 2
f f f f f f f d(16)
Écriture en binaire
1111 1111 1111 1111 1111 1111 1111 1101
Inversion des bits
0000 0000 0000 0000 0000 0000 0000 0010
Ajout de 1
0000 0000 0000 0000 0000 0000 0000 0011
3 en décimal !
Deuxième méthode : on ajoute 3
1111 1111 1111 1111 1111 1111 1111 1101
0000 0000 0000 0000 0000 0000 0000 0011
————————————————————-
0000 0000 0000 0000 0000 0000 0000 0000
la somme donne bien 0.
Activité 3 : mémoire
Enregistrons 9 dans %eax
Enregistrer le contenu de %eax à l’adresse 0030(16) :
Pourquoi ne pas enregistrer le résultat à la suite du programme ?
La mémoire stocke les données et le programme. Les instructions sont codées sur 32bits, il faut donc s’éloigner de la plage correspondant au programme pour ne pas le modifier en cours d’exécution.
____________________________________________________________________________________
Enregistrer 9 à l’adresse 002C(16)
puis enregistrer dans %eax
Enregistrer le contenu de eax à l’adresse 0030(16)
On peut vérifier :
2c(16)=2*16+12=42
30(16)=3*16+0=48
Projet 1 : assembleur
En python :
a=1000
b=0
while a!=0:
b=b+a
a=a-1
#affichage du résultat en hexadécimal
print(hex(b))
–> 0x7a314 = 500500
vérification
(1001*1000)/2=500500
En assembleur :
.pos 0
irmovl 1000,%eax
irmovl 0,%ebx
repeter:
addl %eax,%ebx
isubl 1,%eax
jne repeter
halt
–> on retrouve bien le même résultat.
Exemple avec 3
On recommence jusqu’à ce que %eax soit égal à 0.
Projet 2 : bascule
La logique combinatoire présente des sorties qui, à un instant donné, ne dépendent que des valeurs présentes sur les entrées. La logique séquentielle prend en considération les conditions antérieures à l’instant donné, ce qui permet de réaliser des dispositifs à mémoire.
Les bascules sont de manière générale des bistables, ce qui permet d’obtenir des niveaux logiques stables sur leur sorties (soit « 1 » ou « 0 »). Elles réalisent de ce fait une fonction mémoire temporaire permettant ainsi de stocker des informations. Ces dernières pouvant être aussi annulées à tout moment.
La sortie Q suit l’information présente sur l’entrée D tant que l’entrée C est au niveau logique haut. Quand l’entrée d’horloge (C) est à l’état logique »0″, la sortie Q garde en mémoire le niveau logique que possédait D au moment de la transition de C de « 1 » vers « 0 » et ceci jusqu’à ce que C prenne à nouveau la valeur « 1
Simulation sur logisim :
code Arduino pour réaliser l’inverseur :
int data=12;
int invert_data=8;
int val=0;
void setup() {
pinMode(data, INPUT);
pinMode(invert_data, OUTPUT);
}
void loop() {
val = digitalRead(data);
digitalWrite(invert_data,!val);
}
visualisation Python
from scipy import signal
import matplotlib.pyplot as plot
import numpy as np
#t temps
t = np.linspace(0, 1, 1000, endpoint=True)
#h1 signal horloge
h=signal.square(2* np.pi * 5 * t)
h1=[0.5*y+0.5 for y in h]
# data signal donnée en entrée
sig = np.sin(2 * np.pi * t)
pwm = signal.square(2 * np.pi * 8 * t, duty=(sig + 1)/2)
data=[0.5*y+0.5 for y in pwm]
# q valeur en sortie de bascule
q=[]
a=j[0]
for i in range(len(t)):
if h1[i]==1:
a=data[i]
q.append(a)
else:
q.append(a)
# affichage des chronogrammes
plt.subplot(3, 1, 1)
plt.plot(t,h1)
plt.subplot(3, 1, 2)
plt.plot(t,data)
plt.subplot(3, 1, 3)
plt.plot(t,q)
plt.show()
Aucune réponse