OpenMP並行前綴和加速

Question

考慮下面的代碼，取自here。對於這個代碼，我得到下面的執行時間：

time ./fibomp 40 
Number of threads (OpenMP v200805): 2 
finonacci(40) = 102334155 

real 0m3.193s 
user 0m3.180s 
sys  0m0.000s 

$ export OMP_NUM_THREADS=1 
$ time ./fibomp 40 
Number of threads (OpenMP v200805): 1 
finonacci(40) = 102334155 

real 0m3.224s 
user 0m3.216s 
sys  0m0.000s 

因此，大家可以看到，沒有太多的加快，絕對不是2倍的加速範尼提到在他星期二2011年11月1日上午01時41分電子郵件。我在雙核心機器上運行它（可以這樣嗎？）。我究竟做錯了什麼？ （順便說一句，加分，什麼是ptime命令？有些SPARC Unix命令？）

long comp_fib_numbers(int n) 
{ 
    long fnm1, fnm2, fn; 
    if (n == 0 || n == 1) return(n); 

    // In case the sequence gets too short, execute the serial version 
    if (n < 20) 
    { 
    return(comp_fib_numbers(n-1)+comp_fib_numbers(n-2)); 
    } 
    else 
    { 
    #pragma omp task shared(fnm1) 
     fnm1 = comp_fib_numbers(n-1); 
    #pragma omp task shared(fnm2) 
     fnm2 = comp_fib_numbers(n-2); 
    #pragma omp taskwait 
     fn = fnm1 + fnm2; 
     return(fn); 
    } 

} 

Answer 1

首先，只是可以肯定的，因爲你指出htop顯示了正在使用的單核，確保您已經在編譯器中啓用了OpenMP支持。對於GCC來說，這樣做的選項是-fopenmp，Sun/Oracle編譯器的-xopenmp和英特爾編譯器的-openmp。

其次，n = 20對於並行實現而言可能太低。一個無恥的插件 - 參見OpenMP的一個研討會上的this course material，一個幾個月前我的同事給出的。這裏討論了幾個具有任務的並行版本，從第20張開始討論。

第三，ptime是一個Solaris命令，不是特定於SPARC的，因爲它也可用於x86版本。許多與進程相關的Solaris命令在它們的名稱中都有前綴p。請注意，在您的情況下，time更可能是Bash提供的內置實現，而不是獨立二進制文件。

第四，也可以是真正的回答你的問題 - 你在你的代碼所缺少一個parallel區域做任務指令不會在所有的工作:)你應該重寫代碼如下：

long comp_fib_numbers(int n) 
{ 
    long fnm1, fnm2, fn; 
    if (n == 0 || n == 1) return(n); 

    // In case the sequence gets too short, execute the serial version 
    if (n < 20) 
    { 
     return(comp_fib_numbers(n-1)+comp_fib_numbers(n-2)); 
    } 
    else 
    { 
     #pragma omp parallel // <--- You are missing this one parallel region 
     { 
     #pragma omp single 
     { 
      #pragma omp task shared(fnm1) 
      fnm1 = comp_fib_numbers(n-1); 
      #pragma omp task shared(fnm2) 
      fnm2 = comp_fib_numbers(n-2); 
     } 
     #pragma omp taskwait 
     } 

     fn = fnm1 + fnm2; 
     return(fn); 
    } 

} 

你可以做更簡潔使用if條款代碼切換並行區域：

long comp_fib_numbers(int n) 
{ 
    long fnm1, fnm2, fn; 
    if (n == 0 || n == 1) return(n); 

    #pragma omp parallel if(n >= 20) 
    { 
     #pragma omp single 
     { 
     #pragma omp task shared(fnm1) 
     fnm1 = comp_fib_numbers(n-1); 
     #pragma omp task shared(fnm2) 
     fnm2 = comp_fib_numbers(n-2); 
     } 
     #pragma omp taskwait 
    } 

    fn = fnm1 + fnm2; 
    return(fn); 
} 

如果n恰好小於20，則並行區域將執行單線程的。由於並行區域通常是在不同的函數中提取的，因此除非編譯器選擇重複的代碼，否則仍然會有一個額外的函數調用。這就是爲什麼我們建議串行實現是在其自身的功能提取：

long comp_fib_numbers_serial(int n) 
{ 
    if (n == 0 || n == 1) return(n); 

    return (comp_fib_numbers_serial(n-1) + comp_fib_numbers_serial(n-2)); 
} 

long comp_fib_numbers(int n) 
{ 
    long fnm1, fnm2, fn; 
    if (n < 20) return comp_fib_numbers_serial(n); 

    #pragma omp parallel 
    { 
     #pragma omp single 
     { 
     #pragma omp task shared(fnm1) 
     fnm1 = comp_fib_numbers(n-1); 
     #pragma omp task shared(fnm2) 
     fnm2 = comp_fib_numbers(n-2); 
     } 
     #pragma omp taskwait 
    } 

    fn = fnm1 + fnm2; 
    return(fn); 
} 

編輯：現在，我已經看了你已經鏈接到的代碼，我可以看到調用comp_fib_numbers被嵌入到parallel區域中。因此，如果您的代碼中已有一個，請忽略我對關於丟失的parallel區域的評論。爲了完整性，我將把它留在這裏。嘗試調整並行和串行版本之間切換的值。在現代處理器上它可能相當高，你看到的例子是相當古老的。通過設置環境變量OMP_DYNAMIC到false（或FALSE）或通過在並行區域之前的某個位置調用omp_set_dynamic(0);來確保沒有使用動態組。

您尚未說明您的編譯器是什麼，但請注意OpenMP 3.0自4.4版以來由GCC支持，自11.0版以來由英特爾編譯器支持，由Sun/Oracle編譯器自版本I_dont_know支持，並且完全不受Visual C/C++編譯器。

的四路英特爾至強X7350系統（舊預Nehalem的系統FSB）

$ time OMP_NUM_THREADS=1 ./fib.x 40 
finonacci(40) = 102334155 
OMP_NUM_THREADS=1 ./fib.x 40 1.86s user 0.00s system 99% cpu 1.866 total 
$ time OMP_NUM_THREADS=2 ./fib.x 40 
finonacci(40) = 102334155 
OMP_NUM_THREADS=2 ./fib.x 40 1.96s user 0.00s system 169% cpu 1.161 total 

隨着截止設置爲25觀察到加速（似乎是對X7350的最佳值） ：

$ time OMP_NUM_THREADS=2 ./fib.x 40 
finonacci(40) = 102334155 
OMP_NUM_THREADS=2 ./fib.x 40 1.95s user 0.00s system 169% cpu 1.153 total 

隨着截止設置爲25和一個單獨的功能串行執行：

$ time OMP_NUM_THREADS=2 ./fib.x 40 
finonacci(40) = 102334155 
OMP_NUM_THREADS=2 ./fib.x 40 1.52s user 0.00s system 171% cpu 0.889 total 

瞭解用戶時間如何減少大約400毫秒。這是因爲刪除了開銷。

這些數據是使用您鏈接到的網站的代碼來衡量的。在64位Scientific Linux 6.2系統上使用的編譯器是GCC 4.4.6。