Februar 2013
Prüfer: Dr. Ronald Veldema Beisitzer: Dipl.-Inf. Georg Dotzler

Während der Prüfung herrschte eine angenehme Atmosphäre. Für die Beantwortung schwieriger Fragen darf man sich ruhig auch kurz etwas Zeit zum Nachdenken nehmen; es muss also nicht auf jede Frage sofort eine Antwort folgen. Der Prüfungsstoff orientierte sich gefühlsmäßig an den Übungsblättern sowie den Programmier-Hausaufgaben, dazu kamen ein paar Transferfragen.

Q: Warum sollte man sich für parallele Algorithmen interessieren?

• wenn sequentiell zu langsam
• größere Probleme
• bestehende Einsatzmöglichkeiten (mehrere Cores, Cluster, …)

Q: Speedup? Gesetz von Amdahl?

• S = T_seq / T_par
• T_seq = T_p + T_s
• T_par = T_p / n + T_s
• Gesetz von Amdahl: n → unendlich: Speedup begrenzt durch sequentiellen Anteil

Q: Wie kann man Tiefensuche/Breitensuche parallel implementieren?

• Breitensuche:
  1. Prozessoren besuchen Knoten
  2. bei einer globalen Queue: Keine Breitensuche mehr, da Knoten aus tieferen Ebenen besucht werden können, bevor eine Ebene komplett abgearbeitet
  3. Lösung: Für jede Ebene eine Queue; Barriere zwischen Ebenen
• Tiefensuche:
  1. Knoten besuchen
  2. Für jeden Kindknoten neuen Thread starten

Q: Schachbrett: Wie kann man einen optimalen Zug mit einer NDTM finden?

• Für jeden möglichen Zug neue NDTM starten
• Sobald „gute“ Position gefunden: Andere NDTMs beenden und durchgeführte Züge zurückgeben
  1. > „schnellster“ Weg zum Sieg

Q: Aufwand dieses NDTM-Algorithmus?

• abhängig von Anzahl der Schritte bis zum Sieg

Q: Wir greifen mit Linda auf ein Bankkonto zu: Was ist, wenn man parallel von zwei Geldautomaten Geld abheben will?

• out(kontonummer, ?x) Abheben des gesamten Geldes vom Konto * x -= betrag * in(kontonummer, x) Einzahlen des verbleibenden Geldes
• Funktioniert auch, wenn parallel von zwei Bankautomaten, da dann der eine kein Tupel finden kann (out entnimmt Tupel)

Q: Wie funktioniert der Ticketing-Algorithmus?

• Zwei Zähler: Ticket-Zähler und Zähler für aktuelles Ticket
• lock():
  1. Thread zieht Ticket (Ticket-Zähler++)
  2. Thread wartet, bis aktuelles Ticket == gezogenes Ticket
• unlock():
  1. Thread erhöht Nummer des aktuellen Tickets
• Nur ein Thread im kritischen Abschnitt (nämlich der, für den aktuelles Ticket == gezogenes Ticket gilt)

Q: Wir haben ein sortiertes Zahlenarray: Suche die 5

• Divide and Conquer: Teile Array auf und schaue Partitionen parallel an
• Optimierung: Array ist sortiert
  1. Falls kleinste Zahl > 5 → nicht weiter absteigen
  2. Falls größte Zahl < 5 → nicht weiter absteigen

Q: Jetzt haben wir ein unsortiertes Zahlenarray: Suche Median

• Zähle für jede Zahl Anzahl der größeren Elemente
• Median = Element mit genau (Länge des Arrays) / 2 größeren Elementen

Q: Queue (lockfrei)

• enqueue(e):
  1. Setze Nachfolger von e auf head
  2. Setze head auf e
  3. Prüfe: Falls nicht geklappt: Zurücksetzen und Wiederholen
  4. (Q: Da ist doch eine Wettlaufsituation!) Atomar durchführen, z.B. mit Compare and Swap

Q: Wir wollen das Sieb des Eratosthenes parallelisieren, wie könnte man das machen? Wie ist der Aufwand?

• Das war eine Transferfrage; kam meines Wissens nach so nicht in der Vorlesung dran
• Nur Primzahlen zum Testen benutzen
• Primzahlen zu Menge hinzufügen → parallel
• Zahl x auf Teilbarkeit durch Primzahlen testen
• Aufwand: O(log n)

Q: Supermarkt, Datamining mit Output Partitioning: Wir wollen die Produkte, die am öftesten zusammen gekauft wurden

• Für jede mögliche Produktkombination Vorkommen zählen
• Produktkombination mit maximalem Vorkommen ermitteln (z.B. mit Reduction-Pattern)
  1. > wie in Hausaufgabe

Q: Gegeben sind zufällige Punkte mit zufälligen Kanten. Wie finden wir alle Komponenten?

• Graph contraction, bis jede Komponente nur aus einem Punkt besteht
• Anzahl der Komponenten = Anzahl der Superknoten

Q: Gegeben ist folgender Code:

for i = ...:
	a[i] = b[i + 1] * c[i * 2]

Dieser Code soll vektorisiert werden. Was ist überhaupt Vektorisieren?

• Vektorisieren = Operationen als Vektoroperationen auffassen ⇒ parallelisierbar (SIMD)

      for i = .../4:
		a[i * 4 + 0] = b[i * 4 + 1] * c[(i * 4 + 0) * 2]
		a[i * 4 + 1] = b[i * 4 + 2] * c[(i * 4 + 1) * 2]
		a[i * 4 + 2] = b[i * 4 + 3] * c[(i * 4 + 2) * 2]
		a[i * 4 + 3] = b[i * 4 + 4] * c[(i * 4 + 3) * 2]

• Problem: c[(i * 4 + x) * 2] nicht direkt hintereinander im Speicher → vorher umkopieren