Vector architecture
Vector architecture
這兩天閱讀了量化數據級並行DLP那一章，然後看了一些GPU，Vector架構相關的論文，當然，都是介紹或者綜述性質的。我不知道該怎麼描述比較好，於是我決定先單獨描述，再做對比分析。
以下內容主要是總結自論文Vector architectures: Past, Present and Future，量化書第四章DLP還有附錄G。
歷史
Vector architecture一開始主要是用在高性能計算領域，主要是用於大量的數據級並行任務。當年的機器叫向量機Parallel Vector Supercomputers（PVPs），一般是若干個向量處理器通過一個專用的交換網路，連接到memory，所以處理器可以共用同一個地址空間，上面運行的程序是一種share-memory的並行架構。
早期的計算應用基本都是科學計算等應用，裡面有大量的數據級並行，然後在當年設計出vector architecture是非常自然的，因為早期的向量機，主要就是以scalar處理器為基礎，然後加上向量部件以及相對規則的數據通路，實現起來複雜度不高，設計出vector architecture，是當年非常合理的選擇。
從八十年代開始，隨著PC市場的發展，微處理器迎來快速發展。由於如下的原因，微處理器比傳統的向量處理器性價比高很多。
- 微處理器市場龐大，規模效應顯著，使得巨大的研發投入以及均攤下來後每片的低成本成為可能
- 向量處理器使用的是較傳統的ECL工藝，而微處理器使用較新的CMOS還有DRAM技術
- 激烈的市場競爭
然後就出現了用微處理器搭建超算集群的嘗試，多個微處理器連接上同一個memory，組成Symmetric Multiprocessor（SMP），這些SMP的系統可以通過網路連接起來，組成Massive Parallel Systems（MPP）。MPP系統的可擴展性比PVP好，但是它的可編程性不如PVP，需要大量的編譯以及並行編程技術，我猜測MPI的出現是不是與這個趨勢有關？
然後Vector architecture在超算系統中就逐漸失勢，然後隨著GPGPU以及CUDA的出現，GPU又逐漸成為超算系統中的主力。
在這篇論文中，它總結了vector architecture失勢的一些原因，最最主要的原因，還是cost。即基於vector architecture的超算系統比基於MPPs或者SMPs的超算系統貴很多，所以大家自然就拋棄它了。
- 最最主要的原因是其他系統都是用的commodity parts，上面已經描述過了。有一個廣大的應用市場作為基礎，對於一個架構的生命力來說至關重要。正如GPU搞得好，除了CUDA，CPCPU等重大創新外，有消費市場，視覺領域的巨大成功，讓它在進軍其他計算領域時，成本比其他架構要低很多。
- PC，工作站，超算最貴的部件往往是memory system。而向量機需要充分發掘出性能，需要巨量的帶寬，而這些是通過大量的memory bank來實現的（256到1024），而且好多都是直接用SRAM作為存儲。
- 要實現的極高的訪存帶寬，封裝開銷大
- 還基於老舊的ECL工藝，沒有及時跟上CMOS、DRAM的大潮
- 理論性能很好，但是要充分發揮出性能很難
- 自從CRAY-1出現後，架構創新已經很少了（當一個架構已經相對成熟，架構創新已經很少時，可能就是其走下坡路的開始）。
Vector architecture的未來
這裡描述的是vector architecture的未來（當然，作者在進二十年前描述的未來，已經成了現在的現實。首先就是作者認為，vector architecture雖然失敗了，但是這並不意味著它的許多設計理念就完全沒有用處了。向量機系統失敗了，但是作者認為向量指令集是個好東西。
向量ISA的優勢：
作者認為優勢主要是三方面的：
- semantic advantage，即作者認為向量指令集用來描述一些問題比較適合。其實語義優勢真的是很看問題領域，還關係的相應的編譯、編程技術。例如VLIW如果讓人手寫，確實非常痛苦，但是用上了編譯器技術後，VLIW和向量指令集在DSP領域都得到了廣泛的應用。語義優勢更多體現的是是否易於編程（底層編程，高級語言編程），生產力高不高。
- 並行性由ISA顯式指出，可以很方便地實現高性能系統。這個可以和亂序，還有VLIW之類的進行對比。與VLIW類似，他們都是用將並行性通過指令顯式指出，只不過VLIW找出的是指令級並行，向量指令集是數據級並行。與亂序不同的是，亂序是通過硬體方案動態地發掘出並行性，而vector architecture，主要靠編譯技術靜態發掘並行性。這一點主要講的是，要實現一個高性能的系統的硬體難度。可見，要實現一個高性能系統，編譯技術，ISA，架構設計是緊密的相關的**。
- vector ISA非常規整，並且是顯式並行，所以在設計實現上，性能可以直接通過功能部件流水，多堆FU，超高的頻率給搞出來。
然後作者又做了對於一些程序的指令數，operation數，以及兩者比例的對比。主要的就是：
- vector ISA的設計，允許我們用少量的指令，完成大量的運算。所以instruction path可以極端簡單，指令取指帶寬小，instruction path上不用做分支預測等複雜的東西了。
- 少量的指令就可以完成大量的運算，控制可以簡化
作者說vector ISA的指令比scalar少很多，主要是因為有許多功能，在vector ISA裡面是隱式實現的，而在scalar ISA裡面是顯式編碼的。例如對於一堆計算，循環控制的開銷，訪存地址的計算等。
然後就是訪存系統了，vector architecture的訪存系統的主要特徵是帶寬高，它主要是用訪存的高帶寬來均攤延遲開銷的，同時vector ISA允許一條指令產生大量訪存請求，所以發出訪存請求的能力也很強。
最後就是作者對vector architecture的預測了，作者預測vector architecture不會死，而是會和微處理器結合起來。作者的預測也確實成為了現實。向量機已經死了，但是向量架構以另外的形式活著。
vector architecture
上面是根據那篇論文，簡要描述了一下vector architecture的歷史沿革。下面介紹vector architecture的主要特點，並與其他的架構進行對比。接下來這部分內容主要是來自量化。
關於寄存器
和scalar processor類似，最早的vector architecture是memory-memory的，而不是load-store architecture。後來引入了向量寄存器，變成了現在常見的load-store的結構。為什麼大家不用memory to memory形式的指令，而選擇要引入向量寄存器呢。
首先就是關於寄存器本質的問題，量化裡面直接就說清楚了：
>These large register files act as compiler-controlled buffers, both to hide memory latency and to leverage memory bandwidth.所以寄存器的功能和Cache類似，都是為了處理內存牆的問題，都是為了降低訪存延遲以及提升訪存帶寬，寄存器本身就是最靠近計算部件的cache。但是與Cache類似的是，寄存器是通過ISA暴露出來的，是可以編程式控制制的。
量化里是直接點明了本質，我們還可以從另外的角度考慮，假設就從memory-memory的形式出發，然後我們想要提升性能。提升性能遇到的直接問題就是訪存帶寬與延遲的問題，所以最最關鍵的還是數據重用，我們可以設計一套類似亂序中的dynamic memory disambiguation的機制，用load-store queue存儲訪存請求，用大量的CAM進行內存地址的匹配，通過硬體發現數據重用，並通過bypass來提供數據，這樣子就不用讓每個訪存請求都真的去訪問內存了。
然後，再仔細想想，我們就會發現，LSQ本質上就是最內層的buffer，它就是寄存器，不過它是硬體維護的，對軟體不可見。那麼既然這樣子，那還不如設計出寄存器，並且讓軟體控制，讓軟體發現數據重用，並利用寄存器來實現數據重用，這樣子硬體複雜度更加簡單，整體性能也更好。
類似的，再來一個軟體寄存器和硬體寄存器的問題。IA32那麼少的寄存器怎麼把性能做好的？它可以通過強化memory子系統，把LSQ，動態消歧做好了，不就相當於增大了寄存器嘛。
這本質上還是一個軟硬體方案對比的問題，只不過在這個問題上，軟體方案具有絕對優勢，就勝出了。
類似的，在下層Cache領域，到底是選用scratch pad還是用memory。一個是軟體方案，一個是硬體方案。只不過在這個問題上，編譯方案不成熟，所以硬體方案就獲勝了。但是，軟體方案還是在實時性等領域大獲成功。
還有就是向量寄存器的一大問題就是太大了，導致上下文切換開銷會比較大。對於這個問題的主要方法就是：pay as you go。你用了多少，切換的時候，就保存多少。還有一個方案，就是lazy的模式。我之前在學習Linux內核時似乎看到過，但是具體記不得了，Intel SSE似乎提供了中斷的機制。即不一定要保存數據，數據就讓它待在寄存器里，如果別人要用了，那就觸發一個中斷，這個時候才來保存。即不到萬不得已，絕不下火線。
怎樣提升vector architecture性能
我們可以從數據通路以及訪存通路的角度來看。
在附錄中有針對vector架構的性能建模，即給幾個參數，如內存延遲，FU數目，FU start up time等，來預測性能，這種性能建模還是非常必要與重要的。
數據通路
數據通路的主要目標就是處理長的內存延遲，以及提升計算吞吐。
處理長的內存延遲
從指令上來看，vector architecture是通過長的vector來amortize訪存延遲，所以延遲其實不太是問題，訪存帶寬是問題。但延遲其實也是問題，這直接影響了要多長的vector才能把訪存延遲均攤低了，直接影響了發揮出vector processor能力的。這個本質上是發掘了一條指令內部的數據級並行。
從指令流的角度來看，通過flexible chaining，即把多個向量指令chain在一起，下一條指令的對應element，只要它依賴的上游element生產好了，它就可以開始執行了，多條指令的執行深度交錯。這個本質上是發掘一個指令塊內部的數據級並行。當然，還有就是指令的啟動延遲可以通過這種方式掩蓋，指令chaining有了結構衝突怎麼處理？這些在附錄的那一章都有描述。還有就是chaining到底應該怎麼實現，我還是有疑問。
在亂序裡面，基於寄存器的依賴，是通過issue queue里的一堆比較器來做的。vector architecture裡面由於有大量的寄存器，所以給每個寄存器配個比較器顯然是不現實的，所以，就算前後兩個指令有依賴，並且它們操作的同一個vector的不同元素，要保持依賴也頗為困難。
而如果兩條指令處理的不是同一個向量，那就沒什麼問題了（不，其實還有問題，總有些變態會把多個向量重疊著放）。所以，在vector的級別，用scoreboard進行依賴檢查或許是可行的，但是如果允許chaining，那麼將極大減少chime數，極大提升速度。
這個chaining本質上是個和亂序處理器類似的喚醒問題。
flexible chaining有點發掘向量指令的ILP的感覺在裡面。
關鍵是flexible chaining的控制邏輯應該怎麼實現？按照亂序那樣的方式來實現，代價顯然就太大了。關鍵是dependency tracking，select-issue變複雜了，肯定不可能搞一個VL項的比較器隊列啊！
對於vector architecture，或許可以簡化，並不需要搞成issue queue那麼複雜，或許可以搞成forward flow那樣子的，但是搞成那樣子，還是少不了對於每個元素都要有一個域來記錄依賴啊。所以真實的向量處理器中，flexible chaining到底是怎麼搞的啊？
另外關於vector architecture與亂序的結合。我還是不太明白。我懷疑對於有大量寄存器的vector architecture，寄存器重命名或許都是不太可行的。那怎麼與亂序流水線整合？Intel的AVX 512，那麼一大堆寄存器是怎麼處理的？Intel不同代的SIMD指令寄存器或許可以從同一個物理寄存器堆裡面分配？
提升計算吞吐
多加幾條lane，跨lane就有寄存器讀寫口的問題，這個在之前的一篇文章裡面討論過了。
內存子系統
訪存帶寬的匹配是個至關重要的問題。
最最重要的問題就是要提升訪存帶寬。vector architecture不是用cache，而是通過分bank，interleave，來提升訪存系統的絕對帶寬。
附錄裡面在對存儲系統的訪問特性做了如下劃分：分別是access time與busy time，它們分別影響了訪存延遲與帶寬。這個劃分值得借鑒。
附錄裡面對於gather-scatter，編譯優化還做了進一步的介紹，尤其是gather-scatter用於稀疏矩陣。這個裡面有一些比較有意思的點。
首先就是gather-scatter裡面生成地址vector佔用的時間會比較長，所以一般會加一個指令用於生成地址vector。還有就是gather-scatter處理分支。原來的方式是用predication，來讓零元素不參與運算，現在的方法是用CVI等指令，先把零元素給collapse掉，然後對非零元素用gathter-scatter的方法處理，這也是個方法。哪種方案更好，就取決於向量中零元素的多少了。predication浪費lane的運算能力，但是CVI增加了額外的指令，並且讓load，store變成了gather-scatter，對訪存不太友好。這全是取捨，需要定量分析。
Vector architecture性能指標
任何時候比較運行時間永遠是比較性能的最準確也是最好的方法。
由於vector長度對於發揮性能至關重要，所以有幾個重要指標是與vector長度相關的。
- R∞—The MFLOPS rate on an infinite-length vector.
- N1/2—The vector length needed to reach one-half of R∞. This is a good measure of the impact of overhead.
- Nv—The vector length needed to make vector mode faster than scalar mode. This measures both overhead and the speed of scalars relative to vectors.
現代的向量機Cray X1
在附錄里最後介紹了一個現代的向量機：Cray X1
這個裡面有幾點我是感覺比較有意思的：
首先就是由於指令的scalar部分適合用Cache，而vector部分有些時候的訪存特徵比較streaming，所以它允許部分vector訪存指令繞過cache，以防止污染cache，同時保證了scalar和vector部分的性能。這是一個比較常用的思路，即不同的訪存特徵的數據，使用不同的訪存通路，以防止互相干擾。例如TPU裡面的weight memory和數據memory通路就是分離開的。
還有就是Multi-Streaming Processors。它的主要功能就是：
The simplest use is to gang together four two-lane SSPs to emulate a single eight-lane vector processor.
Each SSP can process its loop iterations independently but must synchronize back with the other SSPs乍一看，可能感覺這有點像GPU裡面SIMT的思路，但是這個同步執行的粒度比SIMT大，SIMT裡面是一個WARP裡面流處理器執行的是同一條指令（指令diverge怎麼處理的，我還是沒有搞懂）。這個MSP神乎其技的地方在於，它們是在更粗的粒度上執行，並且有快速的同步機制。例如，它們可以做到說，loop的前100個給core 0，後100個給core 1，各自執行完了，就同步一下。這看起來和我們平時寫個並行程序，手動分線程，再同步差不多。神跡的地方在於，編譯器用向量化技術自動完成了這一切。
Vector architecture與其他架構的對比
比較架構，我們主要比較編程模型（這個主要是指指令集），內部數據通路，訪存通路。
從編程模型上說，vector architecture是將數據級並行，通過向量的方式顯式地表示，即一個向量中的不同element，是並行無依賴的（但這並不一定是完全無依賴，有些時候，gather-scatter，處理的各個元素內存地址可能一樣）。
而亂序處理器不顯式地表示並行性，並行性需要硬體上通過檢查依賴，消除依賴，來發掘並行性。亂序處理器發掘的是指令級並行。亂序處理器發掘並行性的能力強烈依賴於指令窗口，ROB，物理寄存器堆大小等關鍵資源的大小。它對instruction flow，register data flow還有memory data flow提出了非常高的要求。
VLIW是顯式地表示指令級並行性。
vector architecture與VLIW類似，都極端依賴編譯器的向量化，並行化能力。對於數據級並行來說，要控制同樣多的運算，vector architecture所需要的指令數量（動態指令數量，即實際執行的指令數，而非靜態的代碼段大小）是最少的。
當然，vector architecture與亂序，VLIW是正交的，它們可以組合存在，並且這些組合確實是廣泛存在。
GPU用在計算領域的編程模型主要就是CUDA，它提供的是一個線程的抽象，即一個元素被一個線程操作，同時線程被組織成兩級的結構，最底下一級的線程組裡可以同步。這是編程抽象，實際在GPU上運行時，同一個WARP是用的SIMT的形式，這個和SIMD非常像。
從內部數據通路上來說：vector architecture一般是有vector unit，並且它一般是圍繞一個scalar core構建，一個scalar core可以管理多個vector unit，例如Cray X1中就是這樣子。vector unit數據通路規整，控制相對簡單。
從訪存通路上來看，首先是處理內存延遲的整體思路是什麼樣子的。vector architecture，為了保證性能，主要是需要極高的帶寬，而延遲問題，主要是靠用長的vector來均攤延遲。vector architecture保證高帶寬，主要就是簡單粗暴的分bank，interleaved memory等，主要是因為vector很多時候是stream的訪存模式，重用可能比較少，所以加cache倒也不一定有效果（注意，這個是依賴於應用的）。有些時候也會配個cache，用來讓scalar core，或者某些有大量重用的vector代碼跑得更快。
亂序還有VLIW主要跑的是通用應用，通用應用一般來說，指令、數據的時間局部性還有空間局部性都很好，所以是用的cache，底下的memory帶寬一般不大，主要是靠cache來降低延遲以及提升訪存帶寬。多級的cache有效降低了延遲，另外對於cache miss等大的延遲，是用speculation來解決的。
而GPU主要就是面向吞吐量相關的計算，因而訪存那邊通過多channel，GDDR等技術，來提供了較高的帶寬。內部也有Cache等來進一步地降低延遲，提升訪存帶寬。而掩蓋延遲主要通過multicore + 激進的multi-threading。
所以，從訪存通路上來說，vector與GPU比較像，兩者都能提供非常高的帶寬，所以從Roofline model上來看，對於很多應用，很容易就達到Roof（計算bound），不怎麼容易被memory bound。而亂序以及VLIW，由於訪存帶寬比較小，所以Roofline model的轉折點非常靠右，要達到極限的計算能力非常困難，很容易就被memory bound。但是通過分塊，將某些塊放在cache裡面重用，也能提升實際的operational intensity，此時就不再被memory bound，就能利用上cache的高帶寬了，進而充分發揮計算能力了。例如矩陣乘法，就可以這樣做。但是也不是所有應用都好這麼搞，所以總的來說，吞吐量相關的，在vector architecture和GPU上更能發揮出極限的運算能力。
推薦閱讀：
