提高使用OpenMP {科普兰 - 鄂尔多斯常数冲

Question

我建立一个程序，找出恒科普兰 - 鄂尔多斯子在C++ 11

Copeland-Erdős constant是为了所有的素数串一串的串行建筑： 2,3,5,7,11,13 ...→23571113 ...

我需要检查给定的子字符串是否在该常量内，并以快速方式执行。

到目前为止，我已经使用Miller Rabin函数构建了一个串行程序，用于检查计数器生成的数字是否为素数并添加到主字符串（常量）。要找到8th Marsene Number（2 -1）该程序花费8分钟。

然后，我使用find来检查给定的子字符串是否在常量和它开始的位置。

问题：

我用串行编程。我从0开始，检查是否所有数字都是主要的添加或不添加......我不知道是否有其他方式来做到这一点。子字符串可以是素数的混合。例如：1 .. {1131} .. 7（11,13,17的子串）

您是否有任何提议通过使用OpenMP来提高程序执行时间？

我想计算“人类时间”中的第9个梅赛德数。我花了一天多的时间，但没有找到它（好吧，到达号码）。

gcc version 4.4.7 20120313 

Main.cpp的

while (found == -1 && lastNumber < LIMIT) //while not found & not pass our limit 
{ 
    //I generate at least a string with double size of the input (llargada) 
    for (lastNumber; primers.length() <= 2*llargada; lastNumber++){ 
     if (is_prime_mr(lastNumber)) 
      primers += to_string(lastNumber); //if prime, we add it to the main string 
    } 
    found = primers.find(sequencia); //search substring and keep position 
    if (found == string::npos){   //if not found 
     indexOfZero += primers.length()/2;  //keep IndexOfZero, the position of string in global constant 
     primers.erase(0,primers.length()/2);  //delete first middle part of calculated string 
    } 
} 

if (found != -1){ 
    cout << "FOUNDED!" << endl; 
    cout << "POS: " << indexOfZero << " + " << found << " = " << indexOfZero+found << endl;} //that give us the real position of the substring in the main string 
    //although we only spend 2*inputString.size() memory 
    else 
     cout << "NOT FOUND" << endl; 

Answer 1

提高串行执行：

对于初学者来说，你并不需要检查每一个数字，看它是否是素数，而是每个奇数（2除外）。我们知道，没有偶数的两个数字可以是素数。这应该会将执行时间缩短一半。

此外，我不明白为什么你有一个嵌套循环。你只需要检查一次你的列表。

此外，我担心你的算法可能不正确。目前，如果您没有找到子字符串，则删除一半字符串并继续。但是，如果连续有50个非素数，则最终可能会删除除最后一个字符以外的整个字符串。但是，如果您要查找的子字符串是3位数字并且需要以前的两个字符？然后，您已经删除了找到您的解决方案所需的一些信息！

最后，你应该只搜索你的子字符串，如果你实际上找到了一个素数。否则，您已经在上次迭代中搜索了它，并且没有任何内容添加到您的string中。

结合所有的这些想法，你有：

primers = "23"; 
lastNumber = 3; 
found = -1; 
while (found == -1) 
{ 
    lastNumber += 2; 
    if (is_prime_mr(lastNumber)) { 
     primers += to_string(lastNumber);  //if prime, we add it to the main string 
     found = primers.find(sequencia);   //search substring and keep position 
     if (found == string::npos) 
      found = -1; 
     else 
      break; 
    } 
} 

此外，你应该写自己的find功能只检查最后几个数字（其中一些您最近串联全球字符串=长度primers）。如果子字符串不在前面的全局字符串中，那么只有几个地方可以弹出到最新的字符串中。该算法应该是O(1)而不是O(n)。

int findSub(std::string total, std::string substring, std::string lastAddition); 

有了这个改变你if语句应更改为：

if (found != -1) 
    break; 

增加并行：

不幸的是，-是，你的算法本质上是串行，因为你必须遍历所有素数一个接一个地加到列表中，以便找到答案。没有简单的OpenMP方式来并行化您的算法。

但是，您可以通过将您的字符串拆分成碎片并让每个线程单独工作来利用并行性。然后，你必须做的唯一棘手的事情是考虑最终字符串之间的界限，以检查你没有遗漏任何东西。喜欢的东西如下：

bool globalFound = false; 
bool found; 
std::vector<std::string> primers; 
#pragma omp parallel private(lastNumber, myFinalNumber, found, my_id, num_threads) 
{ 
    my_id = omp_get_thread_num(); 
    num_threads = omp_get_num_threads(); 
    if (my_id == 0) { // first thread starts at 0... well, actually 3 
     primers.resize(num_threads); 
     #pragma omp barrier 
     primers[my_id] = "23"; 
     lastNumber = 3; 
    } 
    else { 
     // barrier needed to ensure that primers is initialized to correct size 
     #pragma omp barrier 
     primers[my_id] = ""; 
     lastNumber = (my_id/(double)num_threads)*LIMIT - 2; // figure out my starting place 
     if (lastNumber % 2 == 0) // ensure I'm not even 
      lastNumber++; 
    } 
    found = false; 
    myFinalNumber = ((my_id+1)/(double)num_threads)*LIMIT - 2; 

    while (!globalFound && lastNumber < myFinalNumber) 
    { 
     lastNumber += 2; 
     if (is_prime_mr(lastNumber)) { 
      primers[my_id] += to_string(lastNumber); 
      found = findSub(primers[my_id], sequencia, to_string(lastNumber)); // your new version of find 
      if (found) { 
       #pragma omp atomic 
       globalFound = true; 
       break; 
      } 
     } 
    } 
} 

if (!globalFound) { 
    // Result was not found in any thread, so check for boundaries/endpoints 
    globalFound = findVectorSubstring(primers, sequencia); 
} 

我就让你完成这个（通过编写智能find，findVectorSubstring - 只应检查的primers元素之间的界限，并再次确认你理解这个新的算法的逻辑）。此外，如果您设置的任意LIMIT结果太小，则您可以始终将此整个事件封装在搜索i*LIMIT和(i+1)*LIMIT之间的循环中。

最后，是的，会有负载平衡的问题。我当然可以想象线索发现不均匀的质数。因此，某些线程会比其他线程在find功能中做更多的工作。但是，find()的智能版本应该是O(1)，而is_prime_mr()可能是O(n)或O(logn)，所以我假设大部分执行时间将花费在is_prime_mr()函数中。因此，我不相信负载平衡会太糟糕。

希望这会有所帮助。