字符串搜索 - 并行版本比较慢

我正在试图平行化字符串搜索的朴素算法。我创建了简单的版本，然后尝试使用多个线程来加速它。字符串搜索 - 并行版本比较慢

但下面的代码使得它更慢：

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; 
}

我在做什么错？

来源

2016-12-31 tomascapek

随机猜测：每个线程中没有足够的工作来弥补开始/停止/整理结果的开销？ –

可能 - 许多周期将立即结束，因为找不到匹配。如何解决这个问题？ – tomascapek

我很难说，因为我不知道你想要解决的具体问题的具体细节（我了解基本知识，但是有很多细节，比如有多大的弦，有多少是，字符串的第一部分在保存之前有多少匹配，它们是否被排序，它们是否可以被排序等等 - 我确信我没有想到所有重要的东西）。一般来说，每个线程与其他线程分开运行时间越长，并行运行性能越好。 –

所以我后退几步，尝试了不同的方法：

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做到这一点。

来源

2016-12-31 15:06:35 tomascapek

***但我仍然不敢相信，我不能用OpenMP来做这件事***我对这个说法感到困惑。看起来你在这里使用openmp。这是否意味着解决问题的答案？ – drescherjm

我的不好！我的意思是：我想，OpenMP可以很容易地将输入分成块，就像我的解决方案。 – tomascapek

字符串搜索 - 并行版本比较慢

回答

相关问题