稀疏矩陣的多線程程序

Question

我是多線程的新手。我正在設計一個解決稀疏矩陣的程序。在我的代碼中，我多次調用Vector Vector dot product和Matix vector product作爲子程序，以達到最終解決方案。我試圖使用開放MP（特別是上面的兩個子例程）並行化代碼。我也有序列代碼，我不打算並行化。

我的問題是如何處理調用子例程時創建的線程。我應該在每個子例程調用結束時放置一個障礙嗎？

另外我應該在哪裏設置線程數？

Mat_Vec_Mult(MAT,x0,rm); 
#pragma omp parallel for schedule(static) 
for(int i=0;i<numcols;i++) 
    rm[i] = b[i] - rm[i]; 

#pragma omp barrier 


#pragma omp parallel for schedule(static) 
for(int i=0;i<numcols;i++) 
    xm[i] = x0[i]; 
#pragma omp barrier 


double* pm = (double*) malloc(numcols*sizeof(double)); 


    #pragma omp parallel for schedule(static) 
for(int i=0;i<numcols;i++) 
    pm[i] = rm[i]; 
#pragma omp barrier 
scalarProd(rm,rm,numcols); 

感謝

編輯：

的標量dotproduct，我現在用的是下面這段代碼：

double scalarProd(double* vec1, double* vec2, int n){ 
double prod = 0.0; 
int chunk = 10; 
int i; 
//double* c = (double*) malloc(n*sizeof(double)); 

omp_set_num_threads(4); 

// #pragma omp parallel shared(vec1,vec2,c,prod) private(i) 
#pragma omp parallel 
{ 
    double pprod = 0.0; 
    #pragma omp for 
    for(i=0;i<n;i++) { 
     pprod += vec1[i]*vec2[i]; 
    } 

    //#pragma omp for reduction (+:prod) 
    #pragma omp critical 
    for(i=0;i<n;i++) { 
     prod += pprod; 
    } 
} 


return prod; 
} 

我現在已經增加了時間計算的代碼在我的共軛梯度功能如下：

start_dotprod = omp_get_wtime(); 
rm_rm_old = scalarProd(rm,rm,MAT->ncols); 
    run_dotprod = omp_get_wtime() - start_dotprod; 
fprintf(timing,"Time taken by rm_rm dot product : %lf \n",run_dotprod);   

觀察結果：花點時間產品序列版本：0.000007s並行版本：0.002110

我在我的英特爾I7筆記本電腦上在Linux操作系統上使用gcc -fopenmp命令進行簡單編譯。

我目前使用的大小的矩陣N = 5000

我得到巨大的速度整體下降，因爲直到實現收斂（80K左右的時間）相同的點積被多次調用。

請提出一些改進建議。任何幫助深表感謝！

Answer 1

老實說，我會建議在更高層次上並行化。通過這個我的意思是儘量減少你使用的#pragma omp parallel的數量。每次嘗試在線程中分配工作時，都會產生OpenMP開銷。儘可能嘗試並避免這種情況。

所以你的情況起碼我會嘗試：

Mat_Vec_Mult(MAT,x0,rm); 
double* pm = (double*) malloc(numcols*sizeof(double)); // must be performed once outside of parallel region 

// all threads forked and created once here 
#pragma omp parallel for schedule(static) 
for(int i = 0; i < numcols; i++) { 
    rm[i] = b[i] - rm[i]; // (1) 
    xm[i] = x0[i];  // (2) does not require (1) 
    pm[i] = rm[i];  // (3) requires (1) at this i, not (2) 
} 
// implicit barrier at the end of omp for 
// implicit join of all threads at the end of omp parallel 

scalarProd(rm,rm,numcols); 

注意我是如何證明沒有障礙，實際上是需要你的循環之間的事。

如果你的大部分時間都花在這個計算階段，你肯定會看到相當大的改進。不過，我相當有信心，你的大部分時間都花在Mat_Vec_Mult()，也許還有scalarProd()，所以你節省的時間可能是最少的。

** 編輯 **

而且按照您的編輯，我看到了一些問題。 （1）在測試算法性能時，始終使用-O3進行編譯。 （2）您將無法改進需要0.000007秒才能完成的事情的運行時間;這幾乎是瞬間的。這可以追溯到我之前所說的：試着在更高層次上並行化。CG方法本質上是一種順序算法，但肯定有研究論文開發詳細說明並行CG。 （3）您的標量產品的實現不是最優的。事實上，我懷疑你的矩陣向量產品的實現也不是。我個人做到以下幾點：

double scalarProd(double* vec1, double* vec2, int n) { 
    double prod = 0.0; 
    int i; 

    // omp_set_num_threads(4); this should be done once during initialization somewhere previously in your program 
    #pragma omp parallel for private(i) reduction(+:prod) 
    for (i = 0; i < n; ++i) { 
     prod += vec1[i]*vec2[i]; 
    } 
    return prod; 
} 

（4）有跡象表明，已經高度優化的矩陣向量，向量，向量等操作整個庫（LAPACK，BLAS，等等）。任何線性代數庫必須建立在它們之上。因此，我建議您在開始在這裏重新創建輪子並嘗試實現自己的輪子之前，使用其中一個庫進行兩項操作。