Technical pages
Vocabulary and memory
Program memory
Starting up process
Instructions description
Vocabulary and chained list
Instruction searching
Introduction
The object of this page is to describe principles for the
management of the set of FORTH instructions ( vocabulary) in my
system by justifying them. This description is cut in several
paragraphs:
Attention, although my system is completely based on the
FORTH, it is indispensable indeed to study the contents of this
page to be able to benefit from optimal performances of the processor.
Program memory
If one disregards various mass memories (hard disk, ...)
one can consider that a computer board possesses 3 types of memories
being able to contain at the same moment programs and data:
- the ROM or very slow permanent employee allowing the system
starting up at the power on,
- the very fast static RAM but of weak capacity,
- the dynamic RAM of strong capacity but relatively slow.
All the craftiness consists in optimizing the program and
data location in these various memories in functions of wished
performances.
Starting up process
The ROM contains the minimum of program allowing to star
system:
- various logical codes necessary for the processor initialization
(" RESET's " vector, stacks addresses, ...),
- program and code for the downloading of the indispensable
FPGAS for the RAM access and to the files systems containing
the set of the other programs.
The starting up process is so contained in the ROM which
has for inconvenience to be very slow what involves the load of
the FORTH kernel in the RAM. As soon as this load is realized,
the processor does not use any more the ROM to benefit from the
maximum of speed of execution.
By definition, the FORTH kernel contains the set of instructions
the most used in any program. It is for it that it is loaded in
the static RAM which contains also the real-time kernel, variable
system as well as the data and return stacks.
Given that the static RAM is of weak capacity (there is
it all the same 512 KiloBytes!) any new instruction is compiled
by default in the dynamic RAM. A directive " ZONE_RAPIDE
" allows the programmer to add instructions in the static
RAM to optimize its code (graphic or arithmetical primitives for
example). This primitive must be situated just before the definition
of the instruction to be optimized hurriedly. From the end of
the instruction definition, the compiler goes back in dynamic
RAM.
Instructions description
Each of instructions compiled in the memory is consisted
according to the following table:
|
Nb. of bytes
|
Meaning
|
|
4
|
These 4 bytes contain gap
in number of bytes enter its header address which follows and
that of of the previous instruction header address. This number
is always even. It is 0 when it is about the first instruction. |
|
1
|
This byte informs the compiler about the instruction
characteristics:
- bit 7: put in 1 if instruction is immediate (that is executed
in compilation mode),
- bit 6: put in 1 if instruction is direct (that is tha
its contents are directly compiled in the instruction which uses
it in compilation mode),
- bits 5 - 0: they contain the number of characters of the
instruction name (1 in 63).
One can use this address to show the character string of
the instruction name by using the sequence " COUNT 63 AND
TYPE".
|
|
1 - 63
|
It is the character string
giving the instruction name in ASCII code. |
|
0 or 1
|
This byte is added with the value
0 if its address is odd. The processor can indeed execute of
the code only if this one is stored in even addresses. |
|
2*n
|
It is the code of the instruction
wrote in the processor language. It is always ended by the code
of return from subroutine. |
The first 4 bytes correspond to the value "HERE"
more 4 less that of variable " START " at the time of
the compilation of the previous instruction. When a new instruction
is create by the word ":", the contents of variable
" START " are subtracted from the value "HERE"
then incremented with 4 and compiled ("HERE" is then
incremented with 4). The contents of variable " START "
are then replaced by the value "HERE". The character
string followed by the code are then compiled.
Instruction "IMMEDIATE" positions the bit 7 of
the first byte in "1" if instruction must be executed
in compilation mode.
Instruction "DIRECT" positions the bit 6 of the
first byte in "1" if instruction must be directly compiled
and not called by an instruction of jump to subroutine. This is
indispensable completely to benefit from performances of the processor
for basic instructions (" DUP ", " DROP ",
"+", ...). In the case of a processor not FORTH as the
MC68030, the use of one of these instructions amounts to write
a program in assembler language.
If the bits 7 and 6 of this byte are all in "1",
it is then about an instruction which will be executed in interpretation
AND compilation mode.
The character string containing the instruction name is
the type of that manipulable directly by any FORTH kernel. The
minimal length is of 1 (instructions " + " , "
- " , " / " , " * " , ...) and is pu
an upper limit at 63 (length which is relatively impractical to
use). It is evident that it can not there have of character "space".
A byte is added if address following the character string
is odd to allow to start code at an even address as requires i
the processor (padding byte).
Follows finally appropriate code for the instruction which
is directly interpretable by the processor.
Vocabulary and chained list
To understand the location of various instructions in the
memory, here is a table presenting a really very poor FORTH because
it possesses only 5 instructions but, I hope, very clearly to
show the vocabulary organization:
|
Static RAM ( fast execution
time)
|
| |
0
|
|
Instruction 1
|
Byte containing characteristics 1
|
|
Character string containing the name 1
|
|
Code 1
|
| |
Instruction 2 pointer
-Instruction 1 pointer
|
|
Instruction 2
|
Byte containing characteristics 2
|
|
Character string containing the name 2
|
|
Code 2
|
| |
Instruction 4 pointer
- Instruction 3 pointer
|
|
Instruction 4
|
Byte containing characteristics 4
|
|
Character string containing the name 4
|
|
Code 4
|
| |
...
|
|
Dynamic RAM ( relatively
slow execution time)
|
| |
Instruction 3 pointer
- Instruction 2 pointer
|
|
Instruction 3
|
Byte containing characteristics 3
|
|
Character string containing the name 3
|
|
Code 3
|
| |
Instruction 5 pointer
- Instruction 4 pointer
|
|
Instruction 5
|
Byte containing characteristics 5
|
|
Character string containing the name 5
|
|
Code 5
|
| |
...
|
One well finds an instructions chained list establishing
the vocabulary of the language FORTH. To find an instruction,
the most simple way is to leave of the last created instruction
(variable " START " pointing its address) and to go
back up until the name corresponds or then till the beginning
the memory if it does not exist (a gap equal to 0 indicates tha
one arrived at the beginning of the vocabulary).
This method, very simple to implement, possesses the inconvenience
of future more and more slow according to the increase of the
instructions number. And so the original FORTH was introduced
with the notion of multiple vocabularies. This allows to optimize
the time of search with the inconvenience not to arrange the se
of instructions at any time. But I abandoned this idea for the
benefit of another method explained in the following paragraph.
Instructions searching
To optimize the compilation time, I chose the method of
binary search of the instructions which is similar to the method
used to look for a word in a dictionary or an encyclopedia.
The big advantage of a dictionary is that all the words
are alphabetized what allows whoever knowing the alphabet to find
a word by eliminating half of the pages in every comparison with
regard to examined words. To simplify, if one possesses a dictionary
of 1000 pages, know that you will have to examine only a maximum
number of 10 pages to find the word which interests you (logarithm
in base 2 of the 1000 for math student).
To apply this very effective method to the FORTH vocabulary,
it is enough to have an in order alphabetical representation of
instructions what makes very simply with a table containing the
list of all the instructions pointers, classified in the alphabetical
order of the instructions names.
To clear up this speech, nothing is worth a small demonstration:
Let us suppose a FORTH vocabulary constituted by only 10
instructions named each with the first 10 letters of the alphabe
and in the order (rather disorder) following: " H ",
" B ", "I", " A ", " D ",
" F ", " C ", " E ", " G "
and " J " (first defined instruction is " H "
and the last one is " J "). If I want to execute instruction
" A ", the interpreter has to leave of " J "
and make 7 comparisons before finding deliberate instruction.
By making a simple calculation, one can estimate the average
number of comparisons in: 10 (search of "Hr") +9 (search
of " B ") +...+1 (search of " J ") the whole
divided by 10 (number of instructions) what corresponds in 5,5.
Now, let us realize a table containing the addresses of
each of these instructions classified in the alphabetical order:
|
Number of instruction
: 10
|
|
Address of the instruction " A "
|
|
Address of the instruction " B "
|
|
Address of the instruction " C "
|
|
Address of the instruction " D "
|
|
Address of the instruction " E "
|
|
Address of the instruction " F "
|
|
Address of the instruction " G "
|
|
Address of the instruction " H "
|
|
Address of the instruction " I "
|
|
Address of the instruction " J "
|
To find instruction " A ", my searching algorithm
is going to begin by seizing the number of instructions is 10.
It is going then to point at half of the table and to be so on
the address of the instruction " F ". The comparison
of the 2 character string is going to give a lower result in "
F ". It is going then to point at lower half of the table
is on the address of the instruction " C ". The even
lower being result of the comparison, the algorithm points then
known " B " then finally on " A ". This gives
a total number of 4 comparisons to compare with 7 for the previous
algorithm.
Let us make now the estimation of the average number of
comparisons: 4 (search of "A") +3 (search of "
B ") +2 (search of " C ") +4 (search of "
D ") +3 (search of " E ") +1 (search of "
F ") +4 (search for "G" ) 3 (search for "H"
) 2 (search for "I") 3 (" search of " J ")
the whole divided by 10 what corresponds in 2,9
( to compare in 5,5 of the previous
algorithm).
The notion of multiple vocabularies becomes so obsolete.
The doubling of the instruction number introduces only a supplementary
comparison!
