HPC：程序優(yōu)化思考
今天老大在群里說了一個(gè)程序優(yōu)化的事情，就順便想了一下這個(gè)問題，但是比較零散不成體系，下午好好想了想和整理了一下，感覺相對有些完整了，就記錄下來，這些年來光寫代碼不歸納和總結(jié)，這樣是不好的
一、概述
以前學(xué)編譯原理的時(shí)候，記得老師說過一句話，說做編譯優(yōu)化的人永遠(yuǎn)不會失業(yè)，因?yàn)榫幾g優(yōu)化沒有盡頭，而編譯優(yōu)化實(shí)際上是程序優(yōu)化的一個(gè)子集，所以同理，程序優(yōu)化也沒有盡頭，本文想從下面圖中所示的三個(gè)層面對程序優(yōu)化做一點(diǎn)總結(jié)：
圖1
先說明一下上面圖示中的以特定算法為前提這句話的意思，同樣一個(gè)問題，不同的算法有不同的時(shí)空復(fù)雜度，算法就像基因一樣，屬于程序性能的先天因素，只有好的算法加上后面說到的各種合理優(yōu)化手段，才能讓程序性能在特定硬件平臺上有更出色的表現(xiàn)。
再看圖中的宏觀現(xiàn)象層面，這里的占滿都是指有效占滿（舉個(gè)極端的例子，比如設(shè)置一個(gè)無限循環(huán)讓處理器一直算A*B，這種占滿如果不是為了解特定的問題，通常情況下就認(rèn)為是無效占滿）：
CPU占滿：這個(gè)很好理解，理想情況下，當(dāng)然是不浪費(fèi)CPU的每一個(gè)cycle，讓CPU一直在忙
帶寬占滿：這個(gè)其實(shí)和減少訪存（比如通過提高Cache利用率和命中率等方式）不互相矛盾，這里指的是在盡量減少訪存的前提下把帶寬占滿，用更容易理解的話來說，就是讓各種器件盡可能都能一直保持在工作狀態(tài)，沒人在偷懶
當(dāng)然上面說的都是理想情況，實(shí)際上總會有一些bottleneck，讓某些器件時(shí)不時(shí)處于空閑狀態(tài)，這基本上都是由于處理器的處理速度和數(shù)據(jù)加載速度不匹配所造成的，Cache就是為了緩解這種速度不匹配而出現(xiàn)的。
為了能讓物理器件盡可能的達(dá)到上面說的理想情況，做程序設(shè)計(jì)的時(shí)候，相對應(yīng)的需要考慮并行、流水、訪存這些方面，下面從工程實(shí)踐的角度具體一個(gè)個(gè)來看這三個(gè)方面。
二、并行
說到并行，可能大家很快就會想到多線程/多進(jìn)程和分布式（本文就不提分布式了），實(shí)際上并行還有其他的實(shí)現(xiàn)途徑，我感覺并行在工程實(shí)踐的角度可以分為下面圖中的幾個(gè)方面：
圖2
先看多線程/多進(jìn)程這種并行手段，如果處理器是多核的，那么很好理解，通過把任務(wù)劃分成多個(gè)子任務(wù)，每個(gè)處理器核完成一個(gè)子任務(wù)，這是真正的物理上的并行，如果處理器是單核的，實(shí)際上多個(gè)線程/進(jìn)程之間是系統(tǒng)內(nèi)核通過某種調(diào)度算法來實(shí)現(xiàn)的邏輯上的并行，雖然是邏輯上的并行，也是有可能提高硬件使用效率的，最簡單的例子，兩個(gè)進(jìn)程A、B，進(jìn)程A需要在內(nèi)存和外設(shè)之間通過DMA傳一批數(shù)據(jù)，那么在傳數(shù)期間，不需要CPU參與，那么自然可以把CPU讓給進(jìn)程B使用，這樣一來，CPU的使用效率就上去了。當(dāng)然這里分析的都是理想情況，忽略了線程/進(jìn)程調(diào)度本身的開銷等因素。
再看SIMD（單指令多數(shù)據(jù)），原理很簡單，從名字就可以看出來，指令可以運(yùn)算向量數(shù)據(jù)（拿加法來說，傳統(tǒng)指令一次只能算a+b，而這種指令一次可以算a1+b1、a2+b2、a3+b3、a4+b4），之前寫過不少相關(guān)的代碼，ARM系列芯片是通過NEON指令集實(shí)現(xiàn)的，X86系列芯片是通過SSE、AVX指令集實(shí)現(xiàn)的，寫這種代碼時(shí)主要需要注意的問題是內(nèi)存對齊，還有一些corner case的處理（比如有5個(gè)數(shù)，而這種指令一次只能4個(gè)4個(gè)一起處理），Halide中的vectorize這個(gè)schedule生成的就是這種優(yōu)化代碼。
最后看下SIMT（單指令多線程），主要是CUDA編程的范疇，老實(shí)講這個(gè)我了解的很少，之前一直做專用加速器的相關(guān)應(yīng)用，工作中沒用過CUDA，之前看過一點(diǎn)書，寫了兩篇筆記：
總體來講CUDA這方面的知識，目前還處于小白水平，以后有機(jī)會有時(shí)間好好學(xué)一下吧～
三、流水
流水這個(gè)問題在編譯器中是很重要的一個(gè)問題，以下圖為例來說明這個(gè)問題：
圖3
在上圖中，假設(shè)有三種硬件邏輯，Load（拿數(shù)給CPU）、Compute（用拿到的數(shù)做運(yùn)算）、Save（把計(jì)算結(jié)果傳回主存），如果每種操作所用的時(shí)間相同，那么經(jīng)過若干系統(tǒng)時(shí)鐘周期之后，所有的硬件邏輯都能處在一直工作的狀態(tài)，這是最理想的情況，但現(xiàn)實(shí)往往不是理想的，如果Load、Save的時(shí)間比Compute的時(shí)間長，如下圖所示：
圖4
這時(shí)候Compute對應(yīng)的硬件邏輯就會忙一會閑一會，也就是流水流起來之后兩次Compute之間有g(shù)ap，這里如果Load、Save花的時(shí)間相對Compute多太多的話，某些情況下re-compute會是一個(gè)優(yōu)化手段，即如果需要使用到以前的某個(gè)計(jì)算結(jié)果，但是Load、Save的開銷又比較大，還不如重新算一次來的快，OneFlow中的后向計(jì)算中就使用了這種優(yōu)化，具體可參考公司同事寫的這篇《亞線性內(nèi)存優(yōu)化— activation checkpointing在oneflow中的實(shí)現(xiàn)（https://zhuanlan.zhihu.com/p/373662730）》。
還有一種情況，就是Compute所用時(shí)間比Load、Save多，如下圖所示：
圖5
在這種情況下，如果需要使用到以前的某個(gè)計(jì)算結(jié)果，在Compute所用時(shí)間比Load、Save多太多的情況下，re-load可能會是比較好的選擇。
四、訪存
訪存問題幾乎是我們寫代碼時(shí)打交道最多的一個(gè)問題，先做一下這類問題的分類，如下圖所示：
圖6
先看訪問外存的優(yōu)化，這部分大家可能乍一聽覺得接觸不多，確實(shí)如此，這部分的優(yōu)化大部分都被操作系統(tǒng)或者標(biāo)準(zhǔn)庫做掉了，除非是寫一些文件讀寫相關(guān)的程序，我們很少需要關(guān)注，但如果把一些常用外設(shè)的訪問也放在這一類的話，比如標(biāo)準(zhǔn)輸入、標(biāo)準(zhǔn)輸出等，舉個(gè)最簡單的例子，如果用cout << xxx << endl這樣的代碼輸出信息到stdout并換行，需要注意下endl的含義，直接看標(biāo)準(zhǔn)庫中endl的實(shí)現(xiàn)會比較清楚：
// https://github.com/RTEMS/gnu-mirror-gcc/blob/master/libstdc++-v3/include/std/ostream#L678template<typename?_CharT,?typename?_Traits>inline?basic_ostream<_CharT,?_Traits>& endl(basic_ostream<_CharT,?_Traits>&?__os){ return flush(__os.put(__os.widen('\n'))); }
可以看到endl中調(diào)用了flush，所以cout如果頻繁使用endl來換行的話，速度肯定會慢，當(dāng)然這個(gè)要看使用場景，如果想盡量實(shí)時(shí)顯示運(yùn)行輸出，那這樣使用沒問題。
再看訪問內(nèi)存的優(yōu)化，其實(shí)應(yīng)該更細(xì)分為使用棧和使用堆的優(yōu)化：
先看使用棧的優(yōu)化，大家可能馬上想到的是標(biāo)準(zhǔn)庫中的棧，實(shí)際上我們在寫代碼的時(shí)候，我們用的更頻繁或者說每個(gè)人都必然會用到的是函數(shù)的調(diào)用棧，函數(shù)的調(diào)用有開銷，主要是棧上操作的開銷，inline的作用就是為了做這種函數(shù)調(diào)用優(yōu)化，但inline也不是萬能的，它一般只適用于短小精悍的函數(shù)，否則函數(shù)展開之后容易導(dǎo)致代碼膨脹，代碼膨脹會導(dǎo)致生成的binary變大、CPU的指令cache效率變低等問題。之前講的表達(dá)式模板中的優(yōu)化手段歸根結(jié)底也是利用編譯器在編譯期把模板函數(shù)實(shí)例化之后遞歸調(diào)用的inline函數(shù)做展開來實(shí)現(xiàn)的。
再看使用堆的優(yōu)化，也就是通常意義上我們所說的訪存，這是我們寫代碼考慮最多的部分，這部分需要和上面圖6中的訪問cache這部分一起說，寫代碼的時(shí)候既需要考慮內(nèi)存管理（這是個(gè)非常大的話題，可參考之前寫過的一個(gè)相關(guān)系列《內(nèi)存管理：小結(jié)》），又需要考慮和cache的交互，即根據(jù)程序的局部性原理來盡可能的提高cache的使用率和命中率，Halide中的reorder這個(gè)schedule就是來解決這個(gè)方面問題的。
五、Summary and Reference
關(guān)于程序優(yōu)化可說的實(shí)在太多了，一方面我們自己寫的應(yīng)用代碼中自己會做手動優(yōu)化，另一方面還有一些專門的工具如Halide可以做自動優(yōu)化，它里面的fuse、split、tiling、unrolling、reorder、vectorize、parallel等等這些schedule就是在從本文談的并行、流水、訪存這些方面來做優(yōu)化，還有一個(gè)感覺需要提的工具是Polyhedral，這個(gè)我不大懂。。。只是從公眾號和知乎上看過Polyhedral專家趙捷博士（知乎名字是要術(shù)甲杰，公眾號的三篇文章我貼會在最后，此外還有相關(guān)的論文我沒看過）的一些科普文章，目前只看了個(gè)熱鬧，原理性的東西還沒大看懂（捂臉），以后有時(shí)間一定要好好學(xué)一學(xué)。其實(shí)關(guān)于“以后有時(shí)間”這句話我感觸良多，到底啥時(shí)候有時(shí)間我也不知道，感興趣的東西太多，每個(gè)都要花很多時(shí)間研究，那么時(shí)間到底應(yīng)該花在誰身上呢？不會的東西太多，每個(gè)都要花很多時(shí)間學(xué)習(xí)，那么時(shí)間到底應(yīng)該花在誰身上呢？
最后列一下參考資料：
CSAPP的兩個(gè)章節(jié)：
《第五章：優(yōu)化程序性能》
《第六章：存儲器層次結(jié)構(gòu)》
NEON和AVX的官方文檔
CUDA相關(guān)的書，我買了下面這幾本，大家做參考：
《CUDA C編程，權(quán)威指南》
《GPU高性能編程，CUDA實(shí)戰(zhàn)》
《CUDA并行程序設(shè)計(jì)，GPU編程指南》
《CUDA編程，基礎(chǔ)與實(shí)踐》
Halide官方文檔和代碼
Polyhedral相關(guān)的文章，主要來自趙捷博士，知乎上的文章大家自己去搜，下面列一下公眾號上的三篇文章：