Algorithmen für Caching?

Jester

Otze, das sieht so aus, als solltest du insbesondere matrixzeilen, deren g-wert besonders groß oder besonders klein ist bevorzugt behalten solltest, oder?

rapso

dachte ich auch erst, aber eigentlich sagt der inhalt nicht wie wahrscheinlich ein eintrag getroffen wird, jedoch sagt min udn max aus dass die wahrscheinlichkeit von eintraegen an den enden der matrix getroffen zu werden hoeher ist, jedoch mueste LRU und LFU das automatisch abdecken.

tntnet

Ich habe mal einen Algorithmus implementiert, der auf LRU basiert, aber in der Regel ein wenig besser ist. Du kannst die Implementierung in meinen cxxtools unter include/cxxtools/cache.h als C++ Template finden.

Der Algorithmus arbeitet so:

Der Cache wird zunächst einfach nur gefüllt.

Wenn er dann gefüllt ist, und es kommt ein neues Element hinzu, dann wird es in der Mitte platziert. Das Element vom Ende fällt weg. Bei jedem Hit wandert das Element an den Anfang.

Dadurch habe ich in der ersten Hälfte irgendwann nur noch Elemente, die bereits mindestens einmal wieder gebraucht wurden. Elemente, die immer nur ein mal zugegriffen werden, bleiben in der 2. Hälfte und fallen irgendwann raus.

volkard

rapso schrieb:

dachte ich auch erst, aber eigentlich sagt der inhalt nicht wie wahrscheinlich ein eintrag getroffen wird, jedoch sagt min udn max aus dass die wahrscheinlichkeit von eintraegen an den enden der matrix getroffen zu werden hoeher ist, jedoch mueste LRU und LFU das automatisch abdecken.

Schon. Aber Du könntest eventuell auch den Abstand von der Mitte dem Cache als Hint mitgeben und dadurch noch stärker sein.

Nur mal so ne Idee, keine Ahnung, wie brauchbar: Da Du Dich in LRU und LFU vertiefst, vielleicht beide mischen.
Mir fiele da ein, für die Frequenz einen n-Bit-Zähler zu benutzen, und immer je den ältesten kicken von denen mit der kleinsten Frequenz. Und wenn der n-Bit-Zähler eines Eintrags droht, überzulaufen, dann alle Zähler durch 2 teilen. Dann könnte man relativ weich zwischen reinem LRU (n=0) und reinem LFU (n=64) umschalten.
edit: Oder viel einfacher den Speicher teilen in einen LRU- und einen LFU-Teil und am Teilungsverhältnis einstellen.

rapso

mach uns ein zugriffs dump, vielleicht sehen wir ein pattern oder man kann es durchsimulieren mit den ideen hier

otze

Das dauert leider. Ich habe gerade keinen Zugriff auf den Server, da laufen gerade große Dinge drauf. Meine letzten Daten sind auch nicht sonderlich aussagekräftig, da habe ich gerade gemerkt, dass ich nur ca 0.1% bzw 0.6% aller Matrixzeilen speichern konnte (und dabei klangen 512MB cache soooo groß). Nicht gerade gute Voraussetzungen für eine Hit/Miss-Analyse

Andererseits werde ich damit rchnen müssen, dass meine Probleme häufiger so ein Verhältnis haben werden...ich brauch ja nur mal einen Datensatz mit einer Million Datenpunkten rein werfen.

volkard

otze schrieb:

Das dauert leider. Ich habe gerade keinen Zugriff auf den Server, da laufen gerade große Dinge drauf. Meine letzten Daten sind auch nicht sonderlich aussagekräftig, da habe ich gerade gemerkt, dass ich nur ca 0.1% bzw 0.6% aller Matrixzeilen speichern konnte.

*autsch*
Selbst der naivste Gauss mit

//n sei die zeilenanzahl
for(i=0;i<n;++i)
   for(j==0;j<n;++j)
      tuwas(zeile[i],zeile[j])

dürfte zu 50% treffen, weil zeile[i] immer im Cache liegt. Für 0.6% müssen die Zugriffe ja schon fast böswillig verteilt worden sein. Also MRU probieren, falls tatsächlich Böser Wille dahinter steckt.
Bei völligem Zufall kannste auch nix machen. MRU oder RANDOM oder eine beliebige fixe Auswahl und auf ein paar Prozent hoffen.

otze schrieb:

Nicht gerade gute Voraussetzungen für eine Hit/Miss-Analyse

Doch, absolut. Der Algo steht ja fest. Du hättest einfach eine Liste der Zeilen-Indeizes, die nacheinander angefordert werden. Und kannst damit zu Hause oder im Büro jederzeit Cache-Strategien ausprobieren, mit nur Sekunden-Laufzeit, ohne die große Maschine anwerfen zu müssen und ohne echte Daten durchnudeln zu müssen.

otze schrieb:

Andererseits werde ich damit rechnen müssen, dass meine Probleme häufiger so ein Verhältnis haben werden...ich brauch ja nur mal einen Datensatz mit einer Million Datenpunkten rein werfen.

Tja. Wenn man doch nur einen Teile-Und-Herrsche-Algo hätte. Dann wäre, sobald das Problem bis zur Cache-Größe runtergeteilt ist, LRU mit 100% dabei. Wenigstens zum Finden eines sehr guten Starts bevor das Nachiterireren kommt.

otze

volkard schrieb:

*autsch*

Nein, Missverständnis. Der Cache war 512MB groß, aveer die Gesamtgröße der Matrix zum Cachen aber irgendwo bei 500 GB. Dafür mache ich keine Hit/Miss Analyse. Treffe ja eh nie :). Ich muss das selbe Experiment mal mit 4-8GB starten, dann sehen wir bessere Werte (vertraue niemals auf "sichere defaults").

otze schrieb:

Andererseits werde ich damit rechnen müssen, dass meine Probleme häufiger so ein Verhältnis haben werden...ich brauch ja nur mal einen Datensatz mit einer Million Datenpunkten rein werfen.

Tja. Wenn man doch nur einen Teile-Und-Herrsche-Algo hätte. Dann wäre, sobald das Problem bis zur Cache-Größe runtergeteilt ist, LRU mit 100% dabei. Wenigstens zum Finden eines sehr guten Starts bevor das Nachiterireren kommt.

Wenn die Teile- und Herrsche Ansätze nicht Faktor 10 langsamer wären, würde man das ja machen. Dafür nen ordentlichen Cache schreiben ist total trivial (und die Matrix blockweise zu evaluieren ist auch wesentlich schneller), aber ich bezahle das Teilen mit einer echt langsamen Konvergenz.

rapso

otze schrieb:

Das dauert leider. Ich habe gerade keinen Zugriff auf den Server, da laufen gerade große Dinge drauf. Meine letzten Daten sind auch nicht sonderlich aussagekräftig, da habe ich gerade gemerkt, dass ich nur ca 0.1% bzw 0.6% aller Matrixzeilen speichern konnte (und dabei klangen 512MB cache soooo groß). Nicht gerade gute Voraussetzungen für eine Hit/Miss-Analyse

wenn du 2GB ram hast und deine CPU 2MB cache hat, bist du bei exakt dem verhaeltnis und das ist gaengig.

ist es schneller die nicht gecachten daten neu zu berechnen als sie z.b. von einer SSD zu laden? 500GB kosten 250euro und koennten dir vielleicht viel zeit sparen.

otze

Hi,

sorry für die späte Antwort, ich musste leider für ne Besprechung Zeugs vorbereiten ~~. Eine SSD wird wahrscheinlich noch langsamer sein, zumindest bei den meisten Problemen. Vielleicht hilft es bei manchen Datensätzen (ich kriege hier nen Datensatz mit 80000 dimensionalen Daten die Tage rein), bei den Meisten ist aber die Berechnung eines ELements viel schneller als das Laden von der SSD. Es ist nur die Menge der Elemente, die Probleme macht.

Ich habe, da der Server noch immer besetzt ist, für einen Datensatz mit 50.000 Datenpunkten und einem etwas cache-freundlicheren Auswahlverfahren für die Indizes die Experimeente wiederholt. Gerade lasse ich auch was mit 100k Datenpunkten laufen.

Das Verfahren wählt die indizes so, dass in der nächsten iteration i immer eines der indizes der vorherigen iteration ist. Der Cache ist so gewählt, dass 1342 Matrixzeilen in den Speicher passen, was 2.68% sind. Baseline sollten damit 50%+0.5*2.68% = 51.34% sein. Mit LRU erreichen wir jetzt gerade 51.056%.

Daten sind hier:

http://pastebin.com/Zhgcwdnk

rapso

nur um sicher zu gehen, die liste sind die requests und der cache hat 1342 eintraege?

edit:
mit einem simpmlen LRU erreiche ich 2.33% hit rate, passt das mit deinen werten? (ich denke die 50% die du jetzt bias hast zerstoeren ein wenig den cache vom lauf und deswegen hast du keine 52.33%?)

edit2:
hab nun mal random cache, LRU,LFU,direct mapped eingebaut, wenn der cache groesser ist als deine suchmenge (also perfekt caching), kommt man auf
Rand: 8.229740
LRU : 8.229740
LFU : 8.229740
DM : 8.229740

bei 1342 eintraegen
Rand: 2.327011
LRU : 2.338185
LFU : 2.338185
DM : 2.335391

die werteverteilung deiner daten ist dabei
1121 1102 1110 1154 1085 1114 1122 1109 1124 1066 1094 1126 1123 1152 1071 1113 1137 1124 1085 1139 1059 1145 1080 1088 1125 1168 1163 1138 1107 1088 1173 1192

solange niemand in der generierte sequenz ein muster erkennt, ist es random und entsprechend ist so ziemlich jede cache strategie nutzbar, da es nicht auf diese ankommt, sondern einfach nur auf die deckung von cache_size:search_range.

wenn ich mir die hits anschaue, ist die verteilung nicht wirklich gleichmaessig (ich hatte ja vermutet dass die min/max werte oefter vorkommen).
232 118 184 164 280
wenn ich jetzt das direct mapping ein wenig biase dass groessere entries etwas mehr platz bekommen, erhalte ich:
Rand: 2.335391
LRU : 2.338185
LFU : 2.338185
DM : 2.335391
DMB: 2.354946 <-- 0.02 prozentpunkte mehr hitrate. koennte aber auch nur random sein.

otze

Genau. Woher die Differenz kommt, weiß ich nicht.

Hast du beim einlesen der Datenpunkte die verdoppelungen ignoriert? sonst müsstest du ja auch auf 50+% kommen. das würde die differenz auch halbwegs erklären:

wenn du auf 50% der Anfragen 2.33% hast, dann macht das im Gesamten 1.165% aus. Es kann sein, dass der Cache vielleicht 2-3 Zeilen weniger hat, das waren leider nur geschätzte Daten aus der maximalen Cache-Größe. Der Code gibt das leider nicht so einfach her...

Aber deine Beobachtung kann ich bestätigen: Wir gehen davon aus, dass die Zugriffe zufällig sind und dass man a-priori kein Häufungspunkte feststellen kann (der index hat keine Bedeutung, da die Zeilen/Spalten der Matrix zufällig permutiert sind).

Ich verstehe abe rnicht ganz die Bedeutung deiner Zahlen. Insbesondere bei "232 118 184 164 280 " ist mir unklar, was das darstellen soll.

Um das Problem zu beschrieben: das ganze ist ein QP und die indizes sind die Variablen, die der Algorithmus als nächstes optimiert. Als Auswahlkritrium habe ich Hybrid-Maximum-Gain verwendet, was einfach bestimmt, für welches Variablenpaar der Wert der Zielfunktion maximal reduziert wird. Und ja, dieses Verhalten ist ziemlich zufällig - leider.

Was ich mir überlegen kann, ist HMG auf die Variablen im Cache zu beschränken, und somit die Cache-Auslastung "künstlich" zu verbessern. Aber wenn ich mir die Verteilung der Werte anschaue..ich weiß nicht.

rapso

otze schrieb:

Ich verstehe abe rnicht ganz die Bedeutung deiner Zahlen. Insbesondere bei "232 118 184 164 280 " ist mir unklar, was das darstellen soll.

die erste sequenz ist ein histogram der zahlenhaeufigkeit, diese 5 hier ist ein kleines histogram der cachehit haeufigkeit.