Upload
hedda-geister
View
222
Download
1
Embed Size (px)
Citation preview
Software Engineering Software Engineering SS04SS04
Paralleles Paralleles ProgrammierenProgrammieren
FH Aachen, 20.04.2004
Prof. Dr.-Ing. Michael Trautwein
Andrej Kühnal, Perez-Otuno Rodrigo
InhaltverzeichnissInhaltverzeichniss
EinfEinfürungürung Ansätze zur Parallelisierung
SISD SISD SIMD SIMD MIMD MIMD SPMDSPMD
Speicher ModelleSpeicher Modelle Shared MemoryShared Memory Distributed MemoryDistributed Memory
SISD + SIMD Program BeispieleSISD + SIMD Program Beispiele Vektor addition (SISD)Vektor addition (SISD) Vektor addition (SIMD)Vektor addition (SIMD)
Shared MemoryShared Memory Distributed MemoryDistributed Memory GlossarGlossar LiteraturLiteratur
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Warum Paralleles Programmieren?Warum Paralleles Programmieren?
Schnell Ergebniss berechnen.Schnell Ergebniss berechnen.
Grossere Daten Mengen bearbeiten.Grossere Daten Mengen bearbeiten.
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
Ansätze zur Parallelisierung
- SIMD Konzept (parallel)- SPMD Konzept (parallel)- MIMD Konzept (parallel)- SISD Konzept (seriel)
Was ist Paralleles Programmieren?Was ist Paralleles Programmieren?
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Was ist Paralleles Programmieren?Was ist Paralleles Programmieren?
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
Speicher Modelle für paralelles Speicher Modelle für paralelles Programmieren:Programmieren:
Distributed Memory (Cluster)
– MPI– PVM
Shared memory (SMP - Symmetric Multiprocessor Systeme)
– OpenMP– Threads++– Windows API
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
…
…
…3 5 7 11
13 17 19 23
Serielle additionSerielle addition (ein (ein SISD BefehlSISD Befehl))
int* x=new int[N];int* x=new int[N];int* y=new int[N];int* y=new int[N];int* z=new int[N];int* z=new int[N];……for (I=0; I<N; I++)for (I=0; I<N; I++) z[i]=x[i]+y[i];z[i]=x[i]+y[i];
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
+
16 22 26 34
+ + +
SISD - Single Instruction Single Data
x =y =
z =
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
…
…
…
13 17 19 23
16 22 26 34
3 5 7 11
Parallele additionParallele addition (ein (ein SIMD BefehlSIMD Befehl))
include <dvec.h>;include <dvec.h>; // from Processor Pack for MS Visual studio// from Processor Pack for MS Visual studio I32vec4* x4=new I32vec4[N/4];I32vec4* x4=new I32vec4[N/4];I32vec4* y4=new I32vec4[N/4];I32vec4* y4=new I32vec4[N/4];I32vec4* z4=new I32vec4[N/4];I32vec4* z4=new I32vec4[N/4];……for (I=0; I<N/4; I++)for (I=0; I<N/4; I++)
z4[i]=x4[i]+y4[i];z4[i]=x4[i]+y4[i];
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
26 32 36 44
13 15 17 21
13 17 19 23
+ + + ++ + + +
I32vec4
SIMD - Single Instruction Multiplete Data
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Shared MemoryShared MemoryBasis konzepteBasis konzepte Beim verteiltem Speicher (Beim verteiltem Speicher ( distributed memory distributed memory) ) ist ist jedem Prozessor ein Teiljedem Prozessor ein Teil des Speichers des Speichers zugeordnetzugeordnet
Beim Konzept des gemeinsamen Speichers (Beim Konzept des gemeinsamen Speichers ( shared shared memorymemory)greifen alle Prozessoren auf )greifen alle Prozessoren auf denselben denselben SpeicherSpeicher zu zu
Klassischen Klassischen Shared MemoryShared Memory Parallelisierung Parallelisierung versucht das Betriebssystem, versucht das Betriebssystem, mehrere mehrere ProgrammteileProgrammteile auf verschiedenen Prozessoren auf verschiedenen Prozessoren gleichzeitig abzurabeitengleichzeitig abzurabeiten
Perez-Otuno Perez-Otuno RodrigoRodrigo
Kühnal AndrejKühnal Andrej
Shared MemoryShared MemoryGrundlagenGrundlagen Allerdings verfügt jeder Prozessor Allerdings verfügt jeder Prozessor
zumindest über einen eigenen Cachezumindest über einen eigenen Cache
Shared Memory ist nur bei Bus--basierten Shared Memory ist nur bei Bus--basierten Systemen und bei Cross--Bar anwendbarSystemen und bei Cross--Bar anwendbar
Inter--Prozessor-Kommunikation erfolgt Inter--Prozessor-Kommunikation erfolgt
über den Hauptspeicher selber oder über den Hauptspeicher selber oder spezielle Kommunikationsregisterspezielle Kommunikationsregister
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Shared MemoryShared Memory Probleme entstehen,Probleme entstehen, wenn Unterprogrammaufrufe nach dem Schema wenn Unterprogrammaufrufe nach dem Schema
call sub1(einfeld,ausfelda) call sub1(einfeld,ausfelda) call sub1(einfeld,ausfeldb) call sub1(einfeld,ausfeldb) call sub1(einfeld,ausfeldc) call sub1(einfeld,ausfeldc) call call sub1(einfeld,ausfeldd) sub1(einfeld,ausfeldd)
call sub1(einfeld,ausfelde)call sub1(einfeld,ausfelde) ein Feld wie einfeld in ansonsten unabhängigen ein Feld wie einfeld in ansonsten unabhängigen Unterprogram- maufrufen verwendenUnterprogram- maufrufen verwenden
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Shared MemoryShared MemoryVorteile von SMP:Vorteile von SMP:
Gesamtsystem erscheint für jeden Prozeß wie ein Gesamtsystem erscheint für jeden Prozeß wie ein Einprozessorsystem; Einprozessorsystem;
keine Programmanpassungen vorhandener keine Programmanpassungen vorhandener Software notwendig. Die Vorteile von SMP können Software notwendig. Die Vorteile von SMP können durch Anpassung der Software bei Bedarf dennoch durch Anpassung der Software bei Bedarf dennoch genutzt werden; genutzt werden;
durch die gemeinsame Verwendung von durch die gemeinsame Verwendung von Hauptspeicher und Peripheriegeräten sind SMP-Hauptspeicher und Peripheriegeräten sind SMP-Systeme recht preiswert realisierbar.Systeme recht preiswert realisierbar.
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Shared MemoryShared MemoryNachteile von SMP:Nachteile von SMP:
Relativ großer Overhead bei Betriebssystem und Relativ großer Overhead bei Betriebssystem und Hardware notwendig, um Einprozessor-Illusion für Hardware notwendig, um Einprozessor-Illusion für Applikationen zu erzeugen; Applikationen zu erzeugen;
Hohe Auslastung des Busses oder Switches, der die Hohe Auslastung des Busses oder Switches, der die Prozessoren mit gemeinsam benutztem Speicher Prozessoren mit gemeinsam benutztem Speicher und Peripheriegeräten verbindet; und Peripheriegeräten verbindet;
Der Zugriff auf von mehreren Prozessoren Der Zugriff auf von mehreren Prozessoren gemeinsam genutzte Speicherbereiche muß durch gemeinsam genutzte Speicherbereiche muß durch sog. Locks geregelt werden, das bedingt einen sog. Locks geregelt werden, das bedingt einen erhöhten Verwaltungsaufwand für das erhöhten Verwaltungsaufwand für das Betriebssystem. Betriebssystem.
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Shared MemoryShared Memory
Open MPOpen MP
Thread++Thread++
Java ThreadsJava Threads
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
ParallelprogrammierungParallelprogrammierungWarum Warum
Parallelprogrammierung? Parallelprogrammierung? Programme, die auf Programme, die auf
externe Ereignisse externe Ereignisse reagieren müssen, sind reagieren müssen, sind schwierig, sequentiell zu schwierig, sequentiell zu programmieren. programmieren.
In parallelen Programmen In parallelen Programmen wird die Problemstellung wird die Problemstellung in Teilaufgaben zerlegt, in Teilaufgaben zerlegt, die parallel ausgeführt die parallel ausgeführt werden können werden können
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
ThreadThread Was ist Thread?Was ist Thread?
Thread = leichtgewichtiger Prozess = Prozess, der sich mit anderen den
gleichen Adressbereich(bzw. die gleiche Ausführungsumgebung) teilt
= sequentieller "Kontrollflussfaden" innerhalb eines Programms
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
ThreadsThreadsBeispiele „Parallele Beispiele „Parallele Programmierung“Programmierung“
mit Java threadsmit Java threads Mit Threads++Mit Threads++
Shared Memory interfaceShared Memory interface Open MPOpen MP Windows NTWindows NT
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Java ThreadsJava Threads Für die Anwendung von Für die Anwendung von
„Shared Memory“ brauchen „Shared Memory“ brauchen wir die grundlegenden wir die grundlegenden SynchronisationskonzepteSynchronisationskonzepte
In Java gibt es eine In Java gibt es eine Basisklasse Basisklasse java.lang.Threadjava.lang.Thread, die einen , die einen fertigen Thread darstelltfertigen Thread darstellt
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Thread ++Thread ++A New Solution to the Multi-threading A New Solution to the Multi-threading
DilemmaDilemma
Eine C++ Klassenbibliothek, die den Umgang mit den Eine C++ Klassenbibliothek, die den Umgang mit den POSIX-Threads durch die Einbettung in Klassen POSIX-Threads durch die Einbettung in Klassen erleichtern soll erleichtern soll
Aktuelle Fehler hat Entwickler gezwungen zwischen 2 Aktuelle Fehler hat Entwickler gezwungen zwischen 2 Optionen zu wählen:Optionen zu wählen:
1.1. threads anwenden um die Effizienz und Ausführung zu threads anwenden um die Effizienz und Ausführung zu verbessern verbessern
2.2. versichern dass die Anwendungen betriebssicher sindversichern dass die Anwendungen betriebssicher sind
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Threads++Threads++ Threads++ löst dieses Dilemma Threads++ löst dieses Dilemma
indem es die Entwickler der indem es die Entwickler der multithreaded applications erlaubt multithreaded applications erlaubt diese Anwendung gründlich zu diese Anwendung gründlich zu testen – ebenso wie die threads- mit testen – ebenso wie die threads- mit einem state-of-the-art automatic einem state-of-the-art automatic runtime error-detection tool. runtime error-detection tool.
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Open MPOpen MPApplication Program Interface(API)Application Program Interface(API)
OpenMP hat sich kürzlich als ein OpenMP hat sich kürzlich als ein IndustirestandardIndustirestandardinterfaceinterface für für sharedshared memorymemory Programmierungen über parallele Programmierungen über parallele ComputeranwendungenComputeranwendungen
unterstützt multi-platform shared-memory unterstützt multi-platform shared-memory parallel programming in parallel programming in C/C++C/C++ und und FortranFortran
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Open MPOpen MP In allen Architekturen, einschließlich In allen Architekturen, einschließlich UnixUnix
platforms und platforms und Windows NTWindows NT platforms platforms
Es ist ein Es ist ein portableportable, , scalablescalable Modell, Modell, welches shared-memory-Programmierern welches shared-memory-Programmierern ein einfaches und flexibles Interface ein einfaches und flexibles Interface ermöglicht um parallele Anwendungen für ermöglicht um parallele Anwendungen für Plattformen (vom Desktop bis zum Plattformen (vom Desktop bis zum Supercomputer) zu entwickelnSupercomputer) zu entwickeln
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
BeispielBeispiel#include <omp.h> #include <omp.h> main ()main () { int nthreads, tid;{ int nthreads, tid;#pragma omp parallel private(nthreads, tid)#pragma omp parallel private(nthreads, tid) {tid = omp_get_thread_num();{tid = omp_get_thread_num(); printf("Hello World from thread = %d\n", tid);printf("Hello World from thread = %d\n", tid); if (tid == 0) if (tid == 0) { nthreads = omp_get_num_threads();{ nthreads = omp_get_num_threads();printf("Number of threads = %d\n", nthreads); printf("Number of threads = %d\n", nthreads); } } }} } }
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Distributed MemoryDistributed Memory EinfürungEinfürung Aufteilung einer Aufge. Aufteilung einer Aufge. (parallelisierung Ansatz)(parallelisierung Ansatz) MPI + PVM MPI + PVM ((SMPDSMPD Programmiermodel) Programmiermodel) MPI programmier beispiele:MPI programmier beispiele:
Bibiiothek initialisierenBibiiothek initialisieren Aufruf der MPI FunktionenAufruf der MPI Funktionen
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Distributed Memory Distributed Memory ArchitectureArchitecture
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
Memory 1
CPU 1
Rechner 1
Memory 2
CPU 2
Rechner 2…………..
weitereRechner
…………..
netzwerk Einzelrechnern mit jeweils eigenem Hauptspeicher mit einem Netzwerk für Kommunikation miteinander verbunden Relativ preiswerte Hardware (im vgl. zu SMP systemen) Gut skalierbar Gesamtarbeitspeicher fast beliebig gross- Kein direkter Zugriff auf die Gesamtdaten zeitaufwendige kommunication- Aufwendig beim programmieren, debugen- speziele bibliotheken notwendig
Distributed Memory Distributed Memory ArchitectureArchitecture
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
netzwerk
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
…………..weitere
Rechner …………..
Memory 1
CPU 1
Memory 23
CPU 23
• Programmierer ist für die Synchronisation und Kommunikation zwischen unterschiedlichen Prozessen zustaendich.• Es gibt aber Hilfsbibliotheken und Tools die, das Parralele Programieren für Distributed Memory Systemme erleichtern.
Distributed Memory Distributed Memory ArchitectureArchitecture
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
PVM – Parallel Virtual Machine Ist ein Programmpaket, das es erlaubt, ein Netzwerk von heterogenen Rechnern als einen virtuellen parallelen Rechner zu benutzen.
- Es ist eine einheitliche, portable Programmierbibliothek die es Programmen erlaubt Nachrichten auszutauschen.
- Unterstuetzte sprachen sind C,C++,Fortran und (inofiziel) Java.
MPI – Message passing MPI – Message passing interfaceinterface
Distributed Memory Distributed Memory ArchitectureArchitecture
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
MPI – Message passing interfaceMPI – Message passing interface
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
•Das Programm ist in einer gewönliche Sprache geschrieben (C, C++, Fortran) • Beteiligte Prozesse benutzen nur lokalen Speicher• Datenaustausch zwischen den Prozessen erfolgt über Nachrichtenaustausch (Send/Recv)• Das gleiche Programm wird auf jeder Maschine ausgeführt
SPMD - Single Program Multiple Data
Memory 1
CPU 1
Memory 2
CPU 2
Memory 3
CPU 3
netzwerk
hello_mpi.c hello_mpi.c hello_mpi.c
Distributed Memory Distributed Memory ArchitectureArchitecture
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
#include "mpi.h"int main(int argc, char* argv[] ){ ... // System initialisiert MPI_Init(); // jeder Knoten hat eine eindeutige Nummer // MPI-Funktionen koennen benutzt werden .... MPI_Finalize(); // MPI wurde auf allen Knoten gestoppt}
MPI – Message passing interfaceMPI – Message passing interface
bash# mpicc hello_mpi.c –o hello_mpi
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Distributed Memory Distributed Memory ArchitectureArchitecture
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
#include "mpi.h"int main (int argc, char* argv[]) { // variblen declaration int myID; int numprocs; int myChromosome[1024][1024][1024]; // System initialisiert MPI_Init(); // MPI aufrufe MPI_Comm_rank ( MPI_COMM_WORLD, &myID ); MPI_Comm_size ( MPI_COMM_WORLD, &numprocs ); MPI_Finalize(); // MPI wurde auf allen Knoten gestoppt}
MPI – Message passing interfaceMPI – Message passing interface
bash# mpirun –np 23 hello_mpi
Distributed Memory Distributed Memory ArchitectureArchitecture
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
netzwerk
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
…………..weitere
Rechner …………..
Memory 1
myid=0;numprocs=23
CPU 1
Memory 1
myid=22;numprocs=23
CPU 1
Distributed Memory Distributed Memory ArchitectureArchitecture
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
Glossar 1Glossar 1
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
SISD (single instruction stream, single data stream )- Einen Prozessor und bearbeitet damit jeweils nur einen Befehl zur Zeit, erzeugt also auch nur einen Strom von Daten.
SIMD (single instruction stream, multiple data stream )- Mehrere Prozessoren führen jeweils denselben Befehl auf unterschiedlichen Daten aus
MIMD (multiple instruction stream, multiple data stream)- mehrere Prozessoren führen unterschiedliche Befehle auf unterschiedlichen Daten aus
SPMP (single program, multiple data )- wobei jeder Prozessor das selbe Programm auf unterschiedlichen Daten ausführt.- Datenaustausch zwischen den Prozessen erfolgt über Nachrichtenaustausch
SMP (Symmetric Multi Processing) - Arbeitet ein Rechner mit mehr als einem Prozessor, spricht man von einem Multiprozessor- oder Multiprocessing - System. Solche Systeme benutzen Shared Memory Speicher Model.
MPI (Message Passing Interface)PVM (Parralell virtual maschine )
- PVM und MPI sind Softwarebibliotheken, die erlauben Message Passing Parallel programme zu schreiben, die an eim Cluster ausgeführt werden. Das sind hilfsbibliotheken für DIe Cluster programmierung. Die unterstützen als Distributed Memory Model auch Shared Memory Modell.
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
Glossar 2Glossar 2
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
Thread- leichtgewichtiger Prozess. - erzeugen eines Threads ist schneller als erzeugen eines Process- Nebenläfige Threads von einem Prozess laufen im gleichen Adressraum.- Nebenläfige Prozesse laufen in unterschidlichen Adressräumen.
Shared Memory - alle Prozessoren arbeiten mit einem gemeintsammen Speicher - Speicher zugriffe müssen synchronisiert werden
Disributed Memory- Distributed Memory Systeme bestehen aus mehreren Einzelrechnern mit jeweils eigenem Hauptspeicher und Betriebssystem. - Jedes CPU kann nur auf eigene Speicher dierkt zugreifen- Zugriff auf Speicer eines anderen CPU erfolgt über das Netzwerk
Hybrid Memory (Shared Memory + Disributed Memory)- Shared Memory Systeme werden mit einem netzwerk zu einem Cluser verbunden
Cluster- In einem Cluster werden mehrere Rechner parallel zusammengeschaltet und arbeiten zusammen an der gleichen Arbeit. Das ist Disributed Memory System oder Hybrid Memory System.
SWE SS04. Paralleles Programmieren.SWE SS04. Paralleles Programmieren.
LiteraturLiteratur
Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej
SIMDhttp://www.zib.de/zibdoc/zib/mpp/prog/mpi/kurs/edv2-parallel-script.pshttp://www.unix-ag.uni-kl.de/~linux/linuxtag98/vortraege/smp/material.html
MPIhttp://parallel.fh-bielefeld.de/ti/studien/mpi/http://www.mpi-forum.org/docs/docs.htmlhttp://home.btconnect.com/Corebounce/bericht/html/node22.htmlhttp://www.lrz-muenchen.de/services/compute/linux-cluster/cpjava/mpijava.html
Genforschunghttp://www.ftd.de/tm/hs/1051316.html?nv=rshttp://www.3sat.de/nano/news/27353/http://www.bmbf.de/press/143.php
Glossarhttp://tech-www.informatik.uni-hamburg.de/applets/baukasten/DA/kap7_Glossar.html