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.
Brent
Hallo,
ich hätte Fragen zu Brent.
a) Zur Berechnung auf Folie 09-13 (Siehe Anhang) habe ich mir Folgendes gedacht:
T_p(n) = T_n(n) = Laufzeit des vorhandenen Algorithmus mit p Prozessoren (wobei p = n)
Aus T_n(n) € O(log_2(n)) folgt: t = log_2(n)
s/t = (n*log_2(n))/(log_2(n))
→ Weil in diesem Fall T_p(n) == T_(s/t)(n) gilt, gibt es (zumindest laut Brent) keinen besseren Algorithmus.
Ist das so richtig?
Und wie berechnet man das s?
b) Ist der Satz von Brent das gleiche wie das Lemma von Brent?
Satz von Brent: “Ein paralleler Algorithmus, der mit p Prozessoren eine TIME von T_p(n) und einen WORK von W(n) hat, kann auf p’ < p Prozessoren in T_(p’)(n) = T_p(n) + floor(W(n)/p’) ausgeführt werden.”
Hi,
hat schon jemand Antworten auf die Fragen zu Brent gefunden?