[發(fā)明專利]自共軛矩陣的上三角部分存儲裝置和并行讀取方法

有效

• 申請?zhí)枺?/td>: 201811315346.5
• 申請日: 2018-11-06
• 公開（公告）號: CN109558567B
• 公開（公告）日: 2020-08-11
• 發(fā)明（設(shè)計）人: 劉大可;劉劭晗
• 申請（專利權(quán)）人: 海南大學(xué)
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩;吳歡燕

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

技術(shù)領(lǐng)域

本發(fā)明實施例涉及矩陣運算技術(shù)領(lǐng)域，更具體地，涉及自共軛矩陣的上三角部分存儲裝置和并行讀取方法。

背景技術(shù)

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

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

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

發(fā)明內(nèi)容

為了解決現(xiàn)有技術(shù)中存在的受限于三角矩陣的行列向量數(shù)據(jù)存取的并行度不高，導(dǎo)致硬件利用率和矩陣運算算法效率不高的問題，本發(fā)明實施例提供自共軛矩陣的上三角部分存儲裝置和并行讀取方法。

根據(jù)本發(fā)明實施例的一個方面，提供一種自共軛矩陣的上三角部分存儲裝置，包括：

存儲模塊選擇電路，用于確定待存取的自共軛矩陣上三角部分各元素對應(yīng)的存儲模塊；

地址生成電路，用于計算所述待存取的自共軛矩陣上三角部分各元素在其對應(yīng)的存儲模塊中的邏輯地址；

并行的m個存儲模塊，用于存儲所述待存取的自共軛矩陣上三角部分各元素所對應(yīng)的數(shù)據(jù)；

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

取共軛模塊，用于對經(jīng)過混洗后的數(shù)據(jù)進行旁路操作和取共軛操作；

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