| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Mesh Layouts for Block-Based Caches
September-October 2006 (vol. 12 no. 5)
pp. 1213-1220
Current computer architectures employ caching to improve the performance of a wide variety of applications. One of the main characteristics of such cache schemes is the use of block fetching whenever an uncached data element is accessed. To maximize the benefit of the block fetching mechanism, we present novel cache-aware and cache-oblivious layouts of surface and volume meshes that improve the performance of interactive visualization and geometric processing algorithms. Based on a general I/O model, we derive new cache-aware and cache-oblivious metrics that have high correlations with the number of cache misses when accessing a mesh. In addition to guiding the layout process, our metrics can be used to quantify the quality of a layout, e.g. for comparing different layouts of the same mesh and for determining whether a given layout is amenable to significant improvement. We show that layouts of unstructured meshes optimized for our metrics result in improvements over conventional layouts in the performance of visualization applications such as isosurface extraction and view-dependent rendering. Moreover, we improve upon recent cache-oblivious mesh layouts in terms of performance, applicability, and accuracy.
[1] 1213 A. Aggarwal and J. S. Vitter, The input/output complexity of sorting and related problems. Communications of ACM, 31: 1116–1127, 1988.[2] L. Arge, G. Brodai, and R. Fagerberg, Cache Oblivious Data Structures. Handbook on Data Structures and Applications, 2004.[3] A. Bogomjakov and C. Gotsman, Universal Rendering Sequences for Transparent Vertex Caching of Progressive Meshes. Computer Graphics Forum, 137–148. 2002.[4] S. Coleman and K. McKinley, Tile Size Selection using Cache Organization and Data Layout. SIGPLAN Conference on Programming Language Design and Implementation, 279–290, 1995.[5] M. F. Deering, Geometry Compression. ACM SIGGRAPH, 13–20. 1995.[6] J. Diaz, J. Petit, and M. Serna, A Survey of Graph Layout Problems. ACM Computing Surveys, 34 (3): 313–356, 2002.[7] P. Diaz-Gutierrez, A. Bhushan, M. Gopi, and R. Pajarola, Constrained Strip Generation and Management for Efficient Interactive 3D Rendering. Computer Graphics International, 115–121. 2005.[8] F. Evans, S. S. Skiena, and A. Varshney, Optimizing Triangle Strips for Fast Rendering. IEEE Visualization, 319–326. 1996.[9] P. Fishburn, P. Tetali, and P. Winkler, Optimal linear arrangement of a rectangular grid. Discrete Mathematics, 213 (1): 123–139, 2000.[10] M. Frigo, C. Leiserson, H. Prokop, and S. Ramachandran, Cache-oblivious algorithms. Foundations of Computer Science, 285–297. 1999.[11] M. Garey, D. Johnson, and L. Stockmeyer, Some simplified NP-complete graph problems. Theoretical Computer Science 1, 237–267, 1976.[12] C. Gotsman and M. Lindenbaum, On the metric properties of discrete space-filling curves. IEEE Transactions on Image Processing, 5 (5): 794–797, 1996.[13] H. Hoppe, Optimization of mesh locality for transparent vertex caching. ACM SIGGRAPH, 269–276, 1999.[14] M. Isenburg and P. Lindstrom, Streaming Meshes. IEEE Visualization, 231–238, 2005.[15] M. Isenburg, P. Lindstrom, S. Gumhold, and J. Snoeyink, Large Mesh Simplification using Processing Sequences. IEEE Visualization, 465–472, 2003.[16] M. Juvan and B. Mohar, Optimal linear labelings and eigenvalues of graphs. Discrete Applied Mathematics, 36 (2): 153–168, 1992.[17] Z. Karni, A. Bogomjakov, and C. Gotsman, Efficient compression and rendering of multi-resolution meshes. IEEE Visualization, 347–54. 2002.[18] G. Karypis and V. Kumar, Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 96–129, 1998.[19] Y. Koren and D. Harel, A Multi-scale Algorithm for the Linear Arrangement Problem. Lecture Notes In Computer Science, 2573: 296–309, 2002.[20] P. Lindstrom and V. Pascucci, Visualization of Large Terrains Made Easy. IEEE Visualization, 363–370, 2001.[21] G. Mitchison and R. Durbin, Optimal numberings of an N × N array. SIAM journal on Discrete and Algebraic Methods, 7 (4): 571–582, 1986.[22] R. Niedermeier, K. Reinhardt, and P. Sanders, Towards optimal locality in mesh-indexings. Discrete Applied Mathematics, 117 (1): 211–237, 2002.[23] V. Pascucci and R. J. Frank, Global Static Indexing for Real-time Exploration of Very Large Regular Grids. Supercomputing. 2001.[24] H. Sagan, Space-Filling Curves. Springer-Verlag, 1994.[25] C. Silva, Y.-J. Chiang, W. Correa, J. El-Sana, and P. Lindstrom, Out-Of-Core Algorithms for Scientific Visualization and Computer Graphics. IEEE Visualization Course Notes. 2002.[26] M. van Kreveld, R. van Oostrum, C. Bajaj, V. Pascucci, and D. Schikore, Contour Trees and Small Seed Sets for Isosurface Traversal. ACM Symposium on Computational Geometry, 212–220. 1997.[27] L. Velho and J. de Miranda Gomes, Digital halftoning with space filling curves. ACM SIGGRAPH, 81–90. 1991.[28] J. Vitter, External Memory Algorithms and Data Structures: Dealing with MASSIVE Data. ACM Computing Surveys, 209–271, 2001.[29] J.-M. Wierum, Logarithmic Path-Length in Space-Filling Curves. 14th Canadian Conference on Computational Geometry, 22–26. 2002.[30] S.-E. Yoon, P. Lindstrom, V. Pascucci, and D. Manocha, Cache-Oblivious Mesh Layouts. ACM SIGGRAPH, 886–893, 2005.[31] S.-E. Yoon and D. Manocha, Cache-Efficient Layouts of Bounding Volume Hierarchies. Eurographics. 2006. To appear.[32] S.-E. Yoon, B. Salomon, R. Gayle, and D. Manocha, Quick-VDR: Interactive View-Dependent Rendering of Massive Models. IEEE Visualization, 131–138, 2004.
Index Terms:
Mesh and graph layouts, cache-aware and cache-oblivious layouts, metrics for cache coherence, data locality.
Citation:
Sung-Eui Yoon, Peter Lindstrom, "Mesh Layouts for Block-Based Caches," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 1213-1220, Sept. 2006, doi:10.1109/TVCG.2006.162
