[發明專利]一種外積累加求解稀疏矩陣與稠密矩陣內積的方法

在審

• 申請號: 202110104426.1
• 申請日: 2021-01-26
• 公開（公告）號: CN112835552A
• 公開（公告）日: 2021-05-25
• 發明（設計）人: 周曉輝;袁博;華誠
• 申請（專利權）人: 算籌信息科技有限公司
• 主分類號: G06F7/544
• 分類號: G06F7/544;G06F17/16
• 代理公司: 濟南譽琨知識產權代理事務所(普通合伙) 37278
• 代理人: 李照蘭

本發明屬于計算機應用技術領域，尤其涉及一種外積累加求解稀疏矩陣與稠密矩陣內積的方法。包括以下有效步驟：首先對稀疏矩陣A(MxK)與稠密矩陣B(KxN)原始數據的完成讀取；對稀疏矩陣A(MxK)進行列向數據壓縮，將二維布局的稀疏矩陣A(MxK)列向壓縮為一維布局的列向壓縮稀疏矩陣A(MxK)；讀取列向壓縮稀疏矩陣A(MxK)第i列以及讀取稠密矩陣B(KxN)第i行外積運算生成ci；對所得到的外積結果進行累加，即可得到稀疏矩陣A(MxK)與稠密矩陣B(KxN)的內積。本發明通過將原有的二維布局的稀疏矩陣A(MxK)列向壓縮為一維布局的列向壓縮稀疏矩陣A(MxK)，除去了稀疏矩陣A(MxK)的零元素值，進而避免了無效數值的計算，達到節省內存訪問和無效運算的目的，從而提高了運算效率。

技術領域

本發明屬于計算機應用技術領域，尤其涉及一種外積累加求解稀疏矩陣與稠密矩陣內積的方法。

背景技術

矩陣內積乘法是數值計算、機器學習、工程模擬等眾多領域算法的基礎，而稀疏矩陣A(MxK)與稠密矩陣B(KxN)內積乘法是一類常見的計算場景。稀疏矩陣A(MxK)與稠密矩陣B(KxN)，其特點在于稀疏矩陣A其中存在一定量的零元素。這部分零元素是可以不參與計算依然保證運算結果的正確性，同時對于零元素可以直接放棄存儲來提升內存的利用效率。

但是在計算和存儲的過程中對稀疏矩陣A之中零元素的忽略導致內存訪問的不連續，不利于利用現代處理器架構中的各級高速緩存。因而涉及稀疏矩陣內積的計算效率低于稠密矩陣A與稠密矩陣B的內積。

此處以現有常規方法外積累加求解稀疏矩陣A(4x4)與稠密矩陣B(4x3)的內積舉例，稀疏矩陣A(4x4)是一般稀疏矩陣，其特點是零元素的分布沒有規律。圖1是稀疏矩陣A(4x4)與稠密矩陣B(4x3)內積計算按照外積之和累加方式求解的第一步。本步中首先取出稀疏矩陣A(4x4)的第一列a1(4x1)與稠密矩陣B(4x3)第一行b1(1x3)執行外積運算得到結果c1，以此類推稀疏矩陣A的第2列a2與周密矩陣B的第2行b2也執行外積運算得到結果c2。稀疏矩陣A(4x4)有四列，稠密矩陣B(4x3)有四行，一一對應外積得到c1(4x3)、c2(4x3)、c3(4x3)、c4(4x3)。c1、c2、c3、c4四個外積結果對應元素相加即得到內積結果。而在一般的矩陣內積乘法中，以稀疏矩陣A(4x4)的第i行內積稠密矩陣B(4x3)第j列得到目標矩陣(i,j)位置的值。完成整個內積的計算，稠密矩陣B(4x3)需要被稀疏矩陣A(4x4)各行重復讀取計算四次。

圖2將稀疏矩陣A(4x4)第一列a1(4x1)與稠密矩陣B(4x3)第一行b1(1x3)外積計算邏輯做個說明。列向量a1(4x1)與行向量b1(1x3)外積結果構成4行3列的矩陣c1。其計算的過程等價于取列向量a1的各個元素分別乘以行向量b1。稀疏矩陣A(4x4)第i列ai(4x1)與稠密矩陣B(4x3)第i行bi(1x3)外積結果ci的計算同c1計算的邏輯。

圖3說明了上述外積結果c1、c2、c3、c4四個矩陣相加的過程，矩陣相加遵循數學中對應元素相加的過程。如此也就求解出了稀疏矩陣A(4x4)與稠密矩陣B(4x3)內積結果。可以看到上述外積累加求解稀疏矩陣A(4x4)與稠密矩陣B(4x3)內積過程中，并沒有專門考慮稀疏矩陣A(4x4)的零元素與稠密矩陣B的某一行外積相乘后，生成一個零向量。該零向量若是不計算，同時也不參與后面累加過程，不影響內積結果的正確性。但是在現有的外積累加計算中，稀疏矩陣中的零元素參與了外積計算，其不僅降低了外積運算的計算效率也增加了外積計算后零值向內存寫入的需求，進而減少了內存寫入的有效帶寬。

發明內容

本發明針對上述的稀疏矩陣A(MxK)與稠密矩陣B(KxN)內積乘法所存在的技術問題，提出一種方法簡單且能夠有效避免無效運算、節省內存訪問的一種外積累加求解稀疏矩陣與稠密矩陣內積的方法。

為了達到上述目的，本發明采用的技術方案為，一種外積累加求解稀疏矩陣與稠密矩陣內積的方法，包括以下有效步驟：