Sparse Matrix Multiplication on Dataflow Engines

详细信息    查看全文

• 关键词：Sparse matrices ; Matrix multiplication ; Maxeler dataflow engine
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9573
• 期：1
• 页码：23-30
• 全文大小：469 KB
• 参考文献：1.Milovanovic, I., Bekakos, M.P., Tselepis, I.N., Milovanovic, E.I.: Forty-three ways of systolic matrix multiplication. Int. J. Comput. Math. 87(6), 1264–1276 (2010)MathSciNet CrossRef MATH
  2.Smith, T.M., Van De Geijn, R., Smelyanskiy, M., Hammond, J.R., Van Zee, F.G.: Anatomy of high-performance many-threaded matrix multiplication. In: 28th IEEE International Parallel and Distributed Processing Symposium, pp. 1049–1059. IEEE (2014)
  3.Matam, K., Indarapu, S., Kothapalli, K.: Sparse matrix-matrix multiplication on modern architectures. In: 19th International Conference on High Performance Computing (HiPC), pp. 1–10. IEEE (2012)
  4.Saule, E., Kaya, K., Çatalyürek, Ü.V.: Performance evaluation of sparse matrix multiplication kernels on Intel Xeon Phi. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Waśniewski, J. (eds.) PPAM 2013, Part I. LNCS, vol. 8384, pp. 559–570. Springer, Heidelberg (2014)
  5.Weifeng, L., Vinter, B.: An efficient GPU general sparse matrix-matrix multiplication for irregular data. In: IEEE 28th International Parallel and Distributed Processing Symposium, pp. 370–381. IEEE (2014)
  6.Yavits, L., Morad, A., Ginosar, R.: Sparse matrix multiplication on an associative processor. IEEE Trans. Parallel Distrib. Syst. (2014)
  7.Ciric, V., Cvetkovic, A., Simic, V., Milentijevic, I.: Tropical algebra based framework for error propagation analysis in systolic arrays. Elsevier Appl. Math. Comput. 225, 512–525 (2013)MathSciNet CrossRef
  8.Maxeler Technologies, MaxCompiler documentation, Version 2014.1, Maxeler Technologies
  
• 作者单位：Vladimir Simic (19)
  Vladimir Ciric (19)
  Nikola Savic (19)
  Ivan Milentijevic (19)
  
  19. Faculty of Electronic Engineering, University of Nis, Aleksandra Medvedeva 14, P.O. Box 14, 18000, Nis, Serbia
  
• 丛书名：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

文摘

In this paper, a novel architecture for sparse matrix multiplication is proposed. The architecture is suitable for implementation in specific environments such as dataflow engines. In order to avoid multiple streaming of elements from the host, we propose the architecture which buffers the elements from the input stream in on-chip memory in the form of pages. In the case of sparse matrices, the architecture processes only pages with non-zero elements. The proposed architecture allows replication of its blocks in order to parallelize the computation. The architecture is implemented on Maxeler dataflow engine based on Virtex 5 FPGA. The implementation results are given.