Распараллеливание рекурсии в for-l oop с использованием readdir - PullRequest
Новая
       106

Распараллеливание рекурсии в for-l oop с использованием readdir

0 голосов
/ 02 мая 2020

Я бы хотел распараллелить C -программу, которая рекурсивно вычисляет размер каталога и его подкаталогов, используя OpenMP и C.

Моя проблема в том, что когда я получаю в каталог, используя opendir, и я перебираю подкаталоги, используя readdir, я могу получить к ним доступ только один за другим, пока не достигну последнего подкаталога. Все это работает хорошо последовательно.

Однако, при распараллеливании программы, я думаю, что имеет смысл разделить количество подкаталогов пополам (или даже меньших разделов) и проходить по подкаталогам с помощью OpenMp. Задачи.

Очевидно, что я не могу просто разделить размер задачи (= количество подкаталогов) пополам из-за структуры for-l oop, и подобные циклы нельзя распараллелить, используя #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;
}

1 Ответ

1 голос
/ 03 мая 2020

Вам нужен современный компилятор с поддержкой задач 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, так как оно изменится в течение следующего итерация l oop. Следовательно, firstprivate обработка priv_name. Также необходимо иметь возможность изменять size в родительском контексте, следовательно, shared для него.

  3. Поскольку все задачи обновляют одну и ту же переменную size в родительской области доступ должен быть защищен с помощью atomic update.

  4. Частное имя больше не требуется и должно быть удалено.

  5. Родитель задача должна дождаться окончания всех дочерних задач sh, прежде чем вернуть size.

Эта функция должна вызываться из параллельного региона, чтобы выполнять свою работу параллельно: 

int size;

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

Возможно, было бы неплохо ограничить глубину параллелизма, при которой все еще идет параллельно. Я оставляю это вам, чтобы понять, как:)

...