be    empty
nop
ld    [%o0],%l0
cas   [%i0],%o0,%l0
cmp   %o0,%l0
bne   retry
empty:
nop

1.2.2.8 Adressierungsarten

• unmittelbare (immediate) Adressierung: MOV AX,0FFFFH, wobei der Bestandteil 0FFFFH die zu übertragenden Daten darstellt

• direkte Adressierung: MOV AX,MYDATA, dabei ist MYDATA die Adresse der zu übertragenden Daten

• (Register-) indirekte Adressierung: MOV AX,[BX], d.h. die Adresse der zu übertragenden Daten steht in BX

• indirekte Adressierung mit 8/16-Bit Displacement:

MOV AX,4[SI]

MOV AX,MYDATA[SI] MOV AX,ELEM[BX][DI]

1.2.2.9 Beschleunigter Datentransfer und beschleunigte Ausführung von Befehlen

Cache:

Es sei an den von-Neumannschen-Falschenhals erinnert:

CPU + Register Speicher

Abhilfe schafft hier der Cache-Speicher:

16 kB MIPS R4000 CPU  Register 800 MB/s Datenbus 4 MB externer Cache  interner Cache 1200 MB/s Memory 80ns  400 MB/s Speicherzugriff langsamer

Bemerkungen:

• 80ns ↔ \frac{1}{80·10^{−9}s} = 12.5 · 10^{6} Zugriffe/s

• Bus: 50 MHz und 8 Byte Busbreite führen zu 400 MB/s

• Im SIMM müssen also 32 Bit-Zugriffe parallel erfolgen

• Externer und interner Cache bilden einen Puffer, der mit look ahead bei einer Trefferquote von ∼ 90 − 95% betrieben wird.

• Es handelt sich um eine schnelle CPU mit 100MHz; also ergeben sich bei einem Durchsatz von 1200 MB/s durchschnittlich ≤ 12B pro Taktperiode ≤ 3 Worte/Eintakt-Befehl (32 Bit Befehl und 64 Bit Daten).

Hoher Durchsatz wird erreicht bei:

• sequentieller Ausführung von Befehlen,

• Zugriff auf ganze Vektoren (Daten),

• Zugriff auf 64/128 Bit-Gleitkommazahlen bei 32 Bit Datenbusbreite,

• durchschnittlich geringem Bedarf an Daten (aus dem Speicher) pro

Befehl Geringer Durchsatz wird erzielt bei:

• wilden Sprüngen, ...

• Benutzung von verketteten Listen mit großen Knoten (CAD-Programme),

... Bemerkung: Es werden SparcStation10’s ohne SuperCache ausgeliefert, um bei speziellen Anwenderprogrammen das verlangsamende Cache-Füllen zu umgehen.

Pipelinebtrieb der CPU selbst: FPU-Pipeline (baue ALU aus unabhängigen Einheiten auf):

Beispiel: Subtraktion

1) fetch operands 1.082 · 10^{12}, 9.212 · 10^{11}
2) adjust exponent 1.082 · 10^{12}, 0.9212 · 10^{12}
3) execute ”-“  0.1608 · 10^{12}
4) normalize result 1.608 · 10^{11}

C_{i} = A_{i} + B_{i}, ∀i = 1..N

Zyklus  1  2  3  4  5  ⋯
fetch  B_{1}, C_{1} B_{2}, C_{2} B_{3}, C_{3} B_{4}, C_{4} B_{5}, C_{5}
adjust  — B_{1}, C_{1} B_{2}, C_{2} B_{3}, C_{3} B_{4}, C_{4}
execute  —  — B_{1} − C_{1} B_{2} − C_{2} B_{3} − C_{3}
normalize —  —  —  B_{1} − C_{1} B_{2} − C_{2}
↘  ↘
B_{1} − C_{1} B_{2} − C_{2}

Resümee:

• Ein Einzelbefehl (z.B. Subtraktion) braucht 4 Zyklen Zeit.

• Nach einer Startup-Zeit von 4 Zyklen (Füllen der Pipe) wird dann jedoch pro Zyklus ein Endergebnis geliefert. (Das ist allerdings nur eine Komponente des Ergebnis-Vektors.)

• Problem: ”Datenabhängigkeit“

Ein Wert ist noch in der Pipe, obwohl er schon als neues Argument benötigt wird.

Übersicht über die 1996 marktreif gewordenen SPARC-Technologie

Floating Point Unit (FPU)^{FP Multiply}^{FP Add}^{FP Divide}^{Graphics Unit (GRU)}^{FP Reg}^{Grouping Logic} ^{Int.Reg. and Annex}^{Integer Execution Unit (IEU)}  ^{Store Queue}^{Load Queue}^{Data Cache}^{Load Store Unit (LSU)}  ^{External}^{Cache}^{RAM}^{Memory Managment Unit (MMU)}^{Instruction Cache and Buffer}^{Prefetch and Dispatch Unit}  ^{External Cache Unit}^{Memory Interface Unit (MIU)} UltraSPARCI

• IU-Pipeline (9 Phasen): fetch-decode-group-execute-cache access-load missinteger pipe wait- trap resolution-writeback-

• 2 ALU’s in IEU (= interger execute unit)

• FP-pipeline

• getrennte FP-execution units

Operation Throughput (Cycles) Latency (Cycles)
Add (Single Precision) 1  3
Add (Double Precision) 1  3
Multiply (Single Precision) 1  3
Multiply (Double Precision) 1  3
Divide (Single Precision) 12  12
Divide (Double Precision) 22  22
Square Root (Single Precision) 12  12
Square Root (Double Precision) 22  22

Dispatch Unit Integer Execution Unit  Branch Unit Load Store Unit  FP/Graphics Unit & Register File FP  FP  FP Graphics  Graphics ×  + ÷/√  ×  + Completion Unit 4 Instructions 3x64 bits 4x64 bits 64 bits  Data Store 64 bits  2x64 bits 3x64 bits Load Data

Die Ultra Port Architekture arbeitet statt mit einem Bus-System mit packet switched und crossbar-Datentransfer:

Datapath^{Crossbar}^{N×M}  ^{Databus}^{Memory}^{Controller &}^{System}^{Crossbar}^{Address}^{UPA Address Bus}^{and Signaling} Ultra Port Architecture^{UPA Port n-1}^{UPA Port 0}  ^{UPA Databus}  ^{Memory Bank m-1}^{Memory Bank 0}^{Datapath Control}^{Memory Control}^{Dtag Control}^{Snoopbus}

1.2.2.10 Festkommazahlen Festkommazahlen besitzen immer eine feste Anzahl von Nachkommaziffern, z.B. 5 Vor- und 3 Nachkommastellen wie bei kg:

F_{3}^{5} := {(−1)^{s} ∑_{i=−3}^{5} a_{i} · 10^{i} : a_{i} ∈ {0, ..9}; s ∈ {0, 1}}

Veranschaulichung am Zahlenstrahl: F_{3}^{5} 0  0.002 0.001  ...  99999.998 99999.999

Eigenschaften:

• fester Gitterabstand zwischen je zwei benachbarten Zahlen (im Beispiel 10^{−3})

• Addition bis auf Über-/Unterlauf exakt ausführbar

• Multiplikation mit ganzen Zahlen bis auf Über-/Unterlauf exakt ausführbar

• Multiplikation von echt gebrochenen Zahlen mit Rundungsfehlern behaftet

Überlegungen zeigen, daß z.B. die Realisierung von DM-Beträgen mit real-Variablen ungünstig ist, denn

1Pf = \frac{1}{2^{2}5^{2}} DM = 1.\overline{47ae1}_{16}

Man rechnet also besser mit Pfennigbeträgen

type

               Pfennig = integer;  {32 Bit}

var

preis : Pfennig; {−21 474 836, 48DM ... + 21 474 836, 47DM}

Basisumwandlung von Nachkommastellen: Es sei x ∈ [0, 1). Dann gilt für beliebiges b ∈ ℕ \ {0, 1}.

i := -1;

          Wiederhole

z_{i} := trunc(x ∗ b); {∈ [0, .., b − 1]} x := x ∗ b − z_{i}; {∈ [0, 1)} i := pred(i)

          bis((x=0) or (i < −maxStellenzahl))

liefert mit

∑_{j=min{i+1,−maxStellenzahl}}^{−1} z_{j}b^{j}

eine maxStellenzahl-Näherungsdarstellung von x zur Basis b. Sei zum Beispiel x := \frac{9}{64} und b = 2. Dann arbeitet der Algorithmus wie folgt:

\frac{9}{64} · 2 = \frac{9}{32} ⇒ z_{−1} = 0

\frac{9}{32} · 2 = \frac{9}{16} ⇒ z_{−2} = 0
\frac{9}{16} · 2 = \frac{9}{8} = 1 + \frac{1}{8} ⇒ z_{−3} = 1
\frac{1}{8} · 2 = \frac{1}{4} ⇒ z_{−4} = 0
\frac{1}{4} · 2 = \frac{1}{2} ⇒ z_{−5} = 0
\frac{1}{2} · 2 = 1 ⇒ z_{−6} = 1

Damit ergibt sich

\frac{9}{64} = (0.001001)_{2}

Aufgabe 1.4

1. Berechne (\frac{1}{100})_{10} zur Basis b = 16.

2. Wie ist der Algorithmus so zu ändern, daß der Fehler

|x − ∑_{j=i+1}^{−1} z_{j}b^{j}| ≤ \frac{1}{2} · b^{i+1}

und nicht lediglich

|x − ∑_{j=i+1}^{−1} z_{j}b^{j}| ≤ b^{i+1}

ist? (Runden statt Abschneiden)

Die Summe ∑_{j=i+1}^{−1} z_{j}b^{j} berechnet man übrigens am besten mit dem Horner-Schema:

((… (z_{i+1}b^{−1} + z_{i}) + … + z_{−2})b^{−1} + z_{−1})b^{−1}

1.2.2.11 Gleitkommazahlen

Festkommazahlen sind für finanzielle Rechnungen sehr angebracht, solange man mit den Operatoren +, −, ∗, / auskommt. Für Rechnungen, die Funktionen wie log, exp, … benötigen, muß man im allgemeinen auf die Gleitkommazahlen ausweichen. Die Idee für Gleitkommazahlen kommt aus den Ingenieur- und Naturwissenschaften:

F_{3}^{4} = {min F := −9999.999, −9999.998, …, 0, …, 9999.998, 9999.999 =: max F}