33
Software Engineering Software Engineering SS04 SS04 Paralleles Paralleles Programmieren Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

Embed Size (px)

Citation preview

Page 1: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

Software Engineering Software Engineering SS04SS04

Paralleles Paralleles ProgrammierenProgrammieren

FH Aachen, 20.04.2004

Prof. Dr.-Ing. Michael Trautwein

Andrej Kühnal, Perez-Otuno Rodrigo

Page 2: Software Engineering SS04 Paralleles Programmieren 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

Page 3: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Z.B. -Wetter vorhersage.---Passwort knaken.
andrej.kuehnal
z.B. - 20 Gb sortieren- Genforschung
Page 4: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
bei SIMD Konzept (single instruktion stream, multiple data stream) fueren alle beteiligte Prozessoren jewels GLEICHEN Befehl jedoch auf verschiedenen Datetnsätzen.
andrej.kuehnal
Allgemeinste Fall ist MIMD Konzept (multiplete instruktion stream, multiple data stream) jeder Prozessor führt eigenen Code auf eigenen Daten aus
andrej.kuehnal
(single program, multiple data) Jeder Prozessor führt das selbe Programm aus. Dabei kann aber jeder Prozessor einen differenten Kontrollfluß durch das Programm ablaufen.
andrej.kuehnal
Es gibt aber mehrere Ansätze für Parallesieren.Wichtigste sind SIMD MIMD und SPMD.
andrej.kuehnal
Im allgemeinen versteht man unter parallelen Programmieren die gleichzeitiges Ausführung der Befehelen auf unterschiedlichen Datensätzen.
Page 5: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
andrej.kuehnal
PVM and MPI are software systems that allow you to write message-passing parallel programs that run on a cluster, in Fortran, C and C++.
Page 6: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

…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

andrej.kuehnal
Implementation ist trivial:Zuerst alloziere ich die Speicher für Vektoren x,y und z. Danach werden die Vektoren x und y irgend wie belegt.Jetzt kommt eine Schleife über die Vektoren.In jedem Schleifenschritt wird eine Integer addition ausgefüchrt.
andrej.kuehnal
Am Anfang landet das erstes Datensatzpaar aus der Arbeitspeicher in ein ALU und werird da addiert. Danach werden die Ergebnisse zurück in die Arbetspeicher geschrieben. Danach ubergehen wir zum nachsten Datensatzpaar.Anschliesend werden die ergebinisse zurück in Arbeitspeicher geschrieben.
andrej.kuehnal
Hier habe ich Integer vektoren X,Y und Z dargestellt.x und y sind vorbelegt.Im vector z wird Ergebnis der Addition von x und y gespeichert.zuerst zeige ich wie die Serielle addition abläuft
andrej.kuehnal
An der Stelle glabe ich gibt es keine Fragen. Oder? Dann Fangen wir an mit parralellen Addition
Page 7: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Aus der Arbetspeicher landen die Daten in parraleles ALU und da werden die vierer Tupel addiert.parraleles ALU habe ich mit gestriecheltem rechteck Markiert. Parraleles ALU addiert die vierer Tuppel meistens genau so schnell wie die serielle ALU aus vorherige Folie.
andrej.kuehnal
Zuerst alloziere X4 - ich ein Feld von vierer tupples .Danach kommen Y4 und Z4.Im Feld Z4 wird Ergebniss abgespeichert.
andrej.kuehnal
Um parralalle Addition zu implementieren braucht man einen neuen Daten typ für einen vierer Tupel.So ein Datentyp ist z.B. I32vec4.Das ist ein Vierertupel von Integers.
andrej.kuehnal
notvendige include datei ist dvec.h wird zusammen mit dem Prozessor pack für MS Visual studion von Microsoft geliefert.
andrej.kuehnal
Danach ertelle ich eine Schleife über alle Feldelemente.Pro Scleifenschritt werden 4 Zachlenpaaren addiert, deshalb machen wir 4mall so wenig schtitten im Vergleich zu serielle Addition.An der stelle will ich mit SIMD befehlen unterbrechen, denn es gib noch so viele anderen interessanten Ansätzen.
andrej.kuehnal
Gibt es Fragen?Dann frage ich. Was meinen sie über die Vorgefürten Beispiellen. Leuft zweites programm 4mall so schnel wie erstes? N ist sehr gross. Oder Nicht? (Wer ist dagegen?) Begründung dafür ist das Speicher Transfer. die daten mussen zuerst aus RAM ins CPU transferiert werden, und erst danach werden die addiert. Speicher transfer erfolg unabchänig von der Addition und kostet bei Seriele addition genou so viel Zeit wie bei paralelle addition.
Page 8: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 9: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 10: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 11: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 12: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 13: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

Shared MemoryShared Memory

Open MPOpen MP

Thread++Thread++

Java ThreadsJava Threads

Perez-Otuno RodrigoPerez-Otuno RodrigoKühnal AndrejKühnal Andrej

Page 14: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 15: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 16: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 17: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 18: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 19: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 20: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 21: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 22: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 23: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 24: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Distributed Memory Systeme bestehen aus mehreren Einzelrechnern mit jeweils eigenem Hauptspeicher und Betriebssystem. Jedes CPU kann nur auf eigene Speicherdierkt zugraeifen.
andrej.kuehnal
Einzelrechnern sind mit einem Netzwerk zur Kommunikation miteinander verbunden.
Page 25: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Ein Beispiel:Wir untersuchen menschliches Genom um Genkrankheiten zu erkennen unddie Entwicklung von zielgenau wirkenden Medikamenten zu ermoelichen.
andrej.kuehnal
Stellen sie mall vor dass menschliches Chromosomsatz auf 23 Rechner verteilt ist. CPU 1 untersucht ziemlich lange das 1. Chromosom, CPU 2 untersucht das 2. Chromosom usw.
andrej.kuehnal
Auf einmall braucht CPU 1 die erste 14 Genender 23. Chromosom fuer die weitere Arbeit.So muss die CPU 23 die Notwendige Daten zum richtigen Zeitpunkt zu CPU 1 senden.Werden die daten zu spaet versendet so bleibt CPU 1 eine weile arbeitslos.
Page 26: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Die weit verbreitesten bliotheken sind MPI und PVM.
andrej.kuehnal
- MPI steht fuer message pasing interface.Es ist eine einheitliche, portable Programmierbibliothek die es Programmen erlaubt Nachrichten auszutauschen. Unterstuetzte sprachen sind C,C++,Fortran und (inofiziel)java.
andrej.kuehnal
PVM steht fuer parallel virual maschineIst ein Programmpaket, das es erlaubt, ein Netzwerk von heterogenen Rechnern als einenvirtuellen parallelen Rechner zu benutzen.
andrej.kuehnal
Beide Bibliothetken sind gut und weit verbreitet.Ich zeige einige MPI Konzepte und Grudaufbau eines MPI Programms
Page 27: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Fur Distributed Memory Systeme wird SMPD Programmier-Modell verwendet.SMPD stecht fuer Single Program Multiple DataDer Programmierer schreibt ein Programm z.B. "hello_mpi". Das Programm wird auf jedem Knoten gestartet.Die Eingangs Dateten werden zuerst in kleinere Teilaufgaben geteilt und zwischen Knoten verteilt.Jeder Knoten führt die Berechnungen aus.Waered der Berechnungsfase dürfen Knotenmit Einander Kommunizieren um mit Zwischenergebnissen abzutauschenAnschilessend werden die Teiergebnisse zu einemGesamtergebniss zusammengefuert.Das ist die Grundidee des SPMD Konzeptes.Single Programm Multiplete Data.Nicht verwechseln mit SIMD!!!(Wer weiss noch was heist SIMD?)
Page 28: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Ein MPI-Programm wird immer nach folgendem Schema aufgebaut:
andrej.kuehnal
Zuerst wird MPI biliothek inizialisiert.Dabei wird jedem Knoten eine eindeutige Nummer.Knoten sind durchgehend mit 0 angefannen Nummeriert.Ab diese Zeile koennen die MPI-Funktionen benutzt werden
andrej.kuehnal
MPI bibliotheck wird heruntergefahren.Speicher wird freigegeben, geoffnete sockets werden geschlossen. Nach Finalyze sind keine weiteren MPI aufrufe erlaubt.
andrej.kuehnal
Alle MPI funktionen beginnen mitMPI_unterschtriechKompliliern mit angepasste compiler version:mpicccompiler otions sind wie gewoenlich
Page 29: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

andrej.kuehnal
Letztes Beispiel:Wir erweitern unseres Programm.Alles was neu gekommen ist, ist Fett gedückt.Zuerst deklarieren wir 3 variablen.Nach der Initialisation commen zwei MPI Aufruffe.MPI_Comm_rank()MPI_Comm_size()
andrej.kuehnal
anschliessend starten wir unseres Programm auf 23 Knoten.mpirun übernimt das verteilen eines Programm auf alle verfügbare Knoten. Mit -np Option kann mann Anzal der Beteiligten Prozessen festlegen. (Errinern sie noch an SPMD-Programmier model?)SPMD stecht für Single programm multiplete data.
andrej.kuehnal
MPI Biliothek wird inizialisiert.Dabei wird jedem Knoten eine eindeutige Nummer.Knoten sind durchgehend mit 0 angefannen Nummeriert.MPI-Funktionen koennen benutzt werden
andrej.kuehnal
Funcktion MPI_Comm_rank() wird auf jedem Knoten aus gefürt und liefert eindeutiges Knotennummer zurück.Function MPI_Comm_size() ermitelt Die Anzahl der beteiligten KnotenDabei MPI_COMM_WORLD ist ein Konstante deffiniert im MPIBibliothek und letztes Argument der Funktionen ist ein Ausgabeparameter. Da wird Ergebniss abgespeichert
Page 30: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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

Page 31: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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.

Page 32: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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.

Page 33: Software Engineering SS04 Paralleles Programmieren FH Aachen, 20.04.2004 Prof. Dr.-Ing. Michael Trautwein Andrej Kühnal, Perez-Otuno Rodrigo

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