一种基于空间密铺的星型Stencil并行算法

曹杭; 袁良; 黄珊; 张云泉; 徐勇军; 陆鹏起; 张广婷

doi:10.7544/issn1000-1239.2020.20190734

一种基于空间密铺的星型Stencil并行算法

曹杭^1,2,
袁良¹,
黄珊^1,2,
张云泉¹,
徐勇军¹,
陆鹏起^1,2,
张广婷¹

¹(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190) ²(中国科学院大学北京 100049) (caohang@ict.ac.cn)

基金项目: 国家重点研发计划项目(2016YFB0200803)；中国科学院战略性先导科技专项(C类)(XDC01040100)；国家自然科学基金项目(61972376,62072431,61432018)；北京市自然科学基金项目(L182053)

详细信息

中图分类号: TP301
计量
- 文章访问数: 1020
- HTML全文浏览量: 4
- PDF下载量: 464
出版历程
- 发布日期: 2020-11-30

A Parallel Star Stencil Algorithm Based on Tessellating

¹(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190)

Funds: This work was supported by the National Key Research and Development Program of China (2016YFB0200803), the Strategic Priority Research Program of Chinese Academy of Sciences (C) (XDC01040100), the National Natural Science Foundation of China (61972376, 62072431, 61432018), and the Beijing Natural Science Foundation (L182053).

摘要

摘要: Stencil计算(模板计算)是科学工程应用中一类常见的嵌套循环算法.分块方法是提高数据局部性和并行性的高效优化技术之一，目前已有大量针对分块方法的探索，但现有工作往往对不同Stencil形状都采用同一处理方法.首先在空间层面引出“自然块”的概念来区分星型Stencil和盒型Stencil的特征，然后提出一个新的针对星型Stencil的2层密铺方案，此方案中自然块和它的后继块可以密铺数据空间区域，这些分块沿着时间维度扩展，能够密铺整个迭代空间.此外，针对星型Stencil设计了一个新颖的“2次更新”优化技术，改善了核内数据重用模式.理论分析表明：此方案相比现有方法有更低的缓存复杂度，实验结果证实了此方案的有效性.
- Stencil计算 /
- 密铺 /
- 星型Stencil /
- 盒型Stencil /
- 自然块
Abstract: The Stencil computation, i.e. the structured grid computing, is a very common kind of loop nesting algorithm in scientific and engineering applications. The exhaustively studied tiling method is of great effectiveness as one of the transformation techniques to exploit the data locality and parallelism of Stencil computations. However, the state-of-the-art work of tiling often uniformly handles different Stencil shapes. We first present a concept called natural block to identify the difference between the star and box Stencils. Then we propose a new two-level tessellation scheme for star Stencils, where the natural block, as well as its successive blocks can tessellate the spatial space and their extensions along the time dimension are able to form a tessellation of the iteration space. Furthermore, a novel implementation technique called double updating is developed for star Stencils specifically, which updates each element twice continuously and improves the in-core data reuse pattern. In addition, we adopt coarsening and block reuse to enhance the parallelization performance. Theoretical analysis shows that our scheme achieves a better cache complexity than existing methods such as Girih and Pluto. The experiments on performance and bandwidth are conducted on a multicore system. The results demonstrate the effectiveness of our approach.
- Stencil computation /
- tessellation /
- star Stencil /
- box Stencil /
- natural block

HTML全文

参考文献(0)

施引文献(24)

期刊类型引用(8)

1.	张宇姣，徐健，吴迪. 基于图表示学习的知识图谱时序推理模型. 济南大学学报(自然科学版). 2025(02): 272-277 . 百度学术
2.	陆佳炜，王小定，朱昊天，程振波，肖刚. 一种融合实体图上下文的三维旋转知识图谱表示学习. 小型微型计算机系统. 2023(01): 124-131 . 百度学术
3.	陈小英，熊盛武，王盛，张士伟. 基于上下文时序关联的时序知识图谱嵌入方法. 武汉大学学报(理学版). 2023(02): 249-257 . 百度学术
4.	卢菁，陈婉璐，刘丛. KGU-SP:一种挖掘标准模式的知识图谱更新方法. 小型微型计算机系统. 2023(06): 1177-1183 . 百度学术
5.	魏飞鸣，许倩倩，顾网平，李永晨. 知识图谱在探测与识别领域中的应用分析. 制导与引信. 2023(04): 1-8+28 . 百度学术
6.	马昂，于艳华，杨胜利，石川，李劼，蔡修秀. 基于强化学习的知识图谱综述. 计算机研究与发展. 2022(08): 1694-1722 . 本站查看
7.	宁原隆，周刚，卢记仓，杨大伟，张田. 一种融合关系路径与实体描述信息的知识图谱表示学习方法. 计算机研究与发展. 2022(09): 1966-1979 . 本站查看
8.	夏毅，兰明敬，陈晓慧，罗军勇，周刚，何鹏. 可解释的知识图谱推理方法综述. 网络与信息安全学报. 2022(05): 1-25 . 百度学术