Grenoble Universités

One important bottleneck when visualizing large data sets is the data transfer between processor and memory. Cache-aware (CA) and cache-oblivious (CO) algorithms take into consideration the memory hierarchy to design cache efficient al-gorithms. CO approaches have the advantage to adapt to unknown and varying memory hierar-chies. Recent CA and CO algorithms developed for 3D mesh layouts significantly improve perfor-mance of previous approaches. However, these al-gorithms are based on heuristics. We propose in this paper a new CO algorithm for meshes that has both a low theoretical complexity and proven quality. We guarantee that a coherent traversal of an O(N)-size mesh in dimension d will induce less than O(N/B+N/M1/d) cache misses where B and M are the block size and the cache size. We com-pare our layout with previous ones on several 3D meshes