A Fast Cache-Oblivious Mesh Layout with Theoretical Guarantees

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. However, these algorithms 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 N-size mesh in dimension d will induce less than N/B+N/M^{1/d}) cache misses where B and M are the block size and the cache size. We compare our layout with previous ones on several 3D meshes.
Type de document :
Communication dans un congrès
International Workshop on Super Visualization (IWSV'08), Jun 2008, Kos, Greece. 2008
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00436053
Contributeur : Marc Tchiboukdjian <>
Soumis le : mercredi 25 novembre 2009 - 20:42:16
Dernière modification le : mercredi 11 avril 2018 - 01:53:23
Document(s) archivé(s) le : mardi 16 octobre 2012 - 14:51:18

Fichier

send-paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00436053, version 1

Citation

Marc Tchiboukdjian, Vincent Danjean, Bruno Raffin. A Fast Cache-Oblivious Mesh Layout with Theoretical Guarantees. International Workshop on Super Visualization (IWSV'08), Jun 2008, Kos, Greece. 2008. 〈inria-00436053〉

Partager

Métriques

Consultations de la notice

325

Téléchargements de fichiers

112