Binary mesh partitioning for cache-efficient visualization.

Area of Science:

• Computer Science
• Data Visualization
• Algorithm Design

Background:

• Data transfer between processor and memory is a key bottleneck in large dataset visualization.
• Cache-aware (CA) and cache-oblivious (CO) algorithms optimize memory hierarchy usage for cache efficiency.
• Existing CO algorithms for 3D mesh layouts lack theoretical performance guarantees.

Purpose of the Study:

• To present a new cache-oblivious algorithm for computing layouts of unstructured, well-shaped 3D meshes.
• To provide theoretical performance guarantees for cache misses in d-dimensional meshes.
• To evaluate the performance and memory consumption of the proposed algorithm against existing methods.

Main Methods:

• Developed an O(N log N) algorithm for computing a cache-oblivious layout for 3D meshes.
• Derived a theoretical bound for cache misses: less than N/B + O(N/M^(1/d)).
• Conducted experiments comparing the new algorithm with state-of-the-art CO algorithms on visualization tasks and GPU architectures.

Main Results:

• The proposed layout computation is faster and more memory-efficient than the best known CO algorithm.
• Performance is comparable for standard visualization access patterns and superior when using the generated BSP tree as an acceleration structure.
• Cache-oblivious approaches demonstrate significant performance gains on modern GPU architectures.

Conclusions:

• The new O(N log N) CO algorithm provides theoretical guarantees and practical performance improvements for 3D mesh visualization.
• The algorithm's efficiency and adaptability make it suitable for handling large datasets on diverse memory hierarchies, including GPUs.
• Cache-oblivious strategies are crucial for advancing high-performance scientific visualization.