Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Parallele Algorithmen

Parallele Algorithmen

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