1

我正在尝试实现并行蛮力子字符串搜索算法。每个线程都有一个开始和结束索引，因为我用 4 个线程运行它，每个线程将完成四分之一的工作。

现在，当我运行该函数一次时，一切都很好（使用 4 个线程），但是由于该函数是 void 类型，我将结果（子字符串位于较大字符串中的索引）存储在全局变量中回答'。

int ans = -1;

void bruteForce(string mainString, string subString)
{
    int tid, nthreads;
    #pragma omp parallel private (tid) shared (nthreads, ans)
    {
        tid = omp_get_thread_num();
        nthreads = omp_get_num_threads();
        int j = 0;
        int start = tid * (mainString.size() / nthreads);
        int end = start + mainString.size() / nthreads;

        for(int i = start; i < end; i++)
        {
            if(ans == -1)
            {
                while(j < subString.size())
                {
                    if(mainString[i + j] != subString[j]) break;
                    if(j == subString.size() - 1)
                    {
                        #pragma omp critical
                        {
                            #pragma omp flush
                            ans = i;
                        }
                    }
                    j++;
                }
                j = 0;
            }
        }
    }
}

我想要做的是，在函数完成之后或开始之前将“ans”重置为-1，但是当我尝试这样做时，我得到了这个错误，以及内存映射和回溯。

double free or corruption (out): 0xb5b00468 ***

为什么我不能在下面的 for 循环显示中将“ans”更改为 -1 是否有原因？

    start = get_timestamp();
    for(int x = 0; x < N; x++)
    {
        show_percent(x, N);
        bruteForce(STRING, WORD);
    }
    end = get_timestamp();
4

2 回答 2

2

这与更改ans无关。您需要在brutForce()的 while 循环中限制(i+j ) 。

说 mainString = "THIS" 和 subString="XXX"。所以每个线程都得到

T | H | 我 | 小号

对于最后一个线程，您的 start=3，end=4。还有 subString.size() = 3;

所以在 while 循环中，您正在访问 mainString[i+j]，其中 j = 0->2 ==> (i+j) = 3->5。

于 2013-04-03T08:08:08.920 回答
0

正如问题的原始海报所述：

解决方案

Here's a fixed and working version of the code. I've only just started messing about with OpenMP, and it seems really picky with how and where you declare your variables, and how you pass them on to individual threads, so if someone could enlighten me as to why these changes fixed the code, that would be great. Also, the #pragma omp parallel for i added substantially improved performance of the program.

int ans = -1;

void bruteForce(const string mainString, const string subString)
{
    ans = -1;
    int tid, nthreads, start, end, j, i;
    #pragma omp parallel private (tid, start, end, j) shared (nthreads, ans)
    {
        tid = omp_get_thread_num();
        nthreads = omp_get_num_threads();
        start = tid * (mainString.size() / nthreads);
        end = start + mainString.size() / nthreads;
        if(tid == (nthreads - 1)) 
            end = end - subString.size();
        j = 0;

        #pragma omp parallel for
        for(i = start; i < end; i++)
        {
            if(ans == -1)
            {
                while(j < subString.size())
                {
                    if(mainString[i + j] != subString[j]) break;
                    if(j == subString.size() - 1)
                    {
                        #pragma omp critical
                        {
                            ans = i;
                        }
                    }
                    j++;
                }
                j = 0;
            }
        }
    }
}
于 2013-04-06T21:14:28.370 回答