并行处理-pthread的使用增加了执行时间，并提出了改进建议

Question

我有一段代码，看起来像这样，

 for(i=0;i<NumberOfSteps;i++)
{
    for(k=0;k<NumOfNodes;k++)
    {
        mark[crawler[k]]++;
        r = rand() % node_info[crawler[k]].num_of_nodes;
        crawler[k] = (int)DataBlock[node_info[crawler[k]].index+r][0];
    }
}

我更改了它，以便可以在多个线程之间分配负载。现在看起来是这样的，

for(i=0;i<NumberOfSteps;i++)
{
    for(k=0;k<NumOfNodes;k++)
    {            
        pthread_mutex_lock( &mutex1 );
        mark[crawler[k]]++;
        pthread_mutex_unlock( &mutex1 );
        pthread_mutex_lock( &mutex1 );
        r = rand() % node_info[crawler[k]].num_of_nodes;
        pthread_mutex_unlock( &mutex1 );
        pthread_mutex_lock( &mutex1 );
        crawler[k] = (int)DataBlock[node_info[crawler[k]].index+r][0];
        pthread_mutex_unlock( &mutex1 );
   }
}

我需要互斥来保护共享变量。原来我的并行代码比较慢。但为什么呢？是因为互斥吗？

这可能与缓存线大小有关吗？

Answer 1

除了循环头之外，您没有并行化任何东西。锁定和解锁之间的所有操作都必须按顺序执行。由于锁定/解锁是（潜在的）昂贵的操作，代码变得越来越慢。

要解决这个问题，您至少应该将昂贵的计算（没有互斥保护）与访问共享数据区域（使用互斥）分开。然后尝试将互斥对象移出内部循环。

您可以使用原子增量指令（取决于平台），而不是普通的"++"，后者通常比互斥量便宜。但要注意，经常对来自不同线程的单个缓存行的数据并行执行此操作（请参阅"错误共享"）。

AFAICS，您可以重写如下所示的算法，而不需要互斥和原子增量。如果NumOfNodes是NumOfThreads的整数倍，则getFirstK（）为NumOfNodes/NumOfThreads*t。

for(t=0;t<NumberOfThreads;t++)
{
    kbegin = getFirstK(NumOfNodes, NumOfThreads, t);
    kend   = getFirstK(NumOfNodes, NumOfThreads, t+1);
    // start the following in a separate thread with kbegin and kend 
    // copied to thread local vars kbegin_ and kend_
    int k, i, r;
    unsigned state = kend_; // really bad seed
    for(k=kbegin_;k<kend_;k++)
    {
        for(i=0;i<NumberOfSteps;i++)
        {
            mark[crawler[k]]++;
            r = rand_r(&state) % node_info[crawler[k]].num_of_nodes;
            crawler[k] = (int)DataBlock[node_info[crawler[k]].index+r][0];
        }
    }
}
// wait for threads/jobs to complete

这种生成随机数的方式可能会导致糟糕的随机分布，请参阅此问题了解详细信息。