Binary Mesh Partitioning for Cache-Efficient Processing

Marc Tchiboukdjian 1 Vincent Danjean 1 Bruno Raffin 1
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : 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 algorithms. CO approaches have the advantage to adapt to unknown and varying memory hierarchies. Recent CA and CO algorithms developed for 3D mesh layouts significantly improve performance of previous approaches, but lack of theoretical performance guarantees. We present in this report a O(N log N) algorithm to compute CO layout for unstructured meshes. We prove that a coherent traversal of a N-size mesh in dimension d will induce less than N/B+O(N/M^{1/d}) cache-misses where B and M are the block size and the cache size. Experiments show that our layout computation is faster and significantly less memory consuming than for the best known CO algorithm. Performance is comparable to this algorithm for classical visualization algorithm access patterns, or better if the access pattern is adapted to the binary mesh partitioning produced by the algorithm. We also show that cache oblivious approaches lead to significant performance increases on recent GPU architectures.
Type de document :
[Research Report] RR-7118, INRIA. 2009
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger
Contributeur : Marc Tchiboukdjian <>
Soumis le : mercredi 25 novembre 2009 - 20:33:56
Dernière modification le : jeudi 11 octobre 2018 - 08:48:03
Document(s) archivé(s) le : mardi 16 octobre 2012 - 14:51:11


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00436052, version 1


Marc Tchiboukdjian, Vincent Danjean, Bruno Raffin. Binary Mesh Partitioning for Cache-Efficient Processing. [Research Report] RR-7118, INRIA. 2009. 〈inria-00436052〉



Consultations de la notice


Téléchargements de fichiers