TINF Theorie Baumgartner

TINFComputerarchitektur

Dipl.-Ing. Robert Baumgartner, MBA

Robert Baumgartner, [email protected]

Zitat (1)

"Ich denke es gibt nur einen weltweiten Markt für 5 Computer."

Thomas Watson Senior, Chairman of IBM, 1943


Zitat (2)

"In der Zukunft werden Computer nicht mehr als 1,5 Tonnen wiegen."

Zeitschrift Popular Mechanics 1949 Prognose für die Zukunft der Computer


Zitat (3)

"Es gibt keinen Grund warum jemand zuhause einen Computer brauchen sollte."

Ken Olsen, Gründer und Chairman of DEC, 1977


Übersicht

1. Umfang des Fachgebietes

2. Technologische Entwicklung

3. Rechnerleistung

4. Beschleunigung

5. Klassifikation von Computerarchitekturen

6. Speicher

7. Prozessoren

8. Ein/Ausgabe Systeme


Umfang des Fachgebietes

Was alles umfasst das Fachgebiet Computerarchitektur ?

1.


1. Computerarchitektur: Fachgebiet

Allgemeine Strukturlehre Ingenieurwissenschaftliche Disziplin, die bestehende und

zukünftige Rechenanlagen: – beschreibt – vergleicht – beurteilt – verbessert – entwirft

Betrachtet den Aufbau und die Eigenschaften: – des Ganzen (Rechenanlage) – seiner Teile (Komponenten) – seiner Verbindungen (Globalstruktur, Infrastruktur)


1. Entwurf eines Computers

Die Aufgabe ist eine Kompromissfindung zwischen:

Randbedingungen (Technologie, Größe, Geld, Umwelt,...) Gestaltungsgrundsätzen (Modularität, Sparsamkeit,

Fehlertoleranz ...) Zielsetzungen (Leistung, Verfügbarkeit ...)


Die technologische Entwicklung

Die gesamte Leistung des ENIAC ist heute auf einem Chip (ENIAC wog 28 t)

2.


2. Anfänge…(1)

Charles Babbage, ein englischer Mathematiker (1792-1871) beschäftigte sich mit programmierbaren Rechenmaschinen.

Charles Babbage

Differenzmaschineca. 1822


2. Anfänge… (2)

1833 entwickelte Babbage das Konzept eines Universalrechners, der programmgesteuert digitale Befehle und Daten verarbeiten sollte.

Er nannte diesen programmgesteuerten Rechner "Analytical Engine".

Diese Maschine sollte:1. Durch ein vorher ausgearbeitetes Programm (auf Lochstreifen)

gesteuert werden,

2. Speicher für Zwischenergebnisse besitzen,

3. Die Rechnungen unter Verwendung vorher berechneter und gespeicherter Zwischenergebnisse durchführen und

4. Die Ergebnisse ausgeben.


2. Anfänge… (3)

Analytical Engine


2. Erste Programmierin

Die Analytical Engine wurde von seiner Assistentin Ada Lovelace (1815-1852) programmiert.

Ada Augusta Byron, Countess of Lovelace

"Ich bin eines dieser Genies, die sich darauf beschränken, sich zu erholen." (Ada Lovelace an ihren Mann)


2. Erster elektrischer Computer

John Mauchly und Presper Eckert Erfinder des ENIAC 1947


2. ENIAC 1947

Facts:

27.000 Kg17.468 Röhren167 m2

160 KW

pro Sekunde:5000 Additionen, oder 357 Multiplikationen, oder 38 Divisionen


2. Plugboards

Entwurf, Bau, und Programmierung wurde von einer Gruppe von Leuten durchgeführt.

Programmierung erfolgte in Maschinensprache. Herstellen von Verbindungen auf Stecktafeln (Plugboards).

Plugboard


2. ENIAC 1997

5,29

mm

7,44 mm


2. Das ENIAC-On-A-Chip Team

URL: http://www.ee.upenn.edu/~jan/eniacproj.html

ENIAC-On-A-Chip Homepage:


2. Röhren, Transistor, Chip - 1964


2.Intel und der Mikroprozessor

Intel Gründer (1968):

Robert NoyceAndy GroveGordon Moore

Market Capitalization 8/9/2005:157,68 Milliarden Dollar


2. Der Anfang der Mikroprozessoren

Vorher gab es Mainframes und Minicomputer Erfunden 1969 von Ted Hoff (Intel) Erster Mikroprozessor war Intel 4004

– Auftragsarbeit von Intel für

Taschenrechner– 4-Bit Prozessor– Kommerziell nicht nutzbar

Nachfolger war Intel 8008– 8-Bit Prozessor– Auftraggeber sprang ab– Intel war gezwungen ihn selbst

zu vermarkten

Ted Hoff


2. Die technologische Entwicklung (1)

Seit Anfang der siebziger Jahre des vorigen Jahrunderts kontinuierliche Verbesserung der integrierten Schaltungen

– Dichte (Anzahl der Transistoren und Leitungen)– Geschwindigkeit (einfacher logischer Gatter und Speichergeräte)– Fläche (physische Größe der größten herstellbaren Schaltung)

Moores Gesetz (1965): Die Anzahl der Transistoren auf einem Chip verdoppelt sich ca. alle 18 Monate.

Gordon Moore



Chip Jahr der Einführung Transistoren

4004 1971 2.2508008 1972 2.5008080 1974 5.0008086 1978 29.000286 1982 120.000386 1985 275.000486 1989 1.180.000Pentium 1993 3.100.000Pentium II 1997 7.500.000Pentium III 1999 24.000.000Pentium 4 2000 42.000.000Pentium 4 Prescott 2004 130.000.000




2. State of the Art - 2005

Der Cell Prototyp von IBM Sony und Toshiba beherbergt 234 Millionen Transistoren

Intel Pentium D ("Smithfield") hat

230 Millionen Transistoren – verfügbar jetzt.

AMD Toledo (Athlon 64 FX Dual Core Variante) hat

233 Millionen Transistoren – verfügbar 2H 2005

Die Intel "Montecito" Itanium Prozessor Version hat

1,72 Milliarden Transistoren (2 Rechnerkerne) – verfügbar 2H 2005 oder Anfang 2006



2005 wird die 90 nm Technlogie verwendet

2006 planen Intel und AMD die 65 nm Technologie zu verwenden.


2. Intel Platform 2015

2003 2005 2007 2009 2011 2013

HT

Multi-Core ZeitalterEinfache und parallele Anwendungen

Many-Core ZeitalterMassiv parallele Anwendungen

1

10

100


2. Prognose für die nächsten 10 Jahre

Prozessoren: Anzahl der Transistoren verdoppelt sich alle 18 Monate aber die Kosten einer Chipfabrik verdoppeln sich alle 4 Jahre!

– Chipfabrik 1965: 1,5 Million Dollar

– Intel Corporation today announced plans to build a new 300-mm wafer fabrication facility at its site in Chandler, Ariz. The new factory, designated Fab 32, will begin production of leading-edge microprocessors in the second half of 2007 on 45 nanometer process technology. Construction on the $3 billion project is set to begin immediately.

Speicher: 60% mehr Kapazität pro Jahr Kosten: 25% niedriger pro Jahr Festplatten: 60% mehr Kapazität pro Jahr


Rechnerleistung

Ein heutige Laptop hat eine ähnliche Leistung wie weltweit alle Rechner von 1950

3.


3. Rechnerleistung - Begriff

Preis und Rechnerleistung sind die wichtigsten Faktoren bei der Beschaffung eines neuen Rechnersystems

Rechnerleistung ist ein vager Begriff Bester Maßstab für Rechnerleistung wäre die Ausführungszeit

der Programme:

im Allgemeinen nicht praktikabel Die vier bekanntesten Methoden:

– MIPS– FLOPS – CPI/IPC– Benchmarks

Andere Faktoren sind: Programmierbarkeit, Kompatibilität


3. MIPS

MIPS = Million Instructions Per Second Älterer Maßstab für Rechnerleistung Geschwindigkeit mit der ein System Anweisungen ausführt Wird berechnet durch:

Heutzutage wenig in Gebrauch Nachteil: Berücksichtigt nicht Systemunterschiede

Anzahl der Anweisungen eines Referenz-Programmes

Dauer in Sekundenx 10-6


3. CPI/IPC

CPI = Cycle Per Instruction Anzahl der für die Ausführung einer Anweisung benötigten

Taktzyklen. Wird berechnet durch:

IPC = Instructions Per Cycle Anzahl der Anweisungen pro Zyklus Wird berechnet durch:


Anzahl der Taktzyklen


Anzahl der Taktzyklen


3. CPI/IPC Beispiel

Beispiel:

Ein bestimmtes Programm besteht aus einer Schleife von 100

Anweisungen, die 42 mal ausgeführt wird.

Wie hoch sind der CPI-Wert und der IPC-Wert für dieses

Programm, wenn die Ausführung 16.000 Taktzyklen erfordert.


3. Nachteile CPI/IPC

Enthält keine Informationen über die Taktrate eines Systems

erlaubt daher im Gegensatz zu MIPS nicht die Ausführungszeit zu berechnen

Wird für den Vergleich zwischen Rechnersystemen nur selten benutzt

Für Forschung mit Simulationen interessant

Anzahl der Anweisungen x CPI

Taktfrequenz


3. FLOPS

FLOP = Floating Point Operations Per Second Mißt die Gleitkommaoperationen pro Sekunde mit Hilfe eines

Referenzprogrammes (Linpack oder Livermore Loops) Häufig auch:

– 1 MFLOPS = 106 FLOPS – 1 GFLOPS = 109 FLOPS – 1 TFLOPS = 1012 FLOPS

Beispiele:– ENIAC: 300 FLOPS– CRAY-1: 160 MFLOPS– Intel Xeon 3.6 GHz: <1.8 GFLOPS– Earth Simulator: 35.61 TFLOPS– Blue Gene/L: 135.5 TFLOPS

Siehe auch http://researchweb.watson.ibm.com/bluegene/

und http://www.top500.org/lists/2005/06/


3. Blue Gene/L von IBM


3. Mare Nostrum


3. Entwicklungstrends

Blue Gene/L

Letzter der Top 500

Alle Top 500


3. Benchmarks

Ein Benchmark umfasst ein oder mehrere Programme zur Leistungsbewertung

Unterscheidung von 3 Gruppen:1. Reale Programme (Compiler, Wordprocessor, etc.)2. Kernel (Teilprogramme wie Livermore Loops, Linpack)3. Synthetische Benchmarks (Whetstone, Dhrystone)

URL für Benchmarks zum Ausprobieren: http://freespace.virgin.net/roy.longbottom/

Reinhold Weicker: Erfinder von Dhrystone


3. Nachteile Benchmarks

Mit den Programmen werden Rechner UND Compiler getestet Häufig eingabelose Programme

erlauben kaum Vorraussagen für Systeme die große Datenmengen verarbeiten

Optimierungen von Compilern haben auf Benchmarks andere Wirkung als auf ‚richtige‘ Programme:

– Hersteller optimierten ihre Compiler für die Benchmarks!– Beispiel: Procedure Inlining beinflußte Dhrystone so stark, daß es

verboten wurde– Beispiel: Schleifenoptimierungen hatten keinen Einfluß auf

Whetstone Ergebnisse Veränderung des Anforderungsprofiles


3. SPEC

Die Nachteile versucht man zu überwinden durch:– Auswahl eines breiten Spektrums von Testprogrammen– Gewichtung der einzelnen Programme

Im wissenschaftlichen Bereich spielen zur Zeit die Benchmarks von SPEC die größte Rolle

SPEC = Standards Performance Evaluation Corporation

URL: http://www.spec.org/ Der meist zitierte SPEC Benchmark ist CPU2000:

– Viele verschiedene Testprogramme– In zwei Ergebnis-Suiten zusammengefasst:

CINT2000 … Beurteilung der Integer Leistung CFP2000 … Beurteilung der Floating Point leistung


3. SPEC CINT2000 v 1.2


3. SPEC CFP2000 v 1.2


1.3. Benchmark Beispiel



3. Andere Benchmarks

Für Büro- oder Multimedia-Anwendungen müssen andere Benchmarks verwendet werden

Es existiert eine Vielzahl unterschiedlicher Test-Suiten

BAPCo SYSmark® 2004 und MobileMark® 2005

URL: http://www.bapco.com/ SiSoft Sandra 2005 URL: http://www.sisoftware.net/ Futuremark 3DMark® 2005

URL: http://www.futuremark.com/


3. Geometrische Mittel

Für die Charakterisierung der Gesamtleistung wird das geometrische Mittel verwendet

Beispiel:

Testprogramm A Testprogramm B

Referenzsystem 1000 s 20 s

Testsystem 1 500 s Faktor 2 2 s Faktor 10

Testsystem 2 200 s Faktor 5 10 s Faktor 2

Gesamtleistung Testsystem 1 = √ 20 = 4,47

Gesamtleistung Testsystem 2 = √ 10 = 3,16


3. Anwenderprofile

Aus einzelnen Werten der Testprogramme wird versucht einen charakteristischen Wert zu ermitteln:

∑ aller Gewichte muß 1 ergeben Das Gewicht muß die Häufigkeit des Aufrufs eines

Programmes berücksichtigen Alternativ wird ein Referenzwert zu einem realen System

verwendet

= ∑ Gewicht i x Ausführungszeit i

Aller Testprogramme

Gewichtete Ausführungszeit

Ausführungszeit auf Referenzsystem

Ausführungszeit auf TestsystemSpeed up =


Beschleunigung

Für viele Anwendungen gilt jedoch die 90 : 10 Regel, daß mehr als 90% der benötigten CPU-Zeit in weniger als 10% des Programmcodes verbraucht wird.

4.


4. Beschleunigung

Beschreibt wie sich die Leistung einer Architektur ändert, wenn Verbesserungen daran vorgenommen werden:

Beispiel: Programm benötigt 25 Sekunden für die Ausführung nach der Änderung nur mehr 15 Sekunden

Beschleunigung = 1,67

Ausführungszeit (vorher)

Ausführungszeit (nachher)Beschleunigung =


4. Wichtigste Regel

Mach den häufigsten Fall schnell

Bedeutet: die Leistungsverbesserung hängt einerseits von der

erzielten Verbesserung ab, aber auch wie häufig sie eingesetzt

werden kann.


4. Amdahls Gesetz

Zeit alt

Beschleunigung =Zeit neu

=1

Anteil unbenutzt +Anteil benutzt

Beschleunigung benutzt

Anteil unbenutzt +Zeit neu = Zeit alt XAnteil benutzt

Beschleunigung benutzt


4. Gene Amdahl


4. Amdahls Gesetz - Beispiel

Eine bestimmte Architektur benutzt für Multiplikationen keine Hardwarebeschleunigung.

Ein Programm verwendet auf Multiplikationena) 10 % seiner Zeit

b) 40 % seiner Zeit Wie hoch ist die Gesamtbeschleunigung wenn für eine

Multiplikation mittels Software 200 und mittels Hardware 4 Taktzyklen benötigt werden ?


4. Zusammenfassung

Eine korrekte Leistungsbewertung darf nicht nur den Mikroprozessor berücksichtigen sondern muß auch periphere Komponenten wie Speicher, Ein-Ausgabe Einheiten beachten.

Eine Beschleunigung einer Komponente UND die Häufigkeit der Nutzung ergeben die Gesamtbeschleunigung.

Ein gutes Rechnersystem sollte ausgewogen sein. Die Leistungsbewertung ist nicht allgemein gültig sondern

hängt auch von den Anwendungen ab. Die üblichen Leistungsbewertungen von Rechnern haben alle

ihre Schwachstellen Zur Beurteilung eines Rechnersystems sind Kenntnisse über

die Architektur vorteilhaft!


Klassifikation von Rechnerarchitekturen

5.

„We want to make machines that will be proud of us“

Danny Hillis, 1983 Gründer und CEO von Thinking Machines


5. Klassifikation nach M.J. Flynn

Unterscheidung nach:– Befehlstrom I (Instruction Stream)– Datenstrom D (Data Stream)

Vier Möglichkeiten:– SISD (Single Instruction Single Data)– SIMD (Single Instruction Multiple Data)– MISD (Mutiple Instruction Single Data)– MIMD (Multiple Instruction Multiple Data)

Michael J. Flynn


5. Rechnertypen Zuordnung

SISD

Einprozessor System

SIMD

Vektorrechner

Arrayrechner

MISD

Leer

MIMD

Multiprozessorsysteme

Datenstrom

Single Multiple

Inst

rukt

ions

stro

m

Single

Multiple

Ein KontrollwerkMehrere Rechenwerke

Mehrere KontrollwerkeMehrere Rechenwerke


5. SISD

Von Neumann Architektur

Seit den 40er Jahren bekannt In jedem Takt wird eine Instruktion ausgeführt Moderne SISD Prozessoren verwenden auch Elemente der

Parallelrechner wie Cache und Pipelines, sind also keine klassischen SISD


5. John von Neumann

• 1902 in Budapest geboren

• 1933 Princeton, USA

• 1944 Spieltheorie (mit Oskar

Morgenstern)

• 1945 Computer Architekturkonzept

• 1957 gestorben

We can all think clearly, more or less, some of the time, but von Neumann's clarity of thought was orders of magnitude greater than that of most of us, all the time. For von Neumann it seemed to be impossible to be unclear in thought or in expression.

(Paul Halmos)


5. Von Neumann Architektur (SISD)

• Drei Hardware-Subsysteme:• Eine zentrale CPU• Hauptspeicher• Ein E/A-System

• Anweisungen werden nacheinander ausgeführt

• Eine einfache Datenleitung zwischen CPU und Hauptspeicher

Nachteil: sogenannter von Neumann Bottleneck


5. SISD UNIVAC

UNIVAC 1107 - 1967


5. SISD Laptop und Workstation

IBM Notebook - 2003

DELL Precision

Workstation 450 - 2003


5. SIMD

Eine CPU besitzt mehrere Verarbeitungseinheiten Die Verarbeitungseinheiten können zeitgleich

verschiedene Daten verarbeiten Vertreter: Vektorrechner, Feldrechner


5. Beispiel Matrixaddition

Vektorrechner und Arrayrechner bilden reguläre Datenstrukturen (Listen, Arrays) auf ein Prozessorfeld ab

Prozessoren führen die gleiche Operation auf individuellen Daten im Gleichtakt aus

Kommunikation mit Nachbarn in Richtung Gleichtakt Beispiel Matrixaddition

1 2 3

4 5 6

7 8 9

9 8 7

6 5 4

3 2 1

+ =

10 10 10

10 10 10

10 10 10


5. C++ Code (für SISD Rechner)


5. Arrayrechner

Die Additionen [i][j] werden auf Prozessoren [i][j] abgebildet Jeder Prozessor für eine Addition durch Nur ein Schritt notwendig

P[0][0] P[0][1] P[0][2]

P[1][0] P[1][1] P[1][2]

P[2][0] P[2][1] P[2][2]

Zentrale Steuerung


5. SIMD Vektorrechner Cray 1

Seymor Cray

Cray 1 - 1976


5. SIMD Connection Machine (I)

Thinking Machines - CM 1 1986 - CM 2 1987

Keira Bromberg . John Huffman . Tamiko Thiel . Danny Hillis . Carl Feynman . Arlene Chung


5. Connection Machine (II)

Wurde entworfen um Intelligenz und Leben zu simulieren. Modell war das menschliche Gehirn:

– Ca. 100 Milliarden (1011) Nervenzellen, – durch ca. 100 Billionen (1014) Synapsen eng miteinander

verbunden. – Das heißt, dass jedes Neuron im Schnitt mit 1000 anderen

Neuronen verbunden ist und somit im Prinzip jedes beliebige Neuron von jedem Startneuron aus in höchstens 4 Schritten erreichbar ist

CM-2 hatte 65536 Prozessoren, die jeweils 1 Bit bearbeiten konnten. Jeder Prozessor hatte 8 kB Memory.

Massiv parallel: alle Prozessoren führten die gleiche Operation auf ihren eigenen Daten durch


5. CM Architektur (I)

Herausforderung war die Architektur– 16 Processoren auf einem Chip → 4096 Chips– Diese wurden in einer 12 dimenisonalen Würfelstruktur

angeordnet.– Dadurch war jeder Chip in 12 Schritten mit jedem anderen

verbunden,


5. CM Architektur (II)


5. CM Architektur (III)


1.5. CM Architektur (IV)


5. CM Architektur (V)


5. CM Architektur (VI)


5. MIMD

Typische Multiprozessorsysteme Mehrere CPUs arbeiten unabhängig von einander and

verschiedenen Daten 2 Arten: Shared Memory und Distributed Memory


5. Gesamtübersicht

SISD

(Von Neumann)

SIMD

Parallele Rechnerarchitekturen

MISD

?

MIMD

Vektor Rechner

Array Rechner

Multi- Prozessorsysteme

Multi- Computersysteme

UMA COMA NUMA MPP COW

Shared memory Distributed Memory

SMP


5. MIMD Shared Memory

Alle Prozessoren verwenden den gleichen Speicher Jeder Speicherbereich kann von jedem Prozessor addressiert

werden Allerdings kann ein Prozessor auch Bereiche sperren Vorteil: relativ einfach zu programmieren Beispiele:

– CRAY YMP, CRAY C90 – IBM 3090 – VAX 9000


5. Moderne Server

Sun Fire V1280 Server -2003

IBM X Series 255 - 2003


5. UMA (< 10 Prozessoren)

Gleichförmiger Speicherzugriff (uniform memory access) Latenz der Speicherzugriffe für alle Prozessoren gleich Nur mit wenigen Prozessoren realisierbar Üblich bei Mehrprozessorboards.


5. NUMA (< 1000 Prozessoren)

Ungleichförmiger Speicherzugriff (non-uniform memory access) Gruppen von Prozessoren haben gemeinsamen Speicher Nur globale Zugriffe über Verbindungsnetzwerk. Logisch (aus Prozessor Sicht) ein großer Adressraum. Z.B. bei Opteron Servern aus mehreren Prozessoren.


5. COMA

Rechnerspeicher besteht nur aus Cache (Cache only memory access)

Ähnlich wie NUMA aber Datenblöcke migrieren dorthin wo sie benötigtwerden.


5. MIMD Distributed Memory

Jeder Prozessor hat seinen eigenen Speicher Verbindung durch Nachrichtenaustausch Problem der Verbindung zwischen Prozessoren (MPP):

– Bus oder Switch: potentieller Engpaß– N-zu-N: Steigt mit Zweierpotenz– Spezielle Topologien

Verbundene Workstations (COW):– Ethernet

Beispiele:– Blue Gene/L– Earth Simulator– Workstation Cluster


5.1. MPP

MPP = Massiv Parallele Rechner Stellen die derzeitigen Top Rechner dar (siehe Blue Gene) Lose gekoppeltes System aus handelsüblichen Prozessoren. Jeder Prozessor hat seinen eigenen Speicher und

kommuniziert über ein herstellerspezifisches Netzwerk mit den anderen Knoten.

MPP lassen sich viel besser skalieren als SMP. Blue Gene hat 65.536 Prozessoren!

Verwenden spezielle Software zur Überwachung der CPUs (Fehlertoleranz).


5.1. MPP System


5.1. COW

COW = Cluster of Workstations Ein solches System setzt sich aus ein paar hundert PCs oder

Workstations zusammen, die über eine handelsübliche Netzwerkkarte verbunden sind.

Die treibende Kraft hinter einem COW System ist die Technologie.

Billig, da Standardtechnologie verwendet wird.Aber langsamer als MPPs.

Das wichtigste Element ist die Verbindung zwischen den PCs


5. Cluster mit 528 Knoten

Intel - 2003


6.0. Übersicht - Speicher

6.1. Speicherhierarchien

6.2. Cache

6.3. Main Memory

6.4. Virtuelle Speicher


6.1. Warum Speicherhierarchien ?

Zeit

Geschwindigkeit


6.1. Speicherhierarchien - Prinzip

Speicherhierarchien beruhen auf drei Prinzipien:

– dem Lokalitätsprinzip: Programm-Lokalität bedeutet, dass ein Programm innerhalb eines Zeitintervalles nur wenige Code- und Datenabschnitte referenziert.

– Weiters gilt: je kleiner die Hardware und je näher dem Prozessor umso schneller ist der Zugriff

– Amdahl's Law


6.1. Lokalitätsprinzip - Beispiel


6.1. Lokalitätsprinzip

Lokalität besitzt zwei Aspekte:

– Einen zeitlichen Aspekt (temporäre Lokalität):

Zeitliche Lokalität bedeutet die Wiederholung von Referenzen in

naher Zukunft.

– Einen räumlichen Aspekt

Räumliche Lokalität besagt, daß die nächste Referenz in der Nachbarschaft der letzten Referenz liegt.

Ein Programm kann auch dann effizient ablaufen, wenn nur sein zeitlich aktueller und sein räumlich aktueller Ausschnitt im Arbeitsspeicher verfügbar ist.


6.1. Speicherhierarchie (I)

CPU

Register

Cache

Hauptspeicher

(Memory)Ein/AusgabeGeräte

Memory Bus I/O Bus

Register Referenz

Cache Referenz

Memory Referenz

I/O Referenz

500 Bytes 512 KB 512 MB 160 GB0,25 ns 1 ns 100 ns 5 ms


6.1. Speicherhierarchie (II)

Ebene 1 2 3 4

Name Register Cache (L1, L2) Main Memory Harddisk

Größe < 1KB < 2 MB < 16 GB > 100 GB

TechnologieCMOS,

Spez. Memory

CMOS,

SRAM

CMOS,

DRAMMagnetplatte

Zugriffszeit

(ns)0,25 -0,5 0,5-25 80-250 5.000.000

Bandbreite (MB/sec)

20.000-100.000

5.000-10.000 1.000-5.000 20-150

Managed by Compiler Hardware BetriebssystemBetriebssystem/

Operator

Backed by Cache Main Memory Harddisk CD/DVD,…


6.3. Hauptspeicher

Hauptspeicher bestehen aus Speicherstellen (cells, locations) von denen jede eine gewisses Quantum an Informationen aufnehmen kann

Jede Speicherstelle hat eine Nummer: eine Adresse

Alle Speicherstellen haben die gleiche Anzahl von Bits

Computer welche das binäre Zahlensystem verwenden stellen Adressen als binäre Zahl dar

Die Anzahl der Bits welche eine Adresse maximal enthalten kann legt die maximale Anzahl von Speicherstellen die adressiert werden können fest.


6.3. Beispiel LMC-HTL

Wurde zu Lehr- und Übungszwecke erfunden. Simuliert einen von Neumann Computer 16 Bit-Befehl des LMC-HTL

0001 000000000011

212=4096 Speicherstellen

Op Code4 Bits

Adressteil 12 Bits


6.3.Übersicht Befehle LMC-HTL

LDA Lade Akkumulator von Adresse xxx 0001 xxx

STO Speichere Akkumulator auf Adresse xxx 0010 xxx

ADD Addiere Inhalt von Adresse xxx zu Akkumulator 0011 xxx

SUB Subtrahiere Inhalt von Adresse xxx von Akkumulator 0100 xxx

INP Eingabe über Tastatur in Akkumulator 0101

OUT Ausgabe auf Konsole von Akkumulator 0110

HLT Halt des Programmes 0111

JMP Sprung zu Adresse xxx 1000 xxx

JOZ Sprung zu Adresse xxx wenn Akkumulator 0 1001 xxx

JLZ Sprung zu Adresse xxx wenn Akkumulator < 0 1010 xxx

JGZ Sprung zu Adresse xxx wenn Akkumulator > 0 1011 xxx

INC Increment Akkumulator um 1 1100

DEC Decrement Akkumulator um 1 1101


6.3. Ununterscheidbarkeit

Im Hauptspeicher ist es nicht möglich nur aufgrund des Inhaltes zwischen Daten und Befehlen zu unterscheiden.

– Beispiel:

kann LDA 80 sein oder die Zahl 4176!

Die Dekodierung des Befehls erfolgt erst im Steuerwerk. Deshalb arbeiten Disassembler nicht korrekt.

0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0


6.3. Beispiel - Hauptspeicher 96 Bits (I)

0

1

11

8 Bits

…

…

0

1

7

…

…

12 Bits


6.3. Beispiel - Hauptspeicher 96 Bits (II)

0

1

2

3

4

5

16 Bits


6.3. Beispiele

Computer Bits/Speicherstelle

Burroughs B1700 1

IBM PC (orginal) 8

DEC PDP-8 12

IBM 1130 16

DEC PDP-15 18

XDS 940 24

Electrologica X8 27

XDS Sigma 9 32

Honeywell 6180 36

CDC 3600 48

CDC Cyber 60


6.3. Bytefolge im Hauptspeicher

Bytes in einem Wort können auf zwei Arten nummeriert werden:

0 1 2 3

4 5 6 7

8 9 10 11

12 13 14 15

3 2 1 0

7 6 5 4

11 10 7 8

15 14 13 12

0

4

8

12

0

4

8

12

Byte

32 Bit Wort

Byte

32 Bit Wort

Adresse AdresseBig Endian Little Endian

0 1 2 3

3 2 1 0


6.3. Beispiel – Datenspeicherung

15000

TI MS

00\0H

4100

MIJ0

4

8

12

16

Adresse Big Endian

15000

SMIT

H\000

41 00

JIM 0

4

8

12

16

Adresse Little Endian

Datenstruktur mit Schueler mit Namen, Alter und Katalognummer

struct Schueler { char name[12]; // JIM SMITH int alter; // 15 int katnr; // 260}

0 1 2 3

3 2 1 0


6.3. Problem – Daten Übertragen (I)

15000

TI MS

00\0H

4100

MIJ0

4

8

12

16

AdresseBig Endian

00015

SMIT

H\000

0014

JIM 0

4

8

12

16

AdresseLittle Endian

Datenaustausch

0 1 2 3

3 2 1 0

Name ist korrekt, aber Zahlen sind verdreht!


6.3. Problem – Daten Übertragen (II)

15000

TI MS

00\0H

41 00

MIJ0

4

8

12

16

AdresseBig Endian

15000

TIMS

00\0H

4100

MIJ0

4

8

12

16

AdresseLittle Endian

Datenaustausch mit Swap

0 1 2 3

3 2 1 0

Die Zahlen sind korrekt, aber der Name ist nun: MIJTIMS mit H welches abgeschnitten wurde!


6.3. Wann ist das wichtig ?

Little/Big Endian ist ein Thema:

Wenn das Programm auf Bytes (statt Integers) zugreift, muss man wissen, auf welchen Inhalt zugegriffen wird.

Beim Datenaustausch zwischen Computern mit unterschiedlichem Byte-Order (→ standardisierte “network order”).

Wenn man “memory dumps” analysiert, oder Konstanten in Assemblersprache ablegt.

Bemerkung: Little/Big-Endian Problematik existiert auch auf der Bit-Ebene!


6.3. Beispiele

Big-endian:– Mainframe Systeme, z.B. IBM System 370/390, z-Series– Motorola 680x0– Sun SPARC

Little-Endian:– Intel x86– VAX– DEC alpha

Wählbar (!):– MIPS, PowerPC– ARM– IA-64


6.4. Virtueller Speicher – Warum ?

Für die ersten kommerziell genutzen Computer war Hauptsppeicher aufgrund der hohen Herstellungskosten besonders knapp.

Der führende wissenschaftliche Computer in den späten Fünfziger Jahren war die IBM 650:

Anzahl der Worte im Hauptspeicher:

2000


6.4. Virtueller Speicher – Warum ?

Aufgrund der Speicherknappheit wurde die Overlaytechnik

entwickelt:

– Der Programmierer teilte das Programm in mehrere Teile

– Jeder dieser Teile paßte in den Hauptspeicher

– Wenn ein Teil fertig war wurde ein anderer geladen

– Verantwortung des Programmierers: Zerlegung des Programmes in einzelne Teile

Festlegung wo die einzelnen Teile gespeichert werden

Festlegung wie die Overlays in den Speicher geladen werden


6.4 Die Erfindung…(I)

1961 in Manchester, England "Dynamic storage allocation in the Atlas computer, including an

automatic use of a backing store" von John Fotheringham

8191

4096

0

Mapping

Adreßraum

4095

0

4k Hauptspeicher


1.4 Die Erfindung… (II)

1. Der Speicherinhalt wird auf die Platte gespeichert

2. Die Worte 8192 bis 12287 werden auf der Platte gesucht

3. Die Worte 8192 bis 12287 werden in den Hauptspeicher geladen

4. Die Adreßabbildung wird geändert um die Adressen 8192 bis 12287

auf die Speicheradressen 0 bis 4095 abzubilden

5. Weitere Ausführung des Programmes als ob nichts passiert wäre.

Bei Verwendung der Adresse 9122 passiert bei virtuellem Speicher folgendes:

Diese Technik wurde Paging genannt, die Speicherblöcke, die ausgelagert werden nannte man Pages.


6.4. Paging

Auf jedem Computer gibt es eine Menge von

Speicheradressen, die ein Programm erzeugen kann:

– Beispiel: LOAD r1, (r2)+10

Die vom Programm generierten Adressen werden virtuelle

Adressen genannt.

CPU

Memory Disk controller

MMU

CPU sendet virtuelle Adresse zur MMU

MMU sendet physische Adresse zum Hauptspeicher


6.4. Beispiel

…

11 45056 – 49151

10 40960 – 45055

9 36864 – 40959

8 32768 – 36863

7 28672 – 32767

6 24576 – 28671

5 20480 – 24575

4 16384 – 20479

3 1288 – 16383

2 8192 – 12287

1 4096 – 8191

0 0 – 4095

7 28672 – 32767

6 24576 – 28671

5 20480 – 24575

4 16384 – 20479

3 1288 – 16383

2 8192 – 12287

1 4096 – 8191

0 0 – 4095

Page Virtueller Adressraum 64 KB

Page Physische Frame Adresse

32 KB Speicher-bereich


1.4 Implementierung von Paging

Der virtuelle Adressraum wird in eine Anzahl gleich großer

Pages eingeteilt.

Übliche Pagegröße 512 bis 64 KB, immer Vielfaches von 2

Der physische Adressraum wird genau so aufgeteilt (gleiche

Pagegröße)

Ein Block im physischen Speicher kann genau eine Page

speichern und wird Page Frame genannt.

Üblicherweise enthält der physische Speicher Tausende von

Page Frames.


1.4. Beispiel

…

11 45056 – 49151 X

10 40960 – 45055 X

9 36864 – 40959 X

8 32768 – 36863 X

7 28672 – 32767 X

6 24576 – 28671 X

5 20480 – 24575 3

4 16384 – 20479 4

3 1288 – 16383 0

2 8192 – 12287 6

1 4096 – 8191 1

0 0 – 4095 2

7 28672 – 32767

6 24576 – 28671

5 20480 – 24575

4 16384 – 20479

3 1288 – 16383

2 8192 – 12287

1 4096 – 8191

0 0 – 4095

Page Virtueller Adressraum 64 KB

Page Physische Frame Adresse

32 KB Speicher-bereich

Virtuelle Page


1.4 Memory Management Unit (MMU)

…

6

5

4

3 1 110

2

1

0

Virtuelle Page

Bit, das anzeigt ob Page geladen

1 1 0 0 0 0 0 0 0 0 1 0 1 1 0

0 0 0 0 0 0 0 1 0 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

20-Bit virtuelle Pageadresse 12 bit Offset

32-Bit virtuelle Adresse

15-Bit SpeicheradressePage Table


1.4 Multi-Level Page Table

Da eine einzelne Page Table sehr groß werden kann, verwendet man 2-level und 3-level Page Tables.

Die Page-Adresse wird dabei in mehrere Teile zerlegt.

+

Physische Adresse

OffsetP1 P2

Directory Table Page Table

10-Bit 10-Bit 12-Bit


1.2. Schülervorträge zum Thema

Hr. Liu, Hr Luger: inverted Page Tables, TLB


1.4. Page Replacement

1. Bei Page Fault erzeugt die Hardware einen Interrupt.

2. Registerinhalte in der ALU werden gerettet (gespeichert).

3. Das BS sieht nach welche virtuelle Page gebraucht wird.

4. Das BS überprüft die Gültigkeit der Adresse und sucht einen Platz im Hauptspeicher.

5. Wenn die Seite im Hauptspeicher "dirty" (modifiziert) ist, wird die Seite auf die Disk geschrieben (Swapdatei).

6. Neue Seite wird vom BS in den Speicher geladen.

7. Page Table wird upgedated.

8. Registerinhalte werden geladen.

9. Instruktion welche den Page Fault erzeugt hat geht weiter.


1.4. Page Replacement Algorithmen I

Der optimale Algorithmus– Einfach zu beschreiben aber unmöglich zu implementieren– Setzt voraus dass man in die Zukunft sehen kann– Vorgangsweise:

D 5 D 321 D ∞

D 90 C 123 D ∞

D 100 D 555 D ∞

D 3 C 90 D ∞

C 1 D 1000 D 999

Seiten im Speicher

Page fault

ALUInstruktionen


1.4. Page Replacement Algorithmen II

Der Not Recently Used Algorithmus– Um Statistiken zu führen welche Seiten kürzlich verwendet wurden

und welche nicht, werden 2 Status Bits verwendet: R… Page referenced M… Page modified

…

6 0 1 1 001

5 0 0 0

4 0 0 0

3 1 1 1 110

2 0 0 0

1 0 1 1 111

0 1 1 1 101

Page Table

Virtuelle Page

M R

Physische Page

Bit, das anzeigt ob Page geladen

Class 0: nicht referenced, nicht modifiziert

Class 1: nicht referenced, modifiziert

Class 2: referenced, nicht modifiziert

Class 3: referenced, modifiziert


1.4. Page Replacement Algorithmen III

Der FIFO Algorithmus– Das BS verwaltet eine Liste von Pages welche zu einem

gegebenen Zeitpunkt im Hauptspeicher geladen sind.– Die Seite am Kopf der Liste ist die älteste Seite, die Seite am Ende

der Liste ist die jüngste Seite.– Bei einem Page Fault wird die älteste Seite entfernt und die neue

Seite hinten angehängt.

A B C D E

älteste Seite jüngste Seite



Der FIFO Algorithmus – Beladys Anomalie

0 1 2 3 0 1 4 4 4 2 3 3

0 1 2 3 0 1 1 1 4 2 2

0 1 2 3 0 0 0 1 4 4

0 1 2 3 0 1 4 0 1 2 3 4

0 1 2 3 3 3 4 0 1 2 3 4

0 1 2 2 2 3 4 0 1 2 3

0 1 1 1 2 3 4 0 1 2

0 0 0 1 2 3 4 0 1

0 1 2 3 0 1 4 0 1 2 3 4

9 Page Faults

10 Page Faults



Der Second Chance Algorithmus– Wie FIFO nur das R-Bit der ältesten Seite wird betrachtet:

Wenn 0, dann ist die Seite alt und unbenutzt Wenn 1, dann wird das Bit auf 0 gesetzt und die Seite wird hinten in

der Liste angereiht. Zeit wird auf aktuelle Zeit gesetzt!

A B C D E

0 3 7 8 10

Page Fault bei Zeit:12

AB C D E

3 7 8 10 12

R-Bit ==1

R-Bit =0


1.4. Page Replacement Algorithmen IV

Der Clock Algorithmus– Wie Second Chance nur kreisförmig angeordnet

Wenn ein Page Fault auftritt, wir die Seite auf die der Zeiger zeigt untersucht. Die Aktion hängt vom R-Bit ab:

R=0: Page entfernen

R=1: R löschen und Zeiger weiterdrehen


1.4. Page Replacement Algorithmen V

Der Least Recently Used (LRU) Algorithmus– Beobachtung: stark benutzte Seiten werden höchstwahrscheinlich

wieder benutzt werden und umgekehrt!– Implementierung von LRU mit spezieller Hardware:

Mittels 64-bit Zähler: – Erhöhung nach jeder Instruktion. – Zähler wird in Page Table nach jedem Speicherzugriff

abgespeichert.– Bei Page Fault, sucht das BS die Seite im Page Table welche

geladen ist und den niedrigsten Zähler hat. NxN Matrix für N Page Frames:

– Page k referenziert → in Zeile k werden alle Bits auf 1 gesetzt, in Spalte k werden alle Bits auf 0 gesetzt.

– Zeile mit den niedersten Binärwert ist der am wenigsten verwendeten Page Frame zugeordnet.


1.4. Page Replacement Algorithmen V

Der Least Recently Used (LRU) AlgorithmusSeiten referenziert: 0,1,2,3,2,1,0,3,2,3


1.4. Page Replacement Algorithmen VI

Der Working Set Algorithmus

– Working Set: die Menge an Seiten, welche ein Prozess gerade benutzt

– Wenn das ganze Working Set in den Speicher passt, werden nur minimale Page Faults auftreten.

– Thrashing: wenn alle paar Instruktionen Page Faults auftreten. – Demand paging: Man wartet bis eine Page benötigt wird.

Problem bei Multiprocessing wegen der vielen Page Faults.– Prepaging: Pages werden geladen bevor der Process läuft. Dazu

eignet sich das Working Set.

Peter Denning




t

Die Seiten die in diesem Intervall referenziert werden bilden das Working Set W(k,t).

Prozess Zeit

k




W(k,t)

k

W(k,t) = monoton steigende Funktion von k




R-Bit

aktuelle virtuelle Zeit

Durchsuche alle Seiten, checke das R-Bit:

If (R==1) setze die Zeit der letzten Verwendung auf aktuelle virtuelle Zeit

If (R==0 und Alter > k) entferne Seite

If (R==0 und Alter <=k) merke die kleinste Zeit

Information über eine Seite

Zeit der letzten Verwendung

Seite referenziert seit dem letzten Tick

Seite nicht referenziert seit dem letzen Tick



Der WSClock Algorithmus



Der WSClock Algorithmus– Der Zeiger bewegt sich im Kreis

Ist das R-Bit==1 wird das R-Bit=0 und die aktuelle virtuelle Zeit als Zeit der letzten Verwendung gesetzt, Zeiger geht zum Nächsten

Ist das R-Bit==0– Ist das Alter > k und !dirty: wird eine neue Seite hier geladen, Zeiger

geht zum Nächsten– Ist das Alter >k und dirty: wird ein Write to Disk geplant, Zeiger geht

zum Nächsten– Ist das Alter <= k: Zeiger geht zum Nächsten

– Wenn der Zeiger wieder am Anfang ist, gibt es zwei Möglichkeiten:

Zumindest ein Write to Disk ist geplant Keine Writes sind geplant


1.4. Vergleich Virtual Memory - Cache

Ähnlichkeiten:

– Verwendung von Hardware um Adressen abzubilden

– Speichern Daten für CPU zwischen

– Arbeiten auf Anfrage und verwenden einen

Ersetzungsmechanismus

Unterschiede:

Cache VM

Zweck CPU beschleunigen Große Programme zu verarbeiten

Fehlerhäufigkeit Häufig Selten

Backup Memory Harddisk


2.0. Übersicht

Kapitel 2: Komponenten

2.1. Prozessor

2.2. Speicher

2.3. Ein/Ausgabe System


Prozessor

„Es gibt keinen vernünftigen Grund warum jemand zuhause einen Computer brauchen sollte“

Ken Olsen, 1977 Gründer und CEO von DEC

2.1.


2.1. Blockschaltbild Prozessor

RegistersatzSteuereinheit

Ganzzahl-Unit Gleitkomma-Unit

Daten zum Speicher Daten zum Speicher

Daten vom Speicher Befehle vom Speicher


2.1. Speicherhierarchie (I)

CPU

Register

Cache

Hauptspeicher

(Memory)Ein/AusgabeGeräte

Memory Bus I/O Bus

Register Referenz

Cache Referenz

Memory Referenz

I/O Referenz

500 Bytes 512 KB 512 MB 160 GB0,25 ns 1 ns 100 ns 5 ms


2.1. Speicherhierarchie (II)

Ebene 1 2 3 4

Name Register Cache (L1, L2) Main Memory Harddisk

Größe < 1KB < 2 MB < 16 GB > 100 GB

TechnologieCMOS,

Spez. Memory

CMOS,

SRAM

CMOS,

DRAMMagnetplatte

Zugriffszeit

(ns)0,25 -0,5 0,5-25 80-250 5.000.000

Bandbreite (MB/sec)

20.000-100.000

5.000-10.000 1.000-5.000 20-150

Managed by Compiler Hardware BetriebssystemBetriebssystem/

Operator

Backed by Cache Main Memory Harddisk CD/DVD,…


2.1. Bestandteile Mikroprozessor

(Mikro)Prozessor wird auch oft Zentraleinheit (CPU) genannt Besteht aus:

– arithmetischen und logischen Funktionseinheiten (ALUs)– Registern– Steuereinheit (Control Unit)

Befehle werden manchmal als Folge von Mikrobefehlen abgearbeitet

Dadurch steigt der Aufwand für die Steuereinheit bei komplexen Befehlen

Register sind schnelle Datenspeicher die gleichzeitigen Zugriff erlauben

Jeder Prozessor hat mindestens ein Register– Ist nur eines vorhanden wird es Akkumulator genannt


2.1. Der Instruktionssatz

Der Prozessor führt Anwenderprogramme aus Die vom Prozessor gesprochene Sprache wird als

Maschinensprache bzw. Instruktionssatz bezeichnet– Instruktionen: bestimmen wie der Prozessor die Daten verarbeiten

soll– Kontrollsignale: dienen der Ablaufsteuerung im Prozessor

Instruktion spezifiziert:– Daten, die verarbeitet werden sollen– Operation, die ausgeführt werden soll

Es existieren viele verschiedene Instruktionssätze


2.1. Programmierebenen

Höhere Programmiersprache

Assemblersprache

Maschinensprache

Mikrocode

Hardware

C, C++, Java, Basic, COBOL, Fortran,…

In der Regel niederste frei zugängliche Ebene

„Firmware“


2.1. Beispiel CPU – Register


2.1. ALU und Befehlssatz


2.1. Beispiel CPU – Control Unit (I)

fest verdrahtet


2.1. Beispiel CPU – Control Unit (II)

Mikroprogrammiert


2.1. Beispiel CPU - Befehlsablauf

Zyklen zum Holen und Dekodieren eines Befehls– Fetch 1: AR <- PC– Fetch 2: DR <- M, PC <- PC+1– Fetch 3: IR <- DR[7..6], AR <- DR[5..0]

Danach kommt der eigentliche Befehl, z.B ADD– ADD 1: DR <- M– ADD 2: AC <- AC+DR

ADD benötigt 5 Zyklen


2.1. Exkurs: Das Stackprinzip (I)

Stack: Sequenz von Daten auf die nur von einem Ende zugegriffen werden kann (LIFO Prinzip)→ Der Stack ist für die Instruktionen selbst unsichtbar

Ein Operand wird mit PUSH Op auf den Stack geschrieben Operationen (ADD, MUL, etc.) verwenden immer die beiden

oberen Stack Elemente, elimieren diese vom Stack und schreiben das Ergebnis auf den Stack

POP liefert das oberste Element des Stack und eliminiert es vom Stack

Der Stack-Pointer (SP) zeigt immer auf den zuletzt abgelegten Wert des Stack


2.1. Beispiel

Stack


2.1. Exkurs: Das Stackprinzip (II)

Beispiel: 6*3+8/2=? Befehlssequenz:

1. PUSH 6

2. PUSH 3

3. MUL

6

SP

…

6 3

SP

…

18

SP

…




4. PUSH 8

5. PUSH 2

6. DIV

18 8

SP

…

18 8 2

SP

…

18 4

SP

…




7. ADD

8. POP

22

SP

…

SP

…


2.1. Exkurs: Stack - Übungsbeispiele

Berechnen sie mit Hilfe eines Stacks folgende Ausdrücke, schreiben sie vorher Postfix-Notation und die Befehlssequenzen dafür auf:

(3*4)+7*(2+3) =

12,4+13,1*(4+2) =

((12+32)*(2+21)+12)/2+2=

(2+1)*(8/4*2+2)/(12-3) =


2.1.Klassifikation von Instruktionsätzen

Basierend auf der Art der internen Datenspeicherung können folgende Klassen von Instruktionssätzen unterschieden werden:

Speicher-Speicher

Instruktionssätze

Stack Akkumulator GP Register

Register-Register Register-Speicher


2.1. Architekturvergleich bei C=A+B

TOS

…

…

…

…

…

…

…

…

…

ALU ALU ALU ALU

Stack Akkumulator Register-Speicher Register-Register

Spe

iche

rP

roze

ssor


2.1. Befehlssequenz für C=A+B

Stack Akkumulator Register-Speicher

Register-Register

Push A Load A Load R1,A Load R1,A

Push B Add B Add R3,R1,B Load R2, B

Add Store C Store R3,C Add R3,R1,R2

Pop C Store R3, C


2.1. GPR Architektur

Bei der GPR Architektur kann noch weiter unterschieden werden:

– Anzahl der Operanden 2 oder 3 Bei 3 Operanden ist das Ziel explizit erwähnt

ADD R3,R1,R2 (R3 <- R1+R2) Bei 2 Operanden ist einer der beiden auch das Ziel

ADD R1,R2 (R1 <- R1+R2)

Alle gebräuchlichen Architekturen lassen sich in nur 3 Typen einteilen:

– Register-Register – Register-Speicher – Speicher-Speicher


2.1. Beispiele GPR Architekturen

Anzahl der Speicher-adressen

Max Anzahl der Operanden

Architektur Typ Beispiele

0 3 Register-Register Alpha, ARM, MIPS, PowerPC, SPARC, Trimedia TM5200

1 2 Register-Memory IBM 360/370, Intel 80x86, Motorola 68000

2 2 Memory-Memory VAX (einige haben auch 3 Operanden)

3 3 Memory-Memory VAX (einige haben auch 2 Operanden)

RISC = Reduced Instruction Set Computer CISC = Complex Instruction Set Computer


2.1.Beispiele GPR Architektur

DEC Alphaserver 1200

IBM Power PC

Motorola 68000Intel Pentium


2.1.Beispiele Stack Architektur

HP 3000

Burroughs B500 (1962)

HP 3000 (1972) HP Taschenrechner Java VM


2.1.Beispiele Akkumulator Architektur

Digital PDP-8 Motorola 6809 Intel 8080 MOS 6502

PDP-8


2.1.Vergleich der Architekturen

Stack:

+ Befehle sind kürzer, da Operanden implizit sind

+ Einfaches Modell für die Berechnung von Ausdrücken

- Code kann nicht umgeordnet werden (kein Pipelining)

- Schwierig zu beschleunigen (Stack ist Bottleneck) Akkumulator:

+ Minimaler interner Zustand (schnelles Context Switching)

+ Kurze Befehle

- Hat keinen anderen Zwischenspeicher (höchste Speichertransferrate!)

GPR:

+ Beste Struktur für Codeoptimierung, Bsp.: (a*b)-(a*c)-(a*d)

- Längste Instruktionen


2.1.Popularität

Stack und Akkumulator Architekturen waren in der Frühzeit populär weil:

– Hauptspeicher teuer war (man wollte möglichst kleine kompilierte Programme)

– Register waren sehr teuer– Primitive Compilertechnologie

Seit 1980 dominieren die GPR Architekturen– Codegröße ist weniger wichtig da Speicher billig– Register billig– Clevere Compilertechnologie– Pipelining populär zur Beschleunigung


2.1. Beispiel: Intel 8086 (CISC)

Kam 1978 auf den Markt 135 verschiedene Instruktionsarten Neun verschiedene Adressmodalitäten Über 3000 verschiedene Instruktionsformate, jedes zwischen 1

Byte und 6 Bytes lang Der Prozessor hat nur 8 General Purpose Register Die Ausführungsdauer der Instruktionen schwankte von 2

Maschinenzyklen bis zu mehr als 80 Maschinenzyklen.


RISC Pioniere

John Cocke(IBM)

David Patterson(Berkley)

Concept 1974

801 prototype microprocessor

RISC I und RISC II Chips

John Henessy (Stanford)MIPS Chips


2.1. RISC Überlegungen

Komplexe Befehle werden selten benutzt, der negative Effekt auf die Gesamtleistung überwiegt.

Der häufige Zugriff auf Operanden sollte besser unterstützt werden durch große Anzahl von Registerspeicher

Eine vereinfachte Architektur kann schneller entworfen, getestet und realisiert werden, wobei neue Technologien schneller eingesetzt werden können.

Intel i860 RISC Prozessor:– 82 Instruktionsarten, jede 32 Bit lang– 4 Adressierungsmöglichkeiten– 32 General Purpose Register– Alle Instruktionen werden in einem Maschinenzyklus abgearbeitet


2.1. Definition RISC und CISC

RISC– Register-Register Architektur– Instruktion läuft in einem Maschinenzyklus ab– Control Unit ist fix verdrahtet– Wenig Instruktionen– Fixes Instruktionsformat– Viele Register

CISC– Große Anzahl von teilweise komplexen Befehlen – Control Unit verwendet Mikrocode– Mehrere Zyklen pro Befehl– Weniger Register– Zum Vorgänger kompatibel


2.1.Der RISC versus CISC Krieg

Mitte der Achtziger Jahre des vorigen Jahrhunderts entstand ein Glaubenskrieg zwischen RISC Anhängern und CISC Verfechtern

RISC Anhänger argumentierten dass RISC Chips viel schneller wären

DEC Alpha war schnellster Chip der Welt Warum hat dann RISC nicht alle CISC Chips ersetzt?

– Kompatibilität– Intel verwendet seit dem 486er selbst einen RISC Kern in seinem

CISC Chip der die einfachsten (und häufigsten) Instruktionen in einem Zyklus durchführt.


2.1 RISC vs. CISC Performance

RISCEinführung

Jahr


2.1.Exkurs: Design Prinzipien

Design Prinzipien moderner Computer:

Alle Instruktionen werden direkt von der Hardware ausgeführt Maximiere die Rate mit der Instruktionen gestartet werden Instruktionen sollten leicht zum Dekodieren sein Nur Load und Store sollten den Speicher adressieren Stelle viele Register zur Verfügung


2.1.Parallelität in Computern

Parallelität

Prozessor Instruktionen

SIMD MIMD

Vektorrechner,Arrayrechner

Shared Memory

Distributed Memory

Pipeline Architektur

Superskalare Architektur


2.1. Pipelining-Idee

Bottleneck ist das Holen der Instruktionen aus dem Speicher Warum also nicht mehrer Instruktionen zwischenspeichern?

Bereits in der IBM 7030 „Stretch“ 1959 realisiert

Gruppe von Registern, sogenannter Prefetch Buffer


2.1.Pipelining-Prinzip

„Prefetching“ teilt die Instruktionsausführung in zwei Teile:– Aufgabe A: Holen der Instruktion („fetching“)– Aufgabe B: Ausführen der Instruction („execution“)

Pipeline erweitert das Konzept auf mehrere Teilaufgaben Jede dieser Teilaufgaben wird von spezieller, parallel

arbeitender Hardware unterstützt

Einheit zum Fetchen der Instruktion

Einheit zum Dekodieren der Instruktion

Einheit zum Fetchen der Operanden

Einheit zum Ausführen der Instruktion

Einheit zum Abspeichern des Resultats

S1 S2 S3 S4 S5


2.1.Pipelining-Ablauf

S1: 1 2 3 4 5 6 7 8

S2: 1 2 3 4 5 6 7

S3: 1 2 3 4 5 6

S4: 1 2 3 4 5

S5: 1 2 3 4

1 2 3 4 5 6 7 8

Zeit (gemessen in Takten)

Fetch Instr.

Dekode Instr.

Fetch Op.

Execute Instr.

Write Back


Pipelining - Überlegungen

Angenommen die Zeit für einen Takt beträgt 2 ns

Dann benötigt eine Instruktion durch die 5-stufige Pipeline im Idealfall 10 ns

Das bedeutet eine Rechnerleistung von 100 MIPS

Aber bei einer vollen Pipeline wird alle 2 ns eine Instruktion vollendet

Daher also 500 MIPS!


2.1.Pipelining-Begriffe

Latenz (Latency): – Jede Instruktion benötigt Zeit für die Ausführung– Diese Zeit wird als Latenz bezeichnet– Sie ist die Zeit die von Beginn der Instruktion bis zu deren Ende

benötigt wird – Also: die Zeiten aller Stufen einer Pipeline aufsummiert

Durchsatz (Throughput):– Die Anzahl der Instruktionen, die in einer gewissen Zeit beendet

werden– Für die Zeit von einer Sekunde und mit der Größenordnung Million

sind das die MIPS– Auch als Prozessor Bandbreite bezeichnet


2.1.Pipelining-Überlegungen

Latenz kann durch Verfielfältigung der Hardware nicht verbessert werden

Pipelining verbessert nur den Throughput nicht die Latenz Pipelining erhöht die Throughput auf Kosten der Latenz! Mit einer Pipeline kommen wir im Idealfall auf einen CPI = 1


2.1. Superskalare Architekturen

Frage: Wie können wir auf CPI < 1 kommen ?


2.1. Mehrfache Pipelines










S1 S2 S3 S4 S5


2.1. Pipelining - Beispiel

Intel:– 386 und davor: keine Pipeline– 486: eine Pipeline (5 stufig)– Pentium: zwei Pipelines

Pentium:– Die Hauptpipline (u Pipeline) kann beliebige Instruktionen

verarbeiten– Die zweite Pipeline (v Pipline) kann nur einfache Ganzzahl

Instruktionen verarbeiten– Komplexe Regeln bestimmen ob ein Instruktionspaar parallel

verarbeitet werden kann– Spezielle Pentium Compiler optimieren den Code– Ca. doppelt so schnell wie 486 bei gleicher Taktrate und simplen

Ganzzahloperationen


2.1. Mehrfache Elemente in einer Stufe




ALU

ALU

LOAD

STORE

Gleitkomma



Beispiel – Power PC (RS/6000)

Instruktions- Cache

Prefetch Buffer

Dekodierungs-Logik

Operanden Fetch

Ausführung

Abspeichern Resultat

Operanden Fetch

Ausführung

Abspeichern Resultat

Register Satz

Verzweigungs-Vorhersage

Bus Interface

Daten Cache


2.1.Pipeline Probleme


2.1. Pipeline-Probleme - Übung

Nicht immer läuft beim Pipelining alles glatt. Es kann zu verschiedenen Problemen kommen. Betrachten wir folgende Befehlsequenz:

ADD r1,r2,r3

SUB r4,r5,r1

Welches Problem tritt beim Abarbeiten dieser Sequenz in unserer 5 stufigen Pipeline auf ?


2.1. Problem-Beispiel

1 2 3 4 5

Fetch

Instr

ADD r1,r2,r3 SUB r4,r5,r1

Instr.

Dekode


Fetch

Op.

ADD r1,r2,r3 SUB r4,r5,r1 SUB r4,r5,r1

Execute

Instr.

ADD r1,r2,r3

Write

Back

ADD r1,r2,r3

Maschinenzyklus

Blase


2.1. Problem-Beispiel

4 5 6 7 8

Fetch

Instr

Instr.

Dekode

Fetch

Op.

SUB r4,r5,r1 SUB r4,r5,r1 SUB r4,r5,r1

Execute

Instr.


Write

Back


Blase Blase

BlaseBlase

Maschinenzyklus


2.1. RAW Konflikt

Diese Art von Konflikt wird Datenkonflikt bzw. Data Hazard genannt

RAW (read after write)

ADD r1,r2,r3

SUB r4,r5,r1

Nachteil ist, dass andere Instruktionen auch blockiert werden die hinter SUB kommen


2.1.Vermeidung der Konflikte

Daten Hazards können mit verschiedenen Methoden vermieden werden:

1. Pipeline Stall

2. Bypassing

3. Umordnung von Instruktionen


2.1.Limitierung von Bypassing

Betrachten wir folgende Instruktionen:

Bypassing nützt hier nichts, da der eine Operand erst aus dem Speicher geholt werden muß!

Daher versucht man zusätzlich die Instruktionen umzuordnen

LD r1, (r2)ADD r3,r2,r1


2.1.Die 3 Arten von Data Hazards

RAW (read after write)

ADD r1,r2,r3

SUB r4,r5,r1

WAW (write after write)

ADD r1,r2,r3

SUB r1,r5,r6

WAR (write after read)

ADD r1,r2,r3

SUB r2,r5,r6

Entstanden durch Umordnen!


2.1. Hazards (Pipeline-Konflikte)

Hazards

Data Hazards

Control Hazards

StructureHazards

3 Arten von Konflikten (Hazards):


2.1.Control Hazards

If (i == 0) k=1;else k=2;

CMP r1,0 ; vergleiche i (r1) mit 0 JNZ Else ; springe zu Else wenn ungleich

Then: MOV r4,1 ; move 1 nach k (r4) JMP Next ; unbedingter Sprung nach NextElse: MOVE r4,2 ; move 2 nach k (r4)Next: . . . .

Programme sind nicht linear sondern voll von Verzweigungen

Ca alle 4-5 Instruktionen kommt eine Verzweigung

Beispiel:

2 von 5 Instruktionen sind Verzweigungen!


2.1. Beispiel unbedingte Verzweigung

1 2 3

Fetch

Instr

JMP Next ADD r1,r2,r3

Instr.

Dekode

JMP Next

Fetch

Op.

JMP Next

Execute

Instr.

Write

Back

Takte

Befehlszähler geschrieben

XYZ

XYZ


2.1. Beispiel bedingte Verzweigung

1 2 3 4 5

Fetch

Instr

JNZ Else ADD r1,r2,r3

Instr.

Dekode

CMP r1,0 JNZ Else

Fetch

Op.

CMP r1,0 JNZ Else

Execute

Instr.

CMP r1,0 JNZ Else

Write

Back

JMP Next

Takte

Befehlszähler geschrieben

XYZ

XYZ

XYZ

XYZ

XYZ

XYZ

XYZXYZ

XYZ


2.1.Control Hazards- Vorhersagen

Einige statistische Aussagen:

– Ca. 85% aller Verzweigungen, die zurück führen (backward

branch) werden genommen.

– Ca. 60% aller Verzweigungen, die vorwärts führen (forward

branch) werden genommen.

Eine Methode, die daher jede Verzweigung wahrnimmt ist

überraschend effektiv.

Trotzdem eine zu große Zahl an falschen Vorhersagen

Daher versucht man unter Berücksichtigung der Vergangenheit

vorherzusagen wohin gesprungen wird! (Branch Prediction).


2.1. Beispiel Structure Hazard

Diese treten auf, wenn die Hardware nicht in der Lage ist sämtliche Anweisungen in der Pipeline gleichzeitig auszuführen

Beispiel:

– Register können nicht gleichzeitig gelesen und geschrieben werden

– die ALU wird auch zum Erhöhen des Befehlszählers verwendet

– Gemeinsamer Speicher für Daten und Befehle

Kommt bei Single Pipeline Prozessoren selten vor, da diese ja für die Pipeline entsprechend ausgelegt wurden


2.1. Beispiel-Pentium III


Beispiel-Pentium III


2.1. Beispiel-Pentium III (I)

Keine RISC- Architektur aber trotzdem superskalare

Implementierung

Instruction Fetch Unit holt pro Takt 32 Bytes aus L1 Befehls-

Cache

Befehlsdekoder dekodiert max. drei x86-Befehle pro Takt– erzeugt MicroOps aus den x86-Befehlen (118 Bit lange RISC-

Befehle)– insgesamt bis zu 6 MicroOps pro Takt

je ein MicroOp durch die Simple Decoder (für IA-32 Registerbefehle) bis zu 4 durch General Decoder (für komplexere IA-32 Befehle) bei sehr komplexen Befehlen: Mikroprogramme aus dem MicroOp

Sequencer


2.1. Beispiel-Pentium III (II)

Registerumbenennung zur Vermeidung von Datenkonflikten

– Tabelle zur Abbildung der ISA-Register auf 40 physische Register

Reorder-Buffer mit 40 MicroOps

– Auflösung echter Datenabhängigkeiten: MicroOps warten, bis

Operanden verfügbar sind

– danach: Weitergabe an gemeinsame Reservation Station für alle

Ausführungseinheiten

Reservation Station teilt dynamisch bis zu 5 MicroOps an die

(insgesamt 11) Ausführungseinheiten zu, sobald eine

passende Einheit frei ist


2.1. Beispiel-Pentium III (III)

Retirement Unit überprüft den Status der MicroOps und entfernt fertige MicroOps aus dem Reorder Buffer (max.3 MicroOps pro Takt)

– Stellt für fertige Befehle den Ablauf des Orginalprogrammes sicher (Semantik der sequentiellen Befehlsabarbeitung)

– Abbildung in den Intel Registersatz (Retirement Register File)


2.1 AMD Athlon versus Intel P3 (I)


2.1 AMD Athlon versus Intel P3 (II)

Documents

TINF Theorie Baumgartner