===== 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:
		- Prozessoren besuchen Knoten
		- bei einer globalen Queue: Keine Breitensuche mehr, da Knoten aus tieferen Ebenen besucht werden können, bevor eine Ebene komplett abgearbeitet
		- Lösung: Für jede Ebene eine Queue; Barriere zwischen Ebenen
	* Tiefensuche:
		- Knoten besuchen
		- 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
		-> "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():
		- Thread zieht Ticket (Ticket-Zähler++)
		- Thread wartet, bis aktuelles Ticket == gezogenes Ticket
	* unlock():
		- 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
		- Falls kleinste Zahl > 5 -> nicht weiter absteigen
		- 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):
		- Setze Nachfolger von e auf head
		- Setze head auf e
		- Prüfe: Falls nicht geklappt: Zurücksetzen und Wiederholen
		- (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)
		-> 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