NDLI: Cache-oblivious mesh layouts

Content Provider	ACM Digital Library
Author	Yoon, Sung-Eui Lindstrom, Peter Pascucci, Valerio Manocha, Dinesh
Copyright Year	2005
Abstract	We present a novel method for computing cache-oblivious layouts of large meshes that improve the performance of interactive visualization and geometric processing algorithms. Given that the mesh is accessed in a reasonably coherent manner, we assume no particular data access patterns or cache parameters of the memory hierarchy involved in the computation. Furthermore, our formulation extends directly to computing layouts of multi-resolution and bounding volume hierarchies of large meshes.We develop a simple and practical cache-oblivious metric for estimating cache misses. Computing a coherent mesh layout is reduced to a combinatorial optimization problem. We designed and implemented an out-of-core multilevel minimization algorithm and tested its performance on unstructured meshes composed of tens to hundreds of millions of triangles. Our layouts can significantly reduce the number of cache misses. We have observed 2--20 times speedups in view-dependent rendering, collision detection, and isocontour extraction without any modification of the algorithms or runtime applications.
Starting Page	886
Ending Page	893
Page Count	8
File Format	PDF
ISSN	07300301
e-ISSN	15577368
DOI	10.1145/1073204.1073278
Volume Number	24
Issue Number	3
Journal	ACM Transactions on Graphics (TOG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2005-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Mesh Layouts for Block-Based Caches

Binary Mesh Partitioning for Cache-Efficient Visualization

Cache-oblivious ray reordering

Cache-oblivious wavefront: improving parallelism of recursive dynamic programming algorithms without losing cache-efficiency

Cache-oblivious mesh layouts (2005)

AUTOGEN:automatic discovery of cache-oblivious parallel recursive algorithms for solving dynamic programs

Cache-oblivious mesh layouts (2005)

Urban pattern: layout design by hierarchical domain splitting

Locality-oblivious cache organization leveraging single-cycle multi-hop NoCs (SIGP, Vol. 49, Issue. 4)

Cache-oblivious mesh layouts

Similar Documents

Mesh Layouts for Block-Based Caches

Binary Mesh Partitioning for Cache-Efficient Visualization

Cache-oblivious ray reordering

Cache-oblivious wavefront: improving parallelism of recursive dynamic programming algorithms without losing cache-efficiency

Cache-oblivious mesh layouts (2005)

AUTOGEN:automatic discovery of cache-oblivious parallel recursive algorithms for solving dynamic programs

Cache-oblivious mesh layouts (2005)

Urban pattern: layout design by hierarchical domain splitting

Locality-oblivious cache organization leveraging single-cycle multi-hop NoCs (SIGP, Vol. 49, Issue. 4)

Cache-oblivious mesh layouts