A Cache-Aware Algorithm for PDEs on Hierarchical Data Structures Based on Space-Filling Curves
A Cache-Aware Algorithm for PDEs on Hierarchical Data Structures Based on Space-Filling Curves
复制标题
基于空间填充曲线的分层数据结构偏微分方程缓存感知算法
DOI：
10.1137/040604078
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
C. Zenger
中科院分区：
文献类型：
--
作者：
Frank Günther;M. Mehl;Markus Pögl;C. Zenger
用于解决部分微分方程的竞争数值算法必须与最有效的数值方法（如多移民和自适应网格细化）一起使用，因此不幸的是，在大多数实现中，层次数据（均可存储在树木中）。访问。实际上是线性处理的结构。仔细减少。
Competitive numerical algorithms for solving partial differential equations have to work with the most efficient numerical methods like multigrid and adaptive grid refinement and thus with hierarchical data structures. Unfortunately, in most implementations, hierarchical data—typically stored in trees—cause a nonnegligible overhead in data access. To overcome this quandary—numerical efficiency versus efficient implementation—our algorithm uses space-filling curves to build up data structures which are processed linearly. In fact, the only kind of data structure used in our implementation is stacks. Thus, data access becomes very fast—even faster than the common access to nonhierarchical data stored in matrices—and, in particular, cache misses are reduced considerably. Furthermore, the implementation of multigrid cycles and/or higher order discretizations as well as the parallelization of the whole algorithm become very easy and straightforward on these data structures.