[發明專利]一種基于圖計算加速器的稀疏矩陣列向量比較裝置

有效

• 申請號: 201910877555.7
• 申請日: 2019-09-17
• 公開（公告）號: CN110598175B
• 公開（公告）日: 2021-01-01
• 發明（設計）人: 鄧軍勇;田璞;楊博文;趙一迪
• 申請（專利權）人: 西安郵電大學
• 主分類號: G06F17/16
• 分類號: G06F17/16;G06F15/163
• 代理公司: 北京易捷勝知識產權代理事務所(普通合伙) 11613
• 代理人: 齊勝杰;李會娟

本發明公開一種基于圖計算加速器的稀疏矩陣列向量比較裝置，包括：N個比較運算電路，比較向量的所有非零元素輸入第一個比較運算電路；目標向量的所有非零元素分別輸入至N個比較運算電路；每一個比較運算電路包括：操作電路、直接輸出模塊和中間輸出模塊；每一個操作電路將比較向量的全部或部分非零元素和輸入至比較運算電路的目標向量的一個非零元素進行比較；N個比較運算電路通過中間輸出模塊、直接輸出模塊依次連接，第n?1個比較運算電路的中間輸出模塊、直接輸出模塊的結果分別輸入至第n個比較運算電路；最后一個比較運算電路輸出稀疏矩陣列向量比較后的結果向量，解決了現有技術中沒有對兩個稀疏矩陣列向量的比較裝置的缺陷。

技術領域

本發明涉及一種圖計算加速器技術，特別涉及一種基于圖計算加速器的稀疏矩陣列向量比較裝置。

背景技術

隨著社交網絡等新型互聯網應用的興起和各種電子設備的普及，圖計算、尤其是大規模圖計算的相關應用日益成為學術界和工業界的研究熱點，從技術、應用及自主知識產權等角度看圖計算加速器的研發都勢在必行。在圖計算加速器的設計過程中，需要考慮經CSCI(Compressed Sparse Column Independently，獨立稀疏列壓縮)壓縮過的稀疏矩陣列向量比較的高效實現。在這里，每一個稀疏矩陣列向量中的每個非零元素按照CSCI格式壓縮成一個個的數據對，每一個數據對結構包括：(索引index，數值value)。

當前，矩陣中非零元素的個數遠遠小于矩陣元素的總數，并且非零元素的分布沒有規律，則該矩陣為稀疏矩陣，與之相反，若非零元素數目占大多數時，則稱該矩陣為稠密矩陣。對于稠密矩陣列向量的運算，需要將矩陣的所有元素進行存儲，在進行兩個稠密矩陣列向量運算時，直接對相同行的元素進行運算。

然而，現有技術中沒有提供任何可以高效實現兩個稀疏矩陣列向量的比較運算的裝置。

發明內容

本發明的目的是提供一種基于圖計算加速器的稀疏矩陣列向量比較裝置，用于解決現有技術中沒有對兩個稀疏矩陣列向量的比較裝置的缺陷。

為了達到上述的目的，本發明采用的主要技術方案包括：

第一方面，本發明提供一種基于圖計算加速器的稀疏矩陣列向量比較裝置，所述稀疏矩陣列向量包括：至少一個比較向量和至少一個目標向量，其中，所述裝置包括：

N個比較運算電路，所述比較運算電路的數量大于所述稀疏矩陣中列向量的非零元素的最大個數；

針對每一個比較向量，所述比較向量的所有非零元素輸入第一個比較運算電路；

針對每一個目標向量，所述目標向量的所有非零元素分別輸入至N個比較運算電路；

每一個比較運算電路包括：操作電路、直接輸出模塊和中間輸出模塊；其中，每一個比較運算電路的操作電路用于將比較向量的全部或部分非零元素和輸入至比較運算電路的目標向量的一個非零元素進行比較；

N個比較運算電路通過中間輸出模塊、直接輸出模塊依次連接，具體地，第n-1個比較運算電路的中間輸出模塊、直接輸出模塊的結果分別輸入至第n個比較運算電路；n屬于N的元素；

第n個比較運算電路的操作電路對第n-1個比較運算電路的直接輸出模塊的結果進行透傳，第n個比較運算電路的操作電路對第n-1個比較運算電路的中間輸出模塊的結果進行處理；

最后一個比較運算電路輸出稀疏矩陣列向量比較后的結果向量。

可選地，針對第一個比較運算電路的操作電路，基于比較策略將比較向量的所有非零元素和目標向量的第一個非零元素進行比較；