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
Drei hätte ich noch LIRS: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.116.2184&rep=rep1&type=pdf RACE: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.5192&rep=rep1&type=pdf (z.T. besser als AMP und Konsorten (Vergleich mit AMP, LIRS, PCC, LRU unter verschiedenen Bedingungen ist im Paper)) PCC: http://people.cs.vt.edu/butta/docs/osdi04_pcc.pdf
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
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.