快速了解SIMD – Chaofan's

SIMD即Single Instruction Multiple Data縮寫，單指令多數(shù)據(jù)，表示CPU設(shè)計(jì)中一種提高程序并行度的技術(shù)。和它對(duì)應(yīng)的SISD、MISD和MIMD三個(gè)概念已很少有人提及，倒是GPU又引入了個(gè)新概念叫SIMT (Single Instruction Multiple Threads)。

換種理解方式或許更實(shí)在些：SIMD和SIMT表示邏輯上有多個(gè)執(zhí)行的實(shí)體，但只有一個(gè)執(zhí)行的狀態(tài)。至于其他三種：

• 一個(gè)執(zhí)行實(shí)體，一個(gè)執(zhí)行狀態(tài)，屬于單線程
• 一個(gè)執(zhí)行實(shí)體，多個(gè)執(zhí)行狀態(tài)，屬于協(xié)程
• 多個(gè)執(zhí)行實(shí)體，多個(gè)執(zhí)行狀態(tài)，屬于多線程

更實(shí)用地說，編程用途上的SIMD就是一組指令集擴(kuò)展，能用一條指令同時(shí)完成若干個(gè)數(shù)據(jù)的相同操作。由于大量計(jì)算程序最耗費(fèi)時(shí)間的代碼都是核心的若干循環(huán)，如果能有SIMD指令的幫助，雖然復(fù)雜度還是沒有改變，但相當(dāng)于耗時(shí)除以一個(gè)不小的系數(shù)，不算免費(fèi)午餐也是廉價(jià)午餐了。

快速上手SIMD指令

這里用C語(yǔ)言舉例，看下面的代碼。

#include <stdio.h>

typedef unsigned vecu32 __attribute__((vector_size(16)));

extern unsigned data0[];
extern unsigned data1[];
extern unsigned datalen;

int main(void) {
  for (int i = 0; i < 100000; ++i) {
    int j = 0;
    for (; j + 4 <= datalen; j += 4) {
      vecu32 a = *(vecu32*)(&data0[j]);
      vecu32 b = *(vecu32*)(&data1[j]);
      *(vecu32*)(&data0[j]) = a + b;
    }
    for (; j < datalen; ++j)
      data0[j] += data1[j];
  }
}

為阻止編譯器做常量?jī)?yōu)化，這里把兩個(gè)數(shù)組的定義放置在另一個(gè)文件里，長(zhǎng)度都為65536個(gè)unsigned。在Apple M1上，使用Apple Clang 16搭配-O選項(xiàng)，運(yùn)行時(shí)間是0.87秒。而如果不使用vecu32，即注釋掉中間用到vecu32的for循環(huán)，運(yùn)行時(shí)間會(huì)來到2.40秒。這里一個(gè)vecu32是16字節(jié)，即能容納4個(gè)unsigned。雖然沒有完全達(dá)到4倍性能差距，但2.8倍也是非常明顯的性能提升，奧秘就在這里聲明的vecu32類型。

如果你稍微熟悉GCC或Clang，就能發(fā)現(xiàn)這里的__attribute__是GCC風(fēng)格屬性擴(kuò)展，而vector_size屬性就是為向量類型準(zhǔn)備的。在編譯器語(yǔ)境，SIMD容器就被稱作向量 (vector)，實(shí)際上確實(shí)比C++的std::vector更接近數(shù)學(xué)上向量的原始定義。這里一個(gè)vecu32能容納4個(gè)unsigned變量，那我能否定義一個(gè)32字節(jié)的vecu32來進(jìn)一步加速呢？

先看當(dāng)前版本的匯編。在ARM上用clang -S可以發(fā)現(xiàn)輸出中有一條add.4s v0, v0, v1指令，查詢文檔可得知這條指令的意思就是向量整數(shù)加。再把源碼中的16改成32，for循環(huán)頭上的4改成8編譯一遍，會(huì)發(fā)現(xiàn)執(zhí)行時(shí)間幾乎沒有變化，而匯編里有了兩條 add.4s而沒有想象中的add.8s存在。失落之余先別著急，在輸出匯編的編譯命令中加入-arch x86_64 -mavx，能驚喜地發(fā)現(xiàn)X86平臺(tái)是有32字節(jié)SIMD指令的，叫vpaddd。甚至，甚至可以更進(jìn)一步，把上面代碼的向量尺寸改為64字節(jié)，循環(huán)步長(zhǎng)改為8，然后加上-mavx512f選項(xiàng)，會(huì)發(fā)現(xiàn)X86版本還能有對(duì)應(yīng)的單條指令 (盡管名字還叫vpaddd，但寄存器類型變了，實(shí)質(zhì)上是和前面的vpaddd算不同的指令)。

這告訴我們一個(gè)道理，SIMD指令的支持范圍和CPU架構(gòu)有關(guān)，和編譯器選項(xiàng)也有關(guān)。

SIMD和CPU架構(gòu)

不同CPU架構(gòu)支持的SIMD長(zhǎng)度和類型各有不同，但主流指令集都有面向SIMD的擴(kuò)展。

x86

最早的x86 SIMD擴(kuò)展指令集叫MMX，來自1996年的Intel，以加速多媒體程序。但它僅支持64位長(zhǎng)度，并且只能加速8位到32位的整數(shù)操作。因?yàn)樵缙趚86 CPU的古怪設(shè)計(jì)，這個(gè)MMX指令不光短，還會(huì)占用浮點(diǎn)數(shù)的寄存器，用今天的目光看實(shí)在雞肋。AMD也看不下去，推出了名叫3DNow!的擴(kuò)展，支持浮點(diǎn)SIMD。為了應(yīng)對(duì)，Intel很快推出了新的SIMD擴(kuò)展，也就是今天有名的SSE (Streaming SIMD Extensions)。

SSE支持128位長(zhǎng)度的向量，且可容納如4xfloat、2xdouble、4xint、8xshort或16xchar等不同類型。更重要的是，因?yàn)檫^去X86對(duì)浮點(diǎn)的支持過于奇葩 (x87指令集)，SSE對(duì)標(biāo)量（即單個(gè)）浮點(diǎn)數(shù)的操作也做了延伸，float和double的操作終于可以對(duì)應(yīng)到和整數(shù)相似的指令了。SSE經(jīng)歷了多次擴(kuò)展，涵蓋了整數(shù)和浮點(diǎn)數(shù)從算術(shù)到重排和加密等各種操作。對(duì)今天的x86 CPU來說，SSE可以視作默認(rèn)支持。

十年后，Intel又發(fā)布了新的SIMD擴(kuò)展，稱作AVX (Advanced Vector eXtensions)，總體和SSE相似，不過長(zhǎng)度又?jǐn)U展了一倍，支持256位向量。AVX還有更變態(tài)的延伸版本叫做AVX-512，顧名思義就是512位向量，8個(gè)double或者64個(gè)char同時(shí)操作。

ARM

ARMv7引入了高級(jí)SIMD擴(kuò)展，通常也被稱作NEON。和x86的MMX/SSE類似，NEON支持64位和128位兩種向量。雖然ARM處理器家族比x86更復(fù)雜多樣，但今天也基本可以假定，主流ARM芯片都支持NEON指令集。

一部分面向服務(wù)器的ARM處理器，為了支持更長(zhǎng)的向量，走了和x86不同的道路，推出了稱作SVE (Scalable Vector Extension) 的動(dòng)態(tài)向量擴(kuò)展。和AVX固定256位、AVX512固定512位不同，SVE沒有固定向量長(zhǎng)度，而是在向量操作之外，又引入了一組謂詞指令和寄存器，這就可以在匯編層面體現(xiàn)上層的循環(huán)邏輯，從而在運(yùn)行時(shí)確定向量長(zhǎng)度（也就代表著循環(huán)次數(shù)）。這樣做的好處是：一個(gè)為SVE編譯的二進(jìn)制程序，在不同向量長(zhǎng)度的CPU上都可不經(jīng)改動(dòng)執(zhí)行，自動(dòng)獲得硬件向量變長(zhǎng)帶來的性能提升。

SVE支持128到2048位的向量，ARMv9引入的SVE2又加入了若干新指令。本文不計(jì)劃深入討論SVE的使用。普通桌面級(jí)的ARM CPU (如Apple M1)，并不支持SVE。

RISC-V

RISC-V把除最基本整數(shù)指令外的所有指令都?xì)w類為擴(kuò)展，并以單獨(dú)的字母標(biāo)記，如擴(kuò)展F和D分別表示單精度和雙精度浮點(diǎn)數(shù)。RISC-V曾經(jīng)有個(gè)叫做P (Packed SIMD) 的擴(kuò)展，但今天更主流的是擴(kuò)展V。RISC-V的創(chuàng)造者之一David Patterson （《計(jì)算機(jī)體系結(jié)構(gòu)：量化研究方法》的作者之一），曾經(jīng)寫過一篇文章批評(píng)傳統(tǒng)的SIMD指令設(shè)計(jì)不夠靈活，增加了復(fù)雜度。

也因此，RISC-V的擴(kuò)展V (經(jīng)常稱作RVV) 指令設(shè)計(jì)更類似ARM SVE。而細(xì)節(jié)上更加靈活。比如說，向量長(zhǎng)度存儲(chǔ)在一個(gè)特殊寄存器中，計(jì)算指令也并不包含元素長(zhǎng)度，具體元素多長(zhǎng)會(huì)由特別指令設(shè)置。一條vfadd.vv可能是f32也可能是f64。

在RISC-V語(yǔ)境中，SIMD和向量兩個(gè)詞有明顯區(qū)分：SIMD指x86風(fēng)格的定長(zhǎng)定類指令，向量指可動(dòng)態(tài)擴(kuò)展的多數(shù)據(jù)指令。但在本文其他部分，不作嚴(yán)格區(qū)分。

POWER

在Mac電腦還在使用PowerPC CPU的年代，蘋果、IBM和摩托羅拉組建過所謂的AIM聯(lián)盟。90年代末還沒有今天的GPU概念，多媒體相關(guān)的加速都由CPU完成。為了和x86 SSE競(jìng)爭(zhēng)，AIM在PowerPC指令集上推出了Vector Media eXtension (VMX) 擴(kuò)展。該擴(kuò)展引入了一種128位向量類型，支持整數(shù)和部分單精度浮點(diǎn)指令。

PowerPC Mac的絕唱，PowerMac G5，支持該指令集。而后續(xù)IBM服務(wù)器上的POWER指令集依然包括這個(gè)擴(kuò)展。VMX更出名的名稱叫AltiVec，但2004年摩托羅拉半導(dǎo)體部門分拆為飛思卡爾公司，AltiVec商標(biāo)由飛思卡爾持有。為避免商標(biāo)糾紛，IBM用到的場(chǎng)合繼續(xù)稱之為VMX。在GCC和Clang等編譯器眼中，這個(gè)指令集依然叫AltiVec。

從POWER指令集2.06版開始（即POWER 7），POWER在VMX基礎(chǔ)上引入了新的VSX (Vector Scalar eXtension) 指令集。在傳統(tǒng)的POWER浮點(diǎn)指令外，VSX加入了一組新的和IEEE-754完全兼容的標(biāo)量和向量浮點(diǎn)指令，類似SSE。浮點(diǎn)和向量寄存器也統(tǒng)一起來，VSX共64個(gè)128位寄存器，傳統(tǒng)的32個(gè)浮點(diǎn)寄存器成為了前32個(gè)VSX寄存器前64位的別名，32個(gè)VMX寄存器則對(duì)應(yīng)到后32個(gè)VSX寄存器。

WebAssembly

雖然WebAssembly不是真實(shí)的CPU指令集，但因?yàn)樵O(shè)計(jì)上考慮性能，加入SIMD指令也有助于模擬和JIT執(zhí)行。Wasm的SIMD類型相對(duì)簡(jiǎn)單，固定128位，配合不同類型的計(jì)算指令，和SSE、NEON、VMX/VSX都能對(duì)上。

編譯器與SIMD

雖然SIMD能給計(jì)算密集的程序帶來提升，但我們并不是每次都要手寫這堆奇怪的語(yǔ)法才能用上SIMD。在開優(yōu)化的情景下，編譯器會(huì)努力地將代碼中的標(biāo)量操作組合成向量指令，這部分功能在編譯器中稱作Vectorizer。LLVM中有循環(huán)Vectorizer和SLP Vectorizer兩類，前者針對(duì)循環(huán)而后者針對(duì)非循環(huán)。其實(shí)，開頭那個(gè)程序如果用O3編譯，即使不手工使用向量擴(kuò)展，Clang也可以生成出向量指令。

像開頭例子中這樣簡(jiǎn)單的循環(huán)，循環(huán)體內(nèi)只出現(xiàn)了一次加法，為了「湊」出四個(gè)加法構(gòu)成SIMD，編譯器需要像我們手寫的代碼一樣把循環(huán)體擴(kuò)充為原來的4倍，然后讓循環(huán)次數(shù)除以4，并且還要處理剩下幾個(gè)余數(shù)的情況，所以匯編容易變得非常大。這種優(yōu)化叫做循環(huán)展開 (Loop Unrolling)。有關(guān)其他自動(dòng)向量化中可能涉及到的優(yōu)化，可以查閱LLVM向量化的官方文檔。

如果還是有要手寫向量化代碼的情況，除開頭提到的__attribute__((vector_size()))外，每個(gè)平臺(tái)都提供了自己的C語(yǔ)言擴(kuò)展：

• x86上immintrin.h，使用文檔
• ARM上arm_neon.h，使用文檔
• POWER上altivec.h，使用文檔
• RISC-V上riscv_vector.h，參考文檔