Servus
Ich suche das obige. Vielleicht weiß jemand was :) Hab heute recht lange
gegooglet aber nichts brauchbares gefunden. Wie der kram in der Theorie
funktioniert weiß ich grob, das hilft mir aber nicht den Algorithmus zu
programieren.
Grüße
Gelesen habe ich mittlerweile viel und ich denke ich könnte einen selbst
implementieren. Ich denke mir aber, dass Beispielcode nach wievor eine
Anregung sein kann. Immerhin ist nicht optimaler Code nicht unbedingt
schnell...
Villeicht kann jajemand helfen
Da der Gedanke hinterm "Cash" ja einfach ist und die verschiedenen
Strategien auch in drei / vier Sätzen erklärt sind, ist Pseudocode ja
fast schohn eine Armutserklärung.
Siehe:
http://en.wikipedia.org/wiki/Cache_algorithms
Bedenke:
optimaler Code != optimaler Algorithmus
Ja natürlich, LRU ist nicht für jede Situation geeignet und genauso kann
ARC falsch sein. Ich denke nur, dass optimierter Code ggf. besser ist
als das was aus meiner Feder stammt.
Was mich auch stutzig macht: Ich habe bei Koders eine ARC
implementierung aus dem Sun Solaris gefunden. >2000LOC, das was mir als
implementierung im Kopf rumgeistert hat vll 200LOC - da macht sich in
mir der Gedanke breit, dass meine Überlegung nicht die beste sein kann.
Ich werf noch zwei zusätzliche Fragen ein: Wie benchmarked man die
Algorithmen am besten? Ich würde nun Dummy-Datensätze aus dem Cache
laden und in den Cache schreiben. Die häufigkeit wie oft ein Datum
geschrieben/gelesen wird kann man dabei ja relativ einfach steuern
(jeder 2te Schleifendurchlauf Datum A, jeder 5te Datum B, jeder 20te
Datum C).
Und wie entscheide ich, dass ein Algorithmus besser tauglich ist als ein
anderer.
Grüße
Ano Nym schrieb:> Ja natürlich, LRU ist nicht für jede Situation geeignet und genauso kann> ARC falsch sein. Ich denke nur, dass optimierter Code ggf. besser ist> als das was aus meiner Feder stammt.
Selber den Code studieren macht schlau.
Gerade dann wenn es um die Feinheiten geht
> Was mich auch stutzig macht: Ich habe bei Koders eine ARC> implementierung aus dem Sun Solaris gefunden. >2000LOC, das was mir> als implementierung im Kopf rumgeistert hat vll 200LOC - da macht> sich in mir der Gedanke breit, dass meine Überlegung nicht die> beste sein kann.
Was hat das eine mit dem anderen zu tun?
Ich könnte ja auch argumentieren, dass dein Cache besser ist, weil er
weniger COde braucht und daher schneller abgearbeitet wird.
Was hilft mir der beste Cache, wenn der Cache Algorithmus bei einem
Cache Miss länger braucht als wie wenn einfach auf die Daten zugegriffen
wird und ich ständig Cache Misses habe? Dann wäre ich ohne Cache besser
bedient gewesen.
> Und wie entscheide ich, dass ein Algorithmus besser tauglich ist als ein> anderer.
Indem du zuerst einmal definierst was "besser" bedeutet.
Und du dann eine Vergleichsimplementierung des Konkurenzalgorithmuses
schaffst und die benchmarkst.
Besondere Bedeutung kommt deiner Teststrategie zu. Da ist es wichtig,
dass deine Zugriffe realistisch sind. Das heißt: sie spiegeln die
wahrscheinliche tatsächliche Zugriffsfolge wieder. Jeden Cache kann man
mit der falschen Zugriffsstrategie aushebeln. Daher gibt es auch per se
kein "besser" oder "schlechter" sondern nur ein "besser in Bezug auf ...
" oder "schlechter in Bezug auf ..."
Karl heinz Buchegger schrieb:> Selber den Code studieren macht schlau.> Gerade dann wenn es um die Feinheiten geht
Mit ein Grund weshalb ich Beispiele suche :)
> Was hat das eine mit dem anderen zu tun?> Ich könnte ja auch argumentieren, dass dein Cache besser ist, weil er> weniger COde braucht und daher schneller abgearbeitet wird.> Was hilft mir der beste Cache, wenn der Cache Algorithmus bei einem> Cache Miss länger braucht als wie wenn einfach auf die Daten zugegriffen> wird und ich ständig Cache Misses habe? Dann wäre ich ohne Cache besser> bedient gewesen.
Geb ich dir auch wieder recht. Nur glaube ich im vorliegenden Fall nicht
das die Mechanik schlecht ist - daher Argumentiere ich mit mehr=besser
> Indem du zuerst einmal definierst was "besser" bedeutet.> Und du dann eine Vergleichsimplementierung des Konkurenzalgorithmuses> schaffst und die benchmarkst.
So hätte ich es wohl gemacht ... einfach die, die es gibt implementieren
und schauen welcher die besten Ergebnisse erzielt (die wenigstens
Misses, die wenigsten Zugriffe auf den physikalisch echten Speicher).
> Besondere Bedeutung kommt deiner Teststrategie zu. Da ist es wichtig,> dass deine Zugriffe realistisch sind. Das heißt: sie spiegeln die> wahrscheinliche tatsächliche Zugriffsfolge wieder. Jeden Cache kann man> mit der falschen Zugriffsstrategie aushebeln. Daher gibt es auch per se> kein "besser" oder "schlechter" sondern nur ein "besser in Bezug auf ...> " oder "schlechter in Bezug auf ..."
Jup, hab ich ja oben schon geschrieben.
Ich buddel das mal aus hier...
Ich bin immer noch auf der suche nach verwertbarerem Material als man
bei wikipedia.de und .com finden kann. Das ganze sollte aber für
ETechniker verständlich sein, mit dem ganzen "theoretischen Informatik
Quatsch" kann ich nicht viel Anfangen. Ist schön wenn man 5 Seiten in
einem IEEE Formatierten Dokument mit Grafiken voll wirft, statistische
Berechnungen anstellen kann und irgendwelche O's (wie Aufwändig ein
Algorithmus ist, oder?) ausrechnet. Ich brauch Fakten mit denen ich was
Anfangen kann, zum Beispiel die ich in eine Bewertungsmatrix werfen kann
die ich selbst verstehe.
Was es für Algorithmen gibt hab ich verstanden. Das die am häufigsten
Verwendeten FiFo, L/MRU, L/MFU sind auch. Das "der beste" und
"universellste" wohl der Adaptive ist, da aber IBM die Finger drauf hält
ebenfalls.
Was ich suche ist nachwievor ein Dokument das mir sagt
- Wie Aufwändig ein Algorithmus ist. Meinet wegen auch innem O
Verpackt, dann lern ich das auch noch (ist ja nicht zu schwer). Aber
halt klar Untergliedert in die Ecke "Cache -> FiFo -> O(1)"
- Wie schnell die Algorithmen im Vergleich nach einem Test sind
- Wie kann man einen selbst gebauten Cache Testen. Das Testmaterial ist
dabei ja am interessantesten. Ich hab mir hier einen Cache gebastelt,
ich find ihn nicht schlecht, simulier den Speicher in Form von Arrays
und arbeite mit Zusatzzahlen. Was passiert: Ich hab kaum
Überschneidungen, das heißt ich hab Cache-Länge+EinBisschen Hits und den
Rest der Zugriffe Misses. Das hilft mir nix zum vergleichen und mir 1000
Fälle von Hand zusammen zu schreiben sehe ich als wenig Sinnvoll ...
- Irgendwie eine Quelle die Wirklich sagt "Cache ist - LMU ist LFU ist
usw." darf auch ein Buch für 200$ sein.
Ich hoffe mir kann jemand weiter helfen...
Grüße
Danke. Race schau ich mir mal an.
Fragen die sich mir aufwerfen:
Warum ist der Vollassoziative Cache der am schwierigsten zu
implementierende? Alles kann überall stehen oder?
N-Way Set Assoziativer Cache: Ist in C doch eigentlich nur ein Array mit
einer zweiten Dimension oder? Also
1
cache[set][block];
Set und Block kann ich mir aus der realen Adresse bilden, auch das ist
korrekt? Ich frag mich nur: Wenn mein Adressbereich so doof liegt, dass
ich nicht von 0 bis CacheEnde durchiteriere - ist das dann nicht
ungünstig weil stellen leer bleiben?
Vielleicht kann mir jemand weiter helfen :) Blödes Thema irgendwie ...
Ano Nym schrieb:> Blödes Thema irgendwie ...
Nö, einer der seltenen Fälle in dem es doch eine blöde Frage ist.
Oder anders ausgedrückt, beschreibe ein konkretes Problem, dann kann man
dir auch helfen.
Caching ist ein abstraktes Konzept und keine konkrete Problemlösung.
Konkrete Fragen stehen doch da :) Blöd ist das Thema in der Tat nicht,
zumindest was den Inhalt angeht. Blöd ist es aber als Thema, die
Informationen die ich so finde wiedersprechen sich gegenseitig und sind
teilweise unglaublich oberflächlich - zumindest für mich wo ich der
Sorte Mensch angehöre die bisschen mehr Details in einem Text braucht um
daraus was zu bauen, ist einfach so.
Ok ich versuchs noch mal in ganz einfachen Sätzen:
1.) Einen Cachealgorithmus passt man einem Problem an.
2.) Verschiedene Cachealgoithmen zu vergleichen ist das gleiche Prinzip
wie bei Äpfeln und Birnen.
3.) Können Cachealgorithmen durchaus so komplex werden, dass Du sie
nicht verstehen kannst ohne entsprechendes Wissen aus Beruf und/oder
Studium.
4.) Ergo wird sie auch niemand mit bunten Bildchen erklären (wollen).
Weiß ich selbst. Dennoch gibts gewisse Grundprinzipien - oder etwa
nicht? Ich glaube jedenfalls nicht das sich Prinzipien wie "LRU" oder
"Direct Mapped Cache" je nach Anwendungsfall ändern. Direct Mapped Cache
ist Direct Mapped Cache. Ob der nun in meinem Use Case mit meinen
Requirements passt ist eine andere Geschichte.
Ano Nym schrieb:> Prinzipien wie "LRU"
Und was passt dir an:
http://de.wikipedia.org/wiki/Least_recently_used
Nicht? Da ist unter Implementierung doch beschrieben als "Textaufgabe"
wie es abläuft mit allen Details die man benötigt.
Ansonsten schnap dir ein (Lehr)Buch (z.B. Computer System - A
programmer's perspective), in genanntem Werk ab Kapitel 6.3.1 werden
Caches incl. Bilder, Text und Übungsbeispielen behandelt. Also von der
Theorie bis hin zu Praxis.
Ano Nym schrieb:> Fragen die sich mir aufwerfen:> Warum ist der Vollassoziative Cache der am schwierigsten zu> implementierende? Alles kann überall stehen oder?
Ja. Daher musst Du das Tag jeden Eintrags vergleichen. In Hardware
wird das meist mit CAMs gemacht. Deren Kosten sind bei größeren Caches
allerdings sehr hoch.
> N-Way Set Assoziativer Cache: Ist in C doch eigentlich nur ein Array mit> einer zweiten Dimension oder? Also>
1
>cache[set][block];
2
>
Zweidimensional, ja. Deine Bezeichnungen sind etwas
missverständlich. Ein N-Way Set Associative Cache ist ja nichts
anderes als N parallele Instanzen eines Direct Mapped Cache. Welchen
Grades die Assoziativität ist, wird hauptsächlich von den Kosten
begrenzt, die eine hohe Assoziativität mit sich bringt.
Wenn ein DMC aus dem Array cache[set] besteht, dann wird man den SAC
als cache[way][set] implementieren.
Um noch mal auf den ersten Punkt zurückzukommen: Ein /Fully
Associative Cache/ (FAC) ist im Grunde der Extremfall des SAC. Der
Cache Speicher besteht aus beliebig vielen ways, die jeweils nur
einen einzigen set beinhalten.
> Set und Block kann ich mir aus der realen Adresse bilden, auch das ist> korrekt?
Nein. Der way wird nicht aus der Adresse gebildet. Nur der set
(auch index) wird von der Adresse bestimmt.
--
Marcus
Gut wir meinen das selbe und nennen es unterschiedlich. In dem Artikel
den ich eben zum Thema gelesen habe wurde der Cache so beschrieben (kein
Zitat):
Ein Cache besteht aus Blöcken (=Cache Zeilen/Lines). Bei einem Set
Assoziativen Cache werden je N Blöcke (N als 2er Potenz (2 4 8 ...) zu
einem Set zusammen gefasst. Ist N=1 hat man einen Direct Mapped Cache,
hat man N=sehr groß (bzw gleich der Cache Länge) hat man einen Fully
Associative.
Richtig ist: Der Block (=die Cache Zeile/Line) im jeweiligen Weg (Set)
wird nicht aus der Adresse gebildet. Aber eben das Set oder der Weg
sowie das Tag.
Heißt: Ich hab ein Array cache[][] und eine Adresse. Aus der Adresse
bilde ich mir nun an passender Stelle meine Set Nummer und suche
innerhalb dieses das item - also quasi
1
while(suche)
2
{
3
if(cache[set][i]==tag)
4
...
5
6
i++;
7
}
Das ist von der Vorstellungskraft her etwas schwierig zu verwursten,
muss man schon sagen. Aber darum gehts ja im ersten Schritt: Die
einzelnen Versionen verstehen. Dann kann man die mit dem Use Case
verheiraten.
Ich bins wieder.
Ich überlege gerade auf welche standard Replacement Strategien ich ein
Auge werfen soll. FiFo ist klar, L/MRU auch. Random? L/MFU? Weitere?
Ich frage mich auch wie man LRU und L/MFU implementieren soll..
LRU: Least Recently Used. Tut es da nicht schon ein Flag am
entsprechenden Eintrag der sagt "ich wurde zuletzt benutzt"?
L/MFU: Least/Most Frequently Used. Tut es hier nicht eine Variable die
das Alter der Variable anzeigt? Die Tabelle wird fortlaufend gefüllt.
Jedesmal wenn ein neuer Eintrag hinzukommt oder ein anderer Eintrag
wieder benutzt wird altern alle auser dem neuen/wieder benutzten. Ist
die Tabelle voll sucht man sich den mit der höchsten Variable (also den
ältesten) raus und ersetzt ihn.
Grüße
Wenn das Forum mich bearbeiten lassen würde würd ichs tun. Hab eben noch
mal den Wiki Artikel zu LRU gelesen - der hilft in der Tat.
http://de.wikipedia.org/wiki/Least_recently_used
Damit wäre der Drops gelutscht. Bleibt LFU.
http://de.wikipedia.org/wiki/Least_frequently_used
Bei LFU
http://de.wikipedia.org/wiki/Least_frequently_used
Ist die Beschreibung doch auch besser als ich irgendwie in Erinnerung
hatte. Egal wie, ich frag mich nun wie ich den in C auf dem PC Beispiel
implementieren könnte ... ich hab da ja eine wirklichen Timer Interrupts
die ich nutzen könnte (um zu verhindern das ich Leichen im Cache hab).
Und das mit der Alterungsvariablen ist wohl eher NFU - Not Frequently
Used.
Grüße
