红黑Gauss-Seidel Stencil并行性和局部性优化  

Parallelization and Locality Optimization for Red-Black Gauss-Seidel Stencil

作　　者：纪璎芮 袁良[2] 张云泉[2] JI Ying-rui;YUAN Liang;ZHANG Yun-quan(School of Information Science and Engineering,Dalian Ocean University,Dalian,Liaoning 116023,China;State Key Laboratory of Computer Architecture,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190,China)

机构地区：[1]大连海洋大学信息工程学院,辽宁大连116023 [2]中国科学院计算技术研究所计算机体系结构国家重点实验室,北京100190

出　　处：《计算机科学》2022年第5期363-370,共8页Computer Science

基　　金：国家自然科学基金(61972376,62072431,62032023)。

摘　　要：Stencil(模版计算)是一类常见的循环嵌套计算模式,被广泛应用于计算电磁、天气模拟、地球物理、海洋模拟等许多科学和工程模拟应用中。随着现代处理器体系结构的发展,多核和多层存储层次不断加深,研究并行性和局部性成为了提高程序运行速度的主要途径。分块是开发数据局部性和程序并行性的主要技术之一,目前,针对Stencil已提出了大量高效分块和向量化方法,但大多局限于具有较高并行度的Jacobi类型的Stencil。Gauss-Seidel Stencil具有更优的收敛速度,被广泛应用于多重网格的计算中。这类Stencil的数据依赖更为复杂,文中面向红黑排序的Gauss-Seidel Stencil设计了一种并行分块和向量化算法,提升了Gauss-Seidel Stencil的数据局部性、中粒度多核并行性以及核内细粒度并行性。实验结果证实了本文方案的有效性。Stencil is a common cyclic nested computing model,which is widely used in many scientific and engineering simulation applications,such as computational electromagnetism,weather simulation,geophysics,ocean simulation and so on.With the deve-lopment of modern processor architecture,the multi-core and multi-layer memory levels have been deepened.Research on paralle-lism and locality is the main way to improve the performance of programs.Blocking is one of the main techniques to exploit data locality and program parallelism.At present,a large number of blocking methods have been proposed for Stencil,but most of them are limited to Jacobi Stencils which is featured with high parallelism and locality.Gauss-Seidel Stencil has a better convergence rate and is widely used in multi-grid calculations.However,the data dependence of this type of Stencil is more complicated.In this paper,a parallel blocking and vectorization algorithm is designed for Gauss-Seidel Stencil for red black sorting,which improves the data locality,medium granularity multi-core parallelism and intra core fine-grained parallelism of Gauss-Seidel Stencil.Experimental results demonstrate the effectiveness of this scheme.

关 键 词：Stencil计算 分块 GAUSS-SEIDEL 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]