| 摘要: |
| 稀疏三角线性方程组求解（SpTRSV）在科学与工程计算领域是比较重要的核心计算函数，其中基于结构化网格构造的线性方程组是SpTRSV求解器经常遇到的一类问题.在国产神威×太湖之光超级计算机所配备的SW26010处理器上，SpTRSV求解器通常需要结合该平台的架构特点，通过搭建一定的数据路由体系来满足各工作线程对未知量数据的需求.面向与结构化网格相关的稀疏三角方程组问题，提出一套适用于SW26010处理器的并行求解器.该求解器在任务划分阶段将各线程的数据依赖模式限制在相对可控的范围之内，并在无数据路由的条件下解决线程的通信问题，不仅消除了数据路由带来的额外通信开销，而且适用的问题范围也不再受数据路由规则的制约.经测试，针对多种不同类型的结构化网格问题，提出的求解器框架的平均访存带宽利用率达88.2%，部分问题的访存带宽可达平台峰值带宽的94.5%（24.5 GB/s），整体性能相比现有工作有较为明显的提高. |
| 关键词: 稀疏三角线性方程求解(SpTRSV) 结构化网格 SW26010处理器 异构计算 |
| DOI：10.13328/j.cnki.jos.006381 |
| 分类号:TP301 |
| 基金项目:国家重点研发计划（2020YFB0204601，2016YFB0200603） |
|
| Parallel Sparse Triangular Solver for Structured Grid Problems on SW26010 Processor |
|
CHEN Dao-Kun1,2, LIU Fang-Fang1,2, YANG Chao3
|
|
1.Laboratory of Parallel Software and Computational Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;2.University of Chinese Academy of Sciences, Beijing 100049, China;3.School of Mathematical Sciences, Peking University, Beijing 100871, China
|
| Abstract: |
| 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. OnSW26010 processor, 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). |
| Key words: sparse triangular solver (SpTRSV) structured-grid SW26010 processor heterogeneous computing |
