Bachelor Thesis BCLR-0115

BibliographySchneider, Marcel: Die Peano-Kurve für Dünngitterhierarchisierung mit raumfüllenden Kurven.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 115 (2014).
67 pages, german.
CR-SchemaG.1.0 (Numerical Analysis General)
G.1.2 (Numerical Analysis Approximation)
F.2.0 (Analysis of Algorithms and Problem Complexity General)
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.

Full text and
other links
PDF (859388 Bytes)
Department(s)University of Stuttgart, Institute of Parallel and Distributed Systems, Simulation of Large Systems
Superviser(s)Pflüger, Dirk
Entry dateSeptember 9, 2014
   Publ. Computer Science