c - OpenMP 自定义调度

Question

我有一个可以轻松并行化的并行循环。我需要为循环实现自定义调度选项。为此，我将显式地将迭代分配给线程，而不是使用标准并行区域，如下所示:

#pragma omp parallel for

相反，我只是使用:

#pragama omp parallel [declarations]

到目前为止我的代码如下:

#define N 500
#pragma omp parallel 
{
int num_threads = omp_get_num_threads();
int thread = omp_get_thread_num();
int start = N*thread/num_threads;
int end = N*(thread+1)/num_threads;
   for (i=start; i<end; i++){
   /* LOOP */
   }
}

我需要应用一种调度算法，以便为每个线程分配一组本地迭代，我相信我已经完成了。每个本地集被分成每个线程执行的 block 。当线程完成它的 block 时，它会找到剩余 block 最多的线程并开始执行这些 block 。重复此过程，直到没有 block 剩余。我正在努力思考如何开始这个，因为我不完全确定如何找出负载最重的线程是什么，以及如何将本地迭代集拆分成 block ，同时仍然保留在平行区域。

Answer 1

您需要实现的是 work stealing算法。听起来您想要的是为每个线程分配一个双端队列(有时称为出队)。如果您允许任何线程从任何其他线程窃取工作，您将需要与每个队列关联的锁以防止两个线程试图窃取同一 block 工作。

您还需要将这些队列中的每一个放入一个优先级队列中，使用它们的大小作为键，以便允许已完成的线程获得剩余工作最多的线程以从中窃取。您还需要锁定该全局优先级队列，以便在执行更新时保持其完整性。

综上所述，当可用时，dynamic #pragma omp for 或产卵的时间表 tasks (通过 #pragma omp task)可能更可取。如果您确实实现了自己的工作窃取算法，请记住，根据所有线程都相同的指标选择要从哪个线程窃取通常会导致冲突(即，所有空闲线程都将尝试从同一个线程窃取队列)。考虑改为根据地点选择在哪里窃取工作。