面向国产申威26010众核处理器的SpMV实现与优化-刘芳芳 , 杨超 , 袁欣辉 , 吴长茂 , 敖玉龙.pdf

上善若水

546

12页

4次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2018,29(12):3921−3932 [doi: 10.13328/j.cnki.jos.005309] http://www.jos.org.cn

面向国产申威 26010 众核处理器的 SpMV 实现与优化

∗

刘芳芳

1,2

杨

超

1,3, 5

袁欣辉

吴长茂

敖玉龙

1,2,5

(中国科学院软件研究所并行软件与计算科学实验室,北京 100190)

(中国科学院大学,北京 100049)

(计算机科学国家重点实验室(中国科学院软件研究所),北京 100190)

(国家并行计算机工程技术研究中心,北京 100190)

(北京大学数学科学学院,北京 100871)

通讯作者: 杨超, E-mail: chao_yang@pku.edu .cn

摘要: 世界首台峰值性能超过 100P 的超级计算机——神威太湖之光已经研制完成,该超级计算机采用了国产

申威异构众核处理器,该处理器不同于现有的纯 CPU,CPU-MIC,CPU-GPU 架构,采用了主-从核架构,单处理器峰值

计算能力为 3TFlops/s,访存带宽为 130GB/s.稀疏矩阵向量乘 SpMV(sparse matrix-vector multiplication)是科学与工程

计算中的一个非常重要的核心函数,众所周知,其是带宽受限型的,且存在间接访存操作.国产申威处理器给稀疏矩

阵向量乘的高效实现带来了很大的挑战.针对申威处理器提出了一种 CSR 格式 SpMV 操作的通用异构众核并行算

法,该算法从任务划分、LDM 空间划分方面进行精细设计,提出了一套动静态 buffer 的缓存机制以提升向量 x 的访

存命中率,提出了一套动静态的任务调度方法以实现负载均衡.另外还分析了该算法中影响 SpMV 性能的几个关键

因素,并开展了自适应优化,进一步提升了性能.采用 Matrix Market 矩阵集中具有代表性的 16 个稀疏矩阵进行了测

试,相比主核版最高有 10 倍左右的加速,平均加速比为 6.51.通过采用主核版 CSR 格式 SpMV 的访存量进行分析,

测试矩阵最高可达该处理器实测带宽的 86%,平均可达到 47%.

关键词: 稀疏矩阵向量乘;SpMV;申威 26010 处理器;异构众核并行;自适应优化

中图法分类号: TP3

中文引用格式: 刘芳芳,杨超,袁欣辉,吴长茂,敖玉龙.面向国产申威 26010 众核处理器的 SpMV 实现与优化.软件学报,2018,

29(12):3921−3932. http ://www.jos.org.cn/1000-9825/5309.ht m

英文引用格式: Liu FF, Yang C, Yuan XH, Wu CM, Ao YL. General SpMV implementation in many-core domestic sunway

26010 processor. Ruan Jian Xue Bao/Journal of Software, 2018,29(12):3921−3932 (in Chinese). http://www.jos.org.cn/1000-

9825/5309.htm

General SpMV Implementation in Many-Core Domestic Sunway 26010 Pro cessor

LIU Fang-Fang

1,2

, YANG Chao

1,3,5

, YUAN Xin-Hui

, WU Chang-Mao

, AO Yu-Long

1,2,5

(Institute of Software, The Chinese Academy o f Sci ences, Beijing 100190 , China)

(University of Chinese Academy of S ciences, Beijing 10 0049, Chin a)

(State Key Laboratory of Comput er Science (Ins titute of Software, The Chinese Academy of Sciences), Beijing 100190, Ch ina)

(National Research Center of Parallel Computer Engineering and Technology, Beijing 100190, China)

(School of Mathematical Sciences, Peking University, Beijing 100871 , China)

Abstra ct : The fastest supercomputer in the world—Sunway TaihuLight with performance of more th an 100P has been released. It makes

use of heterogeneous many-core processors which is different from the existing pure CPU, CPU-MIC, CPU-GPU architecture. Each

∗ 基金项目: 国家重点研发计划(2016YFB0200603); 国家自然科学基金(91530323)

Foundation item: Nation al Key R&D Program (2016YFB0200603); National Natural Science Foundation of China (91530323)

收稿时间: 2017-01-11; 采用时间: 2 017-05-01

3922

Journal of Software 软件学报 Vol.29, No.12, December 2018

processor has 4 core groups (CGs), with each including one management processing element (MPE) and one computing processing

element (CPE) cluster of 64 CPEs. The peak performance of single processor is 3TFlops/s, the memory bandwidth is 130GB/s. Sparse

matrix-vector multiplication is a very important kernel in scientific and engineering computing, which is bandwidth limited and subject to

indirect memory access. Implementing an efficient SpMV kernel is a big challenge in Sunway processor. This paper proposes a general

SpMV heterogeneous manycore algorithm for th e traditional sparse matrix storage for mat CSR, which divides the task and LDM sp ace in

detail, a cache mechanism of dyn ami c and static buff ers to improve the hit rate of vector x, and a dynamic-static task scheduling method

to achieve load balan cing . In addition, several key factors affecting th e performance of SpMV are analyzed, and adaptive optimization is

carried out to further enhance the performance. Finally 16 matrix from matrix market collection are used to perform tests. The

experimental results show that the algorithm achieves bandwidth of 86% and average bandwidth utilization of 47%. Compared with the

implementation of the controller core, the sp eedup can be up to 10x, and average speedup is 6.51x.

Key words: sparse matrix-vector multiplication; SpMV; Sunway 26010 processor; heterogeneous many-core; adaptive optimization

稀疏矩阵向量乘(SpMV) y=Ax 是科学与工程计算中一个非常重要的计算内核,其性能往往对应用整体性

能有着很大影响.SpMV 是属于访存密集型的,算法中的浮点计算与存储访问的比率很低,且稀疏矩阵非零元素

分布很不规则,使得向量 x 为间接访问且访问不规则,可重用性差,这些因素给 SpMV 的高效实现带来很大挑战.

目前,超级计算机的体系结构已经从多核向众核乃至异构众核发展,然而访存墙问题却越来越突出,带宽受

限型操作的峰值性能也越来越低,并且实现难度逐步增大.由我国国家并行计算机工程技术研究中心研制的新

一代申威异构众核处理器已经面世,其峰值性能为 3TFlops/s,聚合访存带宽为 130GB/s,相比计算能力,其访存能

力偏弱,给稀疏矩阵向量乘的高效实现带来了巨大的挑战.本文针对该处理器特点,提出一种面向传统的稀疏矩

阵存储格式 CSR 的通用 SpMV 异构众核并行算法,并从任务划分、LDM 空间划分、向量 x 访存优化、负载均

衡、自适应优化等角度开展工作.

1 相关工作介绍

SpMV 的实现和优化,一直是高性能计算领域科研人员的研究重点.每当一款新的处理器问世,基于该处理

器的 SpMV 实现及优化的工作就会持续出现.基于 CPU 的 SpMV 工作有很多,主要从存储格式

[1,2]

、分块算

法

[3−5]

、值和索引压缩

[6,7]

、向量化

[8,9]

、自适应优化

[10,11]

等角度开展研究.

2008 年,GPGPU 出现,开启了 GPU 用于通用计算的热潮.随后,基于 GPU 的 SpMV 工作大量涌现,这些工作

主要通过存储格式、重排、压缩、自适应调优等技术解决带宽利用率、负载均衡、并行度等问题,先后提出了

HYB

[12]

,ELLPACK-R

[13]

,sliced-ELLPACK

[14]

,blocked ELLPACK

[15]

,BRC

[16]

,BCCOO

[17]

等新型存储格式;研究了

稀疏矩阵的重排技术

[18]

及压缩格式

[19]

,以减少访存开销;研究了 GPU 平台体系结构特征、稀疏矩阵存储格式、

稀疏矩阵集之间的关系,并给出自动选择模型

[20]

;另外还研究了自动调优技术

[17,21,22]

,以根据稀疏矩阵的特征选

择最优参数并获取较优的性能.

2011 年,Intel 公司的异构众核处理器 Xeon Phi 发布.随后,Liu 等人

[23]

提出了新的 ESB 格式,该格式可有效

改善 Xeon Phi 上 SpM V 向量化性能,并能减少访存开销,另外还提出了混合的动态调度器以改善并行任务的负

载均衡性;Tang 等人

[24]

通过新的存储格式 VHCC、二维不规则任务划分、自动调优技术等优化了一类 scale-free

稀疏矩阵 SpMV 的性能.

另外还有一类工作涉及到多个异构众核处理器,Kreutzer 等人

[25]

主要从改善向量化性能的角度提出新的

存储格式 SELL -C-

;Liu 等人

[26]

提出了 CSR5 存储格式用于改善不规则稀疏矩阵 SpMV 的性能,在多个异构众

核处理器上实现并与现有最优工作进行了对比.

本文主要研究面向申威 26 010 异构众核处理器的 SpMV 并行算法及实现和优化技术,以支撑该国产平台相

关应用.

2 国产申威 26010 处理器介绍

国产申威 26010 处理器采用异构众核架构,由 4 个核组(core group,简称 CG) 组成,其双精度计算能力

of 12

免费下载

软件学报计算机技术

关注

评论