Parallele E/A auf Clustern
Joachim Worringen
Lehrstuhl für Betriebssysteme
RWTH Aachen
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Agenda
• Cluster, verteilte & parallele E/A• Anwendungen, Eigenschaften und
Entwicklung paralleler E/A• Verfahren und Implementationen• Fallstudien: Cplant & PVFS• Parallele E/A via SCI• Zusammenfassung
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Was sind Cluster ?
Eine Zahl eigenständiger, vernetzter Rechnersysteme zur Lösung einer oder mehrerer gleichartiger Aufgaben.
Aspekte:• Dedizierte Systeme – kein NOW
• „off-the-shelf“ Standardkomponenten – billig!
• Evtl. leistungsfähiges Verbindungsnetz
• 2 bis tausende Knoten
• Häufig: frei verfügbare Software
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Verteilte vs. Parallele E/A
Verteilte E/A:• Ein gemeinsamer Datenbestand steht einer Gruppe verteilter
Systeme gleichartig zur Verfügung
• Typische Nutzung: ein Prozess pro Datei
• Typische Architektur: Zentrales Speichersystem
Parallele E/A:• Paralleles Programm mit P > 1 Prozessen
• Gleichzeitige Nutzung mehrerer Speichergeräte für eine Datei
• Typische Nutzung: P Prozesse pro Datei gleichzeitig
• Notwendige Architektur: Parallel arbeitende Speichersysteme
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Parallele E/A auf Clustern
Parallele E/A: aufkommendes Thema Anfang 90er
• SMP-Server: Erweiterung existierender Technologie
• MPP: Spezialtechnologie und Algorithmik- Scalable IO-Initiative
- Vielzahl von Applikationsbibliotheken
- Neue Schnittstellen (MPI-IO)
• Cluster: Mischung von SMP- und MPP-Technologie- Neue Entwicklungs- und Einsatzbedingungen
- Übertragen von Erkenntnissen auf neue Umgebung
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Anwendungsfelder
• Datenbanken• Multimedia• Ingenieursanwendungen:
• Strömungssimulation• EM-Feld-Berechnungen• ... SFB Numerik ...
• Wissenschaftliche Simulationen:• Quantendynamische Molekülsimulation (Uni Münster):
- 6 x 580 MB/Molekül- Nicht-sequentielle Lese- & Schreibzugriffe
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Fälle paralleler E/A
Wann ist E/A in einem parallelen Programm erforderlich?• Ausgabe der Ergebnisse
- Einmalig oder wiederholt
- Online- oder Offline-Visualisierung
• Einlesen von Parametern / Initialisierung
• Temporäres Auslagern von Daten
• Fehlersuche / Validierung
• Checkpointing
• Out-of-Core Berechnungen
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Eigenschaften paralleler E/A
• N-facher Zugriff auf eine Datei• Burst-Charakteristik; zeitgleich von allen Prozessen
• Zugriffsmuster:• Typisch: Verschachtelt, aber regulär
• Mitunter irregulär
• 90 : 10 Regel: 90% der Zugriffe betreffen nur 10% der Daten
• Vielfach Schreibzugriffe• i.d.R. auf disjunkte Dateibereiche
• Lesezugriffe von externen Systemen• Häufig möglich: Überlappung von E/A / Berechnung
• Viel Hauptspeicher erforderlich !
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
E/A-Anforderungen: Abschätzung
• Hypothetisches System: F = 1 TFLOP/s Peak• Effektive Leistung: 10% Peak = 100 GFLOPS/s• FLOP-to-byte Verhältnis 500 : 1
Datenrate:
200 MB/s effektive, kontinuierliche E/A-Bandbreite
Datenrate:
Nach einer Woche: 120 TB• Problem:
• Daten sind verteilt
• Datenausgabe nicht kontinuierlich
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
E/A-Anforderungen: Entwicklung (1)
• RAM-Kapazität: M / F ~ 0.5 ... 1• E/A-Kapazität: Ctotal / M ~ 10 ... 20• Heute: 1 TFLOP/s-System
• Ctotal = 20 TB
• Mit Cdisk = 40 GB ist Ndisk = 500
• Mit Rdisk = 20 MB/s ist Rtotal = 10 GB/s
F/ Rtotal = 100
• Wachstum:• E/A-Datenrate: 40% pro Jahr• E/A-Kapazität: 100% pro Jahr• CPU-Leistung: 60% pro Jahr
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
E/A-Anforderungen: Entwicklung (2)
• 5 Jahre später – neuer Rechner:• F = 10 TFLOP/s (60% pro Jahr)
• entsprechend: Ctotal = 200 TB
• Mit Cdisk = 1200 GB und Rdisk = 100 MB/s: Rtotal = 166 * Rdisk = 16,6 GB/s
F / Rtotal = 625
Dieser Rechner hat ein 6-fach schlechteres Verhältnis von E/A-Rate zu CPU-Leistung !
Engpaß ist E/A-Rate, nicht E/A-Kapazität
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Kostenfaktoren
Was sind die Kostenfaktoren ? Flaschenhälse Optimierungspotential
• Zugriffszeiten Speichersystem (Platten)- Zahl der Anforderungen
- Suchzeiten & Bandbreite
• Kommunikationszeit- Zahl und Größe der Datenpakete / Nachrichten
• Überlastungseffekte- Zahl der Clients, die gleichzeitig eine Ressource nutzen
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Verfahren & Implementationen
• Aufbau von Systemen mit paralleler E/A• Verfahren zur Nutzung dieser Systeme• Implementationen
• Hardware
• Software
• Schnittstellen
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Striping
Basisverfahren zur Bandbreitenerhöhung:• Nutzung von N parallelen Speichersystemen bis zu N-fache Bandbreite
Stripetiefe
Stripefaktor
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
RAID (1)
Redundant Array of Inexpensive Disks• RAID 0: Striping ohne Redundanz
- N-fache Bandbreite bei N Platten
- softwaremäßig möglich
• RAID 3: Striping mit Redundanz- Jeder Zugriff erfolgt auf alle Platten
- gut für wenige, große Zugriffe
• RAID 5: Striping mit Redundanz- Separate Plattenverwaltung, verteilte Paritätsspeicherung
- bei kleinen, hochfrequenten Zugriffen besser als Level 3
- schlechter bei bei (langen) Schreibzugriffen
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
RAID (2)
Kombinationen einzelner RAID-Modi:• RAID 10: Modi 0 und 1 (Spiegelung)
- Striping über gespiegelte Platten
- Schnell & sicher, aber verschwenderisch
• RAID 53: Modi 0 (sic!) und 3- Striping über redudante Arrays
- Schneller als entspr. RAID 3
- Platz-effizienter als RAID 10
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Shared Memory (1)
SpeicherSpeicherPP PP PP PP
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Shared Memory (2)
cc-NUMAcc-NUMA
cc-NUMAcc-NUMA
SpeicherSpeicherPP PP PP PP
BridgeBridge
BridgeBridge
SpeicherSpeicherPP PP PP PP
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Distributed Memory (1)
Rechen- und E/A-Knoten
PP PP PP PP
PP PP PP PP
PP PP PP PP
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Distributed Memory (2)
Separates E/A Netz für SAN-System
PP PP PP
PP PP PP
PP PP PP
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Distributed Memory (3)
Homogene Universalknoten
P P P
P P P
P P P
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Dateisysteme: Architektur
Schnittstelle: Zugriff über
• Bibliothek• Betriebssystemschnittstelle
Dateistruktur• Verteilung der Daten über die Speichersysteme• Steuerbar durch den Benutzer ?
Implementationsaspekte:• Zuverlässigkeit (RAID ?)• Zugreifbarkeit – intern und extern• Caching – Ort und Größe des Caches, Konsistenzmodell• Andere Optimierungen (Prefetching)• Dedizierte E/A-Knoten ?
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Intel PFS
Einsatz in Intel Paragon:• Verteiltes Betriebssystem OSF/1 AD• Strikte Trennung der Knotenfunktionen:
- E/A, Compute, Service
• E/A-Knoten = Compute-Knoten + RAID-3• PFS setzt auf UFS auf
- Striping über mehrere UFS-Dateisysteme
• E/A-Knoten für Paging in Baumstruktur organisiert• Caching auf E/A-Knoten deaktivierbar
Einsparung (mindestens) eines Kopiervorgangs
• Prefetching
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Sun MC
Solaris MC: Sun Forschungsprojekt• Basierend auf Solaris
• Ziel: Multi-Computer mit Single-System-Image virtuelles SMP System
• Kernel-Dateisystem PXFS (Proxy File System):• Kohärentes Caching der Clients:
- Daten, Attribute, Verzeichniseinträge
- Granularität: VM page oder Cacheline (cc-NUMA)
• Hochverfügbarkeit und Replikation
• CORBA-basierte Schnittstellen / Kommunikation Ersatz für vnode-Schnittstelle
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Sun MC: Integration
KernelKernel
vnode1vnode1
Standard Solaris
vnode2vnode2
Solaris MC
KernelKernel
vnode/VFS
vnode/VFS
pxfs clientpxfs client CachesCaches
pxfs Serverpxfs Server
vnode1vnode1 vnode2vnode2
IDL
vnode/VFS
ProvidesProvides
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Sun MC: Hochverfügbarkeit
• Server-Replikation mit Shared Mirrored Disks• Client- und Serverausfälle sind transparent
pxfs Clientpxfs Client
pxfs Serverpxfs Server
logging UFSlogging UFS
pxfs Clientpxfs Client
pxfs Serverpxfs Server
logging UFSlogging UFS
Checkpointmessages
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Sun PFS: Kennzeichen
• Client/Server Prinzip- dedizierte oder nicht-dedizierte E/A-Knoten möglich
- Kommunikation über MPI
• Schnittstellen:- Standard-VFS Dateisystem
- Laufzeitbibliothek
• Optimiert auf große Dateien- Einfachere Dateiindizierung (als bei UFS)
- größere Datenblöcke (als bei UFS)
• Server-seitiges Caching
• Konsistenz: sequentiell oder „entspannt“
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Kernel
Userspace
Sun PFS: Architektur
RTLRTL
MPI-IO JobMPI-IO Job
Proxy-DaemonProxy-Daemon
VFSVFS PFSPFS
Unix CommandsUnix Commands
Kernel
Userspace
Raw I/O DeviceRaw I/O Device
Client Server
I/O-Daemon
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Sun PFS: Leistung
• 32 x HPC 450, 4 CPUs @ 300MHz, 4 GB RAM
• Dedizierte PFS-Platte, ATM-Netz (16MB/s)
• 32 Prozesse, verteilte Matrix, Spaltengröße variiert
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Sun PFS vs. UFS
Warum nicht immer PFS statt UFS ?• PFS optimiert auf typisches paralleles Lastprofil
• Schlechtere Leistung bei Standard-Lastprofil:- kein client-side caching & große Blöcke!
- Ineffizient für viele kleine Dateien: Platz & Overhead
• Verfügbarkeit:- Keine Redundanz zwischen den Servern Replikation / Software-RAID kostet Leistung
• Integrität:- Beschädigung auf einem Server betrifft gesamtes FS
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
IBM PIOFS / Vesta
Einsatz auf SP2 unter AIX:• Keine dedizierten E/A-Knoten
- Alle Knoten haben mindestens eine Platte- Zuweisung via Software (E/A, Compute, oder beides)
• Striping über JFS Dateisysteme- Stripe-Faktor pro Datei setzbar- Caching des JFS auf E/A-Knoten
• 2-Dimensionales Dateilayout möglich- Einrichtung von Sub-Dateien
• Standard-mäßiges mounten • Kommunikation über UDP/IP via SP2-Switch
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
IBM GPFS / Tiger Shark
Shared-Disk Dateisystem für SP2-Cluster:• Platten senden/empfangen Datenblöcke direkt über SP-
Switch
• Skalierbarkeit:- verteilte Verarbeitung der Metadaten
- Aber: tokenbasierte Synchronisation mit einzelnem Server!
• Tokensynchronisation für Schreibzugriffe feingranulare gemeinsame Zugrife: thrashing!
• Pagepool für Caching/Prefetching (typ. 20MB)
• Prefetching nur bei sequentiellen Zugriffen Sequentialisierung von versetzten Zugriffen
MPI-IO für irreguläre Zugriffe empfohlen!
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Weitere Systeme
• CXFS (SGI) - Komplexes SAN-FS• Fibre-Channel Interconnect, Hochverfügbar• Client-Side Caching• Standardschnittstellenicht (primär) für parallele E/A entworfen
• xFS (Berkeley NOW) – Software RAID• Datenreplikation• Jeder Rechen-Knoten ist auch E/A Knoten• ein Knoten als Manager pro Datei
kein zentraler Server
• Andere E/A-Modelle:• River (Berkeley): Datenflußmodell (Producer-Consumer)• Kopplung auf Device-Ebene (Honkkong)
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
PVFS
Siehe Fallstudie
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
POSIX
Standard-Unix-Dateioperationen:• open(), read(), write(), flush(), fcntl(), close()
• synchron
• Übermittelte Informationen:- Kontinuierlicher Datenblock (mit Länge)
- Position in der Datei
• Erweiterungen:- Asynchrone Ausführung
- Nicht-kontinuierliche Datenblöcke
Kein Ausdruck für Parallelität!
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Intel OSF/1 mit PFS
Erweiterungen von POSIX:• Synchrone und asynchrone Aufrufe
• Neue I/O-Modi:
PFS I/O ModiPFS I/O Modi
UngeordnetUngeordnet KnotenordnungM_RECORDKnotenordnungM_RECORD
AtomarM_UNIXAtomarM_UNIX
Nicht atomarM_ASYNCNicht atomarM_ASYNC
Gleiche DatenM_GLOBALGleiche DatenM_GLOBAL
Versch. DatenM_LOGVersch. DatenM_LOG
Nicht sync‘iertNicht sync‘iertsync‘iertM_SYNCsync‘iertM_SYNC
Getrennte DateizeigerGetrennte Dateizeiger Gemeinsame DateizeigerGemeinsame Dateizeiger
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
MPI-IO
• Ziel: Anwendungen mit hohem E/A-Anteil portabel und effizient zu machen
• Analogie zu Message Passing:- Daten schreiben / lesen = Nachricht senden / empfangen
• Unterstützung von collective buffering und disk-directed I/O durch Anwendungs-Schnittstelle
- Partitionierung der Datei zwischen Prozessen
- Kollektive Zugriffe
• (benutzerdefinierte) Datentypen
• Asynchrone Zugriffe
• Kontrolle der physikalischen Lage der Daten
• Teil des MPI-2 Standards, verschiedene Implementierungen
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
MPI-IO: etype & filetypes
etype: elementary datatype = MPI Datentyp• Grundeinheit des Datenzugriffs
filetype: aufgebaut aus etypes• Partitionierung der Datei auf die Prozesse
etype
filetype
Löcherview:
displacementSichtbare, zugreifbare Daten
...
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
MPI-IO: file partitioning
Mehrere Prozesse greifen auf eine Datei zu• Datenverteilung via filetypes & views
etype
filetype Prozess 0
filetype Prozess 1
filetype Prozess 2
view:
displacement
...
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
MPI-IO: API - Dateimanipulation
Common Prefix: MPI_File_...• open(), close(), delete(), ...
• set_info(), get_info()- Striping Parameter
- E/A-Knoten spezifizieren
- Felddimensionen („chunks“)
• set_view(), get_view()
View 1
View 2
Offset 1 Offset 2
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
MPI-IO: API – Individueller Zugriff
Positionierung blockierend? AufrufLokaler Zeiger
Expliziter Offset
Gemeinsamer Zeiger
blockierend
nicht-blockierend
blockierend
nicht-blockierend
blockierend
nicht-blockierend
readwriteiread / MPI_Waitiwrite / MPI_Waitread_atwrite_atiread_at / MPI_Waitiwrite_at / MPI_Waitread_sharedwrite_sharediread_shared / MPI_Waitiwrite_shared / MPI_Wait
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
MPI-IO: API – Kollektiver Zugriff
Positionierung blockierend? AufrufLokaler Zeiger
Expliziter Offset
Gemeinsamer Zeiger
blockierend
nicht-blockierend
blockierend
nicht-blockierend
blockierend
nicht-blockierend
read_allwrite_allread_all_begin / ...endwrite_all_begin / ...endread_at_allwrite_at_allread_at_all_begin / ...endwrite_at_all_begin / ...endread_orderedwrite_orderedread_ordered_begin / ...endwrite_ordered_begin / ...end
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Fallstudie: Cplant@Sandia
• MPP-Hintergrund- Ehemals größte Intel Paragon-Installation- ASCI Red / Intel TFLOPS
• Umstellung auf Off-the-shelf-Technologie• Konzept: Maximale Skalierbarkeit (1000e Knoten)
- Unabhängige, „skalierende“ Komponenten• Generische Technologie• Kontinuierlicher Aus- und Umbau des Systems
- Partitionierung des Systems in Funktionsbereiche• Trennung durch klare Schnittstellen• Einfache Umkonfiguration
- Ausreichend Ressourcen zur Systembeobachtung/wartung
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Cplant: Architektur
Prinzipieller Aufbau:
Realisation: vielstufige Entwicklung mehrere Clustergenerationen (z.Z. bis 1024 Knoten)
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Cplant: I/O, Stufe 1
• I/O-Dienst yod auf I/O-Knoten
• Round-Robin-Scheduling Compute – I/O Knoten
• „parallele“ I/O auf unabhängige, getrennte Dateien
• POSIX-Schnittstelle:pf_open(), pf_seek(), pf_read(), ...
• Jeder Prozeß arbeitet auf individueller Datei:- Brauchbar für temporäre Dateien etc.
- fixierte Zahl von Prozessen für Anwendung
- Administration der Dateien: Albtraum
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Cplant: I/O, Stufe 2
• ENFS-Dienst:• NFS ohne locking
• Keine Sychronisation
• Skalierbarkeit:• Mehrere Pfade zum Server
• I/O-Knoten als Proxy
• Server muß Leistung bringen:- 119 MB/s von 8 I/O-Knoten auf
eine SGI O2K mit XFS
• Einsatz: Visualisierung
VizNFS
ENFS ENFS ENFS ENFS
gigE switch
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Cplant: I/O, Stufe 3
Evaluierung:• PVFS ?
• Compaq’s Petal/Frangipani ?
• Anderes kommerzielles SAN-System ?
Fortsetzung unter www.cs.sandia.gov/cplant
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Fallstudie: PVFS
Vielzahl von frei verfügbaren Lösungen für parallele E/A:• Galley FS• Panda• PIOUS• PPFS• .... Forschungsprojekte mit bestimmten Schwerpunkt
PVFS:• Entwicklung & Zielgruppe• Architektur• Evaluation
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
PVFS: Entwicklung & Zielgruppe
Open-Source Entwicklung der Clemson University• Zielgruppe:
• Linux-Cluster mit TCP/IP Interconnect
• Designziele:• Hohe Bandbreite für typische parallele E/A
• Vielfältige API Unterstützung:- Native PVFS, Unix/POSIX, MPI-IO
• Integration:- Nutzbar mit Standard-Unix-Werkzeugen
- Allgemein: durch jede Anwendung ohne Neucompilierung
• Robust, skalierbar, einfach zu installieren, ...
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
PVFS: Architektur
• Frei konfigurierbare Knotentopologie:- Compute, I/O, Compute & I/O
• TCP/IP-Kommunikation• Zentraler Metadaten-Server• Aufsatz auf lokales Dateisystem:
- ext2, ReiserFS, ... Server-seitiger Cache
• Client-seitiger Cache? Prefetching?• Stripe-Konfiguration pro Datei
Nicht aufregend – aber einsatzfähig!
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
PVFS: Evaluation
• POSIX-Leistung sequentiell:• durch Interconnect auf 10MB/s beschränkt
• Designgerechter Einsatz: parallel BTIO Benchmark
- POSIX
- pseudo-POSIX via MPI-IO
- optimiertes MPI-IO
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BT / BTIO Benchmark
• BT: Teil der NAS Parallel Benchmarks• Strömungssimulation• Block-triagonaler Gleichungslöser• Diskrete Approximation• Gebietsaufteilung für quadratische Prozesszahl
• BTIO: Erweiterung um E/A• Abspeichern des 3D-Lösungsvektors alle N Berechnungschritte Nur Schreibzugriffe• Verschiedene Implementationen:
- Explizit parallel- MPI-IO „naiv“ und optimiert
• BT Klasse A: E/A-Größe etwas 420MB
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO: Datenstruktur
Logisch: 3D-Feld
Linearisierung für E/AEntlang der Dimensionen
Gebietszerlegung
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO: Testumgebung
8 Dual-SMP Knoten mit- 800MHz Pentium III- 512 MB RAM- 64bit / 66 MHz PCI- 30 GB IDE-Festplatte
• 7200 RPM, DMA 66MHz~ 25 MB/s Transferrate (Linux, ext2)
- 100 Mbit switched Ethernet (TCP/IP, MPICH P4)- SCI Interconnect (SCI-MPICH)- Linux 2.4.4- PVFS 1.5
• Jeder Knoten diente als I/O-Knoten• 20 GB pro Knoten für PVFS, entspr. 160GB Partitionsgröße
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BT: Ethernet vs. SCI
0
20
40
60
80
100
MFLOPS pro Prozess
Ethernet 80,27 75,83 52,6 44,19
SCI 80,27 76,25 58,57 52,25
1 4 9 16
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO via NFS: IO-Bandbreite
0
50
100
150
200
250
MB/s pro Prozess
explicit 37,93 32,18 13,86 5,02
simple 6,74 1,54 0,45 0,12
full 204,14 13,99 7,42 3,8
1 4 9 16
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO via PVFS: IO-Bandbreite
0
100
200
300
MB/s pro Prozess
explicit 59,88 61,98 94,52 28,4
simple 14,03 1,23 0,82 0,61
full 16,93 274,93 62,03 29,62
1 4 9 16
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – Caching in PVFS
Vergleich: 512 MB/Knoten vs 256 MB/Knoten (full MPI-IO)
0
50
100
150
200
250
300
MB/spro Prozess
512 MB 16,39 274,93 62,03 29,62
256 MB 61,05 32,91 20,01
1 4 9 16
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – Caching in PVFS
Vergleich: 512 MB/Knoten vs 256 MB/Knoten (full MPI-IO)
0
200
400
600
800
1000
1200
MB/sakkumuliert
512 MB 16,39 1099,71 558,3 473,96
256 MB 244,21 296,2 320,14
1 4 9 16
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Dedizierte IO-Knoten vs. Compute-IO-Knoten• Konzeptvergleich: Nutzung der Ressourcen
• Einfluß von CPU / Speicherauslastung auf E/A-Leistung
3 Testkonfigurationen:• 8 x C-IO:
• 4 x IO:
• 4 x C-IO:
BTIO: PVFS-IO-Topologie (1)
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO: PVFS-IO-Topologie (2)
050
100150200250300350
400
MB/s akkumuliert
4 9 16
8xC-IO
4xIO
4xC-IO
256 MB/Knoten (full MPI-IO)
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – simple MPI-IO (1)
call MPI_File_open(comm_solve, filenm, MPI_MODE_WRONLY + MPI_MODE_CREATE,
MPI_INFO_NULL, fp, ierr)
iseek = 0
call MPI_File_set_view(fp, iseek, MPI_DOUBLE_PRECISION,
MPI_DOUBLE_PRECISION,
'native', MPI_INFO_NULL, ierr)
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – simple MPI-IO (2)
do cio=1,ncellsdo kio=0, cell_size(3,cio)-1
do jio=0, cell_size(2,cio)-1
iseek=5*(cell_low(1,cio) + …. count=5*cell_size(1,cio)
call MPI_File_write_at(fp, iseek,
u(1,0,jio,kio,cio),count, MPI_DOUBLE_PRECISION, mstatus, ierr)
enddoenddo
enddo
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – simple MPI-IO (3)
MPI-IO-Trace: kompletter Compute-IO-Zyklus
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – simple MPI-IO (4)
MPI-IO-Trace: Beginn der IO-Phase
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – full MPI-IO (1)
Vereinbarung eines Datentyps: Block von 5 doublescall MPI_Type_contiguous(5, MPI_DOUBLE_PRECISION,
element, ierr)call MPI_Type_commit(element, ierr)call MPI_Type_extent(element, eltext, ierr)Aufteilung des gesamten Feldes in Subfelder call MPI_Type_create_subarray(3, sizes, subsizes,
starts, MPI_ORDER_FORTRAN, element, cell_btype(c), ierr)
Gesamtes Feld als ein Typ aus Subfeldern zusammengesetztcall MPI_Type_struct(ncells, cell_blength, cell_disp,
cell_btype, combined_btype, ierr)call MPI_Type_commit(combined_btype, ierr)call MPI_Type_extent(combined_btype, iosize, ierr)
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – full MPI-IO (2)
call MPI_File_open(comm_solve, filenm,
MPI_MODE_WRONLY+MPI_MODE_CREATE,
MPI_INFO_NULL, fp, ierr)
Datei als Folge von Subfeldern darstellen
iseek = 0
call MPI_File_set_view(fp, iseek, element,
combined_btype, 'native', info, ierr)
Gesamtes Feld ausgeben – ohne Schleife
call MPI_File_write_at_all(fp, iseek, u,
1, combined_btype, mstatus, ierr)
call MPI_Type_size(combined_btype, iosize, ierr)
iseek = iseek + iosize/eltext
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – full MPI-IO (3)
MPI-IO-Trace: kompletter Compute-IO-Zyklus
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
BTIO – full MPI-IO (4)
MPI-IO-Trace: Beginn der IO-Phase
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Parallele E/A via SCI
• SCI – Scalable Coherent Interface• Beschränkungen von E/A in verteilten
Systemen• „shared state“ Konzept
• Festes Striping: einfach, aber nicht immer optimal
• SVM-Prinzip: zu langsam, wenn Nachrichtenbasiert
• Aufbau & Potential
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Scalable Coherent Interface – Übersicht
• Protokoll für ein speicherkoppelndes Verbindungsnetz
• eigener 64-bit Adressraum
• optional: effiziente, verteilte Cache-Kohärenz
• kein Bus - aber bietet Bus-typische Dienste
• flexibel skalierbar
• transparent für Ziel und Quelle
• Standard seit 1992 (IEEE 1596-1992)
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Scalable Coherent Interface – Topologien
• Punkt-zu-Punkt Verbindungen zwischen „Mini-Switches“• Mögliche Topologien:
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Scalable Coherent Interface - Implementation
• Integrierte Systeme • PCI-SCI Adapter:
• 64-bit 66 MHz PCI-PCI Bridge
• Leistungseckdaten:- Datum schreiben 1,5 us
- Datum lesen 3,2 us
- Bandbreite PIO > 170 MB/s (90 % Peakbandbreite bei 512byte
Transfer)DMA > 250 MB/s
- Synchronisation~ 15 us
- Remote Interrupt ~ 30 us
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
E/A in Distrib. Memory Systemen
• Zugriffsmuster:• Häufig: synchroner Zugriff aller Prozesse• EIN Prozess kann Plattensystem ausnutzen 1:1 Verhältnis CPU/Plattensystem
• Verhältnis der Bandbreiten Netz vs. Platten• Netz: feste max. Bandbreite > Plattenbandbreite• Aber:
- (lokale) Plattenbandbreite skalierbar & deterministisch- i.d.R. zu wenig E/A-Knoten, um jeden Compute-Knoten zu
sättigen
soviel lokale E/A wie möglich !
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Shared State: Hintergrund
Maximierung der E/A-Lokalität durch Migration der Daten• SVM/DSM-Prinzip
• Probleme: Wo ist ein Datum? Synchronisation?
• Generischer Kommunikationsansatz: Nachrichtenaustausch
• Mögliche Kommunikation mit SCI: gemeinsamer Speicher
(Datei)zustand global sichtbar, somit: individuell lesbar / veränderbar
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Shared State: Prinzip
• globale Hashtabelle• lokale Kopien• Synchronisation über
gemeinsamen Speicher• Thread für Datentransport
• Server-Side Cache im FS• oder: RawIO in Zielpuffer
Eigenschaften:• volles Caching• Maximale Lokalität
bei festem Aufwand• Schnelle
Kommunikation
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Shared State: Lesezugriff
1. Lokalität bestimmen: Welcher Teil der Daten ist• In meinem Besitz? Lesezugriffe absetzen• Im lokalen Cache? Kopieren• Nicht lokal vorhanden? Siehe 2.
2. Entfernte Daten anfordern:• Hashwert bestimmen• In lokaler Hashtabelle suchen – gefunden?
Ja: ohne Lock global verifizieren – o.k.? Sonst s. ‚Nein‘Nein: in globaler Hashtabelle suchen:
- Leselock auf Hash-Entry setzen- Start-hnode finden & hnode-Kette aufbauen (beim Suchen hnodes in lokale Hashtabelle kopieren)
Daten anfordern !
3. Daten in lokalem Speicher cachen
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Shared State: Schreibzugriff
1. Lokalität bestimmen: Welcher Teil der Daten ist• In meinem Besitz? asynchrone Schreibzugriffe absetzen• Im lokalen Cache oder nicht lokal vorhanden? Siehe 2.
2. Entfernte Daten invalidieren:• asynchronen Schreibzugriff in lokale Datei absetzen• Gleichzeitig: hnode-Kette aufbauen (wie beim Lesen)
• ggf. ersten und letzten hnode aufteilen• Schreibanforderung setzen (Schreiblock!)
• Existierende Kopien invalidieren:• Aktuellem Besitzer der Daten: Invalidate schicken• dieser invalidiert alle weiteren Kopien
• Auf Invalidate-Bestätigungen und Schreibvorgang warten
3. Lokale & Globale Hashtabelle aktualisieren
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Zusammenfassung
Parallele E/A auf Clustern:• Probleme sind identisch zu MPP Systemen:
- Größe und Synchronität der Datenzugriffe, Verfügbarkeit
• Lösungsmöglichkeiten sind anders:- Plattenkapaziäten wachsen schnell
- Günstige RAID-Lösungen werden Standard Hohe knoten-lokale E/A-Kapazität Neue Möglichkeiten, neue Probleme
• Kommerzielle Lösungen verfügbar – aber: Lösungen immer problemspezifisch !?
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Quellen
• John M. May: Parallel I/O for High Performance Computing. Academic Press, 2001
• B. Nitzberg and S. Fineberg: Parallel I/O Tutorial. Supercomputing ’95
• Dokumente der SIO (Scalable IO) Initiative• Veröffentlichungen von
• Sun, SGI, Intel
• Sandia National Labs
• PVFS Manuals und Publikationen• ... weitere auf Anfrage
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Nun bitte...
Fragen, Bemerkungen, Widerspruch !
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Einleitung
• ClusterWas sind Cluster ?
• Parallele vs. Verteilte E/AWarum nicht NFS ?
Was macht parallele E/A cluster-spezifisch ?
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
Anwendungen paralleler E/A
• Anwendungsfelder• Anforderungen an E/A• Anwendungsfälle und -beispiele
Parallele E/A auf Clustern – Chemnitz 2001 Lehrstuhl für Betriebsysteme
„Single IO Space“ (SIOS)