Article

Cache-efficient parallel isosurface extraction for shared cache multicores

Authors:

M. Tchiboukdjian,

B. RaffinAuthors Info & Claims

EG PGV'10: Proceedings of the 10th Eurographics conference on Parallel Graphics and Visualization

Pages 81 - 90

Published: 02 May 2010 Publication History

Abstract

This paper proposes to revisit isosurface extraction algorithms taking into consideration two specific aspects of recent multicore architectures: their intrinsic parallelism associated with the presence of multiple computing cores and their cache hierarchy that often includes private caches as well as caches shared between all cores. Taking advantage of these shared caches require adapting the parallelization scheme to make the core collaborate on cache usage and not compete for it, which can impair performance. We propose to have cores working on independent but close data sets that can all fit in the shared cache. We propose two shared cache aware parallel isosurface algorithms, one based on marching tetrahedra, and one using a min-max tree as acceleration data structure. We theoretically prove that in both cases the number of cache misses is the same as for the sequential algorithm for the same cache size. The algorithms are based on the FastCOL cache-oblivious data layout for irregular meshes. The CO layout also enables to build a very compact min-max tree that leads to a reduced number of cache misses. Experiments confirm the interest of these shared cache aware isosurface algorithms, the performance gain increasing as the shared cache size to core number ratio decreases.

References

[1]

ARGE L., BRODAL G., FAGERBERG R.: Cache oblivious data structures. Handbook on Data Structures and Applications (2004).

[2]

BROWNE S., DONGARRA J., GARNER N., HO G., MUCCI P.: A portable programming interface for performance evaluation on modern processors. The International Journal of High Performance Computing Applications 14 (2000), 189-204.

Digital Library

[3]

BLELLOCH G. E., GIBBONS P. B.: Effectively sharing a cache among threads. In Proceedings of SPAA'04 (2004), pp. 235-244.

Digital Library

[4]

BAJAJ C. L., PASCUCCI V., SCHIKORE D. R.: Fast isocontouring for improved interactivity. In Proceedings of VVS'96 (1996), p. 39.

Digital Library

[5]

CHEN S., GIBBONS P. B., KOZUCH M., ILEIOS LIASKOVITIS V., AILAMAKI A., BLELLOCH G. E., FALSAFI B., FIX L., HARDAVELLAS N., MOWRY T. C., WILKERSON C.: Scheduling threads for constructive cache sharing on cmps. In Proceedings of SPAA'07 (2007), pp. 105-115.

Digital Library

[6]

CIGNONI P., MONTANI C., PUPPO E., SCOPIGNO R.: Optimal isosurface extraction from irregular volume data. In Proceedings of VVS'96 (1996), pp. 31-38.

Digital Library

[7]

CHIANG Y.-J., SILVA C.: I/O optimal isosurface extraction. In Proceedings of Visualization'97 (1997), pp. 293-300.

Digital Library

[8]

CHIANG Y.-J., SILVA C. T.: External memory techniques for isosurface extraction in scientific visualization. In External memory algorithms (Boston, MA, USA, 1999), American Mathematical Society, pp. 247-277.

Digital Library

[9]

CHIANG Y.-J., SILVA C., SCHROEDER W.: Interactive out-of-core isosurface extraction. In Proceedings of Visualization'98 (1998), pp. 167-174.

Digital Library

[10]

FRIGO M., LEISERSON C. E., PROKOP H., RAMACHANDRAN S.: Cache-Oblivious Algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (1999), p. 285.

Digital Library

[11]

HASSIDIM A.: Cache replacement policies for multicore processors. In Proceedings of Innovations in Computer Science (2010).

[12]

PASCUCCI V., FRANK R.: Global Static Indexing for Real-Time Exploration of Very Large Regular Grids. In Proceedings of Supercomputing'01 (2001), pp. 45-45.

Digital Library

[13]

SUTTON P. M., HANSEN C. D., WEI SHEN H., SCHIKORE D.: A case study of isosurface extraction algorithm performance. In Data Visualization 2000 (2000), Springer, pp. 259-268.

[14]

SCHROEDER W., MARTIN K., LORENSEN B.: The Visualization Toolkit, An Object-Oriented Approach To 3D Graphics, 3rd ed. Kitware Inc., 2004.

[15]

TCHIBOUKDJIAN M., DANJEAN V., RAFFIN B.: Binary mesh partitioning for cache-efficient visualization. IEEE Transactions on Visualization and Computer Graphics 99, PrePrints (2010). http://moais.imag.fr/membres/ marc.tchiboukdjian/pub/tvcg10.pdf.

Digital Library

[16]

WALD I., FRIEDRICH H., MARMITT G., SLUSALLEK P., SEIDEL H.-P.: Faster isosurface ray tracing using implicit kd-trees. IEEE Transactions on Visualization and Computer Graphics 11 (2005), 562-572.

Digital Library

[17]

WANG Q., JAJA J., VARSHNEY A.: An efficient and scalable parallel algorithm for out-of-core isosurface extraction and rendering. J. Parallel Distrib. Comput. 67, 5 (2007), 592-603.

Digital Library

[18]

WILHELMS J., VAN GELDER A.: Octrees for faster isosurface generation. ACM Trans. Graph. 11, 3 (1992), 201-227.

Digital Library

[19]

YOON S.-E., LINDSTROM P., PASCUCCI V., MANOCHA D.: Cache-oblivious mesh layouts. In ACM SIGGRAPH (2005), pp. 886-893.

Digital Library

[20]

YOON S.-E., MANOCHA D.: Cache-Efficient Layouts of Bounding Volume Hierarchies. Computer Graphics Forum 25, 3 (2006), 507-516.

[21]

ZHANG H., NEWMAN T. S., ZHANG X.: Case study of multithreaded in-core isosurface extraction algorithms. In EGPGV (2004), pp. 83-92.

Digital Library

Cited By

Thébault LPetit EDinh Q(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyACM SIGPLAN Notices10.1145/2858788.268851750:8(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688517
Thébault LPetit EDinh QCohen AGrove D(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688517(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688517
Ettinger MBroquedis FGautier TPloix SRaffin BLópez MMarton FMoreland K(2013)vtkSMPProceedings of the 13th Eurographics Symposium on Parallel Graphics and Visualization10.5555/2602119.2602127(41-48)Online publication date: 4-May-2013
https://dl.acm.org/doi/10.5555/2602119.2602127

Index Terms

Cache-efficient parallel isosurface extraction for shared cache multicores
1. Computing methodologies
  1. Computer graphics
    1. Image manipulation
    2. Rendering
  2. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Location cache: a low-power L2 cache system
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and design

While set-associative caches incur fewer misses than direct-mapped caches, they typically have slower hit times and higher power consumption, when multiple tag and data banks are probed in parallel. This paper presents the location cache structure which ...
Tag-Split Cache for Efficient GPGPU Cache Utilization
ICS '16: Proceedings of the 2016 International Conference on Supercomputing

Modern GPUs employ cache to improve memory system efficiency. However, large amount of cache space is underutilized due to irregular memory accesses and poor spatial locality which exhibited commonly in GPU applications. Our experiments show that using ...
An efficient cache design for scalable glueless shared-memory multiprocessors
CF '06: Proceedings of the 3rd conference on Computing frontiers

Traditionally, cache coherence in large-scale shared-memory multiprocessors has been ensured by means of a distributed directory structure stored in main memory. In this way, the access to main memory to recover the sharing status of the block is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EG PGV'10: Proceedings of the 10th Eurographics conference on Parallel Graphics and Visualization

May 2010

140 pages

ISBN:9783905674217

Editors:
James Ahrens
Los Alamos National Laboratory
,
Kurt Debattista
University of Warwick
,
Renato Pajarola
University of Zurich

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 02 May 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Thébault LPetit EDinh Q(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyACM SIGPLAN Notices10.1145/2858788.268851750:8(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2858788.2688517
Thébault LPetit EDinh QCohen AGrove D(2015)Scalable and efficient implementation of 3d unstructured meshes computation: a case study on matrix assemblyProceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming10.1145/2688500.2688517(120-129)Online publication date: 24-Jan-2015
https://dl.acm.org/doi/10.1145/2688500.2688517
Ettinger MBroquedis FGautier TPloix SRaffin BLópez MMarton FMoreland K(2013)vtkSMPProceedings of the 13th Eurographics Symposium on Parallel Graphics and Visualization10.5555/2602119.2602127(41-48)Online publication date: 4-May-2013
https://dl.acm.org/doi/10.5555/2602119.2602127

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents