Mimd-architekturen

Transcript

Vorlesung Rechnerarchitektur 2 Seite 42 MIMD-Architekturen Einführung MIMD-Architekturen verfügen im Gegensatz zu den SIMD-Architekturen über keine zentrale Steuerungsinstanz. Die Verarbeitungseinheiten können verschiedene Programmsequenzen autonom bearbeiten (lokale Autonomie) und verfügen damit jeweils über einen eigenen Programmzähler. Um die Verarbeitungseinheiten kostengünstig realisieren zu können, greift man häufig auf hochintegrierte Standard-Prozessoren (off-the-shelf processor, commodity-off-the-shelf) zurück. Diese erlauben durch ihre weite Verbreitung in Arbeitsplatzrechnern (workstations) oder eingebetteten Systemen die synergistische Nutzung des technologischen Fortschritts bei der Prozessorentwicklung und die Verwendung vieler sequentieller Softwarepakete für die Entwicklung oder Portierung von Anwendungen auf den MIMD-Parallelrechner. Aber auch Prozessorentwicklungen mit Eigenschaften speziell optimiert für die Anwendung in MIMD-Parallelrechnern sind in kommerziellen Systemen zu finden. Der Transputer [Inmos] ist eine der Entwicklungen, die bereits zu einem sehr frühen Zeitpunkt einen Prozessor mit einer Kommunikationseinheit auf einem Siliziumbaustein vereinte. Vergleich zu SIMD Trotz der großen Erfolge von SIMD-Architekturen (viele Supercomputer gehören in diese Klasse: Cray Y, NEC SX2, CM-2, etc.) ist die Ausführung nur eines Instruktionsstromes eine zu starke Einschränkung für die Ausnutzung der Parallelität auf allen Ebenen. Man muß aber beachten, daß der Erfolg dieser Systeme unter anderem auch auf der Compilerunterstützung (vektorisierende Compiler) beruht, die den Anwender bei der Programmierung dieser Systeme unterstützen. Vergleichbare Compiler gibt es für MIMD-Systeme nicht, bei nachrichtenorientierten Systemen muß der Anwender sogar explizite Kommunikation betreiben. MIMD-Systeme können im Vergleich zu den SIMD-Systemen durch die verteilten autonomen Steuerungsinstanzen mehr Parallelität ausnutzen und einen größeren Anwendungsbereich erschließen. Ein anderer wichtiger Punkt ist die Skalierbarkeit, der größte Vorteil der MIMD-Systeme mit verteiltem Speicher. Im Vergleich zu den MIMD-Systemen skalieren SIMD-Systeme eher schlecht, insbesondere die Vektorrechner. Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 43 MIMD-Architekturen Einteilung der MIMD-Architekturen MIMD-Architekturen lassen sich bezüglich verschiedener Merkmale unterscheiden, welche in der folgenden Abbildung dargestellt sind. Diese Merkmale sind orthogonal zueinander. physikalische Speicheranordnung gemeinsamer Speicher verteilter Speicher Programmiermodell Adressraum global, gemeinsam globaler Adressraum lokal, privat Synchronisation Kommunikationsstruktur Speicherkopplung Nachrichtenorientiert gemeinsame Variablen Semaphoren Nachrichten synchronisierende Nachrichten Latenzbehandlung verstecken minimieren In speichergekoppelten Systemen wird meist nur das Programmiermodell des globalen Adressraums verwendet, da es keine Datenverteilung erfordert und somit einfacher zu handhaben ist. Natürlich lässt sich in speichergekoppelten Systemen aber auch nachrichtenorientiert kommunizieren. Die physikalische Speicheranordnung ist eines der meistbenutzten Unterscheidungsmerkmale, womit sich die MIMD-Systeme in zwei Hauptkategorien einteilen lassen: • speichergekoppelte Systeme (shared memory architectures), Multiprocessors • Systeme mit verteiltem Speicher (distributed memory architectures), Multicomputers Bei dieser Unterteilung sollte beachtet werden, daß die physikalische Anordnung des Speichers sich durchaus von der logischen Sicht des Adressraums unterscheiden kann. Die Bezeichnung des gemeinsamen Speichers (shared memory) wird sowohl für die physikalische Anordnung als auch für die logische Sicht des Adressraums verwendet Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 44 MIMD-Architekturen Globale Architektur Mg Mg Mg Mg ‘shared memory’ Multiprozessor VN P P P P Mischformen VN P Ml P Ml P Ml P Ml ‘message based’ Multiprozessor • geringe Anzahl von P • VN mit hoher Bandbreite • Kommunikation durch gemeinsame Variablen • Synchronisation durch kritische Bereiche • sehr hohe Anzahl von P möglich • VN mit geringerer Bandbreite • Kommunikation durch Datentransport von Objekten • Synchronisation durch Botschaftenaustausch Die weiteren Merkmale sind stark durch diese physikalische Struktur der Speicherankopplung beeinflußt. Bei Systemen mit gemeinsamem Speicher finden wir fast ausschließlich den globalen, gemeinsamen Adressraum als Programmiermodell mit den gemeinsamen Variablen zur Synchronisation vor (shared memory). Bei Systemen mit verteilten Speicher ist naturgemäß das nachrichtenorientierte Programmiermodell vorzufinden (message passing). Es ist aber durchaus möglich, auf ein solches System durch entsprechende Hard- und Softwareverfahren einen gemeinsamen Adressraum aufzusetzen. Diese Vorgänge sind für den Anwender transparent, ihm erscheint das eigentlich auf verteiltem Speicher basierende System wie ein System mit gemeinsamen Speicher. Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 45 MIMD-Architekturen Distributed Memory vs. Shared Memory Mnemonics Bei Systemen mit physikalisch verteiltem Speicher ist zu unterscheiden, ob die Prozessoren ausschließlich auf ihre zugeordneten lokalen Speicher zugreifen können (verteilter lokaler Speicher, distributed local memory) und der Datenaustausch explizit durch Nachrichten erfolgen muß, oder ob ein Prozessor auch Zugriff auf die Speicher der anderen Prozessoren hat (verteilter gemeinsamer Speicher, distributed shared memory, DSM). Die zwei unterschiedlichen Sichtweisen des Adressraums - lokaler oder gemeinsamer - unterteilt die MIMD-Rechner mit verteiltem Speicher in zwei vom Programmiermodell recht unterschiedliche Architekturformen. Es sollte beachtet werden, daß bei den Architekturbezeichnungen oft bei den Systemen mit verteiltem gemeinsamen Speicher die Bezeichnung der physikalischen Verteilung des Speichers weggelassen wird und nur die Sicht des Adressraums hervorgehoben wird (shared memory), wohingegen bei den Systemen mit verteiltem lokalen Speicher allein die physikalische Verteilung die Bezeichnung dominiert (distributed memory). physikalische Speicheranordnung gemeinsamer Speicher Programmiermodell Adressraum global, gemeinsam verteilter Speicher lokal, privat Lehrstuhl für Rechnerarchitektur - Universität Mannheim globaler Adressraum Nachrichtenorientiert WS03/04 Vorlesung Rechnerarchitektur 2 Seite 46 MIMD-Architekturen Architekturunterscheidung nach Programmiermodell und Latenz Aus den beiden Unterscheidungsmerkmalen Programmiermodell und Latenzbehandlung lassen sich die MIMD-Architekturen wie folgt einteilen: [Gil93] MIMD-Architekturen Programmiermodell Nachrichtenorientiert Behandlung der Kommunikationslatenz globaler Adressraum Latenz minimieren Latenz verstecken Distributed Memory Architecture Multiprocessor System with Central Memory Distributed Shared Memory Architecture Virtual Shared Memory Architecture Multithreaded Architecture Architekturen mit verteiltem Speicher Multiprozessor mit zentralem Speicher Architektur mit verteiltem gemeinsamem Speicher Architektur mit virtuell gemeinsamem Speicher Mehrfädige Architektur Eigenschaften: Speicherzugriff: nur lokal Granularität: grob Skalierbarkeit: sehr gut Working Sets: nicht genutzt Eigenschaften: Speicherzugriff: zentral Granularität: fein Skalierbarkeit: schlecht Working Sets: (nicht) genutzt Eigenschaften: Speicherzugriff: lokal und entfernt Granularität: fein Skalierbarkeit: mittel Working Sets: genutzt, im Cache Eigenschaften: Speicherzugriff: nur lokal Granularität: grob Skalierbarkeit: gut Working Sets: genutzt, im lok. Sp. Eigenschaften: Speicherzugriff: lokal und entfernt Granularität: fein oder mittel Skalierbarkeit: gut Working Sets: (nicht) genutzt DSM: Distributed Shared Memory VSM: Virtual Shared Memory (bzw. in Literatur: SVM: Shared Virtual Memory) [Kai Li] MTA: Multi-threaded Architecture SMT: Simultaneous Multi-Threading Im folgenden soll nun die Unterscheidung nach der physikalischen Speicherstruktur näher beschrieben werden. Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 47 MIMD-Architekturen Gemeinsamer Speicher In Architekturen mit gemeinsamem Speicher (shared memory architecture) arbeiten die Prozessoren auf einem von allen Prozessoren zugänglichen Speicher. Das Verbindungsnetzwerk stellt die Transportwege für die zu übertragenden Daten von den Speichern zu den Prozessoren zur Verfügung. Die erforderliche Speicherbandbreite läßt sich nur durch mehrere parallele Speichermodule aufbringen. Entscheidend für die Architekturform ist, daß die Kommunikation zwischen den Prozessoren über gemeinsame Daten (shared variables) im gemeinsamen Adressraum des Speichers erfolgt. Bei der Zugriffsweise auf den Speicher lassen sich im wesentlichen drei Klassen von Architekturen unterscheiden: - gleichförmiger Speicherzugriff (‘uniform memory access’, UMA) - ungleichförmiger Speicherzugriff (‘non-uniform memory access’, NUMA) - nur Cachespeicherzugriffe (‘cache-only memory architecture’, COMA) [Hwang] Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 48 MIMD-Architekturen UMA Bei der UMA-Architektur ist die Zugriffsweise aller Prozessoren auf die Speichermodule identisch (uniform memory access), der Zugriff auf die Speicherworte ist für alle Prozessoren gleich. Jeder Prozessor kann trotzdem einen eigenen Cache haben. Prozessor 0 Prozessor 1 Prozessor 2 Prozessor n-1 Verbindungsnetzwerk Speicher 0 Speicher 1 Speicher 2 Speicher m-1 UMA-Parallelrechner Da sich Prozessoren und Speichermodule wie in einem Tanzsaal gegenüberstehen, wird die symmetrische Form auch als Tanzsaal-Architektur (dance-hall architecture) bezeichnet. Alle Prozessoren haben bei dem Zugriff auf den zentralen Speicher eine gleichförmige Zugriffslatenz. Die Anzahl der Prozessoren und der Speichermodule muß aber nicht notwendigerweise gleich sein. Der Zugriff auf die Daten dieses speichergekoppelten Systems wird durch das Verbindungsnetzwerk zwischen den Prozessoren und den Speichermodulen ausgeführt. Die Datenzugriffe erfolgen von den Prozessoren durch elementare Lade- und Speicherbefehle. Das Verbindungsnetzwerk benötigt bei dieser Speicheranordnung eine recht hohe Bandbreite, um allen Prozessoren einen möglichst schnellen und konfliktfreien Zugriff auf die Daten zu ermöglichen. Diese Anforderungen lassen sich nur bei einer geringen Anzahl von Prozessoren erfüllen, so daß die existierenden UMA-Architekturen mit gemeinsamem Speicher nur über eine sehr begrenzte Anzahl von Prozessoren verfügen. Das Verbindungsnetzwerk stellt hierbei die entscheidende Begrenzung für die Skalierbarkeit dar. Man kann symmetrische und asymmetrische Architekturen unterscheiden. • In symmetrischen Architekturen haben alle Prozessoren Zugang zu der Peripherie. • In asymmetrischen Architekturen gibt es einen Master-Prozessor, auf dem das Betriebssystem läuft und der I/O-Anforderungen bedient. Dieser steuert die Slave-Prozessoren. Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 49 MIMD-Architekturen UMA Als Beispiel für eine UMA-Architektur kann jedes heutzutage aktuelle SMP (symmetric multi-processing) System aufgeführt werden. Dies sind Systeme nach obiger Definition, bestehend aus einem Speicher und mehreren Prozessoren (Dual-XEON, Dual-Athlon, Quad*, ...). Obwohl es bei diesen Systemen einen dedizierten Bootprozessor gibt, d.h. der die Aufgabe der Initialisierung der Hardware und den Einsprung in das OS übernimmt, sind diese Systeme symmetrisch: Im laufenden Betrieb gibt es keine Einschränkungen bei den verschiedenen Prozessoren. In der folgenden Figur sind die Zugriffsschemata für ein symmetrisches UMA-System aufgeführt. Da man die Zugriffszeiten auf die Speicherworte vergleicht, wird der Unterschied zwischen der Zugriffszeit in den Cache und in den Hauptspeicher nicht beachtet. Blockschaltbild UMA P P Processor Cache Zugriff C globaler Zugriff C VN System controller & Address crossbar C Processor Processor Processor I/O bridges a x n data crossbar P Sun Enterprise 450 (4x UltraSPARC-II) Memory M M M SMP-Systeme Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 50 MIMD-Architekturen NUMA Um die hohen Anforderungen an das Verbindungsnetzwerk abzumildern, kann man die Speichermodule den einzelnen Prozessoren lokal zuordnen und nur den globalen Zugriff über das Verbindungsnetzwerk ausführen. Der Zugriff auf den lokalen Speicher eines Prozessors ist schneller als der Zugriff auf einen entfernten Speicher, da hier noch die Verzögerung des Verbindungsnetzwerkes hinzukommt. Daher werden die Zugriffszeiten ungleichförmig und man erhält eine NUMA-Architektur. Wenn man eine UMA-Architektur um eine Speicherhierarchie erweitert, erhält man ebenfalls eine NUMA-Architektur. In diesem Falle gibt es wie im ersten Fall Prozessoren mit lokalen Speicher, aber auch einen globalen Speicher. Daraus ergeben sich drei verschiedene Zugriffsmodi mit verschiedenen Zugriffszeiten: Zugriff auf lokalen Speicher, Zugriff auf globalen Speicher und Zugriff auf entfernten lokalen Speicher. (Hierarchie ist nicht mit Caches zu vergleichen!) Beispiel AMD Opteron: Hier werden die Prozessoren in einem Gitter angeordnet und mit dem Hypertransport-Verbindungsnetzwerk verbunden. Jedem Prozessor ist sein eigener Speicher zugeordnet, der jedoch global zugänglich ist. Da jeder Prozessor auf den lokalen und den entfernten Speicher zugreifen kann, ist dies eine NUMA-Architektur. P P M lokaler Zugriff globaler Zugriff M VN P Prozessor M Speicher VN Verbindungsnetzwerk NUMA-Parallelrechner Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 51 MIMD-Architekturen Cache-Kohärenz bei (N)UMA Der Einsatz von Cache-Speichern bei den Prozessoren führt für Daten (nicht für Instruktionen, da keine Schreiboperationen auf Code) auf das Problem der Cache-Kohärenz [Dubois Scheurig]. Da jetzt lokale Kopien des Hauptspeichers in den Caches der Prozessoren existieren, muß mit Hilfe von Konsistenzprotokollen die Gültigkeit der Daten gewährleistet werden. Für Architekturen mit einem Bus als Verbindungsnetzwerk kann die Cache-Kohärenz z.B. durch das MESI-Protokoll gewährleistet werden. Dafür muß jeder Cache-Speicher die Bustransfers überwachen (snooping) und die Cache-Einträge gemäß den Protokollzuständen (modified, exclusive, shared, invalid) verwalten. Solche Systeme sind nur bedingt erweiterbar, da die Transferleistung vom Bus begrenzt ist. Die Einhaltung der Cache-Kohärenz bei anderen Verbindungsnetzwerken ist wesentlich aufwendiger und bedarf der Hardwareunterstützung. Das SCI-Protokoll (scalable coherent interface) und seine Implementierung durch einen schnellen seriellen Verbindungskanal stellt eine mögliche Lösung dar, aber auch der Hypertransport von AMD ist ein cache-kohärentes Verbindungsnetzwerk. Bei UMA-Architekturen wird normalerweise nicht nach Cache-Kohärenz unterschieden, aufgrund der einheitlichen Zugriffsweise ist eine Cache-Kohärenz unproblematisch und alle UMA-Architekturen, die einen Cache haben sind auch cache-kohärent. Es sollte jedoch erwähnt werden, daß bei der klassichen UMA-Architektur, der Dance-Hall-Architecture, der Cache per Definition nicht vorhanden ist. Cache-kohärente NUMA-Architekturen werden auch als CC-NUMA bezeichnet, nicht cache-kohärente auch als NCC-NUMA. Beispiele für CC-NUMA: • Stanford DASH • MIT Alewife • SGI Origin 2000 Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 52 MIMD-Architekturen COMA Ein Weiterentwicklung der NUMA-Architektur ist die COMA-Archtitektur, hier werden die Speichermodule ausschließlich als Cache-Speicher benutzt. Alle Cache-Speicher befinden sich in einem globalen Adressraum. Die Speicherhierarchie entfällt. P D VN C P P P C C C D D D Prozessor Directory Verbindungsnetzwerk Cache VN COMA-Architektur Da diese Systeme zwingend cache-kohärent sein müssen, ist hier eine Unterstüzung der Hardware notwendig. Daher wird der Zugriff auf die entfernt liegenden Caches durch eine cache-directory [Dash] unterstützt. Die Datenobjekte werden durch den Cache-Mechanismus zu dem Prozessor transportiert, von dem sie zur Berechnung angefordert werden [KSR2]. Dieser Mechanismus sorgt auch für Invalidierungen bei Schreiboperationen. Beispiele für COMA-Architekturen: • Data-Diffusion-Machine (DDM) • Kendall Square Research (KSR-1, KSR-2) Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 53 MIMD-Architekturen Verteilter Speicher In Architekturen mit verteiltem Speicher (distributed memory architecture) sind die einzelnen Speichermodule über das System verteilt und typischerweise den Prozessoren physikalisch zugeordnet. Hat jeder Prozessor nur Zugriff auf seinen lokalen Speicher, so spricht man von einem verteilten Speicher mit lokalem Adreßraum (distributed local memory). Eine solche Architektur kann somit keine Zugriffe auf Speicher anderer Knoten durchführen (no-remote memory access) und wird auch als NORMA-Architektur bezeichnet. Die Verbindung der Prozessoren untereinander erfolgt über das Verbindungsnetzwerk. Das Verbindungsnetzwerkinterface (VNI, oder Network Interface Controller NIC), der Prozessor und der lokale Speicher bilden eine Funktionseinheit, die als Knoten (Verarbeitungsknoten) bezeichnet wird. Sind alle Knoten im System gleich, so liegt ein symmetrischer Parallelrechner vor. Asymetrische Systeme entstehen durch Knotentypen, deren Funktionen erweitert oder spezialisiert sind. Solche Funktionseinheiten bezeichet man typischerweise als Spezial-Knoten, wobei je nach Funktion die Namensgebung erfolgt (z.B. Ein/AusgabeKnoten). Das folgende Bild zeigt die prinzipielle Struktur eines Parallelrechners mit verteiltem Speicher: Knoten Knoten Knoten M M M P P P nur lokale Zugriffe VNI VNI VNI BotschaftenVerbindungsnetzwerk VN austausch Parallelrechner mit verteiltem Speicher Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04 Vorlesung Rechnerarchitektur 2 Seite 54 MIMD-Architekturen Verteilter Speicher Die Prozessoren besitzen eine sehr enge Verbindung zu ihren lokalen Speichermodulen, die damit über eine sehr hohe Zugriffsbandbreite und eine geringe Latenz verfügen. Die Verbindung der Knoten untereinander erfolgt nur über die Schnittstelle zum Verbindungsnetzwerk, die in den meisten Parallelrechnern dieses Typs eine geringere Bandbreite besitzt als das Speicherinterface. Die Kommunikation erfolgt ausschließlich über den Austausch von Nachrichten oder Botschaften (messages). Das Verbindungsnetzwerk kann von geringerer Leistung und höherer Latenz sein als bei der Realisierung des gemeinsamen Speichers, wenn es möglich ist, die Daten in den lokalen Speichern zu halten. Eine große Zahl von numerischen Applikationen zeigt diese ausgeprägte Lokalität der Daten, hervorgerufen z.B. durch die physikalische Anordnung des Lösungsraumes. Aufgrund der geringeren Anforderungen an das Verbindungsnetzwerk und den Wegfall von entfernten Zugriffen (remote-access), ist es leichter solche Systeme skalierbar zu entwerfen. Die klassische Beispiel für solche Architekturen sind die Cluster-Systeme. Cluster-Systeme bestehen aus normalen PCs (COTS) und werden über normale Verbindungsnetzwerke wie z.B. Ethernet verbunden. Für eine bessere Leistungsfähigkeit gibt es auch speziell für distributed-memory entworfene Systeme, die System-Area-Interconnects (SAN). Beispiele für SANs sind: • • • • • • Myrinet Quadrics QsNet ATOLL SCI (Infiniband) ... Lehrstuhl für Rechnerarchitektur - Universität Mannheim WS03/04