一种基于空间密铺的星型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)

施引文献(14)

期刊类型引用(9)

1.	臧洁，任旭，冯艳爽，王妍，肖萍，鲁锦涛. 一种干扰系数自探测的网络事件选取方法. 小型微型计算机系统. 2024(03): 763-768 . 百度学术
2.	路苗，门可，马永红，张海瑞，冯彦成. 基于SIS模型的群体社交网络舆情演化仿真. 吉林大学学报(信息科学版). 2023(01): 106-111 . 百度学术
3.	马帅，刘建伟，左信. 图神经网络综述. 计算机研究与发展. 2022(01): 47-80 . 本站查看
4.	夏一雪，张立红，何巍，张双狮. 自治线性风险作用下网络舆情演化建模与仿真研究. 情报杂志. 2022(05): 92-98 . 百度学术
5.	易杰，曹腾飞，黄明峰，黄肖翰，张子震. 基于时间编码LSTM的高校舆情热点趋势预测研究. 大数据. 2022(05): 124-138 . 百度学术
6.	张杨，廉吉庆，张扬，高德毅. 国内网络舆情情感研究热点分析. 网络安全与数据治理. 2022(07): 47-55 . 百度学术
7.	徐缤荣. 融媒体背景下社会热点新闻舆情传播控制模型构建. 微型电脑应用. 2022(10): 149-152 . 百度学术
8.	臧洁，任旭. 考虑兴趣偏好和多事件影响的网络事件推演模型研究. 辽宁大学学报(自然科学版). 2022(04): 298-306 . 百度学术
9.	赵剑，董文华，史丽娟，匡哲君，毕京晓，王晢宇，强文倩. 针对突发公共事件的舆情监测与可视化分析. 吉林大学学报(信息科学版). 2021(06): 712-719 . 百度学术