Algorithmen für Caching?

[otze]

Hi,

mein Problem ist folgendes:

ich habe eine symmetrisch Matrix M. Ein Eintrag M(i,j) ist (beliebig) teuer zu berechnen und die gesamte Matrix ist so groß, dass sie nicht einmal ansatzweise in den Speicher passt. Da wir pro Iteration unseres Algorithmus nur einzelne Matrixzeilen (in zufälliger Reihenfolge) brauchen, cachen wir einzelne Zeilen der Matrix und geben vor, dass wir nur eine maximale Speichermenge zur Verfügung stellen, zum Beispiel 500.000 Elemente der Matrix. Wir gehen davon aus, dass wir zu Anfang fast nur cache-misses haben, sich aber nach einiger Zeit Zugriffsmuster bilden, d.h. das bestimmte Variablen viel häufiger als andere ausgewählt werden (und es kann sein, dass einzelne Zeilen gar nicht benötigt werden).

Bislang haben wir dafür einen selbst gebastelten Algorithmus verwendet, der einfach nur die älteste Zeile der Matrix entfernt, wenn ein Cache-Miss eintritt und di nue Zeile nicht mehr in den Cache passt. Wir sind uns aber eigentlich sicher, dass es dafür schon fertige Algorithmen gibt. Ziel ist es, den Caching Aufwand zu minimieren und den Cache intelligenter hinzukriegen.

Kennt sich vielleicht jemand mit Caching-Strategien aus, wie man diesen Matrixcache relativ effizient hin kriegt? Literatur reicht mir völlig :).

[volkard]

Vielleicht helfen Dir Suchwörter? http://de.wikipedia.org/wiki/Cache#Verdr.C3.A4ngungsstrategien

Welche Strategie am besten ist, dürfte allein vom Zugriffsmuster abhängen. Und da das nicht bekannt ist, mußt Du wohl verschiedene Algos ausprobieren.

Ich vermute, anm besten wäre es, was Einfaches und gut vorhersehbares wie Euer LRU zu nehmen, um den Leuten, die die Matrix-Algos schreiben, eine verläßliche Sache zu bieten, wohin sie ihre Algos optimieren können.

[knivil]

http://en.wikipedia.org/wiki/Cache_algorithms Ein full associative cache wie aktuell genutzt wird, ist nicht optimal.

[hustbaer]

knivil schrieb:

Ein full associative cache wie aktuell genutzt wird, ist nicht optimal.

Kann man so allgemein wohl nicht sagen.
Kommt stark drauf an um wie viele Hits man durch einen Cache mit begrenzter Assoziativität verliert, und wie lange es dauert die "verpassten" Werte neu zu berechnen.

@otze
Ihr könntet die Zugriffe mal rausloggen lassen. Dann hätte man Daten anhand derer man leicht und vor allem schnell mehrere Caching-Strategien vergleichen kann. Einfach ne kleine Simulation schreiben.
Macht natürlich nur Sinn wenn ein "echter" Testlauf relativ langsam/umständlich/teuer/... ist.

[otze]

Danke für die Antworten.

Ja, wahrscheinlich muss man das einfach Benchmarken.

Wir benutzen momentan LRU und die Berechnung der Matrixzeilen machen trotzdem noch gut 80-90% der Rechenzeit aus. Das kann aber beliebig ansteigen. In einem einfachen Problem bnötigt die Berechnung eines elements ca 200 Multiplikationen, Additionen und eine exp-Funktion. Der Algorithmus selbst benötigt dann vielleicht noch 2 multiplikationen und additionen pro Element. Also völlig vernachlässigbar.

Leider kann man nicht einfach einmal vor-simulieren und dann den richtigen Cache für die Praxis finden. Der Algorithmus wird zwar für eine Matrix M bis zu 100-150 mal mit unterschiedlichen Parametern aufgerufen, aber leider verändern die Parameter das Laufzeitverhalten beträchtlich (ein bestimmter Parameter verändert die Laufzeit von wenigen Stunden auf mehrere Wochen...).

Es gibt aber immer 3 Phasen:
1. Anfang: vollkommen zufällige Zugriffsmuster, viele Zeilen werden nur einmal gebraucht
2. Mitte: ziemlich zufällig, aber bestimmte Zeilen werden wesentlich öfter genutzt als andere
3. Ende: wieder relativ zufällig, aber nur noch eine geringe Anzahl von Zeilen in Verwendung, häufig sogar weniger als der Cache Platz hat.

Ich glaube, dass ich drei lohnenswerte Strategien habe:
1. LRU, was wir jetzt verwenden
2. LFU
3. Least-Priority - ich kann grob die Zeilen in 3 Kategorien einteilen:
3.1 wahrscheinlich, dass sie wiederverwendet wird
3.2 unwahrscheinlich
3.3 nicht in den nächsten 10000 Iterationen.

Ich könnte also zuerst Zeilen des Typs 3.3 entfernen und dann round-robin mäßig 3.1 und 3.2 nach LRU/LFU. Das Problem an Zeilen des Typs 3.3 ist, dass sie wahrscheinlich gar nicht gecached sind(mal von der Anfangsphase abgeshen, da kommt das sicherlich vor)

[rapso]

wie hoch ist denn eure hit:miss rate? wie gross ist der cache in relation zum suchraum?

am besten funzen caches wenn sie an die algorithmen angepasst sind die sie nutzen, wenn es komplett random ist/waere, wuerde die hit rate bestenfalls cache-size:range-size sein, aber das nette dabei ist, dass auch schlechte algorithmen dann noch fast ans optimum kommen.

kannst du den algorithmus vielleicht 10stufen weiterarbeiten lassen bevor du die aktuelle cache anfrage beim miss verarbeitest? du koenntest dann wissen welche nachfolgenden 10 treffer benoetigt werden und diese dann in keinem fall entfernen.

vielleicht bringt es was partielle teile der berechnungen zu speichern, falls diese weniger speicher verwenden? -> (so ala rainbow table effekt) -> mehr cache

kompression vielleicht?

haben cache eintraege irgend eine relation zueinander? koennte man nachbar eintraege vielleicht rekonstrukieren?

du koenntest ein zugriffsmuster mal dumpen und dann verschiedene cachesimulationen drauf laufen lassen, oft ist profilen besser als theorie
(und/oder hier verlinken :D)

manchmal kann ein direct mapped cache besser sein als der voll assoziative den du jetzt nutzt, das haengt stark von den zugriffsmustern ab, es kann auch was bringen nur gewisse teile zu cachen und andere immer zu berechnen.

[otze]

Hi,

Rapso, die Ansätze sind zwar gut, aber leider bei mir nicht anwendbar.

stark vereinfacht sieht der Algorithmus so aus:

initialisiere g = (1,...1);//1 Eintrag pro Matrixzeile
while (not converged)
    i = arg min g;
    j = arg max g;
    mu = getStepLength(i,j);
    g-= mu*(M.row(i)-M.row(j));

wenn also Zeile i oder j nicht im Cache ist, kann ich nicht weiter machen, weil ich das nächste arg min/arg max nicht berechnen kann. In der Theorie ist das etwas freier, in der praktischen Anwendung schlägt diese Form aber alles andere.

die Berechnungen speichern/rekonstruieren kann ich vergessen. M ist sowas wie:

M(i,j)=exp(-x_i^Tx_j)

(wobei x_i Datenpunkte sind) aber auch beliebig viel hässlicher. Im Allgemeinen Fall, für den ich programmieren muss, können die x_i irgendwelche strings sein und M(i,j) dann irgendeine Metrik im Raum der Strings oder so.

[rapso]

mit kompression auch nichts zu holen? was sind da fuer werte in der matrix? floats? ints? duerftest du die quantitisieren?

und wie hoch ist die hitrate? und die cache size in relation zum suchraum, daraus koennte man abschaetzen wie effektiv es schon ist.

[Swordfish]

...

[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.