Low-constant parallel algorithms for finite element simulations using linear octrees
Low-constant parallel algorithms for finite element simulations using linear octrees
复制标题
使用线性八叉树进行有限元模拟的低常数并行算法
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
G. Biros
中科院分区：
文献类型：
--
作者：
H. Sundar;R. Sampath;Santi S. Adavani;C. Davatzikos;G. Biros
在本文中，我们提出了平行算法，以构建线性动力学的有限元离散化。现有的基于OCTREE的离散量表到数十亿个要素，但复杂性常数可能很高。在我们的方法中，我们使用多种技术来最大程度地减少开销：一种新颖的自下而上的树木结构和2：1平衡约束执法；通过将OCTREE和元素连接表示为唯一可解码的代码（UDC），用于压缩的Golomb-Rice编码；重叠的通信和计算；和字节对齐，以提高缓存效率。应用Laplacian的成本与使用直接索引的常规网格离散化（具有相同数量的元素）相当。我们的算法在匹兹堡超级计算中心的Cray XT3上的4096处理器上的算法在4096处理器上扩展了40亿个八分之一。与先前需要几分钟的实施相比，整个树木的建造时间不到一分钟。可变的laplacian的离散化评估仅需几秒钟。
In this article we propose parallel algorithms for the construction of conforming finite-element discretization on linear octrees. Existing octree-based discretizations scale to billions of elements, but the complexity constants can be high. In our approach we use several techniques to minimize overhead: a novel bottom-up tree-construction and 2:1 balance constraint enforcement; a Golomb-Rice encoding for compression by representing the octree and element connectivity as an Uniquely Decodable Code (UDC); overlapping communication and computation; and byte alignment for cache efficiency. The cost of applying the Laplacian is comparable to that of applying it using a direct indexing regular grid discretization with the same number of elements. Our algorithm has scaled up to four billion octants on 4096 processors on a Cray XT3 at the Pittsburgh Supercomputing Center. The overall tree construction time is under a minute in contrast to previous implementations that required several minutes; the evaluation of the discretization of a variable-coefficient Laplacian takes only a few seconds.