c - 使用 openmp 任务的部分并行循环

Question

先决条件:

• 并行引擎:OpenMP 3.1+(如果需要可以是 OpenMP 4.0)
• 并行构造:OpenMP 任务
• 编译器:gcc 4.9.x(支持OpenMP 4.0)

输入:

• 带循环的 C 代码
• 循环具有交叉迭代数据依赖性:“i+1”迭代需要来自“i”迭代的数据(只有这种依赖性，没有其他)
• 循环体可以部分依赖
• 循环不能分成两个循环；循环体应保持稳定
• 任何合理的东西都可以添加到循环或循环体函数定义中

代码示例:

(这里的 conf/config/configData 变量仅用于说明目的，主要兴趣在于 value/valueData 变量。)

void loopFunc(const char* config, int* value)
{
    int conf;
    conf = prepare(config);         // independent, does not change “config”
    *value = process(conf, *value); // dependent, takes prev., produce next
    return;
}

int main()
{
    int N = 100;
    char* configData;           // never changes
    int valueData = 0;          // initial value
    …
    for (int i = 0; i < N; i++)
    {
        loopFunc(configData, &valueData);
    }
    …
}

需要:

• 使用 omp 任务的并行循环(不能使用 omp for/omp 部分)
• “准备”功能应与其他“准备”或“处理”功能并行执行
• “处理”功能应根据数据依赖性排序

已提出和实现的内容:

• 定义整数标志
• 分配给它一些第一次迭代
• 每次迭代需要数据时都会等待标志等于它的迭代
• 在下一次迭代的数据准备就绪时更新标志值

像这样:

(我提醒 conf/config/configData 变量仅用于说明目的，主要兴趣在于 value/valueData 变量。)

void loopFunc(const char* config, int* value, volatile int *parSync, int iteration)
{
    int conf;
    conf = prepare(config);         // independent, do not change “config”
    while (*parSync != iteration)   // wait for previous to be ready
    {
        #pragma omp taskyield
    }
    *value = process(conf, *value); // dependent, takes prev., produce next
    *parSync = iteration + 1;       // inform next about readiness
    return;
}

int main()
{
    int N = 100;
    char* configData;           // never changes
    int valueData = 0;          // initial value
    volatile int parallelSync = 0;
    …
    omp_set_num_threads(5);
    #pragma omp parallel
    #pragma omp single
    for (int i = 0; i < N; i++)
    {
        #pragma omp task shared(configData, valueData, parallelSync) firstprivate(i)
            loopFunc(configData, &valueData, &parallelSync, i);
    }
    #pragma omp taskwait
    …
}

发生了什么:

它失败了。 :)

原因是openmp任务占用了openmp线程。例如，如果我们定义 5 个 openmp 线程(如上面的代码)。

• “For”循环生成 100 个任务。
• OpenMP 运行时将 5 个任意任务分配给 5 个线程并启动这些任务。

如果已启动的任务中没有 i=0 的任务(这种情况时有发生)，执行中的任务将永远等待，永远占用线程，并且 i=0 的任务永远不会启动。

下一步是什么？

我不知道如何实现所需的计算模式。

当前解决方案

感谢下面@parallelgeek 的想法

int main()
{
    int N = 10;
    char* configData;           // never changes
    int valueData = 0;          // initial value
    volatile int parallelSync = 0;
    int workers;
    volatile int workingTasks = 0;
    ...
    omp_set_num_threads(5);
    #pragma omp parallel
    #pragma omp single
    {
        workers = omp_get_num_threads()-1;  // reserve 1 thread for task generation

        for (int i = 0; i < N; i++)
        {
            while (workingTasks >= workers)
            {
                #pragma omp taskyield
            }

            #pragma omp atomic update
                workingTasks++;

            #pragma omp task shared(configData, valueData, parallelSync, workingTasks) firstprivate(i)
            {
                loopFunc(configData, &valueData, &parallelSync, i);

                #pragma omp atomic update
                    workingTasks--;
            }
        }
        #pragma omp taskwait
    }
}

Answer 1

1. AFAIK volatiles 不会阻止硬件重新排序，这就是为什么你最终可能会导致内存困惑，因为数据尚未写入，而标志已被消费线程视为 true。
2. 这就是为什么要提一点建议:改为使用 C11 原子以确保数据的可见性。如我所见，gcc 4.9 支持 c11 C11Status in GCC
3. 您可以尝试将生成的任务分成 K 个任务组，其中 K == ThreadNum 并仅在任何正在运行的任务之后开始生成后续任务(在第一组中的任务生成之后)完成了。因此，您有一个不变性，每次您只有 K 个任务在 K 个线程上运行和调度。
4. 也可以通过使用 C11 中的原子标志来满足任务间依赖性。