#lost · 2013-06-08
104 Nachrichten · Seite 1 von 1 · Original-CSV herunterladen
- mromanMoin.
- mromanGibt es eine effiziente Methode Lookups zu machen anhand einer Ober- und Untergrenze?
- mgottschlagja.
- mromanMein Insertkey ist lower_bound, upper_bound
- mromanund mein Lookup key ist halt eine Nummer.
- mromanbinary trees?
- mromanmit start, end
- mromanaber ich vermute das geht sicher noch kleverer.
- mgottschlageine Möglichkeit, die mir in den Sinn kommt, wäre ein BVH
- mgottschlagmit einem "normalen" sortierten Binärbaum dürfte es nicht so effektiv gehen
- mgottschlagBVH = die Intervalle liegen nur in den Blättern, in höheren Baumebenen liegen dann die Intervalle, die alle Kindknoten enthalten
- mgottschlagBVH = bounded volume hierarchy
- mgottschlagwobei bei dir natürlich die Information fehlt, ob die Intervalle sich überlappen
- mromanIch koennte es O(1) machen
- mromanaber das kostet dann viele Megabytes :)
- mromanhm
- mroman2 MB um genau zu sein.
- mgottschlagwenn das Problem sich in O(1) lösen lässt, dann hast du mit ziemlicher Sicherheit noch irgendetwas wichtiges nicht erzählt :p
- mromanmgottschlag: Es sind Adresslookups
- mromanaligned
- mromandaher koennte man einfach die oberen Bits als Arrayindex benutzen
- mgottschlagwas für lookups?
- mgottschlagund was hast du eigentlich vor?
- mromanmoment
- mromanhttps://bitbucket.org/mroman_/emulathor/src/79a430ee334e63d618d87c67037c0226a6eef004/src/memory.c?at=master#cl-122
- mroman^- das ist die Funktion die schaut, ob Zeugs im cache ist oder nicht.
- mromanund cache lines sind 64B aligned
- mromandaher koennte man fuer 128MB
- mromanein 2MB grosses Array benutzen
- mgottschlagwas für ein Cache ist das? direct mapped, n-fach assoziativ, oder...?
- mromanEr hat 16 Cache-Lines, eine Cache-Line enthaelt die Daten ab cache_start bis cache_start + cache_line_size
- mromanich koennte die Adresse um 6 nach links shiften und dann als Index benutzen
- mgottschlagokay, das klingt schonmal recht vollassoziativ
- mgottschlagdas... wiederum nicht.
- mromanreturn c[addr >> 6u];
- mromandas waere dann die Cache-Line in der addr ist.
- mgottschlaginsofern, schau dir mal die verschiedenen Cachetypen an, damit zu zumindest formal genau sagen kannst, was du da baust
- mromanDer Hauptseicher ist unterteilt in 64B Bloecke
- mromanund eine Cache-Line enthaelt genau einen Block
- mromand.h die Adresse um 6 nach links geshiftet gibt dir den Block index.
- mromaneh
- mromannach rechts
- mgottschlaghttps://de.wikipedia.org/wiki/Cache#Organisation <- les es dir mal durch. Es macht keinen Sinn, Cache emulieren zu wollen, wenn du nicht weißt, was es überhaupt für Cachetypen gibt
- mgottschlagin jedem Fall lässt sich ein Lookup übrigens in erwartet O(1) implementieren, auch mit wesentlich weniger Speicheraufwand als 2MB
- mromanvollassoziativ
- mromanwenn ich das richtig verstehe.
- mromanin einem Cacheblock steckt genau immer ein Speicherblock
- mromanwobei ein Speicherblock in einem beliebigen Cacheblock sein kann
- mgottschlagdann nimm z.B. eine Hashtable, die zum Tag einer Adresse die Cachezeile sucht
- mromandas ginge ja
- mgottschlag(in der CPU ist das durch n parallele Vergleicher realisiert, das wäre O(n), wenn du es direkt umsetzen würdest)
- mromander Key ist dann einfach (addr >> 6)
- mromander code fuer ensure_cache stammt noch aus der Zeit, als kein Alignment erforderlich war :)
- mromanaber ja
- mromanmit alignment geht das natuerlich so
- mromanok. danke fuer deinen Input.
- mgottschlagübrigens wird vollassoziativer Cache eigentlich nur für L1-Cache oder die TLB benutzt, und auch L1 ist in den allermeisten Fällen eher 8fach-assoziativ
- mromanIm Auftrag wird nur ein Cache gewuenscht
- mromanalso nicht mehrer Caches :)
- mromanzumindest im inoffiziellen Auftrag.
- mromandie Sache ist noch nicht voll offiziell :)
- mgottschlagdie Aussage war auch eher "vollassoziativ ist unüblich"
- mromannun
- mromandirect mapping?
- mromandas liest sich zumindest sehr effizient.
- mgottschlag"cat /sys/devices/system/cpu/cpu*/cache/index*/ways_of_associativity"
- mromanmit Nachteilen jedoch
- mgottschlagwie WP schreibt, ist das immer ein Tradeoff zwischen einfacher Realisierbarkeit (DM) und niedriger Miss-Rate (VA)
- mgottschlagdieser i5 hat 8fach-assoziativen L1-Cache, 8-fach assoziativen L2-Cache und 12-fach assoziativen L3-Cache
- mromanwofuer steht die 8?
- mromanah
- mromanok
- mroman32 Saetze
- mromanmoment.
- mgottschlag32 Saetze?
- mromanneh
- mromankommt natuerlich auf die Groesse an
- mromanspaetestens beim tlb muss ich mir eh etwas einfalles lassen
- mromanmem_translate_address und mem_ensure_cache sind die bottlenecks schlechthin.
- mgottschlagwarum emulierst du überhaupt caches?
- mromanZwecks Demonstration.
- mromander Emulator ist kein Virtualisierer.
- mromansondern ein Demonstrationstool.
- mromanich meine
- mromancache zu emulieren bremst sowas von aus.
- mromanmgottschlag: Wunsch des Auftraggebers
- mgottschlagder "Auftraggeber" ist eine Schule, oder?
- mgottschlagweil sonst eigentlich niemand so seltsame Requirements stellen würde :p
- mromanJa :)
- mromanim Grunde ist es ja ein visualisierungs Tool
- mgottschlagCaches emulieren macht eigentlich nur im Rahmen von entweder Timinganalyse oder Performanceanalyse (Hit/Miss-Verhältnis) Sinn
- mromandu siehst spaeter dann quasi wie eine Flashanimation was abgeht
- mromanmit aufleuchtenden Linien wenn Daten in den Cache geschoben werden und so
- mromanund roten Lampen wenn es einen Cache Miss gibt etc. etc.
- mromanalso im Endeffekt ist da null performance
- mromanaber ich will diese Oberflaeche optional machen
- mromandamit der Emulator trotzdem einigermassen performant ist, wenn man das life tracking nicht will :)
- mromanohne MMU im Moment etwa 13 MIPS.
- mromander 13bit Prototyp ohne Cache etc. war min. 12 mal schneller
- mromanwenn du mir gestattest MIPS zu vergleichen
- mromanwas immer etwas problematisch ist.
- mromanmgottschlag: Um praezis zu sein: Der Arbeitgeber bin ich, aber die Schule hat Interesse daran, es als Projektarbeit anzunehmen ;)
- mromanum es spaeter im Unterricht einzusetzen.
- mromanund dann waere die Schule der Arbeitgeber, ja .