TY - GEN
T1 - Memory-efficient sierpinski-order traversals on dynamically adaptive, recursively structured triangular grids
AU - Bader, Michael
AU - Rahnema, Kaveh
AU - Vigh, Csaba
PY - 2012
Y1 - 2012
N2 - Adaptive mesh refinement and iterative traversals of unknowns on such adaptive grids are fundamental building blocks for PDE solvers. We discuss a respective integrated approach for grid refinement and processing of unknowns that is based on recursively structured triangular grids and space-filling element orders. In earlier work, the approach was demonstrated to be highly memory- and cache-efficient. In this paper, we analyse the cache efficiency of the traversal algorithms using the I/O model. Further, we discuss how the nested recursive traversal algorithms can be efficiently implemented. For that purpose, we compare the memory throughput of respective implementations with simple stream benchmarks, and study the dependence of memory throughput and floating point performance from the computational load per element.
AB - Adaptive mesh refinement and iterative traversals of unknowns on such adaptive grids are fundamental building blocks for PDE solvers. We discuss a respective integrated approach for grid refinement and processing of unknowns that is based on recursively structured triangular grids and space-filling element orders. In earlier work, the approach was demonstrated to be highly memory- and cache-efficient. In this paper, we analyse the cache efficiency of the traversal algorithms using the I/O model. Further, we discuss how the nested recursive traversal algorithms can be efficiently implemented. For that purpose, we compare the memory throughput of respective implementations with simple stream benchmarks, and study the dependence of memory throughput and floating point performance from the computational load per element.
KW - adaptive mesh refinement
KW - cache oblivious algorithms
KW - memory-bound performance
KW - partial differential equations
KW - space-filling curves
UR - http://www.scopus.com/inward/record.url?scp=84857491485&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-28145-7_30
DO - 10.1007/978-3-642-28145-7_30
M3 - Conference contribution
AN - SCOPUS:84857491485
SN - 9783642281440
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 302
EP - 312
BT - Applied Parallel and Scientific Computing - 10th International Conference, PARA 2010, Revised Selected Papers
T2 - 10th International Conference on Applied Parallel and Scientific Computing, PARA 2010
Y2 - 6 June 2010 through 9 June 2010
ER -