Thema: Cluster-Computing und Parallele Algorithmen (2006)

• Prüfer: Philippsen
• Beisitzer: Veldema
• Ergebnis: 1,0

• Philippsen hat die Fragen zu Cluster Computing gestellt, Veldema die zu Parallele Algorithmen
• Philippsen ist ein angenehmer Pruefer, fragt aber mitunter auch Details
• Veldema hat teilweise sehr seltsame Fragen gestellt, siehe unten.

• Welche Architektur haben nach Flynn Cluster? → MIMD
• Was heisst das? Was gibt es noch? → SIMD, z.B. Vektorrechner. Erfordern Spezialhardware, sind daher teuer.
• Wir wollen einen Cluster bauen. Wie vernetzen wir ihn? → Myrinet, Infiniband, Gigabit Ethernet, SCI
• Topologie von Infiniband? → Geswitches Netzwerk, man kann beliebige Topologien bauen.
• Malen Sie mal ein einfaches Beispielnetzwerk.
• Bandbreite und Latenz von Infiniband? → ca. 2 GBit/s pro Link, Buendelung moeglich bis ca. 40 GBit/s. Latenz: 2-3 Mikrosekunden.
• Wie misst man Latenz? → Leere Nachrichten hin- und herschicken. Um keine Aufwaermeffekte zu messen, erst einige Vorlaufbotschaften. Latenz = Zeit fuer ping bei ping pong, also GesamtZeit/(AnzahlNachrichten*2)
• Spielen Aufwaermeffekte bei Infiniband ueberhaupt eine Rolle? → Wegen Source Routing evtl. schon.
• Was ist der Half Power Point? → Im Durchsatz-Diagramm die Nachrichtenlaenge, bei der die halbe Bandbreite erreicht ist. Charakterisiert die Kurve.
• Wir wollen einen logischen Ring in MPI implementieren, also z.B. 4 Rechner, die sich im Kreis eine Nachricht schicken. Was kann man da fuer Probleme bekommen und wie macht man es besser? → Wenn man auf jedem Knoten ein MPI_Send und dann MPI_Recv macht, funktioniert das nur manchmal, abh. von MPI Implementierung und Nachrichtenlaenge, weil MPI_Send evtl. synchron sendet. also per MPI_Ssend. Mit MPI_Bsend geht es. Mit MPI_Sendrecv auch.

• Was ist List Ranking? Welchen Algorithmus haben wir dafuer kennen gelernt? → Wylies Algorithm. Dann hab ich schoen ausfuehrlich eine Beispielliste damit durchnummeriert.
• Was kann man alles parallel machen? → Man kann jedes Element der Liste parallel bearbeiten. log n Schritte mit n Prozessoren.
• Dann hat er mir folgenden Codeschnipsel gezeigt. proc1 und proc2 koennen jederzeit parallel laufen. Beweisen Sie, ob das assert stimmt.

shared int var=0; proc1(){ var++; } proc2(){ if (var==1){ var=2; } assert(var==2); } → stimmt offensichtlich nicht, wenn proc2 zuerst laeuft. Das sollte ich noch mit einem parallelen endlichen Automaten beweisen. Zeichnen Sie ein ein Sortiernetzwerk → Batchers Merging Netzwerk hingemalt, das sorting Netzwerk wollte er dann gar nicht mehr.

• Dann hat er mir gesagt, ich soll die Catalan Zahlen mit dynamischer Programmierung berechnen. Dazu hat er mir folgende Formel fuer die Catalen Zahlen hingelegt; (i,j) steht hier fuer „i ueber j“:

(n,0)=0; (2n,k)=(2n,k-1) Hier wusste ich nicht so genau, was er will, also hab ich erstmal bisschen was allgemeines ueber DP erzaehlt (Problem mit Divide and Conquer herunterbrechen und zwischenergebnisse speichern und wiederverwenden). Dann hab ich ihm gesagt, dass ja immer nur 0 rauskommen kann. Daraufhin hat er mir noch eine Zeile gezeigt: (n,k)=(n-1,k) Ich hab ihm erklaert, dass ich nicht glaube, dass die Formel stimmt, und das man das so auch nicht mit Divide and Conquer loesen kann. Ich hab eben nochmal nachgeschaut, was Catalan Zahlen sind, und festgestellt, dass die Formel fuer die n-te Catalan Zahl lautet: C_n = (2n,n)-(2n,n-1), wobei die Klammern Binomialkoeffizienten sind. Was er mir da gezeigt hat, war also ziemlicher Unsinn. Diese Frage hat dann auch zum Glueck nicht gezaehlt.

• Mit welcher Komplexitaet kann man eine P-CRCW PRAM Maschine mit n Prozessoren auf einer EREW simulieren? → Ich habe „in konstanter Zeit mit n*n Prozessoren“ geantwortet. Das hat er geschluckt. Es gab naemlich ein Uebungsaufgabe „can you sketch an algorithm to simulate a P-CRCW with N cpus by an EREW machine using n*n cpus?“. Allerdings war die Loesung, die er dazu an die Tafel gemalt hatte, falsch, weil sie nicht in O(1) funktioniert. Ich hab jetzt nochmal in Prof. Schneiders Folien nachgesehen, dort heisst es:

-Any algorithm running on a PRIORITY-CRCW with p(n) processors in time t(n) can be simulated on an EREW in time t(n)O(log(p(n)) without increasing the number of processors. -Any algorithm running on a PRIORITY-CRCW can be simulated by a COMMON-CRCW with no loss of parallel time provided sufficiently many processors are available.