Wie effizient Suchen in einem Cache
-
Hallo,
ich weiß nicht ob ich hier eigentlich richtig bin aber ich frage einfach mal, da effizientes Suchen ja auch ein klassisches Software-Problem ist.
Ich möchte einen Cache durchsuchen habe aber keinen gescheiten Hash-Wert zur Verfügung. Üblicherweise sortiert man doch einen Cache nach einen Hash-Wert o.ä. um damit möglichst effizient suchen zu können. Wenn man dann pro Hash-Wert mehrere Speicherplätze vorsieht (also einen Mehr-Wege-Cache hat) kann man auch das Problem mit dem häufigen Verdrängen von unterschiedlichen Werten mit identischem Hash abmildern.
Ich habe jetzt das Problem das ich für meine Suchwerte keinen Hash ermitteln kann und bin mir nun unschlüssig wie ich einen Cache effizient durchsuchen soll, was besseres als eine simple aber zeitintensive lineare Suche fällt mir einfach nicht ein.
Mein Problem ist ganz konkret eine Art L2-Cache für einen TLB für variable Page-Größen. Der TLB ist ein voll-assoziativer Cache, dort werden bei jeder Suchanfrage immer alle Plätze gleichzeitig durchsucht was natürlich sehr viel Logik erfordert weil ja jeder TLB-Platz einen eigenen "Vergleicher" hat. Man versucht also den TLB möglichst klein zu halten um möglichst wenig Transistoren dafür zu brauchen und gleichzeitig möglichst groß zu machen damit er möglichst effektiv ist. Der TLB selber kommt auch sehr gut mit variablen Page-Größen zurecht da der Vergleicher immer nur die Bits vergleicht die tatsächlich umgesetzt werden sollen (bei einer 4 kB-Page wären das also die Bits 31:12, bei einer 64 kB-Page die Bits 31:16 und bei einer 1 MB-Page die Bits 31:20). Da man den TLB aber aufgrund der enormen "Kosten" nicht beliebig groß machen kann möchte ich eine Art L2-Cache hinter den TLB schalten der die seltener benutzen Umsetzungs-Werte aufnimmt. Dieser Cache soll natürlich nicht voll-assoziativ sein, da die Page-Größen aber variabel sind (also jede beliebige Zweier-Potenz haben dürfen) kann ich nicht einfach bestimmte Bits als Cache-Index benutzen.
Außer dummes lineares Suchen fällt mir keine machbare Lösung meines Problems ein.
Kennen da die SW-Profis was besseres? Hat irgendwer eine gute Idee?
Ich bin für jede Anregung dankbar!Wenn ich es in SW implementieren müsste würde ich wohl versuchen das in einen Binär-Baum zu packen (bei Bit 31 angefangen) aber sowas kann man leider schlecht in Hardware implementieren.
Grüße
ErikPS: Wie schon geschrieben, ich bin mir nicht sicher ob meine Frage in diesem Forum überhaupt richtig ist. Wenn nein dann bitte einfach löschen.
-
erik.vikinger schrieb:
Ich möchte einen Cache durchsuchen habe aber keinen gescheiten Hash-Wert zur Verfügung. Üblicherweise sortiert man doch einen Cache nach einen Hash-Wert o.ä. um damit möglichst effizient suchen zu können.
Nein, eigentlich sortiert man nicht. Entweder etwas ist an der addresse (vom hash) oder nicht.
Ich habe jetzt das Problem das ich für meine Suchwerte keinen Hash ermitteln kann und bin mir nun unschlüssig wie ich einen Cache effizient durchsuchen soll, was besseres als eine simple aber zeitintensive lineare Suche fällt mir einfach nicht ein.
wieso solltest du keine addresse ermitteln koennen?
Mein Problem ist ganz konkret eine Art L2-Cache für einen TLB für variable Page-Größen. Der TLB ist ein voll-assoziativer Cache, dort werden bei jeder Suchanfrage immer alle Plätze gleichzeitig durchsucht was natürlich sehr viel Logik erfordert weil ja jeder TLB-Platz einen eigenen "Vergleicher" hat. Man versucht also den TLB möglichst klein zu halten um möglichst wenig Transistoren dafür zu brauchen und gleichzeitig möglichst groß zu machen damit er möglichst effektiv ist. Der TLB selber kommt auch sehr gut mit variablen Page-Größen zurecht da der Vergleicher immer nur die Bits vergleicht die tatsächlich umgesetzt werden sollen (bei einer 4 kB-Page wären das also die Bits 31:12, bei einer 64 kB-Page die Bits 31:16 und bei einer 1 MB-Page die Bits 31:20). Da man den TLB aber aufgrund der enormen "Kosten" nicht beliebig groß machen kann möchte ich eine Art L2-Cache hinter den TLB schalten der die seltener benutzen Umsetzungs-Werte aufnimmt. Dieser Cache soll natürlich nicht voll-assoziativ sein, da die Page-Größen aber variabel sind (also jede beliebige Zweier-Potenz haben dürfen) kann ich nicht einfach bestimmte Bits als Cache-Index benutzen.
natuerlich kannst du das. CPUs lesen auch variable groessen und fangen das mit caches auf. Es kommt garnicht auf die menge der daten an die hinter einer adresse sind, sondern einzig und allein auf die addresse.
-
Hallo,
rapso schrieb:
Nein, eigentlich sortiert man nicht. Entweder etwas ist an der addresse (vom hash) oder nicht.
Okay, man bildet vom Wert (der als Tag mit in den Cache soll) einen Hash um zu bestimmen an welche Stelle alles in den Cache soll. Damit ist der Cache quasi "Sortiert nach Hash". Für normale Daten-Caches nimmt man keine Hash-Funktionen sondern direkt ein paar Bits der Adresse.
rapso schrieb:
Ich habe jetzt das Problem das ich für meine Suchwerte keinen Hash ermitteln kann und bin mir nun unschlüssig wie ich einen Cache effizient durchsuchen soll, was besseres als eine simple aber zeitintensive lineare Suche fällt mir einfach nicht ein.
wieso solltest du keine addresse ermitteln koennen?
Ich kann keinen Hash für die virtuelle Adresse ermitteln weil ich vor dem Suchen nicht weiß wie viele Bits den umgesetzt werden müssen, diese Info hab ich erst nachdem der passende Umsetzungs-Eintrag gefunden wurde und damit die Page-Größe (von der Page in welche die virtuelle Adresse gehört welche zum Suchen benutzt werden muss) fest steht. Falls nichts gefunden wird gibt es eine teure TLB-Miss-Exception und das OS muss dann die Page-Tables durchsuchen, das soll natürlich möglichst selten passieren.
rapso schrieb:
natuerlich kannst du das. CPUs lesen auch variable groessen und fangen das mit caches auf. Es kommt garnicht auf die menge der daten an die hinter einer adresse sind, sondern einzig und allein auf die addresse.
Ich will keine Daten sondern Adressen, eigentlich die Umsetzungs-Werte von virtuell nach physisch, cachen. Der virtuellen Adresse sehe ich aber nicht die Page-Größe an also weiß ich vor dem Suchen nicht wie viele Bits der virtuellen Adresse eigentlich zum Suchen benutzt werden müssen/können.
Grüße
Erik
-
erik.vikinger schrieb:
Hallo,
rapso schrieb:
Nein, eigentlich sortiert man nicht. Entweder etwas ist an der addresse (vom hash) oder nicht.
Okay, man bildet vom Wert (der als Tag mit in den Cache soll) einen Hash um zu bestimmen an welche Stelle alles in den Cache soll. Damit ist der Cache quasi "Sortiert nach Hash". Für normale Daten-Caches nimmt man keine Hash-Funktionen sondern direkt ein paar Bits der Adresse.
der hash ist die addresse und man indiziert in der hashmap indem man hash modulo der hashmap size rechnet. "unterste bit nehmen" ist das modulo. das ist der grund weshalb man hashmaps eigentlich nicht resizen kann, weil die hashes willkuerlich verstreut sind und mit der veraenderung der groesse der hashtable komplett andere positionen fuer die hashes vergeben werden wuerden. (man kann natuerlich resizen wenn man den hash mit ablegt bzw wiederberechnen kann).
rapso schrieb:
Ich habe jetzt das Problem das ich für meine Suchwerte keinen Hash ermitteln kann und bin mir nun unschlüssig wie ich einen Cache effizient durchsuchen soll, was besseres als eine simple aber zeitintensive lineare Suche fällt mir einfach nicht ein.
wieso solltest du keine addresse ermitteln koennen?
Ich kann keinen Hash für die virtuelle Adresse ermitteln weil ich vor dem Suchen nicht weiß wie viele Bits den umgesetzt werden müssen, diese Info hab ich erst nachdem der passende Umsetzungs-Eintrag gefunden wurde und damit die Page-Größe (von der Page in welche die virtuelle Adresse gehört welche zum Suchen benutzt werden muss) fest steht. Falls nichts gefunden wird gibt es eine teure TLB-Miss-Exception und das OS muss dann die Page-Tables durchsuchen, das soll natürlich möglichst selten passieren.
dein problem ist also dass du die startaddresse der page nicht kennst. in dem fall hatte ich mal fuer einen memory manager in die obersten bits die page groesse abgelegt. (ich hatte 2 bits benutzt weil die hardware eh nur 4 moegliche pagegroessen kannte). das limitiert natuerlich die range, aber mein system hatte eh weit weniger als 512mb.
falls du mit dem zerhackselten page ranges nicht hinkommst, hast du im worst case halt cache misses, das system an sich koennte dennoch funktionieren.rapso schrieb:
natuerlich kannst du das. CPUs lesen auch variable groessen und fangen das mit caches auf. Es kommt garnicht auf die menge der daten an die hinter einer adresse sind, sondern einzig und allein auf die addresse.
Ich will keine Daten sondern Adressen, eigentlich die Umsetzungs-Werte von virtuell nach physisch, cachen. Der virtuellen Adresse sehe ich aber nicht die Page-Größe an also weiß ich vor dem Suchen nicht wie viele Bits der virtuellen Adresse eigentlich zum Suchen benutzt werden müssen/können.
da du es in hardware machst (und ich denke du hast nicht uebermaessig viele page groessen), berechne mehrere hashes, einen pro moegliche groesse (zum einen kann man das sicherlich gut pipelinen in hardware, zum anderen ist das sicherlich immer noch viel fixer als ein miss).
Im L2 musst du dann ja eh die die base address und page size ablegen, sodass du validieren kannst, ob das wirklich ein cachehit war.
-
Wie raps(o?) schon geschrieben hat (wenn ich ihn richtig verstehe): speichere den Eintrag im Cache einfach mit dem "richtigen" Hash, und such ihn dann mit allen möglichen Hashes.
Dabei kannst du z.B. mit der Page-Grösse anfangen, mit der zuletzt ein Treffer erziehlt wurde. Oder du schreibst ne Statistik mit, anhand derer du die Reihenfolge bestimmen kannst.
Wobei es denke ich in jedem Fall günstig wäre, die Anzahl der möglichen Page-Grössen zu limitieren. Unabhängig davon wie du den Cache dann letztendlich aufbaust.
IMO braucht man auch nicht viele. Jeweils Faktor 16 zwischen möglichen Grössen halte ich für keine arge Einschränkung. Und kleinste Grösse 4K, grösste 16M sollte auch ausreichen. Das wären dann 4 mögliche Grössen und damit 4 mögliche Hashes. Nicht so schlimm denke ich.Falls es aus Kompatibilitätsgründen nicht möglich sein sollte das zu machen (alter Code muss noch laufen), könnte man zumindest den Cache auf diese 4 Page Grössen optimieren. Entweder überhaupt nur Einträge mit diesen Grössen im Cache speichern (alles andere ist dann eben immer ein Miss), oder zumindest diese Grössen immer als erste probieren.
In dem Fall laufen dann Applikationen/OSe schnell, die sich auf diese 4 Grössen beschränken. Alles andere läuft aber auch noch, d.h. Kompatibilität ist gewährleistet, wenn auch nicht mit max. Performance.
-
Hallo,
raps schrieb:
.... (man kann natuerlich resizen wenn man den hash mit ablegt bzw wiederberechnen kann).
Ein Hardware-Cache hat (üblicherweise) eine feste Größe, resizen ist also uninteressant. Aber trotzdem Danke für diesen Hinweis, diese Einschränkung war mir noch gar nicht so bewusst.
raps schrieb:
dein problem ist also dass du die startaddresse der page nicht kennst.
genau
raps schrieb:
in dem fall hatte ich mal fuer einen memory manager in die obersten bits die page groesse abgelegt.
Das bedeutet aber das wenn das OS zur Laufzeit kleine Pages zu einer größeren Page zusammenfassen will, oder auch umgedreht, das dann die Daten ihre virtuelle Adresse ändern müssten. Das stelle ich mir quasi unmöglich vor. Außerdem reduziert sich damit der nutzbare virtuelle Adressraum. Wimre kann der Itanium auch mit beliebigen (zumindest vielen) Page-Größen umgehen aber man muss ihm wohl sagen welche Page-Größe in welchen virtuellem Adressbereich ist damit er den Hash zum Suchen im VHPT passend berechnen kann. Diese Einschränkung möchte ich nicht, es geht mir darum immer und überall eine möglichst große Page-Größe nutzen zu können um die Effizienz des TLB möglichst hoch zu halten.
raps schrieb:
da du es in hardware machst (und ich denke du hast nicht uebermaessig viele page groessen), berechne mehrere hashes, einen pro moegliche groesse (zum einen kann man das sicherlich gut pipelinen in hardware, zum anderen ist das sicherlich immer noch viel fixer als ein miss).
An Page-Größen wollte ich eigentlich von 4 kByte bis mindestens 128 MByte alle Zweierpotenzen haben. Wenn ich mich auf jede zweite Zweierpotenz im Bereich von 4k bis 64M beschränke dann sind es 8 Hashes zum sequentiell nach schauen (also 2 bis 10 Takte), ich denke das ist ein akzeptabler Kompromiss. Mehr Page-Größen verlängern nur die maximale Latenz, ändern aber nichts am Prinzip.
raps schrieb:
Im L2 musst du dann ja eh die die base address und page size ablegen, sodass du validieren kannst, ob das wirklich ein cachehit war.
Fest zu stellen ob ein Hit oder Miss vorliegt ist klar, es geht mir darum möglichst effizient zu suchen. Beim MicroBlaze z.B. wird die Latenz des L2-TLB (heißt dort UTLB) mit 2 bis 32 Takten angegeben was bei 64 unsortierten/ungeordneten Einträgen nach einer primitiven linearen Suche mit 2 Prüfungen pro Takt aussieht. Genau sowas langsames wollte ich vermeiden. Vor allem möchte ich die Latenz nicht von der Größe abhängig machen.
hustbaer schrieb:
Dabei kannst du z.B. mit der Page-Grösse anfangen, mit der zuletzt ein Treffer erziehlt wurde.
Das könnte, im Durchschnitt, bestimmt noch was bringen. Sollte sich auch einfach implementieren lassen, eventuell sogar für Code und Daten getrennt.
hustbaer schrieb:
Oder du schreibst ne Statistik mit, anhand derer du die Reihenfolge bestimmen kannst.
Das klingt schon recht kompliziert, aber auch ziemlich verlockend. Da müsste man mal schauen wie schwer die Latenz des TLB-L2-Cache wirklich wiegt, wenn die Page-Größen immer möglichst hoch sind dann sollte der normale TLB schon eine hohe Effizienz erreichen und damit die L2-Latenz weniger/seltener zum Problem werden.
hustbaer schrieb:
Wobei es denke ich in günstig Fällen wäre, die Anzahl der möglichen Page-Grössen zu limitieren.
Das möchte ich nicht, es wäre mir schon recht wenn das OS da mit möglichst feiner Granularität ran gehen kann.
Grüße
Erik
-
erik.vikinger schrieb:
hustbaer schrieb:
Wobei es denke ich in günstig Fällen wäre, die Anzahl der möglichen Page-Grössen zu limitieren.
ROFL
Da sieht man mal was rauskommt, wenn man einen Satz zu oft editiert, dann mitten drin an was anderes denkt, dann ganz drauf vergisst, und nicht nochmal drüberliest
(Hab's in meinem Beitrag korrigiert)erik.vikinger schrieb:
hustbaer schrieb:
Oder du schreibst ne Statistik mit, anhand derer du die Reihenfolge bestimmen kannst.
Das klingt schon recht kompliziert, aber auch ziemlich verlockend. Da müsste man mal schauen wie schwer die Latenz des TLB-L2-Cache wirklich wiegt, wenn die Page-Größen immer möglichst hoch sind dann sollte der normale TLB schon eine hohe Effizienz erreichen und damit die L2-Latenz weniger/seltener zum Problem werden.
Naja, rein das Mitzählen sollte ja einfach sein, oder?
Und dann könnte man z.B. alle 100 oder 1000 oder 10000 Zugriffe hergehen, und daraus eine Reihenfolge errechnen, die dann für die nächsten 100/1000/10000 Zugriffe verwendet wird. usw.
Dieser Vorgang kann dann ja ruhig etwas länger dauern, da er viel seltener ausgeführt wird. Das Resultat steckt man dann in irgendwelche Register/Puffer, direkt in der Form, wie man es braucht. Also inklusive Shift-Werte, Masken etc., so dass man in dem Teil der dann letztendlich die Suche ausführt nicht (oder nur wenig) mehr Logik/Gatter/... braucht, als wenn es fest verdrahtet wäre.Zusätzlich könnte der Vorgang ja nach dem "triggernden" Request ablaufen, so dass man mit etwas glück gar keine zusätzliche Latenz dadurch bekommt. Nämlich dann wenn der nächste Request lange genug auf sich warten lässt.
Wobei ich zugeben muss, dass ich von Hardware-Design nicht viel Ahnung habe, und daher auch nicht gut abschätzen kann, wie aufwendig das wirklich zu implementieren wäre.
-
Wobei... je länger ich darüber nachdenke...
Es könnte sogar sein, dass das kontraproduktiv wäre.1st Level Misses werden ja vermutlich umso seltener vorkommen, je grösser die Page ist. Von daher könnte es vollkommen ausreichend sein, von klein nach gross zu suchen.
Kommt natürlich ganz auf die Applikation und das OS an.
Wenn du passende Daten hast, könntest du es ja auch einfach mal durchsimulieren. Also einfach ne Liste von Adressen wie sie von einem realen OS mit realen Anwendungen angefragt werden. Dann wären das ein paar hundert Zeilen in deiner bevorzugten Programmiersprache, und du wüsstest, ob die Optimierung was bringt oder nicht.
-
hustbaer schrieb:
Und dann könnte man z.B. alle 100 oder 1000 oder 10000 Zugriffe hergehen, und daraus eine Reihenfolge errechnen, die dann für die nächsten 100/1000/10000 Zugriffe verwendet wird. usw.
Eine Move-To-Front-Liste braucht höchstens doppelt so viele Zugriffe, als jede beliebige statische Anordnung.
-
erik.vikinger schrieb:
Dieser Cache soll natürlich nicht voll-assoziativ sein, da die Page-Größen aber variabel sind (also jede beliebige Zweier-Potenz haben dürfen) kann ich nicht einfach bestimmte Bits als Cache-Index benutzen.
Wieso? Sind Pages nicht alle gleich groß? Wenn ein Register existiert, das die Große alle Pages verrät, kannste die dummen Bits schnell damit ausmaskieren.
-
Hallo,
hustbaer schrieb:
Wobei... je länger ich darüber nachdenke...
Es könnte sogar sein, dass das kontraproduktiv wäre.Deine Idee klingt zwar gut, und sollte auch mit vertretbarem Aufwand umsetzbar sein, aber es könnte tatsächlich sein das jeder Versuch da was zu optimieren eher kontraproduktiv ist bzw. der Nutzen so klein bleibt das dieser den Logik-Verbrauch einfach nicht rechtfertigt.
hustbaer schrieb:
1st Level Misses werden ja vermutlich umso seltener vorkommen, je grösser die Page ist.
Das ist zu hoffen, deshalb mach ich das ganze ja.
hustbaer schrieb:
Von daher könnte es vollkommen ausreichend sein, von klein nach gross zu suchen.
Vor allem wenn das OS viele verschiedene Page-Größen nutzt dann ist es eher unwahrscheinlich dass das User-Mode-Programm immer in gleich großen Pages liegt. Je nach Situation kann da sicher ein ziemliches durcheinander an unterschiedlichen Page-Größen sein. Irgendeine Vorhersage-Logik wird da mit hoher Wahrscheinlichkeit nicht besser sein als Raten oder eben einfach von "klein nach groß". Ich denke für einen echten Nutzwert muss diese Vorhersage-Logik schon richtig was können und dafür natürlich auch einiges an Logik verbrauchen, da ist es vermutlich einfacher und effektiver den TLB um ein paar Einträge zu vergrößern damit der L2-Cache einfach nicht so oft benötigt wird und damit das Problem seiner Latenz abnimmt.
Ich denke das ich als erstes den einfachsten Weg gehe und dann vielleicht mal schaue wie hoch die durchschnittliche L2-Latenz und die TLB-Miss-Quote tatsächlich sind. Dann kann ich immer noch an verschiedenen Parametern drehen und schauen an welcher Stelle ich mit welchem Logik-Verbrauch wie viel verbessern kann.
hustbaer schrieb:
Wenn du passende Daten hast, könntest du es ja auch einfach mal durchsimulieren.
Ich programmiere einen Simulator für die CPU aber der simuliert nicht den TLB exakt nach. Für welche Pages ein TLB-Miss auftritt, nur das sieht ja der L2-Cache, hängt ganz wesentlich von der Ersetzungsstrategie im TLB ab. Als Ersetzungsstrategie wollte ich eine Art Zufall unter Ausschluss der letzten 3 Hits nehmen. Ein richtiger LRU-Algorithmus ist von der Anzahl der Elemente (hier die TLB-Plätze) abhängig und da wollte ich auch gerne flexibel bleiben, nebst dessen das richtiges LRU mit mehr als 5 Elementen (ich möchte mindestens 8 für Code und mindestens 12 für Daten) dann ziemlich bis extrem aufwändig wird oder viel Logik verbraucht.
volkard schrieb:
Eine Move-To-Front-Liste braucht höchstens doppelt so viele Zugriffe, als jede beliebige statische Anordnung.
Ein dynamische Liste braucht vor allem Speicher, eine konstante Liste kann dagegen recht gut klein-optimiert werden.
volkard schrieb:
[Wieso? Sind Pages nicht alle gleich groß?
Nein, auf den meisten modernen CPUs erlaubt man viele verschiedene Page-Größen. Das man damit die TLB-Effizienz steigern kann ist schließlich kein Geheimnis mehr.
Auf x86 soll die Benutzung der 4 MB-Pages anstatt der 4 kB-Pages, je nach Programm, einige Prozent mehr Gesamt-Performance gebracht haben. Eine effiziente Umsetzung der virtuellen Adressen in physische Adressen ist also von hoher Wichtigkeit. Die beliebten Prefetch-Befehle haben nicht nur den Vorteil das damit demnächst benötigte Daten schon im Cache stehen sondern das dann auch bereits ein Umsetzung-Eintrag (dessen Ermittlung ja manchmal ein aufwendiger Page-Table-Walk vorausgeht) im TLB bereit liegt.Grüße
Erik
