270
5 Bewertung und Validierung
jeden Index verfügbar sein, wobei alle Indizes unabhängig voneinander behandelt
werden. Unter dieser Annahme sind alle Verdrängungen für einen bestimmten Index
vollständig unabhängig von den Entscheidungen für andere Indizes. Diese Unabhängigkeit ist sehr wichtig, da sie es uns ermöglicht, jeden der Indizes für sich alleine
zu betrachten.
Dementsprechend sehen wir uns nun das Verhalten des Caches für einen bestimmten Index und die dazu gehörige Cachezeile an. Was passiert jetzt bei einem Zugriff
auf diesen Index? Als erstes betrachten wir den Fall des Zugriffs auf eine Variable
e, die sich im Cache befindet. Nach dem Zugriff ist diese Variable die jüngste (siehe
Abb. 5.7). In der Abbildung sind die Einträge links stets jünger als solche rechts.
{e}
{a}
{d}
{f}
{e}
{a}
{d}
{f}
Abb. 5.7 Zugriff auf Variable e macht sie zur jüngsten
Im zweiten Fall gehen wir davon aus, dass wir einen Zugriff auf eine Variable c
haben, die sich noch nicht im Cache befindet. In diesem Fall wird die älteste Variable
verdrängt (siehe Abb. 5.8).
{f}
{d}
{a}
{e}
{c}
{e}
{a}
{d}
Abb. 5.8 Zugriff auf Variable c verdrängt f
Als nächstes beschäftigen wir uns mit rekonvergenten Programmpfaden, wie sie
nach der Bearbeitung von bedingten Anweisungen auftreten. Welche Informationen
haben wir über den Inhalt des Cacheteils nach einer solchen Vereinigung?
Wir müssen zwischen der may-Analyse und der must-Analyse unterscheiden.
Die must-Analyse gibt Auskunft darüber, welche Informationen sich sicher im Cache
befinden. Sie ist geeignet, Zusicherungen bei der Bestimmung von WCET-Schranken
zu geben. Die may-Analyse resultiert in Aussagen darüber, welche Informationen
sich möglicherweise im Cache befinden könnten. Diese Aussagen sind wichtig, um
zu wissen, was sich mit Sicherheit nicht im Cache befindet. Mit diesem Wissen
können wir BCET-Schranken bestimmen.
Betrachten wir zunächst die must-Analyse für rekonvergente Programmpfade.
Abbildung 5.9 zeigt eine entsprechende Situation. Das Alter der Einträge wachse
innerhalb eines Rechtecks von links nach rechts. Das Speicherobjekt c in Abb. 5.9
sei das jüngste Element in der Cachezeile, sofern wir über einen Programmpfad zur
Rekonvergenz gelangen und a sei das jüngste Element, sofern wir über den anderen
Pfad dorthin gelangen. Entsprechendes gilt für die älteren Einträge im Cache. Wir
wollen jetzt im Kontext der must-Analyse bestimmen, was der „schlechteste“ Fall