c++ - 并行 for 比顺序 for 慢

Question

我的程序应执行单词和文本的平行不同旋转。

如果您不知道这是什么意思:“BANANA”的旋转是

• 香蕉
• 阿纳布
• 七叶草
• ANABAN
• 纳巴纳
• 阿巴南

(简单地将第一个字母放在最后。)

vector<string> rotate_sequentiell( string* word )
{
vector<string> all_rotations;

for ( unsigned int i = 0; i < word->size(); i++ )
{
    string rotated = word->substr( i ) + word->substr( 0,i );
    all_rotations.push_back( rotated );
}

if ( verbose ) { printVec(&all_rotations, "Rotations"); }


return all_rotations;
}

我们应该能够做到这一点。我不想将一个字母移动到末尾，而是一次将两个字母移动到末尾，例如，我们将 BANANA将te“BA”走到最后得到NANA BA，也就是上面列表中的第三个条目。

我是这样实现的

vector<string> rotate_parallel( string* word )
{
vector<string> all_rotations( word->size() );

#pragma omp parallel for
for ( unsigned int i = 0; i < word->size(); i++ )
{
    string rotated = word->substr( i ) + word->substr( 0,i );
    all_rotations[i] = rotated;
}

if ( verbose ) { printVec(&all_rotations, "Rotations"); }

return all_rotations;
}

我预先计算了可能的旋转次数并使用了#pragma omp parallel for，所以它应该按照我的想法去做。

为了测试这些功能，我有一个 40KB 的大文本文件，它是用来“旋转”的。我想要一个巨大文本的所有不同旋转。

现在发生的情况是，顺序过程大约需要 4.3 秒，而并行过程大约需要 6.5 秒。

为什么会这样？我做错了什么？

我是这样计算时间的:

clock_t start, finish;
start = clock();
bwt_encode_parallel( &glob_word, &seperator );
finish = clock();
cout << "Time (seconds): "
     << ((double)(finish - start))/CLOCKS_PER_SEC;

我编译我的代码

g++ -O3 -g -Wall -lboost_regex -fopenmp -fmessage-length=0

Answer 1

与顺序版本相比，并行版本有两个额外的工作来源:(1) 启动线程的开销，以及(2)线程间的协调和锁定。

当数据集变大时，(1) 的影响应该会减弱，而且可能不值得 2 秒，但这会限制并行化有意义的小作业。

(2) 在您的情况下可能主要是由 omp 将任务分配给线程引起的，并且不同的线程为 2 个中间子字符串和最终字符串“旋转”进行内存分配 - 内存分配例程可能必须获得全局锁定，然后才能为您保留一 block 堆。

在单个线程中预分配最终存储并引导 OMP 在每个线程的大型 (2048) 迭代 block 中运行并行循环会使结果倾向于并行执行。使用以下代码，单线程版本大约需要 700 毫秒，多线程版本大约需要 330 毫秒:

 enum {SZ = 40960};
 std::string word;
 word.resize(SZ);
 for (int i = 0; i < SZ; i++) {
   word[i] = (i & 127) + 1;  // put stuff into the word
 }
 std::vector<std::string> all_rotations(SZ);
 clock_t start, finish;
 start = clock();
 for (int i = 0; i < (int)word.size(); i++) {
   all_rotations[i].reserve(SZ);
 }
 #pragma omp parallel for schedule (static, 2048)
 for (int i = 0; i < (int)word.size(); i++) {
   std::string rotated = word.substr(i) + word.substr(0, i);
   all_rotations[i] = rotated;
 }
 finish = clock();
 printf("Time (seconds): %0.3lf\n", ((double)(finish - start))/CLOCKS_PER_SEC);

最后，当您需要 burrows wheeler 变换的结果时，您不一定需要包含 N 个字符的字符串的 N 个拷贝。将字符串视为环形缓冲区并从缓冲区中的不同偏移量读取每个旋转将节省空间和处理。