使用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 sections不能使用)
• "准备"功能应与其他"准备"或"处理"功能并行执行
• 应根据数据依赖性对"进程"函数进行排序

已提出并实施的内容:

• 定义整数标志
• 为其分配一些第一次迭代
• 每次迭代时,它需要数据等待标志等于它的迭代
• 当下一次迭代的数据准备好时更新标志值

像这样:

(我提醒说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 易失性不会阻止硬件重新排序，这就是为什么您最终可能会在内存中出现混乱，因为数据尚未写入，而 flag 已被消费线程视为true。
2. 这就是为什么小建议：使用 C11 原子代替以确保数据的可见性。正如我所看到的，gcc 4.9 支持GCC 中的 c11 C11Status
3. 您可以尝试将生成的任务按 K 个任务进行分组，K == ThreadNum只有在任何正在运行的任务完成后才开始生成后续任务（在生成第一组中的任务之后）。因此，您有一个不变量，即每次只有 K 个任务在 K 个线程上运行和调度。
4. 任务间依赖性也可以通过使用 C11 中的原子标志来满足。