Pages techniques

La mémoire morte contient le minimum de programme permettant de démarrer le système:

• les différents codes logiques nécessaires à l'initialisation du processeur (vecteur de "RESET", adresses des piles...),
• le programme et le code pour le téléchargemen des FPGAs indispensables pour l'accès à la mémoire vive et aux systèmes de fichiers contenant l'ensemble des autres programmes.

Le processus de démarrage est donc contenu dans la mémoire morte qui a pour inconvénient d'être très lente ce qui implique le chargement du noyau FORTH dans la mémoire vive. Dès que ce chargement es réalisé, le processeur n'utilise plus la mémoire morte afin de bénéficier du maximum de vitesse d'exécution.

Par définition, le noyau FORTH contient l'ensemble des instructions les plus utilisées dans n'importe quel programme. C'est pour cela qu'il est chargé dans la mémoire vive statique qui contient aussi le noyau temps réel, les variables système ainsi que les piles de données et de retour.

Etant donné que la mémoire vive statique es de faible capacité (il y en a quand même 512 KiloOctets !), toute nouvelle instruction est compilée par défau dans la mémoire vive dynamique. Une directive "ZONE_RAPIDE" permet au programmeur d'ajouter des instructions dans la mémoire vive statique pour optimiser son code (primitives graphiques ou arithmétiques par exemple). Cette primitive doit être située juste avant la définition de l'instruction devant être optimisée en vitesse. Dès la fin de la définition de l'instruction, le compilateur repasse en mémoire vive dynamique.

Chacune des instructions compilées dans la mémoire est composée selon le tableau suivant:

Nb. d'octets	Signification
4	Ces 4 octets contiennen le décalage en nombre d'octets entre l'adresse de l'entête qui suit et celle de l'entête de l'instruction précédente. Ce nombre est toujours pair. Il est à 0 lorsqu'il s'agi de la première instruction.
1	Cet octet renseigne le compilateur sur les caractéristiques de l'instruction: bit 7 : mis à 1 si l'instruction est immédiate (c'est à dire exécutée en mode compilation), bit 6 : mis à 1 si l'instruction est directe (c'es à dire que son contenu est directement compilé dans l'instruction qui l'utilise en mode compilation), bits 5 à 0 : ils contiennent le nombre de caractères du nom de l'instruction (1 à 63). On peut utiliser cette adresse pour afficher la chaîne de caractère du nom de l'instruction en utilisant la séquence "COUNT 63 AND TYPE".
1 à 63	C'est la chaîne de caractère donnant le nom en code ASCII de l'instruction.
0 ou 1	Cet octet est ajouté avec la valeur 0 si son adresse est impaire. Le processeur ne peu en effet exécuter du code que si celui-ci est stocké dans des adresses paires.
2*n	C'est le code de l'instruction écrit dans le langage du processeur. Il est toujours terminé par le code de retour de sous-programme.

Les 4 premiers octets correspondent à la valeur "HERE" plus 4 moins celle de la variable "START" au momen de la compilation de l'instruction précédente. Lorsqu'une nouvelle instruction est crée par le mot ":", le contenu de la variable "START" est soustrait à la valeur "HERE" puis incrémenté de 4 et compilé ("HERE" est alors incrémenté de 4 à son tour). Le contenu de la variable "START" est alors remplacé par la valeur "HERE". La chaîne de caractère suivi du code sont ensuite compilés.

L'instruction "IMMEDIAT" positionne le bit 7 du premier octet à "1" si l'instruction doit être exécutée en mode compilation.

L'instruction "DIRECT" positionne le bit 6 du premier octet à "1" si l'instruction doit être compilée directement et non pas appelée par une instruction de saut à sous-programme. Ceci est indispensable pour bénéficier pleinement des performances du processeur pour les instructions de base ("DUP", "DROP", "+", ...). Dans le cas d'un processeur non FORTH comme le MC68030, l'utilisation d'une de ces instructions équivau à écrire un programme en assembleur.

Si les bits 7 et 6 de cet octet sont tous les 2 à "1", il s'agit alors d'une instruction qui sera exécutée en mode interprétation ET en mode compilation.

La chaîne de caractère comportant le nom de l'instruction est du type de celle manipulable directement par n'importe quel noyau FORTH. Sa longueur minimale est de 1 (instructions "+", "-", "/", "*", ...) et est plafonnée à 63 (longueur qui est relativemen peu pratique à utiliser mais qui sait...). Il est éviden qu'il ne peut y avoir de caractère "espace".

Un octet est ajouté si l'adresse suivant la chaîne de caractère est impaire pour permettre de démarrer le code à une adresse paire comme l'exige le processeur (octet de "padding" pour les anglophobes).

Suit enfin le code propre à l'instruction qui es directement interprétable par le processeur.

Pour comprendre la disposition des différentes instructions dans la mémoire, voici un tableau présentant un FORTH vraiment très pauvre car il ne possède que 5 instructions mais, je l'espère, très clair pour visualiser l'organisation du vocabulaire:

Mémoire vive statique (exécution rapide)
	0
Instruction 1	Octet contenant les caractéristiques 1
	Chaîne de caractère contenan le nom 1
	Code 1
	Pointeur sur Instruction 2 - Pointeur sur Instruction 1
Instruction 2	Octet contenant les caractéristiques 2
	Chaîne de caractère contenan le nom 2
	Code 2
	Pointeur sur Instruction 4 - Pointeur sur Instruction 3
Instruction 4	Octet contenant les caractéristiques 4
	Chaîne de caractère contenan le nom 4
	Code 4
	...
Mémoire vive dynamique (exécution relativement lente)
	Pointeur sur Instruction 3 - Pointeur sur Instruction 2
Instruction 3	Octet contenant les caractéristiques 3
	Chaîne de caractère contenan le nom 3
	Code 3
	Pointeur sur Instruction 5 - Pointeur sur Instruction 4
Instruction 5	Octet contenant les caractéristiques 5
	Chaîne de caractère contenan le nom 5
	Code 5
	...

On retrouve bien une liste chaînée d'instructions constituant le vocabulaire du langage FORTH. Pour retrouver une instruction, la manière la plus simple est de partir de la dernière instruction créée (la variable "START" pointant son adresse) et de remonter jusqu'à ce que son nom corresponde ou alors jusqu'au début de la mémoire si elle n'existe pas (un décalage égal à 0 indique que l'on est arrivé au débu du vocabulaire).

Cette méthode, très simple à implémenter, possède l'inconvénient de devenir de plus en plus lente au fur et à mesure de l'augmentation du nombre des instructions. C'est ainsi que le FORTH original a été introduit avec la notion de vocabulaires multiples. Ceci perme d'optimiser le temps de recherche avec l'inconvénient de ne pas disposer de l'ensemble des instructions à tout moment. Mais j'ai abandonné cette idée au profit d'une autre méthode expliquée dans le paragraphe suivant.

Pour optimiser les temps de compilation, j'ai choisi la méthode de recherche dichotomique des instructions qui s'apparente à la méthode utilisée pour chercher un mot dans un dictionnaire ou une encyclopédie.

Le gros avantage d'un dictionnaire est que tous les mots sont classés par ordre alphabétique ce qui perme à quiconque connaissant l'alphabet de trouver un mot en éliminant la moitié des pages à chaque comparaison par rapport aux mots examinés. Pour simplifier, si l'on possède un dictionnaire de 1000 pages, sachez que vous n'aurez à examiner qu'un nombre maximum de 10 pages pour trouver le mot qui vous intéresse (logarithme en base 2 de 1000 pour les matheux).

Afin d'appliquer cette méthode très efficace au vocabulaire FORTH, il suffit d'avoir une représentation des instructions par ordre alphabétique ce qui se fai très simplement avec une table contenant la liste de tous les pointeurs des instructions, pointeurs classés dans l'ordre alphabétique du nom des instructions.

Pour éclaircir ce discours, rien ne vaut une petite démonstration:

Supposons un vocabulaire FORTH constitué de seulemen 10 instructions nommée chacune avec les 10 premières lettres de l'alphabet et dans l'ordre (plutôt désordre) suivant : "H", "B", "I", "A", "D", "F", "C", "E", "G" et "J" (la première instruction définie est "H" et la dernière est "J"). Si je veux exécuter l'instruction "A", l'interpréteur doit partir de "J" et faire 7 comparaisons avant de trouver l'instruction voulue.

En faisant un calcul simple, on peut estimer le nombre de comparaisons moyen à: 10(recherche de "H")+9(recherche de "B")+...+1(recherche de "J") le tout divisé par 10(nombre d'instructions) ce qui correspond à 5,5.

Maintenant, réalisons une table contenant les adresses de chacune de ces instructions classées dans l'ordre alphabétique:

Nombre d'instruction : 10

Adresse de l'instruction "A"

Adresse de l'instruction "B"

Adresse de l'instruction "C"

Adresse de l'instruction "D"

Adresse de l'instruction "E"

Adresse de l'instruction "F"

Adresse de l'instruction "G"

Adresse de l'instruction "H"

Adresse de l'instruction "I"

Adresse de l'instruction "J"

Pour trouver l'instruction "A", mon algorithme de recherche va commencer par saisir le nombre d'instructions soit 10. Il va alors pointer sur la moitié de la table et se trouver ainsi sur l'adresse de l'instruction "F". La comparaison des 2 chaînes de caractère va donner un résultat inférieur à "F". Il va alors pointer sur la moitié inférieure de la table soit sur l'adresse de l'instruction "C". Le résulta de la comparaison étant encore inférieur, l'algorithme pointe alors sur "B" puis enfin sur "A". Ceci donne un nombre total de 4 comparaisons à comparer à 7 pour l'algorithme précédent.

Faisons maintenant l'estimation du nombre moyen de comparaisons: 4(recherche de "A")+3(recherche de "B")+2(recherche de "C")+4(recherche de "D")+3(recherche de "E")+1(recherche de "F")+4(recherche de "G")+3(recherche de "H")+2(recherche de "I")+3(recherche de "J") le tout divisé par 10 ce qui correspond à 2,9 (à comparer à 5,5 de l'algorithme précédent).

La notion de vocabulaires multiples devient ainsi obsolète. Le doublement du nombre d'instruction n'introduit qu'une comparaison supplémentaire !