Paralleles Rechnen 2011

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ötigt =MPI_Isend= einen weiteren Parameter?

c) Der durch die Kommunikation verursachte Overhead kann zu Leistungseinbußen bei einem MPI-Programm führen. Nennen und erläutern Sie zwei Techniken, um den Kommunikationsoverhead zu reduzieren! Werden dafür blockierende oder nicht-blockierende Kommunikationsprimitiven benötigt?

(1 + 2 + 3 Punkte)

Aufgabe 2: Leistungsanalyse

Gegeben sei das Programm Roadrunner. Es benötigt auf einem Einprozessorsystem eine Ausführungszeit von T(1)=200h. Dieses Programm wird auf ein

Cluster portiert. Es kann z.B. mit 2 oder 8 Prozessen abgearbeitet werden und benötigt hierfür T(2)=100h und T(8)=40h.

a) Berechnen Sie den Speedup S(2) und S(8).

b) Berechnen Sie für n=2 und für n=8 die Karp-Flatt-Metrik!

c) Berechnen Sie die Effizienz E(2) und E(8)!

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ür diese Anwendung sinnvoll?

e) Geben Sie zwei Gründe an, wieso parallele Anwendungen häufig keinen linearen Speedup besitzen! In seltenen Fällen wird super-linearer Speedup beobachtet. Was kann die Ursache für superlinearen Speedup sein?

(1 + 1 + 1 + 1 + 2 Punkte)

Aufgabe 3: OpenMP

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 übernimmt! Kennzeichnen Sie die Stellen im Diagramm, an denen sich eine Barriere befindet!

main() { 
  int i, a[[10000],][b[10000]]; 
  int its = 32;

  printf("Anzahl Prozessoren: %d\n", omp_get_num_procs());
  
  pragma omp parallel { 
    printf("Thread %i ist gestartet \n", omp_get_thread_num());
    pragma omp sections {
      pragma omp section for (int i=0; i<its; i++) a[i] = 0;
      pragma omp section for (int i=0; i<its; i++) b[i] = 100; }
      pragma omp for schedule(dynamic,4) for (int i=0; i<its; i++) calculate(i);
  } 
}

(4 Punkte)

Aufgabe 4: Network-on-Chip

Entwerfen Sie ein Network-on-Chip für einen Prozessor mit 64 Kernen!

a) Verwenden Sie ein zweidimensionales Gitter!

b) Verwenden Sie eine n-Cube-Topologie.

c) Vergleichen Sie Ihre Lösung anhand von Grad und Durchmesser!

(4 Punkte)

Aufgabe 5: Clusterkommunikation

a) Was versteht man unter expected bzw. unexpected Messages?

b) Für welchen dieser Nachrichtentypen ist Zero-Copy einfach zu realisieren?

c) Was versteht man unter RDMA? Muss ein Netzwerk RDMA-fähig sein, um Zero-Copy zu ermöglichen? Begründen Sie Ihre Antwort!

d) Auf dem Zuse-Cluster wird ein InfiniBand-Netzwerk für die High-Performance-Kommunikation genutzt. Dabei wird die MPI-Implementation MVAPICH der Ohio State University genutzt. Wieso benutzt MVAPICH nicht den TCP/IP-Stack?

(1 + 1 + 2 + 1 Punkte)

Aufgabe 6: Cluster-Management

a) Zur Verwaltung des Zuse-Cluster wird das Ressourcenmanagementsystem Torque/Maui eingesezt. Wie können die folgenden Benutzer-Policies umgesetzt werden? Welche Queues mit welchen Prioritäten richten Sie ein?

(1) Teilnehmer der PR-Kurses sollen Jobs maximal der Länge 3h auf Zuse rechnen dürfen. Der Benutzer Garfield will 1000 Jobs rechnen, die jeweils 2 Cores benötigen und ca. 2-4h laufen. Falls ein PR-Teilnehmer einen Job submitted, soll dieser Job höhere Priorität haben als alle wartenden Jobs von Garfield.

(2) Jeden Montag zwischen 8:00-10:00h soll das Cluster frei für System-Updates sein.

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?

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.

(3 + 1 + 2 Punkte)