Parallelizing recursion in a for-loop using readdir

Question

I'd like to parallelize a C-program which recursively calculates the size of a directory and its sub-directories, using OpenMP and C.

My issue is, that when I get into a directory using opendir, and I iterate through the sub-directories using readdir I can only access them one by one until I've reached the last sub-directory. It all works well sequentially.

When parallelizing the program, however, I think it would make sense to split the number of sub-directories in half (or even smaller partitions) and recurse through the sub-directories using OpenMp Tasks.

Obviously I can't simply split the problem size (= number of sub-directories) in half, because of the structure of the for-loop, and loops like this cannot be parallelized using #pragma omp for.

Does anybody have an idea on how to split this function into tasks? Any help would be greatly appreciated.

This is some of my code (I've removed parts I do not deem relevant for this question.)

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;
}

Given that the file system is likely to be a tree, and your underlying machine is likely to not be a tree, you likely have a fixed amount of parallel computational capacity. Mapping a tree of work onto a fixed set of workers is best done by futures and promises. — user3185968
– user3185968, Commented May 2, 2020 at 11:09
I don't see any use in parallel processing directories as the main bottleneck will be the [disk] I/O. At worst you will decrease performance due to the disk heads seeking and seeking and seeking to satisfy te requests of the parallel threads. — Paul Ogilvie
– Paul Ogilvie, Commented May 2, 2020 at 11:11
Thank you two. Considering that afaik the hard drive cannot perform parallel read/write operations it seems like an odd homework assignment that I was given here... — Dreana
– Dreana, Commented May 2, 2020 at 14:53
The hard drive cannot perform reads in parallel, but the filesystem can issue more reads per unit of time when read in parallel than when read sequentially. This is a typical example of a latency hiding technique. — Hristo Iliev
– Hristo Iliev, Commented May 2, 2020 at 21:15

Hristo Iliev · Accepted Answer · 2020-05-02 22:28:20Z

You need a modern compiler with support for OpenMP tasks, which removes Visual C++ from the equation. Provided you are using such a compiler, all you need to do is to turn the recursive invocations to calculate_folder_size() into OpenMP tasks:

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;
}

The important parts here are:

You need to pass the task a name parameter that will live and retain its value until the task gets executed, which could be any time in the future. Therefore, you need to make a copy of name, e.g., using strdup(3).
The task should remember the current value of priv_name since it will change during the next iteration of the loop. Therefore, the firstprivate treatment of priv_name. It also needs to be able to modify size in the parent context, hence shared for it.
Since all tasks are updating the same size variable in the parent scope, the access needs to be protected with atomic update.
The private name is no longer needed and must be disposed.
The parent task should wait for all child tasks to finish first before returning size.

This function must be called from within a parallel region in order to do its job in parallel:

int size;

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

It might be a good idea to limit the depth of parallelism at which things still run in parallel. I leave it to you to figure it out how :)

Thanks a lot for your help! This works well and your explanations really helped me.

Collectives™ on Stack Overflow

Parallelizing recursion in a for-loop using readdir

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related