Unified Parallel C (UPC) ist eine Spracherweiterung zur Programmiersprache C (C99) für Programme im Hochleistungrechnen auf Massivparallelrechnern. UPC-Programme können sowohl auf SMP- und NUMA-Architekturen mit einem globalen Adressraum als auch auf Clustern, auf denen ein Querzugriff nur über ein Datennetz erfolgt, ablaufen.
Bei Parallelrechnern laufen auf den einzelnen Rechnern (auch Prozessoren oder Cores) getrennte Programme gleichzeitig ab. Im allgemeinen werden solche getrennten Programme Prozesse genannt. In UPC heißen sie Threads.
In der Sprache UPC wird das PGAS-Speichermodell verwendet, das allen Rechnern erlaubt, auf einen gemeinsamen Speicher (GAS - global adress space) zuzugreifen. Dieser Speicher ist jedoch unterteilt, so dass jeder Rechner priviligierten Zugriff auf den ihm selbst zugeordneten Speicherbereich hat (PGAS - partitioned global adress space).
Dieses Speichermodell des Programms muss nicht in der ausführenden Hardware vorhanden sein, es kann simuliert werden. Sind die Prozessoren über ein Message Passing Netz verbunden, kann der Zugriff auf andere Speicherbereiche über dieses Netz erfolgen (GASNET - Global address space networking).
Entscheidend ist, dass jede Einzelvariable eindeutig einem Prozessor zugeordnet ist und notfalls von dem Prozessor bezogen werden muss.
UPC-Programme sind SPMD-Programme, bei denen erstens zu Programmbeginn die Anzahl der Prozessoren festgelegt ist, bei denen zweitens jeder Prozessor dasselbe Programm abarbeitet (SP - single process) und drittens nur die Datenobjekte der Prozesse verschieden sind (MD - multiple data). Natürlich können die verschiedenen Kopien des Programms, gesteuert über if-Anweisungen, verschiedene Tätigkeiten durchführen. Das ändert nichts daran, dass auf allen Prozessoren dasselbe Programm läuft.
Der Sprache UPC liegt C (C99) zugrunde. Ideen wurden auch aus anderen Sprachen aufgegriffen: AC, Split-C, PCP (Parallel C Preprocessor).
| http://upc.gwu.edu/ | George Washington University |
| http://www.gwu.edu/~upc/publications/LBNL-59208.pdf | UPC Language Specifications V 1.2 |
| http://upc.gwu.edu/downloads/Manual-1.2.pdf | UPC Manual, Draft 1.2 |
| http://upc.lbl.gov/ | Lawrence Berkeley National Lab |
| http://www.hcs.ufl.edu/upc/ | University of Florida |
| http://www.upc.mtu.edu/ | MUPC - Michigan Technological University |
| http://www.gccupc.org/ | gcc-upc - Intrepid Technology, Inc. |
| http://h30097.www3.hp.com/upc/ | HP upc - Hewlett Packard |
| http://upc.lbl.gov/ | University of California, Berkeley |
| http://docs.cray.com/ | Cray Compiling environment (Browse/Books/C, Cray C and C++ Reference Manual |
| http://www.alphaworks.ibm.com/tech/upccompiler | IBM XL UPC Compilers |
| https://upc-wiki.lbl.gov/index.php/Main_Page |
Im von UPC verwendeten PGAS-Modell ist der gesamte Speicher in einen gemeinsam genutzten sog. shared Speicher und in einen privaten Teil aufgeteilt. Beide Speicherteile gehören jeweils zu einem Thread. Jeder Thread hat exklusiven Zugriff auf seinen privaten Speicher und nicht exklusiven Zugriff auf seinen shared Speicher. Weiter kann er nach Belieben den shared Speicher anderer Threads benutzen. Im allgemeinen sollte man davon ausgehen, dass der Zugriff auf shared Speicher anderer Threads langsamer ist und zusätzliche Koordinierung sowohl durch den Programmierer als auch durch den zugrundeliegenden Compiler oder das System benötigt.
In UPC wird das oben beschriebene PGAS-Speichermodell verwendet. Die Prozesse heißen Threads. Die Anzahl der Threads steht spätestens bei Programmstart fest und kann vom Programmierer als Wert THREADS verwendet werden. Die einzelnen Threads sind, beginnend mit 0, durchnumeriert. Jeder Thread kennt seine eigene Nummer als Wert MYTHREAD.
Trotz der großen Unterschiede in den Konzepten und in der praktischen Programmierung zwischen UPC und MPI sind die Paralleltechniken in weiten Bereichen sehr ähnlich. MPI ist jedoch ein weitgehend ausgereiftes System, das kaum noch Wünsche offen läßt; UPC bietet dagegen nur für eine Teilmenge von MPI Alternativen an. So fehlen etwa UPC-Äquivalente zu den Kommunikatoren, Prozesstopologien oder zum Prozessmanagement.
Die Beziehung von UPC zu OpenMP ist noch enger: OpenMP verwendet von Haus aus einen gemeinsamen Speicher (GAS-Modell), auf den die verschiedenen Threads Zugriff haben.
Die Ähnlichkeiten werden in der Tabelle 4 auf Seite pageref aufgeführt.
| UPC | MPI | OpenMP | |
| Thread | Process | Thread | |
| THREADS | MPI_COMM_SIZE | ||
| MYTHREAD | MPI_COMM_RANK | ||
| Kollektive Kommunikation | upc_all_broadcast | MPI_BCAST | |
| upc_all_scatter | MPI_SCATTER(V) | ||
| upc_all_gather | MPI_GATHER(V) | ||
| upc_all_gather_all | MPI_ALLGATHER(V) | ||
| upc_all_exchange | |||
| upc_all_permute | |||
| Kritische Regionen | lock | unnötig | critical |
| Kollektive Reduktionen | upc_all_reduce | MPI_REDUCE | |
| upc_all_prefix_reduce | MPI_(ALL)REDUCE | ||
| Einseitige Kommunikation | upc_memcpy | ||
| upc_memget | MPI_GET | ||
| upc_memput | MPI_PUT | ||
| upc_memset |
In UPC bezeichnet das Wort private als Gegensatz zu shared eine Variable im lokalen Speicher eines Threads und nicht wie in C++ oder Java als Gegensatz zu protected und public ein Zugriffsrecht.
In UPC bezeichnet das Wort Objekt wie in C ein Speicherobjekt, also eine Variable oder eine Funktion und nicht wie in C++ oder Java eine Instanz einer Klasse mit Feldern und Methoden.
siehe 5 auf Seite pageref
| 1993 | Parallel Programming in Split-C. Erste Sprache nach dem PGAS Programmiermodell |
| 1998 | Co-array Fortran von Numrich und Reid liefert die Grundidee zu UPC |
| 5'1999 | Technical report von William Carlson, Jesse Draper, David Culler, Katherine Yelick, Eugene Brooks. (auch UPC 0.9) |
| und Karen Warren (Introduction to UPC and Language Specification) | |
| 5'2000 | UPC Consortium Bowie Maryland |
| 2'2001 | UPC 1.0 von Tarek El-Ghazawi, William Carlson und Jesse Draper et al (UPC Workshop) |
| 10'2003 | UPC 1.1 Dan Bonachea et al |
| 12'2003 | Collective operations, Seidel Greenberg Wiebel |
| 7'2004 | I/O specification, Ghazawi Cantonnet Saha Thakur Ross Bonachea |
| 9'2004 | UPC 1.1.1 I/O specification, Ghazawi Cantonnet Saha Thakur Ross Bonachea |
| 5'2005 | UPC 1.2 (Collective specifications speziell I/O) |
| 2008 | bupc 2.8; gccupc 4.0.3.5 |
| 2009 | bupc 2.10.0; gccupc 4.3.2.5 |
| 2010 | bupc 2.12.0, 2.11.4, 2.10.2; gccupc 4.5.1.2 |
| 8'2010 | GWU Unified Testing Suite(GUTS) (http://upc.gwu.edu/download.html) |
| 5'2011 | bupc 2.12.2 |
| 10'2011 | bupc 2.13.6 (2.14.0) |
| 30.10.2012 | bupc 2.16.0 |
| 2012 | gccupc 4.8.03 |
| 30.4.2013 | bupc 2.16.2 |
Tarek El-Ghazawi, Carlson, Sterling, Yelick: UPC, Distributed Shared Memory Programming, 2005, 0-471-22048-5
Weitere Literaturangaben finden Sie auf meiner Webseite mit Literatur zum Parallelrechnen:
Compilerübersicht:
| Name | Organisation | Compiler | Start | Version |
| Berkeley UPC | University of California, Berkeley | upcc | upcrun | 2.12.0, 11'2010 |
| gcc UPC | intrepid | upc | ./a.out | 4.5.1.2, 10'2010 |
| MuPC | Michigan Technological University | upc | 1.1.2 β | |
| HP UPC | Hewlett Packard | upc | prun | 3.3 |
| CCE | Cray Compiling Environment | cc | aprun | 7.2, 2'2010 |
| xlupc | IBM XL UPC Compilers | xlupc | export UPC_NTHREADS=4; poe |
Windows ohne Cygwin: Datei Cygwin-1.7.9-BerkeleyUPC-2.16.0.tar.gz aus dem Web holen (braucht Bandbreite, Zeit und Geduld). Dekomprimieren (gzip -d ...). Auspacken (tar -xf ...). Das Installationsprogramm c:\Cygwin-1.7.9-BerkeleyUPC-2.16.0\setup.exe starten. Danach ist Cygwin mit upcc unter Windows installiert. Diese Installation ist auch in den CIP-Pools verfügbar (cmd.exe starten und F:\BAT\cygwin-upc.cmd eingeben).
Windows mit vorhandenem Cygwin: Im Cygwin-setup die Programme ash, binutils, gawk, gcc4, gcc4-core, grep, gzip, make, perl, tar installieren. Datei berkeley_upc-2.16.0.tar.gz aus dem Web holen. Dekomprimieren und in Cygwin auspacken. In Cygwin ./Bootstrap, ./configure CC=gcc-4 CXX=g++-4, make und make install eingeben.
Linux: Datei berkeley_upc-2.16.0.tar.gz aus dem Web holen. Dekomprimieren und auspacken. ./Bootstrap, ./configure CC=gcc CXX=g++, make und make install eingeben.
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/upc.txt)
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/upcc.txt)
| http://www.intrepid.com/upc/ | alte Homepage |
| http://www.gccupc.org/ | neue Homepage |
| http://www.gccupc.org/gcc-upc-configuration.html?start=1 | Installation |
| http://www.gccupc.org/gcc-upc-downloads.html | Download |
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/gccupc.txt)
Suse Sles 11 rrzvm034: gmp, mpfr und mpc zu alt und nicht in den packages.
Debian hat zunächst ebenfalls wegen mpfr/mpc Schwierigkeiten gemacht.
Das folgende Rezept hat auf beiden Systemen funktioniert. Dabei war das Kommando 1008 entscheidend, das aktuelle Versionen benötigter Pakete läd und mit installiert:
1005 time tar -xf upc-4.8.0.3.src.tar 1006 cd upc-4.8.0.3/ 1007 ls 1008 ./contrib/download_prerequisites 1010 cd .. 1012 mkdir objdir 1013 cd objdir 1015 time ../upc-4.8.0.3/configure --prefix=/usr/local/ --enable-languages=c,upc --disable-bootstrap 1017 time make 1019 su make install 1020 time make install 1021 su 1022 history > x.xDie folgenden Installationszeiten wurden auf rrzvm034 (Intel Xeon, X5450, 3.00GHz) gemessen:
rrzvm034 tar: real 0m19.088s user 0m0.316s sys 0m2.596sDie folgenden Installationszeiten wurden auf pc51315 (Intel Pentium 4, 1.80GHz) gemessen:configure: real 0m3.969s user 0m0.984s sys 0m0.612s
make: real 23m12.446s user 13m35.023s sys 4m15.508s
make install real 0m21.923s user 0m2.960s sys 0m2.460s
make real 66m22.167s user 52m59.395s sys 6m2.075s
Opensuse Laptop: installiert ist gmp-devel-4.2.3-10, mpfr-devel-2.3.2-3 und libmpc2-0.8.2.1. Verlangt werden von upc gmp 4.2+ (ok), mpfr 2.4.0 und mpc 0.8.0.
Pakete: gmp-devel, mpfr-devel, mpc-devel, libnuma-devel, glibc-devel-32bit.
Debian: libgmp-dev libmpfr-dev flex bison; Dann das Rezept (Achtung: eine Zeile sehr lang; nicht abschneiden!)
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/upc-inst-os-13.tex)
Der erste und zweite Installationsversuch verlief nicht erfolgreich.
Das obige Rezept zunächst auch nicht.
Schwierigkeiten: gmp/mpfr/mpc; 64 Bit Rechner libgmp-dev, libmpfr-dev (3.1.0-5), libmpc-dev (0.9-4) kommen in geeigneten Versionen. Zusätzlich wurden bison, flex und gfortran installiert. make vermisste eine Headerdatei (bits/predefs.h). Deshalb wurde gcc-4.7-source installiert.
./configure --prefix=/usr/local --enable-languages=c,c++,upc - Zeit: 1m45.244s
Abbruch mit:
... checking whether make sets $(MAKE)... yes checking if compiler cc1upc has been built... no checking if UPC driver 'gupc' has been built... no make[2]: Entering directory `/home/brf09510/upc-4.8.0.3/x86_64-unknown-linux-gnu/libgupc' make[2]: *** Keine Regel, um all zu erstellen. Schluss. make[2]: Leaving directory `/home/brf09510/upc-4.8.0.3/x86_64-unknown-linux-gnu/libgupc' make[1]: *** [all-target-libgupc] Fehler 2 make[1]: Leaving directory `/home/brf09510/upc-4.8.0.3' make: *** [all] Fehler 2real 84m17.412s user 75m47.844s sys 3m27.789s brf09510@pc101100643X:~/upc-4.8.0.3$
Installation erfolgreich am 29.5.2013; Installationshistory:
632 rm -fr upc-4.8.0.3 633 time tar -xf upc-4.8.0.3.src.tar 634 cd upc-4.8.0.3/ 635 time ./contrib/download_prerequisites 636 cd .. 637 mkdir objdir 638 cd objdir/ 639 time ../upc-4.8.0.3/configure --prefix=/usr/local/ --enable-languages=c,c++,upc --disable-bootstrap 640 time make 641 su 642 upc 643 history
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/upc-inst-db-video4.tex)
http://www.upc.mtu.edu/MuPCdistribution/
http://h21007.www2.hp.com/portal/site/dspp/menuitem.863c3e4cbcdc3f3515b49c108973a801/?ciid=c108e1c4dde02110e1c4dde02110275d6e10RCRD
upc x.upc
siehe http://docs.cray.com/books/S-2179-71//S-2179-71.pdf
Wie CAF in der CCE (Cray Compiling Environment) verfügbar. Beschreibung im Cray C and C++ Reference Manual.
cc -h upc -X 15 -o bps beispiel.c
http://www.cs.mtu.edu/~zlwang/papers/TR0802.pdf
Webseite mit Compiler-Dokumentation:
| http://upc.lbl.gov/docs/user/upcc.html | Manual Reference Pages - UPCC (1) |
| http://upc.lbl.gov/docs/user/upcrun.html | Manual Reference Pages - UPCRUN (1) |
bupc: cmd.exe starten; F:\BAT\cygwin-upc.cmd eingeben; upcc, upcrun
geht bei genügend Geduld.
Beispiellauf:
brf09510@pc55556 ~
| upcc -network=smp -pthreads -T 5 x.upc | Übersetzung für sequentielle Ausführung |
| upcc -network=mpi -pthreads -T 5 x.upc | Übersetzung für parallele Ausührung |
| upcc x.upc | Übersetzung für IB-Knoten |
| ./a.out | Sequentieller Start auf Athene1 |
| upcc x.upc | Übersetzung für parallele Ausführung (Optionen voreingestellt) |
| qsub pbsjob | Paralleler Start als PBS-Job |
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/pbsjob.txt)
bupc: upcc; mpiexec; qsub; qstat
PBS-Jobskript:
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/pbsjob.txt)
| upcc -pthreads qsort.upc (dynamic translation environment) |
| upcc -pthreads -T 4 qsort.upc (number of threads known by compiler) |
| upcrun -n 4 a.out (Start mit vier threads) |
Installiert auf VM074
| upcc -pthreads qsort.upc | dynamic translation environment |
| upcc -pthreads -T 4 qsort.upc | static te: number of threads known by compiler |
| upcrun -n 4 a.out | Start mit vier threads |
Installiert auf VM074
| upcc -pthreads qsort.upc | dynamic translation environment |
| upcc -pthreads -T 4 qsort.upc | static te: number of threads known by compiler |
| upcrun -n 4 a.out | Start mit vier threads |
Vorbereitung: Kommandofenster starten (cmd.exe); UPC-Cygwin starten F:\BAT>cygwin-upc.cmd);
UPC-Programme: siehe Linux (upcc -pthreads -T 4 x.upc; upcrun -n 4 ./x.exe)
Vorbereitung: Kommandofenster starten (cmd.exe); UPC-Cygwin starten F:\BAT>cygwin-upc.cmd);
UPC-Programme: siehe Linux (upcc -pthreads -T 4 x.upc; upcrun -n 4 ./x.exe)
| upcc -pthreads qsort.upc (dynamic translation environment) |
| upcc -pthreads -T 4 qsort.upc (number of threads known by compiler) |
| upcrun -n 4 a.out (Start mit vier threads) |
| http://upc.lbl.gov/docs/user/upcc.html | Manual Reference Pages - UPCC (1) |
| http://upc.lbl.gov/docs/user/upcrun.html | Manual Reference Pages - UPCRUN (1) |
| http://www.intrepid.com/upc/ | alte Homepage |
| http://www.gccupc.org/ | neue Homepage |
| http://www.gccupc.org/gcc-upc-configuration.html?start=1 | Installation |
| http://www.gccupc.org/gcc-upc-downloads.html | Download |
UPC wurde aus C abgeleitet. Dabei wurde der C-Standard C99 von 1999 (ISO/IEC 9899:1999) zugrundegelegt. Jedes C-Programm nach diesem Standard sollte auch als UPC-Programm übersetzbar sein. So sind anders als in C88 die schon aus C++ bekannten Zeilenendkommentare (//) erlaubt.
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/helloc.c)
Kurze Übersicht über die Neuerungen in C99 (teils mit den Originalbezeichnungen):
Eine (englische) Kurzeinführung für C99:
Ein Hello World in echtem UPC benötigt natürlich etwas mehr. Mit dem UPC-Compiler stehen auch die UPC-Sprachelemente bereit. In UPC heißen die Ausführungsstränge bei paralleler Ausführung Threads. Wie in C sind einige Leistungen in einer Bibliothek (upc.h) definiert. Dazu gehören die Informationen über die Anzahl der Threads (THREADS) und die individuelle Threadnummer (MYTHREAD).
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/hello.upc)
Es wird wie folgt übersetzt.
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/helloueb.txt)
Weitere in UPC definierte Werte stehen in der Tabelle.
| __UPC__ | 1 | für eine standardtreue Implementierung von UPC |
| __UPC_VERSION__ | 200505L | für Implementierung von UPC 1.2 |
| 200310L | für Implementierung von UPC 1.1.1 | |
| UPC_MAX_BLOCK_SIZE | maximaler Wert für Blocklayout eines shared Feldes | |
| __UPC_DYNAMIC_THREADS__ | 1 | wenn Anzahl der Threads erst zur Laufzeit festgelegt werden |
| __UPC_STATIC_THREADS__ | 1 | wenn Anzahl der Threads dem Compiler bekannt ist |
| THREADS | Anzahl der Threads | |
| MYTHREAD | Nummer des prozesseigenen Threads |
Zum Verständnis von UPC müssen allgemeine und UPC-eigene Begriffe aus der parallelen Programmierung bekannt sein. Dabei ist zwischen den Hardwaremodellen und den Programmiermodellen zu unterscheiden.
In Texten zur parallelen Programmierung werden oft verschiedene Begriffe für Prozessoren fast synonym verwendet, obwohl sie jeweils eigene Konnotationen haben.
Ein Prozessor ist eine eigene Ausführungseinheit, die unabhängig von anderen agieren kann. Speziell kann ein Prozessor ein eigener Datenprozessor (FPU) sein, der nur Arithmetik durchführt. Diese Form der Parallelisierung existiert in Vektorrechnern.
Verfügt ein Parallelrechner über mehrere unabhängige selbstständige CPUs, spricht man von Knoten. Die Kommunikation zwischen Knoten erfolgt meist durch ein Datennetz, manchmal auch über einen gemeinsam verfügbaren Speicher. In diesem Fall muss der Zugriff koordiniert werden und die Caches kohärent gehalten werden.
Bei mehreren vollständigen CPUs auf einem integrierten Schaltkreis spricht man von Cores oder Rechnerkernen. Mehrere Cores haben meist integrierte spezielle Kommunikationsmöglichkeiten.
Betont man mehr die abstrakte Programmierebene, dann nennt man die Prozessoren eher Threads oder Prozesse. Hier spielt die technische Realisierung der Kommunikation keine Rolle mehr.
Wenn aus dem Kontext klar ist, was genau gemeint ist, werden die Begriffe Prozessor, Prozess, Knoten, Core und Thread auch synonym verwendet.
In den Anfangszeiten der parallelen Programmierung wurde hauptsächlich die Klassifizierung von Parallelrechnern nach Flynn verwendet (SISD, SIMD, MISD, MIMD - single, multiple, instruction und data), die sich als zu grob herausgestellt hat. Deshalb wurden MIMD-Rechner weiter unterteilt in SMP, UMA, NUMA, ccNUMA und DMP.
Ein SISD ist ein klassischer sequentieller Rechner, der zu einem Zeitpunkt mit einem Befehl (single instruction) ein Datum (single data) bearbeitet.
Ein SIMD ist der klassische Vektorrechner, der zu einem Zeitpunkt mit einem Befehl mit mehr als einem Datenprozessor in jeweils eigenen Datenregistern mit verschiedenen Daten dieselbe Operation durchführt. So können z.B. Vektoren wesentlich schneller bearbeitet werden.
MISD sind eigentlich eine überflüssige Vervollständigung, aber man kann so fehlerredundante Architekturen bezeichnen, die mit denselben Daten dieselbe Berechnung mehrfach durchführen und das Ergebnis nur akzeptieren, wenn es überall gleich ist.
MIMD ist der klassische Parallelrechner, der zu jedem Zeitpunkt in eigenen Prozessoren jeweils andere Befehle mit verschiedenen Daten durchführt.
Ein SMP (symmetric multiprocessor - falsch ist shared memory processor, obwohl diese Bezeichnung ebenso korrekt wäre) ist ein Parallelrechner, der mehreren CPUs Zugriff auf gemeinsame Ressourcen, insbesondere gemeinsamen Speicher gestattet. Dieser Zugriff bildet meist einen Flaschenhals, der Vorteile nur bei relativ wenigen Prozessoren erwarten lässt.
Die UMA-Architektur löst diesen Flaschenhalt durch mehrere Zugänge zu gemeinsamen Ressourcen auf. Der Flaschenhals besteht jetzt nur noch, wenn mehrere Rechner auf dieselbe Speicherbank zugreifen. Probleme treten auf, wenn Daten in Caches liegen und gleichzeitig von anderen Prozessoren gebraucht werden.
Bei einer NUMA-Architektur hat jeder Rechner seinen eigenen Speicher, kann aber in jeden anderen Speicher zugreifen. Zugriffe in Fremdspeicher sind typischerweise langsamer.
Cache-Kohärenz wird in einer ccNUMA-Architektur erreicht.
Völlige Unabhängigkeit der einzelnen Prozessoren bietet ein DMP-Rechner (distributed memory processor). Hier sind die Resourcen der einzelnen CPUs vollständig getrennt und jede Kommunikation findet über ein Netz statt.
Heutige Architekturen sind meist Hybridarchitekturen. So ist ein Mehrkernchip in dieser Klassifikation ein SMP. Mehrere Mehrkernchips auf einem Motherboard haben gemeinsame Resourcen und bilden einen ((cc)N)UMA-Rechner. Schließlich werden viele solcher Motherboard zu einem Cluster zusammengebaut, der einen typischen DMP ergibt.
Der Programmierer braucht im Programm diese Architekturen nicht mehr zu unterscheiden. Jedoch fließt das Wissen um die verwendete Maschine häufig bewusst (gut) oder unbewusst (problematisch) in den produzierten Code ein, wenn ein Programm z.B. bestimmte Kommunikationen vermeidet, weil sie langsamer sind.
In der Programmierung versucht man die Vielfalt der Hardwaremodelle auf wenige abstrakte Softwaremodelle zu reduzieren. Meist unterscheidet man nur zwischen SPMD- und MPMD-Programmen.
SPMD (Single Program, Multiple Data): Ein einziges Programm läuft entweder in mehreren Kopien auf einem Rechner in mehreren Threads oder alternativ auf mehreren Rechnern parallel und kann mit verschiedenen Daten arbeiten. In dieser reinen Form kommt SPMD nicht in der Praxis vor. Die Threads können über bedingte Anweisungen sehr wohl leicht bis komplett verschiedene Tätigkeiten durchführen. Weiter können sie miteinander Daten austauschen.
Mit diesem Modell kann man also Rechenarbeit auf mehrere Rechner verteilen:
switch(MYTHREAD){case 0: T1; break; case 1: T2; break; case 2: T3; break; }
Das ist keine bedingte Anweisung im sequentiellen Sinn, wo maximal eine der Anweisungen ausgeführt wird; hier werden im Gegenteil alle Tätigkeiten durchgeführt, unter Umständen sogar gleichzeitig!
MPMD: Für jeden Prozessor wird ein eigenes Programm geschrieben; alle Programme können miteinander kooperieren. SPMD-Programme, die wie oben angedeutet zwischen den Prozessoren unterscheiden können, sind eigentlich schon MPMD-Programme, wenn man sich nicht auf den formalen Standpunkt stellt, dass auf allen Prozessoren dasselbe .exe-File läuft, wenn auch nicht überall mit denselben Anweisungen.
Hier unterscheidet man nur noch zwei Gruppen.
Auf der einen Seite steht das Message Passing Modell, bei dem der Parallelprogrammierer explizit formuliert, wann wie welche Daten mit wem ausgetauscht werden. Ob der Austausch über gemeinsamen Speicher oder im Netz erfolgt, bleibt in der Blackbox verborgen. Das Standardsystem ist MPI; ältere ist PVM.
Das zweite Modell PGAS (partitioned global address space) setzt einen realen oder virtuellen globalen Speicher voraus und wickelt alle Vorgänge mit diesem gemeinsamen Speicher ab. Sprachen sind UPC, coArray Fortran und Titanium.
In neueren Ansätzen wird versucht die Beschränkung der beiden Modelle zu durchbrechen. DARPA hat dazu 2003 ein Projekt ins Leben gerufen, das zu drei Entwürfen geführt hat. Es sind Chapel von Cray, X10 von IBM und Fortress von Sun.
Variable eines UPC-Programms sind privat. Jeder Thread hat seine eigenen Variablen mit Werten, die von den gleichnamigen Variablen der anderen Threads verschieden sein können.
Gemeinsame Variable aller Threads im shared Speicher werden mit dem Wort shared gekennzeichnet. Solche Variable müssen im C-Sinn statisch sein (entweder global oder mit dem Wort static gekennzeichnet). Das Schlüsselwort shared hat in UPC eine Stellung als qualifier wie in C die Schlüsselworte const, volatile und restrict.
Schon mit diesen Hilfsmitteln kann eine einfache Parallelisierung erreicht werden. Das folgende Programm rechnet Temperaturen von Celsius in Kelvin um. Dabei führt jeder Thread nur eine Umrechnung durch. Nur mit mehreren Threads erhält man mehr als eine Berechnung. Anders als bei einer klassischen Schleife kann der Programmierer hier nicht mehr die Reihenfolge der Ausgaben bestimmen.
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/kelvin.upc)
Ergebnis:
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/kelvin.res)
Ein UPC-Programm endet, wenn der letzte Thread mit exit (e);, mit return e; in main oder mit der schließenden } in main endet.
Ein UPC-Programm kann auch mit dem Aufruf von
upc_global_exit(e);
in einem der Threads beendet werden. Damit werden alle offenen Ein- und Ausgabevorgänge beendet, belegter Speicher aller Threads freigegegeben und alle beteiligten Threads beendet.
Manche Programmaktivitäten betreffen mehrere oder alle Threads gemeinsam, auch wenn sie nur von einem Thread durchgeführt werden. Sie heißen dann global. Lokale Tätigkeiten sind Aktivitäten, die nur einen einzigen Thread betreffen. Eine globale Tätigkeit kann von nur einem Thread durchgeführt werden und heißt dann nicht kollektiv. Sie kann auch gemeinsam von mehreren Threads gleichzeitig und in Zusammenarbeit durchgeführt werden und heißt dann kollektiv.
Dynamischer Speicher kann als shared Speicher von einem Thread alloziert werden (eine nicht kollektive Allokation). Er kann aber auch als shared Speicher in einer einzigen Variablen alloziert werden, die mehreren Threads gemeinsam gehört (eine kollektive Allokation).
upc_global_exit(e) ist eine globale, nicht kollektive Tätigkeit. Jeder Thread kann alleine das gesamte Programm beenden.
Die meisten Rechneruhren bez. ihre Programmierschnittstellen sind für Laufzeitmessungen von parallelen Programmen zu ungenau. MPI hat deshalb eine eigene Schnittstelle zur Messung von Rechenzeiten MPI_WTIME().
Eine solche Schnittstelle fehlt in UPC. Es wird <time.h> verwendet.
In bupc existiert eine Spracherweiterung zur Ermittlung der Rechenzeit:
Mit der Funktion clock() aus der C-Schnittstelle <time.h> wird die kumulierte Prozesslaufzeit gemessen. Die Laufzeiten mehrerer Cores werden also kumuliert erfasst. Das muss speziell bei der Threadkommunikation mit SMP beachtet werden.
Auch Linux hat eine Schnittstelle zur Laufzeitmessung <sys/times.h>. Mit der Funktion times(&t) kann die Rechenzeit mehrerer Cores kumuliert erfasst werden. Hier wird die Userzeit und die Systemzeit, sowie die Zeiten geforkter Childprozesse getrennt erfasst. Die Zeiten müssen in Sekunden umgerechnet werden. Dazu braucht man die Funktion sysconf (_SC_CLK_TCK) aus <unistd.h>.
struct tms tt;
Noch genauer kann die Rechenzeit mit dem Linux-Kommando time erfasst werden.
upcc -network=smp -pthreads=5 g.upc rzeit.c
athene1 brf09510/upcexamples> time upcrun -n 5 ./a.out
Im Beispiel hat das Programm auf 5 Cores 25,6 s im Usermode und 0.7 s im Systemmode verbraucht (kumulierte CPU-Zeit). Die Verweilzeit war 6,56 s. Das entspricht einer Auslastung der CPU (Singular) von (25.6 + 0.7) / 6.5 = 403 %, die ebenfalls angezeigt wird. Die maximale Auslastung bei 5 Cores könnte 500 % sein. Diese Differenz ist die Wartezeit des Programms.
embarrassing parallel pi
work distribution (siehe parallele Threads)
data distribution (siehe shared arrays/Datenverteilung)
domain decomposition (siehe nn)
Speicher unterteilt in shared und private
shared [], b=∞
shared [0], b=∞
shared, b=1
shared[1]
shared[b], b ≥ 0
shared[*]
Siehe UPC Manual S. 26, 3.5
#include<upc.h> size_t upc_threadof (shared void * p);
upc_threadof(p) liefert den Threadindex des Threads, dem der Speicherplatz der Variablen *p gehört. (siehe 7.2.3.1)
sehr einfach und flexibel
Bei der Übersetzung eines UPC-Programms ist der Compiler entweder im statischen oder im dynamischen Modus - offiziell als translation environment bezeichnet.
Im statischen Modus kennt der Compiler die Anzahl der späteren Threads, meist durch eine Option beim Compileraufruf wie -T 7 oder -fupc-threads-5. Im Programm kann dieser Modus mit der Präprozessorvariablen __UPC_STATIC_THREADS__ abgefragt werden. Der Compiler berücksichtigt diesen Modus bei der Verteilung der shared Feldvariablen auf die einzelnen Threads.
Im dynamischen Modus kennt der Compiler die Zahl der späteren Threads nicht. Sie wird erst beim Start des Programms festgelegt. Um Felder beim Start verteilen zu können, muss daher zwingend die Anzahl der Threads als Faktor in den Feldgrößen angegeben werden. Im Programm kann dieser Modus mit der Präprozessorvariablen __UPC_DYNAMIC_THREADS__ abgefragt werden.
| shared int x [10*THREADS]; | statisch und dynamisch erlaubt |
| shared [] int x [1000]; | statisch und dynamisch erlaubt |
| shared int x [10+THREADS]; | nur statisch erlaubt |
| shared [] int x [THREADS]; | nur statisch erlaubt; Compiler kennt Feldgröße in Thread 0 nicht! |
| shared int x [1000]; | nur statisch erlaubt |
| __UPC_DYNAMIC_THREADS__ | 1 | wenn Anzahl der Threads erst zur Laufzeit festgelegt werden |
| __UPC_STATIC_THREADS__ | 1 | wenn Anzahl der Threads dem Compiler bekannt ist |
Neben den aus C bekannten Schleifen gibt es in UPC zusätzlich eine kollektive Schleife. Sie hat syntaktische und semantische Ähnlichkeit zur for-Schleife.
upc_forall ( expr; expr; expr; aff) statem
Die Schleife ist kollektiv. Alle Threads sind gemeinsam und gleichzeitig an ihrer Ausführung beteiligt. Die Schleifensteuerung wird von allen Threads mit identischem Ergebnis ausgewertet. Bei jeder Iteration ist die Bedingung, die Affinität und der Schleifenrumpf ein gemeinsamer einzelner Wert. Alle Threads stimmen in der Gesamtzahl der Iterationen, ihrer Reihenfolge und darin, welcher Thread eine Iteration ausführt, überein.
Der vierte Schleifenparameter, die Affinität, entscheidet, welchen Thread für welchen Fall den Schleifenrumpf ausführt. Ist er leer oder hat er den Wert continue, ist die upc_forall-Schleife eine normale nicht-kollektive C-Schleife, die von jedem Thread unabhängig ausgeführt wird. Ist er eine ganze Zahl (integer) i, führt der Thread i % THREADS für diesen Wert von i den Schleifenrumpf aus. Alle anderen Threads haben für diesen Fall nichts zu tun. Ist er eine Adresse p im shared memory, so führt der Thread upc_threadof (p), dem diese Adresse gehört, für diesen Fall den Schleifenrumpf aus. Jede Iteration wird von genau einem Thread abgearbeitet.
Bei mehreren verschachtelten upc_forall-Schleifen werden alle inneren mit einer Affinität wie Schleifen mit continue als Affinität betrachtet. Nur die äußerste Schleife mit Affinität übernimmt die kollektive Kontrolle.
Im folgenden Beispiel wird fa() von allen Threads genau einmal aufgerufen. Jeder Thread führt fb() und fc() im Wechsel aus, fb() einmal öfter als fc(). Alle Threads gemeinsam führen fd() unsynchronisiert und insgesamt genau n-mal aus, jeder Thread die über die Affinität ihm zugeordneten. Alle Threads enthalten nach der Schleife in der Variablen i den Wert n.
upc_forall (i=fa(); (fb(), i<n); (fc(), i++); i)
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/forall.txt)
Im folgenden Beispiel ist die zweite Schleife mit j die eigentliche kollektive Schleife:
upc_forall (i=0; i < n; i++; continue)
Eine upc_forall-Schleife darf im Rumpf keine Seiteneffekte haben, die sich auf Iterationen anderer Threads auswirken. (Streng genommen darf sie es doch, aber es ist ein Programmierfehler und das Verhalten des Programmes ist dann, wie in C üblich, nicht definiert). Die folgende Schleife ist also ein Fehler:
upc_forall (i=alternate=0; i < n; i++; i)
Die Schleife in diesem Beispiel kann leicht durch eine korrekte Programmierung ohne Seiteneffekte ersetzt werden:
upc_forall (i=0; i < n; i++; i)
Sie ist sogar erlaubt, vorausgesetzt sie befindet sich nur nicht im Schleifenrumpf:
upc_forall (i=alternate=0; i < n; i++, alternate=!alternate; i)
Faustregel: Eine Iteration darf ausschließlich vom momentanen Wert der Variable i abhängen.
Leider ist nicht bei allen denkbaren Schleifen eine derart einfache Lösung möglich.
Sprünge, die die kollektive Schleife verlassen, sind ebenfalls nicht erlaubt. Das sind break, goto, return und longjmp. Die Anweisung continue im Schleifenrumpf ist erlaubt. Anders ausgedrückt müssen alle Threads die gemeinsam begonnene Schleife auch gemeinsam beenden. Selbstverständlich darf wie jede C-Schleife auch eine upc_forall-Schleife nicht mit goto betreten werden.
Barrieren
upc_barrier
split barriers
upc_wait upc_notify
Sperren
upc_lock upc_unlock
Datentransporte
fence
Auch shared Speicher kann in UPC mit Zeigern angesprochen werden. Die Zeigerdefinition folgt der Logik von C-Zeigern und den Regeln von const und volatile.
int * p; shared int * sp;
Der shared und der private Speicher sind logisch streng getrennt. Deshalb müssen auch Zeiger in den shared und den private Speicher unterschieden werden. Im Programm erfolgt dieser Unterschied natürlich mit dem Schlüsselwort shared. Es gibt prinzipiell vier Fälle und weitere ableitbare.
| int * p1; Zeiger im privaten Speicher auf Variable im privaten Speicher |
| shared int * p2; Zeiger im privaten Speicher auf Variable im shared Speicher |
| int shared * p3; ebenfalls Zeiger im privaten Speicher auf Variable im shared Speicher |
| int * shared p4; Zeiger im shared Speicher auf Variable im privaten Speicher |
| shared int * shared p5; Zeiger im shared Speicher auf Variable im shared Speicher |
| int shared * shared p6; ebenfalls Zeiger im shared Speicher auf Variable im shared Speicher |
| int shared * shared * p7; Zeiger im privaten Speicher auf Zeiger im shared Speicher auf Variable im shared Speicher |
p2 und p4 sind nur alternative Schreibweisen für dieselbe Definition. Das gilt auch für p5 und p6.
Die Variable p4 ist aus logischen Gründen sehr problematisch: sie steht im shared Speicher und kann von allen Threads benutzt werden. Da sie in den privaten Speicher eines Threads zeigt, darf sie jedoch nur von diesem einen Thread aus dereferenziert werden. Also kann jeder Thread p4 benutzen, darf aber auf keinen Fall *p4 verwenden, was natürlich in der Konsequenz dann sinnlos ist. Wenn man es trotzdem tut, zeigt der Speicher in den privaten Speicher der dereferenzierenden Threads an die analoge Adresse, wo sich natürlich keine Bezugsvariable befindet, also ins Nirwana. p4 ist nicht verboten, aber sinnlos und deshalb in der UPC-Spezifikation not recommended.
Adressen im shared Speicher müssen anders aufgebaut sein, als normale C-Adressen, da sie Informationen über den Thread und über die Blockung benötigen. Sie sind in drei Bitfelder aufgeteilt: den Thread, die Phase und die eigentliche Adresse. Bei vielen Compilern werden sie in 64-Bit-Variablen gespeichert.
struct{
Compiler sind natürlich frei, andere Definitionen vorzunehmen.
Der Thread enthält die Information über die Affinität der Adresse zu einem Thread. Das Adressfeld beschreibt im wesentlichen den Ort eines zusammenhängenden Datenblockes im Speicher des Threads. Die Phase ist die Position (offset) des Feldelements innerhalb dieses Datenblocks.
Die in C definierte Adressarithmetik funktioniert nach denselben Regeln auch in UPC. Kurz: Adressarithmetik ist nur mit Feldern erlaubt, solange die Adresse das Feld nicht verläßt. Sie referenziert mit Additionen und Subtraktionen benachbarte Feldelemente. Ist der Feldelementtyp void, darf der Speicher byteweise (eigentlich char-weise) referenziert werden.
Natürlich gelten Sonderregeln für shared Adressen, die am Beispiel am einfachsten klar werden: Wenn der Zeiger p in ein Feld v mit Blockgröße bs zeigt (shared [bs] int x[N], *p=&x[0];), entspricht die Anweisung p++ im wesentlichen die Gruppe:
p.Phase++;
sizeof unary-expression sizeof ( type-name ) upc localsizeof unary-expression upc localsizeof ( type-name )
Größe in Byte des lokalen Anteils eines shared Objektes.
upc blocksizeof unary-expression upc blocksizeof ( type-name )
Blockgröße in Byte eines shared Objektes. Identisch mit dem im Blocklayout spezifizierten Wertes.
upc elemsizeof unary-expression upc elemsizeof ( type-name )
Elementgröße in Byte eines shared Objektes.
Die Bitfelder einer UPC-Adresse können mit drei Funktionen ausgelesen werden und als ganze Zahlen weiterverarbeitet werden.
Die Worte const, volatile, restrict und shared sind sogenannte qualifier. Sie spezifizieren Annahmen, die der Compiler über die Verwendung der deklarierten Variablen im Deklarationsbereich macht. Bei einfachen Variablen bezieht sich qualifier natürlich auf die Variable selbst, ansonsten auf Feldelemente oder Bezugsvariable von Zeigern. Im folgenden wird shared exemplarisch verwendet; alles Gesagte gilt für jeden qualifier. Die Blockgröße eines shared [*] qualifier gehört zum qualifier und spzifiziert zusätzlich Compilerannahmen über die Verteilung von Feldelementen auf die Threads.
shared int i; // i ist im shared Speicher
Bei einer Zeigervariablen oder einem Feld ist immer die Bezugsvariable gemeint. Bei Feldern sind dies die Feldelemente.
shared int v [10], *p; // v [2] oder *p ist im shared Speicher
Wenn eine Zeigervariable selbst im shared Speicher liegen soll, steht der qualifier hinter dem Stern.
int * shared q; // q ist im shared Speicher
Natürlich können auch beide, Zeiger und Bezugsvariable, im shared Speicher liegen.
shared int * shared r; // r und *r sind beide im shared Speicher
In Zeigerketten kann jeder Stern mit einem nachfolgenden shared versehen werden.
int * shared * * shared * pk;
Faustregel: Ein shared am Anfang wirkt auf die letzte Bezugsvariable; jedes andere shared wirkt nach links auf Sterne. Man kann auch jedes shared auf die gesamte rechts von ihm stehende Sternenkette angewendet denken.
Da diese Schreibweise gewöhnungsbedürftig ist, darf wie in C++ der qualifier auch nach dem Typ stehen. Das ist konsistenter, denn jetzt wirkt der qualifier immer nach links:
int const * const * * const *pkcxx; // nur C++
Problematisch ist jedoch, dass beide Schreibweisen nebeneinander verwendet werden dürfen und dass die meisten Programmierer die klassische C-Schreibweise verwenden.
Der qualifier const verbietet dem Compiler jeden Schreibzugriff auf die Variable.
Der qualifier volatile verbietet dem Compiler jede Zugriffsoptimierung, die einen irgendwie gearteten Cache oder ein Register einbezieht. Mit diesem qualifier werden Optimierungen verboten.
Der qualifier restrict betrachtet einen Zeiger als fest zu seiner Bezugsvariablen gebunden. Kein anderer Zeiger kann mehr auf dieselbe Bezugesvariable zugreifen. Mit diesem qualifier werden weitere Optimierungen wie Cachezugriff ermöglicht.
Die folgende Tabelle 1 auf Seite pageref erläutert alle UPC-qualifier.
| qualifier | Annahmen des Compilers |
| const | Variable bleibt (zeitweilig) konstant (C88) |
| volatile | Variable ist unabhängig vom Programm veränderlich (C88) |
| Optimierungen durch den Compiler verboten | |
| restrict | Fest an seine Bezugsvariable gebundener Zeiger (C99) |
| shared | Variable im shared Speicher |
| shared [b] | Variable im shared Speicher; b Blöcke im selben Thread |
| shared [0] | Variable im shared Speicher; alle Blöcke in Thread 0 |
| shared [] | wie shared [0] |
| shared | wie shared [1] |
| shared [*] | Variable im shared Speicher; Blockgröße maximal, um alle Threads mit je einem Block zu füllen |
In C wirken qualifier nur auf Variable. Sie dürfen zwar in Typbeschreibungen stehen, wirken aber dann nur auf direkt vereinbarte Variable. Nachfolgende Variablendefinitionen erben den qualifier nicht. Im folgenden Beispiel ist die Variable v shared, die Variable v1 dagegen lokal.
shared struct t { int a; } v;
Bei drei Threads erscheint die Ausgabe:
t=0, v.a=2, v1.a=0
In UPC wird shared Speicher entweder global vereinbart. Er ist dann in Größe und Layout festgelegt.
Wie in C kann alternativ dynamischer shared Speicher bereitgestellt werden. Die Methode der Allozierung orientiert sich an den in <stdlib.h> deklarierten Allozierungsfunktionen wie malloc. Dynamischer Speicher ist flexibel sowohl was seine Größe, als auch was sein Layout betrifft.
Die in C vorhandenen Allozierungsfunktionen wie malloc. werden auch in UPC für dynamischen privaten Speicher verwendet.
Für dynamischen Speicher im shared Bereich gibt es zusätzliche UPC-Funktionen.
Liegt der dynamische Speicher vollständig im selben Thread, in dem auch der Aufruf erfolgt, wird er lokal genannt. Er wird mit upc_alloc alloziert. Die Funktion upc_local_alloc mit gleicher Leistung wie upc_alloc und ähnlicher Signatur wir upc_global_alloc ist deprecated und sollte nicht mehr verwendet werden.
Ein echter PGAS-Speicher in mehr als einem Thread heißt global. Er kann kollektiv mit upc_all_alloc alloziert werden. Dann erhalten alle Threads einen Zeiger auf einen gemeinsamen Speicherbereich. Er kann auch nichtkollektiv mit upc_global_alloc alloziert werden. Dann muss nicht jeder Thread a, Aufruf teilnehmen; jeder teilnehmende Thread erhält einen separaten Speicherbereich.
Das schließt natürlich nicht aus, dass der shared Speicher von mehr als einem Thread genutzt wird.
Es ist erlaubt, einen Bereich von 0 Bytes zu allozieren; der Zeiger auf den (nicht existierenden) Bereich ist dann 0.
Wie in C muss die Größe des allozierten Speicherbereichs in char-Einheiten (meist Bytes) angegeben werden. Wie in C ist der Zeiger auf den Speicherbereich nur gültig, wenn er ≠ 0 ist.
Aber Vorsicht: (void*) 0 ≠ (shared void *)0! Die Bit-Zahl ist verschieden. Bitte nicht mit NULL vergleichen!
Die Funktion upc_all_alloc alloziert kollektiv einen globalen Speicherbereich im shared Speicher. Alle Threads erhalten einen eigenen Zeiger auf diesen Speicherbereich.
Der allozierte Speicher entspricht der globalen Variablendefinition:
Die Funktion upc_global_alloc alloziert nichtkollektiv einen globalen Speicherbereich im shared Speicher. Als nichtkollektive Funktion müssen nicht alle Threads am Aufruf teilnehmen. Jeder aufrufende Thread erhält einen eigenen Zeiger auf einen zunächst eigenen Speicherbereich. Natürlich kann dieser Speicherbereich später auch von anderen Threads zugegriffen werden.
Der allozierte Speicher entspricht der globalen Variablendefinition:
Die Funktion upc_alloc alloziert nichtkollektiv einen lokalen Speicherbereich im shared Speicher. Als nichtkollektive Funktion müssen nicht alle Threads am Aufruf teilnehmen. Jeder aufrufende Thread erhält einen eigenen Zeiger auf einen Speicherbereich im threadeigenen Speicher. Natürlich kann dieser Speicherbereich später auch von anderen Threads zugegriffen werden.
Der allozierte Speicher entspricht der globalen Variablendefinition:
Die Funktion upc_local_alloc erbringt dieselbe Leistung wie upc_alloc und hat dieselbe Signatur wie upc_global_alloc. Sie ist veraltet und sollte nicht mehr verwendet werden, obwohl sie für ältere Programme noch existiert, kurz sie ist deprecated.
Für solche Speicherbereiche sorgt malloc aus <stdlib.h>.
broadcast, scatter, gather, exchange, permute
reduce, prefix_reduce
Es gibt vier Bibliotheks-Header in UPC:
| #include <upc.h> | alle elementaren UPC-Funktionen wie global_exit + relaxed |
| #include <upc_strict.h> | strict pragma + upc |
| #include <upc_relaxed.h> | relaxed pragma + upc |
| #include <upc_collective.h> | Alle kollektiven Funktionen wie broadcast |
Deklaration:
Der allozierte Speicher entspricht der globalen Variablendefinition:
Deklaration:
Der allozierte Speicher entspricht der globalen Variablendefinition:
Deklaration:
Der allozierte Speicher entspricht der globalen Variablendefinition:
Deklaration:
Deklaration:
Weitere Beispiele: Ising Spinmodelle, Bitonisches Sortieren
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/psrs.upc)
(http://www.uni-regensburg.de/EDV/kurs_info/brf09510/hpc/upc/gauspar.upc)
Code conventions, auch coding conventions oder coding standards sind Hilfen beim Programmieren, um Standardsituationen nicht zeitaufwendig jeweils neu überlegen zu müssen, sondern ohne Nachzudenken einheitlich in einem Programm umsetzen zu können.
Hier stehen Vorschläge für code conventions die ich speziell für parallele UPC-Programme als wichtig erachte.
Allgemeinere code conventions findet man unter:
http://www.gnu.org/prep/standards/
Die Überschrift wurde in Ermangelung eines besseren Wortes gewählt. Gemeint ist eine genauere Bestimmung, welche Threads an einer aufgerufenen Funktion beteiligt sind, in welchem Verhältnis die bearbeiteten Daten der verschiedenen Threads stehen oder unter welchen Bedingungen die Threads die Funktion parallel ausführen dürfen.
Beim Lesen eines UPC-Programms werden diese Merkmale aus dem Funktionsaufruf selbst nicht unmittelbar klar. Da sie trotzdem zu den wichtigsten Komponenten gehören, die zum Verständnis nötig sind, wie ein UPC-Programm funktioniert, müssen sie vom Programmierer explizit überlegt und durchdacht werden. Weiter sollten sie gut dokumentiert werden.
Schon in der UPC-Spezifikation wird dieser Unterschied teilweise hervorgehoben: Eine Funktion, die gemeinsam von allen Threads aufgerufen wird und einen gemeinsamen Datenbereich in shared Speicher bearbeitet, wird als kollektiv bezeichnet. Eine solche Funktion synchronisiert die Threads automatisch. Die kollektiven Funktionen werden im Namen mit dem Wort all gekennzeichnet. Leider gilt diese Kennzeichnung nicht für kollektive Anweisungen, wie upc_barrier.
In diesem Kapitel versuche ich, charakteristische solcher Fälle zu identifizieren.
Nur zum Kontrast zum Folgenden beginne ich mit dem Normalfall: Alle Threads eines Programms rufen dieselbe Funktion auf. Die bearbeiteten Datenbereiche sind vollkommen entkoppelt. Der genaue Zeitpunkt der Aufrufe spielt keine Rolle. Die einzelnen Threads müssen sich nicht synchronisieren. Wie lange sie für ihren Funktionsaufruf brauchen, hat nur Auswirkung auf die Rechenzeit, nicht auf die Ergebnisse.
Ein typisches Beispiel ist der erste Aufruf von qs im Beispielprogramm psrs.upc zur Durchführung der threadeigenen Sortierungen..
Programmphasen können inhärent sequentiell sein. Da ist der Fall, wenn kleine Mikroschritte schon von den unmittelbar vorhergehenden Schritten abhängen und auf deren Ergebnisse warten müssen (Beispiel: Fibonacci-Folge: F0=F1=1; Fi = Fi-2 + Fi-1). Das ist der Fall, wenn eine vorgegebene Reihenfolge wünschenswert ist, wie bei der Ausgabe von errechneten Matrizen auf dem Bildschirm. Hier sollen die Zahlen nicht in der Reihenfolge erscheinen, wie sie in den Threads gerade anfallen, sondern zeilen- und spaltenweise in ihren mathematische vorgegebenen Reihenfolge. Ähnliches gilt für Pixel in erzeugten Bildern. Ein drittes Beispiel sind externe Medien, die nur einmal real existieren und sequentiell bedient werden müssen, wie Drucker, Bildschirme und Dateien.
Prinzipiell kann eine solche Phase von einem Thread erledigt werden. Alle anderen Threads müssen möglicherweise warten.
Alternativ kann man die Ausführung der Threads sequentialisieren.
Die sequentielle Phase sei in der Funktion fseq () programmiert. Ich nehme an, dass der abarbeitende Thread immer Thread 0 ist.
upc_barrier; // wenn nicht anderweitig sichergestellt ist, dass fseq fertige Daten vorfindet
if (MYTHREAD == 0) fseq();
upc_barrier; // wenn die nachfolgenden Arbeiten von fseq abhängen
void fseq (void) { if (MYTHREAD != 0) return; // sequentielle Arbeit
}
Da beim Lesen eines Programms solche Funktionen nicht erkannt werden können, sollten sie im Namen gekennzeichnet werden. UPC schlägt bisher eine solche Kennzeichnung nicht vor. Man könnte Signalwörter wie thread0, zero, single oder singleThread im Funktionsnamen unterbringen. Im Beispiel wäre ein besserer Name fseqSingle ().
Eine Barriere in der Funktion könnte kontraproduktiv sein, wenn die anderen Threads in der Zwischenzeit sinnvolle unabhängige Arbeiten erledigen könnten.
void fseq (void) { upc_barrier; if (MYTHREAD == 0) { // sequentielle Arbeit
} upc_barrier; // alle müssen warten!
}
Ein typisches Beispiel ist der Ausdruck der Matrizen in gausspar.upc mit umxPrMat. Ein weiteres Beispiel ist die Sortierung der Pivotelemente mit dem zweiten Aufruf von qs im Programm psrs.upc.
Bei großen Datenmengen kann es ungünstig sein, wenn ein Thread sich zeitaufwendig Daten aus allen Threads holen muss. Dann kann man auch den Ablauf sequentialisieren.
void fseq (void) { int i; for (i = 0; i < THREADS; i++) { if (i == MYTHREAD) { // sequentielle Arbeit
} upc_barrier i; // alle ausser einem müssen warten!
} } }
Wenn an einer Tätigkeit alle Threads gemeinsam auf derselben Datenmenge arbeiten, auch wenn die Datenmenge im shared Speicher der Threads verteilt ist, spricht man von kollektiver Tätigkeit.
Auch bei Eigenentwicklung von kollektiven Funktionen sollte man die UPC-Konvention einhalten, solche Funktionen mit dem Signalwort all im Namen zu versehen.
Beispiel: umxAllCreateMatrix und umxAllDestroyMatrix im Programm gausspar.upc.
Bei der Entwicklung von Funktionen muss die Position der Barrieren genau überlegt werden. Da meistens nur beim Aufruf entschieden werden kann, ob alle Daten schon bereitstehen oder ob schnelle Threads auf langsamere warten müssen, ist die bessere Position von Barrieren vor dem Aufruf. Auch nach einem Funktionsaufruf hat man oft die Freiheit, schnelle Threads schon weiterlaufen zu lassen, wenn von der Funktion berechnete Daten nicht sofort benötigt werden.
In beiden Fällen wäre es ungünstig, Barrieren innerhalb der Funktion unterzubringen.
Faustregel: Barrieren im Zweifelsfall dem Aufrufer einer Funktion überlassen.
TTH-Seite: