Die Peano-Kurve für Dünngitterhierarchisierung mit raumfüllenden Kurven

Abstract

Übliche Gitteransätze zur Diskretisierung von Räumen leiden an einem exponentiellen Anstieg der Anzahl Freiheitsgrade mit der Dimensionszahl und sind deshalb nicht für höherdimensionale Probleme geeignet. Einen Ausweg bieten dünne Gitter, die deutlich weniger Freiheitsgrade benötigen. Allerdings ist die Struktur der dünnen Gitter komplexer, was praktisch zu Problemen der Cache-Ausnutzung führt: bei der Dünngittertraversierung können viele Speicherzugriffe nicht aus Cache-Speichern bedient werden. In dieser Arbeit werden raumfüllende Kurven benutzt, um eine Operation auf dünnen Gittern, die Hierarchisierung, Cache-effizient durchzuführen. Dazu wird ein Stack & Stream Verfahren vorgestellt, das als alleinige Datenstruktur Stacks verwendet und so Cache-Effizienz garantiert, ohne das spezifische Annahmen über die Cache-Struktur gemacht werden müssen.