[發明專利]基于矩陣運算的并行計算方法

無效

• 申請號: 201010508334.1
• 申請日: 2010-10-15
• 公開（公告）號: CN101980182A
• 公開（公告）日: 2011-02-23
• 發明（設計）人: 汪玉;吳天際;楊華中
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 北京中偉智信專利商標代理事務所 11325
• 代理人: 張岱

技術領域

本發明涉及一種計算機并行計算領域。

背景技術

如今，并行計算已經成為計算性能提升的最重要方式之一。近年來，一些大規模并行計算單元，被廣泛應用到通用計算領域中。這些大規模并行計算單元在計算機中央處理器的控制下，協助完成計算任務，可以大大提高整個計算任務的完成效率。圖形處理單元(GPU，Graphics?Processing?Unit)就是一種大規模并行計算單元(下文簡稱加速器)，它不僅可以完成圖形渲染相關的運算，也可以完成與圖形無關的通用計算。和通用處理器相比，圖形處理單元有著極高的浮點運算性能。另外，可編程邏輯器也是一種加速器，使用者可以針對具體的應用需求自定義硬件電路結構，設計出高效、專用的并行處理單元。

目前，各種加速器技術的發展均逐漸成熟，而如何快速、高效地實現并行算法就成為了并行計算領域中的關鍵問題。盡管多數平臺都有完善的開發工具，但對于程序員來說，開發高效的并行加速程序仍然是一項很艱巨的任務。任務和難點主要表現為以下幾點：(1)如何實現算法的并行化；即發現和挖掘串行算法中的并行性。(2)如何將并行算法映射到具體加速器編程模型中，以及如何進行代碼實現。不同的映射方式往往可以導致非常大的性能差異，因此，實現最佳的映射需要程序員對加速器底層硬件結構有一定了解，并做出針對性的優化。(3)需要編寫大量的調度代碼。由于各種加速器的開發工具均考慮到盡可能高的通用性，因此其應用編程接口相對底層。使用這些開發工具，需要編寫大量控制代碼來控制加速器的運行。

發明內容

針對上述的問題，本發明提供一種并行算法實現簡單，且能夠簡化并行加速程序開發的基于矩陣運算的并行計算方法。

為達到上述目的，本發明基于矩陣運算的并行計算方法，包括以下步驟：

定義矩陣運算算式；

將待描述算法描述為由至少兩個矩陣運算構成的算式；

定義參與運算的矩陣及矩陣的表達方式；

定義矩陣運算中的標量算子；

執行矩陣運算。

其中，所述的矩陣運算算式包括抽象矩陣加法運算算式和抽象矩陣減法運算算式。

所述的參與運算的矩陣為由同一類元素構成的二維陣列；其中，所述元素為數字，或數據結構體。

所述的矩陣的表達方式為BUF方式，或XY方式，或CSR方式，或CSC方式。

所述的標量算子包括抽象加法算子和/或抽象乘法算子。

進一步地，所述的執行矩陣運算，具體實現如下：

將矩陣運算映射到加速器編程模型中；

加速器執行運算；

輸出結果。

本發明提出的并行計算方法涉及以下兩個主要步驟：以矩陣運算方式表述算法；然后執行矩陣運算。本發明將參與計算的數據抽象為具有某種元素類型的矩陣，然后，將計算任務抽象為具有某種元素類型的各矩陣之間的抽象乘法算子和/或抽象加法算子。本發明所述基于矩陣運算的并行計算方法利用矩陣運算規則來表述算法的并行性，從而降低了描述并行算法的難度。同時，基于推廣的矩陣運算來實現并行算法，可以盡可能地排除具體算法的特點，實現較為通用的并行算法到加速器的映射，可以針對常用的矩陣運算設計調度軟件，使得軟件可以較普遍地適合于多種算法。

本發明具有以下幾點有益的效果：

(1)本發明利用矩陣運算規則來描述并行計算算法，利用矩陣運算中固有的并行性來表達其描述的算法的并行性，思路簡單明確，無需再去發現和挖掘串行算法中的并行性。

(2)本發明將非矩陣運算的算法轉換為基于矩陣運算的算法。由于矩陣運算有內在的并行性，可以方便高效地映射到加速器的并行編程模型上，因此使用本發明可以有效地簡化挖掘算法并行性，以及將其映射到加速器的工作。

(3)本發明執行矩陣運算的過程只與原算法的矩陣運算表述有關，而與原算法本身無關。因此，可以針對常用的矩陣運算設計調度軟件，使得軟件可以較普遍地適合于多種算法。從而，本方法減少了開發加速器調度代碼的重復工作，簡化了開發過程。

(4)本發明將算法的描述和其在并行系統上的實現拆分開來，形成兩個層次。即，算法本身的描述在第一個層次，它不涉及如何在特定硬件上實現計算過程；針對特定硬件的計算過程的實現和性能優化在第二個層次，它與算法本身無關，因此實現和優化的工作是可重用的。采用本發明的方法來實現具體算法，只需要在第一個層次上完成算法的描述，所需編寫的代碼量非常少。

附圖說明

圖1為本發明所述本發明所述基于矩陣運算的并行計算方法的流程圖。

具體實施方式

下面結合說明書附圖對本發明的具體實施方式做詳細描述。