Rechnerorganisation

SoSe 2020

Author: Denis Falk

Stand: 3 September 2020

1 Lernziele und Lerninhalte

• Architektur von Mikroprozessoren: Programmierung in Assembler und Maschinensprache,

Adressierungsarten, Werkzeugflüsse, Laufzeitumgebung
• Mikroarchitektur: Befehlssatz und architektureller Zustand, Leistungsbewertung, Mikroarchitekturen mit
Eintakt-/Mehrtakt-/Pipeline-Ausführung, Ausnahmebehandlung, fortgeschrittene Mikroarchitekturen
• Speicher und Ein-/Ausgabesysteme: Leistungsbewertung, Caches, virtueller Speicher, Ein-
/Ausgabetechniken, Standardschnittstellen

1.1 Schichtenmodell eines Computers

Die wesentlichen Eigenschaften des Schichtenmodells sind:

- Eine untere Schicht erbringt „Dienstleistungen“ für die nächst höhere Schicht.
- Eine obere Schicht nutzt nur die Dienste der nächst niedrigeren Schicht.

Die Vorteile einer sauberen Schichtenstruktur sind:

- Austauschbarkeit einzelner Schichten, ohne benachbarte Schichten oder das gesamte System ändern zu
müssen.
- Ein Benutzer braucht nur die von ihm zu bearbeitende Schicht zu kennen. Die darunterliegenden Schichten
bilden
eine fest definierte Funktionalität.
- Anmerkung: Für manche Aufgaben ist eine genauere Kenntnis der unteren Schichten notwendig
(z.B. Programmierung von Gerätetreibern.)
- Ein Nachteil ist ggf. eine geringere Leistungsfähigkeit des Systems.

1.2 Definition einiger Grundbegriffe

Was ist ein Computer? Ein Computer ist ein Synonym für ein Datenverarbeitungssystem. Die Definition eines
Datenverarbeitungssystems nach DIN lautet „Ein Datenverarbeitungssystem ist eine Funktionseinheit zur
Verarbeitung und Aufbewahrung von Daten. Verarbeitung umfasst die Durchführung mathematischer,
umformender, übertragender und speichernder Operationen.“

Aus der Definition kann man folgende vier Grundfunktionen ableiten, die ein Rechner ausführt.
Verarbeitung von Daten: Rechnen (+,-,*,/), logische Verknüpfungen (AND,OR,..)
Speichern von Daten: Ablegen, Wiederauffinden, Löschen (und das in ganz unterschiedlichen Speichern)
Unformen von Daten (welches auf die Verarbeitung der Daten zurückzuführen ist): Sortieren, Packen und
Entpacken.
Kommunizieren: Mit dem Benutzer (Mensch-Maschine Schnittstelle) und mit anderen Rechnersystemen.

Die Abgrenzung von Rechnersystemen zu Taschenrechnern und Messgeräten erfolgt über die Art der Steuerung.
Merkmal: Die Steuerung eines Rechnersystems erfolgt über ein ladbares Programm, das aus einer Folge von
Anweisungen, sogenannten Maschinenbefehlen besteht und schrittweise die gewünschte Funktion ausführt.

1.3 Komponenten eines Rechnersystems

In einem Rechnersystem sind mindestens die drei folgenden Komponenten vorhanden.

- Ein Prozessor (Zentraleinheit, CPU), der die Programme ausführen kann.
- Ein Speicher der Programme und Daten enthält (Speichersystem).
- Eine Möglichkeit, zum Transferieren von Informationen zwischen dem Speicher und dem Prozessor, sowie der
Außenwelt (Ein-/Ausgabesystem).
Anmerkung: Die Komponenten eines Rechnersystems müssen in der Regel eine gemeinsame Zeitbasis haben,
damit das Zusammenspiel funktioniert. Die Zeitbasis nennt man auch Takt/Taktsignal/Systemtakt.

2.1 Struktur eines Rechnersystems

2.1.1 Speicherhierarchie – Klassifikation von Speichern

Die Explizite und transparente Nutzung, d.h. Speicher können zunächst danach klassifiziert werden, ob sie für
den Programmierer (bzw. das später auszuführende Maschinenprogramm) explizit zugreifbar sind oder nur
impliziert, d.h. Für das Maschinenprogramm transparent, verwendet werden.
Die explizite Nutzung, d.h. Der interne Prozessorspeicher, der Hauptspeicher und der Sekundärspeicher.
Die transparente Nutzung, d.h. Die bestimmten Register auf dem Prozessor und der Cache-Speicher

2.1.2 Speicherhierarchie 2 – Explizit nutzbare Speicher

Der interne Prozessorspeicher/Register: schnelle Register zur temporären Speicherung von Maschinenbefehlen
und Daten. Direkter Zugriff durch Maschinenbefehlen. Technologie: Halbleiter ICs
Hauptspeicher: Relativ großer und schneller Speicher für Programme und Daten während der Ausführung.
Direkter Zugriff durch Maschinenbefehle. Technologie: Halbleiter ICs.
Sekundärspeicher: Sehr großer, aber langsamer(er) Speicher für die permanente Speicherung von Programmen
und Daten. Indirekter Zugriff über E/A-Programme, die Daten in den Hauptspeicher transferieren. Technologie:
Halbleiter ICs, Magnetplatten, optische Laufwerke, Magnetbänder.
2.1.3 Speicherhierarchie 3 – Übersicht

2.2 Einführung in die maschinennahe Programmierung

2.2.1 Programmierparadigmen

Was ist ein Paradigma? Synonyme sind Denkmuster oder Musterbeispiel. Die Verwendung des Paradigma-
Begriffes in der Informatik sind: Ein Paradigma bezeichnet ein übergeordnetes Prinzip, dieses Prinzip ist für eine
ganze Teildisziplin typisch, es ist jedoch nicht klar ausformulierbar, sondern manifestiert sich in Beispielen.
Die Maschinensprache (bzw. Assembler) ist ein primitives Paradigma.

2.2.2 Programmiermodell

Das Programmiermodell ist ein Begriff, der häufig in unterschiedlichen Definitionen verwendet wird.
Bei höheren Programmiersprachen z.B. Grundlegende Eigenschaften einer Programmiersprache
(Programmiermodell dieser Hochsprache) oder auch anders genannt Verarbeitungsmodell, Modellierungsmodell
etc.
In der maschinennahen Programmierung bezeichnet das Programmiermodell den Registersatz eines Prozessors.
Eher die Register die durch Programme angesprochen werden können sowie die verfügbaren Befehle
(Befehlssatz). Diese Register die Prozessor intern verwendet werden (z.B. IP/PC) zählen nicht zum Registersatz des
Prozessors. (IP = Instruction Pointer, PC = Program Counter)
2.2.3 Assemblersprache

Die Assemblersprache ist Programmieren in der Sprache des Computers. Ein Maschinenbefehl sind Einzelne Worte
und der Befehlssatz das Gesamte Vokabular. Die Befehle geben Art der Operation und ihre Operanden an. Es gibt
Zwei Darstellungen, die Assemblersprache die für den Menschen lesbare Schreibweise für Instruktionen und die
Maschinensprache die maschinenlesbares Format genannt wird. (1en und 0en).

2.2.4 ARM-Architektur

Die Arm-Architektur wurde 1983 von Acorn entwickelt. ARM steht für Acorn RISC Machines / Advanced RISC
Machines. Der Befehlssatz wurde von Sophie Wilson entwickelt und die Mikroarchitektur von Steve Furber. Der
erste ARM Computer war der 1987 erschienene Acorn Archimedes. Heute ist ARM groß verbreitet wie z.B. in
Smartphones etc.

2.2.5 Verfeinerung des Rechnersystems

Dieses Bild zeigt einen modernes Rechnersystem mit ihrer Struktur.

CPU/Prozessor: führt die im Hauptspeicher abgelegten Befehle aus.
ALU (Artihmetic Logic Unit): Ausführung der Operationen, typische Befehle sind: add,sub,mul und div.
PC (Programm Counter): Programmzähler, der immer auf den nächsten Maschinenbefehl im Hauptspeicher (Main
memory) zeigt.
Register (Register File): schneller Speicher für Operanden.
Hauptspeicher (Main memory): Speichert Befehle und Daten.
Bus Interface: Verbinden der einzelnen Komponenten (z.B. System bus, Memory bus).
2.2.6 Beispielprogramm in C

Wie wird auf dem Rechnersystem ein Programm ausgeführt?

Hier anhand eines Beispiels: hello world (Datei hello.c)
#include <stdio.h>
int main() {
printf(„Hello World\n“);
return 0;
}

2.2.6 Phasen der Übersetzung

Das obige C Programm ist für den Menschen verständlich, aber zur Ausführung auf dem Rechnersystem muss es in
Maschinenbefehle übersetzt werden. Mit z.B. dem Unix System Befehl: gcc -o hello hello.c

Der Übersetzungsvorgang ist in verschiedene Phasen unterteilt wie oben zu sehen.

1. Phase (Preprocessor)
Aufbereitung durch Ausführung von Direktiven (mit #)
z.B. bearbeiten von #include <stdio.h> → Lesen des Inhalts der Datei stdio.h und Kopieren des Inhalts in die
Programmdatei.
Ausgabe ist dann das C-Programm mit der Endung .i

2. Phase (Compiler)
Übersetzt das C-Programm hello.i in ein Assemblerprogramm hello.s

3. Phase (Assembler)
Übersetzt hello.s in Maschinensprache. Das Ergebnis ist das Objekt-Programm hello.o

4. Phase (Linker)
Zusammenfügen verschiedener Module. Beispielprogramm nutzt die printf Funktion, der Code von printf existiert
bereits übersetzt in einer Bibliothek (Der Standard C Library) als printf.o Datei.
Der Linker kombiniert hello.o und printf.o zu einem ausführbaren Programm (u.a. Auflösen von Referenzen)
Ausgabe des Bindevorgangs: hello Datei
hello ist eine ausführbare Objekt-Datei, die in den Speicher geladen und ausgeführt werden kann.

2.2.7 Wie wird das Programm hello ausgeführt?

Der Ausgangspunkt ist, dass hello ein ausführbares Objektprogramm auf der Festplatte ist. Das Starten der
Ausführung des Programms unter Nutzungs eines speziellen Programms, der Shell ./hello
Die Shell ist ein Kommandozeileninterpreter, d.h. Sie druckt Eingabeaufforderungen (Prompt), wartet auf Eingabe
einer Kommandozeile und führt Kommandos aus (bzw. intiiert die Ausführung).

2.2.8 Schritte zur Ausführung von hello

Die Shell liest zunächst die Zeichen des Kommandos in die Register und speichert den Inhalt dann im
Hauptspeicher ab. Wie unten zu sehen ist.
Danach wird schrittweise die Befehle und Daten von Festplatte in den Hauptspeicher (hier wird Direct Memory
Access (DMA) benutzt) kopiert.

Nun folgt die Ausführung der Maschinenbefehle des hello Programms.

2.2.9 Ein erstes Assemblerprogramm – noch in C

/* Addition */
#include <stdio.h>
int main() {
int p = 5;
int q = 12;
int result = p + q;
printf(„result ist %d\n“,result);
return 0;
}

Übersetzung des C-Programms: gcc addition.c

Generierung des Assemblerprogramms: gcc -S addition.c
2.2.10 Befehle eines Rechnersystems – CISC,RISC

Was für Maschinenbefehle soll ein Prozessor eigentlich haben? Wieviele Befehle soll eine Prozessor haben?
Diese Frage ist nicht so einfach zu beantworten. Früher wurden relativ viele komplexe Befehle eingesetzt. Diese
Rechner wurden und werden als CISC-Maschinen (Complex Instruction Set Computer) bezeichnet. Desweiteren gibt
es die Klasse der RISC-Maschinen (Reduced Instruction Set Computer). Eine Eigenschaft der RISC ist die weitgehend
identische Ausführungszeit der Befehle, die erst ein effizientes Pipelining ermöglicht. RISC-Maschinen werden auch
als Load/Store-Architektur bezeichnet.
Eine Analyse der Assemblerprogramme zeigt, dass es Befehle gibt, die eigentlich „jeder“ Prozessor hat. z.B. AND,
OR, NOT, ADD.
CISC-Maschine: Intel Architektur
RISC-Maschine: ARM Architektur

Rechnersysteme haben ähnliche Grundstrukturen. Einen Prozessor (Zentraleinheit, CPU), der die Programme
ausführen kann. Einen Speicher der die Programme und Daten enthält (Speichersystem) und eine Möglichkeit, zum
Transferieren von Informationen zwischen dem Speicher und dem Prozessor, sowie der Ausßenwelt
(Ein./Ausgabesystem).
Der interne Aufbau (Struktur) eines Rechnersystems hat viele Freiheitsgerade, die Struktur eines Prozessors hat
erheblichen Einfluss auf die Leistungsfähigkeit (und die Kosten) eines Rechnersystems.

Eine Einteilung kann z.B. nach der Anzahl der Operanden in einem Maschinenbefehl vorgenommen werden.
Man spricht dann auch von n-Adressmaschinen: 2-Adressmaschine (Intel Architektur), 3-Adressmaschine (ARM
Architektur).

2.2.11 ARM-Prozessor Registersatz

2.2.12 Speicherorganisation: Big-Endian und Little-Endian

Sie sind eine Schemata für Nummerierungen von Bytes in einem Wort (Wort-Adresse ist bei beiden gleich)
Big-Endian: Bytes werden vom höchstwertigen Ende an gezählt
Little-Endian: Bytes werden vom niederwertigen Ende an gezählt

2.3 Lernkontrolle

– Ich habe die Verfeinerung des abstrakten Rechnersystems nachvollziehen können und die Idee sog.
Speicherpyramide nachvollziehen können
– Die Begriffe Programmiermodell und Maschinenbefehle sind mir geläufig und ich kann die
„Maschinensprache“ gegenüber Hochsprachen abgrenzen
– Ich kann die Schritte der Programmübersetzung nachvollziehen und habe den Kern/die Funktion des ersten
Assemblerprogramms verstanden.

(a) Was ist der Unterschied zwischen wort-adressiertem und byte-adressiertem Speicher?
A: Bei einer wort-adressierten Speicherung hat jedes Datenwort eine eindeutige Adresse. Bei einer byte-
addressierten Speicherung hat jedes einzelne Byte eine individuelle Adresse.

(b) Erklären Sie den Unterschied zwischen Big-Endian und Little-Endian

A: Bei Big-Endian werden die Bytes vom höchstwertigen Ende an gezählt. Das MSB wird an der niedrigsten
Speicheradresse abgelegt. Bei Little-Endian werden die Bytes vom niederwertigen Ende an gezählt. Das LSB wird an
der niedrigsten Speicheradresse abgelegt.

(c ) Wann sollten Daten in Registern gespeichert werden?

A: Wenn die Daten häufig verwendet werden. Dabei ist zu beachten, dass nur eine begrenzte Anzahl von Registern
zur Verfügung steht.

(d) Gegeben sei ein wort-adressierter Speicher. Wieviele Wörter lassen sich maximal adressieren, wenn die Adresse
zwei Byte groß ist?
A: 2^16 = 65536
3.1.1 Programmiermodell des ARM-Prozessors – Registersatz II

– R0
– R1 – R12
– R13 (sp) – stack pointer (Stapelzeiger)
– R14 (lr) – link register (Rückkehradresse)
– R15 (pc) – programm counter (Befehlszähler)
– CPSR – Current Processor Status Register (enthält u.a. Statusflags)

3.1.1 Operanden: Speicher

Alle Daten passen nicht in 15 Register. Daher werden Daten im Hauptspeicher abgelegt. Der Hauptspeicher ist groß
(GB...TB) und kann viele Daten aufnehmen aber ist langsamer als z.B. ein Register. Daher speichert man häufig
verwendete Daten in Registern. Man kann Register und Speicher zum Halten von Daten kombinieren, das Ziel ist
schnell auf gerade benötigte Daten zu zugreifen.

3.1.2 Wort- und Byte-Adressierung von Daten im Speicher

ARM ist byte-adressiert, das heißt jedes Byte hat eine eindeutige Adresse. 32-bit Wort = 4 Bytes.
Adressen von Worten sind also das Vierfache von 4.
3.1.3 Lesen aus byte-adressiertem Speicher

Das Lesen geschieht durch Ladebefehle (load)

Der Befehlsname ist: load word (ldr)

Beispiel:
mov r5,#0
ldr r7,[r5,#8]

Die Funktion: Lese ein Datenwort von der Speicheradresse (r5+8) und schreibe dieses in das Register r7.
Adressarithmetik: Adressen werden relativ zu einem Register angegeben. Basisadresse (r5) plus Distanz (Offset) (8).
Entspricht Adresse = (r5 + 8).

Ergebnis: r7 enthält das Datenwort von Speicheradresse (r5 + 8)

Jedes Register darf als Basisadresse verwendet werden!

Beispiel 2 Lese Datenwort 3 (Speicheradresse 0xC) nach r7:

mov r5,#0
ldr r7, [r5,#0xC]

Adresse = (r5 + 12) = 12

Nach Abarbeiten des Befehls hat r7 den Wert 0x40F30788

3.1.4 Schreiben in byte-adressierten Speicher

Schreiben geschieht durch Speicherbefehle (store)

Befehlsname: store word (str)

Beispiel:
mov r1,#0
mov r9,#42
str r9,[r1,#0x14]

Funktion: Schreibe (speichere) den Wert aus r9 in Speicherwort 5 (bzw. Speicheradresse 5x4=20=0x14)
Adressarithmetik: „Wie ldr“
Ergebnis: Nach Abarbeiten des Befehls enthält Speicheradresse (r1 + 20) das Datenwort von r9.

Die Transportbefehle können auf Worten oder Bytes arbeiten.

Speichern: str / strb
Laden: ldr / ldrb

3.1.5 Befehle eines Rechnersystems

Mehrere Befehlsformate erlauben Flexibilität.

ADD,SUB: verwenden z.B. drei Register als Operanden
LDR,STR: verwendet zwei Register und eine Konstante als Operanden

Die Anzahl von Befehlsformaten sollte klein sein, da dadurch wird die Hardware weniger aufwendig (und damit
billiger) und erlaubt ggf. höhere Verarbeitungsgeschwindigkeit.
3.1.6 Operanden: Konstante Werte in Befehlen (immediates)

ldr und str zeigen die Verwendung von konstanten Werten (immediates). Sie sind direkt im Befehl untergebracht,
deshalb auch Direktwerte genannt. Sie brauchen kein eigenes Register oder einen Speicherzugriff.

Der Befehl add addiert Direktwert auf Register. Direktwert ist die Zweierkomplementzahl, die 12 Bit breit ist

Hochsprache:
a = a + 4;
b = a - 12;

ARM-Assembler (r0 = a, r1 = b):

add r0,r0,#4
add r1,r0,#-12

3.1.7 Programmierung in Assembler

Die Hochsprachen z.B. C, C++, Java, Python oder Scheme werden auf einer abstrakten Ebene programmiert. Die
häufigen Konstrukte in Hochsprachen sind if/else-Anweisungen, while-Schleifen, for-Schleifen, Feld (Array) Zugriffe
oder auch Unterprogramme (Funktion, Prozedur, Rekursion).

3.1.8 Abbildung von Kontrolloperationen

Die wichtigsten Statusflags sind:

C - Carryflag (Übertragsflag)
Z - Zeroflag (Nullflag)
N - Negativflag (Vorzeichenflag)
V - Overflowflag (Überlaufflag)

Für was werden diese Flags verwendet? z.B. Z in der Hochsprache wäre t == 0
oder N in der Hochsprache wäre t < 0.

Wichtig! Beim ARM-Prozessor werden die Flags im CPSR (Current Processor Status Register) abgespeichert!
3.1.9 Kontrollstrukturen in Assembler - Berechnung der Statusbits

Beispiel: Unterschied zwischen Carry und Overflow.

Angenommen: 2K-Darstellung. Die Zahlen sind 4 Bit breit. Der Zahlbereich ist also von -8 bis +7.
0101 5
0001 1
E: 0110 6

Es tritt kein Carry und kein Overflow auf.

C = 0, V = 0

Beispiel:
0101 5
0011 3
E 1000 8

In diesem Fall tritt kein Carry, aber ein Überlauf auf. Beide Operanden 5 und 3 sind positiv. Das Vorzeichen aber ist
negativ. C = 0, V = 1

Beispiel:
0101 5
1111 -1
E: 1 0100 4

In diesem Fall tritt ein Carry, aber kein Überlauf auf. C = 1, V = 0

Beispiel (3+(-5)):

0011 3
1011 -5
E: 1110 -2

In diesem Fall tritt kein Carry und kein Überlauf auf. Das Vorzeichen ist negativ und das Vorzeichenbit wird eins.
C = 0, V = 0, N = 1
3.1.10 Sprünge / Verzweigungen

Sprünge / Verzweigungen ändern die Ausführungsfolge von Befehlen. Es gibt 2 Arten von
Sprüngen/Verzweigungen. Unbedingte Sprünge: b target (Springe (branch) zu target)
und bedingte Sprünge beq target (branch equal).

Unbedingte Sprünge (b):

add r1,r2,#17 // r1 = r2 +17
b target // branch to target
orr r1,r1,r3 // nicht ausgeführt
and r3,r1,#0xFF // nicht ausgeführt

target: //Positionsmarkierung (label)

sub r1,r1,#78 // r1 = r1 - 78

Wichtig! Labels sind Namen für Stellen (Adressen) im Programm. Sie müssen anders
als Maschinenbefehle (Mnemonics) heißen. Achtung! Labels müssen mit einem Doppelpunkt abgeschlossen
werden!

Bedingte Sprünge (beq):

mov r0,#4 // r0 = 4
add r1,r0,r0 // r1 = r0 + r0 = 8
cmp r0,r1 // setze Flags auf der Basis der Rechnung r0-r1 = -4. Statusflags: N=1, Z=0, C=0, V=0
beq there // Kein Sprung (Z != 1)
orr r1,r1,#1 // r1 = r1 or 1 = 9

there:
add r1,r1,#78 // r1 = r1 + 78 = 87
3.1.11 Hochsprachen Sprachkonstrukte in Assembler

if-Anweisungen:
//Hochsprache
if (apples == oranges)
f = i + 1;

f = f -1;

//Assembler r0 = apples; r1=oranges, r2=f, r3=i

cmp r0,r1
bne L1
add r2,r3,#1
L1:
sub r2,r2,r3

if/else-Anweisung:
//Hochsprache
if(apples == oranges)
f = i + 1;
else
f = f - i;

//Assembler r0 = apples; r1=oranges, r2=f, r3=i

cmp r0,r1
bne L1
add r2,r3,#1
b L2
L1:
sub r2,r2,r3
L2:

while-Schleifen:
//Hochsprache berechnet x = log2(128)
int pow = 1; int x = 0;
while(pow != 128) {
pow = pow * 2;
x = x+1;
}

//Assembler r0 = pow, r1 = x
mov r0,#1
mov r1,#0
WHILE:
cmp r0,#128
beq DONE
lsl r0,r0,#1 //pow = pow * 2
add r1,r1,#1 // x= x+1
b WHILE
DONE:

for-Schleifen:
//Hochsprache addiere Zahlen von 0 bis 9
int sum = 0; int i;
for (i = 0; i < 10; i = 1+1) {
sum = sum + i;
}

//Assembler r0 = i, r1 = sum
mov r1,#0
mov r0,#0
FOR:
cmp r0,#10
bge DONE
add r1,r1,r0 //sum = sum+i
add r0,r0,#1 //i=i+1
b FOR
DONE:

3.2 Lernkontrolle

(a) Wie kann mit Maschinenbefehlen die Multiplikation mit 2 und die Division mit 2 effizient implementieren? Wie
heißen diese Maschinenbefehle bei einer ARM-Architektur?
A: Durch das Schieben nach links, ergibt sich eine Multiplikation mit 2. Entsprechend wird eine Division durch 2
durch das Schieben nach Rechts realisiert. Die Maschinenbefehle heißen lsl (für den Links-Shift) und lsr (für den
Rechts-Shift)

(b) Mittels welcher Flags werden Verzweigungen im Programmablauf realisiert?

A: Die Flags heißen: CF Übertragsflag (Carryflag), ZF Nullflag (Zeroflag), SF/NF Vorzeichenflag (Signflag/Negativflag),
OF Überlaufflag (Overflowflag).
Bemerkung beim ARM-Prozessor werden die Flags im CPSR - Current Processor Status Register abgespeichert und
werden dort mit C,Z,N,V bezeichnet.
4.1 Nutzung des Hauptspeichers

Statt die Daten direkt in Register zu schreiben (z.B. durch mov r1,#42) gibt es auch die Möglichkeit die Werte durch
Variablen bzw. die Angabe des Variablennamens zu laden.

Direkt laden:

Durch Variablen:

Es gibt auch die Möglichkeit die Werte der Variablen durch eine indirekte Adressierung zu Laden (=var):

Eine Ergänzung in Zeile 13 und Angabe eines Registers in Zeile 14 nun ist die Ausgabe 24:
Erklärung der Nutzung der Register und des Hauptspeichers:

4.2 Datenfelder (Arrays)

Das Laden (und Speichern) von Worten ist bekannt. Die Datenfelder (arrays) bestehen aus mehreren Worten, sie
sind nützlich um auf eine große Zahl von Daten vom gleichen Typ zuzugreifen. Der Zugriff auf einzelne Elemente
über den Index. Die Größe eines Arrays entspricht die Anzahl der Elementen im Array.
4.2.1 Verwendung von Arrays

Hier dargestellt ein Array mit 5 Elementen. Die Basisadresse ist 0x12348000, das ist die Adresse des ersten Array-
Elements (Index 0, geschrieben als array[0])

Array in einer for-schleife bearbeiten:

//Hochsprache:
int i;
int scores[200];
for (i = 0; i < 200; i = i + 1) {
scores[i] = scores[i]+10;
}

//Assembler r0=Basisadresse von Array, r1=1

mov r0,#0x14000000 //Basisadresse in r0
mov r1,#0
LOOP:
cmp r1,#200 // i < 200
bge L3 // if i >= 200, exit loop
lsl r2,r1,#2 // r2 = i * 4
ldr r3,[r0,r2] //r3 = scores[i]
add r3,r3,#10 //r3 = scores[i]+10
str r3,[r0,r2] //scores[i] = scores[i] + 10
add r1,r1,#1 // i = i + 1
b LOOP // repeat
L3:
4.3 Unterprogramme

Unterprogramme helfen bei der strukturierten Programmierung, im Prinzip gibt es zwei grundlegende Konzepte zur
Realisierung von Unterprogrammen (eine Funktion stellt ein spezielles Unterprogramm da). Betrachtet wird ein
Programm (Hauptprogramm), in dem ein Teilprogramm (TP) an verschiedenen Stellen ausgeführt werden soll. Es
gibt zwei Konzepte: Makrotechnik und Unterprogrammtechnik.

4.3.1 Makrotechnik

Hier wird das Teilprogramm an den Stellen, wo es gebraucht wird einkopiert. Dazu wird dem Teilprogramm, dem
sogenannten Makro, ein Name zugeordnet (Makroname). Das passiert durch die sogenannte Makrodefinition. An
den Stellen, an denen das Makro einkopiert werden soll, wird dann der Makroname genannt (Makroaufruf).
4.3.2 Unterprogrammtechnik

Hier ist das Teilprogramm (Unterprogramm (UP)) nur einmal im Code vorhanden. Es wird durch eine Marke
(Unterprogrtammname) gekennzeichnet. An den Stellen, an denen das Unterprogramm ausgeführt werden soll
erfolgt der Aufruf durch einen Sprungbefehl mit dem Unterprogrammbezeichner als Operand. Am Ende des
Unterprogramms erfolgt die Rückkehr in das aufrufende Programm wiederum durch einen speziellen Sprungbefehl
auf die Rückkehradresse, d.h. die Adresse des Befehls, der im aufrufenden Programm nach dem Befehl zum Aufruf
folgt. Die Rückkehradresse wird gespeichert (Register, Stack).

4.3.3 Unterscheidungen und Probleme

Das Konzept der Funktionen und das Konzept der Prozeduren ist aus höheren Programmiersprachen abgeleitet
(z.B. C/C++, Pascal). Zwei grundsätzliche Fragen sind dabei zu betrachten: Wie erfolgt die Paramterübergabe und
wie werden die Ergebnisse zwischen dem aufrufenden Programm und dem Unterprogramm ausgetauscht. Die
Implementierung von lokalen Variablen der Funktion sind auch zu betrachten. Sichtbarkeit der Variablen ist sehr
wichtig dabei: Globale Variablen, stehen allen Funktionen eines Programmes zur Verfügung. Lokale Variablen,
stehen nur in der Funktion zur Verfügung. Während ihrer Lebensdauer besitzt eine Variable einen Speicherplatz.

4.3.4 Funktions- und Prozeduraufruf - ein Beispiel

Aufrufer: Ursprung des Funktionsaufrufs (hier main)

Aufgerufener: Aufgerufene Funktion (hier sum)

int main() {
int y;
y = sum (42, 7);
}
int sum(int a, int b) {
return (a+b);
}

4.3.5 Funktions- und Prozeduraufruf - Regeln

Aufrufer: Übergibt Argumente (aktuelle Parameter) an Aufgerufenen. Springt Aufgerufenen an.

Aufgerufener: Führt Funktion/Prozedur aus. Gibt Ergebnis (Rückgabewert) an Aufrufer zurück (für Funktion).
Springt hinter Aufrufstelle zurück. Darf keine Register oder Speicherstellen überschreiben, die im Aufrufer genutzt
werden.

4.3.6 Aufrufargumente und Rückgabewert

//Hochsprache
int main(){
int y;
y = diffofsums(14,3,4,5);
}
int diffofsums(int f, int g, int h, int i) {
int result;
result = (f +g) - (h + i);
return result;
}

//Assembler r4 = y
1 main:
2 mov r0,#14 //Argument 0 = 14
3 mov r1,#3 //Arg. 1 = 3
4 mov r2,#4 //Arg. 2 = 4
5 mov r3,#5 //Arg. 3 = 5
6 bl diffofsums // Funktionsaufruf
7 mov r4,r0 //y = Rückgabewert
8
9 diffofsums:
10 add r8,r0,r1
11 add r9,r2,r3
12 sub r4,r8,r9
13 mov r0,r4 //Lege Rückgabewert in r0 ab
14 mov pc,lr //Rücksprung zum Aufrufer

Nach Abarbeitung der Zeilen 3 - 6 sind die zu übergebenden Argumente in den Registern r0-r3 abgelegt.
Zeile 6 ruft das Unterprogramm mit dem Befehl bl (branch & link) auf. Dieser Befehl sorgt dafür, dass die
Rückkehradresse 7 in das Register r14 (lr) geschrieben wird. Das Unterprogramm beginnt an der Adresse 9. Nach
Durchführung der arithmetischen Operationen (Zeilen 10-12) wird das Ergebnis in das Register r0 geschrieben
(Zeile 13). r0 wird auch return value Register gennant. In Zeile 14 wird die zuvor gespeicherte Rückkehradresse (7)
aus dem Register r14 (lr) in das Register r15 (pc) kopiert. Der nächste auszuführende Befehl ist an der Adresse 7 zu
finden und lautet mov r4,r0.

4.4 Lernkontrolle

a) In welchem Register wird die Rücksprungadresse bei Ausführung des Befehls bl gespeichert?
A: Im Register r14 (lr)

b) Was ist der Unterschied zwischen einer Funktion und einer Prozedur?
A: Eine Funktion hat einen Rückgabewert, eine Prozedur hat keinen Rückgabewert.

5.1 Stack (Stapel- oder Kellerspeicher)

Der Stack ist ein Speicher für temporäres Zwischenspeichern von Werten, er agiert wie ein Stapel (Beispiel: Teller)
d.h. Zuletzt aufgelegter Teller wird zuerst heruntergenommen ("Last in, first out " (LIFO)). Der Stack dehnt sich aus
also belegt mehr Speicher, wenn mehr Daten unterzubringen sind und zieht sich zusammen, sobald weniger
Speicher belegt ist, wenn zwischengespeicherte Daten nicht mehr gebraucht werden.

Der Stack wächst bei ARM nach unten (von hohen zu niedrigen Speicheradressen), die übliche Realisierung
(deshalb auch Kellerspeicher gennant) heißt Stapelzeiger ("stack pointer") also der sp (r13). Er zeigt auf den zuletzt
auf dem Stack abgelegtes Datenelement.

5.1.1 Verwendung des Stacks in Unterprogrammen

Die Bedingung ist das aufgerufende Unterprogramme keine unbeabsichtigten Nebenwirkungen ("Seiteneffekte")
haben. Das Problem bei dem vorgestellten Programm "diffofsums" ist es überschreibt die drei Register r8,r9,r4.

//r4 = y
diffofsums:
add r8,r0,r1
add r9,r2,r3
sub r4,r8,r9
mov r0,r4
mov pc,lr

Stack variante:
diffofsums:
sub sp,sp,#12 //Speicher auf Stack reservieren
str r9,[sp,#8] //Sichern von r9 auf Stack
str r8,[sp,#4] //Sichern von r8 auf Stack
str r4,[sp] //Sichern von r4 auf Stack

add r8,r0,r1 //Rechnung

add r9,r2,r3
sub r4,r8,r9
mov r0,r4 //Rückgabewert in r0 legen

ldr r4,[sp] //Herstellen von r4

ldr r8,[sp,#4] //Herstellen von r8
ldr r9,[sp,#8] //Herstellen von r9
add sp,sp,#12 //Speicher auf Stack freigeben

mov pc,lr //Rücksprung zum Aufrufer

Hier zu sehen die Veränderung des Stacks während diffofsums.

5.1.2 Mehrfache Unterprogrammaufrufe

Sicherung von lr:

main:
mov r0,#14
mov r1,#3
mov r2,#4
mov r3,#5
mov r10,lr //Sichern der Rücksprungadresse in r10
bl diffofsums
mov r4,r0
mov lr,r10 //Herstellen der Rücksprungadresse
mov r0,r4
bx lr //Zurück zum Aufrufer
Push und Pop:
main:
mov r0,#14
mov r1,#3
mov r2,#4
mov r3,#5
push {lr} //Sichern der Rücksprungadresse auf dem Stack
bl diffofsums
mov r4,r0
pop {lr} //Herstellen der Rücksprungadresse
mov r0,r4
bx lr //Zurück zum Aufrufer

push und pop sind sogennante Pseudoinstruktionen.

5.2 Rekursion

Rekursiver Unterprogrammaufruf anhand des Beispiels Fakultätsberechnung.

//Hochsprache
#include <stdio.h>
int fak(int n) {
if (n >= 1) {
return fak (n-1) * n;
} else {
return 1; // 0! = 1
}
}

int main() {
int n = 3; //3! = 6
int z;
z = fak (n);
printf("Fakultaet: %d\n", z);
}
Vor der Umsetzung erstmals einige Überlegungen. Der Ablauf eines Unterprogramms wird auch als Inkarnation
(wiederholter Unterprogrammaufruf) bezeichnet.

Die Abbildung der Inkarnation zeigt, dass es zwei verschiedene Rückkehradressen gibt. Die Adresse RA_1 ist die
Adresse im Hauptprogramm, die Adresse RA_2 ist die Adresse im Unterprogramm.
Für alle Inkarnationen des Unterprogramms fak ist die Rückkehradresse RA_2 dieselbe Adresse, da alle
Inkarnationen Abläufe desselben Codes sind.

//Assembler
.data
mystring: .asciz "Fakultaet:%d\n"
.text
.global main //Einsprungspunkt Hauptprogramm

main:
push {lr}
mov r0,#3 //Fak von 3
bl fak //Funktionsaufruf UP

RA_1:
mov r1,r0 //Ergebnis UP in r1
ldr r0,=mystring
bl printf //Ausgabe Ergebnis
pop {lr}
bx lr //Zurück zum Aufrufer

fak:
sub sp,sp,#8 //Speicher Stack reservieren
str r0,[sp,#4] //Sichern von r0 auf Stack
str lr,[sp] //Sichern Rücksprungadresse
cmp r0,#1 //Rekursionsende pruefen
blt else //branch less
sub r0,r0,#1 // n-1
bl fak //Funktionsaufruf

RA_2:
ldr r1,[sp,#4] //laden von n
mul r0,r1,r0 // fak (n-1) * n

fin:
ldr lr,[sp] //Laden Rückkehradresse
add sp,sp,#8 //Speicher Stack freigeben
bx lr //Sprung zum Aufrufer

else:
mov r0,#1 //Rekursionsanker
b fin

Aufbau des Stacks:

Die Maximale Ausdehnung des Stacks (Stackpointer schwarze Linie). Die Rückkehradresse steht an SP, der Wert von
n and SP+4

5.2.1 Zusammenfassung Unterprogrammaufrufe

Der Aufrufer legt Aufrufparameter (aktuelle Parameter) in Registern oder auf dem Stack ab. Er sichert notwendige
Register auf dem Stack (z.B. lr). bl zum Aufgerufenen. Wiederherstellen von gespeicherten Registern (z.B. lr) und
hole evtl. Rückgabewert aus r0 (bei Funktionen).

Der Aufgerufener sichert zu erhaltende verwendete Registern auf dem Stack. Führt die Berechnung des
Unterprogramms aus. Legt den Rückgabewert in r0 (bei Funktionen). Stellt gesicherte Register wieder her und
macht den Rücksprung zum Aufrufer durch mov pc,lr Unter den Aufrufkonvention (calling convention) versteht
man die Methode, mit der einem Unterprogramm Daten übergeben werden.
5.3 Diskussion der Assemblerprogramme

//Hochsprache

//Übersetzt vom gcc (c -> assembler) mit gcc -S addidtion.c

//Selber in Assembler geschrieben

//Übersetzt mit Optimierungsstufe 1 (gcc -S -O1 addition.c)

Die Übersetzung eines Programms aus einer Hochsprache nach Assembler kann offenbar sehr verschiedene
Ergebnisse haben. Nicht alle in der Hochsprache sichtbare Sprachelemente werden in Assembler abgebildet.
Beispiele: Nicht jede lokale Variable wird au dem Stack sichtbar. Ggf. Realisierung von lokalen Variablen bei
Schleifen ausschließlich in Registern (Dies hängt auch davon ab, mit welcher Optimierungseinstellung ein Compiler
aufgerufen wird. Beim gcc sind das z.B. -O1 oder -O2). Bei Konstanten Variablen (=Konstanten) wird ggf. eine
sogennante Common subexpression elemination durchgeführt. Das bedeutet, dass Teilstücke zur Übersetzungszeit
berechnet werden und als Konstanten gespeichert werden.

5.4 Lernkontrolle

a) Erläutern Sie die Funktionsweise des Registers sp

A: Das Register sp ist das sogennante stack pointer Register. Es zeigt auf das zuletzt auf dem Stack abgelegte
Element.

b) Wie werden (lokale) Variablen üblicherweise realisiert?

A: Die Realisierung erfolgt auf dem Stack. Wenn ein Programm wenige Variablen hat, kann ein optimierenden
Compiler auch Programmcode erzeugen, der auf die Nutzung des Stacks verzichtet.

6.1 OpenMP

Bessere (parallele) Algorithmen zu implementieren ist häufig aufwändig. Thread Programmierung nicht trivial.
Eine Lösung ist OpenMP: Sammlung von Compiler-Anweisungen (Direktiven) und Bibliotheksfunktionen,
Kombination von C, C++ oder Fortran. Das Ziel ist threadparalleles Arbeiten auf Rechnersystemen mit
gemeinsamen Adressraum, ist gut geeignet für Multi-Core-Architekturen.

Ein Thread bzw. Prozess ist ein Betriebssystemkonzept zur Repräsentation eines Programms in der Ausführung.

Das Grundkonzept von OpenMP ist, dass OpenMP als einzelner Thread startet und dann für Codeabschnitte, die
parallel ausgeführt werden können, forkt (verzweigt) sich das Programm in zusätzliche Threads.
Diese Codeabschnitte werden als parallele Regionen bezeichnet. Sie werden am Schluss wieder zusammengeführt
(join) zu einem einzelnen Thread. Es wird auch das Fork-Join-Programmiermodell genannt.

OpenMP in der Praxis:

Einbinden von #include <omp.h>, Codeabschnitte parallelisieren.
Compileraufruf: gcc –fopenmp pi_omp.c
Setzen der Umgebungsvariable für die Anzahl der Threads: export OMP_NUM_THREADS=2

//Ohne OpenMP
#include <stdio.h>
#include <math.h>

int main(){
long i;
long num_steps = 2000000000;
double x,pi,step,sum = 0.0;
step = 1.0 / (double) num_steps;
for(i = 1; i < num_steps; i++) {
x = (i – 0.5) * step;
sum = sum + 4.0 / (1.0 + x * x);
}
pi = step * sum;
printf(„PI: %lf\n“, pi);
return 0;
}

//Ohne OpenMP
#include <stdio.h>
#include <math.h>
#include <omp.h>

int main(){
long i;
long num_steps = 2000000000;
double x,pi,step,sum = 0.0;
step = 1.0 / (double) num_steps;
#pragma omp parallel for private(x) reduction (+:sum)
for(i = 1; i < num_steps; i++) {
x = (i – 0.5) * step;
sum = sum + 4.0 / (1.0 + x * x);
}
pi = step * sum;
printf(„PI: %lf\n“, pi);
return 0;
}

Unterschiede der beiden Ausführungen ohne Parallelisierung und mit.

6.2 Funktionsweise eines Assemblers

Der Assembler übersetzt das Assemblerprogramm (MNEMONICS) in Maschinensprache.

Die allgemeinere Definition ist: Ein Assembler ist ein Programm, das die Aufgabe hat, Assemblerbefehle in
Maschinencode zu transformieren und dabei: Symbolische Namen (z.B. Labels bei Sprungmarken)
Maschinenadressen zu zuweisen und eine oder mehrere Objektdatei(en) zu erzeugen.

Assembler gibt es außerdem als:

- Crossassembler: Assembler läuft auf einem Rechnersystem X, generiert aber Maschinencode für eine
Platform Y. Kommt sehr häufig im Bereich der Embedded Systems vor (Intel IA32 als Entwicklungsplattform
=> ARM als Zielplattform)
- Disassembler: Übersetzung von Maschinensprache in Assemblersprache => Üblicherweise Verlust von
Kommentaren und symbolischen Namen.

Der Assembler übersetzt die Datei in Assemblersprache in eine Datei mit binären Maschinencode in zwei Schritten.
1. Schritt:
- Auffinden von Speicherpositionen mit Marken, so dass Beziehungen zwischen symbolischen Namen und Adressen
bei Übersetzung von Instruktionen bekannt sind.
- Übersetzung jedes Assemblerprogrammbefehls durch Kombination der numerischen Äquivalente der Opcodes,
Registerbezeichner und Marken in eine legale Instruktion.

2. Schritt: Assembler erzeugt ein oder mehrere Objektdateien, die Maschinencode, Daten, und
Verwaltungsinformationen enthält. Eine Objektdatei ist meist nicht ausführbar, da im Allgemeinen auf Funktionen,
Prozeduren oder Daten in anderen Dateien verwiesen wird.
Probleme beim 1. Schritt -> Nutzen von Marken bevor sie definiert sind.
Beispiel: Abarbeiten des Programms Zeile für Zeile, Befehle können Vorwärts-Referenzen enthalten
cmp r0,r1
beq there
orr r1,r1,#1
there:
add r1,r1,#78

Problem: Adresse von Sprungmarke there: ist beim ersten Auftreten unbekannt => korrekter Code kann nicht
erzeugt werden.

Lösung: Assembler macht 2 Läufe (Two-pass) über das Programm

1-ter Lauf (Phase): Zuordnen von Maschinenadressen
2-ter Lauf (Phase): Erzeugen des Codes

Probleme beim 2. Schritt => Erzeugen der Objektdatei (.o-Datei)

1. Fall:
- Assembler verwendet absolute Adressen und eine Objektdatei (Objektprogramm), dann ist das Laden unmittelbar
möglich, aber absolut adressiert bedeutet, der Speicherort muss vorher bekannt sein.
- Nachteil => Verschieben des Programms im Speicher ist nicht möglich.

2. Fall:
- Assembler verwendet relative Adressen und als Eingabe ggf. mehrere Programm-Segmente.
- Assembler-Ausgabe: >= 1 Objekt-Datei(en)
- Adressen werden relativ zu den einzelnen Objektdateien vergeben.
- Konsequenz daraus => weitere Transformationsschritte sind notwendig
=> Aufgabe des Binders/Linkers und Laders

6.3 Aufbau eines Objekt-Programms

Objekt-Programme (Im Folgenden Files) kommen in drei Formen vor

- Relocatable (verschiebbare) object files: Enthalten binären Code und Daten in einer Form, die mit anderen
verschiebbaren Objekt-Files zu einem ausführbaren Objekt-File zusammengefügt werden können.
- Executable object files: Enthalten binären Code und Daten in einer Form, die direkt in den Speicher kopiert und
ausgeführt werden können.
- Shared object files: Spezieller Typ von relocatable object files, welche in den Speicher geladen werden können
und dynamisch mit anderen Objekt-Files zusammengeführt werden können.

In der Regel generieren Compiler und Assembler relocatable object files.

Die ELF (relocatable object files) beginnt mit einer 16-Byte Sequenz
- Wort Größe
- Byte Ordering (Little Endian, Big Endian)
- Weitere Informationen, die vom Binder (Linker) verarbeitet werden z.B. Maschinentyp (ARM, IA32)

.text
Maschinencode des compilierten/assemblierten Programms

.rodata
Daten, die nur gelesen werden müssen, z.B. Formatierungsstrings in Ausgabefunktionen oder Sprungtabellen in
switch-Statements (!)

.data
Initialisierte globale Variablen

.bss (Block Storage Start, Better Save Space)

Uninitialisierte globale Variablen => belegt kein Platz im Objekt-File

.symtab
Symboltabelle mit Informationen über Funktionen und globale Variablen, die im Programm definiert bzw.
referenziert sind.

.rel.text
Eine Liste von Stellen im .text Segment, welche beim Linken modifiziert werden müssen (z.B. kombinieren mit
anderen Objekt-Files).

.debug
Debugging Symboltabelle => wird nur erzeugt, wenn C-Compiler mit der Option –g aufgerufen wird.

.line
Zuordnung der C-Anweisungen zu Maschinencode => wird nur erzeugt, wenn C-Compiler mit der Option –g
aufgerufen wird.
.strtab
Zeichentabelle für Symboltabelle und Debugging Symboltabelle

Beispiel (schleife.s):
.global main

main:
mov r0,#1
mov r1,#0
WHILE:
cmp r0,#256
beq DONE
lsl r0,r0,#1
add r1,r1,#1
b WHILE
DONE:
mov r0,r1
bx lr

Analysewerkzeuge sind z.B. gcc Toolchain, IDA (Interactive Disassembler) ist ein Disassembler, der es ermöglicht,
Binärcode in Assemblersprache umzuwandeln, Ghidra: Reverse-Engineering-Werkzeug der NSA (Open-Source)
6.4 Binder/Linker & Lader

Definition Binder/Linker:
Der Binder (engl. linker) hat die Aufgabe, aus einer Menge von einzelnen verschiebbaren Objekt-Files ein
ausführbares Objektprogramm zu erzeugen, indem die noch offenen externen Referenzen aufgelöst werden.

Das Objektprogramm kann durch einen Lader zur Ausführung gebracht werden.

Definition Lader:
Ein Lader (engl. loader) ist ein Systemprogramm, das die Aufgabe hat, Objektprogramme in den Speicher zu laden
und ggf. deren Ausführung anzustoßen.

Dazu wird das Objektprogramm in den Speicher kopiert.

6.4.1 Arbeitsweise eines Laders

Aufgabe des Laders:

- Ein Programmmodul (Lademodul) wird – beginnend mit einer vom Betriebssystem vorgegeben Startadresse – in
den Hauptspeicher geladen.

Varianten des Ladevorgangs:

- Absolutes Laden (Absolute Loading)
- RelativesLaden (Relocatable Loading)
- Dynamischen Laden zur Laufzeit (Dynamic Run-Time Loading)

6.5 Laufzeit und Analyse von Programmen

Für das Schreiben von effizienten Programmen muss man wissen, wo die Performance Bottlenecks sind. Unter Unix
(und Windows) sind verschiedene Programme zur Performance Analyse vorhanden.

Der gcc (und andere Compiler) können darüber Aussagen liefern

- gcc –pg –o sample sample.c (-pg ist ein run-time flag)
- ./sample (Aufruf des Programms, Programm läuft langsamer (ca. 25s))
- gprof sample gmon.out > analysis.txt (wertet die Profile-Datei aus)

fak_rek = Fakultät Rekursiv berechnen

fak_ite = Fakultät durch Schleifen berechnen.
7.1 Interpretation und Ausführung eines Befehls

Wie funktioniert die Verarbeitung eines Befehls bzw. der Daten in einem Rechnersystem?
=> Sowohl der Befehl, als auch die Daten stehen in dem Speicher(-system).

1. Die Aufgabe des Prozessors bzw. des Steuerwerks ist es, die Befehle aus dem Speicher zu lesen (bzw. die
Anweisung dafür geben). Diesen Vorgang bezeichnet man als Befehlsholphase (instruction fetch)
2. Wenn der Befehl geholt ist und in einem Register steht, muss er dekodiert werden. Diesen Vorgang bezeichnet
man als Befehlsdekodierung (instruction decode).
3. Als letztes wird der Befehl ausgeführt (Befehlsausführung (instruction execute)). Danach wird der nächste Befehl
aus dem Speicher geholt.

Man spricht hierbei auch von den drei Phasen der Befehlsausführung.

7.2 Takt und Taktfrequenz

Die Komponenten eines Rechnersystems müssen in der Regel eine gemeinsame Zeitbasis haben, damit das
Zusammenspiel funktioniert. Diese Zeitbasis nennt man auch Takt/Taktsignal/Systemtakt.

Hier zu sehen der Takt, er ist ein Rechtecksignal.

Er dient der Synchronisation der Komponenten eines Rechnersystems, deswegen auch Systemtakt.

Aus dem Rechtecksignal kann man die Periodendauer/die Taktfrequenz ableiten (f = 1/T).

Je höher die Taktfrequenz ist, desto schneller verarbeitet das Rechnersystem Daten.

7.2.1 Taktfrequenz – Bedeutung und Grenzen

Eine Leistungssteigerung wurde lange Zeit durch erhöhen der Taktfrequenz erreicht. Aktuell liegt der Prozessortakt
vieler Mikroprozessoren bei 3.x GHz. Bedingt durch die Technologie (CMOS-Technologie) steigt der Leistungsumsatz
der Prozessoren mit dem Takt (P ≈ U^2 * f * CL). Die entstehende Wärme ist nur mit großem Aufwand
abzutransportieren.
7.2.2 Terminologie

Im Kontext von Rechnerarchitekturen / Prozessorarchitekturen gibt es einige Begriffe, die im Folgenden erklärt
werden.

ISA – Instruction set architecture (Menge der verfügbaren Instruktionen / Befehle)

RISC – Reduced inctruction set computer (Kleine und schnelle ausführbare ISA), Beispiel ARM
CISC – Complex instruction set computer (Schwergewichtige ISA), Beispiel Intel
SIMD – Single instruction multiple data (vector processing), Beispiel NEON beim ARM
VLIW – Very long instruction word (static multi-issue), superscalar processors (dynamic multi-issue)

µarch – microarchitecture (ISA Implementierung)

- Anzahl der Instruktionen/Befehle pro Zyklus (IPC (Instructions per cycle))
- Pipelining für Instruktionslevel Parallelismus (ILP (Intruction level parallelism))
- Sprungvorhersage (engl. branch prediction)
- out-of-order execution von Befehlen (engl. dynamic instruction scheduling)
- multi-issue systems (engl. start multiple operations per cycle)

7.3 Mikroarchitektur - Einführung

Mikroarchitektur: Hardware-Implementierung einer Architektur

Prozessor/Rechnersystem:
- Datenpfad: verbindet funktionale Blöcke
- Kontrollpfad: Steuersignale / Steuerwerk

Es sind mehrere Implementierungen für eine Architektur (hier ARM) möglich. Der Unterschied ist die
Unterscheidung vom Takt bzw. die Art der Befehlsausführung.

Eintakt-Implementierung (Im Folgenden wird der Begriff Eintakt-Prozessor verwendet):

Jeder Befehl wird in einem Takt ausgeführt.

Mehrtakt-Implementierung:
Jeder Befehl wird in Teilschritte zerlegt.

Pipelined-Implementierung:
Jeder Befehl wird in Teilschritte zerlegt. Mehrere Teilschritte werden gleichzeitig (parallel) ausgeführt.

7.3.1 Rechenleistung eines Prozessors

Die Ausführungszeit eines Programmes lässt sich wie folgt berechnen. Ausführungszeit = (#Instruktionen) *
(Takte/Instruktionen) * (Sekunden/Takt)

Takte/Instruktionen = CPI (cycles per instruction)

Sekunden/Takt = Taktperiode
1/CPI = Instruktionen/Takt = IPC (inctructions per cycle)

Dabei muss man die zusätzlichen Anforderungen einhalten: Kosten, Energiebedarf, Rechenleistung.
7.4.1 Mikroarchitektur ARM

Die Untermenge des ARM Befehlssatzes:

- Speicherbefehle: ldr,str
- Arithmetische/logische Befehle: add,sub,and,orr
- Sprungbefehle: b

7.4.2 Architekturzustand

Der Architekturzustand (auf Ebene der Architektur sichtbare Daten) sind für den Programmierer zugänglich.

Die folgenden sichtbaren Daten bestimmen den Zustand der Architektur:

- PC (Program Counter, Befehlszähler)
- 16 Register
- Speicher

Die Elemente des Architekturzustands:

7.4.3 Von-Neumann-Architektur, Havard-Architektur, Speicher

Die Von-Neumann-Architektur hat einen gemeinsamen Speicher für Maschinenbefehle und Daten. Im Gegensatz zur
Havard-Architektur hier sind Befehlsspeicher und Datenspeicher getrennt.

Das Verhalten des Speichers, die Speicher können, bezogen auf den Takt, asynchron gelesen werden und die Speicher
werden synchron mit dem Takt geschrieben.
7.4.4 Eintakt-Prozessor, Vorgehensweise und Bitfelder eines Befehls

7.4.5 Eintakt-Prozessor, Phasen der Befehlsausführung

Beispiel ldr Befehlsholphase:

Der Datenpfad ldr Zugriff auf PC:
Der PC kann Quelle oder Ziel bei Instruktionen sein.
- Quelle: r15 muss im Registerfeld verfügbar sein. PC wird gelesen als aktueller PC + 8 (Zitat: aus
historischen Gründen)
- Ziel: Es muss möglich sein, PC als Zielregister zu verwenden.
Beispiel Erweiterung Datenpfad str:
Datenpfad für arithmetische/logische Befehle:
7.4.6 Arithmetische Logische Einheit (ALU)
7.4.7 Eintakt-Prozessor, Sprungbefehl b

7.4.8 Eintakt-Prozessor, ExtImm

ExtImm:

Funktionserklärung der Einheit ExtImm:

- Für die bisher vorgestellten Befehle sind unterschiedliche Funktionen notwendig.
- Die arithmetischen/logischen Befehle erlauben einen 8 Bit Wert als Direktwert und müssen entsprechend
um 24 Bit erweitert werden (vgl. Zeile 1 in Tabelle).
- Im Befehl ldr besteht die Möglichkeit, einen Direktwert der Breite 12 Bit zu speichern. Dieser Wert muss
für die Adressrechnung auf 32 Bit erweitert werden. Es ist also notwendig, dass der Wert mit 20 Nullen zu
einem 32 Bit Wert konkateniert wird (vgl. Zeile 2 in Tabelle).
- Im Befehl b wird das Sprungziel als 24 Bit Adresse angegeben. Es ist eine vorzeichenrichtige Erweiterung
vorzunehmen (vgl. Zeile 3 in Tabelle).
7.4.9 Eintakt-Prozessor, Datenpfad und Kontrolleinheit

Kontrolleinheit:
Beispiel add r1,r2,r3:
Beispiel orr r1,r2,#f0:

Beispiel andeq r5,r6,r7:

7.5 ARM Instruction Set

The Condition Field:

Arithmetische/logische Befehle:
7.6 Lernkontrolle

a) Wann ist es sinnvoll, Programme direkt in Assembler (statt in C oder JAVA) zu schreiben?
A: Wenn der Speicher knapp ist, Programmierung von Echtzeitsysteme mit kritischen Antwortzeiten, Wenn
Handoptimierungen aus Performanzgründen notwendig sind, Wenn direkter Zugriff auf den Prozessor nötig
ist.

b) Nennen Sie einige Vorteile einer Hochsprache wie C gegenüber Assembler

A: Kontrollstrukturen sind vorhanden, Besseres Verständnis des Codes, Datenstrukturen sind vorhanden,
Type-Checking, Bessere Wartbarkeit des Codes.

8.1 Mehrtakt-Prozessor

Zustandselemente im Mehrtakt-Prozessor:
Ersetze getrennte Instruktions- und Datenspeicher (Havard-Architektur) durch einen gemeinsamen
Speicher (Von-Neumann-Architektur, heute weiter verbreitet)

8.1.1 Mehrtakt-Prozessor, Instruktion holen

Beispiel Erweiterung für str:

Beispiel arithmetische/logische Befehle:

Beispiel Sprungbefehl b:
8.1.2 Mehrtakt-Prozessor, Datenpfad und Kontrolleinheit

Datenpfad:

Kontrolleinheit:
Kontrolleinheit genauer im Detail:

8.1.3 Mehrtakt-Prozessor: Steuerwerk

Hier anhand des Beispiels Fetch:

Decode ldr:
Steuersignale sind so lange 1, wie sie in Zuständen dediziert auf 1 gesetzt sind.
Beispiel: IRWrite; dieses Signal ist im Zustand S0 auf 1 gesetzt und in allen weiteren Zuständen 0
Execute ldr:
Execute ldr, mit den richtigen Bezeichnungen der Steuersignale:
8.2 Eintakt-Prozessor vs. Mehrtakt-Prozessor

Eintakt-Prozessor:
+ Einfach
- Taktfrequenz wird durch langsamste Instruktion bestimmt.
- Drei Addierer / ALUs und zwei Speicher

Mehrtakt-Prozessor:
+ Höhere Taktfrequenz
+ Einfachere Instruktionen laufen schneller
+ Bessere Wiederverwendung von Hardware in verschiedenen Takten
- Aufwendigere Ablaufsteuerung

Der Eintakt-Prozessor und der Mehrtakt-Prozessor haben die gleichen Grundkompenten:

- Datenpfad: verbindet funktionale Blöcke
- Kontrollpfad: Steuersignale/Steuerwerk

8.3 Lernkontrolle

a) Was ist der Unterschied zwischen einem Eintakt-Prozessor, einem Mehrtakt-Prozessor und einem
Pipelined-Prozessor?
A: Beim Eintaktprozessor wird jede Instruktion in einem Takt ausgeführt. Beim Mehrtaktprozessor hingegen
kann dies mehrere Takte dauern. Jede Instruktion wird also in Teilschritte zerlegt. Beim Pipelined-Prozessor
werden die Instruktionen ebenfalls in Teilschritte zerlegt und die Teilschritte mehrerer Instruktionen (ggf.)
gleichzeitig ausgeführt.

b) Warum benötigt das Registerfeld in dem vorgestellten Prozessor ein Write Enable Signal?
A: Da das Registerfeld nicht bei jedem Befehl überschrieben werden darf.

c) Erläutern Sie anhand des Datenpfads wie bei einem ldr/str Befehl die Adresse berechnet wird.
A: Zur Berechnung wird eine Addition mit der ALU ausgeführt. Am Eingang SrcA liegt der Wert des
Registers, das die Basisadresse enthält, an. An SrcB liegt der erweiterte Immediate-Teil des Befehls.

d) Worin unterscheidet sich eine Von-Neumann-Architektur von einer Harvard-Architektur

A: Von-Neumann-Architektur: gemeinsamer Speicher für Maschinenbefehle und Daten.
Havard-Architektur: Befehlsspeicher und Datenspeicher sind getrennt.

e) Welcher Teil des Prozessors bestimmt, welche Rechenoperationen die ALU ausführt?
A: Das Steuerwerk bestimmt ALUControl.

f) Durch was wird die Taktfrequenz beim Eintakt-Prozessor bestimmt?

A: Die langsamste Instruktion bestimmt die Taktfrequenz. Die Taktfrequenz ergibt sich aus den
Verzögerungszeiten im Datenpfad.
9.1 Pipeline-Prozessor

Die Phasen der Befehlsausführung werden beim ARM Prozessor in fünf Phasen eingeteilt.
- Instruction Fetch
- Instruction Decode, Read Register
- Execute ALU
- Memory Read/Write
- Write Register

Abstrakte Darstellung:
9.1.1 Pipeline-Prozessor - Datenpfad

Datenpfad (korrigiert):
Datenpfad Optimierungen:

9.1.2 Pipeline-Prozessor – Datenpfad & Kontrolleinheit

9.2 Hazards

Hazards = Abhängigkeiten zwischen Pipeline Stufen.

Sie treten auf wenn eine Instruktion vom Ergebnis einer vorhergehende abhängt und diese aber noch kein
Ergebnis geliefert hat.

Arten von Hazards:

- Data Hazards: z.B. Neuer Wert von Register noch nicht in Registerfeld eingetragen
- Control Hazard: Unklar welche Instruktion als nächstes ausgeführt werden muss (tritt bei Verzweigungen
auf)

Data Hazard:

Umgang mit Data Hazard:

Möglichkeiten:
- Plane Wartezeiten von Anfang an ein.
- Füge nops (no operations) zur Compile-Zeit ein
- scheduling (Ablaufplanung)
- Stelle Maschinencode zur Compile-Zeit um
- scheduling / reordering
- Leite Daten zur Laufzeit schneller über Abkürzungen weiter
- bypassing / forwarding
- Halte Prozessor zur Laufzeit an bis Daten da sind
- stalling
Data Hazard mit nops:

Data Hazard mit bypassing / forwarding:

Pipeline-Prozessor: Datenpfad, Kontrolleinheit und Hazard-Unit:

Data Hazard – ldr:

Data Hazard – stall:

Pipeline-Prozessor: Datenpfad, Kontrolleinheit, Hazard- & Stall-Unit

Control Hazards:
9.3 Pipeline-Prozessor: Datenpfad, Kontrolleinheit, Hazard, Stall & Controll-
Unit
9.4 Lernkontrolle

a) Vergleichen Sie die Eigenschaften eines Eintakt-Prozessors mit den Eigenschaften eines Mehrtakt-
Prozessor.
A:
Eintakt-Prozessor:
+ einfach
- Taktfrequenz wird durch langsamste Instruktion bestimmt
- Drei Addierer / ALUs und zwei Speicher

Mehrtakt-Prozessor:
+ Höhere Taktfrequenz
+ Einfachere Instruktionen laufen schneller
+ Bessere Wiederverwendung von Hardware in verschiedenen Takten
- Aufwendigere Ablaufsteuerung.

b) Die langsamste Instruktion bestimmt bei einem Eintakt-Prozessor die Taktfrequenz. Die langsamste
Instruktion ldr benötigt zur Ausführung 6ns. Mit welcher Taktfrequenz kann der Eintakt-Prozessor maximal
getaktet werden.
A: Taktsignal: Periodendauer/Taktfrequenz (f = 1/T) 6 ns entsprechen einem Takt von 166666666.67 Hz
oder 166,67 MHz.

10.1 Gleitkommazahlen

Zahlendarstellung in Rechnersystemen: Man unterscheidet zwischen ganzen Zahlen (Integer) und reelen
Zahlen (Real).
10.1.1 Darstellung reeller Zahlen

Es gibt zwei verschiedene Darstellungen für reelle Zahlen.

- Festkommadarstellung
- Gleitkommadarstellung

Zur Festkommadarstellung:
- Bei der Festkommadarstellung lässt man bei internen Zahlenabbildung das Komma weg und merkt sich,
wo es stehen müsste.
- Zum Programmbeginn wird die Kommastelle der entsprechenden Variablen definiert und bleibt dann
während des Programms fest.

Gleitkommadarstellung nach ANSI/IEEE 754:

- Bei der Gleitkommadarstellung (auch halblogarithmetische Darstellung gennant) ist die Kommastelle
Bestandteil der Zahl und kann dadurch auch im Laufe der Berechnung verändert werden.
- Durch eine standardisierte Schreibweise bzw. Darstellung braucht man dabei das Komma nicht explizit
anzugeben.
- Die Floatingpoint-Darstellung ist standardisiert nach ANSI/IEEE 754 (US-American National Standard
Institute / Institute of Electrical und Electronics Engineers).

Im IEEE 754 Standard sind single, double und extended precision (Genauigkeit) Formate definiert.

Abbildung der Formate:

Keine Zahl = NaN: not a number, z.B. Division durch Null, Ergebnis der Quadratwurzel einer negativen Zahl.
10.1.2 Verarbeitung reeller Zahlen in ARM-Prozessoren

Vorgehensweise:
- Code-Analyse
- Studium der Datenblätter/Handbücher
- Code-Analyse und Studium der Datenblätter / Handbücher

Bemerkung: Bzgl. Der Nutzung von Gleitkommazahlen/Gleitkommaoperationen in Eingebetteten Systemen

gibt es auch die Auffassung, dass man diese aufgrund von Geschwindigkeitsgründen vermeiden sollte
(Sollte ein Eingebettetes System keine Hardware-Unterstützung haben, dauern Gleitkommaoperationen
verhältnismäßig lang.)

10.2 Code-Analyse

C-Programm zur Addition von zwei Gleitkommazahlen (32 Bit)

Assembler-Programm zur Addition von zwei Gleitkommazahlen (32 Bit)

Analyse des Assemblerprogramms:
- Speicherung des Konstanten (im Dezimalsystem)
- p = 5.4 -- 1085066445, s.u.
- q = 12.6 – 1095342490
- 0100 0000 1010 1100 1100 1100 1100 1101 - Umrechnung
- 0100 0000 1010 1100 1100 1100 1100 1101 - Errechnung
- Neue Befehle und Register
- vldr.32, vadd.f32,…
- s14,s15,d7

C-Programm zur Addition von zwei Gleitkommazahlen (64 Bit)

Assembler-Programm zur Addition von zwei Gleitkommazahlen (64 Bit)

Analyse des Assemblerprogramms:
- Speicherung der Konstanten (im Dezimalsystem)
- p = 5.4 -- -1717986918 1075157401
- q = 12.6 -- 858993459 1076441907
- Neue Befehle und Register
- strd, vldr.64, vadd.f64, ...
- d6, d7, ..

CPU-Informationen unter Linux cat/proc/cpuinfo

10.3 Studium der Datenblätter/Handbücher

- Suche im Internet nach Datenblättern / Handbüchern (ARM Floating Point)

-> Ergebnisse:
- Datenblätter / Handbücher zum Programmiermodell (Registersatz/Befehle)
- Datenblätter / Handbücher zur Hardware-Architektur

Handbuch zum Programmiermodell – Registersatz:

Handbuch zum Programmiermodell – Befehle

Es gibt offenbar zwei „Möglichkeiten“ Gleitkommazahlen zu verarbeiten:

- eine Funktionseinheit NEON
- eine Funktionseinheit VFP
Das Handbuch Assembler Guide vermerkt auf Seite 5-9, dass die Funktionseinheiten NEON und VFP die
gleichen Register verwenden.

10.3.1 Mögliche Realisierung einer Gleitkommaeinheit

Die Technik, die Berechnung von Gleitkommazahlen in sogennante Gleitkomma-Coprozessoren auszulagern

wird schon sehr lange verwendet. Die Gleitkomma-Coprozessoren besitzen häufig separate Instruktions-
Pipelines, z.B. Multiplikations und Additions (FMAC) Pipeline und die Divisions und Quadratwurzel (DS)
Pipeline.

Die Pipelines können auch unabhängig voneinander operieren.

Analyse der Assembler-Programme – Köpfe:

10.4 SIMD (Single Instruction Multiple Data)-Einheit ARM NEON

Zur Beschleunigung von Berechnungen (Ganzahl und Gleikommazahlen) werden dedizierte

Funktionseinheiten in Prozessoren integriert. Beim ARM Prozessor hat diese Funktionseinheit die
Bezeichnung NEON. In zahlreichen Prozessoren wurden Funktionseinheiten zur Beschleunigung eingebaut
(z.B. Intel SSE: Streaming SIMD Extensions). Sie finden oft Anwendung in der Verarbeitung von
Multimediadaten/Bildern.

10.4.1 Die Klassifikation von Flynn

Aufteilung in sogenannte Instruction Streams und Data Streams.

Instruction Stream:
- SI – Single Instruction
- MI – Multiple Instruction (mehrere Befehle zu einem Zeitpunkt)

Data Stream:
- SD – Single Data
- MD – Multiple Data

Ergibt dann vier Kombinationen:

- SISD – Von-Neumnn-Rechner
- SIMD – Feldrechner, Vektorrechner
- MIMD – Multiprozessorsysteme
- MISD - ?
Die Klassifikation von Flynn, ist eine grobe Klassifikation, denn verschiedene Aspekte werden nicht oder
grob erfaßt wie,
- Pipelining
- Wortbreite
- Verbindungsstrukturen
- Speicherorganisation
- lokale/globale Speicher, Virtueller Speicher, Caches
- Trennung von Programm- und Datenspeicher
Aber die Begriffe haben sich etabliert.

10.4.2 SIMD-Einheit ARM NEON

Der NEON ist eine SIMD-Einheit in den ARM Cortex-A Serie Prozessoren. Die SIMD-Einheit beschleunigt
zahlreiche Anwendungen wie Signalverarbeitung, Video Encodierung/Decodierung, Bildverarbeitung usw.

NEON Befehle führen „Packed SIMD“ aus

- Register werden als Vektoren von Elementen desselben Datentyps betrachtet
- Verschiedene Datentypen sind möglich
- Die Ausführung der Befehle in sogennanten „lanes“ erfolgt gleichzeitig

Es gibt eine separate Register-Bank mit 32x 128 bit Registern. Diese Register können 8/16/32/64 bit Integer
verarbeiten.

Bis zu 16x8 bit Operationen pro Befehl möglich.

Befehle des NEONS:
- Die Befehle haben das folgende Format: V{<mod>}<op>{<shape>}{<cond>}{.<dt>}{<dest>}, src1, src2
- Dabei sind folgende Modifier (mod) möglich: Q = Der Befehl nutzt Saturations-Arithmetik

10.4.3 Saturations-Arithmetik

Kennzeichen der Saturations-Arithmetik: Die Resultate von Operationen wie Addition und Multiplikation
sind auf einen festen Bereich zwischen einem minimalen und maximalen Wert begrenzt.
Das Resultat einer Operation, welches Größer als das Maximum ist, wird auf das erlaubte Maximum
gesetzt. Resultate kleiner als das Minimum werden auf das erlaubte Minimum gesetzt.

Beispiel: Der gültige Bereich einer Operation wurde auf -40 bis +40 festgelegt.
20+10 = 30
20-42 = 40 (und nicht 62)

10.4.4 NEON Programmierung

Es gibt vier Wege, NEON zu nutzen

- NEON optimized libraries (OpenMax DL, Ne10)
- Vectorizing compilers (gcc)
- NEON intrinsics
- NEON assembly
Und natürlich das NEON Programmers Guide.
10.5 Lernkontrolle

a) In welche Phasen wird die Ausführung einer Instruktion bei dem vorgestellten Pipelined-Prozessor
unterteilt?
A: Fetch-, Decode-, Execute-, Memory- und Writeback-Phase.

b) Was versteht man unter einem Hazard?

A: Hazards sind Abhängigkeiten zwischen Pipeline-Stufen. Man unterscheidet zwischen Data- und Control-
Hazards. Data-Hazards treten auf, wenn Daten gelesen werden, die jedoch von einer der vorherigen
Instruktionen noch nicht vollständig bearbeitet worden sind. Da erste relativ spät in der Pipeline
entschieden wird, ob ein Sprung vorliegt oder nicht, können die folgenden ausgeführten Instruktionen
unter Umständen nicht die gewünschten sein. Dies wird als Control Hazard bezeichnet

c) Bei der Entwicklung von modernen Prozessoren werden viele Ressourcen in die Verbesserung der
Sprungvorhersage gesteckt. Warum wirkt sich ein falsch vorhergesagter Sprung negativ auf die
Performance aus?
A: Falls ein Sprung falsch vorhergesagt worden ist, müssen die falschen Instruktionen verworfen werden.
Wäre der Sprung korrekt vorhergesagt worden, hätten die Takte für die Berechnung der falschen
Instruktionen genutzt werden können.

d) Bei Prozessoren unterscheidet man zwischen in-order oder out-of-order Ausführung von Instruktionen.
Welcher Ansatz ist schneller? Können Sie sich auch Einsatzszenarien für den anderen Ansatz vorstellen?
A: Die out-of-order Ausführung ist schneller, da durch die Umsortierung der Befehle Stalls vermieden
werden können und die Pipeline besser ausgelastet werden kann. Die Einheiten zur Selektion der nächsten
Instruktion belegen jedoch Siliziumfläche. Dies treibt die Herstellungskosten und die Leistungsaufnahme in
die Höhe. Deswegen wird bei manchen günstigen oder sparsamen Prozessoren auf in-order Ausführung
gesetzt.

10.1 Speicher

Bisheriges Modell des Rechnersystems war: Drei Phasen der Befehlsausführung, Prozessor (CPU) mit
Registern (r0,…) und Speicher (var1: .word 5)

In diesem Modell besteht der Speicher (das Speichersystem) als ein lineares Feld aus Bytes. Die CPU kann
auf jede Speicherzelle in konstanter Zeit zugreifen. Es ist ein einfaches Modell, welches die Realität
moderner Rechnersysteme nicht abbildet. In der Praxis wird ein Speichersystem verwendet, welches eine
Hierarchie unterschiedlicher Speichertechnologien und –techniken darstellt.

Das Lesen und Schreiben in einen Speicher dauert eine gewisse Zeit. Im Vergleich zur Taktfrequenz eines
Mikroprozessors ist diese Zeit relativ lang. Wenn ein Speicher (von Neumann-Architektur) vorhanden ist,
müssen sowohl die Befehle, als auch die Daten aus einem Speicher (nacheinander) geholt werden.
Bei einer Havard-Architektur mit getrennten Speichern kann sowas ggf. auch parallel ausgeführt werden.
Außerdem können sogenannte Pipelinestufen eingeführt werden.
10.1.1 Speicherhierarchie

Eigenschaften von Speichern:

- Kosten und Zugriffzeit
- Geschwindigkeit und Kapazität
- Zugriffverfahren
- Änderbarkeit der Daten
- Permanenz der Daten

Kosten und Zugriffzeit:

Die Kosten werden in Dollar/Bit oder Dollar/Mbyte gemessen.
Kenngröße von Speichern:
- Zugriffzeit: durchschnittliche Zeit, um ein Wort aus dem Speicher zu lesen
- Zykluszeit: minimale Zeit zwischen zwei Speicherzugriffen, hier spielt neben der Zugriffzeit auch das
Busprotokoll eine Rolle.
- Bandbreite (Datenübertragungsrate): Maximale Datenmenge, die pro Sekunde übertragen werden kann,
gemessen in Byte/sec.

Die Entwicklung der Kosten und Zugriffzeit beruht sich auf: geringere Zugriffzeit, höhere Kosten!
Zugriffsverfahren:
Speicherk können nach den beiden folgenden Zugriffsverfahren klassifiziert werden: wahlweiser Zugriff
(Random Access) oder der serielle Zugriff

Speicher mit Random Access Zugriff:

- Register
- Cache-Speicher
- Hauptspeicher

Speicher mit seriellem Zugriff:

- Festplatte
- Optische Platten
- Magnetband

Speicher können bezüglich der Änderbarkeit in folgenden Kategorien eingeordnet werden:

Read-Only:
- Der Speicher kann ausschließlich gelesen werden
- Ein Überschreiben ist nicht möglich

Read-Write:
- Inhalt kann während des Betriebs geändert werden

Read-Mostly:

Beispiele:
Read-Only Speicher: ROM-Halbleiterspeicher (Read-only Memory). Der Inhalt des Speicher wird während
des Fabrikationsprozesses festgelegt.

Read-Write Speicher: RAM-Halbleiterspeicher (Random-access Memory). Wird als Cache- oder

Hauptspeicher verwendet. Festplatten, CD-R(W), DVD

Read-mostly: PROM-Halbleiterspeicher oder (E)EPROM: z.B. für BIOS verwendet.

Speicher können bezüglich der Permanenz in zwei Klassen eingeteilt werden.

Flüchtiger Speicher: der Inhalt geht bei Stromausfall verloren.
Nicht flüchtiger Speicher: Der Inhalt bleibt bei Stromausfall erhalten.

Flüchtige Speicher werden unterteilt in:

- Dynamische Speicher: Um Informationsverlust zu vermeiden, muss die Spannung periodisch erneuert
werden (Refreshing).
- Statische Speicher: Kein Refreshing notwendig.

Flüchtige Speicher sind: Register, Hauptspeicher

Nicht flüchtige Speicher sind: ROM, PROM, EPROM, Festplatte, optische Speicher, Band
10.1.2 Speichertechnologien – Random-Access Memory (RAM)

Random-Access Memory (RAM) gibt es in zwei Varianten:

- Statisches RAM (SRAM)
- Dynamisches RAM (DRAM)

SRAM ist schneller und deutlich teurer als DRAM

SRAM wird im Cache verwendet.

DRAM wird im Hauptspeicher verwendet.

Die typische Verteilung auf einem Rechner:

- 12 MB SRAM
- 4 GB DRAM

RAM Organisation:
Das Statische RAM speichert Informationen so lange, wie die Spannungsversorgung angeschaltet ist.
Die gekoppelten Inverter haben zwei stabile Zustände => Bistabile Schaltung.
Das dynamische RAM speichert die Informationen in einem Kondensator:

Sie wird als 1T-Zelle bezeichet.

Der Kondensator entlädt sich und verliert damit die Information.
Der Refresh-Zyklus ist notwendig, um Informationen aufzufrischen.
10.2 Speicherorganisation

Eigenschaften eines RAM-Chips sind durch zwei Größen gegeben:

- Anzahl adressierbarer Plätze
- Breite (in Bit) jedes Adressierbaren Platzes

Beispiel: 256K x 1 SRAM

- 256K Einträge mit 1 Bit Breite
- 256K = 218, also 18 Adresseingänge sowie ein 1 Bit Dateneingang/-ausgang

32K x 8 SRAM
- 32K Einträge mit 8 Bit Breite
- 32K = 215, also 15 Adresseingänge sowie 8 Bit Dateneingang/-ausgang
10.3 Lokalität

Für eine funktionierende Speicherhierarchie ist Lokalität wichtig.

Das Lokalitätsprinzip stellt fest: Eine Eigenschaft bei der Ausführung von Programmen ist, dass meistens nur
auf einen relativ geringen Teil des Adressraumes zugriffen wird.

Formen der Lokalität:

- Zeitlich (temporale) Lokalität
- Nach Zugriff auf einen bestimmen Datensatz wird mit großer Wahrscheinlichkeit bald erneut darauf
Zugegriffen.
- Räumliche Lokalität:
- Nach dem Zugriff auf einen bestimmten Datensatz wird mit großer Wahrscheinlichkeit auch auf einen
Datensatz zugegriffen, der in unmittelbarer Nähe im Speicher steht.
- Beispiel: Sequentielle Instruktionsfolgen (Ohne Sprünge)
- Beispiel: Reihungen, Matrizen.

Vorteile der Lokalität:

- Gut geschriebene Programme haben eine gute Lokalität
- Die Anwendung des Lokalitätsprinzips hat eine enorme Auswirkung auf die Performance eines
Rechnersystems (Hardware/Software).
- Programme mit guter Lokalität laufen schneller, als Programme mit schlechter Lokalität
- Zweifache Unterscheidung ist möglich: Lokalität der Daten & Lokalität der Befehle
Lokalität der Befehle:
- Wie die Daten sind auch die Befehle im Speicher abgelegt
- Auch für die Befehle ist also das Lokalitätsprinzip anwendbar
- Für die for Schleifen der Beispiele gilt eine gute räumliche Lokalität, da der Schleifenkörper wiederholt
ausgeführt wird, gibt es auch eine gute zeitliche Lokalität
- Bei der Programmierung an das Lokalitätsprinzip denken!
- Lokalitätsprinzip läßt die Speicherhierarchie funktionieren
10.4 Prinzip des Caches

Ein Cache ist ein kleiner und schneller Speicher (SRAM)

Der Prozess, einen Cache zu benutzen wird auch als caching bezeichnet.
Es ist die zentrale Idee der Speicherhierarchie. Ein schneller und kleinerer Speicher auf dem Level k fungiert
als Cache für einen langsameren und größeren Speicher auf dem Level k+1. Ein Vergleich mit der
Speicherhierarchie zeigt, dass das mehrfach angewendet wird. Deshalb ist das Lokalitätsprinzip für eine
sinnvolle Nutzung der Speicherhierarchie notwendig.

Cache Hits:
Wenn ein Programm Daten von einem Objekt d braucht, wird geschaut, ob d in einem der Blöcke auf dem
Level k gespeichert ist. Wenn d in dem Cache auf Level k gefunden wird, nennt man das einen Cache Hit.
Das Programm liest dann d direkt aus dem Level k, da Level k schneller ist, als Level k+1 ergibt sich dadurch
ein Geschwindigkeitsvorteil.

Bemerkung: Auch wenn L1,L2 und L3 Cache alle als SRAM ausgeführt sind, gibt es trotzdem
Geschwindigkeitsunterschiede.

Cache Miss:
Wenn ein Programm Daten von einem Objekt d braucht, wird geschaut, ob d in einem der Blöcke auf dem
Level k gespeichert ist. Wenn d in dem Cache auf Level k nicht gefunden wird, nennt man das einen Cache
Miss.
Bei einem Cache Miss holt der Cache auf dem Level k den Block mit d von dem Cache auf Level k+1.
Möglicherweise muss dann ein existierender Block (wenn Cache auf Level k voll ist) überschrieben werden.
Der Prozess des Überschreibens wird auch als Ersetzung bezeichnet. Die Entscheidung, welcher Block
ersetzt wird, kann mit unterschiedlichen Strategien erfolgen: Zufallsersetzung oder die Least-recently used
(LRU) Ersetzung.
10.5 Cachehierarchie ARM / Intel Core i7

Cachehierarchie ARM A53

- Getrennte Caches für Daten (d-cache) und Instruktionen (i-cache) auf Level 1

Cachehierarchie Intel Core i7:

- Getrennte Caches für Daten (d-cache) und Instruktionen (i-cache) auf Level 1
- Alle SRAM Cache Speicher sind auf dem CPU Chip (on die).
- Charakteristische Werte
Anordnung und Organisation des Cache Speichers: