文字列検索 - パラレルバージョンが遅い

Question

文字列検索のための単純なアルゴリズムをパラレル化しようとしています。私はシンプルなバージョンを作成し、その後、複数のスレッドを使用してそれをスピードアップしようとしました。

しかし、次のコードは、それが非常に遅くなります：

template<typename T> long unsigned int simple_paralel(const T * str1, unsigned long int str1_length, const T * str2, unsigned long int str2_length) { 
    unsigned int long result = ~0; 
    unsigned int long count = 0; 

    unsigned long int in; 
    unsigned int long top; 
    #pragma omp parallel 
    #pragma for ordered shared(result, count) private(in, top) firstprivate(str1, str2, str1_length, str2_length) 
    for (top = 0; top < str1_length; top++) { 
    in = 0; 

    // & top + in < str1_length 
    while (in < str2_length) { 
     if (top + in >= str1_length) 
     break; 

     if (str1[top+in] != str2[in]) { 
     break; 
     } 
     ++in; 

     if(in == str2_length) { 
     // shared and we want to have the smallest index 
     if(result >= top + 1) { 
      result = top + 1; 
     } 
     count++; 
     } 
    } 
    } 
    return count; 
} 

私が間違って何をしているのですか？

Answer 1

だから私は後ずさりし、別のアプローチを試みた：

template<typename T> long unsigned int simple_paralel(const T * str1, unsigned long int str1_length, const T * str2, unsigned long int str2_length, int threads) { 
    count = 0; 

    unsigned long int block = str1_length/threads; 
    unsigned long int total = 0; 
    unsigned long int result = 0; 

    unsigned long int smallest = ~0; 
    #pragma omp parallel for shared(count) 
    for(int i=0; i<threads; i++) 
    { 
    unsigned long int res; 
    unsigned long int start = i * block; 
    if(i != threads -1) 
    { 
     total += block; 
     res = simple_p(str1 + start, block, str2, str2_length, false); 
    } else { 
     res = simple_p(str1 + start, str1_length - total, str2, str2_length); 
    } 

    if(res < result && res != 0){ 
     result = res; 
    } 
    } 

    return count; 
} 

をそして期待どおりに動作します。しかし、私はまだは、私ははOpenMPでこれを行うことはできません信じることができない。