Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Thema: Cluster-Computing und Parallele Algorithmen (2006) (Übersicht)
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
pruefungen:hauptstudium:ls2:maerz_2006 [31.08.2006 11:52] – angelegt ThomasJanu | pruefungen:hauptstudium:ls2:maerz_2006 [08.09.2006 22:42] (aktuell) – Externe Bearbeitung 127.0.0.1 | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
+ | ====== Thema: Cluster-Computing und Parallele Algorithmen (2006)====== | ||
+ | |||
+ | * Prüfer: Philippsen | ||
+ | * Beisitzer: Veldema | ||
+ | * Ergebnis: 1,0 | ||
+ | |||
+ | ===== Bemerkungen ===== | ||
+ | |||
+ | * 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. | ||
+ | |||
+ | ===== Fragen ===== | ||
+ | |||
+ | ==== Cluster Computing (Philippsen): | ||
+ | |||
+ | * Welche Architektur haben nach Flynn Cluster? -> MIMD | ||
+ | * Was heisst das? Was gibt es noch? -> SIMD, z.B. Vektorrechner. Erfordern Spezialhardware, | ||
+ | * 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/ | ||
+ | * Spielen Aufwaermeffekte bei Infiniband ueberhaupt eine Rolle? -> Wegen Source Routing evtl. schon. | ||
+ | * Was ist der Half Power Point? -> Im Durchsatz-Diagramm die Nachrichtenlaenge, | ||
+ | * Wir wollen einen logischen Ring in MPI implementieren, | ||
+ | |||
+ | ==== Parallele Algorithmen (Ronald Veldema): ==== | ||
+ | |||
+ | * 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. | ||
+ | |||
+ | '' | ||
+ | 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, | ||
+ | |||
+ | * 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" | ||
+ | |||
+ | -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. | ||
+ | |||