Week#8 開發記錄

作業要求 (B)

  • 說明 naive_transpose, sse_transpose, sse_prefetch_transpose 之間的效能差異,以及 prefetcher 對 cache 的影響
  • 在 github 上 fork prefetcher,嘗試用 AVX 進一步提昇效能
  • 修改 Makefile,產生新的執行檔,分別對應於 naive_transpose, sse_transpose, sse_prefetch_transpose (學習 Homework #2 的做法)
  • 用 perf 分析 cache miss/hit
  • 詳細描述實驗設計,以及你的觀察
  • 建立新的 Hackpad,列於「+作業區」,需要標注「開發紀錄 (B)」
 

Learn prefetcher

  • 先分析一下原始碼,首先是naive_transpose,其實現最簡單的矩陣轉置想法,從矩陣的左上角第一個元素開始,把舊矩陣中的元素按轉置後的順序存入新的矩陣中
void naive_transpose(int *src, int *dst, int w, int h)
{
    for(int x = 0; x < w; x++){
        for(int y = 0; y < h; y++){
             *(dst + x*h + y) = *(src + y*w + x);
        }
    }
}
  • 接著sse_prefetch_transpose,使用了Intel處理器SIMD的技術,在+Week#1有做簡單的整理,簡單說就是一次將4筆資料放入sse暫存器中,執行一條指令就可以完成4筆資料處理。
  • SSE指令的格式:
  • _mm_unpacklo_epi32(I0, I1)讀入兩個128位暫存器後會使用他們的2個低32位值,返回[a0, b0, a1, b1],_mm_unpackhi_epi32同理,而_mm_unpacklo_epi64則是一次取64位
  • 這種方法的效能改進在:
  • 一條指令處理4筆數據,要比4筆數據4條指令處理快
  • loop unrolling:
  • 執行loop循環的組合語言代碼執行次數會變少
  • branch prediction miss機率降低
  • wikipedia還提到如果數據沒有相依性有機會使用並行處理,在這裡SIMD已經實現
void sse_transpose(int *src, int *dst, int w, int h)
{
    for(int x = 0; x < w; x+=4){
        for(int y = 0; y < h; y+=4){
            __m128i I0 = _mm_loadu_si128 ((__m128i*)(src+y*w+x));
            __m128i I1 = _mm_loadu_si128 ((__m128i*)(src+(y+1)*w+x));
            __m128i I2 = _mm_loadu_si128 ((__m128i*)(src+(y+2)*w+x));
            __m128i I3 = _mm_loadu_si128 ((__m128i*)(src+(y+3)*w+x));
            __m128i T0 = _mm_unpacklo_epi32(I0, I1);
            __m128i T1 = _mm_unpacklo_epi32(I2, I3);
            __m128i T2 = _mm_unpackhi_epi32(I0, I1);
            __m128i T3 = _mm_unpackhi_epi32(I2, I3);
            I0 = _mm_unpacklo_epi64(T0, T1);
            I1 = _mm_unpackhi_epi64(T0, T1);
            I2 = _mm_unpacklo_epi64(T2, T3);
            I3 = _mm_unpackhi_epi64(T2, T3);
            _mm_storeu_si128((__m128i*)(dst+(x*h)+y), I0);
            _mm_storeu_si128((__m128i*)(dst+((x+1)*h)+y), I1);