Beschleunigung und Parallelität Flashcards
Klassifikation von Speichern
- Volatilität:
- flüchtig: Betriebsspannung weg = Datenweg
- nicht flüchtig: Speicher weg = Daten noch da
- Zugriffsart:
- wahlfrei: Festplatte - man kann an beliebige Stelle im Speicher gehen
- sequentiell: Magnetband - Spulen nötig
Speicherorganisation
Klassifikationsparameter
- Zugriffszeit: Zeit zwischen Anforderung eines Lesezugriffs und Eintreffen des Inhalts der adressierten Speicherzelle am Speicherausgang
- Kosten pro Bit
► sind gegenläufig → Optimierungsproblem
Cache
Lokalitätsprinzip
= heuristisches Prinzip, das sich mit einiger Wahrscheinlichkeit aus abgelaufenen Programmteil auf den folgenden schließen lässt, da komplexe Datenstrukturen im Speicher dicht hintereinander gespeichert sind und sequentiell aufeinanderfolgende Befehle dicht sequentiell gespeichert sind
-
Zeitliche Lokalität:
- Betrachtung einer Zelle
- Zugriff auf eine Speicherzelle lässt es erwarten, dass bald wieder auf sie zugegriffen wird → im Zwischenspeicher behalten
-
Räumliche Lokalität
- Betrachtung benachbarter Zellen
- Zugriff auf eine Speicherzelle lässt baldigen Zugriff auf benachbarte Speicherzellen erwarten
Speicherhierarchien
Optimierungskriterien:
- minimale Zugriffszeit
- minimale Kosten pro gespeicherten Bit
je teurer der Speicher, desto weniger ist davon im Rechner → Speicherhierarchie
Cache
Weitere Verwendung des Cache-Prinzips
-
Hardware
- Pufferspeicher der MMU (Memory Management Unit)
- übersetzt von virtuellen Adressen zu physischen Adressen
- ermöglicht Zugriff auf gesamten virtuellen Adressraum
- lokaler Pufferspeicher bei peripheren Geräten (Netzwerkschnittstelle, Festplatte)
- Sprungvorhersage in der Pipelinesteuerlogik der CPU
- Pufferspeicher der MMU (Memory Management Unit)
-
Software
- Pufferspeicher des Betriebssystems
- Pufferspeicher für Datenbanken
- Browser laden (Unter-)Seiten vor ihrer Anforderung
Cacheleistung
- Zugriffszeiten geringer als auf Hauptspeicher
- h = hit rate (Trefferrate in %): Anteil aller Speicherzugriffe, bei denen die gewünschte Information im Cache verfügbar ist
- Niete (miss): Information im Cache nicht gefunden
- Teff = effektive Zugriffszeit
- TC = Zugriffszeit des Cache
- TM = Zugriffszeit des Hauptspeichers
Amdahls Gesetz
- Modell über die Beschleunigung von Programmen durch parallele Ausführung
- zu parallelisierendes Programm = parallelisierbarer + nicht parallelisierbarer/sequentieller Code
- P = Anteil der Laufzeit der parallelen Teilstücke eine Programms
- (1 - P) = sequentieller Anteil
- Gesamtlaufzeit: 1 = (1 - P) + P
- mehr Prozessoren: t = (1 - P) + P/n
Amdahls Gesetz
Schlussfolgerungen
- Beschleunigung wird vor allem durch sequentiellen Teil beschränkt
- Maximum: 1 / (1 - P)
- Mindeslaufzeit eines Programms:
- (Laufzeit bei einem Prozessor) / Maximum des SpeedUp)
- umso mehr Prozessoren
- desto kleiner (1 - P) + P/n
- desto größer SpeedUp
Erweiterung von Amdahls Gesetz
-
zusätzliche Kosten o(N) steigen monoton mit Prozessorenzahl
- Aufwand durch Aufteilung auf mehrere Prozessoren
- zusätzlicher Aufwand durch Kommunikation/Datentransfer
- die Funktion konvergiert nicht mehr gegen (1 / (1 - P)), sondern erreicht ein Maximum, um dahinter wieder abzufallen
Amdahls Gesetz
Amdahls Gesetz bei Prozessanpassungen
Gesetz kann auch für potentielle Verbesserung durch Teilanpassungen in Systemen angewandt werden
Parallelität
2 Arten
-
zeitliche Parallelität
- Aufgabe wird in mehrere Unteraufgaben unterteilt
- Unteraufgaben werden parallel ausgeführt
- auch genannt: Pipelining
-
räumliche Parallelität
- vervielfachte Hardware bearbeitet mehrere Aufgaben gleichzeitig
- Zusammenschalten mehrerer kleinerer Computer realisiert leistungsfähigeren Computer
zeitliche Parallelität
- durch Datenflussanalyse von Algorithmen
- Steuerflussabhängigkeit
- Datenflussabhängigkeit
- jedes Programm hat Potential für Parallelität
- Ziel: Operationen finden, die nicht zwingend in der Reihenfolge ausgeführt werden müssen, in der sie im Programmtext stehen
- Kosten: Analyseaufwand
- je nachdem wie viel parallel ausgeführt werden soll, so viel ALUs braucht man
zeitliche Parallelität
Steuerflussabhängigkeit
= control
v1 (x) →c v2 (y)
Ausführung von Zeile x entscheidet über Ausführung von Zeile y
z.B. IF - ELSE
zeitliche Parallelität
Datenflussabhängigkeit
es gibt wenigstens eine Variable z, auf die in beiden Anweisungen x und y zugegriffen wird
- echte Datenflussabhängigkeit = true:
- 1. schreibend → 2. lesend
- v1 (x) →t v2 (y)
- Ausgangsdatenabhängigkeit = output:
- 1. schreibend → 2. schreibend
- v1 (x) →o v2 (y)
- Anti-Datenabhängigkeit = anti:
- 1. lesend → 2. schreibend
- v1 (x) →a v2 (y)
- durch Pipelining ist bei gleichen Taktzyklus paralleles Ausführen möglich
zeitliche Parallelität
Beispiel
- echte Datenflussabhängigkeit:
- v1 (1) →t v2 (2) Variable x
- v1 (1) →t v2 (3) Variable x
- v1 (4) →t v2 (5) Variable b
- Ausgangsdatenabhängigkeit:
- v1 (4) →o v2 (6) Variable b
- v1 (3) →o v2 (7) Variable a
- Anti-Datenabhängigkeit:
- v1 (5) →a v2 (6) Variable b
- durch Pipelining ist bei gleichen Taktzyklus paralleles Ausführen möglich
räumliche Parallelität
Klassifizierung nach Flynn
- S - Single, M - Multiple
- I - Instruction (Prozessoren), D - Data (Speicher)
- SISD: klassischer Einprozessorenrechner, keine Parallelität
- SIMD: Spezialrechner - ein Programm, alle Prozessoren machen das Gleiche (z.B. Graphikkarte, gleiche Berechnungen für jeden Pixel)
- MISD: Spezialrechner - eine Variable, viele Prozessoren (z.B. Matrizenberechnung)
- MIMD: heutiger Standard-Universalrechner
räumliche Parallelität - MIMD
Klassifizierung
- logischer Ort des Speichers
- Distributed Memory
- Shared Memory
- Symmetrie des Prozessors
- SMP: Symmetrische Multiprozessorsysteme
- ASMP: Asymmetrische Multiprozessorsysteme
räumliche Parallelität - MIMD
Shared Memory
- globaler Adressraum → eine Variable immer auffindbar und gleich angesprochen
-
Vorteil:
- einfaches Programmiermodell (wie Uniprozessorsystem)
- ein Prozessor kann auf gesamten Adressraum zugreifen
-
Nachteil:
- nur bei kleiner Prozessorenzahl leicht beherrschbar
- skaliert nicht
räumliche Parallelität - MIMD
Distributed Memory
- nur lokale Adressräume
- Kommunikation erfolgt durch Message Passing
- Prozessoren arbeiten asynchron:
- müssen nicht gleich getaktet sein
- unterschiedliche Prozessoren mit unterschiedlicher Geschwindigkeit möglich
- Vorteil: physikalisch einfach herstellbar, skalierbar
- Nachteil: Message Passing muss explizit programmiert werden (zwischen Prozessoren übersetzen, wo man welche Variablen holen muss)
- Nachteil umgangen von Distributed-Shared Memory = distributed memory + Abstraktionsschicht, die alles koordiniert
räumliche Parallelität - MIMD
SMP: Aufbau
- Bus kann zu einem Zeitpunkt nur von je einem Prozessor genutzt werden
- n Prozessoren: Speicherbandbreite sinkt auf 1/n pro Prozessor
- wirkt nicht leistungsbegrenzend, solange ein Prozessor ca. n Zugriffe im Cache und dann erst im Hauptspeicher vornimmt (hohe Hitrate)
- durch Begrenzung der Busbandbreite und der Cache-Lokalität, “skalieren” MPs diese Architektur nur bis ca. 30 Prozessoren
räumliche Parallelität - MIMD
SMP: physikalische Sicht
Verbindung über Bus-/Interruptsystem
räumliche Parallelität - MIMD
SMP: logische Sicht
- Stapelbearbeitung: wenn 1 Prozessor Zeit hat, übernimmt er den nächsten Job
- aufgeteilt in 2 Stapel:
- Warten auf I/O und Interrupts
- Sonstiges
- bei zu großen Stapeln können Jobs verschoben werden, weil jeder Prozessor alles kann
räumliche Parallelität - MIMD
ASMP - Asymmetrische Multiprozessorsysteme
Physikalische Sicht
-
MASTER: 1 Prozessor
- verfügt über I/O-Anschlüsse inkl. der damit verbundenen Interruptleistungen
- führt alle privilegierten Operationen wie I/O und Management des BS aus
- kann Betriebscode ausführen
-
SLAVES: restliche Prozessoren
- arbeiten Anwendercode ab und rufen Master zur Ausführung von Systemdiensten
- skalieren sind schlecht, sind aber einfach zu implementieren
räumliche Parallelität - MIMD
ASMP - logische Sicht
Cache
Kohärenz
- in MPs können von 1 Hauptspeichervariablen in mehreren Caches Kopien enthalten sein
- typisch: Write-Back-Caches
- wenn Variable in einem Cache geändert wird, greift anderer Prozessor viell. auf veraltete Variable aus Hauptspeicher zu
- vorübergehende Inkonsistenzen zwischen- Cache und Hauptspeicherdaten
- nicht-kohärente Mehrfachkopien möglich, wenn keine speziellen Cache-Kohärenzmechanismen zur Anwendung kommen
