Home

Impressum

kreissl.info[rmation science]

best practices

Parallelrechner

Kapitel 9 - Parallelrechner

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

Inhalt

Anfang

zurück

EOT

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