C-OpenMP /タスクで再帰的コードを並列化しようとしましたが、動作は遅くなります

Question

メキシコからのご挨拶！

私は、再帰を含むいくつかのコードを並列化する作業に直面していましたが、いくつかの研究を行った後、ompのタスクを利用するのが最善の方法であることに気付きました。しかし、そのランタイムはシリアル対応のものよりかなり大きいようです。

私はこの質問がこのフォーラムで2,3回以上尋ねられていることを知っていますが、提案された解決策のどれも私のケースに合っていないようです。

以下、私のコードを追加します。 infijaParallelSearch（）は、BSTの先頭と検索する値を受け取り、ツリー内にあればノードを返します。 convertToBST（）はソートされたリストを受け取り、それを頭を返すバイナリ検索ツリーに変換します。私は（omp_get_wtimeとの時間を計測しています）およびIから、ほとんどすべてを試してみましたRuntime results

：私はそのシリアル相手とそのランタイムを比較するために、長さを増加させるのリストでそれを実行すると、私はこれを取得

typedef struct node 
{ 
    int key; 
    struct node *left; 
    struct node *right; 
} Node; 


Node* convertToBST(int* array, int size) { 
    if(size == 1) 
     return NULL; 
    Node* root= (Node*)malloc(sizeof(Node)); 
    if(root == NULL) 
    { 
     printf("Error creating a new node.\n"); 
     exit(0); 
    } 
    root->key=array[size/2-1]; 
    root->left=convertToBST(array,size/2); 
    root->right=convertToBST(array+size/2,size-size/2); 
    return root; 
} 

Node* infijaParallelSearch(Node* root, int x){ 
    if(root == NULL) 
     return NULL; 
    if(root->key == x) 
     return root; 
    #pragma omp task firstprivate(root) 
     infijaParallelSearch(root->left,x); 

    infijaParallelSearch(root->right,x); 
} 

複数のトラバースに対して単一のトラバースを持ち、何も違いを生むようなものはありません。私はまた、そのコードの長さがパラレルコードの方が性能が優れている値よりも低い場合には、コードを複数回実行した後にその値が存在しないように見えることを考慮しました。

お返事ありがとうございます。これは私の最初の質問であり、私はどんな方法でも漠然としていなかったことを願っています。私は初心者です。私はコーディングに対する情熱を磨いているだけなので、助けや助言をいただければ幸いです。

PS：違いが出るかどうかわかりませんが、以下では両方のコードのランタイムを比較するコードを追加します。

int main(){ 
    int i,*ptrA,n=10; 
    double startTime, normalTime, parallelTime; 
    FILE *fPtr; 

    fPtr=fopen("statistics.txt","w"); 
     if(fPtr == NULL){ 
      printf("File cannot be created"); 
      exit(0); 
     } 
    while(n<=100000){ 
     printf("\nTamaño: %d\t",n); 

     ptrA = (int*)calloc(n,sizeof(int)); 
     if (ptrA == NULL) 
     { 
      printf("Error 401. Memory not available"); 
      exit(0); 
     } 


     for (i=0;i<n;i++){ 
      ptrA[i]=i+1; 
     } 
     Node *root=convertToBTS(ptrA,n); 

     startTime=omp_get_wtime(); 
     infijaParallelSearch(root,-1); 
     normalTime=omp_get_wtime()-startTime; 
     printf("Parallel final Time: %f\t",normalTime); 

     for (i=0;i<n;i++){ 
      ptrA[i]=i+1; 
     } 

     root=convertToBTS(ptrA,n); 

     startTime=omp_get_wtime(); 
     infijaSearch(root,-1); 
     parallelTime=omp_get_wtime()-startTime; 
     printf("Normal final Time: %f\n",parallelTime); 
     free(ptrA); 

     fprintf(fPtr,"%d::%f::%f\n",n,normalTime,parallelTime); 

     n+=100; 
    } 
    fclose(fPtr); 
    return 0; 
} 

Answer 1

まず、検索を並列化すると、データサイズとは関係なくパフォーマンスが向上するという仮定はfalseです。 実行時の結果によると、シリアライズされたバージョンで提供された配列サイズでは、実行時間の合計がより速いものの、パラレルバージョンに比べてサイズが大きくなるにつれ、間違いなく悪化すると結論づけられます。

たとえば、配列サイズを100倍から10000倍に増加させると、シリアライズされたバージョンではパフォーマンスが50倍遅くなります。しかしparrallelバージョンは〜40倍しか遅くない（つまり、parrallelバージョンではパフォーマンスが向上しています）。

これは、十分な大きさのデータセットでは、parrallelバージョンがシリアル化バージョンよりも性能が劣ると仮定しています。

どうしてですか？ ここで並行処理をどのように実装するかにかかわらず、新しいタスク（スレッド）を作成するとオーバーヘッドが発生します。その場合は、実行する作業項目のジョブに比べて大きくなることがあります。