趙志建

（江蘇聯(lián)合職業(yè)技術(shù)學(xué)院 南京工程分院，南京 211135）

0 引言

矩陣相乘作為數(shù)值分析統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)中最為常見的數(shù)學(xué)運(yùn)算，在FEA 平衡方程、線性回歸、決策樹、樸素貝葉斯等等的求解上都可以分解成系列矩陣相乘或者矩陣乘向量的運(yùn)算。在深度學(xué)習(xí)領(lǐng)域，常用的卷積（Convolution）、全連接、批歸一化（Batch-Normalization）、下采樣（MaxPooling）等計(jì)算機(jī)視覺中常用算子操作也都離不開矩陣相乘運(yùn)算。常用的編解碼器（Encoder -Decoder）、注意力機(jī)制（Multi-Head Attention）等自然語言處理中的基本算子依舊離不開矩陣相乘運(yùn)算。

隨著矩陣維度的激增，傳統(tǒng)單CPU 矩陣相乘算法的高復(fù)雜度帶來了巨大的性能瓶頸，為了緩解單線程大矩陣相乘運(yùn)算的耗時(shí)問題，一種基于共享內(nèi)存的多線程并發(fā)機(jī)制應(yīng)運(yùn)而生。通過將大矩陣相乘任務(wù)劃分給多個(gè)子線程，提高計(jì)算性能；另一種是將大矩陣劃分成多個(gè)子模塊單獨(dú)相乘后再相加，以減少內(nèi)存訪問次數(shù)，提高性能。但是就目前而言，深度學(xué)習(xí)的應(yīng)用正日趨普及，大矩陣相乘的運(yùn)算量突增，對(duì)于實(shí)時(shí)性要求很高的人臉識(shí)別、無人駕駛、醫(yī)療影像分割等應(yīng)用來說，傳統(tǒng)CPU 平臺(tái)實(shí)現(xiàn)的矩陣運(yùn)算已無法滿足需求，亟需一種更加高效的并行計(jì)算模式打破該性能瓶頸。

英偉達(dá)工智能計(jì)算公司首次定義了GPGPU 概念，并提出了CUDA（Compute Unified Device Architecture）并行計(jì)算架構(gòu)，同時(shí)支持硬件和軟件。CUDA 可利用圖形處理器中的多顆計(jì)算核心進(jìn)行通用計(jì)算處理，計(jì)算性能顯著提升，包含CUDA 指令集架構(gòu)（ISA）以及GPGPU 內(nèi)部的并行計(jì)算引擎，還方便開發(fā)人員直接使用C 語言來為CUDA 架構(gòu)編寫程序，并在支持CUDA 的GPGPU 流處理器（Stream Multiprocessor，SM）上以超高性能實(shí)現(xiàn)運(yùn)行。CUDA 并行計(jì)算架構(gòu)的問世，使得矩陣運(yùn)算性能得到質(zhì)的飛躍。本文通過使用CUDA 來做矩陣相乘運(yùn)算，并充分利用SM 資源對(duì)其性能進(jìn)行優(yōu)化，且在不同GPGPU 硬件平臺(tái)上針對(duì)不同優(yōu)化算法做了充分的實(shí)驗(yàn)對(duì)比及性能分析。

1 相關(guān)工作

1.1 矩陣乘積定義

矩陣相乘是一種將2 個(gè)矩陣乘積運(yùn)算，得到第3 個(gè)矩陣的二元運(yùn)算。設(shè)A為M×K的矩陣，B為K×N的矩陣，那么稱M×N的矩陣C為矩陣A與B的乘積，記作C＝AB，其中矩陣C的第i行第j列如公式（1）所示：

1.2 并行計(jì)算架構(gòu)簡(jiǎn)介

CPU 實(shí)現(xiàn)的并行計(jì)算大多依據(jù)多處理器共享內(nèi)存機(jī)制進(jìn)行多線程并行編程，典型的框架包括MPI（Message Passing Interface），OpenMP（Open Multi-Processing），TBB（Intel Threading Building Blocks），OpenCL（Open Computing Language）等。

目前，主流的GPGPU 實(shí)現(xiàn)的并行計(jì)算架構(gòu)有CUDA 架構(gòu)、ROCM、OpenCL 等。NVIDIA 提出的GPGPU 作為現(xiàn)如今最為流行的并行框架，其整體結(jié)構(gòu)主要由大量的SM 和DRAM 存儲(chǔ)等構(gòu)成，每個(gè)SM又由大量計(jì)算核（又稱CUDA 核）、LDU（Load-Store Units）、SFU（Special-Function Units）、寄存器、共享內(nèi)存等構(gòu)成。GPGPU 具有高并行度計(jì)算能力的基礎(chǔ)，每個(gè)SM 支持?jǐn)?shù)百線程并發(fā)執(zhí)行，每個(gè)GPGPU通常有多個(gè)SM，所以一個(gè)GPGPU 可以并發(fā)執(zhí)行數(shù)千線程。CUDA 采用和CPU 編程中常見的單指令多數(shù)據(jù)（SIMD）架構(gòu)類似的單指令多線程（SIMT）架構(gòu)來管理和執(zhí)行線程，每32 個(gè)線程為一組，被稱為線程束。一個(gè)線程塊只能在一個(gè)SM 上被調(diào)度，而且一旦線程塊在一個(gè)SM 上被調(diào)度，就會(huì)保存在該SM 上直到執(zhí)行完成。需要注意的是，這2 種層級(jí)并不是完全一一對(duì)應(yīng)的，比如在同一時(shí)間，一個(gè)SM 可以容納多個(gè)線程塊。

在SM中，共享內(nèi)存和寄存器是非常重要的資源。共享內(nèi)存被分配在SM 上的常駐線程塊中，寄存器在線程中被分配。線程塊中的線程通過這些資源可以進(jìn)行相互的合作和通信。盡管線程塊里的所有線程都可以邏輯地并行運(yùn)行，但并不是所有線程都可以同時(shí)在物理層面執(zhí)行。因此線程塊中的不同線程可能會(huì)有不同的運(yùn)行速度，且在需要時(shí)可以使用CUDA 語句進(jìn)行線程的同步。

1.3 內(nèi)存優(yōu)化算法

在大多數(shù)GPGPU 應(yīng)用程序中，性能優(yōu)化的關(guān)鍵點(diǎn)在于如何高效訪問內(nèi)存，尤其共享內(nèi)存的合理分配使用。

典型的GPGPU 內(nèi)存優(yōu)化算法包括共享內(nèi)存優(yōu)化、內(nèi)存合并優(yōu)化、內(nèi)存沖突優(yōu)化等。共享內(nèi)存相較于全局內(nèi)存而言，延遲要低上大約20～30倍，而帶寬要高出約10倍，因此合理分配共享內(nèi)存是性能優(yōu)化的關(guān)鍵。矩陣分塊思想與CPU 矩陣分塊思想相同。對(duì)齊訪問含義就是如果“內(nèi)存事務(wù)”（32 和128字節(jié)兩種）的訪問首地址是緩存粒度（L1 的128 字節(jié)或L2 緩存的32 字節(jié)）的偶數(shù)倍，即實(shí)現(xiàn)了對(duì)齊訪問。在L1 緩存的情況下，由“128 字節(jié)內(nèi)存事務(wù)”進(jìn)行訪問，如果一個(gè)線程束訪問的地址是連續(xù)的128 字節(jié)，且首地址又是128 的倍數(shù)，那么這種訪問就稱為合并訪問，內(nèi)存合并對(duì)齊訪問對(duì)性能提升起著關(guān)鍵作用。往往為了獲得較高的內(nèi)存帶寬，共享內(nèi)存被劃分成了多個(gè)大小相等的存儲(chǔ)器模塊，稱為bank。內(nèi)存bank 沖突表示當(dāng)一個(gè)線程束中的不同線程訪問一個(gè)bank 中的不同的字地址時(shí)，就會(huì)發(fā)生bank 沖突。如若沒有bank 沖突，共享內(nèi)存的訪存速度將會(huì)非?？?，而如果在使用共享內(nèi)存時(shí)發(fā)生了bank 沖突的話，性能將會(huì)降低很多，所以避免內(nèi)存bank 沖突尤為重要。不同于內(nèi)存優(yōu)化，循環(huán)延展是一種以編程復(fù)雜為代價(jià)來提升并行代碼性能的高級(jí)的編程方式，是一種指令集優(yōu)化，其性能較內(nèi)存優(yōu)化提升更為明顯。

2 CPU 并行優(yōu)化算法

CPU 實(shí)現(xiàn)的矩陣相乘偽代碼，具體見算法1。通過3 個(gè)for 循環(huán)即可完成公式（1）中表達(dá)的矩陣相乘運(yùn)算。

算法1 矩陣相乘串行實(shí)現(xiàn)

2.1 OpenMP 并行優(yōu)化

OpenMP 是基于共享內(nèi)存模型的多線程并行模式，適合于應(yīng)用在單機(jī)多核心平臺(tái)上。程序開始時(shí)只有一個(gè)主線程，程序中的串行部分都由主線程執(zhí)行，并行的部分是通過派生其他線程來執(zhí)行。目前主流編譯器默認(rèn)都已支持OpenMP，只需要在第一個(gè)for 循環(huán)之前加上“＃pragma omp” 語句，表示動(dòng)態(tài)分配線程數(shù)，且保證每個(gè)CPU 線程單獨(dú)并行地完成矩陣點(diǎn)乘任務(wù)。算法實(shí)現(xiàn)偽代碼具體見算法2。

算法2 矩陣相乘并行實(shí)現(xiàn)

2.2 訪存優(yōu)化

無論對(duì)于串行、還是OpenMP 并行實(shí)現(xiàn)都未經(jīng)過任何優(yōu)化，訪存延遲和通信開銷會(huì)隨著維度M，N，K的增加而增大。例如：對(duì)于M＝N＝K的大型方陣，矩陣乘積運(yùn)算次數(shù)為N3、即時(shí)間復(fù)雜度為O（N3），所需的數(shù)據(jù)量為O（N2），從而產(chǎn)生N階的計(jì)算強(qiáng)度。而該算法又依賴于訪存中保存的一個(gè)大工作集，這就使得隨著M、N和K增長(zhǎng)時(shí)，CPU 需要來回傳送數(shù)據(jù)，顯然不符合減小訪存的思想。

C／C++中，默認(rèn)會(huì)按行優(yōu)先儲(chǔ)存數(shù)據(jù)（一維數(shù)組），ijk枚舉順序?qū)?huì)使得內(nèi)層k循環(huán)中B［k，j］＝B［k?K+j］在內(nèi)存中的枚舉出現(xiàn)不連續(xù)、即按列讀取，顯然降低效率。若此時(shí)采用ikj的枚舉順序?qū)⑻岣咴L存效率，偽代碼具體見算法3。

算法3 矩陣相乘訪存優(yōu)化實(shí)現(xiàn)

算法3中，在k循環(huán)中先讀取A［i，k］保存到寄存器變量S中，在內(nèi)層j循環(huán)計(jì)算時(shí)直接讀取S，而B［k，j］和C［i，j］在j循環(huán)中是連續(xù)訪問的。需要指出的是，在外層k循環(huán)中，omp并行后去掉了最外層i循環(huán)，A［i，k］也是連續(xù)讀取的，這樣就極大提高了訪存效率。

2.3 矩陣分塊優(yōu)化

將矩陣乘法的計(jì)算轉(zhuǎn)化為其各自分塊矩陣相乘后相加，能夠有效減少乘數(shù)矩陣和被乘數(shù)矩陣調(diào)入內(nèi)存的次數(shù)，可加快程序運(yùn)行速度。矩陣分塊優(yōu)化思想如圖1 所示，通過將原始矩陣進(jìn)行分塊，并將每個(gè)分塊看作另一個(gè)矩陣的元素參與矩陣乘運(yùn)算，接著將相乘結(jié)果進(jìn)行累加，從而完成一個(gè)矩陣分塊的矩陣乘，其他塊的處理流程也和這個(gè)一樣。

圖1 矩陣分塊優(yōu)化思想Fig.1 Matrix block optimization

3 CUDA 并行優(yōu)化算法

CUDA 允許用戶定義被稱為內(nèi)核（kernel）的C語言函數(shù)，在調(diào)用此類函數(shù)時(shí)，將由N個(gè)不同的CUDA 線程并行執(zhí)行N次，這與普通C 語言函數(shù)只執(zhí)行一次的方式有所不同。在定義內(nèi)核時(shí)，需要使用global 聲明限定符并使用一種全新的＜＜＜…＞＞＞語法啟動(dòng)內(nèi)核，同時(shí)還要指定每次調(diào)用的CUDA 線程數(shù)。通過讓每個(gè)線程對(duì)應(yīng)矩陣C中一個(gè)元素來進(jìn)行計(jì)算，每個(gè)線程從矩陣A中讀取一行向量，從矩陣B中讀取一列向量，對(duì)這2 個(gè)向量做相乘累加運(yùn)算，再將結(jié)果寫回矩陣C。

A、B、C三個(gè)矩陣都保存在GPGPU 的全局內(nèi)存中，每個(gè)線程都進(jìn)行了大量重復(fù)的全局內(nèi)存訪問操作，雖然線程束機(jī)制優(yōu)化了全局內(nèi)存的訪問效率，最大程度實(shí)現(xiàn)了合并訪問，但GPGPU 全局內(nèi)存的讀取速度仍然不高、即帶寬有限。

3.1 共享內(nèi)存優(yōu)化

CUDA 中每個(gè)線程都有自己的私有的全局內(nèi)存和寄存器，用來保存在核函數(shù)內(nèi)不加修飾的聲明的局部變量；線程塊有自己的共享內(nèi)存（Shared Memory），并對(duì)塊內(nèi)所有的線程可見。相較于全局內(nèi)存400～600 個(gè)時(shí)鐘周期的訪問延遲，共享內(nèi)存只有20～30 時(shí)鐘周期訪問延遲，且?guī)捯脖热謨?nèi)存高10倍，極大程度上提高了訪存效率。

共享內(nèi)存優(yōu)化算法的核心思想借鑒了矩陣分塊優(yōu)化思想，通過充分利用數(shù)據(jù)的局部性，讓一個(gè)線程塊內(nèi)的子線程先從全局內(nèi)存中讀取分塊矩陣數(shù)據(jù)，并寫入到共享內(nèi)存中，在計(jì)算時(shí)，直接從共享內(nèi)存中讀取分塊數(shù)據(jù)進(jìn)行矩陣乘和累加操作，從而大大降低了訪問延遲。接下來，讓子矩陣塊分別在矩陣A的行向以及矩陣B的列向上滑動(dòng)，直到計(jì)算過所有N個(gè)元素的相乘累加為止。

3.2 合并內(nèi)存優(yōu)化

內(nèi)存優(yōu)化的目標(biāo)在于通過更少的內(nèi)存事務(wù)獲得更多的內(nèi)存請(qǐng)求，因此需要盡量進(jìn)行對(duì)齊合并訪問。內(nèi)存合并訪問是指所有線程訪問連續(xù)且對(duì)齊的內(nèi)存塊，內(nèi)存塊大小支持32 字節(jié)、64 字節(jié)以及128 字節(jié)，分別表示線程束中每個(gè)線程以一個(gè)字節(jié)（1×32＝32）、16 位（2×32＝64）、32 位（4×32＝128）為單位讀取數(shù)據(jù)。

以合并內(nèi)存訪問128 字節(jié)為例，每個(gè)線程讀取一個(gè)浮點(diǎn)變量，那么一個(gè)線程束（32 個(gè)線程）將會(huì)執(zhí)行32×4＝128 字節(jié)的合并訪存指令，通過一次訪存操作完成所有線程的讀取請(qǐng)求，其緩存有效利用率達(dá)到128／128＝100%，如圖2 所示。

圖2 合并內(nèi)存訪問Fig.2 Coalesced memory access

非合并內(nèi)存訪問的對(duì)比如圖3 所示，128 字節(jié)的數(shù)據(jù)沒有進(jìn)行內(nèi)存對(duì)齊，首地址位于96～128 字節(jié)之間，為了訪問128 字節(jié)之前的數(shù)據(jù)，必須訪問從0～127 字節(jié)的整段內(nèi)存，其緩存的有效利用率僅有一半，128／256＝50%。

圖3 非合并內(nèi)存訪問Fig.3 Non-coalesced memory access

3.3 內(nèi)存沖突優(yōu)化

往往為了獲得較高的內(nèi)存帶寬，共享內(nèi)存被劃分成了多個(gè)大小相等的存儲(chǔ)器模塊，稱為bank。一個(gè)bank 內(nèi)對(duì)多個(gè)地址進(jìn)行讀取和寫入的操作可以同時(shí)進(jìn)行，大大提高了整體帶寬。當(dāng)每個(gè)線程訪問一個(gè)32 位大小的數(shù)據(jù)類型的數(shù)據(jù)（如int，float）時(shí)，就不會(huì)發(fā)生bank 沖突，例如圖4 呈現(xiàn)了一種非內(nèi)存bank 沖突的場(chǎng)景。

圖4 非內(nèi)存bank 沖突Fig.4 Non-memory bank conflict

但是很多情況下，無法充分發(fā)揮bank 的作用，以致于共享內(nèi)存的帶寬受阻，這可能是因?yàn)橛龅搅薭ank 沖突。例如，當(dāng)同一個(gè)線程束中不同線程去訪問共享內(nèi)存中同一個(gè)bank 的不同字地址時(shí)，就會(huì)發(fā)生bank 沖突，例如圖5 中同一個(gè)線程束中多個(gè)線程訪問了Bank 0 的數(shù)據(jù)。

圖5 內(nèi)存bank 沖突Fig.5 Memory bank conflict

避免內(nèi)存bank 沖突常用的優(yōu)化思路有2 個(gè)：

（1）典型的線程訪問方式：每個(gè)線程束的線程和每個(gè)bank 的ID 一一對(duì)應(yīng)或者每個(gè)線程對(duì)應(yīng)唯一的bank。

（2）多播機(jī)制：當(dāng)一個(gè)線程束中的多個(gè)線程同時(shí)訪問一個(gè)bank 的相同字地址時(shí)，會(huì)將該字廣播給這些線程，從而也不會(huì)產(chǎn)生bank 沖突。

3.4 循環(huán)延展優(yōu)化

循環(huán)延展（Loop Unrolling）不同于內(nèi)存優(yōu)化，是一種指令級(jí)優(yōu)化。前面提到的所有優(yōu)化算法實(shí)現(xiàn)都離不開for 循環(huán)的運(yùn)用，而實(shí)際上for 循環(huán)是一種以犧牲計(jì)算性能為代價(jià)的編程思路。

循環(huán)延展優(yōu)化思想的提出，主要是為了降低循環(huán)開銷，為具有多個(gè)功能單元的處理器提供指令集并行，同時(shí)也有利于指令流水線的調(diào)度。目前基于CUDA 編程的編譯器默認(rèn)都已支持循環(huán)延展化，其實(shí)現(xiàn)方式和OpenMP 并行優(yōu)化算法類似，只需在for循環(huán)前添加“＃pragma unroll”語句，編譯器將會(huì)識(shí)別該語句，自動(dòng)對(duì)其進(jìn)行展開，而后并發(fā)去執(zhí)行。具體偽代碼見算法4。

算法4 矩陣相乘循環(huán)延展優(yōu)化

4 性能分析

在不同設(shè)備上進(jìn)行M＝N＝K＝2 048 階矩陣相乘及優(yōu)化算法的性能對(duì)比，矩陣相乘CPU 并行算法的性能對(duì)比見表1。明顯看出基于OpenMP 并行優(yōu)化實(shí)現(xiàn)算法稍優(yōu)于串行算法；矩陣相乘分塊優(yōu)化算法明顯優(yōu)于未分塊算法；最優(yōu)的仍是訪存優(yōu)化算法帶來的性能提升。因此，內(nèi)存優(yōu)化一直是性能瓶頸的難點(diǎn)、也是挑戰(zhàn)。

表1 矩陣相乘CPU 并行優(yōu)化算法性能對(duì)比Tab.1 Performance comparison of matrix multiplication CPU parallel optimization algorithm ms

從表1 明顯看出，雖然基于CPU 的并行優(yōu)化算法較串行算法有了很大提升，但運(yùn)行時(shí)間仍然較長(zhǎng)，最優(yōu)矩陣相乘訪存優(yōu)化算法也需18.4 s，這個(gè)時(shí)間明顯無法滿足實(shí)時(shí)性應(yīng)用需求。

基于CUDA 并行優(yōu)化矩陣相乘算法的運(yùn)行時(shí)間，見表2。

表2 矩陣相乘CUDA 并行優(yōu)化算法性能對(duì)比Tab.2 Performance comparison of matrix multiplication CUDA parallel optimization algorithm

由表2 明顯看出，未經(jīng)任何優(yōu)化的CUDA 并行算法比CPU 實(shí)現(xiàn)的最快訪存優(yōu)化算法提升了400倍之余。盡管原生CUDA 矩陣相乘實(shí)現(xiàn)算法得到了性能上的飛躍，但原生實(shí)現(xiàn)并沒有真正充分利用GPGPU 硬件資源，利用率往往達(dá)不到100%。通過使用共享內(nèi)存優(yōu)化的矩陣分塊優(yōu)化算法，性能得到了明顯提高，這是因?yàn)楣蚕韮?nèi)存訪問帶寬明顯高于全局內(nèi)存。其次，在CUDA 內(nèi)存使用中，經(jīng)常會(huì)遇到內(nèi)存并非對(duì)齊、內(nèi)存bank 沖突等現(xiàn)象，通過使用NVIDIA 提供的nvprof 和nvvp 性能分析工具可以發(fā)現(xiàn)內(nèi)存使用中存在的問題。通過內(nèi)存合并對(duì)齊優(yōu)化之后的性能較未優(yōu)化實(shí)現(xiàn)有很大提升，解決了內(nèi)存bank 沖突后也得到了部分性能提升。除此之外，還發(fā)現(xiàn)通過指令集優(yōu)化的循環(huán)延展方法性能最為出色，這點(diǎn)得益于編譯器優(yōu)化。

5 結(jié)束語

隨著GPGPU 的普及，陸續(xù)推出了CUDA、ROCM、OpenCL 等并行計(jì)算架構(gòu)，不僅解決了CPU低算力帶來的高延時(shí)，同時(shí)還為高實(shí)時(shí)性要求的人工智能應(yīng)用提供了強(qiáng)有力的支撐。本文借用CPU平臺(tái)和當(dāng)今主流的CUDA 并行計(jì)算架構(gòu)實(shí)現(xiàn)了數(shù)學(xué)領(lǐng)域常用的矩陣相乘并行計(jì)算，并對(duì)其進(jìn)行了有效的性能優(yōu)化，提高了利用率，從而能夠充分利用GPGPU 硬件資源。實(shí)驗(yàn)結(jié)果表明，合理使用共享內(nèi)存優(yōu)化、指令集編譯器優(yōu)化能帶來明顯的性能提升。