×

zbMATH — the first resource for mathematics

Fast mesh-to-mesh remaps using hash algorithms. (English) Zbl 1394.65158
MSC:
65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs
65Y10 Numerical algorithms for specific classes of architectures
68Q25 Analysis of algorithms and problem complexity
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68W10 Parallel algorithms in computer science
Software:
p4est; Peano; RAGE; STREAM
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D. A. Alcantara, Efficient Hash Tables on the GPU, Ph.D. thesis, UC Davis, Davis, CA, 2011.
[2] D. A. Alcantara, A. Sharf, F. Abbasinejad, S. Sengupta, M. Mitzenmacher, J. D. Owens, and N. Amenta, Real-time parallel hashing on the GPU, ACM Trans. Graph., 28 (2009), 154, .
[3] M. Bader, C. Böck, J. Schwaiger, and C. Vigh, Dynamically adaptive simulations with minimal memory requirement—solving the shallow water equations using Sierpinski curves, SIAM J. Sci. Comput., 32 (2010), pp. 212–228, . · Zbl 1410.76149
[4] J. L. Bentley, Multidimensional binary search trees used for associative searching, Commun. ACM, 18 (1975), pp. 509–517, . · Zbl 0306.68061
[5] H.-J. Bungartz, M. Mehl, T. Neckel, and T. Weinzierl, The PDE framework Peano applied to fluid dynamics: An efficient implementation of a parallel multiscale fluid dynamics solver on octree-like adaptive Cartesian grids, Comput. Mech., 46 (2010), pp. 103–114, . · Zbl 1301.76056
[6] C. Burstedde, L. C. Wilcox, and O. Ghattas, p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees, SIAM J. Sci. Comput., 33 (2011), pp. 1103–1133, . · Zbl 1230.65106
[7] R. Castro, T. Lewiner, H. Lopes, G. Tavares, and A. Bordignon, Statistical optimization of octree searches, Computer Graphics Forum, 27 (2008), pp. 1557–1566, . · Zbl 1162.68737
[8] B. Choi, R. Komuravelli, V. Lu, H. Sung, R. L. Bocchino, S. V. Adve, and J. C. Hart, Parallel SAH kD tree construction, in Proceedings of the Conference on High Performance Graphics, Eurographics Association, Saarbrücken, Germany, 2010, pp. 77–86.
[9] T. H. Cormen, Introduction to Algorithms, MIT Press, Cambridge, MA, 2009, pp. 191–193.
[10] M. Gittings, R. Weaver, M. Clover, T. Betlach, N. Byrne, R. Coker, E. Dendy, R. Hueckstaedt, K. New, W. R. Oakes, D. Ranta, and R. Stefan, The RAGE radiation-hydrodynamic code, Comput. Sci. Discovery, 1 (2008), 015005.
[11] J. Grandy, Conservative remapping and region overlays by intersecting arbitrary polyhedra, J. Comput. Phys., 148 (1999), pp. 433–466, . · Zbl 0932.76073
[12] J. M. Grandy, Scaling of the Overlink Mesh Interpolation Code on Sequoia, Tech. report, Lawrence Livermore National Laboratory (LLNL), Livermore, CA, 2015.
[13] A. M. Herring, O. Certik, C. R. Ferenbaugh, R. V. Garimella, B. A. Jean, C. M. Malone, and C. M. Sewell, (U) Introduction to Portage, Tech. Report LA-UR-17-20831, Los Alamos National Laboratory (LANL), Los Alamos, NM, 2017.
[14] D. E. Knuth, Minimum-comparison sorting, in The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison–Wesley, Reading, MA, 1997, pp. 180–197.
[15] J. D. MacDonald and K. S. Booth, Heuristics for ray tracing using space subdivision, The Visual Computer, 6 (1990), pp. 153–166, .
[16] D. Madeira, A. Montenegro, E. Clua, and T. Lewiner, GPU octrees and optimized search, in Proceedings of the 8th Brazilian Symposium on Games and Digital Entertainment, Rio de Janeiro, Brazil, 2009, pp. 73–76.
[17] J. D. McCalpin, Stream Benchmark Results, available at .
[18] J. D. McCalpin, A Survey of Memory Bandwidth and Machine Balance in Current High Performance Computers, available at .
[19] B. McKenzie, R. Harries, and T. Bell, Selecting a hashing algorithm, J. Software Practice Exp., 20 (1990), pp. 209–224, .
[20] D. Meagher, Geometric modeling using octree encoding, Comput. Graphics Image Process., 19 (1982), pp. 129–147, .
[21] M. Mehl, T. Weinzierl, and C. Zenger, A cache-oblivious self-adaptive full multigrid method, Numer. Linear Algebra Appl., 13 (2006), pp. 275–291, . · Zbl 1174.65550
[22] S. J. Plimpton, B. Hendrickson, and J. R. Stewart, A parallel rendezvous algorithm for interpolation between multiple grids, J. Parallel Distrib. Comput., 64 (2004), pp. 266–276, . · Zbl 1069.68651
[23] C. Redman, G. Collom, and R. W. Robey, Compact Hash Remap GitHub, available at , LA-CC-15-102.
[24] R. N. Robey, D. Nicholaeff, and R. W. Robey, Hash-based algorithms for discretized data, SIAM J. Sci. Comput., 35 (2013), pp. C346–C368, . · Zbl 1276.68172
[25] H. Samet, Region representation: Quadtrees from boundary codes, Commun. ACM, 23 (1980), pp. 163–170, . · Zbl 0429.68074
[26] S. R. Slattery, P. P. H. Wilson, and R. P. Pawlowski, The data transfer kit: A geometric rendezvous-based tool for multiphysics data transfer, in Proceedings of the International Conference on Mathematics and Computational Methods Applied to Nuclear Science and Engineering, M and C 2013, Sun Valley, ID, 2013, 45033752.
[27] H. Sundar, R. S. Sampath, and G. Biros, Bottom-up construction and 2:1 balance refinement of linear octrees in parallel, SIAM J. Sci. Comput., 30 (2008), pp. 2675–2708, . · Zbl 1186.68554
[28] R. Tumblin, P. Ahrens, S. Hartse, and R. W. Robey, Parallel compact hash algorithms for computational meshes, SIAM J. Sci. Comput., 37 (2015), pp. C31–C53, . · Zbl 1343.65144
[29] M. S. Warren and J. K. Salmon, A parallel hashed Oct-Tree N-body algorithm, in Proceedings of the 1993 ACM/IEEE Conference on Supercomputing, ACM, New York, 1993, pp. 12–21, .
[30] T. Weinzierl, The Peano Software—Parallel, Automaton-Based, Dynamically Adaptive Grid Traversals, manuscript.
[31] T. Weinzierl and M. Mehl, Peano—a traversal and storage scheme for octree-like adaptive Cartesian multiscale grids, SIAM J. Sci. Comput., 33 (2011), pp. 2732–2760, . · Zbl 1245.65169
[32] S. Williams, A. Waterman, and D. Patterson, Roofline: An insightful visual performance model for multicore architectures, Commun. ACM, 52 (2009), pp. 65–76, .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.