mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik Beispiel Implementierungen/Pseudocode verschiedener Cache Algorithmen


Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Volker Zabe (vza)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ..."

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Drei hätte ich noch
LIRS:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=...

RACE:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=...
(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

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
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 ...

Autor: Jan S. (jan_s)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Jan S. (jan_s)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
>
> cache[set][block];
> 

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

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
while(suche)
{
 if(cache[set][i] == tag)
 ...

i++;
}

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.

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Ano Nym (oorim)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.