Kapitel 9 - Parallelrechner
|
Inhalt
|
- Flynn's Klassifikation
- Shared Memory und Distributed Memory
- Prinzip des Vektorrechners
- Interleaved Memory
- BUS-Arbitierung
- Cache-Kohärenz-Protokolle
|
Wie kann man Parallelrechner klassifizieren?
In SIMD (Single Instruction Multiple Data) wie Array-Rechner und MIMD (Muliple Instruction Multiple Data),
wie
- MPP - Massive Parallel Processor System
- VC - Vector Processor (Paralleliät durch Pipeline)
- PVP - Parallel Vector Processor
- Cluster (COW) - Uniprocessor, SMP
- NOW - Network Of Workstations
- Grid - Metacomputer (Cluster von vernetzten homogenen Parallelrechnern)
In der Implementation wird zwischen MIMD-Systemem mit gemeinsamen oder globalen Speicher und
synchronen oder asynchronen Systemen unterschieden.
Was ist ein Cluster
"Form einer parallelen Rechnerarchitektur, die auf einem
Ensemble von unabhängigen Computern beruht, welche durch
ein Verbindungsnetzwerk zu einem koordinierten System zusammengefasst werden,
um gemeinsam an einer Aufgabe arbeiten zu können."
Was unterscheidet Cluster von MPP (Massiv Parallel Processors)?
Ein Cluster basiert auf COTS-Komponenten und stellt einen Knoten mit vollständigem Betriebssystem
dar:
- Knoten als Single Node nutz- und kontrollierbar
- gewöhnte vollständige Ablaufumgebung(bekannte Konzepte, Compiler, Tools usw.)
- Multi-tasking und potentiell Multi-User fähig
- Paging, BS Protection
- Betriebssystem liefert die Kommunikations-Abstraktion
- Stand-alone, d.h. kein Front-end Rechner nötig
Was ist ein Grid
Computational Grid ist eine Form eines parallel-verteilten Systems. Es basiert auf
dem Zusammenschluß regionaler, nationaler und globaler (heterogener) Rechner, Daten ,Grafiken und
Embedded Ressourcen durch ein Hochleistungs-Kommunikationsnetz.
Grids werden zur Bildung übergeordneter verteilter Verbundsysteme (Metacomputer) mit Leistungen im
Tera-scale Bereich benutzt. Grids werden immer in Verbindung mit einer entsprechenden (Grid)Software-
Infrastruktur und Zugangssoftware(Grid-Portale) genutzt.
Was ist der Unterschied zwischen symmetrischen und asymmetrischen MPs?
Bei asymmetrischen Systemem gibt es einen Master-Prozessor, welcher an das I/O Subsystem
gekoppelt ist. Restliche Prozessoren sind Slaves und sind nicht direkt mit dem I/O Subsystem
verbunden. Daher können die Slaves auch nur Anwenderkode ausführen. Zur Ausführung von
Systemdiensten muss der Master gerufen werden, da nur er Betriebssystemoperationen ausführen darf.
Bei symmetrischen Systemem liegt das Kernel-Image für alle Prozessoren erreichbar im Shared Memory.
Das I/O Subsystem und Interrupts können parallel von mehreren Prozessoren bearbeitet werden.
Was besagt die Klassifikation nach Flynn?
|
Instruktionsströme
|
Datenströme
|
Bezeichner
|
Typische Anwendungsfälle
|
|
1
|
1
|
SISD
|
Von-Neumann Rechner
|
|
1
|
N
|
SIMD
|
Vektorrechner
|
|
N
|
1
|
MISD
|
(noch) nicht existent
|
|
N
|
N
|
MIMD
|
Mehrprozessor und -rechner
|
Worin liegt der signifikante Unterschied zwischen SIMD und MIMD Systemen?
SIMD Systeme benutzen zwar getrennte Datenspeicher, bekommen ihre Befehle aber aus einem
globalem Befehlsspeicher. Bei MIMD Systemen hat jede Einheit seinen eigenen Befehlsspeicher.
Was macht ein Shared Memory Sytem (Mehrprozessorsystem) aus?
Alle CPU's teilen sich gemeinsamen Speicher. Deshalb ist Kommunikation hier besonders einfach.
Ist jede CPU gleichberechtigt und austauschbar, wird das System SMP genannt.
Nachteile sind, daß dieses Prinzip nur bei kleinen Prozessorzahlen überschaubar bleibt und
das das Prinzip nicht skaliert.
Was ist Distributed Memory? (Mehrrechnersystem)
Diese Systeme definieren sich dadurch, dass jede CPU ihren eigenen Speicher besitzt.
Kommunikation erfolgt hier über ein Verbindungsnetz, was Mehrrechnersysteme weitaus
komplizierter macht, als Multiprozessorsysteme.
Eine Möglichkeit des gemeinsamen Speichers ist Distributed Shared Memory. Hier stellt
das Betriebssystem den systemweiten Adressraum als gemeinsamen Speicher zur Verfügung.
Der Vorteil ist, dass LOAD und STORE Befehle auf fremde Speicher möglich sind. Es wird
sozusagen die Seitenersetzung nicht von der Festplatte, sondern vom entfernten Rechner
vollzogen. Kommunikation erfolgt mit Hilfe von Eingangs- und Ausgangspuffern an den
jeweiligen Maschinen durch das Message Passing.
Was bedeutet UMA - Uniform Memory Architektur?
Es gibt entweder einen globalen Bus mit einem einzigen physischen Speicher oder einen globaler Speicher,
bestehend aus mehreren Teilen, die parallel zugreifbar sind (besser skalierbar).
Hinsichtlich der Zugriffgeschwindigkeit sind beide Lösungen "uniform", d.h. es gibt keine
Unterschiede abhängig davon, auf welchen Teil des Globalspeichers zugegriffen wird = Uniform Memory Architektur (UMA)
Was sind Non-Uniform Memory Architecture Systeme?
Hier geht es um Systeme die auf Distributed Shareded Memory basieren. D.h. die Rechner können gegenseitig
auf den Speicher anderer Rechner zugreifen. Der Zugriff auf lokale und entfernte Speicherteile erfolgt mit
unterschiedlicher Geschwindigkeit. Deshalb Non-Uniform Memory Architecture (NUMA).
Routing von Paketen im Mehrrechnersystem
Wie die einzelnen Pakete vom Sender zum Empfänger gelangen, bestimmt das Routing. Es ist
ebenso dafür verantwortlich Deadlocks zu vermeiden. Dabei sind die Prozesse die Rechner und
die Betriebsmittel die Ein - und Ausgabeports der jeweiligen Stationen.
Was ist ein Vektorrechner?
Viele numerische Probleme lassen sich auf Skalarprozessoren nur in vielen Schleifendurchlaufen
berechnen. Vektorcomputer bieten high level instructions, um diese Schleife mit einem Befehl zu
berechnen. Pipelines bieten sich mehr als an. Da die Datenelemente unabhängig sind, treten keine
Data Hazards auf und das Fehlen von Schleifensprungbefehlen lässt keine Control Hazards in der
Pipeline zu. Um die Speicherbandbreite zu erhöhen, verwendet man das Prinzip der
Speicherverschränkung. Caches haben wenig Effizienz, da Vektorprobleme geringe Lokalität
aufweisen. Die Bandbreite wird durch Blockzugriff und zeitlich verschränkten Speicherbankzugriff
maximiert. (memory interleaving und memory banking)
Was unterscheidet die Hardware eines Vektorrechners von Konventionellen?
Die Register sind nicht eindimensional sondern bestehen aus Vektoren. D.h. das ein Registersatz
2-Dimensional ist. Sämtliche Hardwarekomponenten sind somit auf die Verarbeitung von Vektoren,
anstatt einzelner Worter ausgelegt.
Wie arbeitet Speicherverschränkung?
Der der Hauptspeicher wird in gleichgroße, voneinander unabhängige Bereiche (Module, Speicherbänke)
unterteilt, die zeitlich verschränkt gelesen oder beschrieben werden können. Aufeinanderfolgende
Speicherworte werden zyklisch in aufeinanderfolgenden Speicherbänken abgespeichert. Sinn macht
das Ganze wegen der Diskrepanz zwischen Zugriffs- und Zykluszeit der Hauptspeichermodule. Während
die Zugriffszeit jene Zeit angibt, die zum Lesen bzw. Schreiben eines Speicherwortes benötigt wird,
beschreibt die Zykluszeit eines Speichers die Zeitspanne vom Beginn eines Zugriffs bis zu jenem
Zeitpunkt, zu dem der nächste Zugriff beginnen kann. Daß Zugriffs- und Zykluszeit für
Hauptspeichermodule nicht übereinstimmen, liegt daran, daß sich der Speicher nach einem
Zugriff zunächst regenerieren muß, bevor er neue Zugriffe erlaubt. Für gängige Halbleiterbauteile
ist die Zykluszeit eines Speichers etwa drei- bis viermal so groß wie dessen Zugriffszeit. Für
den Durchsatz eines nichtverschränkten Speichers ist dessen Zykluszeit und nicht die Zugriffszeit
ausschlaggebend.
Bei einem verschränkten Speicher ist, wenn auf die verschiedenen Module in geeigneter Reihenfolge
zugegriffen wird, für den Durchsatz die deutlich kürzere Zugriffszeit sowie die Anzahl der Module
entscheidend. Die größte Beschleunigung der mittleren Zugriffszeit wird erreicht, wenn
aufeinanderfolgende Speicherzugriffe auf verschiedene Module erfolgen.
Interleaved Memory bei Vektorrechnern
Da Speicher zu langsam, werden nun mehrere unabhängige Speicherbänke realisiert, von denen
jeder einen bestimmten Teil des Adressraums zugesprochen bekommt. Beziehen sich aufeinander
folgende Speicherzugriffe jeweils auf Adressen verschiedener Speicherbänke, können die
Folgezugriffe überlappt werden. Bis 512 Speicherbänke sind durchaus normal, um diese Latenzzeiten
der DRAMs zu minimieren. Um Speicherbankko nflikte zu vermeiden, müssen Programmablauf und
Speicherimage aufeinander abgestimmt sein. Dabei wird der Vorteil genutzt, dass die Position
von aufeinander folgenden Vektorelementen im Speicher nicht sequentiell sein muss. Wie bei
Pipelines wird hier die Forwarding-Ähnliche Technik des Chainings angewandt, um Resultatelemente
einer Vektoroperation sofort an den Folgebefehl weiterzuleiten, ohne auf das Fertigstellen des
Befehls zu warten. Unter Nutzung mehrerer Funktionseinheiten können Vektoroperationen damit quasi
parallel ausgeführt werden.
Worauf muss ein Programmierer bei Interleaved Memory achten?
Der Programmablauf muss auf das Speicherabbild abgestimmt sein, das keine Konflikte auftreten
können. Konflikte treten auf, wenn bspw. durch eine ungünstige Schleifenvariante immer die gleiche
Speicherbank angesprochen wird und somit eine starke Verzögerung eintritt. Die Schleife sollte
so aufgebaut sein, dass die Bandbreite komplett ausgenutzt werden kann.
Was definiert im Besonderm die Leistung eines Vektorrechners?
Die Leistung berechnet sich vor allem aus der Vektorlänge. Umso größer die verarbeiteten Vektoren
sind, umso höher die Leistung. Da bei Vektorrechnern die StartUp-Zeit beträchtlichen Einfluss hat,
sind hohe Performance-Werte nur bei ausreichend gefüllten Vektoren zu erreichen. Pauschal kann man
sagen, dass ein Vektor mindestens halb gefüllt sein muss, um parallesierbare Programme ausreichend
Effizient abarbeiten zu können.
Wie arbeiten Bus-basierte Multiprozessorsysteme?
Hier arbeiten mehrere CPU's in einem System parallel. Dabei hat jeder Prozessor gleichen Zugriff
zum zum Hauptspeicher über einen Systembus, welcher von allen Prozessoren genutzt wird. (Shared
Memory)
Logische Konsequenz ist, daß die Speicherbandbreite proportional zu der Anzahl N der Prozessoren
sinkt. (1/N) Dieser Flaschenhals wird durch Caches vermindert. Solange ein Prozessor im Mittel N
Zugriffe im Cache und erst dann einen im Hauptspeicher tätigt, wirkt diese Bandbreitenbegrenzung
noch nicht negativ.
Da die Lokalität von Programmen nunmal auch begrenzt ist, sind soclche Multiprozessorsysteme
höchstens bis um die 30 Prozessoren skalierbar.
Kann sich die Leistung eines SMP-Systems überproportional steigern (bei 4 CPU's 5-fache Leistung)?`
Ja, dass kann genau dann passieren, wenn die benötigten Daten im Singlesystem nicht in den Cache passen. So kann es
unter Umständen bei cleverer Programmierung passieren, daß die Daten verteilt in die vier Caches der vier CPU's passen und
somit die Leistung überproportional erhöht werden kann.
Wie wird der Bus verteilt (Arbitierung)?
Zentral oder dezentral mit Test & Set Befehlen.
Zentrale Arbiterlogik
Die Master senden einen Bus-Request an die zentrale Abiterlogik. Diese entscheidet, welcher
Prozessor das acknowlege-Signal und somit den Bus zugesprochen bekommt.
Dezentral - Daisy Chained Prinzip
Die Priorität der einzelnen Master ist durch Ihre Reihenfolge implizit gegeben. Ein BusGrant
Signal wird durchgeschleift und kann, wenn es benötigt wird, durch einen Bus-Request an die
Zentrale aktiviert werden. Dieses Verfahren ist äußerst ungerecht.
Test & Set Befehle und Bus-Arbitierung
Test & Set Befehle sind atomare Befehle zum Synchronisieren von Prozessen. In Uni-Prozessorsystemem
ist das Problem der "Zerissenen Befehle" dadurch gelöst. Anders bei Multiprozessorystemen. Dort
kann es nach wie vor passieren, dass der aktive Prozessor den Bus entzogen bekommt und somit eine
laufende Test & Set Instruction unterbrochen würde. Deshalb ist hier ein zusätzlicher Mechanismus
notwendig. Es wird ein Lock-Signal eingeführt, welches dem Bus-Arbiter ein Umschalten zwischen
einer Read- und Write-Phase eines Test & Set Befehls verhindert.
Cache-Kohärenz-Protokolle
Write-Through (Keine Inkonsistenz wegen Durchschreiben) und Write-Back (verringert Speicherverkehr,
aber ermöglicht Inkonsistenten) sind die wichtigsten Methoden auf Singleprozessorsystemem.
Write-Throung ist das einfachste und Write-Back das effizienteste, welches in Form des
MESI-Protokoll z.B. im Pentium angewendet wird. Bei SMP's dominieren Write Invalidate
(alle anderen Kopien werden ungültig gemacht) und Write Broadcast (alle Kopien werden bei
Schreibaktion aktualisiert) als Vertreter der Snooping-Protokolle. Ein anderes Snooping
Protokoll ist das Write Once-Protokoll.
MESI-Protokoll für Multiprozessorsysteme
Ein Cache Eintrag kann einen von vier verschiedenen Zuständen besitzen. Treten Zustandswechsel auf,
werden alle Prozessoren benachrichtigt.
- Invalid (die Cacheline ist veraltet)
- Shared (mehrere Prozessoren haben die aktuelle Cacheline)
- Exklusive (Prozessor hat die korrekte Cacheline alleine)
- Modified (Die Cacheline ist aktuell, aber nicht mehr mit Speicher konsistent)
Welche drei wesentlichen parallelen Programmiermodelle gibt es?
- Message-passing Programmiermodell
- Shared-memory Programmiermodell
- Data parallel Programmiermodell
Wie arbeitet Message-passing?
Die Prozesse einer parallelen Applikation haben je
ihren eigenen privaten Adreßbereich und tauschen
sich Daten über explizite Messages aus. Die Synchronisation ist implizit im Akt des
Message-Austausches enthalten. Die Programme sind im allgemeinen in einer
Single-Program, Multiple-Data- (SPMD) Stream-Struktur geschrieben. Programmierstandards werden
de facto durch MPI und PVM gesetzt.
Wie arbeitet das Shared-memory Programmiermodell?
Die Prozesse können hier auf einen gemeinsamen Adreßraum zugreifen. Die Prozeßsynchronisation muß
explizit auf der Basis spezieller Synchronisationskonstrukte erfolgen. Als Programmierstandard setzt
sich zunehmend OpenMP durch.
Wie funktioniert das Data parallel Modell?
Dieses Modell wird durch eine Data Parallel-Sprache wie FORTRAN unterstützt. Geschrieben werden die
Programme unter Nutzung sequentiellen FORTRANs, um die Berechnungen auf den Daten zu spezifizieren,
wobei sowohl iterative Konstrukte als auch Vektoroperationen von FORTRAN90 geliefert werden.
Daten-Mapping Direktiven werden verwendet, um die Verteilung von Arrays über verteilte Prozesse
zu spezifizieren.
Nennen Sie die drei Parallelrechner-Rechenprinzipien!
| Von Neumann | Steuerfluß-gesteuert |
Operationen werden entsprechend der gesetzten Befehlsfolge ausgeführt |
| Datenfluß | Datenfluß-gesteuert | Operationen werden
ausgeführt, sobald die dazu benötigten Daten verfügbar sind |
| Reduktion | Funktionsaufruf-gesteuert | Hierarchisch
verschachtelte Funktionen werden von der Hierarchie-spitze nach unten aufgelöst |
|
|
|
|
|
| Kapitel 1 | Einleitung |
|
Befehlsschleife, Risc und Cisc...
|
| Kapitel 2 | Interrupts |
|
Interrupts, Polling, DMA...
|
| Kapitel 3 | Speicherschutz |
|
Segmentation, Paging, Mapping, Multitasking...
|
| Kapitel 4 | Caches |
|
Lokalität, Cache-Arten, Schreibstrategien...
|
| Kapitel 5 | Risc |
|
Risc-Architektur, Load/Store, Registerfenster...
|
| Kapitel 6 | Pipelining |
|
Prinzip, Datenkonflikte, Forwarding, Delayed Load
|
| Kapitel 7 | Branch Prediction |
|
Statische / Dynamische Brach-Prediction...
|
| Kapitel 8 | Superskalarität |
|
Out-Of-Order Execution, Scoreboard und Tomasulo, VLIW...
|
| Kapitel 9 | Parallelrechner |
|
SMP,Vektorrechner, Cache-Kohärenz
|
|
|
|
|
|
|
|
|
Quellen:
|
Andrew S. Tanenbaum
Computerarchitektur
|
Andrew S. Tanenbaum
Moderne Betriebssysteme
|
Petterson
Computer Architectur & Design
|
Christian Märtin
Rechnerarchitekturen
|
Rehm
Skript und Vorlesung
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
|
|
Home 
RISC - CISC