Warm tip: This article is reproduced from serverfault.com, please click

c-使用readdir在for循环中并行递归

(c - Parallelizing recursion in a for-loop using readdir)

发布于 2020-05-02 11:01:50

我想并行化一个C程序,该程序使用OpenMP和C递归计算目录及其子目录的大小。

我的问题是,当我使用进入目录opendir,并使用遍历子目录时,readdir只能逐个访问它们,直到到达最后一个子目录。依次运行,一切都很好。

但是,在并行化程序时,我认为将子目录的数量分成两半(甚至更小的分​​区)并使用OpenMp Tasks遍历子目录是有意义的。

显然,由于for循环的结构,我不能简单地将问题大小(=子目录数)分成两半,并且这样的循环无法使用进行并行化#pragma omp for

是否有人对如何将此功能拆分为任务有任何想法?任何帮助将不胜感激。

这是我的一些代码(我删除了我认为与该问题不相关的部分。)

int calculate_folder_size(const char *path) {

    struct stat sb;

    if (S_ISREG(sb.st_mode)) { // if it's a file, not a directory (base case)
        return sb.st_size;
    }

    DIR *folder = opendir(path);

    struct dirent *element;
    size_t size = 4096;

    for (element = readdir(folder); element != NULL; element = readdir(folder)) {

   //(...)
            if (element->d_type == DT_DIR) {
                // recursive call of calculate_folder_size
                size += calculate_folder_size(name);
            } else {
             //(...)
            }
        }
    }
    closedir(folder);
    return size;
}
Questioner
Dreana
Viewed
1
Hristo 'away' Iliev 2020-05-03 06:28:20

你需要一个支持OpenMP任务的现代编译器,该编译器将从等式中删除Visual C ++。只要你使用的是这样的编译器,你要做的就是将递归调用转换calculate_folder_size()为OpenMP任务:

int calculate_folder_size(const char *path) {
    struct stat sb;

    if (S_ISREG(sb.st_mode)) { // if it's a file, not a directory (base case)
        return sb.st_size;
    }

    DIR *folder = opendir(path);

    struct dirent *element;
    size_t size = 4096;

    for (element = readdir(folder); element != NULL; element = readdir(folder)) {
        //(...)
        if (element->d_type == DT_DIR) {
            // Make sure the task receives a copy of the path
            char *priv_name = strdup(name); // (1)
            // recursive call of calculate_folder_size
            //               (2)
            #pragma omp task shared(size) firstprivate(priv_name)
            {
                // (3)
                #pragma omp atomic update
                size += calculate_folder_size(priv_name);
                free(priv_name); // (4)
            }
        } else {
            //(...)
        }
    }
    // (5)
    #pragma omp taskwait

    closedir(folder);
    return size;
}

这里的重要部分是:

  1. 你需要为任务传递一个名称参数,该名称参数将一直存在并保留其值,直到执行任务为止(可能在将来的任何时间)。因此,你需要使用复制一个name,例如strdup(3)

  2. 任务应记住当前值,priv_name因为它将在循环的下一次迭代期间更改。因此,firstprivate治疗priv_name因此,还需要能够size在父上下文中进行修改shared

  3. 由于所有任务都将更新size父作用域中的相同变量,因此需要使用来保护访问atomic update

  4. 不再需要私有名称,并且必须将其丢弃。

  5. 父任务应先等待所有子任务先完成,然后再返回size

必须从并行区域内调用此函数才能并行执行其工作:

int size;

#pragma omp parallel
#pragma omp single
size = calculate_folder_size("/some/path");

限制事物仍然并行运行的并行度的深度可能是一个好主意。我把它留给你弄清楚如何:)