Ich interessierte mich kürzlich für das allgemeine Problem der Optimierung der Speichernutzung in einer Situation, in der mehr als eine Art von Speicher verfügbar ist und es einen Kompromiss zwischen der Kapazität eines bestimmten Speichersegments und der Geschwindigkeit des Zugriffs darauf gibt.
Das bekannte Beispiel ist ein Programm, das entscheidet, wann aus dem Prozessor-Cache, dem RAM und der Festplatte (über den virtuellen Speicher) gelesen bzw. in diesen geschrieben werden soll .
Ich interessiere mich besonders für den Sonderfall, dass die zu ladende Datenmenge (einschließlich des Programms selbst) die Kapazität des schnellsten verfügbaren Speichers erheblich übersteigt (dh die triviale Lösung "nur alles laden" ist nicht anwendbar).
Ich fand, dass eine Wikipedia-Seite einige gängige Cache-Algorithmen beschreibt, was ich fast will. Leider sind diese ein bisschen niedrig:
- Viele, wie z. B. LRU oder MRU, sind nur dann sinnvoll, wenn Unterprogramme vorhanden sind, auf die häufig zugegriffen wird. Wenn ich ein Programm mit einer großen Anzahl von Unterroutinen habe, auf die einige in einem bestimmten Durchlauf nie zugegriffen werden, und auf einige von ihnen wird ein oder zwei Mal zugegriffen, funktioniert diese Strategie nie, weil nicht genügend Daten darauf aufgebaut werden können wird häufig verwendet und was nicht.
- Andere wie CLOCK scheinen sich eher mit den Besonderheiten der Implementierung zu befassen, als die eigentliche Wurzel des Problems anzugreifen.
- Ich weiß, dass es eine Strategie gibt, bei der man zuerst ein Programm während eines Testlaufs profiliert und dann das Profil für das Betriebssystem bereitstellt, um es entsprechend zu optimieren. Wir müssen jedoch das Problem der Bereitstellung eines wirklich repräsentativen "Beispielgebrauchs" beim Erstellen des Profils noch lösen.
Worüber ich wirklich lernen möchte, ist Folgendes: Wenn wir alle technischen Aspekte von Hardware und Software abstrahieren und in einem rein theoretischen Kontext sprechen, ist es möglich, die Struktur eines Algorithmus zu analysieren, um eine effektive Cache-Strategie für zu erarbeiten basiert es auf einem umfassenden Verständnis dessen, was der Algorithmus tut?
Antworten:
Ich kenne keine Methode zum Analysieren eines beliebigen Algorithmus, um im Allgemeinen eine Cache-Richtlinie zu erstellen (das klingt ziemlich schwierig), aber dies ist im Wesentlichen das, was im Einzelfall (im asymptotischen Sinne optimal) getan wurde -Fallbasis für die meisten bekannten Algorithmen , die den Cache nicht kennen , indem ihre Divide-and-Conquer-Struktur analysiert wird. Cache-vergessene Algorithmen sind für FFT, Matrixmultiplikation, Sortierung und einige andere bekannt. Siehe die Wikipedia-Seite und Referenzen darin.
quelle