hedgezzz的部落格

假設你有四個 thread 要去計算一些數據,然後 sum 起來給 global 變數:sum4 ,

你會使用哪些方法 ?

Method1 :

double sumx[4] ;

thread i  do :  sumx[i] = getdata(i) ;

and then finally sum4 = sumx[0] +...+sumx[3]

Method2:

double sumx ;

thread i  do 

spinlock(); sumx += getdata(i);  spin_unlock() ;

這個 sumx 就是最終的答案 !!!!

Method2  因為使用到 lock , 所以速度基本就不快 , 如果不使用 lock , sumx 答案就可能是錯的!!!

Method1  要看 thread 跑在哪種硬體 topology , M1 很明顯有 false sharing 問題 ,

假設這部主機有四個 cpu sockets , 剛好這四個 threads 各跑在不同四個 socket cpu 的 core 上 ,

那麼 sumx[0] to sumx[3]  因為同在一條 cache line 上 (intel cpu has 64 bytes in one cache line),

所以 這條 cache line 必須要跨過 memory 到每一個 socket 的 core 的 L1 cache , 這樣就算沒有使用

lock , false sharing 就讓 M1 慢的嚇人 , 然而 , 如果你跑在同一 cpu socket 且所有 core 共用 L1,L2,L3 cache,

這樣 M1 就非常地快了  !!!!  false sharing 在這樣硬體沒有造成傷害 !!! (using sched_setaffinity to do so)

值得一提 , sumx[0] 正被 core1 執行 , sumx[1] 正被 core3 執行, 為什麼無需 lock ? 它們在同一條 cache line 上呀 ,

原因就是 , cpu 保證 cache line 每一個  aligned memory location 都能被 atomic 存取  ,

sumx[0] 跟 sumx[1] 同在一條 cache line , 但是它們在不同的 memory location 上,所以 concurrent 存取沒有問題 !!

struct xxx_

{

int x1:4 ;

int x2:28;

} ;

這個 struct 裡面的 x1,x2 在同一個 memory location 上 , 所以 concurrent 存取 x1 , x2 會有問題  !!!!

最後是 openmp solution :

omp_set_num_threads(4) ;

#pragma omp  parallel for schedule(dynamic,1) reduction(+:sumx)

for(idx=0;idx<4;idx++)

{

    sumx += getdata(idx);

}

openmp reduction 裡面的 sumx , openmp 會

每一個 thread 產生一個暫時的變數 , 等最後全部 thread 做完後 , 把這些暫時變數加起來給 sumx ,

所以 , 就算四個  thread 跑在不同四個 cpu socket , 不會發生像 M1 一樣 必須把 cache line 拋來拋去 ,

也不會像 M2 一樣 必須 lock 才能得到正確的值 , 所以 openmp 的 reduction 功能是經過設計的好東西 !!!