Not logged in. · Lost password · Register

siccegge
Debian Dude
Avatar
Member since Oct 2009
316 posts
Subject: Zeigerverdopplung
+1 Marcel[Inf]
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 ...
Sommerhitze
Member since Jun 2019
1 post
+2 LasagneAlForno, zge
*push*  :-)
Destranix
Erfahrener Webhelfer und Um-Rat-Frager
Member since Sep 2018
288 posts
In reply to post #1
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.
I hate Forumssignaturen
mkmdl
Member since Nov 2009
272 posts
+2 Marcel[Inf], LasagneAlForno
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. ;)
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen