Parallel Algorithm for Quasi-Band Matrix-Matrix Multiplication

详细信息    查看全文

• 关键词：Band ; Quasi ; band ; spmm ; Real ; world ; Synthetic
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9573
• 期：1
• 页码：106-115
• 全文大小：286 KB
• 参考文献：1.Bell, N., Garland, M.: Implementing sparse matrix-vector multiplication on throughput-oriented processors. In: Proceeding SuperComputing (SC), pp. 1–11 (2009)
  2.Buluc, A., Gilbert, J.R.: Challenges and advances in parallel sparse matrix-matrix multiplication. In: Proceeding International Conference on Parallel Processing, pp. 503–510 (2008)
  3.Gharaibeh, A., Costa, B., Santos-Neto, E., Ripeanu, M.: On Graphs, GPUs, and Blind Dating: a workload to processor matchmaking quest. In: Proceeding International Parallel & Distributed Processing Symposium (IPDPS), pp. 851–862 (2013)
  4.Hong, S., Rodia, N.C., Olukotun, K.: On fast parallel detection of strongly connected components in small-world graphs. In: Proceedings of the SC (2013). Article No. 92
  5.Indarapu, S., Maramreddy, M., Kothapalli, K.: Architecture- and workload-aware algorithms for spare matrix- vector multiplication. In: Proceeding of ACM India Computing Conference (2014). Article No. 3
  6.Liu, W., Vinter, B.: An efficient GPU general sparse matrix-matrix multiplication for irregular data. In: Proceeding of IPDPS, pp. 370–381 (2014)
  7.Ramamoorthy, K.R., Banerjee, D.S., Srinathan, K., Kothapalli, K.: A novel heterogeneous algorithm for multiplying scale-free sparse matrices. In: Proceeding of IPDPS Workshops, pp. 637–646 (2015)
  8.Nvidia sparse matrix library (cuSPARSE). http://​developer.​nvidia.​com/​cusparse
  9.Intel Math Kernel Library. https://​software.​intel.​com/​en-us/​articles/​intel-mkl/​
  10.University of Florida UF sparse matrix collection (2011). http://​www.​cise.​ufl.​edu/​research/​sparse/​matrices/​groups.​html
  11.Yang, W., Li, K., Liu, Y., Shi, L., Wan, L.: Optimization of quasi-diagonal matrix-vector multiplication on GPU. Int. J. High Perform. Comput. Appl. 28(2), 183–195 (2014)CrossRef
  
• 作者单位：Dharma Teja Vooturi (19)
  Kishore Kothapalli (19)
  
  19. International Institute of Information Technology, Hyderabad, Gachibowli, Hyderabad, 500032, India
  
• 丛书名：Parallel Processing and Applied Mathematics
• ISBN：978-3-319-32149-3
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Sparse matrices arise in many practical scenarios. As a result, support for efficient operations such as multiplication of sparse matrices (spmm) is considered to be an important research area. Often, sparse matrices also exhibit particular characteristics that can be used towards better parallel algorithmics. In this paper, we focus on quasi-band sparse matrices that have a large majority of the non-zeros along the diagonals. We design and implement an efficient algorithm for multiplying two such matrices on a many-core architecture such as a GPU.