隨便聊聊高性能計算和性能優化，想到哪說到哪。文章分為4個部分，第一個部分聊聊并行算法，第二個部分系統地說一下性能優化的方法論，第三個部分介紹一下性能分析，第四個部分介紹一下小結和感悟。
1. 并行算法
目前單核處理器性能已經碰到了瓶頸，想通過單核上的優化去顯著提高算力已經是一個非常困難的事情了。但是，現在對算力的需求卻日益劇增，科學與工業領域需要更多的算力進行仿真模擬，游戲渲染需要更多的算力滿足人的娛樂需求，人工智能領域需要更多的算力進行模型訓練和推理服務。因而，對算力的巨大需求促使了英偉達的股價近十年內一輪又一輪地暴漲以及目前異構加速器遍地開花。所有人都知道這是塊肥肉，大家都想吃上一口。而從最底層角度而言，所有的一切都源于一件事情，并行算法可以將單核的任務劃分到多核異構設備上從而實現加速。這個事情保證了，在一個可以并行的算法上，計算核心越多，理論上，你的代碼就能跑地越快，人類社會的發展也能越快。
不過，說實話，我一直覺得并行算法是一個非常難的課題，并行算法的思維是非常反人類的。對于一堆的事情，如果有相關性的話，人總是習慣于列個計劃，比如，要聚會了，一堆人在一起。大家先一起做飯，再一起吃飯，最后一起洗碗。干完一件事，再干下一件事。而并行算法在干一個什么事情呢，就是非得讓一些人在做飯，一些人在吃飯，一些人在洗碗，然后加一些亂七八糟的同步保證做飯的時候不會拿臟盤子盛飯，洗碗的時候不會把別人碗里沒吃的米飯倒了。正常人去看這個思維，覺得這人腦子多少是有點問題的。但是計算機里面經常要這么干，導致人去理解并行算法的時候就會變得非常困難。比如scan算法，給定一串數，求出這些數中，每一個數前面所有數的和。公式表達是這樣子，sum[i]=sum[i-1]+num[i]。這個計算過程有著很強的數據依賴，怎么在GPU里面去做？稍微一想就覺得費勁。再比如排序，給一堆數，怎么在GPU上開一堆線程把這些數排好？又比如圖里面的寬度優先遍歷和最短路徑，怎么樣在GPU上跑起來？學計算機的同學學習了數據結構，各種樹和圖的算法。但是這些玩意怎么在GPU上跑起來，又得再開一門課來介紹。嘮嘮叨叨說這些多，其實都是想說并行算法的困難，這一點在于圖計算領域尤其突出，而對于BLAS這樣的線性代數計算庫而言，又顯得相對容易，畢竟把一個矩陣拆分成多行或者多列，這個事情理解起來基本沒什么難度。當然對于一些其他的線性代數計算庫，也存在著較多的數據依賴，導致并行較為困難的情況。
2. 性能優化方法論
這一節聊聊性能優化方法論。當不同的人談論性能優化的時候，腦子里面想的東西還不一定是同一個事。當搞網絡的人談性能優化，想的可能是怎么降低網絡延時，想的是網絡協議和socket相關的東西。當搞數據庫的人談性能優化，想的可能是怎么減少查詢數據庫的耗時，想的可能是多級索引，盡可能地減少對磁盤的訪問。當搞HPC的人談性能優化，估計腦子里立馬就涌現出cache、分塊、SIMD相關的概念。所以這里還是得說明白，這篇文章里面講的性能優化是HPC相關從業者腦子里的那種性能優化。我讀過一些論文，看過一些博客。對于不同問題的性能優化，不用的人可能有不同的方法論術語。在深度學習訓練的時候，有的時候先分IO瓶頸、CPU瓶頸、GPU瓶頸。有的時候又分為通信瓶頸、IO瓶頸、訪存瓶頸、計算瓶頸。林林總總，都有道理，都是在不同的角度去解析實際的問題。我有的時候想著，是不是能夠有一個統一的東西去盡可能地說明所有的問題。自然科學領域有一個詞叫做第一性原理，從一個最基礎的原理和規律開始，再不斷擴展到其他事物。最近有一些搞深度學習理論的科學家用到這個詞，深度學習的第一性原理，想要通過一些數學手段來解讀深度學習，從而指導模型的優化，并往通用人工智能努力。我想了想，如果HPC也要整一個第一性原理，我覺得應該就是訪存優化。所有的技巧和努力都是在試圖跨過一道墻，也就是內存墻，memory wall。之前oneflow的一篇博客提到了這個，把內存墻稱為AI算力的阿喀琉斯之踵。但我覺得AI可以去掉，內存墻是算力的阿喀琉斯之踵。
對于現代的計算機而言，相比于訪存，計算已經足夠快了。為了讓訪存盡可能地快一點，延時盡可能地少一點，科研人員絞盡腦汁，因而有了多層cache，有了TLB，有了現代計算機架構。近些年來又有人在折騰存算一體，也是挺有意思的一個領域。當然，前面是硬件的角度，軟件的角度來說，那就是HPC。我覺得高性能計算這個領域本身的存在就是通過軟件的方式來減少memory wall的影響。我們試想一下，如果沒有了memory wall，訪存足夠地快，所有的計算單元都能在瞬間拿到數據并進行計算，那么pipeline可以全部跑滿，計算單元一直保持在100%的利用率，那么HPC這個領域就沒有什么可以研究的東西了。
當我們假定了訪存優化是第一性原理之后，其實，從某種角度而言，其他的東西也可以被涵蓋到訪存優化這個大目錄下面。IO優化本質上就是對最底層的存儲結構-訪存磁盤數據的優化。通信優化本質上就是盡可能地加快不同計算節點訪問其他計算節點存儲單元的速度。而計算優化，當訪存已經優化地足夠好了之后，計算其實就基本上已經沒有什么可以優化的，無非是將循環展開，將地址對齊，將SIMD單元打滿。說完了訪存優化這個第一性原理之后，接下來擴展，說些具體的優化技巧。當我們在說訪存優化的時候，我們具體需要做些什么。總的來說，就是三板斧。一是減少數據搬運，二是減少數據訪存延時，三是保證負載均衡。
2.1. 減少數據搬運。
現代計算架構都是多級存儲，需要一級一級地將數據往計算單元上搬。如何減少數據搬運，最主要的手段就是分塊，或者說tiling。
為什么是三級分塊，不是四級或者兩級。因為NV的GPU內存結構是三級的，global mem->shared mem，shared mem->register。通過三級分塊可以盡可能地提高數據的復用性。也就是盡可能地將數據放到更近的存儲結構上進行多次利用。而如果存儲結構是四級的話，那就需要再多一次分塊。再舉個例子，對于稀疏矩陣的計算而言，常常會使用不同的存儲結構，本質上也是為了減少對于內存的訪問，壓縮效率越高，對于內存的訪問就越少。而sparse里面五花八門的各種算法，核心也是根據數據排布的不同特性，盡可能地將數據放到shared mem或者其他更近的存儲結構上cache住，從而獲得加速。
再比如我們一直在強調cache命中率，要盡可能地提高cache命中率，為什么提高cache命中率可以提高性能。原因就是：如果cache不命中，那么就要到更下層的存儲結構上去搬運數據，這個開銷就立馬上去了。所以我們說，要盡可能地保證數據連續訪問，其中最主要的一個原因就是提高cache命中率，從而避免不必要的數據搬運。當然，盡可能地保證數據連續訪問，還有一個原因是為了讓DMA搬運數據的時候更加高效。這個可以歸納為減少數據訪存延時。接下來介紹一下減少數據訪存延時。
2.2. 減少數據訪存延時。
這個部分跟減少數據搬運的區別在于，減少數據搬運是減少數據搬運的次數，但減少數據訪存延時指的是當數據搬運的次數已經確定了之后，怎么讓每一次數據搬運盡可能地更快。這個部分跟硬件綁定在一起，沒有辦法撇開硬件單獨去說這個事情。總的來說有這么幾個點。
首先是減少bank沖突，如何減少shared memory上的bank沖突，如何減少register上的bank沖突，這需要對于硬件的深入理解以及如何通過合理的數據排布來避免bank沖突。
其次是軟流水，有的時候叫double buffer，有的時候叫ping pong操作，我覺得跟預取也差不多，其思想都是一樣的，就是訪存和計算錯開，讓流水更加順暢，減少計算等待訪存導致的空泡。而NV則是把這一套思想放到了硬件，SIMT架構和CUDA的這套軟硬件一體的方式，做得實在是太漂亮了，每當我仔細地揣摩NV的這套架構時，我都會暗暗說一句，MD，真tm牛逼。通過warp切換來掩蓋訪存的開銷，再配合上標量計算。可以最低程度地減少開發者成本，一個初學者，依葫蘆畫瓢寫個簡單的CUDA kernel，很容易就能達到百分之七八十的硬件性能。再詳細地說一下這個東西，當數據訪存的時候，就讓warp stall，而后再選一個warp進行計算，通過這種方式交錯開計算和訪存，讓訪存單元一直忙碌，帶寬打滿。這個操作跟雙緩沖或者說pingpong操作里面的思路是一樣，缺點也非常一致。雙緩沖需要雙倍的存儲空間來存儲額外的數據，而SIMT架構也需要大量的register file從而保證warp被選中后能立馬接著工作。也因此，對于NV的GPU，只有極少數情況需要開發者手寫double buffer進行流水排布。
最后的技巧其實跟前面的軟流水是一個道理，就是切分更多的塊，啟動更多的warp來掩蓋訪存延時。舉個例子，以sgemv為例，給定矩陣A[M,N]，x[N]計算Ax。比如[50,1024]*100。M比較小，而N相對來說比較大的情況。如果還是按照之前的方式，讓一個warp負責一行的計算，那么只有50個warp在工作，而NV的卡上有幾十個SM，warp太小，那性能會非常地差.這個時候可以讓8個block來負責一行的數據，每個block128線程，負責128個元素。這樣的話，更多的warp可以更好地掩蓋訪存開銷，性能自然可以上去。再擴展一下，M很大，N又很小的情況，則可以讓一個線程負責一行的計算，這個過程就跟elementwise的優化比較接近了。讓多個block負責一行從而切分更多的數據塊，有的時候叫做XX2D算法。之前斯坦福和google在SC20上發的一篇叫做《Sparse GPU Kernels for Deep Learning》論文里面最重要的一個優化就是在SPMM里面，讓多個block負責一行的計算。
2.3.?保證負載均衡
關于負載均衡的話題，主要是在sparse里面談的比較多，核心都是保證兩個，block/warp之前負載均衡，thread之間負載均衡。要么讓一個block負責一個大的和一個小的，保證每個block負責的大數據和小數據加起來差不多。要么在nnz維度上進行切分，天然地保證每個block上的負載是均衡的，但這個時候需要引入額外的開銷來進行判斷數據是數據哪一行。思想都是樸素且易于理解的。在這里面，我主要想說的是硬件層面的負載均衡。我們設想一個場景，如果有100個block，block的負載是均勻的。GPU上有50個SM，按常理，每個SM負責2個block，那SM之間肯定是負載均衡的。那有沒有可能是每個SM需要負責4個block，25個block在忙碌，25個block啥也不干？正常人都會說，不可能吧。那為什么不可能，這個分配具體是什么樣的呢？只有清楚地了解了這個硬件運行機制才能清楚地說明白為什么不可能。這個機制其實就是在硬件層面如何進行block索引號和SM索引號的映射，只有清楚這個，才能保證軟件層面的負載均衡在硬件層面也是負載均衡的。
這一節介紹了性能優化的核心，也就是訪存優化。隨后又介紹了訪存優化的三板斧，也就是減少數據搬運、減少數據訪存延時、保證負載均衡。并通過大量的case來說明為什么這三者能夠有效地提高訪存性能。但遇到實際問題的時候，還是應該case by case地進行分析，切勿一上來就說我要分塊，我要避免哪哪哪的bank沖突，我要做負載均衡。一定要做足夠多的profiling工作之后，深刻地了解性能瓶頸之后，再著手進行優化。
3. 性能分析
本節介紹性能分析，也就是profiling。這個部分實在是太過于重要，所以必須單獨拎出來放在一節講。在分析任何具體的問題時，都必須做充足的profiling。其實當我們談優化的時候，需要做的工作，就是profiling找到性能瓶頸，對性能瓶頸優化，再profiling找到性能瓶頸，再對性能瓶頸優化。不斷重復，直到接近硬件瓶頸或者達到想要的目標即可。
profiling可以簡單地分為粗粒度和細粒度。粗粒度主要是判斷瓶頸是不是在GPU上，具體又是哪個kernel，典型代表就是nsight system工具，會顯示出整個程序的timeline。可以從timeline上直接清晰明了地看到瓶頸是在CPU還是GPU，如果是GPU，那又是在GPU的哪個kernel上。細粒度主要是判斷kernel或者一個函數里面的性能瓶頸在哪。
關于粗粒度的部分，其實需要說的并不多。主要是細粒度的部分需要好好嘮一嘮。怎么判斷一個kernel的性能瓶頸在哪里，這個事情其實并沒有那么簡單。需要非常豐富的經驗才能做到真正游刃有余。上一節說到了性能優化的核心在于訪存優化，性能分析里面最重要的也是對于訪存的分析。像NV的卡，主要是分為四層，DRAM、L2 cache、L1 cache + shared memory、register。我們需要盡可能地保證每一層的數據搬運效率都足夠地高，盡可能地把帶寬打滿。
如果發現實際帶寬比較差，數據搬運效率比較低，這個時候就要去思考，是不是可以有辦法，通過分塊的一些技巧來減少數據搬運。如果數據搬運不能夠再減少了的話，是否可以通過一些方式來提高數據的搬運效率，比如向量化訪存、合并訪問來提高對DRAM的訪存性能、避免bank沖突來提高對shared memory的訪存性能、調整分塊大小來讓更多的warp跑起來從而減少訪存的延時，如果不是SIMT架構，就需要精細地設計各級訪存的pipeline，讓訪存操作盡可能地pingpong起來，從而讓訪存流水盡可能地連續起來不要被打斷。理論大概是這樣，但是每一個問題都有著不同的處理方式，每一個問題可能都是不同的瓶頸。總之就是萬變不離其宗，準確地評估每一級存儲的訪存效率然后盡可能地提高每一級的訪存效率，盡可能地把訪存流水打滿，不要有空泡。
大概地說了一下profiling，然后再提一下MicroBenchmark。很多時候，硬件廠商給出的性能分析工具不可能覆蓋所有的東西，也不可能詳細地告訴開發者相應的細節，尤其是一代新硬件出來之后。比如說訪問global memory需要多少個cycle，訪問L2 cache需要多少個cycle，訪問shared memory需要多少個cycle，訪問寄存器時寄存器號和bank索引號的映射關系。這些東西都需要進行詳細的microbenchmark才能讓我們更加了解硬件從而指導優化。至于怎么指導優化，這又可以另外開一個話題詳細地說。舉個例子，做矩陣乘法的優化時，可以大概地評估從shared memory訪存需要多少個cycle，然后再相應地計算出往里面加多少條計算指令差不多可以掩蓋shared mem訪存的開銷。當然這部分跟warp切換也有關系，不同的參數選擇會導致不同的warp活躍數，warp切換的話，會產生不同的影響。再比如我們需要知道指令cache的大小，這樣的話，對于計算密集型的kernel，可以大概確定分塊的大小以及循環展開的次數，這個時候說一下GEMM里面為啥很多介紹都是使用128*8的shared memory塊和8*8的寄存器塊，因為這個數字所需要的空間開銷，可以使得每個SM上跑大概4個左右的block，用上雙緩沖能掩蓋訪存開銷，并且計算的部分循環展開到8，使用的指令數差不多剛好可以在指令cache中放下。當然這個數據針對不同的硬件又有所不同，所以每一代硬件都需要單獨進行處理。關于這部分的內容有很多的MicroBenchmark和CostModel相關的論文，大家有興趣可以去查一下。
4. 小結和感悟
4.1. 經驗or完善的知識體系
大家普遍會覺得高性能計算是一個非常注重經驗的領域，很多東西都是case by case的方式。每一個問題都需要進行具體的分析，一個新手入門時，遇到性能問題總是容易束手無策，常常會有疑問，“這個kernel性能應該怎么提高？”“為什么別人的代碼比我快好幾倍？”有的時候苦思冥想都很難找到關鍵的點，很難提高代碼的性能，長久下去就喪失信心，不再愿意做這個方向。這些情況大多數都是因為經驗不足，但所有人都是從新手村里出來的。有的時候想想為什么會出現這個原因，我覺得，主要還是因為這個領域目前關注的人還不是很多，而且中國關于這方面的學科建設并不成熟，在本科期間，只有極少數的人接觸過CUDA編程或者高性能計算，一般只有研究生才能接觸到，而且說實話，目前國內做這方面工作的高校并不多。所以每一年培養出來的合格的人才其實非常少，而且只在少數top高校能夠找到合適的人。也因為搞的人少，相關的文檔和資料非常少。在網上可以很容易找到某個深度學習算法的解析，但是很難找到詳細的中文文檔來告訴大家怎么分析性能怎么提高性能、怎么一步步地達到硬件極限。總之高性能計算是一個比較吃經驗的領域，什么叫做經驗，經驗就是有著完善的知識體系，真正去做了很多實踐，形成系統的方法論，這就是經驗。
4.2. 通用代碼or針對性優化。
這些年隨著硬件產品的不斷涌現，對計算庫的需求也越來越多。針對不同的硬件架構、不同的算子、不同的數據排布都要針對性進行優化，這個工作量非常巨大。所以工業界和學術界都在思考著如何減少計算庫開發的人力成本，如何讓代碼在更多的硬件設備上跑起來且性能還OK，如何實現性能可移植可擴展。目前TVM、XLA等相關的深度學習編譯器在這方面做出了突出的工作。采用了Halide的思想將一系列成熟的優化技巧封裝到schedule中，再通過代碼生成的方式，就能達到不錯的性能。再加上圖優化，通過一系列的fusion就能優化整張圖的計算耗時。總得來說，非常牛逼，也解決了一些工業界的問題，于是掀起了一股研究的浪潮。細細去想為什么TVM這樣的深度學習編譯器能夠成功，在某些程度上在于深度學習里面需要的算子相對簡單，大部分還是GEMM、reduce、elementwise這樣的訪存模式，而這些東西在高性能領域研究地足夠透徹，并且現在主流的硬件已經做得足夠牛逼，所以相對簡單的優化策略就能生成性能比較好的kernel。但如果真的要在工業場景落地，還是比較依賴于硬件廠商經過細致調優的計算庫，當然這兩者也不是對立關系，實際上是相輔相成的，相互配合使用，在不同的應用場景中發揮作用。話再說回來，如果真的能夠實現一套通用代碼來實現多種硬件設備，且保證性能OK，生產環境能用起來用的好，在科學計算和深度學習等多個領域都能work。這會是一個極其牛逼的工作。但是這里面需要花費巨大的人力成本和時間成本，而且需要一定程度上的理論突破。個人覺得，還是學術界來主導，然后一些天才型的開發者掌握合適的方向，再做幾年冷板凳沒準會有一些成果出來。然后再由工業界不斷地迭代幾輪，達到成熟。
4.3. 正確地評估和認識。
這里想說的倒不是profiling那些東西，而是說一下我的一些感悟。就是看待別人的一些工作時，盡可能地理智客觀，如果有必要，最好動動手。有的事情，看著比較難，比如說寫一個kernel性能超過官方庫啥啥的，其實如果針對特定的數據，特定的硬件，特定的庫版本，如果還不到硬件極限的話，要超越官方庫是一個相對簡單的事情，無非是多一些hard code，根據數據特性和硬件特性，總是能把性能提上去。但有一些官方庫在特定的硬件上已經做了非常好的優化，盡量就不要再另外花時間去想著超越官方庫了，意義不大。有的事情看著比較簡單，實際上會有各種阻力，中間可能會遇到各種困難。比如做計算庫，很多時候功能可能比較簡單，就像blas，但實際上要針對各種硬件，針對各種數據排布都能有一個比較好的性能，這個是非常困難的，里面所需要的精力和耗時也不是外行人能夠搞清楚的。
總結一下，就是盡可能地跟專業的團隊做專業的事情，如果對其他領域不是那么那么清楚，沒有真正寫過相關代碼，沒有踩過相關的坑，那不要亂下結論，不要總是拍腦子想事情。這一點其實非常重要，整個人類社會出現外行領導內行的情況非常多，其實倒不可怕，最可怕的是外行覺得自己是內行，總是瞎指揮。那小到幾人的團隊，大到一個國家，都容易出現問題。
