轉載：http://blog.sina.com.cn/s/blog_70684c2a0100vjhj.html
這兩天看到Vasily Volkov牛人的ppt，對如何更有效的使用GPU做通用計算提出了增加線程級并行以外的另一種方法---增加指令級并行，受益匪淺。剛好也沒找到中文版本，就翻譯過來與大家交流下，有錯誤請各位牛人指正，所有的實驗結果和圖檔均出自原ppt。請參考《Better Performance at Lower Occupancy》後面兩個案例有時間會放上來...
-------------------------------------------------------------------------------------------------
為提升GPU的效率，常用的方法是提升裝置占用率(occupancy)，包括在每個流處理器上運作更多的線程和為每個線程塊設定更多的線程。人們常常認為這是隐藏延遲的唯一方法，但我們的實驗結果證明最大化占用率反而可能會降低性能：
大矩陣相乘，單精度浮點（SGEMM）
1024點複數到複數快速傅裡葉變換（FFT），單精度浮點：
兩個常見謬誤：
1. 多線程是GPU上隐藏延遲的唯一方法
2. 共享記憶體和寄存器一樣快
整個報告分成五部分：
1. 使用更少線程隐藏計算延遲
2. 使用更少線程隐藏記憶體通路延遲
3. 使用更少線程來加速
4. 案例研究：矩陣相乘
5. 案例研究：FFT
1. 使用更少線程隐藏計算延遲
計算的延遲
延遲：執行操作所需時間。一次計算操作需要約20個時鐘周期，一次記憶體通路操作需要400+個時鐘周期：
以上代碼中計算z時，由于z對x的依賴性，在計算x的延遲期内（約20cycle），該操作無法執行。但y的計算由于沒有依賴性，因而可以與x的計算重疊（即在20cycle内執行）。
計算的吞吐量
延遲的概念常常與吞吐量的概念混淆，比如“計算比記憶體操作快100倍----每個warp（G80）隻需花費4個時鐘周期，而記憶體操作要花費400個時鐘周期”這句話就是錯誤的，因為前者是比率，而後者是時間。
吞吐量：每個時鐘周期完成多少條指令。
計算：1.3Tflop/s = 480 ops/cycle（指令每周期）（指令為乘加運算）
通路顯存：177GB/s ≈ 32 ops/cycle (指令為32位裝載)
隐藏延遲：在延遲等待時做其他的操作。這樣可以運作更快，但上限為峰值。那麼怎樣達到峰值呢？
使用裡特爾定律（Little’s law），即所需并行度=延遲*吞吐量
那麼目前裝置的并行度怎樣呢？
（延遲随指令的不同而變化）
由于指令的延遲固定，如果沒有足夠的并行度，就不可能達到100%的吞吐量，也就是說沒有足夠多的運作中指令，那麼就存在空閑指令周期。
怎樣得到足夠的并行度？
線程級并行（TLP）：通常做法是使用足夠的線程來提供需要的并行度，比如：在G80上每個SM執行192個線程。
指令級并行（ILP）：但你同樣可以在單個線程内利用指令間的并行性來達到足夠的并行度。
你可以在GPU上同時使用ILP和TLP
這個規則适用于所有可以運作CUDA的GPU。
比如在G80上，如果沒有ILP，你可以通過25%的GPU占用率達到100%的峰值；或者，在每個線程中有三條指令可以同時進行的情況下，通過8%的GPU占用率達到峰值。
而在GF104上，如果要達到66%以上的峰值性能，你則必須應用IPL，因為：每個SM中有48個核，單條指令每次廣播給16個核。而為了使每個核都有指令執行，單個時鐘周期内必須分發3條指令，但事實上每個SM中隻有2個warp排程器，無法分發3條指令。是以NV在這裡提供了ILP，每個warp在同一指令周期内卻可以分發兩條以上的指令，這就給我們提供了使每個核都有指令執行的方法。
我們用實驗來證明：
1.不用ILP來運作大量計算指令
将N_ITERATIONS設定為一個很大的數，選擇合适的UNROLL，并保證a,b,c都存儲在寄存器中。執行一個block（即隻使用一個SM），選擇不同的線程塊大小，檢測所能達到的性能：
GPU為GTX480，理論峰值為1.3Tflop/s，一個SM就是89.6Gflop/s（1.3T/15, GTX480中有15個SM）
可以看到，如果沒有ILP，一個SM上需要576個線程才能達到100%的使用率
2. 引入指令級并行
實驗ILP=2時，即每個線程執行2條互相獨立的指令，
那麼如果使用更多線程是在GPU上隐藏延遲的唯一方法，則我們應該得到相同的性能曲線，事實上：
虛線标出的是原本曲線，可以看出：
當ILP=2時，隻需要320個線程就能達到100%的使用率
加入更多的指令級并行：
當ILP=3時，每個線程3條獨立指令：
得到的結果是：
即當ILP=3時，隻需要256個線程就可以達到100%使用率。
不幸的是，當ILP超過4時，就不會再擴充了（lz：猜想每個warp在一個時鐘周期内最多就隻能分發4條指令了）
當ILP=4時，需要192個線程就能達到100%的使用率。
總結：可以通過兩種方法隐藏計算延遲
這條同樣适用于其他GPU，比如G80架構
謬誤：提升占用率是隐藏延遲的唯一方法？錯誤，提升ILP是另一種方法。
謬誤：占用率是衡量GPU使用率的标準？錯誤，它隻是一個影響因素。
謬誤：“為完全隐藏計算延遲，流處理器必須在計算能力為1.x的裝置上運作至少192個線程，或者在計算能力為2.0的裝置上運作384個線程”（出自CUDA Best Practices Guide）。錯誤，在G80-GT200上通過64個線程，在GF100上通過192個線程同樣可以達到目的。
上一部分是用IPL隐藏指令延遲，這一部分是用ILP隐藏顯存通路延遲。
----------------------------------------------------------------------
2.使用更少線程隐藏記憶體通路延遲
隐藏記憶體通路延遲，使用相同的說明方式，但針對記憶體操作。
所需并行度 =延遲 * 吞吐量
是以隐藏記憶體延遲意味着保持100KB的資料讀取速率，當然如果kernel是計算限制（compute bound）的，則這個數值可以變小。
那麼，多少線程可以達到100KB呢，有多種方法：
1. 使用更多的線程
2. 使用指令級并行（每個線程進行更多次存儲通路）
3. 使用位級（bit-level）并行（使用64/128位方式存儲通路）
每個線程做更多的工作，則線程數量可以更少：每個線程取回（fetch）4 Byte，需要25000個線程，取回100B，僅需要1000個線程。
經驗驗證：
每個線程拷貝一個浮點數：
運作多個線程塊，通過動态配置設定共享記憶體來控制SM占用率。
每個線程拷貝單個浮點數（GTX480）
隻能通過最大化占用率來隐藏延遲嗎？不，也可以每個線程做更多的并行工作。
注意，線程并不會被存儲通路阻塞，它隻會因為資料依賴性而阻塞。
每個線程拷貝2個浮點數
虛線部分為原曲線，是以我們可以減少占用率了。
注意，本地數組會盡量配置設定在寄存器中，以下是每個線程拷貝4個浮點數
可以看到，僅僅25%的占用率就足夠了，那麼我們究竟能做到什麼程度？
以下是拷貝8個浮點數：
每個線程拷貝8個float2型資料，
每個線程拷貝8個float4型資料
隻通8%的占用率就達到了87%的pin帶寬！
每個線程拷貝14個float4型資料
隻通過4%的占用率就達到了峰值的84%。
有兩種方法來隐藏記憶體通路開銷
謬誤：“低占用率常常會影響GPU隐藏記憶體延遲的能力，進而導緻性能下降。”（CUDA Best Practices Guide）。我們剛才看到，僅僅4%的占用率就可以達到峰值的84%，注意這已經超過了cudaMemcpy所能達到的最好性能（71%）。
謬誤：“一般來說，需要更多的warps，如果對片下記憶體的通路指令比例。。。”（CUDA Programming Guide）錯，我們剛才看到了，在一個記憶體通路密集型的kernel中，每個SM僅僅隻有4個warps就可以達到87%的記憶體性能峰值。
前兩部分是有關ILP隐藏計算和訪存延遲，進而在GPU低占用率的情況下達到高并行度和吞吐率。下一部分是讨論在共享記憶體（shared memory）和寄存器（register）之間的權衡，作者從吞吐率的角度上說明使用共享記憶體達不到最好性能，最好降低占用率進而盡可能多的使用寄存器。
----------------------------------------------------------------------------------------------
3.使用更少線程運作更快
使用更少線程意味着每個線程擁有更多的寄存器。
每個線程的寄存器數：
GF100：在100%占用率時有20個，在33%占用率時63個，為3倍。
GT200：在100%占用率時有16個，在12.5%占用率時約有128個，為8倍
那麼每個線程有更多的寄存器是不是更好呢？
隻有寄存器的速度才能足夠達到峰值。考慮這樣一個計算: a*b+c：2個flops，12B輸入，4B輸出，則對于1.3Tflop/s的計算峰值，需要8.1TB/s的帶寬，寄存器可以滿足這樣的要求，我們來看看共享記憶體（shared memory）能不能達到？
隻有 4B*32banks*15SMs*half 1.4GHz = 1.3TB/s
需要的帶寬和可以達到的帶寬比較：
lz：可以看出共享記憶體的帶寬是全局記憶體（顯存）的7.6倍，而寄存器是共享記憶體的6倍，至少需要8TB/s的帶寬才能讓GPU的計算達到峰值，寄存器可以做到（廢話，做不到這個計算峰值就根本不存在了）。
謬誤：“事實上，對一個warp中的所有線程來說，如果線程間沒有bank conflicts，通路共享記憶體和通路寄存器一樣快。”（CUDA Programming Guide）
不，在Fermi架構中，共享記憶體的帶寬比寄存器慢6倍以上。（非Fermi為3倍）
運作更快可能需要更低的占用率：
1. 必須使用寄存器才能接近峰值
2. 不同存儲的帶寬差距越大，越多的資料就必須從寄存器中讀取
3. 而使用越多的寄存器意味着越低的占用率
這常常可以通過每個線程計算更多的輸出來完成。
對線程來說，越多的資料存放于寄存器意味着越少次數的共享記憶體通路。越少的線程，但每個線程做越多的工作，使得低占用率不成問題。
從Tesla到Fermi是一種倒退嗎？
共享記憶體帶寬和計算帶寬的差距增加了：
使用快速的寄存器會有幫助，但寄存器的數目被嚴格限制：
G80-GT200: 每個線程最多128個寄存器
Fermi：每個線程最多64個寄存器