Fonctionnement d'un ordinateur/Les ordinateurs à encodages non-binaires
Jusqu'à présent, tous les ordinateurs que nous avons vu utilisaient le binaire pour coder leurs nombres. Mais il a existé quelques rares ordinateur qui n'utilisaient pas l’encodage binaire du tout, ou du moins pas complètement. Nous avons déjà parlé des très anciens ordinateurs décimaux, qui comptaient en base 10. Mais ils utilisaient en réalité le binaire en sous-main, en utilisant des encodages hybrides entre binaire et décimal, le plus connu étant l'encodage BCD (Binary Coded Decimal). Mais il y a aussi eu quelques ordinateurs qui codaient leurs entiers en ternaire, c'est à dire en base 3.
Dans ce chapitre, nous allons voir plusieurs exemples d'ordinateur qui soit comptaient naturellement en base 3/4/5/6/7/autre, soit qui utilisaient un encodage hybride similaire au BCD. En premier lieu, nous allons rapidement parler des ordinateurs ternaires, qui comptaient naturellement en base 3. En second lieu, nous allons voir des ordinateurs qui utilisaient le binaire, mais qui encodaient non pas des nombres, mais des probabilités. De tels ordinateurs s'appellent des ordinateurs stochastiques.
Les ordinateurs ternaires
[modifier | modifier le wikicode]Le ternaire est un encodage au même titre que le binaire, le décimal, l'hexadécimal, ou autre. Il encode un nombre non pas en base 10 comme le décimal, en base 2 comme le binaire, ou en base 16 comme l'hexadécimal, mais en base 3 ! Il encode un nombre en utilisant non pas des chiffres, ni des bits, mais des trits qui peuvent prendre trois valeurs.
Les portes logiques en ternaire
[modifier | modifier le wikicode]Un défaut des ordinateurs ternaires est la conception des portes logiques. Pour rappel, avec du binaire, le nombre de portes logiques possibles à n entrées se calcule comme suit :
Et c'est ce qui explique qu'il existe 4 portes logiques à deux entrées : 2^(2^1), 16 portes logiques à deux entrées : 2^(2^2), 256 portes logiques à deux entrées : 2^(2^3). Mais en ternaire, le nombre de portes logiques se calcule avec cette formule :
Le nombre de portes logiques augmente alors beaucoup plus rapidement. Il y a 27 portes logiques à une entrée, 19 683 portes logiques à deux entrées. Et surtout, les portes logiques pertinentes en ternaire ne sont pas celles utilisées en binaire. Il y a bien des équivalents pour les portes OU et ET, NOT et autres, mais ils sont assez peu utiles. Concevoir des circuits logiques en ternaire est donc un véritable défi pour les concepteurs de hardware. Ce qui explique probablement pourquoi le ternaire normal est aussi peu utilisé. Le ternaire équilibré est utile pour concevoir des circuits arithmétiques, mais la conception de circuits bit à bit est déjà plus problématique.
Les différentes formes de ternaires
[modifier | modifier le wikicode]Il existe plusieurs formes différentes d'encodage ternaires, que nous allons voir, avant de passer aux ordinateurs ternaires proprement dit. Qu'il existe plusieurs variantes de ternaire ne devrait pas vous étonner. Après tout, le binaire lui-même a beaucoup de variantes, entre le binaire normal, les différents encodages pour les nombres signés, la virgule fixe, la virgule flottante, etc. En ternaire, il y a la même chose, avec un encodage non-signé, plusieurs encodages signés, des nombres flottants ternaires.
Dans le ternaire non-signé, les trois valeurs d'un trit sont 0, 1 et 2. L'encodage multiple un trit par une puissance de 3, à savoir 1, 3, 9, 27, etc. On parle alors de ternaire non-équilibré. Inutile de développer plus, le principe est le même qu'en binaire ou en décimal, mais en base 3. De plus, aucun ordinateur ne l’utilise, contrairement aux suivants.
Pour ce qui est des encodages signés, la plupart des encodages signés binaires ont un équivalent en ternaire. La représentation en complément à deux devient un complément à trois, le signe-magnitude existe, de même que la représentation négabinaire. Mais en ternaire, les nombres signés peuvent aussi être codés avec une représentation spécifique au ternaire, appelée le ternaire non-équilibré. Avec elle, chaque trit encode les trois valeurs suivantes : 0, 1 et -1. Le trit est donc signé ! L'équivalent en binaire serait d'encoder les trois valeurs sur deux bits : un bit de signe et un bit pour coder 0/1. La différence est qu'utiliser deux bits fait qu'on a un zéro positif et un zéro négatif. Ici, ce n'est pas le cas.
| Valeurs encodables par un trit | |||
|---|---|---|---|
| Ternaire non-équilibré | 0 | 1 | 2 |
| Ternaire équilibré | −1 | 0 | 1 |
Voici ce que donne un encodage sur trois trits.
| Notation ternaire | 000 | 001 | 002 | 010 | 011 | 012 | 020 | 021 | 022 | 100 | 101 | 102 | 110 | 111 | 112 | 120 | 121 | 122 | 200 | 201 | 202 | 210 | 211 | 212 | 220 | 221 | 222 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Nombre décimal correspondant | -13 | -12 | -11 | -10 | -9 | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
Il faut noter qu'avec le ternaire équilibré, le signe d'un nombre se détermine uniquement en regardant le bit de poids fort du nombre. Le bit de poids fort agit à la fois comme un bit de signe, mais sert aussi à coder sa valeur. Cela résout de nombreux problèmes liés à la gestion des entiers signés, qui sont présents dans les encodages binaires.
Les opérations en ternaire équilibré
[modifier | modifier le wikicode]L'avantage du ternaire équilibré est qu'il permet de représenter des entiers positifs comme négatifs, sans compter que certaines opérations deviennent bien plus simples à implémenter qu'en binaire. L’inconvénient est que c'est une base intrinsèquement signée, ce qui fait qu'elle n'est pas adaptée pour implémenter des fonctions logiques comme des décodeurs/multiplexeurs, pour lesquelles du ternaire ou du binaire normal est plus indiqué.
L'opération d'inversion est conceptuellement plus simple. Elle transforme un 1 en -1 et laisse les 0 inchangés. Vous remarquerez que l'opération d'inversion, appliquée à tous les bits, transforme un nombre en son opposé. Il s'agit là d'une caractéristique du ternaire équilibré, mais pas forcément des autres encodages binaires. En binaire, il était possible de faire pareil en complément à un, mais pas en complément à deux où il fallait faire une incrémentation supplémentaire après le NOT.
Voici les opérations ternaires à une entrée qui sont pertinentes :
| Entrée 1 | Inversion | Increment | Decrement | |
|---|---|---|---|---|
| -1 | 1 | 0 | 1 | |
| 0 | 0 | 1 | -1 | |
| 1 | -1 | -1 | 0 |
L'addition et la multiplication sont plus simples qu'en binaire, car la gestion des retenues et des tables de multiplication est légèrement plus simple. Voici ce que donne la table de multiplication en ternaire :
| Entrée 1 \ Entrée 2 | 1 | 0 | -1 |
|---|---|---|---|
| 1 | 1 | 0 | -1 |
| 0 | 0 | 0 | 0 |
| -1 | -1 | 0 | 1 |
En binaire, l'addition de deux bits est faite avec un XOR. Mais en ternaire, la porte équivalente au XOR ne calcule pas l'addition de deux trits. A la place, une autre porte logique calcule la somme de deux trits.
| Entrée 1 \ Entrée 2 | Somme | Retenue | ||||||
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | -1 | 1 | 0 | -1 | |||
| 1 | -1 | 1 | 0 | 1 | 0 | 0 | ||
| 0 | 1 | 0 | -1 | 0 | 0 | 0 | ||
| -1 | 0 | -1 | 1 | 0 | 0 | -1 | ||
Les ordinateurs ternaires
[modifier | modifier le wikicode]Le ternaire non-équilibré a été utilisé sur d'anciens ordinateurs ternaires, dont le plus connu est l'ordinateur SETUN de l'université de Moscou. SETUN était un véritable ordinateur ternaire, qui utilisait des mémoires et un processeur ternaire, qui gérait des trits directement. Il ne s'agit pas d'un équivalent aux ordinateurs décimaux, qui étaient des hybrides entre ordinateurs décimaux et binaire, avec une interface décimale mais une conception fondamentalement binaire. A vrai dire, il s'agit peut-être du seul ordinateur ternaire réellement construit. Si vous faites des recherches, vous allez trouver beaucoup de noms de projets, mais aucune source montrant que la machine a réellement été implémentée.
SETUN utilisait le ternaire équilibré. Son architecture encodait les instructions sur 9 trits, et il avait deux registres de 18 trits pour les additions et multiplications, ainsi qu'un registre d'index de 5 trits. Les registres mémorisaient des nombres entiers, flottants ou bien des nombres complexes. Il contenait une mémoire RAM de 162 cellules de 9 trits chacune, divisée en pages de 54 cellules. Il avait aussi une mémoire de stockage magnétique de 36 à 72 pages. Les lectures/écritures en RAM se faisaient par paquets de 9 à 18 trits, ce qui fait que son byte était de 9 trits, et la taille du mot de 18 trits. Une lecture de 9 trits altérait soit les 9 trits de poids faible, soit les 9 de poids fort des deux registres d'addition/multiplication.
La difficulté pour créer des ordinateurs ternaires tient en plusieurs choses. Elle ne se situe pas au niveau des bus de communication, pour lesquels de encodages ternaires sont déjà utilisés, voire carrément des encodages en base 4/16/autres. Elle n'est pas non plus au niveau des mémoires de stockages. Les mémoires FLASH MLC utilisent déjà des cellules mémoires qui fonctionnent en base 4, voire 8. Par contre, pour ce qui est des mémoires RAM, c'est une autre paire de manche. L'imprécision des circuits utilisés, le fait que les tensions électriques doivent avoir plus de 3 seuils, les problèmes électriques, sont bien plus important dans ce contexte. A ce propos, l'ordinateur SETUN n'avait pas de véritables registres ternaires. Chaque trit était stocké dans deux bascules binaires qui étaient connectées de manière à simuler une bascule ternaire.
Liens externes
[modifier | modifier le wikicode]Pour information, il existe un émulateur qui recréé de manière logicielle l'ordinateur SETUN. Voici un lien vers cet émulateur :
De même, voici un lien vers le Ternary manifesto, un document qui décrit très bien comment le ternaire peut être utilisé dans un ordinateur. Il parle de l'encodage en ternaire, des portes logiques en ternaire, de comment faire une addition ou une multiplication en ternaire, et bien d'autres choses.
Les ordinateurs stochastiques
[modifier | modifier le wikicode]Les ordinateurs stochastiques sont de vieux ordinateurs datant des années 50, qui ont périclité dans les années 60-70. Ils avaient une application assez limitée, dans des applications demandant de manipuler des statistiques. En effet, ces architectures ne manipulaient pas des nombres entiers, mais des probabilités comprises entre 0 et 1. Enfin presque, tout dépend de l'encodage utilisé, mais l'encodage le plus simple utilise bel et bien des statistiques. Dans le cas général, les ordinateurs stochastiques encodent des données en faisant la moyenne d'un flux de bits.
Les ordinateurs stochastiques regroupent un ensemble de quelques prototypes, aux noms de RASCEL (Regular Array of Stochastic Computing Elements), POSTCOMP (Portable Stochastic Computer), TRANSFORMATRIX, APE (Autonomous Processing Element) system, BUM (Bundle Machine), SABUMA (Safe Bundle Machine) et ERGODIC. La plupart de ces machines étant assez anciennes, elle mélangeaient des éléments analogiques et numériques, avec pas mal d'analogique au niveau des entrées-sorties. La documentation sur ces machines s'est perdue, mais on peut encore trouver quelques sources. Par exemple, voici un document qui détaille l'architecture de l'ordinateur RASCEL, sur l'internet archive :
L'encodage stochastique de base
[modifier | modifier le wikicode]Il existe plusieurs encodages possibles sur les architectures stochastiques, mais le plus simple encode directement des probabilités comprises entre 0 et 1. Une probabilité est codée sur N bits, par la population count de ces N bits. En clair, avec N bits, si n bits sont à 1, alors la probabilité encodée vaut n/N. Il s'agit donc d'une forme d'encodage unaire, en base 1, mais spécialisée pour les nombres dans l'intervalle [0,1].
- Attention, dans les tableaux qui vont suivre, nous n'utilisons pas des octets, mais des paquets de 10 bits !
| Valeur encodée | Suite de bits | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 0.1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0.3 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| 0.8 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 |
Un même nombre peut être encodé de plusieurs manières différentes. L'encodage stochastique n'est donc pas compact, il autorise de la redondance.
| Valeur encodée | Suite de bits | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1/2 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | |
Un avantage de ces encodages est que le stockage d'une probabilité est assez stable, résistant aux interférences. Si jamais un bit change de valeur, cela n'affecte pas beaucoup la probabilité. En conséquence, les encodages stochastiques étaient très adaptés sur des ordinateurs peu fiables. Au tout début de l'informatique, les transistors étaient peu fiable et il arrivaient que des bits s'inverse dans un registre, que des circuits fassent des erreurs de calcul, ou autres. Mais avec un code stochastique, de tels erreurs n'avaient que peu d’impact du fait de cette redondance.
Dans ce qui précède, nous avons implicitement admis qu'une valeur est codée sur un nombre fixe de bits, qui fixé une fois pour toute lors de la conception du processeur. Mais il est possible d'adapter ce codage avec un nombre variable de bits, un N qui varie selon l'opérande. Pour différencier les deux, nous parlerons de Time Stochastic Processing (TSP) pour des flux de bits de longueur variable, de Bundle Processing (BP) pour des flux de bits de longueur fixe. Les machines RASCEL, TRANSFORMATRIX, APE et POSTCOMP utilisaient le TPS, alors que les machines BUM, SABUMA et ERGODIC utilisaient le BP. Le BP est plus simple à comprendre, mais il a aussi d'autres avantages en terme de précision, comme on le verra plus bas.
La conversion entre binaire et encodage stochastique
[modifier | modifier le wikicode]Un point très important pour comprendre ce qui suit est que les ordinateurs stochastiques sont généralement de type bit sériels ce qui veut dire que les bits sont traités un par un par l'unité de calcul. Les architectures stochastiques n'ont pas de mémoire RAM, elles se contentent de registres à décalage pour stocker les opérandes des calcul. Il faut dire qu'une mémoire RAM serait mal adaptée à un encodage unaire, mieux vaut stocker les données en binaire dans la RAM et les convertir si besoin. En combinant des circuits de conversion binaire-stochastique, des registres à décalage et une ALU sérielle, on obtient une architecture stochastique.
Les conversions binaire <-> stochastique sont assez simples à faire, sur le papier. Dans ce qui suit, on part du principe que les nombres encodés en binaire sont des nombres en virgule fixe, compris entre 0 et 1. En clair, ils encodent la partie fractionnaire d'un nombre de la forme 0.xxxxxxxxxxxx, à l'exception du 1 et du 0. Pour gérer des nombres entiers ou flottants, il faut trouver un moyen de ramener deux-ci dans l'intervalle [0,1], chose qu'on abordera pas ici.
Pour convertir un nombre encodé en binaire vers un nombre stochastique, un circuit assez simple fait l'affaire. Il est composé d'un générateur de nombre aléatoire relié à un comparateur. Le comparateur compare l’opérande à convertir avec un nombre aléatoire. Si le nombre aléatoire est supérieur, le comparateur produit un 1, qui est ajouté au flux de bits. S'il est inférieur, c'est un zéro qui est inséré dans le flux de bit.
La conversion inverse, d'un nombre stochastique vers un nombre binaire en virgule fixe, demande un simple compteur. On suppose que le compteur a une entrée COUNT, qui ordonne d'incrémenter le compteur. Le compteur est automatiquement incrémenté quand l'entrée est à 1, il ne se passe rien sinon. Le flux de bit alimente l'entrée COUNT de ce compteur.
Les opérations sur les processeurs stochastiques
[modifier | modifier le wikicode]Les ordinateurs stochastiques sont généralement de type bit sériels ce qui veut dire que les bits sont traités un par un par l'unité de calcul. Les opérations simples entre deux probabilités se font donc avec des opérations bit à bit. L'avantage est que les processeurs bit-sériels ont une unité de calcul très simple, qui utilise très peu de portes logiques. Par exemple, l'ALU de l'ordinateur RASCEL n'utilisait que 32 portes logiques et 3 bascules pour faire son travail, tout en supportant les 4 opérations de base.
Nous avions vu comment faire une unité de calcul bit-sérielle dans les premiers chapitres sur wikilivres, nous ne reviendrons pas dessus. Par contre, il est intéressant de regarder ce que font les opérations logiques, quels calculs probabilistes elles implémentent.
La porte NOT prend en entrée une probabilité p et fournit en sortie le terme (1 - p).
| NOT | Opérande | Suite de bits | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.6 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | |
| 0.4 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | |
Le ET bit à bit multiplie deux probabilités :
| ET | Opérande | Suite de bits | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.6 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | |
| 0.5 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | |
| 0.3 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
Le OU bit à bit effectue le calcul suivant entre deux probabilités P1 et P2:
L'addition classique n'a pas beaucoup de sens avec des probabilités. Par contre, il existe une opération d'addition normée, qui est définie comme la moyenne de deux probabilités. Elle calcule la moitié de leur somme, ce qui garantit que le résultat reste dans l'intervalle [0,1]. Avec l'encodage stochastique, elle se calcule en prenant aléatoirement la moitié des bits de chaque opérande et de les combiner pour obtenir le résultat. Pour cela, on peut envoyer les deux opérandes à additionner sur les entrées d'un multiplexeur, si l'entrée de commande reçoit un flux de bit aléatoire égal à 1/2 en codage stochastique. Le bit choisit change d'un cycle à l'autre, ce qui combine aléatoirement les bits des deux opérandes.
Il est possible d'améliorer le tout pour ne pas calculer la moitié de la somme, mais une addition pondérée. Par addition pondérée, on veut dire faire le calcul suivant :
Pour cela, il suffit de modifier ce qui est envoyée sur l'entrée de commande du MUX. La séquence de bits envoyée sur l'entre de commande est elle-même un nombre stochastique, qui encode le nombre K. Par exemple, si on veut utiliser le coefficient K = 1/3, il suffit d'envoyer le nombre 1/3 codé par encodage stochastique, sur l'entrée de commande du MUX.
L'opération de division est plus complexe que la multiplication. Mais les machines stochastiques utilisaient souvent un encodage particulier pour les résultats de divisions. Elles encodaient le numérateur et le dénominateur séparément. Il était possible de multiplier/additionner/soustraire des numérateur entre eux, des dénominateurs entre eux, ce qui permettait de manipuler des fractions.
La précision et l'indépendance des résultats
[modifier | modifier le wikicode]Les exemples précédents sont conçus pour donner un résultat exact, mais le résultat n'est pas toujours exact sur un ordinateur stochastique. Mais pour la multiplication 0.6 * 0.5, avec 10 bits, on peut trouver des cas où le résultat est 0.1, 0.2, 0.5, voire 0, et non 0.3. Tout dépend de comment les bits sont répartis. Mais avec un grand nombre de bits, le résultat se rapproche du résultat exact.
C'est là un désavantage clair du calcul stochastique. Les opérations sont imprécises, elles ne donnent pas un résultat exact. L'imprécision se réduit en augmentant le nombre de bits codant une probabilité, mais ne s'annule jamais. Il faut donc utiliser un grand nombre de bits pour obtenir un résultat correct. Dans le détail, si les bits sont supposés indépendants et générés par un processus aléatoire de type binomial, on peut prouver que la précision n'est pas la même entre le TPS et le BP. Avec le TPS, la précision augmente avec la racine carrée du nombre de bits. Alors qu'avec le BP, il augmente proportionnellement au nombre de bits.
Une autre propriété importante est que les bits doivent être indépendants pour que les calculs soient corrects. C'est à dire que quand on reçoit un bit, on ne peut pas prédire le suivant, ni même avoir une quelconque information en plus sur le suivant, au-delà de la probabilité encodée. Quand ce n'est pas le cas, les calculs stochastiques deviennent plus compliqués. Par exemple, prenons le cas où on multiplie une probabilité par elle-même. Le ET entre un nombre A et lui-même donne toujours A. Pour éviter ce problème, une solution est de simplement décaler la seconde opérande d'un cycle d'horloge, pour casser la dépendances entre A et lui-même. Les bits ne sont alors pas à la même place et la multiplication fonctionne.
| ET | Opérande | Suite de bits | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0.6 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | X | |
| 0.6 | X | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | |
| 0.3 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | |
Les architectures stochastiques : conclusion
[modifier | modifier le wikicode]Pour résumer, les architectures stochastiques ont de nombreux défauts. Il s'agit d'architectures fondamentalement simples, très limitées. Elles utilisent peu de circuits, c'est leur seul avantage. Mais elles sont imprécises, font des erreurs, donnent des résultats approximatifs.
Et c'est sans compter que l'implémentation des quatre opérations de base est compliquée. Déjà, faire rentrer des opérandes entières-flottantes dans une probabilité demande d'appliquer une fonction mathématique précise lors de la traduction, pour faire rentrer les opérandes dans l'intervalle [0,1] via une bijection. De plus, autant la multiplication est triviale, autant la division, l'addition et la soustraction s'adaptent assez mal à l'encodage utilisé. En tant qu'architectures généralistes, force est de constater qu'il s'agit d'une impasse.
Un autre défaut est que leur encodage unaire colle assez mal avec des mémoires RAM, mieux vaut stocker les données en binaire dans de la RAM, avant de convertir le tout en unaire avec de faire les calculs. Et dans ce cas, autant faire les calculs directement en binaire. Le cout des conversions binaire <-> stochastique réduit grandement l'intérêt d'utiliser un encodage unaire.
Par contre, les architectures stochastiques ont des utilisations très spécialisées. Il est possible d'utiliser des circuits stochastiques simples dans des applications fondamentalement statistiques. Par exemple, des circuits de décodage LPDC peuvent utiliser des circuits stochastiques. La simulation de certains réseaux de neurones, dit spike-timed neural networks, s'adapte assez bien à des circuits stochastiques. Des applications de niche, mais qui existent.