并行 for 比顺序 for 慢

Question

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

如果您不知道这是什么意思："BANANA" 的旋转是

香蕉
ANANAB
七叶树
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 的大文本文件，这意味着 "rotated"。我想要一个巨大的文本的所有不同的旋转。

现在发生的情况是，顺序过程大约需要 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 个中间子字符串和最终字符串 "rotated" 进行内存分配 - 内存分配例程可能必须获得全局锁才能为您保留一块堆。

在单个线程中预分配最终存储并将 OMP 引导至运行每个线程的大型 (2048) 迭代块中的并行循环使结果倾向于并行执行。使用以下代码，单线程版本大约需要 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 个副本。它将节省 space 和处理以将字符串视为环形缓冲区并从缓冲区中的不同偏移量读取每个旋转。

并行 for 比顺序 for 慢

parallel for is slower than sequential for

c++

parallel-processing

openmp