Simulation du microprocesseur GAPP en Smalltalk

(Suite numéro 2)

La classe Ram

 


Figure 1

 


Pour représenter la mémoire des processeurs élémentaires, nous préférons regrouper 128 plans de 6x12 bits plutôt que de distribuer une mémoire individuelle de 128 bits à chacun des 6x12 processeurs.

 

Lors de la construction des Pe, leur position dans la grille est mémorisée dans la variable position de chaque Pe. Chaque Pe connaît également le Gapp les contenant, et enfin, le message « memoire » envoyé au Gapp permet un accès à l’instance de Ram créée lors de l’initialisation du Gapp.

 

Message pour créer une instance de Ram, configurée correctement :

 

Ram new: (6@12) profondeur: 128

 

Habituellement lorsque l’on créer une sous-classe de la classe Object, le message new envoyé à la classe permet de créer une nouvelle instance. Donc, pour créer une instance de la classe Ram, il suffit d’utiliser l’expression Ram new. Mais l’instance ainsi créée ne serait pas initialisée.

 


 

Nous avons besoin de donner les paramètres de taille et de profondeur pour initialiser notre instance. Nous avons donc défini dans la métaclasse Ram class un nouveau message d’instanciation, (le message new:profondeur:) Voir cadre 4.

 

La variable frames est définie (Voir cadre 1) pour contenir un tableau d’images à un bit par pixel. La variable profondeur n’est donc pas strictement nécessaire, puisqu’on pourrait connaître la profondeur de la mémoire en demandant la taille du tableau frames (avec l’expression frames size).

La variable adresse ne fait pas partie de la structure[1] de la Ram, elle représente plutôt le décodeur d’adresse, ou encore la valeur du bus d’adresse pendant l’éxecution d’une instruction.

 

Object subclass: #Ram

            instanceVariableNames: 'frames profondeur adresse '

            classVariableNames: ''

            poolDictionaries: ''

            category: 'VL-Gapp'!

Cadre 1 : Définition de la classe Ram

 

!Ram methodsFor: 'initialize-release'!

 

taille: taille  profondeur: plans

            frames := (1 to: plans) collect: [:page |

                        Image extent: taille depth: 1 palette: (MappedPalette whiteBlack) ].

            profondeur := plans.! !

Cadre 2 : protocole d’initialisation.

 

Construction des Images

La classe Image et ses sous-classes sont utilisées pour représenter les images (ou bitmap) en Smalltalk.

Par exemple, pour faire une « photo d’écran », envoyez un message « fromUser » à la classe Image. Le curseur de la souris se met en croix, et attends que vous désigniez une zone de l’écran. Le résultat est une instance d’une des sous classes d’Image correspondant à la définition en bit par pixel de votre écran.

Avec le message fromUser, les pixels de l’image sont chargés avec le contenu de la mémoire d’écran. Une autre façon d’instancier une image, sans contenu particulier, est d’envoyer un message  « extent:depth:palette: » à la classe Image (toutes les valeurs des pixels seront à zéro).

L’argument du mot clé extent: doit être une instance de Point dont le x spécifie la largeur de l’image et le y spécifie la hauteur.

L’argument introduit par le mot clé depth: est la « profondeur » de l’image, c'est-à-dire sa « définition » en terme de nombre de bits par pixel. Pour des raisons d’implémentation, les profondeurs d’image sont contraintes à des valeurs comprises entre 1 et 32 bits par pixel.

Le mot clé palette: introduit le dernier paramètre : la Palette de couleurs à utiliser par le système pour décoder les valeurs des pixel en couleur (et inversement pour encoder les couleurs en valeur de pixel).

Par exemple, la palette retournée par l’expression MappedPalette whiteBlack, fait correspondre le 0 au blanc et le 1 au noir.

!Ram methodsFor: 'accessing'!

 

adresse: adr

            adresse := adr!

 

frames

            ^frames!

 

profondeur

            ^ profondeur!

 

readAt: position

            ^ (frames at: adresse + 1) atPoint: position - 1!

 

taille

            ^ frames first width @  frames first height!

 

write: value at: position

            (frames at: adresse + 1) atPoint: position - 1 put: value! !

Cadre 3 : protocole d’accès

Accès à la mémoire

Le cadre 3 présente les méthodes d’accès que nous avons prévu pour les instances de la classe Ram.

La méthode adresse: permet d’affecter la variable d’instance adresse dans le but de préparer les prochaines lectures ou les prochaines écritures. La valeur de l’adresse sera utilisée dans les méthodes readAt: et write:at:.

La méthode readAt: prend en argument la position (x@y) du pixel souhaité (correspondant à la position du Pe dans la grille), utilise la variable adresse pour connaître le numéro de l’image à utiliser (correspondant au numéro du bit dans la mémoire du Pe), et ramène la valeur 1 ou 0.

Pourquoi adresse + 1 et position – 1 ?

Dans le programme les adresses varient de 0 à 127 (ce que l’on peut encoder sur les 7 lignes d’adresse), nous ajoutons 1 pour obtenir un index dans le tableau frames, qui lui, doit varier de 1 à 128.

Le message atPoint: implémenté dans la classe Image prend quand à lui en argument un point dont le x doit varier de 0 à largeur de l’image moins 1 et le y de 0 à hauteur de l’image mois 1.

Le premier pixel de l’image (en haut à gauche), à pour coordonnées 0@0 (ou Point zero).

Le message write:at: est structuré de la même façon, il prend en outre la valeur à écrire, 0 ou 1, et la stocke dans l’image avec le message atPoint:put:.

 

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

 

Ram class

            instanceVariableNames: ''!

 

 

!Ram class methodsFor: 'instance creation'!

 

new: taille profondeur: plans

            ^super new

                        taille: taille  profondeur: plans! !

Cadre 4 : définition des variables d’instance de métaclasse (aucune), et protocole d’instanciation

 

Classe Instruction

 

La classe Instruction est très simple. Elle sert uniquement à mémoriser les instructions pour le Gapp.

Nous avons créé une variable programme dans la classe Gapp, et lors de l'initialisation la variable programme est affectée avec une collection ordonnée vide :

            programme := OrderedCollection new.

Les instructions du Gapp étant constituées d'une adresse (sur 7 bits) et du code opératoire (sur 13 bits) nous créons naturellement deux variables d'instance, adresse et code.

En Smalltalk, le type des variables n'a pas besoin d'être déclaré. Nous pouvons mettre n'importe quel objet dans n'importe quelle variable (à nous de savoir ce que nous faisons). C'est au moment de l'exécution du programme, lorsqu'un objet reçoit un message qu'il recherche la méthode à exécuter en fonction de sa classe.

 

Object subclass: #Instruction

            instanceVariableNames: 'adresse code '

            classVariableNames: ''

            poolDictionaries: ''

            category: 'VL-Gapp'!

Définition de la classe Instruction

 

 

!Instruction methodsFor: 'initialize-release'!

 

code: c adresse: a

            code := c.

            adresse := a! !

Protocole d'initialisation. Lors de la création d'une nouvelle instruction, nous spécifions son adresse et son code, ensuite, ces valeurs ne changent pas.

 

 

!Instruction methodsFor: 'execution'!

 

executeAvec:gapp

            gapp cycle1.

            gapp cycle2cm: ((code bitShift: 0) bitAnd: 3)

                        ns:  ((code bitShift: -2) bitAnd: 7)

                        ew:  ((code bitShift: -5) bitAnd: 7)

                        c:  ((code bitShift: -8) bitAnd: 7)

                        ram: ((code bitShift: -11) bitAnd: 3).

            gapp cycle3! !

Protocole pour l'exécution des programmes Gapp.

Le rôle de l'instruction, après avoir donné son adresse à la mémoire (voir le message executer du Gapp), est de piloter le Gapp en trois cycles. Les 1er et 3ième cycles seront décrits dans le chapitre des Pe. Le second cycle consiste pour l’instruction, à décomposer le code en ses 5 parties, correspondant au contrôles pour le registre de communication cm, le code de contrôle du registre ns, celui du registre ew, de c, et enfin de la mémoire ram.

Les différentes parties sont extraites à coup de bitShift: et de bitAnd:. Le et logique avec 3 (11 binaire) masque tous les autres bits et ne laisse que les deux derniers. Le 7 (111 binaire) permet de ne conserver que les 3 bits de poids faible.

Pourquoi envoyer le message  « bitShift: 0 », puisqu’un décalage de 0 bits ne change pas le résultat ?

Simplement pour la lisibilité et la régularité de la formule, mais on peut la simplifier.

 

 

!Instruction methodsFor: 'printing'!

 

printOn: aStream     

            aStream nextPutAll: adresse printString, ' ', (code printStringRadix: 2)! !

Protocole d’impression.

La méthode printOn: reçoit en paramètre un flux en écriture sur une chaîne de caractères, et doit y produire une version imprimable de l’objet. Ici, l’adresse en base dix et le code en binaire.

 

!Instruction methodsFor: 'accessing'!

 

adresse

            ^ adresse!

 

code

            "pour l'interface"

            ^ code! !

Je n’ai pas écrit beaucoup de commentaires dans le code. Mais en voici un exemple. Le texte entre guillemets n’est pas interprété par Smalltalk. Il est simplement conservé avec le texte source de la méthode pour les relectures.

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

 

Instruction class

            instanceVariableNames: ''!

 

 

!Instruction class methodsFor: 'instance creation'!

 

code: c adresse: a

            ^super new code: c adresse: a! !

Définition des variables d’instance de métaclasse (aucune), et méthode d’instanciation de la classe Instruction.

Pour créer une nouvelle instruction :

Instruction code: 1792 adresse: 0

Exemple de programme qui crée un Gapp, stocke un programme de deux instructions et l’exécute, puis ouvre un éditeur sur le second plan de mémoire (l’image correspondant à l’adresse 1 est à l’index 2 du tableau frames).

 

| gapp |

gapp := Gapp new.

gapp programme add:  (Instruction code: 1792 adresse: 0).

gapp programme add:  (Instruction code: 4096 adresse: 1).

gapp executer.

BitView openOn: (gapp memoire frames at: 2) scale: 8@8!

Ecrivez 1792 et 4096 en binaire, et décodez les deux instructions pour comprendre pourquoi l’Image est toute noire.

 

Classe Pe

Nous atteignons enfin le cœur du problème. La classe Pe qui représente les processeurs élémentaires.

Le nombre de variables d’instance nommées dans un objet Smalltalk est de 256 au maximum. Pour les tableaux dont les variables d’instance sont des entiers, la limite est plus haute. Heureusement, nous n’avons besoin que de 25 variables !

 

Object subclass: #Pe

            instanceVariableNames: 'gapp nord sud est ouest position cm ns ew c ual inputCms outputCm inputE outputEW inputW inputN outputNS inputS outputC microCm microNs microEw microC microRam '

            classVariableNames: ''

            poolDictionaries: ''

            category: 'VL-Gapp'!

Définition de la classe Pe

 


 

gapp

Lien vers le Processeur gapp (pour accéder à la mémoire)

nord

Lien vers les Pe voisins immédiat. Pour les Pe situés sur les bords, lien vers les Pe du bord opposé.

sud

est

ouest

position

Point indiquant les coordonnées x et y du Pe dans la grille (pour accéder à la mémoire)

cm

Registres

ns

ew

c

ual

Unité Arithmétique et logique

inputCms

Entrées sorties du registre Cm (sauvegarde de l’état de cm lors du cycle 1)

outputCm

inputE

Sauvegarde du registre EW du Pe de l’est lors du cycle 1

outputEW

Sauvegarde de l’état de EW lors du cycle 1

inputW

Sauvegarde du registre EW du Pe de l’ouest lors du cycle 1

inputN

Idem pour l’axe nord-sud

outputNS

inputS

outputC

Sauvegarde de l’état de C lors du cycle 1

microCm

Microcode correspondant aux cinq contrôles. Implémenté sous la forme de cinq collections de blocs.

microNs

microEw

microC

microRam

 

!Pe methodsFor: 'connexions'!

 

est: pe

            est := pe.

            pe ouest: self.!

 

nord: pe

            nord := pe!

 

ouest:pe

            ouest := pe!

 

sud: pe

            sud := pe.

            pe nord: self! !

Pour établir les connections entre les Pe voisins, on utilise les messages est: et sud: qui établissent le lien en retour. Voir le message connectionTorique dans la classe Gapp.

 

Le protocole d’initialisation, ci-dessous, contient trois méthodes, la méthode gapp: permet de mémoriser le Gapp qui contient le Pe, la méthode position: permet de mémoriser la position du Pe dans la grille et enfin la méthode initialize, la plus cool, met à zéro tous les registres et rempli les collections de « microcode ».

 

Détaillons l’instruction Smalltalk suivante :

microCm := (OrderedCollection new)

                        add: [cm := gapp memoire readAt: position ];

                        add: [cm := inputCms ];

                        add: [cm := 0];

                        yourself.

Orderedcollection new instancie une nouvelle collection ordonnée, et vide.

Le message add: et envoyé a cette collection a plusieurs reprises, pour ajouter à la collection les blocs correspondant aux actions à faire en fonction du code correspondant au contrôle du registre CM.

Le code 00 n’est pas utilisé (Il s’agit d’un NOP).

Le code 01 correspond à l’instruction GAPP : CM := RAM (chargement du registre CM avec le résultat de la lecture de la ram à l’adresse spécifiée par l’instruction).

Le code 10 correspond au chargement du registre CM par la valeur de l’entrée sud de CM (CMS).

Enfin le code 11 charge 0 dans le registre CM.

Le message yourself envoyé à la collection ramène simplement la collection pour la ranger dans la variable microCm. En effet, le message add: ramène l’élément qui est ajouté à la collection et non pas la collection elle-même. Si on omet le yourself, c’est le dernier bloc qui serait rangé dans microCm.

 

Pour utiliser ce mécanisme, il suffit d’adresser la collection avec le code, et d’exécuter le bloc (avec le message value). Voir la méthode «cycle2cm:ns:ew:c:ram: » elle contient l’instruction Smalltalk suivante :

codecm > 0 ifTrue: [ (microCm at: codecm) value ].

(où codecm est le code de contrôle du registre cm variant de 0 a 3).

 

Pourquoi utiliser des collections de blocs ?

Pour éviter une série de tests du style si codecm = 1 alors truc sinon si codecm = 2  alors machin…

Pas très lisible, ni efficace. Ici un simple accès a la collection avec le message at: permet de trouver directement le bloc de code à exécuter. Il n’y a pas de « switch » ni de « select case » ni de « cond » en Smalltalk.

 

Pourquoi chaque Pe contient ses propres cinq listes de blocs ?

On pourrait penser que, comme tous les Pe doivent se comporter de la même façon, il est inutile de constituer des listes par Pe, on pourrait regrouper cela au niveau de la classe. En fait non, puisque les blocs contiennent des références aux variables d’instance des Pe. Les blocs ne pourraient pas être compilés dans une méthode de classe.

 

Mais alors, pourquoi ne pas en faire des méthodes d’instance ?

Oui, c’est une possibilité, on aurait pu écrire autant de méthodes qu’il y a de blocs et stocker dans les collections les noms des méthodes, puis utiliser le message perform: qui permet d’envoyer à un objet un message dont le nom résulte d’un calcul ou d’une expression. Mais avouez, avec ces listes de blocs, on voit tout le code correspondant à tout le jeu d’instruction en une seule méthode. Je préfère comme ça.

 

 

!Pe methodsFor: 'initialize-release'!

 

gapp: g

            gapp := g!

 

initialize

            cm := ns := ew := c := 0.

            ual := Ual new.

            inputCms  := inputE := outputEW :=  inputW :=  inputN  := outputNS  := inputS := outputC := 0.

            microCm := (OrderedCollection new)

                        add: [cm := gapp memoire readAt: position ];

                        add: [cm := inputCms ];

                        add: [cm := 0];

                        yourself.

            microNs := (OrderedCollection new)

                        add: [ns := gapp memoire readAt: position ];

                        add: [ns := inputN ];

                        add: [ns := inputS ];

                        add: [ns := outputEW ];

                        add: [ns := outputC ];

                        add: [ns := 0];

                        yourself.

            microEw := (OrderedCollection new)

                        add: [ew := gapp memoire readAt: position ];

                        add: [ew := inputE ];

                        add: [ew := inputW ];

                        add: [ew := outputNS ];

                        add: [ew := outputC ];

                        add: [ew := 0];

                        yourself.

            microC := (OrderedCollection new)

                        add: [c := gapp memoire readAt: position ];

                        add: [c := outputNS ];

                        add: [c := outputEW ];

                        add: [c := ual outputCy ];

                        add: [c := ual outputBw ];

                        add: [c := 0];

                        add: [c := 1];

                        yourself.

            microRam := (OrderedCollection new)

                        add: [gapp memoire write: outputCm at: position ];

                        add: [gapp memoire write: outputC at: position ];

                        add: [gapp memoire write: ual outputSm at: position ];

                        yourself.!

 

position: p

            position := p! !

 

!Pe methodsFor: 'printing'!

 

printOn: aStream

            aStream nextPutAll: 'Pe[', position printString, ']'.! !

Méthode d’ « impression » d’un Pe. Pour mieux les voir, quand on inspecte la grille de Pe, chaque Pe s’affichera avec sa position entre crochet.

 

!Pe methodsFor: 'execution'!

 

cycle1

            outputCm := cm.

            outputEW := ew.

            outputNS := ns.

            outputC := c.

            inputCms := sud cm.

            inputE := est ew.

            inputW := ouest ew.

            inputN := nord ns.

            inputS := sud ns.!

 

cycle2cm: codecm ns: codens ew: codeew c: codec ram: coderam

            codecm > 0 ifTrue: [ (microCm at: codecm) value ].

            codens > 0 ifTrue: [ (microNs at: codens) value ].

            codeew > 0 ifTrue: [ (microEw at: codeew) value ].

            codec > 0 ifTrue: [ (microC at: codec) value ].

            coderam > 0 ifTrue: [ (microRam at: coderam) value ]!

 

cycle3

            ual inputNs: ns.

            ual inputEw: ew.

            ual inputC: c.

            ual executer! !

Protocole pour l’exécution.

Le cycle 1

Le cycle 1 sauve dans les variables input* et output* les valeurs des registres qui peuvent être utilisées (en lecture) dans les instructions et qui sont perdues lors de l’exécution des instructions (destinées justement à modifier les valeurs des registres).

Certaines variables sont inutiles en fait. Comme il n’y a que 4 registres, quatre variables de sauvegarde auraient suffit. On voit par exemple que le registre EW est sauvé trois fois, une fois dans outputEW, une fois par le voisin est dans son inputW et une troisième fois dans inputE par le Pe voisin à l’ouest.

Je vous propose donc, de modifier le code, pour ne faire que quatre affectations dans le cycle 1. Il faut modifier la définition de la classe Pe et modifier la méthode d’initialisation (initialisation des variables et blocs de microcode).

Pour contrôler votre travail, testez le programme suivant par exemple :

 

Mnémonique

Ram

C

EW

NS

CM

Adresse

Code

EW=RAM0

 

 

001

000

00

0

32

EW=E

 

 

010

000

00

0

64

EW=E, NS=EW, C=0

 

110

010

100

00

0

1616

EW=RAM0, NS=0, C=BW

 

101

001

110

00

0

1336

C=CY

 

100

000

000

00

0

1024

RAM1=C

10

000

000

000

00

1

4096

Ce programme de six instructions (issu de la description technique du GAPP) permet de détecter les patterns 1 0 1 dans l’image de la RAM 0 en écrivant un 1 dans la RAM 1 là ou le pattern se présente.

L’instruction EW=RAM0 permet de charger l’image à analyser dans l’ensemble des registre EW des Pe.

Ensuite, EW=E fait glisser l’image d’un pixel vers l’ouest (puisque chaque processeur reçoit le contenu du registre de son voisin d’est).

La troisième instruction continue à faire glisser l’image vers l’ouest d’un second pixel dans EW, mais en même temps, l’image décalée d’un pixel est copiée dans l’ensemble des registres NS. C est mis à zéro, de sorte que BW contienne le résultat de (non(NS) et EW), c'est-à-dire 1 si le pixel décalé d’un cran est 0 et le pixel décalé de deux crans est 1, sinon 0.

La quatrième instruction recharge le premier pixel dans EW (en fait recharge l’image complète non décalée dans l’ensemble des registres EW des Pe), récupère le résultat du et logique précédent dans C à partir de BW et colle un 0 dans NS pour mettre dans CY le résultat de (EW et C).

A ce stade dans CY nous avons (3ieme pixel & non(2nd pixel) & 1er pixel), l’instruction suivante place ce résultat dans C avant que la dernière instruction ne l’écrive dans la ram à l’adresse 1.

Simple comme bonjour ! Dans le manuel technique, on peut lire «  Programming the array is relatively straightforward ; bit-serial computation accomplishes traditional tasks like addition and multiplication. The algorithm for recognizing a 101 pattern demonstrates its ability to take care of both arithmetic and logical operations » .

J’admire la simplicité de ce programme, mais j’avoue que la simulation d’un GAPP en Smalltalk, même si elle peut paraître complexe ;-), l’est sûrement moins que d’écrire un compilateur Smalltalk en langage d’assemblage pour GAPP.

Le cycle 2

Le cycle 2 exécute le bloc de microcode correspondant à chaque partie de l’instruction.

Le cycle 3

Le cycle 3 fait fonctionner l’Ual.

Il place les nouvelles valeurs des registres dans les entrées de l’Ual, et lui envoie le message exécuter.

C’est donc à l’instruction suivante que les résultats de l’Ual pourront être placés dans un registre ou dans la mémoire Ram.

 

!Pe methodsFor: 'accessing'!

 

cm      

            ^ cm!

 

ew

            ^ ew!

 

ns

            ^ ns! !

Les câbles pour accéder aux registres des voisins.

 

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

 

Pe class

            instanceVariableNames: ''!

 

 

!Pe class methodsFor: 'instance creation'!

 

new: position

            ^super new initialize position: position! !

Création des instances de la classe Pe.

 

 

 (à suivre…)

 

Le modèle est complet, la suite décrira l’interface réalisée pour visualiser et interagir avec notre simulation.

 

 



[1] Ce que nous considérons comme faisant partie de la structure des objets sont les variables d’instance pointant vers des objets « appartenant » à celui-ci, en général affecté à l’initialisation et changeant rarement de valeur au cours du temps.

Typiquement, la variable frames est dans ce cas.