% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol}
% \usepackage{babel}
\usepackage{xspace}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

%\newcommand{\code}[1]{\texttt{#1}}
%\newcommand{\ret}{\textsf{$<$ret$>$}\xspace}
%\newcommand{\ret}{$\hookleftarrow$\xspace}

\renewcommand{\reftextbefore}{auf der vorherigen Seite}
\renewcommand{\reftextfacebefore}{auf der gegenüberliegenden Seite}
\renewcommand{\reftextafter}{auf der nächsten Seite}
\renewcommand{\reftextfaceafter}{auf der gegenüberliegenden Seite}
\renewcommand{\figurename}{Listing}

\begin{document}

\title{Von der virtuellen Forth–Maschine zum realen Forth–Prozessor}
\ifx\shorttitle\undefined\else
\shorttitle{Forth–VM und realer Forth–Prozessor}
\fi
\author{Willi Stricker}

\begin{document}
\maketitle

\begin{multicols}{2}
Zunächst sollen einige grundsätzliche Überlegungen zum Aufbau des Forth--Systems und zur virtuellen Forth--Maschine angestellt werden:

\section{Der Aufbau des Forth--Systems}

Das Forth--System besteht bekanntlich im Gegensatz zu anderen Programmiersprachen aus mehreren Komponenten:

\begin{itemize}
\item Virtuelle Forth--Maschine (Forth Virtual Machine)
\item Programmiersprache
\item Betriebssystem
\end{itemize}

\section{Die virtuelle Forth--Maschine}
In der Praxis wird die virtuelle Forth--Maschine aufbauend auf einem  beliebigen Mikroprozessor per Software erzeugt. Sie ist, zumindest theoretisch, für alle Mikroprozessoren identisch und bildet eine einheitliche Schnittstelle zwischen der Hardware (unterlagertem Mikroprozessor) und der darauf aufbauenden Programmiersprache Forth.

Die Kombination der individuellen Mikroprozessor--Hardware mit der Software--erzeugten virtuellen Forth--Maschine soll im folgenden als \emph{virtueller Forth--Prozessor} bezeichnet werden. 

\section{Der reale Forth--Prozessor}
Es ist naheliegend, die Kombination aus (Mikro--) Prozessor und Software und damit den virtuellen Forth--Prozessor ausschließlich in Hardware ohne zusätzliche Software direkt zu erstellen, etwa mit Hilfe der heute verfügbaren programmierbaren Logik--Bauelemente (z.$\,$B.\ FPGAs). Das wäre dann ein realer Forth--Prozessor. Um dessen Eigenschaften zu ermitteln, müssen zunächst die Unterschiede zwischen der virtuellen Forth--Maschine und einem \emph{normalen} Mikroprozessor üblicher Bauart und Struktur betrachtet werden. Es sind im Wesentlichen 2 Merkmale:

\begin{enumerate}
\item Anstelle der üblichen Register gibt es einen Parameter--Stack.
\item Jeder Befehl ist eine Adresse (und umgekehrt).
\end{enumerate}
	
Der virtuelle Forth--Prozessor und damit das Forth--Software--System kennt 2 Arten von Befehlen:
\begin{enumerate}
\item \textbf{Primitives:}\\ 
Befehle, die in Assembler--Code geschrieben sind. Sie entsprechen den Maschinen--Befehlen (Assembler--Befehlen) bei einem üblichen Prozessor
\item \textbf{High--Level--Befehle:}\\
Befehle, die in Forth geschrieben sind (aus Primitives zusammengesetzte Befehle). Sie entsprechen den Unterprogrammen bei üblichen Prozessoren.
\end{enumerate}

Wie oben erwähnt, sind beide Befehlsarten im Forth--System durch Adressen im Programm gekennzeichnet und werden durch ihre Adressen aufgerufen.

Die virtuelle Forth--Maschine enthält einen \emph{inneren Interpreter}\/, meist als \emph{NEXT-Routine} bezeichnet. Er dient als \emph{Programm--Weiterschalter} für beide Befehlsarten. Zur Unterscheidung benötigen die Befehle deswegen einen Befehls--Vorsatz (Instruction Prefix) in Form einer (Unter--) Programm--Adresse. Bei Primitives ist der Befehls--Vorsatz die  Adresse des eigenen (Assembler--) Programms, bei High--Level--Befehlen ist er die Adresse eines kleinen Unterprogramms (meist als \emph{DOCOL-Routine} bezeichnet), das anstelle eines Call--Befehls das Speichern der Return--Adresse auf dem (Return--) Stack übernimmt. Die High--Level--Befehle werden durch einen Return--Befehl (\texttt{;S} =  \emph{SEMIS--Routine}) abgeschlossen, der den Rücksprung ins aufrufende Programm bewirkt, d.$\,$h.\ das Rückladen der Return--Adresse vom (Return--) Stack und den Rücksprung auf diese Adresse.

Eine Besonderheit folgt daraus: \textbf{Es gibt keinen expliziten Call--Befehl!}
	
Die virtuelle Forth--Maschine macht keinerlei Aussagen über Hardware--Eigenschaften. Das betrifft insbesondere das Interrupt--System. In der Praxis wird hierbei auf die  Hardware des benutzten (Mikro)--Prozessors zurückgegriffen. Das gilt letztlich aber auch für alle gängigen Programmiersprachen.  

\section{Forderungen an einen realen Forth--\\Prozessor}
Der reale Forth--Prozessor soll so weit wie möglich die gleichen Eigenschaften besitzen, wie der virtuelle Forth--Prozessor. Außerdem muss er über die notwendigen Hardware--Eigenschaften eines Mikro--Prozessors verfügen.

\section{Praktische Realisierung eines realen Forth--Prozessors}
Im Folgenden soll eine Realisierungsmöglichkeit gezeigt werden, die sich möglichst nah an die vorgenannten Forderungen hält.

Er erhält die Bezeichnung: \textbf{STRIP} (\textbf{ST}ack \textbf{R}elated \textbf{I}nstructions \textbf{P}rocessor)

Er besitzt die folgende Hardware--Ausstattung:

\begin{itemize}
\item Je einen separaten Parameter-- und Return--Stack,
\item ein Interrupt Interface,  
\item die Möglichkei interne und/oder externe Speicher anzuschließen
\item die Möglichkeit interne und/oder externe I/Os anzuschließen
\end{itemize}

Er benötigt lediglich 3 Pointer--Register:
\begin{enumerate}
\item Parameter--Stack--Pointer: \textbf{SP}
\item Return--Stack--Pointer: \textbf{RP}
\item Instruction--Pointer: \textbf{IP}
\end{enumerate}

Darüber hinaus besitzt er keine weiteren Pointer oder Register (insbesondere auch kein Flag--Register)!

\section{Befehlssatz:}
Es wird ein \textbf{Minimal--Befehlssatz} vorgesehen, der nach folgenden Kriterien ausgewählt wird:
\begin{itemize}
\item Er soll alle diejenigen Befehle enthalten, die für den Aufbau eines Forth--Systems zwingend erforderlich sind.
\item Er soll zusätzliche Befehle enthalten, die für die Hardware--Steuerung erforderlich sind. 
\end{itemize}

\subsection{System--Befehle (Befehle, die nur vom Compiler benutzt werden):}
\begin{small}
\begin{tabular}{llp{12cm}}
\texttt{;S}	 & ( -> )      & Return = pop address from \\
                 &             & return stack and store to IP\\
\texttt{LIT}	 & ( -> data ) & Load immediate data on stack\\
\texttt{BRANCH}  & ( -> )      & Branch to the following address\\
\texttt{?BRANCH} & ( data -> ) & Branch to the following address \\
                 &             & if data equals zero, else continue\\
\end{tabular}
\end{small}

\subsection{Indirekter Befehls-- und Unterprogramm--Aufruf}
\begin{tabular}{llp{12cm}}
\texttt{EXECUTE}  &  ( address -> ) & Execute address \\
                  &                 & (on top of stack) \\
\end{tabular}

\subsection{Zugriff auf den Parameter-- und den Return--Stackpointer:}
\begin{tabular}{llp{12cm}}
\texttt{RP@}      &      ( -> RP )  & get RP  \\
\texttt{RP!}      &        ( RP -> ) & store RP \\
\texttt{SP@}      &      ( -> SP )  & get SP \\
\texttt{SP!}      &         ( SP -> ) & store SP \\
\end{tabular}

\subsection{Return--Stack manipulation:}
\begin{tabular}{llp{12cm}}
\texttt{R>}       &         ( -> data )  & pop data from return stack \\
\texttt{>R}       &         ( data -> )  & push data to return stack \\
\end{tabular}

\subsection{Parameter--Stack manipulation (wahlfreier Zugriff auf den Parameter--Stack):}
\begin{tabular}{llp{12cm}}
\texttt{DROP}     &     ( data -> )             & drop data from stack \\
\texttt{PICK}     &       ( position -> data )  & load data from relative \\
                  &                             & stack position \\
\texttt{-PICK}    &       ( data position -> )  & store data on relative\\
                  &                             & stack position \\
\end{tabular}

\subsection{Speicher--Zugriff:}
\begin{tabular}{llp{12cm}}
\texttt{@}        &         ( address -> data )  & fetch data from memory \\
                  &                              & address  \\
\texttt{!}        &         ( data address -> )  & store data on memory\\
                  &                              & address  \\
\end{tabular}

\subsection{Logische Funktionen:}
\begin{tabular}{llp{12cm}}
\texttt{INVERT}  &         ( data -> result )         & bitwise NOT \\
\texttt{AND}     &         ( data1 data2 -> result )  & bitwise AND  \\
\texttt{OR}      &         ( data1 data2 -> result )  & bitwise OR \\
\end{tabular}

\subsection{Arithmetische Funktionen:}
\begin{tabular}{llp{12cm}}
\texttt{+C}       & ( data1 data2 -> result carry ) & \\
                  & add data1 to data2 with sum and carry (lsb) & \\
\texttt{U2/C}     &       ( data -> carry result )          & \\
                  & shift right one bit, with result and carry (msb) & \\
\end{tabular}

\subsection{Spezielle Byte--Befehle:}
\begin{tabular}{llp{12cm}}
\texttt{CSWAP}   & ( byte1|byte2 -> byte2|byte1) & \\
                 & swap bytes in data & \\
\texttt{C@}      & \multicolumn{2}{l}{( address -> 0|byte )\ fetch byte from address} \\
                 & \multicolumn{2}{l}{(upper byte = 0)} \\
\texttt{C!}      & \multicolumn{2}{l}{( byte address -> )\  store byte to address}  \\ 
                 & \multicolumn{2}{l}{(only lower byte, upper byte is discarded)} \\
\end{tabular}

\subsection{Prozessor Steuerungs--Befehle (Interrupt--Befehle)}
\begin{tabular}{llp{12cm}}
\texttt{DISINT}      &   ( -> ) & Disable Interrupts \\
\texttt{ENINT}       &   ( -> ) & Enable Interrupts \\
\end{tabular}
\bigskip

In der Summe sind das lediglich 26 Befehle! Mit ihnen lässt sich gemäß obiger Vorgabe ein vollständiges Forth--System aufbauen (siehe dazu den Artikel in der VD Nr.3/2009). Hinweis: Einige der Befehle sind in Forth nicht definiert oder nicht üblich. 

Für den realen Forth--Prozessor ergeben sich aus der Hardware--Realisierung zwei Besonderheiten gegenüber dem virtuellen Forth--Prozessor. 

\begin{enumerate}
\item \textbf{Kein Befehls--Vorsatz}\\ 
Wie vorher beschrieben, benötigt die virtuelle Forth--Maschine den Befehls--Vorsatz (Instruction Prefix, erste Adresse im Code Field), um durch die NEXT--Routine die Unterscheidung zwischen Primitives und High--Level--Befehlen vorzunehmen.

Dieser Weg ist im realen Forth--Prozessor wenig sinnvoll, denn
es wird zusätzlicher Speicherplatz benötigt (mehr Speicherbedarf),
es ist ein zusätzlicher Speicherzugriff nötig (längere Laufzeit).

Der reale Forth--Prozessor verzichtet deswegen auf den Befehls--Vorsatz, er muss dann aber die Befehlsart an der Programmadresse erkennen. Da die Primitives ohnehin keine realen Adressen besitzen, werden dafür Pseudo--Adressen festgelegt, für die ein reservierter Adressbereich vorgesehen wird. Dort  können dann zwar keine High--Level--Programme liegen, wohl aber Speicher-- oder IO--Adressen.

\item \textbf{Return--Bit}\\
Jede Code--Adresse ist eine gerade Adresse (bei 16-- oder 32--Bit--Systemen). Damit ist das ganz rechts stehende Bit (LSB = least significant bit) immer null! Folglich kann dieses Bit für eine zusätzliche Information benutzt werden, in diesem Fall als \emph{Return--Bit}\/! 

Das Return--Bit bewirkt, dass zusätzlich zum gerade ausgeführten Befehl ein Return durchgeführt wird. Das gilt unabhängig davon, ob der Befehl ein Primitive-- oder ein High--Level--Aufruf ist. In einem Unterprogramm (High--Level--Befehl) bekommt dann der letzte Befehl ein Return--Bit. Damit entfällt der explizite Return--Befehl. 

\end{enumerate}

Da es beim Programmieren jedoch Situationen gibt, die einen expliziten Return--Befehl erfordern, wird in dem vorher definierten Befehlssatz an dessen Stelle ein neuer Befehl eingefügt (NOP = no operation) und der Return wird durch einen NOP--Befehl mit Return--Bit ersetzt.

\begin{tabular}{llp{12cm}}
\texttt{NOP} & ( -> ) & No Operation\\
\end{tabular}

Folgende Sonderfälle erfordern einen Return--Befehl (mit Adresse):

\begin{enumerate}
\item \textbf{Trivialfall:}\\
Ein Unterprogramm muss mindestens einen Befehl enthalten, auch dann, wenn es nichts bewirkt. Es muss also mindestens der Return--Befehl vorhanden sein.

\item \textbf{Strukturen (Sprung--Befehle):}\\
Ein Sprung--Befehl erfordert immer eine gültige Sprung--Adresse, an der zwangsläufig ein Befehl stehen muss. Wenn aber der Sprung an das Ende eines Unterprogramm erfolgen soll, ist dort kein Befehl mehr vorhanden, so dass dort ein NOP (mit Return--Bit) stehen muss.   
\end{enumerate}

\section{Praktische Ausführung des STRIP--Forth--Prozessors}
Oberstes Ziel bei der Realisierung des Prozessors ist selbstverständlich eine möglichst hohe Ablauf--Geschwindigkeit. Um dieses Ziel zu erreichen, wird soviel wie möglich parallel verarbeitet. Eingeschränkt wird der Programmablauf lediglich durch die Zugriffe auf externe Speicher. Diese bestimmen damit den  Mindest--Zeitablauf. Im Idealfall sollten deswegen möglichst wenige Buszugriffe erfolgen. 

\subsection{Stack--Zugriff:}
Die Stacks sind physikalisch getrennt vom Arbeitsspeicher untergebracht. Sie sind deswegen nur über die Stack--Befehle zugreifbar. Dadurch hat der Prozessor aber zeitgleich Zugriff auf beide Stacks und auf den  Programm-- oder Daten--Speicher.  

\section{Der STRIP--Kernel}
Er enthält 3 Pointer, deren Steuerung, sowie die die gesamte Befehlsverarbeitung. Er benötigt ein Clock--Signal und besitzt Schnittstellen für den Parameter-- und den Return--Stack sowie ein Interrupt--Interface, außerdem Daten-- und Adressbusse für Speicher und Peripherie.  

Der Kernel wird erweitert zu einem lauffähigen Prozessor durch Anfügen eines Clock--Elements, Parameter-- und Return--Stack sowie eines Reset/Interrupt--Controllers.

Ein vollständiges lauffähiges STRIP--Forth--System benötigt dann noch RAM (bzw ROM) für Daten und Programme sowie eine Programmier-- und Debug--Schnittstelle. Zusätzlich können nach Bedarf Ein-- und Ausgabe--Elemente angefügt werden. 

\section{Zeitablauf (Timing)}
Ein Clock--Zyklus ist identisch mit einem Buszugriff. Er besteht aus 2 Zuständen (States) S0 und S1:
\begin{enumerate}
\item S0 = Fetch State (Befehls--Zugriff)
\item S1 = Execute State (Befehls--Ausführung)
\end{enumerate}
Wie eingangs erwähnt, ist der Kernel so konstruiert, dass die Befehle nur so viele Clock--Zyklen brauchen, wie sie Buszugriffe benötigen (Ausnahmen siehe später). Daraus folgt, dass der Bus (fast) immer im Betrieb ist. Es gibt deswegen keine Pipelines oder Ähnliches.
 
Der Unterprogramm--Aufruf und die meisten Primitives  benötigen nur \textbf{einen Buszugriff}.
Zwei Buszugriffe benötigen lediglich:
\begin{itemize}
\item Befehle, die einen Operanden nachladen müssen: \texttt{LIT}, \texttt{BRANCH}, \texttt{?BRANCH}
\item Befehle, die einen Speicherzugriff vornehmen: \texttt{@}, \texttt{!}, \texttt{C@}, \texttt{C!}
\item Befehle, die mit Return--Bit einen zweiten Zyklus benötigen: \texttt{R>} mit Return, \texttt{RP!} mit Return
\end{itemize}

\subsection{Anmerkungen:}
Befehle mit Operanden benötigen zwei Programm--Speicherplätze, Befehle mit Speicherzugriff dagegen nur einen. Enthält der Befehl ein Return--Bit, dann ist \textbf{kein zusätzlicher Buszugriff} nötig, d.$\,$h., der Return--Befehl benötigt keine zusätzliche Zeit! Ausnahmen sind lediglich die Befehle \texttt{RP!} und \texttt{R>}, sie benötigen dann wegen des doppelten Zugriffs auf den Return--Stack einen zweiten Zyklus für den Reset (ohne Buszugriff).

\section{Befehlsablauf:}
\subsection{Standard--Befehle mit nur einem Buszugriff:}
S0: Laden des Befehlscodes\\
S1: Ausführen des Befehls

\subsection{Befehle mit einem Operanden (2 Buszugriffe):}
\begin{enumerate}
\item Zyklus: \\
S0: Laden des Befehlscodes\\
S1: Interne Bearbeitung\\
\item Zyklus: \\
S0: Laden des Operanden \\  
S1: Ausführen des Befehls\\
\end{enumerate}

\subsection{Befehle mit Speicherzugriff (2 Buszugriffe):}
\begin{enumerate}
\item Zyklus:\\
S0: Laden des Befehlscodes\\  
S1: Vorbereiten des Datentransfers\\
\item Zyklus:\\
S0: Ausgabe der Speicheradresse\\  
S1: Ausführen des Datentransfers\\
\end{enumerate}

\subsection{Befehle \texttt{R>} und \texttt{RP!} mit Return--Bit (ein Buszugriff)}
\begin{enumerate}
\item Zyklus:\\
S0: Laden des Befehlscodes\\
S1: Ausführung des Befehls\\
\item Zyklus: (Bus inaktiv)\\
S0: keine Aktion  \\
S1: Ausführen des Return--Befehls\\
\end{enumerate}

\section{Pseudo--Primitive--Adressen}
Bei der virtuellen Forth--Maschine liegen die Primitive--Befehle als Assembler--Code auf normalen Speicheradressen. Beim STRIP--Forth--Prozessor werden, wie vorher beschrieben, dafür \emph{Pseudo--Adressen} definiert. Das sind Adressen, unter denen die Primitives aufgerufen werden. Diese Adressen stehen dann für High--Level--Befehle (Unterprogramme) nicht zur Verfügung, können aber für Speicher und I/O--Adressen benutzt werden. Die Pseudo--Primitive--Adressen werden deshalb in einen Bereich gelegt, der außerhalb des Programmspeichers liegt. Es ist sinnvoll, sie an den Anfang der Memory Map (bei Adresse 0 beginnend) zu legen.

Bei den 26 benötigten Basis--Befehlen werden entsprechend 26 Adressen belegt, bei einem 16--Bit--System demgemäß 52 Bytes. In der Praxis werden dafür 64 ($2^6$) Bytes  reserviert.

\section{Restart und Interrupts}
Für den Restart wird im Programmspeicher ein Speicherplatz definiert. Er enthält die Restart--Adresse.
Für die Interrupts wird ebenfalls je ein Speicherplatz reserviert. Er enthält jeweils die Startadresse des zugehörigen Interrupt--Service--Programms. 

Der Restart ist ein durch Hardware ausgelöster Primitive--Befehl. Er benötigt einen Buszugriff (Laden der Restart--Adresse) und damit einen Clock--Zyklus.

Ein Interrupt wird hardwareseitig asynchron ausgelöst. Er wird vom Kernel in S0 abgefragt (falls es nicht der 2. Zyklus eines 2--Zyklen--Befehls ist) und muss dann den gleichfalls eingelesenen Befehl abwarten (ein oder 2 Clock--Zyklen), danach wird das zugehörige Interrupt--Programm ausgeführt.

\section{Schlussbemerkung zur praktischen Realisierung}
Der STRIP--Forth--Prozessor wurde zunächst in einem FPGA der Firma Actel auf einem Eval--Kit programmiert (Typ APA 075). Der Baustein enthält 3075 Tiles (kleine Logikeinheiten mit 3 Eingängen und einem Ausgang), dazu RAM--Blöcke mit insgesamt 3 kByte RAM. Das reicht gerade für die experimentelle Realisierung eines STRIP--Systems als 16--Bit--Version zur erfolgreichen Funktionsprüfung. Ein STRIP--Forth--System auf einem größeren Board mit RAM und Flash--ROM ist in Arbeit.

Eine detaillierte Beschreibung für einzelne Baugruppen, wie etwa Hardware--Komponenten, die Interrupt--Organisation oder das Bootprogramm für die Programmier-- und Debug--Schnittstelle, soll in weiteren Artikeln folgen.

\end{multicols}

\vfill
\begin{center}
\includegraphics[width=0.8\textwidth]{2010-04/actel-pro-asic-plus-arch}\\
\end{center}

\hspace*{4.3cm}Architektur der Aktel APA-FPGAs\hfill\\
\hspace*{6.5cm}{\tiny Quelle: Actel}\hfill
\vfill

\end{document}
