Zeigerverdopplung

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Zeigerverdopplung
Hat diese tolle Zeigerverdopplung eigentlich irgendeine sinnvolle Anwendung?

Ich mein des Beispiel ist O(n) Zeit im Gegensatz zu der O(n) sequentiellen Lösung mit einem Thread – um auf O(log(n)) Zeit zu kommen müsst man die Threads noch mit nem exponentiellen Schema forken …

Und dann funktioniert das auch nur solange überhaupt sinnvoll wenn ich in << O(n) aus Iteratiosntiefe und irgendeinem nachfolger den Wert berechnen kann …

1 „Gefällt mir“

push :slight_smile:

2 „Gefällt mir“

1.Schritt: 1 Rank evaluierbar
2.Schritt: 2 Ränge evaluierbar
3.Schritt: 4 Ränge evaluierbar

Das heißt die Laufzeit müsste Logarithmisch sein.


Die Zeigerverdopplung, ebenso wie das Turnier-Verfahren übrigens, sind eigentlich auf einem speziellen Rechenmodell, der sogenannten PRAM (Parallel Random Access Machine), definiert. In diesem Berechnungsmodell sind zu Beginn alle Prozessoren aktiv, haben bereits ihre Daten (d.h. niemand muss den Prozessoren ihre Daten erst senden oder zuteilen) und arbeiten „im Gleichschritt“, d.h. führen parallel jeweils die gleiche Anweisung aus.

Damit spielt für die Laufzeit der Zeigerverdopplung (beim Turnierverfahren analog) auch wirklich bloß die Rangberechnung eine Rolle, weil alle Prozessoren schon zu Beginn „da“ sind und ihre Daten „haben“. Wie von Destranix richtig bemerkt, ist diese Laufzeit dann logarithmisch, da jeder Prozessor in jeder Iteration zwei Aktionen ausführt: Die bedingte Rangberechnung (sofern Nachfolgerrang bekannt) und die bedingte Nachfolgeraktualisierung (sofern Nachfolger vorhanden). Ergo hat eine Iteration konstante Laufzeit.

Das PRAM-Modell weicht sehr stark ab vom eigentlichen Fokus von PFP, nämlich der parallelen Berechnung auf Mehrkern-CPUs, auf denen eine Umsetzung von Verfahren, die für PRAMs optimiert wurden, oftmals keinen Vorteil gegenüber sequentiellen Umsetzungen bringt (ich habe mal testweise ein paar Anwendungen der Zeigerverdopplung – siehe nächster Absatz – implementiert. Selbst Probleme, die gerade so noch in 32 GB Arbeitsspeicher passten, waren zu klein, um irgendwelche Vorteile der parallelen Lösung zu sehen, wobei man natürlich nicht n Prozessoren einsetzen kann, sondern die Arbeit auf die existierenden Prozessoren verteilen muss). Mehr Ähnlichkeit gibt es da schon zur Berechnung auf Grafikkarten, die aber in PFP nicht angeschnitten wird. Auf diesen können dann diese parallelen Algorithmen wieder lohnenswert sein, weil hier die Menge an verfügbaren Prozessoren viel höher ist.

Das Problem, den Rang einer Liste zu bestimmen, kommt übrigens als Subproblem in verschiedenen, fortgeschrittenen parallelen Algorithmen vor, beispielsweise einer parallelen Tiefensuchnummerierung, der parallelen Berechnung der Größe von Unterbäumen, der parallelen Höhenberechnung in Bäumen sowie in verschiedenen anderen Graphalgorithmen. Aber auch das ist außerhalb des Fokus von PFP.

Wer möchte, kann aus meiner Antwort sicherlich ein paar Fragen für die Vorlesungsevaluation extrahieren. :wink:

2 „Gefällt mir“