Zugriffszeit pro Wort berechnen

[osion]

Hallo

Ich weis nicht wie ich das berechnen soll.



Ich dachte, dass ich diese Formel verwenden kann:

Aber jetzt fällt mir noch 2ns aus dem Cache oder nach 10ns aus dem Main Memory.

 

[httpdigest]

Nehmen wir erstmal an, dass es nur zwei Wahrscheinlichkeiten p0 und p1 mit zwei Wartezeiten t0 und t1 gibt.
In diesem Fall wäre ja die durchschnittliche Wartezeit bzw. der "Erwartungswert" (in der Wahrscheinlichkeitsrechnung):
E = p0*t0 + p1*t1

Du hast quasi zwei Wahrscheinlichkeiten gegeben, von denen eine eine bedingte Wahrscheinlichkeit ist.
Und genau genommen hast du drei Wahrscheinlichkeiten, nämlich zusätzlich noch die Restwahrscheinlichkeit für einen Festplattenzugriff, die nicht explizit angegeben ist, sich aber aus den anderen Wahrscheinlichkeiten ergibt. Zusammen muss ja alles 100% ergeben.

"Erwartungswert" in der Wahrscheinlichkeitsrechnung ist also dein Stichwort, zusammen mit "bedingten Warhscheinlichkeiten".

 

[httpdigest]

Das nochmal etwas detaillierter erklärt, was wir hier eigentlich machen müssen.
Ausgehen musst du auf jeden Fall von der Formel des Erwartungswertes E (in der Wahrscheinlichkeitsrechnung).
Diese ist die Summe aus den Produkten der Einzelwahrscheinlichkeiten mit ihren jeweiligen Werten (in deinem Fall die Wartezeiten bzw. Zugriffszeiten).

Konkret hast du bei dir genau drei diskrete Wahrscheinlichkeiten gegeben.
Nennen wir sie:

• P_sram = Wahrscheinlichkeit für einen Cache-Hit im SRAM
• P_dram = Wahrscheinlichkeit für einen Cache-Hit im DRAM (Hauptspeicher)
• P_hd = Wahrscheinlichkeit für einen "Cache-Hit" auf der Festplatte (Harddisk)

Die Wahrscheinlichkeit für einen Cache-Hit im SRAM ist direkt in der Aufgabenbeschreibung gegeben mit 95%, also 0,95 zum Rechnen später.
Die Wahrscheinlichkeit für einen Cache-Hit im DRAM ist auch direkt gegeben mit 99%, also 0,99. Wichtig hierbei ist, dass dies eine bedingte Wahrscheinlichkeit sein wird später im Erwartungswert, nämlich der Wert: P = P_dram | (1 - P_sram). Im Erwartungswert brauchen wir also nicht die 0,99, sondern die bedingte Wahrscheinlichkeit P = 0,99 * (1 - 0,95), da der Zugriff im DRAM ja nur stattfindet, wenn eben der Zugriff auf den SRAM ein Cache-Miss war, und somit von der komplementären Wahrscheinlichkeit von P_sram, also 1 - P_sram, abhängt.

Unsere dritte Wahrscheinlichkeit ist die für einen "Cache-Hit" auf die Festplatte, also die Wahrscheinlichkeit, mit der wir definitiv unser Datum auf der Festplatte finden werden. Diese wird hier implizit mit 100% = 1 angenommen. In dem Erwartungswert brauchen wir hier aber auch wieder eine bedingte Wahrscheinlichkeit. Der Festplattenzugriff findet ja nur statt, wenn sowohl der SRAM Zugriff als auch der DRAM Zugriff beide ein Cache-Miss waren. Also hier: P = P_hd | (1 - P_dram | (1 - P_sram)) = 1 * (1 - 0,99) * (1 - 0,95)

Jetzt brauchst du nur noch den Erwartungswert zu bilden aus den drei einzelnen Wahrscheinlichkeiten (von denen wir zwei bedingte Wahrscheinlichkeiten sind) und musst auf die richtige Einheit bei den Zugriffszeiten achten (also Nanosekunden vs Millisekunden und das Ergebnis soll in Mikrosekunden sein!)

 

[osion]

Das nochmal etwas detaillierter erklärt, was wir hier eigentlich machen müssen.
Ausgehen musst du auf jeden Fall von der Formel des Erwartungswertes E (in der Wahrscheinlichkeitsrechnung).
Diese ist die Summe aus den Produkten der Einzelwahrscheinlichkeiten mit ihren jeweiligen Werten (in deinem Fall die Wartezeiten bzw. Zugriffszeiten).

Konkret hast du bei dir genau drei diskrete Wahrscheinlichkeiten gegeben.
Nennen wir sie:

• P_sram = Wahrscheinlichkeit für einen Cache-Hit im SRAM
• P_dram = Wahrscheinlichkeit für einen Cache-Hit im DRAM (Hauptspeicher)
• P_hd = Wahrscheinlichkeit für einen "Cache-Hit" auf der Festplatte (Harddisk)

Die Wahrscheinlichkeit für einen Cache-Hit im SRAM ist direkt in der Aufgabenbeschreibung gegeben mit 95%, also 0,95 zum Rechnen später.
Die Wahrscheinlichkeit für einen Cache-Hit im DRAM ist auch direkt gegeben mit 99%, also 0,99. Wichtig hierbei ist, dass dies eine bedingte Wahrscheinlichkeit sein wird später im Erwartungswert, nämlich der Wert: P = P_dram | (1 - P_sram). Im Erwartungswert brauchen wir also nicht die 0,99, sondern die bedingte Wahrscheinlichkeit P = 0,99 * (1 - 0,95), da der Zugriff im DRAM ja nur stattfindet, wenn eben der Zugriff auf den SRAM ein Cache-Miss war, und somit von der komplementären Wahrscheinlichkeit von P_sram, also 1 - P_sram, abhängt.

Unsere dritte Wahrscheinlichkeit ist die für einen "Cache-Hit" auf die Festplatte, also die Wahrscheinlichkeit, mit der wir definitiv unser Datum auf der Festplatte finden werden. Diese wird hier implizit mit 100% = 1 angenommen. In dem Erwartungswert brauchen wir hier aber auch wieder eine bedingte Wahrscheinlichkeit. Der Festplattenzugriff findet ja nur statt, wenn sowohl der SRAM Zugriff als auch der DRAM Zugriff beide ein Cache-Miss waren. Also hier: P = P_hd | (1 - P_dram | (1 - P_sram)) = 1 * (1 - 0,99) * (1 - 0,95)

Jetzt brauchst du nur noch den Erwartungswert zu bilden aus den drei einzelnen Wahrscheinlichkeiten (von denen wir zwei bedingte Wahrscheinlichkeiten sind) und musst auf die richtige Einheit bei den Zugriffszeiten achten (also Nanosekunden vs Millisekunden und das Ergebnis soll in Mikrosekunden sein!)

Wie würde das Formelmässig aussehen? Ich verstehe nur die Hälfte...

 

[httpdigest]

E = 0.95 * 2ns + (1 - 0.95) * (0.99 * 10ns) + (1 - 0.95) * (1 - 0.99) * 10000000ns
  = 0.95 * 2ns + (1 - 0.95) * ((0.99 * 10ns) + (1 - 0.99) * 10000000ns)

Check, dass die Gesamtwahrscheinlichkeit immer noch 1 ist:

1 = 0.95 + (1 - 0.95) * (0.99 + (1 - 0.99))

 

[White_Fox]

Wie würde das Formelmässig aussehen? Ich verstehe nur die Hälfte...

Dann bringt dir die Formel nicht viel.

Versuche erstmal zu verstehen, was der httpdigest dir da erklärt hat. Wenn du es selber in eigenen Worten erklären kannst, wird dir die Formel nicht schwerfallen bzw. kannst du dir die Formel dann selber schreiben.

 

[httpdigest]

Vielleicht nochmal eine kleine Erklärung, weil meine Notation nicht exakt war und nicht der in der einschlägigen Literatur entsprach.

Erstmal wichtige Links:
1. https://de.wikipedia.org/wiki/Erwartungswert#Erwartungswert_einer_diskreten_reellen_Zufallsvariable
2. https://de.wikipedia.org/wiki/Bedingte_Wahrscheinlichkeit#Multiplikationssatz

Prinzipiell haben wir eine Zufallsvariable X mit den drei Ereignissen:

• x_0 = SRAM = Wort wird vom SRAM geladen
• x_1 = DRAM = Wort wird vom DRAM geladen
• x_2 = HD = Wort wird von der Festplatte geladen

Wir haben die Wahrscheinlichkeiten der einzelnen Ereignisse:

• P(SRAM) = Wahrscheinlichkeit, dass das Ereignis SRAM eintritt (95%)
• P(DRAM | ~SRAM) = Wahrscheinlichkeit, dass das Ereignis DRAM eintritt unter der Bedingung, dass nicht das Ereignis SRAM eingetreten ist (99%) (die Ereignisse sind ja abhängig voneinander, also SRAM und DRAM können nicht gleichzeitig eintreten)
• P(~DRAM | ~SRAM) = Wahrscheinlichkeit, dass nicht DRAM eingetreten ist unter der Bedingung, dass ebenfalls nicht SRAM eingetreten ist (das wird die Wahrscheinlichkeit für das HD Ereignis sein)

Notation: ~SRAM = Gegenereignis/Komplementärereignis zu SRAM ; also das Ereignis, dass ein SRAM-Cache-Hit nicht stattfand (und deswegen im DRAM oder HD geguckt werden muss)
Äquivalent bedeutet dann halt ~DRAM auch das Komplementärereignis von DRAM.

Wir haben oben bedingte Wahrscheinlichkeiten gegeben, benötigen aber ihre jeweiligen Verbundwahrscheinlichkeiten P(A ∩ B) für die Berechnung des Erwartungswertes. Hierzu wenden wir den Multiplikationssatz (siehe Link 2.) an, welcher sagt, dass sich die Verbundwahrscheinlichkeit ergibt als: P(A ∩ B) = P(A | B) * P(B)

// Ereigniswert ist die Summe über die Produkte aus allen Ereignissen x_i und ihren Wahrscheinlichkeiten p_i
E(X) = Σ x_i * p_i

// Wir haben effektiv drei Ereignisse (SRAM, DRAM und HD) mit ihren jeweiligen Eintrittswahrscheinlichkeiten
E(X) = x_0 * P(x_0) + x_1 * P(x_1) + x_2 * P(x_2)

// Wenn wir unsere konkreten Ereignisse und
E(X) = 2ns * P(SRAM) + 10ns * P(~SRAM ∩ DRAM) + 10ms * P(~SRAM ∩ ~DRAM)
     = 2ns. * 0.95 + 10ns * P(~SRAM | DRAM) * P(DRAM) + P(~SRAM | ~DRAM) * P(~DRAM) * 10ms.
     = 0.95 * 2ns. + (1 - 0.95) * 0.99 * 10ns. + (1 - 0.95) * (1 - 0.99) * 10ms.
     = 5.002395 µs.

Bei Zeile 9 im Codeblock oben wenden wir den Multiplikationssatz P(A ∩ B) = P(A | B) * P(B) an, um die Verbundwahrscheinlichkeit, dass sowohl A als auch B zusammen auftreten, zu berechnen.