Re: [問題] 如何讓計算速度發揮到極限

[littleshan (我要加入劍道社!)]

※ 引述《Lepton (輕子)》之銘言：
: → littleshan:然後若要利用到SSE，在這例子中要把內層迴圈拆開        08/14 23:52
: 可以給點示範嗎?拆掉內層迴圈無所謂
原本的例子有點複雜，我這邊舉個簡化後的例子

假設還沒拆迴圈的 code 長這樣：

    for(int i = 0; i < N; ++i)
        v_new[i] = v[i] + rho[i];

我講的拆迴圈 (loop unrolling) 意指一次處理多個元素

    for(int i = 0; i < N; i+=4){
        v_new[i] = v[i] + rho[i];
        v_new[i+1] = v[i+1] + rho[i+1];
        v_new[i+2] = v[i+2] + rho[i+2];
        v_new[i+3] = v[i+3] + rho[i+3];
    }

然後這邊利用 SSE 裡面的向量運算

    for(int i = 0; i < N; i+=4){
        __mm128 a = _mm_load_ps( v+i );
        __mm128 b = _mm_load_ps( rho+i );
        __mm128 c = _mm_add_ps(a, b);
        _mm_store_ps(v_new+i, c);
    }

_mm_load_ps(v+i) 意指從 v+i 這個位址開始把後面四個 float 載入暫存器 a 中
也就是 v[i], v[i+1], v[i+2], v[i+3]
同理下一行把 rho[i] ~ rho[i+3] 也載入到暫存器 b
然後 _mm_add_ps(a, b) 同時做完四個加法
再把結果存到 v_new[i] ~ v_new[i+3]

這樣做通常可以有明顯的效能提昇 (如果這邊是主要的效能瓶頸)
但要小心的地方很多
比如說你的資料量不一定是四的倍數，多出來的部份要另外計算
另外 load_ps 與 store_ps 要求目的位址是 aligned to 16bytes
所以在配置記憶體的時候需要額外處理


: ※ 編輯: Lepton          來自: 1.170.79.135         (08/14 23:56)
: → purincess:cache miss panelty比改動esp/ebp及branch miss所要花的  08/14 23:57
: → purincess:cycle大太多了 先如l大考慮cache會比較好                08/14 23:57
: → purincess:                      branch prediction miss^         08/15 00:00
: hi,我知道在GPU也有cache的問題但在CPU上要怎樣處理這個問題我不熟悉
你原本的計算順序是這樣 (以100x100為例)

        1   2   3   4  ...  100
      101 102 103 104  ...  200
      201 202 203 204  ...  300


如前所述，存取跨列元素時很容易造成 cache miss
而另一個計算順序是這樣


       1   2   3   4   5   6   7   8    ┌→ 65  66  67  ...  72
       9  10  11  12  13  14  15  16    │   73  74  75  ...  80
                  ...                   │    ...
                  ...                   │    ...
      57  58  59  60  61  62  63  64  ─┘


也就是說，以 8x8 小區塊為單位，一個小區塊計算完成再移到下一個
而使用的資料也就是 V 和 rho 的元素排列順序也要改成區塊式的排列
這麼一來只有在計算區塊邊緣時容易產生 cache miss
區塊內部就能有效利用 cache hit 帶來的效能

另外這邊的 8x8 只是範例，實際上應該要視你的元素型別與 cache 大小來選擇
或是無腦實驗看看哪個大小可以比較快



最後....

如果你已經有速度很快的 GPU 版本
其實沒必要那麼認真的對 CPU 做最佳化不是嗎....

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 202.39.238.242
推 Lepton:我發現這跟寫GPU的概念蠻像的block、unroll我都懂
→ Lepton:會要做CPU高效率是因為CPU閒著也是閒著我想讓他做點事情
→ Lepton:只是我感覺到CPU做事情太慢了想讓他再做更多事情
推 Lepton:看你的示範SSE似乎還滿簡單易懂的只是重編寫一次就好了
→ littleshan:如果你用的是OpenCL配合適當的driver
→ littleshan:其實可以讓CPU與GPU一起執行同一份kernel code
推 Lepton:openCL我還沒學不過聽說CUDA的卡因為架構的差異跑CL不快
→ Lepton:openCL之後我會去學。也感謝你的回覆讓我學習
推 forloricever:用 Eigen 可以讓你少手刻一點 SSE
推 TeaEEE:nvidia跑CL並不會比AMD的差阿？