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

Question

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

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

• 香蕉
• 阿纳纳布
• 七场
• ANABAN
• NABANA
• 阿巴南

(只需将第一个字母放在末尾即可。)

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 将“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

与顺序版本相比，并行版本有 2 个额外工作源: (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 个拷贝。将字符串视为环形缓冲区并从缓冲区中的不同偏移量读取每个旋转将节省空间和处理。