1、引言

在之前的文章中，帶大家了解了一下指令級(jí)并行即ILP相關(guān)的概念。顯然，除了指令級(jí)別的并行，處理器還存在其它維度的并行。本篇文章給大家?guī)?span>數(shù)據(jù)級(jí)并行中的SIMD技術(shù)。首先我們思考一個(gè)問題，為什么會(huì)誕生數(shù)據(jù)級(jí)并行？單純采用ILP有什么缺點(diǎn)和不足嗎？

我們回顧一下ILP的基本概念，所謂的ILP指的是在一個(gè)處理器內(nèi)部同時(shí)執(zhí)行多個(gè)指令，通常指令級(jí)并行包括流水線、VLIW、亂序超標(biāo)量技術(shù)。由于亂序超標(biāo)量技術(shù)在通用CPU中的統(tǒng)治地位，往往在提到ILP都會(huì)默認(rèn)指的是亂序超標(biāo)量處理器。這些技術(shù)當(dāng)然很好，能夠顯著提高IPC，進(jìn)而提升性能。但I(xiàn)LP并沒有完全挖掘出應(yīng)用所具備的并行性。

我們想一想，所謂的ILP，其實(shí)從本質(zhì)上來說，就是一個(gè)周期多跑一些指令。其在通用處理方面具有很顯著的優(yōu)勢，因?yàn)椴还苁鞘裁闯绦?，都?huì)被編譯成為一條又一條的指令。從每個(gè)周期多執(zhí)行一些指令這個(gè)角度思考自然是沒有錯(cuò)誤的，這是一種非常好的解決范式。

但由此我們又有了一個(gè)新的問題：程序編譯出來的這些指令真的是最好的嗎？某些應(yīng)用真的需要很多條指令才能跑完嗎？有沒有一種可能，應(yīng)用程序本身就是存在并行性的？原本需要一二十條指令的代碼片段，通過特殊的硬件架構(gòu)結(jié)合指令編碼，只需要一兩條指令就可以搞定？答案是肯定的，DLP便是解決此問題的方案之一。除了程序內(nèi)在的并行性挖掘度不夠以外（ILP實(shí)際上沒有利用程序本身存在的并行性），ILP還有以下的一些缺陷：

• 隨著工藝制程的限制，摩爾定律帶來的福利已經(jīng)不再，時(shí)鐘頻率已經(jīng)無法持續(xù)天然提升了；

• 不斷增加流水線級(jí)數(shù)，來提高時(shí)鐘頻率的方式，也隨之帶來了“高頻低能”的問題（branches、hazards）；

• 在科學(xué)計(jì)算、流媒體處理等場景中，由于局部性較差，Cache命中率隨之下降；

同時(shí)隨著科學(xué)計(jì)算、視頻處理、以及新興的機(jī)器學(xué)習(xí)等應(yīng)用越來越廣泛，人們逐漸發(fā)現(xiàn)這些算法通常天然具有數(shù)據(jù)并行的特點(diǎn)。由此便逐漸演化出來了DLP相關(guān)的概念，此概念于70年代被美國電氣工程師Seymour Cray發(fā)揚(yáng)光大，并推出了一系列基于DLP思想的科學(xué)計(jì)算處理器，如CRAY-1、CRAY-2等。我們?cè)谶@里通過Cray先生的一句話，引入我們的主題DLP。

2、SIMD體系結(jié)構(gòu)

典型的DLP技術(shù)包括向量處理器、SIMD、GPU。其中向量處理器和SIMD非常像，并且GPU也是SIMD的變體而已，掌握了SIMD再掌握其它的DLP技術(shù)就簡單多了，因此本篇文章的重點(diǎn)放在SIMD上。

2.1、費(fèi)林分類法

美國計(jì)算機(jī)科學(xué)家Michael J. Flynn于1966年提出了“Flynn's taxonomy”這一概念。簡單粗暴的將計(jì)算機(jī)架構(gòu)分為四種，盡管用今天的眼光看，該分類不是非常準(zhǔn)確，但其仍然可以讓我們?cè)诙虝r(shí)間內(nèi)對(duì)計(jì)算機(jī)做一個(gè)大致分類。

Flynn根據(jù)指令和數(shù)據(jù)是否并行，將計(jì)算機(jī)分為了四大類：

• SISD：單指令單數(shù)據(jù)，低端MCU的處理器基本都是這種，比如Cortex-M0/3；

• SIMD：單條指令操縱多個(gè)數(shù)據(jù)元素，包括Array processor和Vector Processor；

• MISD：多條指令控制單一數(shù)據(jù)，實(shí)際上非常罕見，1-D的脈動(dòng)陣列和它有點(diǎn)類似；

• MIMD：多條指令控制多個(gè)數(shù)據(jù)元素，在超級(jí)計(jì)算機(jī)中非常常見，多線程處理器就是MIMD架構(gòu)；

2.2、SIMD和MIMD的區(qū)別

我們來簡單的對(duì)比一下SIMD和MIMD，這兩者都是并行數(shù)據(jù)流，它們的區(qū)別在哪里呢？

對(duì)于MIMD而言，它的核心思想是多條指令控制多個(gè)數(shù)據(jù)流，其多個(gè)指令流可以是完全獨(dú)立的，因此其對(duì)于需要同時(shí)進(jìn)行多個(gè)不同操作的應(yīng)用非常有用，如分布式計(jì)算等。此外MIMD的靈活性通常較高，因?yàn)槠?span>每個(gè)處理單元可以獨(dú)立地執(zhí)行不同指令。

當(dāng)然MIMD不可能各方面都好，必然是有不足之處，才會(huì)有別的模式的存在（無論是搞工程，還是搞科研都是這樣，你要提出一個(gè)新東西，肯定是另外一個(gè)東西有不足之處，各方面都很完美了那也沒必要提出新的解決方案了）。我們想一想MIMD有什么缺點(diǎn)：

首先，靈活性非常高，那就必然導(dǎo)致設(shè)計(jì)變復(fù)雜，因此“規(guī)律代表簡單”。MIMD需要管理多個(gè)獨(dú)立的指令流和數(shù)據(jù)流，編程和調(diào)度的復(fù)雜性變得很高，這對(duì)于軟件開發(fā)者來說也很困難，與之相比，SIMD允許程序員采用順序思維方式但能獲得并行加速比（體系結(jié)構(gòu)圣經(jīng)中將其稱為SIMD相對(duì)于MIMD的最大優(yōu)勢）。除此之外，MIMD存在同步和通信開銷，資源利用率等一些問題。盡管MIMD存在這些缺點(diǎn)，但它在很多并行計(jì)算中仍然非常有效，通過合理設(shè)計(jì)和優(yōu)化可以克服這些缺點(diǎn)，這些話題我們以后再聊，我們繼續(xù)把視角放回到SIMD上。

我認(rèn)為SIMD相比于MIMD，主要優(yōu)勢在兩個(gè)方面，一個(gè)是在能耗效率方面比MIMD更高效，其針對(duì)每組數(shù)據(jù)操作僅需要取指一次，尤其是對(duì)于PMD（Personal mobile devices）等非常在意功耗的場景，SIMD大有用武之地。此外就是前面提到的，SIMD允許程序員采用順序思維方式并獲得并行加速比。有過并行程序開發(fā)經(jīng)驗(yàn)的朋友都知道，并行程序?qū)懫饋硎欠浅＠щy的，存在競爭、死鎖等一系列問題。需要考慮的問題很多，而SIMD不需要考慮這些，你執(zhí)行的就是一條指令而已。

2.3、向量處理器

談到SIMD，必然繞不開向量處理器?，F(xiàn)在很多地方對(duì)這兩個(gè)概念非常摳字眼，我覺得沒必要區(qū)分的特別明顯，可以簡單這么理解，SIMD是一種計(jì)算機(jī)體系結(jié)構(gòu)的設(shè)計(jì)思想，而向量處理器是實(shí)現(xiàn)SIMD計(jì)算的具體硬件實(shí)現(xiàn)。向量處理器是一種支持SIMD指令集的處理器，用于執(zhí)行并行的向量計(jì)算任務(wù)。

當(dāng)然很多處理器也不單單是向量處理器，其一般既可以跑標(biāo)量操作、也可以執(zhí)行向量操作。此外除了所謂的向量處理器以外，通用處理器上的SIMD指令擴(kuò)展、GPU也可以實(shí)現(xiàn)SIMD機(jī)制。

所謂的向量，與標(biāo)量是一組相對(duì)的概念，其代表著一組數(shù)據(jù)。許多特定的程序?qū)嶋H上操作的都是向量，比如下面這個(gè)例子就是非常典型的向量操作（記住這個(gè)例子，后面還要用）。

所謂的向量處理器，即操作的不是標(biāo)量，而是向量，其通常有以下的基本機(jī)制：

• 需要Load/Store向量，因此需要向量寄存器；

• 需要對(duì)不同長度的向量進(jìn)行操作以提高靈活性，因此需要Vector Length Register即（VLEN寄存器）；

• 此外向量的數(shù)據(jù)有可能存在存儲(chǔ)器的不同位置，因此需要Vector Stride Register（VSTR寄存器）；

• 所謂的Stride即一組向量中兩個(gè)相鄰元素在存儲(chǔ)器中的距離；

我們來看一個(gè)Vector Stride的例子，在多媒體處理和AI計(jì)算中非常常見的運(yùn)算：矩陣乘法。

我們假設(shè)有A、B兩個(gè)矩陣，在內(nèi)存中以行優(yōu)先的方式存儲(chǔ)，如下圖所示。假設(shè)沒有Stride的話，就拿A的行和B的行相乘了，這顯然是不符合矩陣乘法運(yùn)算規(guī)則的。這個(gè)時(shí)候我們就需要VSTR寄存器，通過以下的設(shè)置方式：

• 加載A的Row0（A0到A5）到向量寄存器V1；

• 每一次只需要將地址遞增1，從而取下一列的數(shù)據(jù)；

• Stride為1；

• 加載B的Column0（B0到B50）到向量寄存器V2；

• 每一次增加地址10，從而取到下一行的的數(shù)據(jù)；

• Stride為10；

對(duì)于向量處理器而言，其每個(gè)連續(xù)的周期都會(huì)對(duì)數(shù)據(jù)元素進(jìn)行處理，因此：

• 向量功能單元是流水線的；

• 每一級(jí)pipe操作的是不同的數(shù)據(jù)元素；

我們看下面這個(gè)圖，基于向量的操作方式有什么好處呢？假設(shè)我們用的還是超標(biāo)量處理器，通過同時(shí)執(zhí)行多條指令，是不是也可以達(dá)到并行的效果？顯然，超標(biāo)量處理器連續(xù)執(zhí)行一系列的加法，會(huì)存在數(shù)據(jù)沖突、結(jié)構(gòu)沖突。而向量處理器的規(guī)整設(shè)計(jì)，天然就避免了這些問題?？梢钥吹揭欢鸭臃ㄔ谝黄鹚?，是完全沒有問題的。并且這些向量中的各個(gè)元素是獨(dú)立的，因此可以將流水線做的很深，畢竟不用考慮沖突的問題，也就可以進(jìn)一步提高主頻。此外由于Stride的存在，對(duì)于向量元素的地址元素是很簡單的，因此可以很輕松的加載數(shù)據(jù)（甚至是預(yù)取操作等）；

向量處理器這么好，它有什么缺點(diǎn)呢？大家應(yīng)該已經(jīng)發(fā)現(xiàn)了，我們到目前為止操作的數(shù)據(jù)都是非常規(guī)整的向量，當(dāng)并行不規(guī)則的時(shí)候，向量處理器就會(huì)顯得效率非常低。比如搜索一個(gè)鏈表中的key，大家可以想象一下向量處理器應(yīng)該怎么運(yùn)算，實(shí)際上此時(shí)約等于標(biāo)量處理器，浪費(fèi)了大量部件。這一缺點(diǎn)和VLIW有類似之處，當(dāng)找不到那么多并行的運(yùn)算的時(shí)候，效率自然會(huì)降低。

我們?cè)傧胍幌胂蛄刻幚砥鞯男阅芷款i在哪里，既然向量處理器需要同時(shí)操作那么多那么多的數(shù)據(jù)，那當(dāng)這些數(shù)據(jù)需要很多周期才能取出來的時(shí)候，很有可能導(dǎo)致運(yùn)算部件處于閑置狀態(tài)，進(jìn)而影響性能。向量處理器最典型的性能瓶頸就是Memory（Bandwith）。尤其是出現(xiàn)以下情況的時(shí)候：

1、運(yùn)算和內(nèi)存操作的比例沒掌控好的情況（比如實(shí)際運(yùn)算量很少，內(nèi)存操作過多）；

2、數(shù)據(jù)沒有放在多個(gè)Memory Bank當(dāng)中（后面詳細(xì)講）

我們?cè)賮砜匆幌孪蛄考拇嫫?，?duì)于每個(gè)向量寄存器而言，其有N組，每一組為Mbits；此外向量控制寄存器為：VLEN、VSTR、VMASK；其中VLEN最大最大不超過N，其含義在上面已經(jīng)講過了。

至于什么是VMASK呢？VMASK寄存器通常是一個(gè)位向量，其中每個(gè)位對(duì)應(yīng)于向量中的一個(gè)元素。如果對(duì)應(yīng)的位為1，則表示該元素參與向量操作；如果對(duì)應(yīng)的位為0，則表示該元素被屏蔽或忽略。通過使用VMASK寄存器，可以實(shí)現(xiàn)在向量操作過程中對(duì)元素進(jìn)行選擇性處理或過濾。

前面已經(jīng)提到過，由于向量內(nèi)部的元素是互相無關(guān)的，因此向量處理器天然適合深度流水線，畢竟其控制起來簡單，不用白不用。如下圖所示，就是一個(gè)六級(jí)流水線的乘法器。

提到向量處理器，就不能不提到CRAY，其生成的是早期的超級(jí)計(jì)算機(jī)，在那個(gè)年代，超級(jí)計(jì)算機(jī)等同于向量機(jī)。其中最著名的莫過于1978年推出來的CRAY-1，其架構(gòu)如下圖所示，我們簡單看一下其架構(gòu)：

• 有向量模式和標(biāo)量模式；

• 8個(gè)64-Element的向量寄存器（最大并行度為64）；

• 每個(gè)Element為64bit；

• 16個(gè)Memory Bank；

• 8個(gè)64-bit的標(biāo)量寄存器；

• 6個(gè)24-bit的地址寄存器

別的大家可能都很好理解，其中的16 memory bank是什么意思呢？

其實(shí)通過前面的文章內(nèi)容大家可以感性的知道，向量處理器的加載存儲(chǔ)必然比標(biāo)量處理器要復(fù)雜很多。因?yàn)樗枰猯oad/store多個(gè)元素。元素和元素之間為固定的距離（Stride）。

我們現(xiàn)在假設(shè)Stride為1，我們持續(xù)不斷的Load元素到我們的寄存器中，理論上這樣每個(gè)周期可以加載一個(gè)元素。但如果訪問Memory需要超過一個(gè)周期怎么辦呢？前一次的數(shù)據(jù)還沒回來，又發(fā)新的地址，Memory理論上不支持這樣的流水操作（普通RAM沒有Outstanding機(jī)制）。。。

答案就是，將Memory分為一塊又一塊的BANK，將元素在不同的BANK中Interleave起來！

通過分為多BANK，有以下幾點(diǎn)好處。BANK縮小了，相應(yīng)的MUX邏輯也會(huì)減少，SRAM輸出的延時(shí)減少，這樣可能就不需要多拍，一拍就能完成數(shù)據(jù)返回。此外很顯然，多BANK理論上可以實(shí)現(xiàn)N的并行度，因?yàn)楦鱾€(gè)BANK是獨(dú)立的，可以并行的去訪問。當(dāng)然，即便仍然需要多拍才能返回?cái)?shù)據(jù)，多BANK至少可以保證一個(gè)周期有一個(gè)元素的吞吐量，我們看它是怎么實(shí)現(xiàn)的。

我們看下圖，我們假設(shè)每個(gè)元素都是在BANK與BANK之間Interleave的。并且Stride等于1，并且BANK的數(shù)量要大于等Access Latency！這樣的話我們便可以保證一個(gè)周期至少獲得一個(gè)元素！并且沒有引入額外的開銷。就比如下面這個(gè)圖，假設(shè)需要16個(gè)Cycle才回?cái)?shù)據(jù)，對(duì)于Master側(cè)只要正常給地址就行了，16個(gè)周期以后第0個(gè)BANK的數(shù)據(jù)就回來了，17個(gè)周期第一個(gè)BANK的數(shù)據(jù)就回來了.....通過這種方式便實(shí)現(xiàn)了所謂的Outstanding，同時(shí)BANK回?cái)?shù)周期是固定的話，其天然是保序的。（這種RAM基本都是私有RAM，其它的模塊不要使用，不然數(shù)據(jù)回來順序會(huì)亂）

我們繼續(xù)回到之前提到的那個(gè)C代碼例子，如果我們用標(biāo)量代碼實(shí)現(xiàn)，需要多少個(gè)時(shí)鐘周期呢？

其匯編代碼如上圖所示，后面的數(shù)字代表需要多少個(gè)Cycle。假設(shè)我們運(yùn)行在一個(gè)標(biāo)量執(zhí)行的順序處理器，并且只有一個(gè)Memory BANK。

• 其中的LOAD操作不能流水（前面已經(jīng)解釋過了），需要2*11=22個(gè)Cycles，因此X循環(huán)體內(nèi)部為40個(gè)Cycles；

• 整個(gè)操作跑下來一共需要4+50（循環(huán)50次）*40+4=2004個(gè)Cycles；

我們?cè)偌僭O(shè)我們的Memory具有兩個(gè)讀寫端口，即真雙端口RAM。或者是2-BANK的Memory。此時(shí)需要多少個(gè)Cycle呢？此時(shí)實(shí)際上兩次LOAD可以流水操作，因此循環(huán)內(nèi)部只需要11+1+4+1+11+2=30個(gè)Cycles，因此一共只需要4+50*30=1504個(gè)Cycles，立刻少了500個(gè)Cycles！可以看出來，多BANK對(duì)向量操作具有顯著的優(yōu)化作用。

我們?cè)偌僭O(shè)此時(shí)運(yùn)行在一個(gè)向量處理器上，16個(gè)Memory BANK，需要多少個(gè)Cycle呢？

對(duì)于向量處理器，該例子就不會(huì)涉及到循環(huán)了，其對(duì)應(yīng)的匯編代碼如下所示：

我們想一想這樣需要多少個(gè)Cycle呢？

實(shí)際上就是上面的Cycle加起來，VLEN=50，因此總共需要285個(gè)Cycles。

我們?cè)偎伎家幌?，為什么需?6個(gè)Banks?因?yàn)镸emory Access的延遲為11個(gè)Cycle，所以需要大于11個(gè)Bank,而BANK一般為2的冪次方，所以選擇16。上面的例子中我們假設(shè)Stride為1，沒有問題，但如果Stride大于1呢？舉個(gè)極端的例子，Stride為16，那這樣每次都在訪問同一個(gè)BANK，等于做了無用功，因此對(duì)于Stride大于1的場景，我們還得再想辦法。

我們?cè)偎伎家幌?，還可不可以進(jìn)一步優(yōu)化？答案當(dāng)然是可以的，我們看上面的匯編代碼，VADD需要V0和V1的操作數(shù)，有沒有一種可能，可以直接在LOAD的時(shí)候，F(xiàn)ORWARD到乘法器？是可以的！在向量處理器中，一般不叫Forward，稱之為Vector chaining，如下圖所示

利用此技術(shù)，我們可以加速開始的運(yùn)算。開始的運(yùn)算為285個(gè)Cycle，如下圖所示：

但實(shí)際上我們可以將VLD旁路到VADD上，我們考慮將BANK擴(kuò)展為兩讀一寫的BANK。這樣我們可以并行進(jìn)行VLD操作。同時(shí)在第一個(gè)數(shù)據(jù)回來以后，不要存到向量寄存器，直接送給加法器做運(yùn)算，通過此方式只需要79個(gè)Cycles，相比最初的標(biāo)量處理器的2004個(gè)Cycles，獲得了19倍的性能提升！

我們總結(jié)一下上面的思想：

• 利用程序存在的并行性，兩組向量可以并行LOAD，甚至LOAD+STORE（將BANK擴(kuò)展為兩讀端口）；

• 數(shù)據(jù)已經(jīng)有了，沒必要放回寄存器。直接送給運(yùn)算部件做運(yùn)算；（Forward思想）

我們?cè)傧胍幌耄绻麛?shù)據(jù)元素的個(gè)數(shù)，比向量寄存器可以存的元素個(gè)數(shù)還多怎么辦？其實(shí)很簡單，一次算不完，那就分多次算嘛。比如有527個(gè)元素，向量寄存器只有64個(gè)Elements，即最大并行度只有64，此時(shí)通過8次迭代即可。該方法被稱為Vector Stripmining。

2.4、ISA中的SIMD運(yùn)算

除了專用的向量處理器以外，很多通用處理器也增加了SIMD相關(guān)的指令集擴(kuò)展，這樣我們便可以在通用處理器上，也體驗(yàn)一下SIMD機(jī)制了。

對(duì)于SIMD指令級(jí)擴(kuò)展而言，一般有以下特點(diǎn)：

• 單個(gè)指令一次操作多組數(shù)據(jù)（SIMD的特點(diǎn)）；

• 常用于圖形操作，多媒體運(yùn)算，機(jī)器學(xué)習(xí)等領(lǐng)域；

• 執(zhí)行短的算術(shù)運(yùn)算（也被稱為packed arithmetic）

我們看下面這個(gè)例子，加4組8-bit的數(shù)據(jù)，如果沒有向量指令擴(kuò)展。那么就需要執(zhí)行4次加法運(yùn)算，這還不考慮數(shù)據(jù)冒險(xiǎn)和結(jié)構(gòu)冒險(xiǎn)。但是有了向量指令擴(kuò)展，一個(gè)Cycle即可搞定。

談到SIMD指令擴(kuò)展，就不得不提英特爾相關(guān)的指令，最著名的為Intel在其奔騰系列處理器中率先提出了MMX操作，其核心思想是同時(shí)操作多組數(shù)據(jù)元素，即SIMD思想。對(duì)于64位處理器，可以拆分成8個(gè)8bit，4個(gè)16bit，2個(gè)32bit，一個(gè)64bit。然后做相應(yīng)的運(yùn)算即可。思路很簡單，和我后面提到的SIMD實(shí)例沒有本質(zhì)區(qū)別。

該指令擴(kuò)展，最初是用在圖像處理中，我們看個(gè)例子，圖像疊加。

所謂的圖像疊加，即兩幅圖拼在一起。上面這個(gè)拼的機(jī)制是，對(duì)于Blue的背景圖，采用Image Y，否則采用Image X。該例子就涉及了大量的并行運(yùn)算。其實(shí)各個(gè)PIXEL之間是沒有依賴關(guān)系的，可以并行運(yùn)算的，該算法就適合用SIMD去加速。

MMX為早期的SIMD指令擴(kuò)展，X86架構(gòu)下還有以下的SIMD指令擴(kuò)展：

• MMX

• SSE（Streaming SIMD Extensions）

• SSE-1

• SSE-2

• SSE-3

• SSE-4

【manim】動(dòng)畫演示SSE指令集SIMD intrinsics（第一期）_嗶哩嗶哩_bilibiliwww.bilibili.com/video/BV1nX4y147aB/?spm_id_from=333.788&vd_source=aa30a4e19bdd942dc58f16b3be44358e

• AVX（Advanced Vector Extensions）
• AVX：256bit Float Point
• AVX2：256bit Float Point with FMA擴(kuò)展（Fused Multiply Add）
• AVX-512：512-bit
• AMX（Advanced Matrix Extensions）
• 用于AI運(yùn)算
• 二維寄存器
• Tiled matrix multipy unit（TMUL）

孫盔盔：ARM與RISC-V的向量擴(kuò)展比較55 贊同 · 6 評(píng)論文章

2.5、機(jī)器學(xué)習(xí)（包括但不限于）加速器中的SIMD運(yùn)算

3、看個(gè)SIMD實(shí)例

4、總結(jié)

• 向量處理器；
• 帶SIMD指令級(jí)擴(kuò)展的通用處理器；
• GPU以及部分NPU；