FPGA und CRISC

Autor: Andre Adrian
Version: 22.Apr.2011

Einleitung

Die Grenze zwischen Hardware und Software verschwimmt bei einem Field Programable Gate Array. Zur Zeit der 7400 ICs wurde die Hardware eines Gerätes durch die Verdrahtung von Logikbausteinen erzeugt. Eine Aufzugsteuerung kann heute noch mit solchen Bausteinen zusammengelötet werden. Die Mikroprozessoren und Mikrocontroller erhöhten die Komplexität der Logikbausteine gewaltig. Der ZX81 von Sinclair bestand aus vier ICs, dem Mikroprozessor Z80, einem 8 KByte ROM, einem 1 KByte RAM und einem speziell für Sinclair gefertigten Logikbaustein als "Glue-Chip". Ein solcher ASIC Baustein rechnet sich nur für Massenprodukte. Für Kleinserien entstanden programmierbare Logikbausteine. Der Autor hat schon vor über 20 Jahren solche EPLD Logikbausteine von Altera benutzt. Die ICs hatten ein 20 poliges DIL Gehäuse aus Keramik mit einem Quarzglas-Fenster. Für die Programmierung wurde EPROM Technik verwandt. Programmiert wurden die ICs in einem speziellen Gerät, einem EPLD Programmer, gelöscht wurde mit UV-Licht.
Heute erreichen die Nachfolger dieser programmierbaren Logikbausteine erstaunliche Leistungen. Es ist kein Problem einen kompletten Sinclair ZX Spectrum oder Commodore C64 Homecomputer mit einem FPGA zu emulieren. Wenn für Digitale Filter die Rechenleistung eines DSP nicht genügt, wird heute der DSP durch ein FPGA ersetzt..

Altera EP 310 pinout

Bilder links und rechts: Altera EP310 EPLD. Bilder aus Altera Datenblatt.

Inhaltsverzeichnis


Altera FPGA Entwicklungsboard

Die Firmen Altera und Xilinx sind heute wie vor 20 Jahren wichtige Spieler im FPGA Geschäft. Beide Unternehmen bieten Entwicklungsboards auf denen ein FPGA Baustein mit zusätzlichem Speicher und Schnittstellen montiert ist. Der Autor suchte ein Entwicklungsboard mit Anschlussmöglichkeiten für Tastatur, Bildschirm und Massenspeicher. Das Entwicklungsziel ist eine Forth-CPU zu entwickeln, dann einen Forth-Computer. Als Tastatur soll eine Cherry Miniatur-Tastatur mit PS/2 und USB Anschluss benutzt werden. Als Bildschirm ist ein LCD vorgesehen. Kleine LCDs mit z.B. 128x64 Pixel Auflösung werden über eine 8-Bit Schnittstelle angesteuert und können oft nur alphanumerische Zeichen anzeigen. Mittelgrosse LCDs mit z.B. 320x240 Pixel Auflösung haben eine 18-Bit oder 24-Bit Schnittstelle mit jeweils 6-Bit oder 8-Bit Auflösung pro Grundfarbe Rot, Grün, Blau. Grössere LCDs mit z.B. 1024x768 Pixel Auflösung verwenden eine VGA oder DVI Schnittstelle. Als Massenspeicher für den Forth-Computer ist eine Speicherkarte vorgesehen, keine Festplatte.
Ausgewählt wurde das Altera DE1 Board. Dieses Board ist auch als Cyclone II FPGA Starter Development Kit DK-CYCII-2C20N bekannt. Im Terasic Online-Shop kostet das DE1 Board 150 US-Dollar plus 52 US-$ Versandkosten. Das Board hat Anschlüsse für PS/2 Tastatur, VGA und SD Card. Daneben sind noch RS 232 und Audio mit Line Out, Line In und Mic In vorhanden. Die Programmierung erfolgt über USB. Auf die 40 poligen Pfostenstecker JP1 und JP2 passen die Anschlusskabel für IDE Festplatten.
Neben dem DE1 Entwicklungsboard gibt es das DE0 Entwicklungsboard. Für 119 US-Dollar erhält man eine Cyclone III FPGA. Es fehlen gegenüber dem DE1 der Audio Teil und das SRAM. Die RS232 Schnittstelle ist vorhanden, eine RS232 Buchse muss selbst angelötet werden. Am PS/2 Port kann über ein Y-Kabel eine Tastatur und eine Maus angeschlossen werden.
Achtung: Die automatische Treiber-Installation von MS-Windows XP ist nicht mehr aktiv. Hier steht die Anleitung zur USB-Blaster Treiber Installation.

Altera DE1 board
Bild : Altera DE1 Board von Terasic, wird auch als DK-CYCII-2C20N von Altera vertrieben.


Xilinx FPGA Entwicklungsboard

In der gleichen Preisklasse wie das Altera Cyclone II Entwicklerboard liegt das Xiliny Spartan 3A Entwicklerboard HW-SPAR3A-SK-UNI-G. Der Spartan XC3S700A Chip hat 13,248 logic cells, der Altera EP2C20F484C7N hat 18,752 logic cells. Der Unterschied in logic cells, in 18 Bit x 18 Bit embedded multipliers oder in On-Chip RAM dürfte für viele Projekte unwichtig sein. Wichtiger ist die Schnittstellenausstattung. Das Xilinx Board hat einen Ethernet Anschluss und keinen SD Card Anschluss, das Altera Board hat einen SD Card Anschluss aber keinen Ethernet Anschluss. Wer die digitalen Ein- und Ausgänge der FPGA Chips nutzen will hat mit den zwei 40-poligen Pfostensteckern im 2,54mm Rastermaß des Altera Boards keine Probleme. Das Xilinx Board hat einen 100-poligen Stecker Hirose FX2-100P-1.27DS im 1,27mm Rastermaß, ein schwieriger Stecker für den normalen Elektronik-Bastler. Das Xilinx Board gibt es z.B. bei Trenz Electronic für knapp 190€. Trenz liefert auch eine Hirose Buchse.

Xilinx Spartan 3A board

FPGA Projekte

Für einen Anfänger ist es immer sinnvoll zuerst etwas nachzubauen bevor man zur eigenen Tat schreitet. Die folgenden Projekte will der Autor studieren, bevor er die CRISC CPU in VHDL beschreibt..

sopc_builder_tutorial

Die Altera Webseite enthält die PDF Dateien Introduction to the Quartus II Software, Introduction to the SOPC Builder und Altera Monitor Program. In diesen Tutorials wird eine NIOS II CPU mit FPGA On-Chip RAM, mit 8 Bit Eingängen (Schalter auf DE1 Board) und 8 Bit Ausgängen (LED auf DE1 Board) verbunden. Das Programm in NIOS II Assembler oder C ist auf "hello world" Niveau: Die Eingänge werden gelesen und auf die Ausgänge geschrieben.
Als Software unter MS-Windows oder Linux sind Quartus II Web Edition v10.1 Service Pack 1, Nios II Embedded Design Suite v10.1 und University Program Installer nötig.
Achtung: Die Dateinamen für die Altera Software sollen keine Leerzeichen enthalten. Deshalb die Software oder auch die eigenen Projekte nicht abspeichern unter C:\Dokumente und Einstellungen\...
Achtung: Die automatische Treiber-Installation von MS-Windows XP ist nicht mehr aktiv. Hier steht die Anleitung zur USB-Blaster Treiber Installation.
Das Tutorial "Introduction to the SOPC Builder" geht auf die Verdrahtung zwischen FPGA Baustein sowie Schaltern und LEDs nicht ein. Die PDF Datei DE1 Getting Started User Manual enthält die Information für den Quartus Pin Planner. Das folgende Bild zeigt die Pin-Belegung des DE1 Boards. Diese Information wird im Kapitel 4.1 benötigt im Schritt "connect inputs and outputs of the parallel I/O ports, as well as the clock and reset inputs, to the appropriate pins on
the Cyclone-series device".



MCPU

Von Tim Böscke gibt es MCPU - A minimal CPU for a CPLD auf OpenCores.org. Mit 70 Zeilen VHDL Quelltext ist diese 8 Bit CPU winzig. Für den Einstieg in die Welt der FPGA Soft-CPUs ist sie aber prima geeignet.

J1 Forth CPU

Von James Bowman stammt die J1 Forth CPU. Die Beschreibung dieser CPU in j1.v benötigt 200 Zeilen Verilog Quelltext, damit dürfte die J1 eine der einfachsten 16-Bit CPUs sein. Der Verilog Quelltext wurde für einen Xilinx Spartan III FPGA geschrieben. Die J1 Forth CPU arbeitet als Controller für die WGE100 Kamera auf einem Roboter.

uCLinux mit NIOS II CPU

Das Betriebssystem uCLinux arbeitet mit einer CPU ohne Memory Management Unit (MMU). Die NIOS II CPU ist eine 32 Bit CPU von Altera. Die Implementierung von NIOS II ist in FPGA. Das Altera Wiki beschreibt die Installation von uCLinux. Weiterhin gibt es das Altera Forum.Von System Level Solutions gibt es eine Anleitung um uCLinux auf dem Altera NEEK Board zu installieren. Die einfachste Installation erfolgt mit der Buch-DVD von Rapid Prototyping of Digital Systems: SOPC Edition.
Als Software unter MS-Windows oder Linux sind Quartus II Web Edition v9.1 with Service Pack 2, Nios II Embedded Design Suite, Version 9.1 und University Program Installer nötig. Das University Programm Paket enthält den SRAM Controller und PS/2 Controller für den SOPC Builder.



Bild: NIOS II Soft-CPU ohne MMU auf Altera DE1 Board aus dem Buch Rapid Prototyping of Digital Systems: SOPC Edition

Jupiter ACE in FPGA

Der Jupiter ACE wurde von den zwei Sinclair Entwicklern Richard Altwasser und Steven Vickers gebaut. Der ACE hatte 1 KByte Video RAM, 1 KByte Character RAM und 1 KByte Programm RAM. Die Programmiersprache war Forth, eine Besonderheit unter den Homecomputern. Von Roni gibt es den Jupiter Ace on FPGA. Die Z80 FPGA Emulation ist Z80SoC.

Commodore C64 in FPGA

Es scheint mehrere Commodore Homecomputer in FPGA Projekte zu geben. Von Peter Wendrich kommt FPGA64. Diese C64 Emulation läuft auf dem C-One Board.

ZX81 in FPGA

Auf Sourceforge gibt es das ZXGATE - Old Computers in new FPGAs Projekt. Neben dem ZX81 wird auch der Jupiter ACE und der Tandy TRS80 emuliert. Die ZXGATE Quelltexte erhält man über "Download GNU Tarball". Die Z80 FPGA Simulation ist T80.

ZX Sinclair in FPGA

Die ZX Sinclair Emulation stammt von Mike und läuft auf dem Altera DE1 Board.

CRISC CPU in FPGA

English abstract: The CRISC CPU is a Complex Reduced Instruction Set CPU. The CPU has 4 data registers 16 bit, 6 data registers 32 bit and 4 address registers 16 bit and 20 opcodes. Top execution speed is one instruction per clock cycle. The CPU can perform simple precision IEEE754 floating point calculations in software. A good compromise between FPGA real estate and (relative) high CPU speed is the top design goal. The first implementation is on Altera Cyclone II EP2C20. The floating point functions sin(), cos(), ... use the CORDIC algorithm. The CPU registers are designed to allow CORDIC implementation with minimum memory access, all CORDIC relevant data is kept in registers. It is planned to create a floating point Forth operating system/compiler for the CRISC CPU. Further it is planned to extend the LCC C compiler to support the CRISC CPU.

Der eine oder andere Homecomputer-Fan wird sich noch an die Diskussionen erinnern über das Thema 6502 oder Z80, welcher ist besser? Mit einem FPGA Baustein kann heute jeder seine CPU selbst entwickeln. Vielleicht eine CPU mit den Z80 Registern, aber mit dem Businterface des 6502? Oder eine Stackmaschine wie die NC4016 von Charles Moore? Oder eine minimale CPU wie die RCA1802, aber mit einem 16 Bit breiten Akkumulator? Wie wäre eine 68000 ähnliche CPU mit 32 Bit Datenregistern und 16 Bit Adressregistern?
Die CRISC CPU soll 8 Bit, 16 Bit und 32 Bit Daten verarbeiten können. Die CPU soll genügend viele Register besitzen um den CORDIC Algorithmus ohne Speicherzugriffe ausführen zu können. Die CPU muss eine Fließkommazahl nicht direkt verarbeiten. Eine IEEE754 Single Precision Fließkommazahl wird in eine signed Mantisse und in einen signed Exponenten zerlegt. Mantisse und Exponent werden zum Grossteil unabhängig voneinander verarbeitet. Zum Schluß werden signed Mantisse und signed Exponent wieder in eine IEEE754 Fließkommazahl zusammen gesetzt.
Die hier vorgestellte CRISC CPU gehört zur Klasse der CRISC CPUs. Diese modernen Complex RISC CPUs versuchen die Vorteile von CISC und RISC CPUs zu vereinen. Der Schwerpunkt liegt auf der Ausführung von in Hochsprachen wie C geschriebener Programme. Das Ziel des Autors mit seiner CRISC CPU ist ein schnelles CORDIC in Assembler und ein schnelles Fließkomma-Forth. Das Forth Betriebssystem, der Forth innere Interpreter und der Forth : Interpreter werden in Assembler geschrieben. Die weitere Forth Entwicklung findet dann in Forth selbst statt.

CORDIC Besonderheiten

Für Single Precision IEEE754 sind Additionen mit minimal 24 Bit Breite nötig. Eine Instruction mit shift um N Bits ist sinnvoll. Minimal ist neben dem 1 Bit shift ein 8 Bit shift vorzusehen. Der Taschenrechner HP-45 wird im US Patent 4001569 genau beschrieben. Dieser CORDIC Taschenrechner mit Postfix Eingabe enthält 7 Rechenregister. Die Register A, B, C werden für die drei CORDIC Variablen benötigt. Die Register D, E, F und M realisieren die Postfix Eingabe. Die Register enthalten Fließkommazahlen. Rechenoperationen können auf Teilen dieser Fließkommazahlen ausgeführt werden. Zählvariablen für den CORDIC Algorithmus sind im HP-45 Teil der Ablaufsteuerung und nicht Teil der Rechenregister.
Wird eine Fließkommazahl in signed Mantisse und signed Exponent unterteilt sind 2 Register pro Fließkommazahl nötig. Zusammen mit dem CORDIC Schleifenzähler sind 12 Register für den CORDIC Algorithmus nötig. Nicht jedes Register muss 32 Bit breit sein, es genügen 6 Register mit 32 Bit, bei den anderen Registern genügen 16 Bit. Eine Operation wie add zwischen short und long Registern ist nicht nötig.

CPU Blockschaltbild

Die Central Processing Unit oder Zentraleinheit war zuerst ein Schrank voller Relais. Die Relais wurden gegen Elektronenröhren ausgewechselt, dann gegen Transistoren. Die Transistoren wanderten in integrierte Schaltkreise. Durch die immer grössere Anzahl von Transistoren in einem IC wurde die Anzahl der ICs in einem Computer immer kleiner. Die Mikrocontroller enthalten CPU, ROM, RAM und IO-Bausteine in einem Chip. Das FPGA kann CPU, ROM, RAM und IO-Bausteine emulieren.
Für das CRISC-CPU Chip Layout ist wichtig: Die CRISC CPU soll wie eine RISC CPU einfache Instructions in einem Takt ausführen. Alle Speicherobjekte (Instructions, 16 Bit Datenwerte, 32 Bit Datenwerte) können an einer geraden oder an einer ungeraden Adresse beginnen, die Speicherobjekte müssen nicht aligned sein.
Das folgende Blockschaltbild zeigt die Datenpfade, Puffer, Latches und Register der CRISC CPU. In der CRISC CPU wird viel mit Tristate Ausgängen gearbeitet. Der Autor findet diesen Ansatz bei der Menge der Register zweckmässiger als eine Lösung mit Multiplexer. In der CRISC CPU gibt es sechs interne 16 Bit Busse, den left lower bus, den right lower bus, den left upper bus, den right upper bus, den left address bus und den right address bus. Die Busse werden mit LL-bus, RL-bus, LU-bus, RU-bus, LA-bus und RA-bus abgekürzt. Die beiden lower Busse versorgen die 16 Bit ALU und die 16 Bit Register R0 bis R3 und A0 bis A3 mit Daten.
Alle vier Busse versorgen die 32 Bit ALU. Die CRISC CPU ist intern eine echte 32 Bit CPU, auch wenn der externe Datenbus nur 16 Bit breit ist. Das Bus Interface der CRISC CPU arbeitet mit 8 Bit und 16 Bit Zugriffen wie die Motorola 68000. Liegen die Daten aligned vor, können in einem Takt 16 Bit Daten gelesen oder geschrieben werden. Sind die Daten nicht aligned, benötigt ein 16 Bit Zugriff zwei Speicherzugriffe und ein 32 Bit Zugriff drei Speicherzugriffe.



Bild: CRISC CPU Blockschaltbild

Registertypen

Die Variablentypen von Hochsprachen wie C werden auf CPU Register abgebildet. Wie bei C kann mit einer Typexpansion gearbeitet werden. Eine 8 Bit char Variable kann beim Laden in eine 16 Bit short Variable umgewandelt werden, genauso wie eine 16 Bit short in eine 32 Bit long. Für boolsche Operationen wie AND ist die Registerbreite in Bits egal, jedes Bit wird für sich berechnet. Bei arithmetrischen Operationen wie ADD haben die Bits eine gegenseitige Abhängigkeit.
Die Zeigervariablen in C werden auf Adressregister abgebildet. Für eine schnelle Programmausführung ist es sinnvoll die Adressregister mit autoincrement und autodecrement auszustatten. Der C Ausdruck r = *a++ wird dann in eine Instruction übersetzt.
Die Datentypen sind 8 Bit unsigned, 8 Bit signed, 16 Bit unsigned, 16 Bit signed, 32 Bit unsigned und 32 Bit signed. Die long Register können alle Datentypen aufnehmen, die short Register nur die ersten vier Datentypen.

LDW    R0,(A0)     ; Load 16 Bit Word nach R0 ohne Extend von der Adresse in A0
LDBS   R0,(A0)+    ; Load 8 Bit Byte mit Sign Extend von der Adresse in A0, postincrement A0
LDBZ   R0,-(A0)    ; predecrement A0, Load 8 Bit Byte mit Zero Extend von der Adresse in A0
LDW    -(A0),R1    ; predecrement A0, Store 16 Bit Word aus R1 auf die Adresse in A0
LDL    D0,(A0)     ; Load 32 Bit Long nach D0, von der Adresse in A0
LDWS   D0,(A0)     ; Load 16 Bit Word nach D0 mit Sign Extend, von der Adresse in A0
LDBS   R1,d(A0)    ; Load 8 Bit Byte nach R1 mit Sign Extend von der Adresse in A0 plus d

Für die CRISC CPU werden 4 Register R0 bis R3 mit 16 Bit Breite für boolsche und arithmetrische Operationen eingesetzt werden. 6 Register D0 bis D5 mit 32 Bit Breite werden für arithmetrische und shift Operationen eingesetzt. 4 Register A0 bis A3 mit 16 Bit Breite werden als Adressregister eingesetzt. Die CPU verfügt über 3 Rechenwerke (ALUs), ein 32 Bit Rechenwerk und zwei 16 Bit Rechenwerke. Hier ein Vergleich zwischen der CRISC CPU mit 14 Registern, der Motorola 68000 mit 16 Registern und der Intel 80386 mit 8 Registern:


 short Register
 long Register
 Adressregister
CRISC CPU
 R0 bis R3
 D0 bis D5
 A0 bis A3
68000
D0 bis D7
 A0 bis A7
80386
EAX, EBX, ECX, EDX ESP, EBP, ESI, EDI

Bemerkung: Die 68000 und 80386 long Register können auch für 8 Bit und 16 Bit Daten benutzt werden.

Instruction set

Die 20 Instructions der CRISC CPU wurden aus den Bedürfnissen der Hochsprache C an eine CPU abgeleitet. Die Instructions der bekannten CPUs 6502, Z80, 68000 und 80386 wurden betrachtet bei der Auswahl des CRISC Instruction set.

Name
 Klasse
 C
 Funktion
NOP
 Kontrolle
Erhöhe Program Counter um 1
RET
 Kontrolle
 return;
Rückkehr vom Unterprogramm
NOT
 Logik
 R0 = ~R0
 Bits invertieren, Einserkomplement bilden
NEG
 Arithmetrik D0 = -D0
 Vorzeichen wechseln, Zweierkomplement bilden
ASR
 Schiebe
 D0 >>= 1 oder D0 >>= 8
 Arithmetrisch rechts schieben, das Vorzeichen beim Schieben beibehalten
LSR
 Schiebe
 D0 >>= 1 oder D0 >>= 8 Logisch rechts schieben, die freiwerdene Stelle mit 0 füllen
SL
 Schiebe
 D0 <<= 1 oder D0 <<= 8
 Links schieben, die freiwerdene Stelle mit 0 füllen
RR
 Schiebe
Rechts rotieren mit Carry C >> D0 >> C
RL
 Schiebe
Links rotieren mit Carry C << D0 << C
AND
 Logik
 R0 &= R1
 UND Verknüpfung
OR
 Logik
 R0 |= R1
N,Z = f(0 | R0)
 ODER Verknüpfung
oder führe ODER Verknüpfung mit 0 aus um Flags zu setzen (entspricht TST)
XOR
 Logik
 R0 ^= R1
 EXKLUSIV ODER Verknüpfung
ADD
 Arithmetrik
 R0 += R1
R0 += 1
 Addiere Inhalt des zweiten Registers zum Inhalt des ersten Registers
oder addiere Konstante zum Inhalt des Registers (entspricht INC)
SUB
 Arithmetrik R0 -= R1
R0 -= 1
 Subtrahiere Inhalt des zweiten Registers vom Inhalt des ersten Registers
oder subtrahiere Konstante vom Inhalt des Registers (entspricht DEC)
CMP
 Arithmetrik
 N,C,V,Z = f(R0 - R1)
 Wie SUB, aber das Register wird nicht verändert, nur die Flags werden gesetzt
JMP
 Kontrolle
 goto X;
 Springe unbedingt
Jcc
 Kontrolle
 if (), while(), for()
 Springe bedingt in Abhängigkeit von cc
Scc
 Kontrolle
 R0 = f(N,C,V,Z)
 Lade Register mit -1 oder 0 in Abhängigkeit von cc
JSR
 Kontrolle
 func();
 Unterprogrammaufruf
LD
 Transport
Kopiere mit optionalen Sign Extend von Memory nach Register oder kopiere von Register nach Memory

CRISC CPU Assembler

Von Georg Heßmann gibt es das Pogramm assem: Ein konfigurierbarer Assembler. Dieser Assembler-Baukasten wird für den CRISC CPU Assembler genutzt. Der Assembler wandelt die Assembler Mnemonics wie LD und ADD mit ihren Parametern in binäre Zahlen um. Die Wandlung erfolgt zwischen der vom Programmierer benötigten Darstellung in die von der CPU benötigte Darstellung. Das assem Programm von 1995 entspricht nicht dem C Standard von 2011. Hier gibt es eine aktuelle assem Version.

Adressierungsarten

Die CRISC CPU kennt 11 Adressierungsarten. Einer RISC CPU sind meistens nur die Adressierungsarten Implied, Immediate, Register direct, Programm direct, Data direct und Data indirect bekannt. Eine CISC CPU kennt häufig mehr als die hier aufgeführten Adressierungsarten. Die Adressregister haben 16 Bit Breite, die Adressierung erfolgt Byte-weise. Die Program direct Adressierung arbeitet mit einer 16 Bit Adresse. Data und Program indirect Adressierung erfolgt über die Adressregister. Die Adressregister beherrschen Increment und Decrement um 1, 2 und 4. Push ist realisiert als Predecrement des Adressregisters und Store Register auf die vom Adressregister bestimmte Speicherzelle. Pop ist realisiert als Load Register von dem Inhalt der durch das Adressregister bestimmten Speicherzelle und Postincrement des Adressregisters. Eine weitere Form der Adressierung ist die indirekte Adressierung mit Offset. Die relative Adressierung kann nur bei Sprüngen benutzt werden, ein Unterprogrammaufruf benutzt immer die Program direct oder Program indirect Adressierung.

Adressierungsart
 C Beispiel
 Assembler
 Erklärung
Implied
 return;
 RET
 Rückkehr vom Unterprogrammaufruf ausführen.
Immediate r0 = 0xAFFE; LDW R0,#$AFFE
 Lade Register mit einer Konstanten.
Register direct
 r0 = r1;
 LDW R0,R1
 Lade Register mit dem Inhalt eines anderen Registers.
Program direct
 func();
 JSR func
 Unterprogrammaufruf zu einer anderen Stelle im Programm ausführen.
Program relative
 goto near;
 BRA near
 Sprung zu einer nahe liegenden anderen Stelle im Programm ausführen.
Program indirect
 (*a0)();
 JSR (A0)
 Unterprogrammaufruf zu der durch Register a0 bestimmten Stelle im Programm ausführen.
Data direct r0 = variable; LDW R0,variable
 Lade Register r0 mit dem Inhalt einer Speicherzelle.
Data indirect
 r0 = *a0;
 LDW R0,(A0)
 Lade Register r0 mit dem Inhalt der durch Register a0 bestimmten Speicherzelle.
Data predecrement indirect r0 = *--a0;
 LDW R0,-(A0)
 Erniedrige Register a0 um die Grösse der Speicherzelle. Lade Register r0 mit dem Inhalt der durch a0 bestimmten Speicherzelle.
Data postincrement indirect r0 = *a0++;
 LDW R0,(A0)+
 Lade Register r0 mit dem Inhalt der durch Register a0 bestimmten Speicherzelle. Erhöhe a0 um die Grösse der Speicherzelle.
Data offset indirect r0 = a0->offset;
 LDW R0,offset(A0)
 Lade Register r0 mit dem Inhalt der durch Register a0 plus offset bestimmten Speicherzelle. Offset ist eine Konstante.

Instruction Format

Der Entwurf von Instructions (Maschinensprache-Befehlen) verlangt einen Kompromis zwischen gegensätzlichen Zielen. In dem einen Extrem gibt es die Instructions der NC4016 Stackmaschine. Die 16 Bit Instructions steuern direkt das Rechenwerk. Bei der NC4016 können mehrere Forth Primitive in einer Instruction zusammengefasst werden. Das Forth Primitive für ; (Forth Funktion Return) benötigt in den meisten Fälle keine eigene Instruction. Ein anderes Beispiel ist lit SWAP -, hier wird in einer Instruction die 16 Bit Konstante lit auf den Datenstack gelegt, die beiden obersten Stackwerte vertauscht und zuletzt wird die Differenz der beiden obersten Stackwerte gebildet.
Das andere Extrem zeigt die 68000 von Motorola. Hier sind die Instructions so dicht gepackt, das eine zweistufige Dekodierung der Instructions erfolgt. Zuerst wird der Instruction zu einer Mikro-ROM Instruction dekodiert, dann noch zu einem Nano-ROM Instruction weiter dekodiert. Bei höheren Taktfrequenzen stellte sich diese umständliche Dekodierung als Schwachstelle heraus. Die dritte Variante von Instructions stellt der 8 Bit AVR dar. Mit 32 Registern ist der AVR eine RISC CPU. Die CPU beherrscht aber auch die indirekte Adressierung mit Decrement und Increment. Der AVR hat 16 Bit und 32 Bit Instructions. Unterschiedliche Instructionlänge ist typisch für CISC CPUs. Die CRISC CPU hat die Registernamen und Abkürzungen der Adressierungsarten von der Motorola 68000 übernommen und von der Intel 80386 die eingeschränkte 2-Adress Maschine und die Operanden-Schreibweise Ziel,Quelle. Einige Instruction-Namen wie LD stammen von der Zilog Z80. Neu bei der CRISC CPU sind die drei Registertypen short register, long register und Adressregister. Ebenfalls neu ist die direkte Beziehung zwischen Type-Feld-Inhalt und Instruction-Länge. Neu ist auch die systematische Benennung der Branch Instructions mit einem S für die signed number Versionen.

Gibt es Instructions unterschiedlicher Länge, muss der Instruction decoder die Länge des Instructions erkennen können. Bei der CRISC CPU besteht die Instruction aus den drei Teilen Type, Opcode und Parameter. Die Type Bits beschreiben die Länge des Instructions in Bytes, der Opcode beschreibt die Instruction und der Parameter liefert eine Konstante. Das Type-Feld beschreibt den Instruction-Type, die Schablone die benutzt wird um aus den Bits in der Instruction die Bits für das Rechenwerk abzuleiten. Dieser Aufbau der Instruction vereinfacht den Instruction decoder (Befehls-Dekoder). Nach der Untersuchung des ersten Instruction Bytes ist die Instruction Länge und die Dekodierschablone für die Instruction bekannt.
Das Type-Feld hat eine Länge von 3 Bits. Die Zuordnung Type-Feld zu Instruction Länge ist wie folgt:

1 Byte Instruction Control (nop, ret, ...)
 7 6 5 4 3 2 1 0
+-----+---------+
|0 0 0| Opcode  |
+-----+---------+

2 Byte Instruction Control (scc, Jump/Call Program indirect, ...)
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-----+-+-+---------+---+
|1 0 0|J| CC  |F|1| Opcode  |rg |
+-----+-+-----+-+-+---------+---+

2 Byte Instruction Jump/Call Program relative
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-----+-+---------------+
|0 0 1|J| CC  |F| 8 Bit constant|
+-----+-+-----+-+---------------+

3 Byte Instruction Jump/Call Program direct
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-----+-+-------------------------------+
|0 1 0|J| CC  |F|       16 Bit constant         |
+-----+-+-----+-+-------------------------------+

2 Byte Instruction ALU (and, add, shift, ...)
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-------+---+---+---+---+
|0 1 1|L|  ALU  |al2|rg2|al1|rg1|
+-----+-+-------+---+---+---+---+

2 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-+---+-----+---+
|1 0 0| sl1 |rg1|0|ext| sl2 |rg2|
+-----+-----+---+-+---+-----+---+

3 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-+---+-----+---+---------------+
|1 0 1| sl1 |rg1|0|ext| sl2 |rg2| 8 Bit constant|
+-----+-----+---+-+---+-----+---+---------------+

4 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-+---+-----+---+-------------------------------+
|1 1 0| sl1 |rg1|0|ext| sl2 |rg2|       16 Bit constant         |
+-----+-----+---+-+---+-----+---+-------------------------------+

6 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-----+-----+---+---------------------------------------------------------------+
|1 1 1| sl1 |rg1|0 0 0| sl2 |rg2|                      32 Bit constant                          |
+-----+-----+---+-----+-----+---+---------------------------------------------------------------+


Byte
 Type = 0
 Type = 1
 Type = 2
 Type = 3,4
 Type = 5
 Type = 6 Type =7
#1
 Opcode 1
 Opcode 1
 Opcode 1 Opcode 1
 Opcode 1
 Opcode 1 Opcode 1
#2
Parameter 1a Parameter 1a Opcode 2 Opcode 2
 Opcode 2 Opcode 2
#3

Parameter 2a
Parameter 1b
 Parameter 1b Parameter 1b
#4




Parameter 2b
 Parameter 2b
#5





Parameter 3b
#6





Parameter 4b

Load und Store Instruction Format

Die CRISC CPU hat folgende Einschränkung gegenüber einer 2-Adress Maschine: In einem Instruction ist nur ein Speicherzugriff möglich. Der C Ausdruck r0 = r1 wird in eine Instruction übersetzt, das gleiche gilt für r0 = *a0 und *a0 = r0. Der Ausdruck *a0 = *a1 kann nicht in einen Instruction übersetzt werden. Ein bekannter Vertreter einer solchen eingeschränkten 2-Adress Maschine ist die x86 Architektur. Die Einschränkung vereinfacht die CPU. Das Ausdrücke der Art *a0 = *a1 durch zwei Instructions abgebildet werden verschlechtert kaum die CPU Leistung, weil diese Zuweisungen recht selten sind. Die Registerfelder rg1 und rg2 bestehen aus je 2 Bit. Von jedem Registertype gibt es 4 Register, deshalb 2 Bit. Das Select-Feld sl1 mit 3 Bit wählt für rg1 den Registertype oder die Adressierungsart aus (short register, long register, address register, data direct, data indirect, data predecrement indirect, data postincrement indirect, data offset indirect). Das Select-Feld sl2 wählt für rg2 den Registertype oder die Adressierungsart aus. Die Felder sl1 und rg1 gehören zum linken Operanten, die Felder sl2 und rg2 gehören zum rechten Operanten. Das Const-Feld ist entweder 8 Bit, 16 Bit oder 32 Bit lang, die Länge dieses Feldes wird durch das Type-Feld bestimmt. Das 2 Bit Extension-Feld ext bestimmt ob die untere Hälfte des Registers (8 Bit bei R Register und 16 Bit bei D Register) oder ob das ganze Register geladen oder gespeichert wird. Wird die untere Hälfte des Registers geladen, kann noch bestimmt werden ob keine Extension, zero Extension oder sign Extension stattfindet.

2 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-+---+-----+---+
|1 0 0| sl1 |rg1|0|ext| sl2 |rg2|
+-----+-----+---+-+---+-----+---+

3 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-+---+-----+---+---------------+
|1 0 1| sl1 |rg1|0|ext| sl2 |rg2| 8 Bit constant|
+-----+-----+---+-+---+-----+---+---------------+

4 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-+---+-----+---+-------------------------------+
|1 1 0| sl1 |rg1|0|ext| sl2 |rg2|       16 Bit constant         |
+-----+-----+---+-+---+-----+---+-------------------------------+

6 Byte Instruction Load/Store
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-----+---+-----+-----+---+---------------------------------------------------------------+
|1 1 1| sl1 |rg1|0 0 0| sl2 |rg2|                      32 Bit constant                          |
+-----+-----+---+-----+-----+---+---------------------------------------------------------------+



 rg1, rg2
 ext
0
 R0, A0, D0, D4
 full load/store
1
 R1, A1, D1, D5
 half load/store no extend
2
 R2, A2, D2, immediate
 half load/store zero extend
3
 R3, A3, D3, data direct
 half load/store sign extend



sl1, sl2
0
 R Register
1
 A Register
2
 D0..D3 Register
3
 D4, D5 oder Spezial
4
 data indirect
5
 data predecrement indirect
6
 data postincrement indirect
7
 data offset indirect


ALU Instruction Format

Das ALU Instruction Format besteht aus dem 1 Bit Feld L für die ALU Auswahl mit L = 0 ist 16-Bit ALU und L = 1 ist 32-Bit ALU. Die ALU Operation ist in dem 4 Bit Feld ALU kodiert. Die Register werden über die Felder al2, rg2, al1 und rg1 bestimmt. Der Instruction decode Aufwand ist gering.

2 Byte Instruction ALU (and, add, shift, ...)
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-------+---+---+---+---+
|0 1 1|L|  ALU  |al2|rg2|al1|rg1|
+-----+-+-------+---+---+---+---+


#
 L = 0 (R ALU)
 L = 1 (D ALU)
0
 no extend
 no extend
1
 zero extend
 zero extend
2
 sign extend
 sign extend
3
 +
 +
4
 -
 -
5
 NOT
6
 AND
 AND
7
 OR
8
 XOR
 SL,1,Zero fill
9
SL,8,Zero fill
10
LSR,1,Zero fill
11
LSR,8,Zero fill
12
ASR,1,Sign fill
13
ASR,8,Sign fill
14
RL
15
RR



rg1
 rg2
 al1, al2
0
 R0 oder D0 oder A0 oder D4
 R0 oder D0 oder A0 oder D4 R Register
1
 R1 oder D1 oder A1 oder D5
 R1 oder D1 oder A1 oder D5 D Register
2
 R2 oder D2 oder A2 oder 0
 R2 oder D2 oder A2 oder 1
 A Register
3
 R3 oder D3 oder A3
 R3 oder D3 oder A3 oder 2
 Mixed

Jump, JSR Instruction Format

Zwischen Strung und Unterprogrammaufruf wird mit dem 1 Bit Feld J unterschieden. Ein Jump wird bei J=0, ein Jump Subroutine bei J=1 ausgeführt. Das 3 Bit Feld CC (condition codes) und das 1 Bit Feld F bestimmen unter welcher Bedingung gesprungen wird.

2 Byte Instruction Control (scc, Jump/Call Program indirect, ...)
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-----+-+-+---------+---+
|1 0 0|J| CC  |F|1| Opcode  |rg |
+-----+-+-----+-+-+---------+---+

2 Byte Instruction Jump/Call Program relative
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-----+-+---------------+
|0 0 1|J| CC  |F| 8 Bit constant|
+-----+-+-----+-+---------------+

3 Byte Instruction Jump/Call Program direct
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-----+-+-------------------------------+
|0 1 0|J| CC  |F|       16 Bit constant         |
+-----+-+-----+-+-------------------------------+


CC
 Test
 if F = 0
 if F = 1
#0
 1
JMP
#1
 Z
 JNE
 JEQ
#2
 C
 JGE
 JLT
#3
 C | Z
 JGT
 JLE
#4
 N ^ Z
 SJGE
 SJLT
#5
 Z | (N ^ V)
 SJGT
 SJLE

Control Instruction Format

Zur Zeit sind NOP und RET die einzigen 8 Bit Befehle. Der Scc Befehl muss als 16 Bit Befehl implementiert werden.

1 Byte Instruction Control (nop, ret, ...)
 7 6 5 4 3 2 1 0
+-----+---------+
|0 0 0| Opcode  |
+-----+---------+

2 Byte Instruction Control (scc, ...)
 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
+-----+-+-----+-+-+---------+---+
|1 0 0|J| CC  |F|1| Opcode  |rg |
+-----+-+-----+-+-+---------+---+

Algorithmic State Machine

Die Beschreibung der Datenpfade einer CPU ist der erste Entwicklungsschritt. In der Programmierung entspricht dieser Schritt der Definition der Datenobjekte welche im Programm benutzt werden sollen. Die Datenobjekte ändern sich weniger als die Algorithmen, deshalb werden sie zuerst definiert. Der Programmablauf wird durch Algorithmen beschrieben. Die Algorithmic State Machine (Algorithmic-SM) aus der Hardware-Entwicklung ist sehr ähnlich zu den Flussdiagrammen der Programmierung. Die Flussdiagramme wurden zur strukturierten Programmierung weiterentwickelt, genauso kann eine Algorithmic-SM durch strukturierten Pseudocode beschrieben werden. In den Hardware-Entwufssprachen VHDL und Verilog wird genau dies getan.
Um die Hardware-Implementierung einer Algorithmic-SM zu besprechen wird die Realisierung in einem Mealy Automat besprochen. Der Mealy Automat reagiert auf seine Umwelt durch die Eingänge x1 bis x7. Die Umwelt erhält vom Mealy Automaten Anweisungen durch die Ausgänge y1 bis y10. Das Gedächtnis des Mealy Automaten steckt in den Speichern welche zwischen den internen Ausgängen d1 bis d3 und den internen Eingängen t1 bis t3 liegen. Die Reaktion des Mealy Automaten auf einen Reiz an den Eingängen x1 bis x7 hängt vom Zustand an den Eingängen t1 bis t3 ab. Diese Zustände ergeben sich aus der Vergangenheit, der Mealy Automat reagiert auf den gleichen Reiz nicht immer mit der gleichen Reaktion. Durch diese "Entscheidungsfreiheit" des Mealy Automaten wird die Fallunterscheidung realisiert. Die Zustände "Parameter fetch" und "Write back" werden nicht bei jeder Instruction benötigt. Im Speicher des Mealy Automaten wird durch ein Flag (1 Bit Speicherelement) festgehalten ob "Parameter fetch" benötigt wird. Ein weiteres Flag im Speicher bestimmt ob "Write back" nötig ist. In gleicher Weise wird in einem Flag gespeichert ob ein "non-aligned" Speicherzugriff nötig ist. Mehrere Flags werden benutzt um die verschiedenen nötigen Zustände bei der Instruction Ausführung durchzuzählen. Alle Instruction beginnen mit dem Zustand "Instruction fetch". Ein Opcode "ADD R0,R1" benötigt aber andere Folgezustände als ein Opcode "RET".
Die Umsetzung von VHDL oder Verilog Quelltext in FPGA Hardware erfolgt durch Programme der FPGA Hersteller. Welche Flags in der Algorithmic-SM benutzt werden liegt beim Designer. Eine gute Wahl der Speicherflags führt zu einem niedrigen Verbrauch von FPGA real estate (FPGA Logikgatter, FPGA Speicherzellen, FPGA Verbindungen).
Die Abkürzung ASM bedeutet neben Algorithmic State Machine auch Abstract State Machine oder Assembler. Die Benutzung von eindeutigen Begriffen wie Algorithmic-SM, Abstract-SM und Assembler steigert die Qualität der Diskussion.
Mealy State Machine
Bild: Mealy Automat aus dem Buch Logic and System Design of Digital Systems von Samary Baranov. Chapter 4 Algorithmic State Machines and Finite State Machines ist online lesbar.

Instruction States

Alle Instructions beginnen mit den States "Opcode fetch" und "Instruction decode". Das Detail 8 Bit Opcode oder 16 Bit Opcode und bei 16 Bit Opcodes das Detail aligned Zugriff oder non-aligned Zugriff wird durch Varianten des States "Opcode fetch" behandelt. In der CRISC CPU wird eine hierarchische Algorithmic-SM realisiert. Der State #0 "Opcode fetch" besteht aus Sub-States aus der Gruppe "Opcode fetch 1. Byte, aligned", "Opcode fetch 1. Byte, non-aligned", "Opcode fetch 2. Byte, non-aligned".

Instruction States Logik, Arithmetrisch, Schiebe

Alle Instructions beginnen mit den States "Opcode fetch" (state #0) und "Instruction decode" (state #1). Die Instructions der Gruppe Logik, Arithmetrik, Schiebe setzen die ALU Flags N (Negative), Z (Zero), C (Carry) und V (Overflow). Der Zustand der ALU Flags vor der Instruction hat keinen Einfluss auf die Instruction. Alle Instructions dieser Gruppe haben den gleichen Macro-State C. Die ALU kennt acht unterschiedliche Operationen, zwei Schiebe-Operationen, zwei arithmetrische Operationen und vier logische Operationen. Der state C hat sieben Micro-States, fünf für Operationen mit einem Parameter und zwei für Operationen mit zwei Parameter.

Name
 State #2
 State #2
NOT reg
 execute ALU=NOT
 #2.0.5: reg ~= reg
SL reg,1 execute ALU=SL,1,Zero fill #2.0.8: reg <<= 1
SL reg,8 execute ALU=SL,8,Zero fill #2.0.9: reg <<= 8
LSR reg,1 execute ALU=SR,1,Zero fill #2.0.10: reg >>= 1
LSR reg,8 execute ALU=SR,8,Zero fill #2.0.11: reg >>= 8
ASR reg,1
 execute ALU=SR,1,Sign fill
 #2.0.12: reg >>= 1
ASR reg,8 execute ALU=SR,8,Sign fill #2.0.13: reg >>= 8
RL reg
 execute ALU=RL #2.0.14: C << reg << C
RR reg execute ALU=RR #2.0.15: C >> reg >> C
TST reg
 execute ALU=OR #2.1.7: reg = 0 | reg
NEG reg execute ALU=SUB #2.1.4: reg = 0 - reg
ADD reg,1 execute ALU=ADD #2.2.3: reg += 1
ADD reg,2 execute ALU=ADD #2.3.3: reg += 2
SUB reg,1 execute ALU=SUB #2.4.3: reg += -1
SUB reg,2 execute ALU=SUB #2.5.3: reg += -2
AND reg1,reg2
 execute ALU=AND #2.6.6: reg1 &= reg2
OR reg1,reg2
 execute ALU=OR #2.6.7: reg1 |= reg2
XOR reg1,reg2
 execute ALU=XOR #2.6.8: reg1 ^= reg2
ADD reg1,reg2
 execute ALU=ADD #2.6.3: reg1 += reg2
SUB reg1,reg2 execute ALU=SUB #2.6.4: reg1 -= reg2
CMP reg1,reg2
 execute ALU=SUB #2.7.4: N,Z,C,V = reg1 - reg2


Die zweite Stelle von State #2 beschreibt die Anzahl der Parameter.

#
 Parameter
0
 Ein Register
1
 Konstante 0 und Register
2
 Register und Konstante 1
3
 Register und Konstante 2
4
 Register und Konstante -1
5
 Register und Konstante -2
6
 Zwei Register
7
 Zwei Register, Ergebnis verwerfen


Die dritte Stelle von State #2 beschreibt die ALU Operation. Die Belegung ist für die drei ALUs unterschiedlich.

#
 L = 0 (R ALU)
 L = 1 (D ALU)
 A ALU
0
 no extend
 no extend no extend
1
 zero extend
 zero extend
2
 sign extend
 sign extend
 sign extend
3
 +
 +
 +
4
 -
 -
5
 NOT

6
 AND

7
 OR

8
 XOR
 SL,1,Zero fill
9
SL,8,Zero fill
10
SR,1,Zero fill
11
SR,8,Zero fill
12
SR,1,Sign fill
13
SR,8,Sign fill
14
RL
15
RR

Instruction States Kontrolle

Während dem State #1 "Instruction decode" wird festgestellt ob ein bedingter Sprung ausgeführt wird oder nicht. Ist die Sprungbedingungen gegeben (Jcc true), verläuft ein Jcc wie ein JMP. Ist die Sprungbedingung nicht gegeben (Jcc false) wird die Zieladresse des Sprungs verworfen.

Name
 State #2
 State #3
 State #4
 State #5
Jcc false Program direct #2.8: Abus = PC; RD1, RD0 = DBus; PC += 2


JMP, Jcc true Program direct #2.8: Abus = PC; RD1, RD0 = DBus; PC += 2 #3.0: PC = RD1, RD0

JSR Program direct #2.9: Abus = PC; RD1, RD0 = DBus; PC += 2; A3 -= 2
 #3.2: Abus = A3; Dbus = WD1, WD0 = PC #4.0: PC = RD1, RD0
Jcc false Program relative #2.10: Abus = PC; RD0 = DBus; PC += 1


JMP, Jcc true Program relative #2.10: Abus = PC; RD0 = DBus; PC += 1 #3.1: JR = RD0,sign extend #4.2: PC += JR
JSR Program relative #2.11: Abus = PC; RD0 = DBus; PC += 1; A3 -= 2 #3.2: Abus = A3; Dbus = WD1, WD0 = PC #4.1: JR = RD0,sign extend #5.2: PC += JR
Jcc false Program indirect



JMP, Jcc true Program indirect #2.11: PC = Ax mit x=0..3;


JSR Program indirect #2.12: A3 -= 2 #3.2: Abus = A3; Dbus = WD1, WD0 = PC #4.3: PC = Ax mit x=0..3;
RET #2.13: Abus = A3; RD1, RD0 = Dbus; A3 += 2 #3.0: PC = RD1, RD0

Scc reg false
 #2.14: reg = 0;


Scc reg true
 #2.15: reg = NOT 0;



Instruction States Transport


Name
 Klasse
LD reg,reg
 Transport
LD reg,mem
LD mem,reg


Instruction
Load Register, Register
Load Register, Immediate
Load Register, Data direct
Load Register, Data indirect
Load Register, Data predecrement indirect
Load Register, Data postincrement indirect
Load Register, Data offset indirect

Nachlese

Die Nachlese enthält die Reste oder das Beste - es hängt davon ab was man sucht.

Instruction fetch

Der Datenbus einer von Neumann CPU erfüllt zwei Aufgaben. Einmal werden Instructions aus dem Programmspeicher in die CPU geladen. Zweitens werden Parameter aus dem Datenpeicher gelesen oder in den Datenspeicher geschrieben. Die Harvard CPU hat getrennte Busse für Programm- und Datenzugriff. Die CRISC CPU hat eine von Neumann Architektur.
Die Adresse des program counter (PC) mit Adressbit A0 = 0 wird auf dem Adressbus ausgegeben und 16 Bit an Daten werden vom Programmspeicher gelesen. Das A0 Bit des PC bestimmt ob das untere oder das obere Byte (8 Bit Datum) des gelesenen word (16 Bit Datum) der Beginn der Instruction ist. Anhand der Instruction type erkennt die Instruction fetch Logik wieviele weitere words zu lesen sind um die komplette Instruction in das Instruction register zu laden. Im Instruction register sind 3 Bits für den Instruction type, 13 Bits für den Opcode und 32 Bits für den Parameter vorgesehen, insgesamt 48 Bits. Aus dem Opcode im Programmspeicher mit variabler Länge von 8 Bits oder 16 Bits wird im Opcode FIFO ein harmonisierter Opcode mit 16 Bits Länge.
Die Stufen Instruction fetch und Instruction decode sind über einen First in First Out (FIFO) Pufferspeicher verbunden. Der FIFO hat mindestens zwei Speicherplätze für harmonisierte Instructions. In den einen Speicherplatz schreibt die Instruction fetch Stufe die neueste Instruction, aus dem anderen liest die Instruction decode Stufe.
Der Instruction fetch erfolgt bei einer RISC CPU in einem CPU Takt. Während der clock Φ1 High-Phase wird der Inhalt des PC Registers auf den Adressbus ausgegeben. In der clock Φ2 High-Phase wird der Inhalt des Datenbusses in den Instruction buffer übernommen. Als buffer wird ein pegel gesteuertes D Latch (level triggered D latch) benötigt. Für RISC CPUs sind pegel gesteuerte Latches üblich. Für CISC CPUs mit ihren klassischen Mealy und Moore Automaten sind flanken gesteuerte Latches üblich.
Hades, das Hamburg Design System, enthält die Simulation eines two-phase clock generator. Die 6502 CPU benötigte einen solchen nicht-überlappenden Zwei-Phasen Takt, auch NORA (NO RAce) Takt genannt. Schnelle moderne CPUs arbeiten mit True Single Phase Clock (TSPC). Der invertierte clock wird lokal mit einem Inverter erzeugt, es werden nicht mehr zwei clock Leitungen durch das IC gezogen.
6502 memory fetch

Bild links: von oben nach unten: pegelgesteuerter Latch, positive Flanke gesteuerter Latch, negative Flanke gesteuerter Latch, siehe EE200 Digital Logic Circuit Design.
Bild rechts: 6502 CPU Memory fetch in einem Zyklus (Takt) aus dem Synertek Hardware Manual. Die High-Phase von Φ1 löst die Ausgabe des Lese/Schreibsignals und die Ausgabe der Adresse auf den Adressbus aus. Die High-Phase von Φ2 löst das Einlesen der Daten vom Datenbus aus. Der 6502 clock generator erzeugt einen zweiphasigen nicht überlappenden Takt (two-phase non-overlapping clock). Die Zugriffszeit TACC auf den Speicher ist um die internen Verzögerungen in der CPU kleiner als die Zykluszeit TCYC. Bei der höchsten Taktfrequenz für die CPU ist TACC die Hälfte von TCYC. Eine Zykluszeit von 1000ns verlangt mindestens 550ns ROM oder RAM Bausteine.

CRISC CPU Instruction fetch

Die Instruction fetch State Machine ist eine der State Machines in der CRISC CPU. Weitere State Machines sind die Execution State Machine und die Write Back State Machine. Diese drei State Machines hängen über gemeinsam genutzte Resourcen zusammen. Da bei der CRISC CPU die Adress-Register und der Program Counter an unterschiedliche ALUs angeschlossen sind, ist paralleles Arbeiten von der CPU möglich.
Der CRISC CPU Instruction fetch ist komplex. Jede Instruction kann auf einer gerade Adresse beginnnen oder auf einer ungeraden Adresse. Der Opcode kann ein oder zwei Byte lang sein. Das Parameterfeld kann 0 bis 4 Bytes lang sein.

Byte
 Bedeutung
 Bedeutung
 Bedeutung Bedeutung Bedeutung


#1
 Opcode 1
 Opcode 1
 Opcode 1 Opcode 1
 Opcode 1
 Opcode 1 Opcode 1
 Opcode 1
#2
Parameter 1a
 Opcode 2
 Parameter 1a
 Opcode 2
 Opcode 2 Parameter 1a
 Opcode 2
#3


Parameter 2a
 Parameter 1b
 Parameter 1b Parameter 2a
 Parameter 1b
#4




Parameter 2b
 Parameter 3a
 Parameter 2b
#5





Parameter 4a
 Parameter 3b
#6






Parameter 4b



Parameter fetch

Nicht alle CRISC CPU Instructions enthalten einen Parameter fetch. Die Instruction ADD R0,R1 benötigt keinen, die Instruction ADD R0,#100 benötigt einen Parameter fetch. Der Parameter fetch erfolgt wie der Instruction fetch. Beim Parameter fetch wird entweder der Inhalt des PC Registers auf den Adressbus gegeben oder der Inhalt eines der Adress Register oder der Inhalt des JMP Latch.

Instruction decode

Die Instruction decode Stufe und die Execute Stufe arbeiten eng zusammen. Die Instruction decode Stufe bringt die Sequenzer State machine in den nötigen Anfangszustand. Die Sequenzer Zustände werden Mikro-Code, μCode oder μOpcode States genannt. Die Sequenz für einen Jump Subroutine besteht bei der CRISC CPU aus Parameter fetch der Sprungadresse in das JMP Latch, Increment PC und paralleles Decrement von A3, Write Back von PC unter (A3). Bei der nächsten Instruktion wird nicht der Inhalt des PC Latch auf den Adressbus ausgegeben sondern der Inhalt des JMP Latch. Weiterhin wird die Operation PC_latch = JMP_latch + Increment und nicht die übliche Operation PC_latch += Increment ausgeführt.

Execute

Wegen der Execute Stufe werden alle anderen Stufen ausgeführt. Hier wird die eigentliche Arbeit der Instruction ausgeführt. Die exection von ADD R0,R1 beginnt in der High-Phase des Taktes mit der Aktivierung der Tristate Treiber von R0 und R1. Der Inhalt von R0 gelangt über den Left Lower Bus zum Left Latch der ALU, der Inhalt von R1 gelangt über den Right Latch zur ALU. Beide Latche sind während der High-Phase auf Daten-Durchlassen. Bei einer RISC CPU erfolgt dieser Ablauf in einem CPU Takt. Um eine Instruction wie ADD R0,R1 auszuführen wird der linke Tristate Treiber von R0 und der rechte Tristate Treiber von R1 aktiv. In der High-Phase des clock haben dasALU left latch und right latch den Zustand Wert-Durchlassen, dadurch gelangen die Daten von R0 und R1 in die ALU. In der Low-Phase des clockes werden die left und right latches auf Wert-Halten geschaltet, die Tristate Treiber von R0 und R1 auf passiv und das latch des Zielregisters R0 auf Wert-Aufnehmen geschaltet. Am Ende des Taktes wird das R0 latch wieder auf Wert-Halten geschaltet.

Write back

Write back ist das Gegenteil von Parameter fetch. Nicht jede Instruction führt einen Write back aus. Die Adresse für den Write back liefert eines der Adress-Register oder das JMP latch. Die CRISC CPU kennt nur Register zu Memory Schreibzugriffe. Bei der CRISC CPU gibt es keine Instruction wie die Zilog Z80 Instruction INC (HL), erhöhe den Inhalt der durch das Register HL addressierten Speicherstelle. Diese Einschränkung der Instructions ist üblich für RISC CPUs.

ALU

Die Arithmetric Logic Unit (ALU) ist das Rechenwerk in der CPU. Die Zeit für die Berechnung einer arithmetrischen Operation wie ADD und SUB ist üblicherweise länger als die Zeit für eine logische Operation wie NOT, AND, OR oder XOR. Die Bits einer logischen Operation werden individuell, einzeln für sich, verarbeitet. Die Anzahl der Bits spielt deshalb keine Rolle. Bei der Addition ist der Ergebnis der höchstwertigen Stelle abhängig von Ergebnis der zweithöchsten Stelle, die zweithöchste Stelle hängt von der dritthöchsten Stelle ab, usw. Nur das Ergebnis der niedrigsten Stelle kann individuell berechnet werden.
Eine ALU realisiert mindestens die logischen Operatoren NOT, AND, OR, XOR, die arithmetrischen Operatoren Vorzeichenumkehr, Addition und Subtraktion sowie die Schiebe Operatoren. Die Multiplikation ist nach der Addition die häufigsten benutzte arithmetrische Operation. In einem FPGA kann aus vier 18 Bit x18 Bit Multiplizierwerken ein 32 Bit x 32 Bit Multiplizierwerk mit 64 Bit Ergebnis gebaut werden.

Branch

In der Hochsprachen wie C und Forth hat sich die strukturierte Programmierung mit ihren if(), else, while() und for() Konstrukten seit langer Zeit durchgesetzt. Für die CPU gibt es nur bedingte Sprünge (branch). Bei der Assemblerprogrammierung werden für Zahlen ohne Vorzeichen (unsigned char, unsigned short, unsigned long) andere bedingte Sprünge benötigt als für Zahlen mit Vorzeichen (signed char, short, long).
Die Abkürzungen für die Branch Instructions stammen von der Programmiersprache FORTRAN, neben LISP die älteste heute noch benutzte Programmiersprache. Die Branch Instructions testen verschiedene Rechenwerk-Flags um eine Entscheidung zu treffen. Die Berechnung eines 8 Bit Wertes Ergebnis c aus den beiden 8 Bit Operanden a und b lässt sich schreiben als:

c7c6c5c4c3c2c1c0 = a7a6a5a4a3a2a1a0 op b7b6b5b4b3b2b1b0

Abkürzung
 Name
 Bedeutung
N Negative Dieses Flag wird gesetzt wenn das höchstwertige Bit des Ergebnisses gesetzt ist:
N = c7
Z
 Zero
 Dieses Flag wird gesetzt wenn das Ergebnis der letzten Operation 0 ist:
Z = ~(c7 | c6 | c5 | c4 | c3 | c2 | c1 | c0)
C
 Carry
 Dieses Flag wird gesetzt wenn das Ergebnis einen Übertrag an der höchsten Stelle ergab:
C = a7 & b7 | a7 & ~c7 | b7 & ~c7
V
 Overflow
 Dieses Flag wird gesetzt wenn das Ergebnis einen Übertrag an der zweithöchsten Stelle ergab:
V = a7 & b7 & ~c7 | ~a7 & ~b7 & c7

Der Operator ~ steht für Einerkomplement, der Operator & steht für UND, der Operator | steht für ODER und der Operator ^ steht für EXKLUSIV ODER.

Für 8 Bit unsigned Zahlen ist der Wertebereich 0 bis 255. Für 8 Bit signed Zahlen ist der Wertebereich -128 bis 127. Einige Rechenbeispiele mit 8 Bit Zahlen:

Rechnung dez
 Rechnung bin
 Ergebnis
 Z
 C
 N
 V
 Erklärung
126 + 1 = 127
 01111110 + 00000001
 01111111
 0
 0
 0
 0
 Erfolgreiche Addition von positiven signed Zahlen
-64 + -64 = -128
 11000000 + 11000000
 10000000
 0
 1
 1
 0
 Erfolgreiche Addition von negativen signed Zahlen
127 + 127 = -2 01111111 + 01111111 11111110 0
 0
 1
 1
 Überlauf bei Addition von positiven signed Zahlen
127 - 64 = 63
 01111111 - 01000000
 00111111
 0
 0
 0
 0
 Erfolgreiche signed Subtraktion grössere Zahl minus kleinere Zahl
64 - 127 = -63
 01000000 - 01111111
 11000001
 0
 0
 1
 1
 Erfolgreiche signed Subtraktion kleinere Zahl minus grössere Zahl
127 - 127 = 0
 01111111 - 01111111
 00000000
 1
 0
 0
 0
 Erfolgreiche signed Subtraktion gleicher Zahlen
0 - 127 = -127
 00000000 - 01111111
 10000001
 0
 1
 1
 1
 Erfolgreiche Vorzeichenumkehr einer positiven signed Zahl
0 - -1 = 1
 00000000 - 11111111
 00000001
 0
 1
 0
 0
 Erfolgreiche Vorzeichenumkehr einer negativen signed Zahl
0 - -128 = -128
 00000000 - 10000000
 10000000
 0
 0
 1
 0
 Überlauf bei Vorzeichenumkehr einer negativen signed Zahl
254 + 1 = 255
 11111110 + 00000001
 11111110
 0
 0
 1
 0
 Erfolgreiche Addition zweier unsigned Zahlen
255 + 255 = 254
 11111111 + 11111111
 11111110
 0
 1
 1
 0
 Überlauf bei Addition von unsigned Zahlen


Die Bxx Instructions führen einen bedingten Sprung aus wenn der Test erfolgreich war. Die Sxx Instructions laden -1 in das als Operand angegebene short Register wenn der Test erfolgreich war oder 0 wenn der Test nicht erfolgreich war. Mit den Sxx Instructions lassen sich Ausdrücke wie (r0 >= 0 && r0 <= 9) leicht in Maschinensprache übersetzen.

Programmiersprache C
 als Subtraktion
 Instruction
 Test unsigned
 Instruction
 Test signed
if (r0 > r1)
 if (r0-r1 > 0)
 JGT oder SGT
 C | Z == 0
 SJGT oder SSGT
 Z | (N ^ V) == 0
if (r0 >= r1)
 if (r0-r1 >= 0) JGE, JCC oder SGE, SCC
 C == 0
 SJGE oder SSGE
 N ^ V == 0
if (r0 == r1)
 if (r0-r1 == 0) JEQ oder SEQ
 Z == 1

if (r0 != r1)
 if (r0-r1 != 0)
 JNE oder SNE
 Z == 0

if (r0 <= r1)
 if (r0-r1 <= 0) JLE oder SLE
 C | Z == 1
 SJLE oder SSLE
 Z | (N ^ V) == 1
if (r0 < r1)
 if (r0-r1 < 0) JLT, JCS oder SLT, SCS
 C == 1
 SJLT oder SSLT
 N ^ V == 1


Full Adder

Mit dem full adder werden zwei Bits und Übertrag (Carry) addiert. Er hat die drei Eingänge linker Operand a, rechter Operand b und Carry-In Cin sowie die zwei Ausgänge Ergebnis f und Carry-Out Cout. Bei 3 Eingängen gibt es 23 = 8 Möglichkeiten. Die Wahrheitstabelle ist:

Cin
 a
 b
 Cout
 f
0
 0
 0
 0
 0
0
 0
 1
 0
 1
0
 1
 0
 0
 1
0
 1
 1
 1
 0
1
 0
 0
 0
 1
1
 0
 1
 1
 0
1
 1
 0
 1
 0
1
 1
 1
 1
 1

Der Ausgang Cout wird gesetzt wenn zwei oder drei Eingänge eine 1 liefern. Der Ausgang f wird gesetzt wenn einer oder drei Eingänge eine 1 liefern. So kann der full adder in Gatter Logik aufgebaut werden:

Cout = a & b | Cin & a | Cin & b
f = (a ^ b) ^ Cin

Hades enthält die Simulation eines full adders. In der Programmiersprache C lässt sich ein full adder programmieren, auch wenn C für Bitverarbeitung nicht gut geeignet ist. Deshalb wird der elementare Datentype unsigned char als Datentype BIT benutzt.

#define BLEN 8

typedef unsigned char BIT;      // C kennt keine Bitverarbeitung
typedef unsigned char *BOUT;    // Rueckgabewert

void full_adder(BOUT Cout, BOUT f, BIT Cin, BIT a, BIT b) {
    *Cout = a & b | Cin & a | Cin & b;
    *f = a ^ b ^ Cin;
}

Sollen mehrstellige binäre Zahlen addiert werden, wird der full adder zum serial adder erweitert. Angefangen bei der niederwertigsten Stelle wird pro Takt eine Stelle durch den full adder berechnet. Der Cout der vorherigen Stelle wird wird zum Cin bei der Berechnung der nächsten Stelle. Ein solcher serial adder wurde im Taschenrechner HP-35 eingesetzt. Der Hardwareaufwand ist gering, die Ausführungsgeschwindigkeit aber auch. Weil BIT ein elementarer Datentype in C ist, lassen sich leicht Bitvektoren bilden und ein serial adder in C programmieren. Der serial adder liefert neben der Summe im Vektor f auch das Carry Flag C und das Overflow Flag V. Das Carry Flag ist Cout der höchsten Stelle. Das Overflow Flag wird gesetzt wenn sich Cin und Cout der höchsten Stelle unterscheiden. Mit der logischen Funktion XOR wird der Unterschied festgestellt.

typedef unsigned char *BVEC;    // Bitvector

void serial_adder(BOUT C, BOUT V, BVEC f, BVEC a, BVEC b) {
    int i;
    BIT Cout = 0, Cin;
    for (i = 0; i < BLEN; ++i) {
        Cin = Cout;
        full_adder(&Cout, &f[i], Cin, a[i], b[i]);
    }
    *C = Cout;
    *V = Cin ^ Cout;
}

Ein ripple carry adder besteht aus einer Kette von serial adders. Die Verarbeitung erfolgt nicht mehr Bit für Bit, aber auch nicht parallel. Der Übertrag (Carry) pflanzt sich von der niederwertigsten Stelle bis zur höchstwertigen Stelle fort. Der schlimmste Fall (worst case) für einen ripple carry adder ist die Addition von 11111111 + 00000001. In diesem Fall läuft das Carry durch alle Stellen. Der Sequenzer muss die worst case Zeit abwarten um sicherzustellen, dass jede Addition das richtige Ergebnis liefert. Hades enthält die Simulation eines ripple adders.
Mit einer anderen Wahrheitstabelle wird aus einem full adder ein full subtractor für die Subtraktion. Ein serial subtractor oder ripple carry subtractor wird wie oben für den adder beschrieben gebildet. In den FPGA Programmiersprachen VHDL und Verilog sind adder und subtractor fertige Bausteine welche mit den Operatoren + oder - bezeichnet werden. Ein adder der Carry und Overflow für eine Bitlänge N liefert lässt sich aus einem Standard adder für Bitlänge N und einem Standard adder für Bitlänge 2 aufbauen. Die höchste Stelle des ersten adder und die höchste Stelle des zweiten adder werden zur Berechnung von Carry und Overflow benutzt.

#define getBIT(var,ndx) ((var & 1<<ndx)?1:0)
typedef unsigned char BIT8;        // 8 Bit Binaerzahl
typedef unsigned char BIT2;        // 2 Bit Binaerzahl

BIT8 serial_adder2(BOUT C, BOUT V, BIT8 a, BIT8 b) {
    BIT a_msb = getBIT(a, 7);
    BIT b_msb = getBIT(b, 7);
    a &= 0x7f;                        // hoechste Stelle entfernen
    b &= 0x7f;
    BIT8 f1 = a + b;                  // erster adder
    BIT f1_msb = getBIT(f1, 7);
    f1 &= 0x7f;
    BIT2 f2 = a_msb + b_msb + f1_msb; // zweiter adder
    BIT f2_msb = getBIT(f2, 1);
    BIT f2_lsb = getBIT(f2, 0);
    *C = f2_msb;
    *V = f1_msb ^ f2_msb;
    return f2_lsb<<7 | f1;            // beide Ergebnisse zusammensetzen
}

Barrel Shifter

Die Schiebe Instructions logic shift right (LSR) und logic shift left (LSL) werden durch einen Barrel Shifter ausgeführt. Der Barrel Shifter besteht im einfachsten Fall aus einem 2 zu 1 Multiplexer für jedes Eingangsbit. Über eine Steuerleitung wird bestimmt ob alle Multiplexer einer Barrel Shift Stufe den linken oder den rechten Eingang benutzen. Wird der linke Eingang genutzt, werden die Bits vom Eingang zum Ausgang durchgereicht, der Pegel an Eingangsbit 0 bestimmt den Pegel an Ausgangsbit 0. Wird der rechte Eingang genutzt, wird Ausgang N mit einem anderen Eingang als Eingang N verbunden. Ein Rechtsschieben ergibt sich wenn Ausgang N mit Eingang N+1 verbunden ist. Ein Linksschieben ergibt sich wenn Ausgang N mit Eingang N-1 verbunden ist.
Für einen Barrelshifter der die Eingangsdaten um mehrere binäre Stellen verschieben kann werden mehrere 2 zu 1 Multiplexer Stufen hintereinander geschaltet. Wird der linke Eingang eines Multiplxers benutzt erfolgt keine Verschiebung. Der rechte Eingang des Multiplxers der ersten Stufe verschiebt die Eingangsdaten um 1 Bit, die Multiplexer der zweiten Stufe verschieben um 2 Bit und die dritte Stufe verschiebt um 4 Bit. Die Steuerleitungen aller Multiplexer einer Stufe sind verbunden. Mit diesem dreistufigen Barrelshifter lassen sich die Eingangsdaten um 0 bis 7 Bits verschieben. Hades enthält die Simulation eines 3-stufigen Barrel-Shifters.
Um den Hardware-Aufwand für den Barrelshifter in der CRISC CPU klein zu halten kennt der barrel shifter nur die Verschiebungen um 1 Bit nach links, 1 Bit nach rechts, 8 Bit nach links und 8 Bit nach rechts. Schieben um 1 Bit wird fine shifting genannt, Schieben um 8 Bit bulk shifting. Das Schieben um N Bit mit dem fine/bulk barrel shifter erfolgt auf Maschinensprache Ebene durch CRISC Instructions. Ein Shift N Mikroprogramm ist für die CRISC CPU nicht vorgesehen.

Literatur

Volnei A. Pedroni; Circuit Design and Simulation with VHDL, Second Edition; The MIT Press; 2010

Hamblen, James O., Hall, Tyson S., Furman, Michael D.;Rapid Prototyping of Digital Systems: SOPC Edition; Springer; 2008
Die Paperback Ausgabe enthält keine DVD. Hier gibt es den DVD Inhalt. Auf der Buchseite empfehlen die Autoren Quartus 9.1 SP2. Nicht alle Beispiele im Buch passen zum aktuellen Quartus 10.1.

Christopher W. Fraser,  David R. Hanson; A Retargetable C Compiler: Design and Implementation; Benjamin/Cummings; 1995

R. G. Loeliger; Threaded Interpretive Languages; Mc Graw Hill; 1981

Über den Autor

Früher entwickelte der Autor Hardware, heute schreibt er Software. Die Software-"Maschinen" sind komplexer als die Hardware-Maschinen. Bei beiden Tätigkeiten hat testen, testen, testen die höchste Priorität. Dem Gerät oder Programm soll es im Labor viel schlechter ergehen als am Einsatzort. Der Autor versucht immer noch den Programmieranteil hoch und den Verwaltungsanteil niedrig zu halten. Es macht einfach mehr Freude etwas zu erschaffen, als in einer Besprechung etwas zu zerreden. Und wer im Labor fleißig war, kann oft durch Fakten die Diskussion in seine Bahnen lenken. Es gilt immer noch die normative Kraft des Faktischen, oder wie Phillip K. Dick sagte: "Reality is that, which, when you stop believing in it, doesn't go away."