[發明專利]稀疏矩陣乘法在可重構處理器陣列上的實現方法及裝置

有效

• 申請號: 202011508930.X
• 申請日: 2020-12-18
• 公開（公告）號: CN112507284B
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 尹首一;楊軻翔;谷江源;韓慧明;劉雷波;魏少軍
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/16
• 分類號: G06F17/16;G06F7/523
• 代理公司: 北京三友知識產權代理有限公司 11127
• 代理人: 薛平;周曉飛

本發明公開了一種稀疏矩陣乘法在可重構處理器陣列上的實現方法及裝置，其中，該方法包括：采用列壓縮格式存儲待乘法運算的第一稀疏矩陣和第二稀疏矩陣，得到第一稀疏矩陣和第二稀疏矩陣中非零元素的數值數組、行號數組和列偏移數組；通過可重構處理器陣列中的多個處理器，采用列優先法對第一稀疏矩陣和第二稀疏矩陣中的非零元素執行乘法運算，得到多個壓縮列，其中，每個壓縮列包括一個數值數組和一個行號數組；通過可重構處理器陣列中的多個處理器，采用雙調排序歸并法對執行乘法運算后的多個壓縮列進行歸并處理，得到第一稀疏矩陣和第二稀疏矩陣的乘法運算結果。本發明能夠在可重構處理陣列上高效實現稀疏矩陣乘法。

技術領域

本發明涉及可重構計算領域，尤其涉及一種稀疏矩陣乘法在可重構處理器陣列上的實現方法及裝置。

背景技術

本部分旨在為權利要求書中陳述的本發明實施例提供背景或上下文。此處的描述不因為包括在本部分中就承認是現有技術。

近年來，逐漸增長的數據量對計算芯片的功耗和性能提出了越來越高的要求。在過去的幾十年間，隨著摩爾定律的延續，半導體行業和處理器的性能都在迅速發展。然而，摩爾定律即將走到盡頭，但人們對算力、性能和功耗的需求仍未停止，對最新一代設備，對更高性能和更低功耗的要求變得越來越嚴格。新型芯片架構應當能夠執行多種應用，同時保持低功耗、小面積和較短的上市時間。

基于傳統馮諾依曼架構的通用處理器具有最高的靈活性，能夠勝任不同種類算法和任務的需求。然而，通用處理器每條指令執行時都需要經過取指、譯碼的過程，訪問指令存儲器的開銷非常大，指令的串行執行也為流水帶來了一定的困難，需要通過停頓(Stall)、沖刷(Flush)等方式實現，而且會有性能上的損失。盡管人們通過超長指令字、超標量處理器等方式，在一定程度上提高了指令的并行性，但仍未從根本上改變通用處理器功耗大、性能低的問題。另外，由于摩爾定律接近終結，通用處理器將面臨著巨大挑戰。

相比于通用處理器，專用集成電路(ASIC)將指令固化到芯片上，通過數據流驅動芯片運行，由于無需取指譯碼，ASIC具有極高的能量效率和運算速度，但也正是由于指令被固化，芯片只能執行單一應用，實現單一功能。ASIC的問題并不只在于此，芯片流片所需要的一次性工程費用(NRE)成本也很高，通用處理器銷量很高，NRE分攤到每顆芯片上時就很低了，但ASIC往往只局限于某些特殊應用，銷量難以分攤NRE成本，因此，ASIC目前主要在通信基帶、網絡流處理等方面得到使用。

可重構計算是為了解決能量效率和靈活性之間的矛盾而出現的。可重構計算處理器包括一個主處理器和一個可重構硬件，處理器提供靈活性，通過控制可重構硬件的行為來切換不同的功能；硬件在重構后，數據流在其中流動時受硬件暫時固化的指令而非通用處理器控制，因而具有準ASIC的性能。可重構芯片的靈活性和能量效應介于通用處理器和ASIC之間，在性能和靈活性上達到折衷的同時也確保了成本不會過高。

可重構處理器由可重構數據通路和可重構控制器組成。可重構數據通路通常采用許多基本處理單元(PE)組成的陣列結構，每個PE的功能都與通用處理器的算術邏輯單元(ALU)相似，但又不局限于ALU的功能，例如，部分PE具有訪存功能，可以獨立完成訪存操作。此外PE間具有獨特的互聯結構，可以實現中間結果在不同PE間的轉發和傳遞，從而實現復雜的運算功能，有的設計中還具有脈動陣列結構，可以實現數據復用和脈動傳遞，減少訪存操作的次數。由于PE在ALU的基礎上附加了訪存、路由(Route)等功能，而且數據來源相比ALU也拓展到了有路由的PE，傳統指令集很難完全描述每個PE的功能，因此動態可重構處理器通過配置信息控制其行為。在PE進行計算的同時，可重構控制器加載配置信息，發送給各個PE，PE完成當前計算任務后即可加載新的配置信息，切換到不同的功能。相比靜態可重構處理器，這種方式減輕了重新配置的時間代價，而且具有很高的靈活性，但相應的會帶來功耗上的增加。