计算机科学与探索 ›› 2013, Vol. 7 ›› Issue (8): 698-703.DOI: 10.3778/j.issn.1673-9418.1212018

• 学术研究 • 上一篇    下一篇

一般稀疏矩阵相乘的混合并行算法

罗海飙1+，王  婷1,2，张云泉2   

  1. 1. 广州中国科学院 软件应用技术研究所 并行软件云化技术研究中心，广州 511458
    2. 中国科学院 软件研究所 并行软件与计算科学实验室，北京 100190
  • 出版日期:2013-08-01 发布日期:2013-08-06

Hybrid Parallel Algorithm of General Sparse Matrix Multiplication

LUO Haibiao1+, WANG Ting1,2, ZHANG Yunquan2   

  1. 1. Research Center of Parallel Software Cloud Application, Institute of Software Application Technology, Guangzhou & Chinese Academy of Sciences, Guangzhou 511458, China
    2. Laboratory of Parallel Software and Computational Science, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China
  • Online:2013-08-01 Published:2013-08-06

PDF

摘要： 稀疏矩阵相乘广泛应用于科学和工程计算中，是科学计算中的一种常用的基本运算，其面临着数据量大，非零值分布不规则，负载难均衡，计算结果矩阵的列指数无规则分布等问题。通过矩阵分块，优化数据传输，负载均衡，改良并行快速排序方法来解决上述问题，提高了计算效率。在多线程下计算速度比商业软件Intel MKL（Intel math kernel library）平均提高56%。同时，还通过MPI+OpenMP进行混合并行优化，在共享存储系统上两者有类似的计算速度。

关键词: 稀疏矩阵相乘, 混合并行, 负载均衡, 并行快速排序

Abstract: Sparse matrix multiplication is widely used in scientific and engineering computations. It is a basic operation in scientific computation, but it faces many difficulties such as large data set, irregular distribution of non-zero values, load unbalancing and irregular distribution of column index of the resulting matrix. This paper optimizes matrix partitioning, data communication, load balancing and parallel sort methods to tackle the above problems. The computing speed of the algorithm improves 56% in average at multithread over commercial software Intel MKL (Intel Math Kernel Library). This paper further develops MPI+OpenMP hybrid parallel algorithm for multiprocess that achieves similar efficiency on shared memory system. 

Key words: sparse matrix multiplication, hybrid parallel, load balance, parallel quick sort

京ICP备13024263号-1
Copyright © 《计算机科学与探索》编辑部
技术支持：北京玛格泰克科技发展有限公司
总访问量
今日访问
在线人数