SW26010处理器上的并行结构化稀疏三角方程组求解器  

Parallel Sparse Triangular Solver for Structured Grid Problems on SW26010 Processor

作　　者：陈道琨 刘芳芳[1,2] 杨超 CHEN Dao-Kun;LIU Fang-Fang;YANG Chao(Laboratory of Parallel Software and Computational Science,Institute of Software,Chinese Academy of Sciences,Beijing 100190,China;University of Chinese Academy of Sciences,Beijing 100049,China;School of Mathematical Sciences,Peking University,Beijing 100871,China)

机构地区：[1]中国科学院软件研究所并行软件与计算科学实验室,北京100190 [2]中国科学院大学,北京100049 [3]北京大学数学科学学院,北京100871

出　　处：《软件学报》2022年第12期4452-4463,共12页Journal of Software

基　　金：国家重点研发计划(2020YFB0204601,2016YFB0200603)。

摘　　要：稀疏三角线性方程组求解(Sp TRSV)在科学与工程计算领域是比较重要的核心计算函数,其中基于结构化网格构造的线性方程组是Sp TRSV求解器经常遇到的一类问题.在国产神威?太湖之光超级计算机所配备的SW26010处理器上,Sp TRSV求解器通常需要结合该平台的架构特点,通过搭建一定的数据路由体系来满足各工作线程对未知量数据的需求.面向与结构化网格相关的稀疏三角方程组问题,提出一套适用于SW26010处理器的并行求解器.该求解器在任务划分阶段将各线程的数据依赖模式限制在相对可控的范围之内,并在无数据路由的条件下解决线程的通信问题,不仅消除了数据路由带来的额外通信开销,而且适用的问题范围也不再受数据路由规则的制约.经测试,针对多种不同类型的结构化网格问题,提出的求解器框架的平均访存带宽利用率达88.2%,部分问题的访存带宽可达平台峰值带宽的94.5%(24.5 GB/s),整体性能相比现有工作有较为明显的提高.Sparse triangular solver(SpTRSV)is an important computation kernel in scientific computing.The irregular memory access pattern of SpTRSV makes efficient data reuse difficult to achieve.Structured grid problems possess special nonzero patterns.OnSW26010processor,the major building block of Sunway Taihulight supercomputer,these patterns are often exploited during the task partitioning stage to facilitate on-chip reuse of computed unknowns.Software-based routing is usually employed to implement inter-thread communication.Routing incurs overhead and imposes certain restrictions on nonzero patterns.This study achieves on-chip data reuse without routing.The input problem is partitioned and mapped onto SW26010 such that threads with data dependencies are always connected by the register communication network.This enables direct thread communication and obviates routing.The proposed solver is described and it is tested over a variety of problems.In the experiments,the proposed solver sustains an average memory bandwidth utilization of 88.2%with peak efficiency reaching 94.5%(24.5 GB/s).

关 键 词：稀疏三角线性方程求解(Sp TRSV) 结构化网格 SW26010处理器 异构计算 

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