{"id":336,"date":"2019-02-22T12:03:06","date_gmt":"2019-02-22T11:03:06","guid":{"rendered":"https:\/\/fsr.cs.uni-potsdam.de\/?p=336"},"modified":"2019-02-22T12:03:06","modified_gmt":"2019-02-22T11:03:06","slug":"paralleles-rechnen-2011","status":"publish","type":"post","link":"https:\/\/fsr.cs.uni-potsdam.de\/?p=336","title":{"rendered":"Paralleles Rechnen 2011"},"content":{"rendered":"

Aufgabe 1: MPI<\/h1>\n
\n

a) Was versteht man unter dem SPMD-Programmierprinzip (Single Program Multiple Data Parallelismus)?<\/p>\n

b) Beschreiben Sie die Semantik der MPI-Prozeduren =MPI_Send= und =MPI_Isend=! Wieso ben\u00f6tigt =MPI_Isend= einen weiteren Parameter?<\/p>\n

c) Der durch die Kommunikation verursachte Overhead kann zu Leistungseinbu\u00dfen bei einem MPI-Programm f\u00fchren. Nennen und erl\u00e4utern Sie zwei Techniken, um den Kommunikationsoverhead zu reduzieren! Werden daf\u00fcr blockierende oder nicht-blockierende Kommunikationsprimitiven ben\u00f6tigt?<\/p>\n

(1 + 2 + 3 Punkte)<\/p>\n<\/div>\n

Aufgabe 2: Leistungsanalyse<\/h1>\n
\n

Gegeben sei das Programm Roadrunner. Es ben\u00f6tigt auf einem Einprozessorsystem eine Ausf\u00fchrungszeit von T(1)=200h. Dieses Programm wird auf ein<\/p>\n

Cluster portiert. Es kann z.B. mit 2 oder 8 Prozessen abgearbeitet werden und ben\u00f6tigt hierf\u00fcr T(2)=100h und T(8)=40h.<\/p>\n

a) Berechnen Sie den Speedup S(2) und S(8).<\/p>\n

b) Berechnen Sie f\u00fcr n=2 und f\u00fcr n=8 die Karp-Flatt-Metrik!<\/p>\n

c) Berechnen Sie die Effizienz E(2) und E(8)!<\/p>\n

d) Wie beurteilen Sie die Parallelisierbarkeit des Programmes? Wie kommt die Anwendung auf dem Zuse-Cluster zurecht? Ist die Anschaffung einer Blue Gene mit 1024 Cores oder 4096 Cores f\u00fcr diese Anwendung sinnvoll?<\/p>\n

e) Geben Sie zwei Gr\u00fcnde an, wieso parallele Anwendungen h\u00e4ufig keinen linearen Speedup besitzen! In seltenen F\u00e4llen wird super-linearer Speedup beobachtet. Was kann die Ursache f\u00fcr superlinearen Speedup sein?<\/p>\n

(1 + 1 + 1 + 1 + 2 Punkte)<\/p>\n<\/div>\n

Aufgabe 3: OpenMP<\/h1>\n
\n

Das folgende OpenMP-Programm werde zur Laufzeit unter Verwendung von 4 Threads bearbeitet. Erstellen Sie ein Block-Diagramm, aus dem ersichtlich wird, welcher Thread welche Aufgaben \u00fcbernimmt! Kennzeichnen Sie die Stellen im Diagramm, an denen sich eine Barriere befindet!<\/p>\n

main() {\n  int i, a[[10000],][b[10000]];\n  int its = 32;\n\n  printf(\"Anzahl Prozessoren: %d\\n\", omp_get_num_procs());\n\n  pragma omp parallel {\n    printf(\"Thread %i ist gestartet \\n\", omp_get_thread_num());\n    pragma omp sections {\n      pragma omp section for (int i=0; i<its; i++) a[i] = 0;\n      pragma omp section for (int i=0; i<its; i++) b[i] = 100; }\n      pragma omp for schedule(dynamic,4) for (int i=0; i<its; i++) calculate(i);\n  }\n}<\/pre>\n
(4 Punkte)<\/p>\n<\/div>\n
Aufgabe 4: Network-on-Chip<\/h1>\n
\n
Entwerfen Sie ein Network-on-Chip f\u00fcr einen Prozessor mit 64 Kernen!<\/p>\n
a) Verwenden Sie ein zweidimensionales Gitter!<\/p>\n
b) Verwenden Sie eine n<\/em>-Cube-Topologie.<\/p>\n
c) Vergleichen Sie Ihre L\u00f6sung anhand von Grad und Durchmesser!<\/p>\n
(4 Punkte)<\/p>\n<\/div>\n
Aufgabe 5: Clusterkommunikation<\/h1>\n
\n
a) Was versteht man unter expected<\/em> bzw. unexpected Messages<\/em>?<\/p>\n
b) F\u00fcr welchen dieser Nachrichtentypen ist Zero-Copy einfach zu realisieren?<\/p>\n
c) Was versteht man unter RDMA? Muss ein Netzwerk RDMA-f\u00e4hig sein, um Zero-Copy zu erm\u00f6glichen? Begr\u00fcnden Sie Ihre Antwort!<\/p>\n
d) Auf dem Zuse-Cluster wird ein InfiniBand-Netzwerk f\u00fcr die High-Performance-Kommunikation genutzt. Dabei wird die MPI-Implementation MVAPICH der Ohio State University genutzt. Wieso benutzt MVAPICH nicht den TCP\/IP-Stack?<\/p>\n
(1 + 1 + 2 + 1 Punkte)<\/p>\n<\/div>\n
Aufgabe 6: Cluster-Management<\/h1>\n
\n
a) Zur Verwaltung des Zuse-Cluster wird das Ressourcenmanagementsystem Torque\/Maui eingesezt. Wie k\u00f6nnen die folgenden Benutzer-Policies umgesetzt werden? Welche Queues mit welchen Priorit\u00e4ten richten Sie ein?<\/p>\n
(1) Teilnehmer der PR-Kurses sollen Jobs maximal der L\u00e4nge 3h auf Zuse rechnen d\u00fcrfen. Der Benutzer Garfield will 1000 Jobs rechnen, die jeweils 2 Cores ben\u00f6tigen und ca. 2-4h laufen. Falls ein PR-Teilnehmer einen Job submitted, soll dieser Job h\u00f6here Priorit\u00e4t haben als alle wartenden Jobs von Garfield.<\/p>\n
(2) Jeden Montag zwischen 8:00-10:00h soll das Cluster frei f\u00fcr System-Updates sein.<\/p>\n
b) Wieso werden in Grid-Infrastrukturen wie dem D-Grid oder dem Tera-Grid neben dem Ressourcesmanagementsystem noch eine Komponente wie der Globus GRAM eingesetzt?<\/p>\n
c) Das Zuse-Cluster besitzt 28 Knoten mit je einem Dual Quadcore, d.h. 8 Cores pro Knoten. Beschreiben Sie ein Messexperiment, um die Bisektionsbandbreite des Zuse-Clusters zu bestimmen.<\/p>\n
(3 + 1 + 2 Punkte)<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Aufgabe 1: MPI a) Was versteht man unter dem SPMD-Programmierprinzip (Single Program Multiple Data Parallelismus)? b) Beschreiben Sie die Semantik der MPI-Prozeduren =MPI_Send= und =MPI_Isend=! Wieso ben\u00f6tigt =MPI_Isend= einen weiteren Parameter? c) Der durch die Kommunikation verursachte Overhead kann zu Leistungseinbu\u00dfen bei einem MPI-Programm f\u00fchren. Nennen und erl\u00e4utern Sie zwei Techniken, um den Kommunikationsoverhead zu weiterlesen…<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-336","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/posts\/336","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=336"}],"version-history":[{"count":0,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=\/wp\/v2\/posts\/336\/revisions"}],"wp:attachment":[{"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fsr.cs.uni-potsdam.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}