Beschleunigung und Parallelität

Question 1

Klassifikation von Speichern

Answer 1

• 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

Question 2

Speicherorganisation

Klassifikationsparameter

Answer 2

• Zugriffszeit: Zeit zwischen Anforderung eines Lesezugriffs und Eintreffen des Inhalts der adressierten Speicherzelle am Speicherausgang
• Kosten pro Bit

► sind gegenläufig → Optimierungsproblem

Question 3

Cache

Lokalitätsprinzip

Answer 3

= 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

1. Zeitliche Lokalität:
   
   • Betrachtung einer Zelle
   • Zugriff auf eine Speicherzelle lässt es erwarten, dass bald wieder auf sie zugegriffen wird → im Zwischenspeicher behalten
2. Räumliche Lokalität
   
   • Betrachtung benachbarter Zellen
   • Zugriff auf eine Speicherzelle lässt baldigen Zugriff auf benachbarte Speicherzellen erwarten

Question 4

Speicherhierarchien

Answer 4

Optimierungskriterien:

• minimale Zugriffszeit
• minimale Kosten pro gespeicherten Bit

je teurer der Speicher, desto weniger ist davon im Rechner → Speicherhierarchie

Question 5

Cache

Weitere Verwendung des Cache-Prinzips

Answer 5

• 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
• Software
  
  • Pufferspeicher des Betriebssystems
  • Pufferspeicher für Datenbanken
  • Browser laden (Unter-)Seiten vor ihrer Anforderung

Question 6

Cacheleistung

Answer 6

• 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
• T_eff = effektive Zugriffszeit
• T_C = Zugriffszeit des Cache
• T_M = Zugriffszeit des Hauptspeichers

Question 7

Amdahls Gesetz

Answer 7

• 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

Question 8

Amdahls Gesetz

Schlussfolgerungen

Answer 8

• 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

Question 9

Erweiterung von Amdahls Gesetz

Answer 9

• 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

Question 10

Amdahls Gesetz

Answer 10

Question 11

Amdahls Gesetz bei Prozessanpassungen

Answer 11

Gesetz kann auch für potentielle Verbesserung durch Teilanpassungen in Systemen angewandt werden

Question 12

Parallelität

2 Arten

Answer 12

1. zeitliche Parallelität
   
   • Aufgabe wird in mehrere Unteraufgaben unterteilt
   • Unteraufgaben werden parallel ausgeführt
   • auch genannt: Pipelining
2. räumliche Parallelität
   
   • vervielfachte Hardware bearbeitet mehrere Aufgaben gleichzeitig
   • Zusammenschalten mehrerer kleinerer Computer realisiert leistungsfähigeren Computer

Question 13

zeitliche Parallelität

Answer 13

• 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

Question 14

zeitliche Parallelität

Steuerflussabhängigkeit

Answer 14

= control

v₁ (x) →_c v₂ (y)

Ausführung von Zeile x entscheidet über Ausführung von Zeile y

z.B. IF - ELSE

Question 15

zeitliche Parallelität

Datenflussabhängigkeit

Answer 15

es gibt wenigstens eine Variable z, auf die in beiden Anweisungen x und y zugegriffen wird

1. echte Datenflussabhängigkeit = true:
   
   • 1. schreibend → 2. lesend
   • v₁ (x) →_t v₂ (y)
2. Ausgangsdatenabhängigkeit = output:
   
   • 1. schreibend → 2. schreibend
   • v₁ (x) →_o v₂ (y)
3. Anti-Datenabhängigkeit = anti:
   
   • 1. lesend → 2. schreibend
   • v₁ (x) →_a v₂ (y)
   • durch Pipelining ist bei gleichen Taktzyklus paralleles Ausführen möglich

Question 16

zeitliche Parallelität

Beispiel

Answer 16

1. echte Datenflussabhängigkeit:
   
   • v₁ (1) →_t v₂ (2) Variable x
   • v₁ (1) →_t v₂ (3) Variable x
   • v₁ (4) →_t v₂ (5) Variable b
2. Ausgangsdatenabhängigkeit:
   
   • v₁ (4) →_o v₂ (6) Variable b
   • v₁ (3) →_o v₂ (7) Variable a
3. Anti-Datenabhängigkeit:
   
   • v₁ (5) →_a v₂ (6) Variable b
   • durch Pipelining ist bei gleichen Taktzyklus paralleles Ausführen möglich

Question 17

räumliche Parallelität

Answer 17

Realisierung leistungsfähiger Computer durch das Zusammenschalten mehrerer kleinerer Computer

1. Multiprozessor: parallele Prozessoren mit einem einzigen, gemeinsam genutzen Adressraum
2. Cluster: kleine Anzahl von Rechnern, die nebeneinander stehen und eng miteinander arbeiten → Cluster wird angesprochen statt einzelner Rechner
3. Grid: wie Cluster, aber Hunderte Rechner
4. Cloud: Rechner arbeiten weltweit zusammen

Question 18

räumliche Parallelität

Klassifizierung nach Flynn

Answer 18

• 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

Question 19

räumliche Parallelität - MIMD

Klassifizierung

Answer 19

1. logischer Ort des Speichers
   
   • Distributed Memory
   • Shared Memory
2. Symmetrie des Prozessors
   
   • SMP: Symmetrische Multiprozessorsysteme
   • ASMP: Asymmetrische Multiprozessorsysteme

Question 20

räumliche Parallelität - MIMD
Shared Memory

Answer 20

• 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

Question 21

räumliche Parallelität - MIMD
Distributed Memory

Answer 21

• 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

Question 22

räumliche Parallelität - MIMD

SMP - Symmetrische Multiprozessorsysteme

Answer 22

• mehrere Prozessoren besitzen gemeinsamen Adressraum
• jeder Prozessor adressiert mit derselben physikalischen Adresse die selber Speicherzelle oder dasselbe Peripherieregister → shared memory
• wie natürliche Erweiterung eines Uniprozessorsystems
• Problem: jeder Prozessor muss so gebaut sein, dass er alles kann - z.B. Interruptbehandlung sehr aufwendig

Question 23

räumliche Parallelität - MIMD

SMP: Aufbau

Answer 23

• 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

Question 24

räumliche Parallelität - MIMD

SMP: Nutzung

Answer 24

• alle Prozessoren sind gleich
• alle können sowohl BS als auch Anwendercode abarbeiten
• alle haben Zugriff auf Kernelimage im gemeinsamen Hauptspeicher und können im Kern parallel arbeiten
• insb. I/O-Anforderungen und Gerätetreiber-Interrupts können parallel von verschiedenen Prozessoren bearbeitet werden
• jedes Hauptspeicherdatum kann von jeder CPU und jedem I/O-Gerät referenziert werden
• asynchrone Kommunikation zwischen den CPUs kann interruptgesteuert erfolgen

Question 25

räumliche Parallelität - MIMD

SMP: physikalische Sicht

Answer 25

Verbindung über Bus-/Interruptsystem

Question 26

räumliche Parallelität - MIMD

SMP: logische Sicht

Answer 26

• 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

Question 27

räumliche Parallelität - MIMD

ASMP - Asymmetrische Multiprozessorsysteme

Physikalische Sicht

Answer 27

• 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

Question 28

räumliche Parallelität - MIMD

ASMP - logische Sicht

Answer 28

Question 29

Cache

Kohärenz

Answer 29

• 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

Question 30

Cache

Methoden zur Kohärenzerhaltung

Answer 30

• Ziel: Leser einer Hauptspeicherzelle erhält aktuellen Wert
• Systembus und Caches um geeignete Funktionen erweitert:
  
  • Systembus: zusätzliche Bustransaktionen
  • Cache: zusätzliche Statusbits, die in Abhängigkeit von den CPU- und Busaktionen gesteuert werden
• Bus hat Wirkung eines Broadcast-Mediums
  
  • für Caches ist ständiges Mithören (Snooping) der Busaktivitäten möglich
  • Nutzung der Snoop Protocols

Question 31

Cache

Snooping Protokolle

Answer 31

• Write invalidate: “ich habe a geändert”
  
  • schreibender Prozessor bewirkt, dass alle Kopien in anderen Caches ungültig gemacht werden bevor er seine lokale Kopie überschreibt
  • nur noch Kopie des Schreibers existiert
• Write broadcast: “ich habe a auf 5 geändert”
  
  • Schreiber sendet neue Daten über den Bus
  • alle Kopien werden ständig aktualisiert
  • lohnt sich nur, wenn aktuelle Kopien auch verwendet werden (langsamer)