#lost · 2013-06-08

104 Nachrichten · Seite 1 von 1 · Original-CSV herunterladen

  1. mromanMoin.
  2. mromanGibt es eine effiziente Methode Lookups zu machen anhand einer Ober- und Untergrenze?
  3. mgottschlagja.
  4. mromanMein Insertkey ist lower_bound, upper_bound
  5. mromanund mein Lookup key ist halt eine Nummer.
  6. mromanbinary trees?
  7. mromanmit start, end
  8. mromanaber ich vermute das geht sicher noch kleverer.
  9. mgottschlageine Möglichkeit, die mir in den Sinn kommt, wäre ein BVH
  10. mgottschlagmit einem "normalen" sortierten Binärbaum dürfte es nicht so effektiv gehen
  11. mgottschlagBVH = die Intervalle liegen nur in den Blättern, in höheren Baumebenen liegen dann die Intervalle, die alle Kindknoten enthalten
  12. mgottschlagBVH = bounded volume hierarchy
  13. mgottschlagwobei bei dir natürlich die Information fehlt, ob die Intervalle sich überlappen
  14. mromanIch koennte es O(1) machen
  15. mromanaber das kostet dann viele Megabytes :)
  16. mromanhm
  17. mroman2 MB um genau zu sein.
  18. mgottschlagwenn das Problem sich in O(1) lösen lässt, dann hast du mit ziemlicher Sicherheit noch irgendetwas wichtiges nicht erzählt :p
  19. mromanmgottschlag: Es sind Adresslookups
  20. mromanaligned
  21. mromandaher koennte man einfach die oberen Bits als Arrayindex benutzen
  22. mgottschlagwas für lookups?
  23. mgottschlagund was hast du eigentlich vor?
  24. mromanmoment
  25. mromanhttps://bitbucket.org/mroman_/emulathor/src/79a430ee334e63d618d87c67037c0226a6eef004/src/memory.c?at=master#cl-122
  26. mroman^- das ist die Funktion die schaut, ob Zeugs im cache ist oder nicht.
  27. mromanund cache lines sind 64B aligned
  28. mromandaher koennte man fuer 128MB
  29. mromanein 2MB grosses Array benutzen
  30. mgottschlagwas für ein Cache ist das? direct mapped, n-fach assoziativ, oder...?
  31. mromanEr hat 16 Cache-Lines, eine Cache-Line enthaelt die Daten ab cache_start bis cache_start + cache_line_size
  32. mromanich koennte die Adresse um 6 nach links shiften und dann als Index benutzen
  33. mgottschlagokay, das klingt schonmal recht vollassoziativ
  34. mgottschlagdas... wiederum nicht.
  35. mromanreturn c[addr >> 6u];
  36. mromandas waere dann die Cache-Line in der addr ist.
  37. mgottschlaginsofern, schau dir mal die verschiedenen Cachetypen an, damit zu zumindest formal genau sagen kannst, was du da baust
  38. mromanDer Hauptseicher ist unterteilt in 64B Bloecke
  39. mromanund eine Cache-Line enthaelt genau einen Block
  40. mromand.h die Adresse um 6 nach links geshiftet gibt dir den Block index.
  41. mromaneh
  42. mromannach rechts
  43. 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
  44. mgottschlagin jedem Fall lässt sich ein Lookup übrigens in erwartet O(1) implementieren, auch mit wesentlich weniger Speicheraufwand als 2MB
  45. mromanvollassoziativ
  46. mromanwenn ich das richtig verstehe.
  47. mromanin einem Cacheblock steckt genau immer ein Speicherblock
  48. mromanwobei ein Speicherblock in einem beliebigen Cacheblock sein kann
  49. mgottschlagdann nimm z.B. eine Hashtable, die zum Tag einer Adresse die Cachezeile sucht
  50. mromandas ginge ja
  51. mgottschlag(in der CPU ist das durch n parallele Vergleicher realisiert, das wäre O(n), wenn du es direkt umsetzen würdest)
  52. mromander Key ist dann einfach (addr >> 6)
  53. mromander code fuer ensure_cache stammt noch aus der Zeit, als kein Alignment erforderlich war :)
  54. mromanaber ja
  55. mromanmit alignment geht das natuerlich so
  56. mromanok. danke fuer deinen Input.
  57. 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
  58. mromanIm Auftrag wird nur ein Cache gewuenscht
  59. mromanalso nicht mehrer Caches :)
  60. mromanzumindest im inoffiziellen Auftrag.
  61. mromandie Sache ist noch nicht voll offiziell :)
  62. mgottschlagdie Aussage war auch eher "vollassoziativ ist unüblich"
  63. mromannun
  64. mromandirect mapping?
  65. mromandas liest sich zumindest sehr effizient.
  66. mgottschlag"cat /sys/devices/system/cpu/cpu*/cache/index*/ways_of_associativity"
  67. mromanmit Nachteilen jedoch
  68. mgottschlagwie WP schreibt, ist das immer ein Tradeoff zwischen einfacher Realisierbarkeit (DM) und niedriger Miss-Rate (VA)
  69. mgottschlagdieser i5 hat 8fach-assoziativen L1-Cache, 8-fach assoziativen L2-Cache und 12-fach assoziativen L3-Cache
  70. mromanwofuer steht die 8?
  71. mromanah
  72. mromanok
  73. mroman32 Saetze
  74. mromanmoment.
  75. mgottschlag32 Saetze?
  76. mromanneh
  77. mromankommt natuerlich auf die Groesse an
  78. mromanspaetestens beim tlb muss ich mir eh etwas einfalles lassen
  79. mromanmem_translate_address und mem_ensure_cache sind die bottlenecks schlechthin.
  80. mgottschlagwarum emulierst du überhaupt caches?
  81. mromanZwecks Demonstration.
  82. mromander Emulator ist kein Virtualisierer.
  83. mromansondern ein Demonstrationstool.
  84. mromanich meine
  85. mromancache zu emulieren bremst sowas von aus.
  86. mromanmgottschlag: Wunsch des Auftraggebers
  87. mgottschlagder "Auftraggeber" ist eine Schule, oder?
  88. mgottschlagweil sonst eigentlich niemand so seltsame Requirements stellen würde :p
  89. mromanJa :)
  90. mromanim Grunde ist es ja ein visualisierungs Tool
  91. mgottschlagCaches emulieren macht eigentlich nur im Rahmen von entweder Timinganalyse oder Performanceanalyse (Hit/Miss-Verhältnis) Sinn
  92. mromandu siehst spaeter dann quasi wie eine Flashanimation was abgeht
  93. mromanmit aufleuchtenden Linien wenn Daten in den Cache geschoben werden und so
  94. mromanund roten Lampen wenn es einen Cache Miss gibt etc. etc.
  95. mromanalso im Endeffekt ist da null performance
  96. mromanaber ich will diese Oberflaeche optional machen
  97. mromandamit der Emulator trotzdem einigermassen performant ist, wenn man das life tracking nicht will :)
  98. mromanohne MMU im Moment etwa 13 MIPS.
  99. mromander 13bit Prototyp ohne Cache etc. war min. 12 mal schneller
  100. mromanwenn du mir gestattest MIPS zu vergleichen
  101. mromanwas immer etwas problematisch ist.
  102. mromanmgottschlag: Um praezis zu sein: Der Arbeitgeber bin ich, aber die Schule hat Interesse daran, es als Projektarbeit anzunehmen ;)
  103. mromanum es spaeter im Unterricht einzusetzen.
  104. mromanund dann waere die Schule der Arbeitgeber, ja .