[發明專利]對稱矩陣的三角部分存儲裝置和并行讀取方法

有效

• 申請號: 201811315320.0
• 申請日: 2018-11-06
• 公開（公告）號: CN109857982B
• 公開（公告）日: 2020-10-02
• 發明（設計）人: 劉大可;劉劭晗
• 申請（專利權）人: 海南大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;吳歡燕

本發明實施例提供對稱矩陣的三角部分存儲裝置和并行讀取方法，所述裝置包括：存儲模塊選擇電路，用于選擇待存取的對稱矩陣上三角部分或下三角部分各元素對應的存儲模塊；地址生成電路，用于計算待存取的對稱矩陣上三角部分或下三角部分各元素在其對應的存儲模塊中的邏輯地址；并行的m個存儲模塊，用于存儲所述待存取的對稱矩陣上三角部分或下三角部分各元素所對應的數據；數據混洗模塊，用于對從存儲模塊中讀取出的數據進行混洗操作。本發明實施例只需對對稱矩陣的上三角部分或下三角部分進行存儲，并且支持并行讀取并恢復對稱矩陣的任意行向量和列向量，能充分利用硬件的并行計算單元，提高矩陣運算算法效率。

技術領域

本發明實施例涉及矩陣運算技術領域，更具體地，涉及對稱矩陣的三角部分存儲裝置和并行讀取方法。

背景技術

對稱矩陣(Symmetric Matrix)是對稱的方陣，在數字信號處理領域有著廣泛的使用。例如，許多信號檢測算法需要利用實數自相關矩陣得到信號的二階統計特征。對稱矩陣的求解復雜度隨著矩陣階數增加而平方增加，為了減小計算復雜度，可以根據對稱矩陣的對稱特性，只計算對稱矩陣的上(下)三角部分，對稱矩陣的下(上)三角部分可以根據對稱特性由上(下)三角部分求出。并且如果能夠合理的安排對稱矩陣元素在存儲器中的位置，使得在不影響數據并行存取需求的條件下，存儲器只需要保存上(下)三角部分元素的值，那么就可以節省接近一半的數據存儲空間。

但是，對稱矩陣運算，如對稱矩陣乘法和對稱矩陣與向量乘，通常需要并行讀取對稱矩陣的行向量或列向量。這些行列向量通常既包含上三角部分矩陣的元素又包含下三角部分矩陣的元素。對于只保存了上(下)三角部分元素的對稱矩陣，由于上(下)三角矩陣無法包含需要讀取的行列向量的全部元素，需要根據對稱特性對矩陣運算進行特殊的優化才能完成運算功能。現有技術給出了多種矩陣運算優化的方案，具體包括：中國專利CN107590106A公開了一種應用于對稱矩陣與向量乘法的計算方法，利用矩陣分塊和對角矩陣數據擴展的方法進行矩陣向量乘法；第二種方法是根據BLAS(Basic Linear AlgebraSubprograms)庫中的對稱矩陣乘法算法，從算法的最內層循環進行循環展開，并映射到硬件的并行處理單元上；第三種方法是將對稱矩陣分解為上三角矩陣和根據對稱特性生成的下三角矩陣，分別進行矩陣乘法，再將結果矩陣相加。

以上方法均可以應用于對稱矩陣運算。但是第一種方法將上(下)三角矩陣進行數據擴展成為對稱矩陣的過程需要額外的數據搬移和時間開銷。第二種方法通過對原始算法進行并行優化實現了矩陣運算，但是由于最內層循環的循環次數可變且通常較小，導致數據存取的并行度不高，從而降低了硬件利用效率和算法效率。第三種方法雖然有效地減少了計算復雜度，但是仍然受限于并行數據存取的速度，導致硬件利用率和算法的效率不高。

發明內容

為了解決現有技術中存在的受限于三角矩陣的行列向量數據存取的并行度不高，導致硬件利用率和矩陣運算算法效率不高的問題，本發明實施例提供一種對稱矩陣的三角部分存儲裝置和并行讀取方法。

根據本發明實施例的一個方面，提供一種對稱矩陣的三角部分存儲裝置，包括：

存儲模塊選擇電路，用于選擇待存取的對稱矩陣上三角部分或下三角部分各元素對應的存儲模塊；

地址生成電路，用于計算所述待存取的對稱矩陣上三角部分或下三角部分各元素在其對應的存儲模塊中的邏輯地址；

并行的m個存儲模塊，用于存儲所述待存取的對稱矩陣上三角部分或下三角部分各元素所對應的數據；

數據混洗模塊，用于對從所述存儲模塊中讀取出的數據進行混洗操作；

其中，m為所述對稱矩陣的三角部分存儲裝置的硬件并行度。

根據本發明實施例的另一個方面，提供一種基于第一方面所提供的對稱矩陣的三角部分存儲裝置的并行讀取方法，包括：