Chen-hsiu Huang's Blog

這兩段短文是去年六月的時候寫的, 當時基於經驗分享, 就寫下來張貼在公司內部的討論區上, 久了也就忘了
前兩天有同事跑來跟我討論這個問題, 結果他照著我這兩段短文的做法去改, 當場就快了 10%
聽了其實蠻高興的, 畢竟經驗能夠累積, 不走冤枉路, 總是好事一件
就再翻出來放到 blog 上充充版面. 有時候看看以前寫的東西, 也蠻有趣的

---

64K aliasing conflict fix (part I)

這幾天剛好在處理 64K aliasing 的問題, 就順便分享一下. 先來看下面這段簡單的 code:

void Split_RGB24(BYTE *buffer, BYTE *pR, BYTE *pG, BYTE *pB, int width, int height, int stride)
{
  int i, j;
  for(i = 0; i < height; i++) {
    for(j = 0; j < width; j++) {
      *pB++ = *buffer++;             // 64K aliasing conflict
      *pG++ = *buffer++;             // 64K aliasing conflict
      *pR++ = *buffer++;             // 64K aliasing conflict
    }
    buffer += (stride - width * 3);
  }
}

這個 function 在 vtune 上跑的並不快, 原因就是 64k aliasing. 因為 pR, pG, pB 這三個 buffer 是這樣宣告的:

BYTE *pR = (BYTE *) _mm_malloc(m_Width * m_Height, 64);
BYTE *pG = (BYTE *) _mm_malloc(m_Width * m_Height, 64);
BYTE *pB = (BYTE *) _mm_malloc(m_Width * m_Height, 64);

似乎當我們 malloc 大的區塊, 系統會傾向於把這些 buffer "排的整齊一些", 這時候就幾乎躲不掉 64K aliasing 的問題 (不管有沒有 align 64).
所以當我們執行類似 c[i] = a[i] * b[i] 這樣的運算時, 64K aliasing 的 penalty 就會很高.

解決分法是多配置一些記憶體, 並加上 offset 把不同 buffer 的起始位置錯開, 例如:

BYTE *psR = (BYTE *) _mm_malloc(m_Width * m_Height, 64); 
BYTE *pR = psR; 
BYTE *psG = (BYTE *) _mm_malloc(m_Width * m_Height + 128, 64); 
BYTE *pG = psG + 128; 
BYTE *psB = (BYTE *) _mm_malloc(m_Width * m_Height + 256, 64); 
BYTE *pB = psB + 256;

至於 offset 該用多少? 我試過幾種不同的值, 有時候 penalty 反而更高, 後來看到 vtune 手冊上寫要用 128 的倍數, 就照著用.
果然這個 function 的 64K aliasing conflict 從 20051 降到幾乎沒有. 從 clocktick 上看 sample 數目也降到很低

結論: 當我們發現某個 function 跑的不快, 不用急著進 SIMD, 看一下 64K aliasing 的問題, 說不定解掉 64K aliasing 之後也不需要進 SIMD 了.

---

64K aliasing conflict fix (part II)

另一個要講的是 stack variable 的 64K aliasing conflict, 例如下面的 function:

void func_job()
{
  int a; 
  int b;
  ...
  // other operations
}

pthread_create(&thread0, &attr, func_job, (void *)&pam0);
pthread_create(&thread1, &attr, func_job, (void *)&pam1);
pthread_create(&thread2, &attr, func_job, (void *)&pam2);

依照 vtune 手冊的說法, OS 會把 thread 的 stack space 安排在 1MB or 2MB 的 boundary 上, 剛好都是 64K 的倍數.
所以 func_job() 裡面的 stack 變數 (a, b 等等) 全部都是 64K apart (一點都不差), 跑起來就是 conflict 到爆

解決方法是在進入 working function 之前, 用 _alloca() 在 program stack 上要一塊記憶體來做 offset:

struct my_param_t
{
  int offset;
};

void thread_entry(void *param)
{
  my_param_t *p = (my_param_t *) param;
  _alloca(p->offset);
  func_job();
}

my_param_t pam1 = { 0 };
my_param_t pam2 = { 128 };
my_param_t pam3 = { 256 };

pthread_create(&thread0, &attr, thread_entry, (void *)&pam0);
pthread_create(&thread1, &attr, thread_entry, (void *)&pam1);
pthread_create(&thread2, &attr, thread_entry, (void *)&pam2);

這樣一來, 雖然三個 fork 出來的 thread 在 thread_entry() 裡面的 esp 都是 64K apart, 但是因為加上 offset, 真正在做工作的 func_job() 裡面的 esp 起始位置就會被錯開, 也就沒有 64K aliasing 的問題

至於應該錯開多少? 我這邊用的還是 128 的倍數, 看來這個數字不錯用 :P

像我的例子中, 如果不處理 64K aliasing, multi-thread 反而會慢 12%, 解決 64K aliasing 問題之後, 就可以快 12%, 這樣一來一回就差了 24%, 可見 64K aliasing 的 penalty 真的很高 @@