Scene Graph Memory Management
Typ
Examensarbete för masterexamen
Program
Publicerad
2019
Författare
Magnus, Åkerstedt Bergsten
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Due to the growing disparity in performance between memory and processors, it is becoming increasingly important to consider the layout of applications’ working set data in memory to make effective use of cache memories and avoid performance bottlenecks from memory latency. This thesis studies the effects of data layout on scene graphs, a common data structure for organising scenes in graphics applications. Specifically, it studies (1) which way of packing nodes in memory yield the best performance for typical scene graph traversal patterns, and (2) proposes a novel technique for maintaining such a data layout in a scene graph in which nodes are added and deleted. Three data layouts — orderings for nodes, in which they are packed in memory — are evaluated for static scene graphs: a depth-first order, a breadth-first order, and a van Emde Boas layout. These are compared against a “naïve” layout, wherein nodes are individually allocated on the heap. Inasetbenchmarksrepresentingtypicaloperationsonscenegraphs,alldatalayouts yield similar performance, which is up to three times faster than the naïve layout for large scene graphs. They show very similar performance to the naïve layout for smaller scene graphs, however. Further, the dynamic memory management system presented in this thesis yields better performance than the naïve layout, in an evaluation simulating a highly dynamic scene-graph application, by up to a factor two for large scene graphs. A limitation with the approach, though, is that memory usage increases on average by a factor of 2.2 in the evaluation.
Beskrivning
Ämne/nyckelord
Computer , science , computer science , engineering , thesis , scene graph , memory management , cache friendly , cache efficient