How to run all threads in sequence as static with out using opemMP for?

Question

I'm new to openMP and multi-threading.

I have been given a task to run a method as static, dynamic, and guided without using OpenMPfor loop which means I cant use scheduled clauses.!

I could create parallel threads with parallel and could assign loop iterations to threads equally
but how to make it static and dynamic(1000 block) and guided?

void static_scheduling_function(const int start_count,
                                const int upper_bound,
                                int *results)
{
    int i, tid, numt;
    
    #pragma omp parallel private(i,tid) 
    {
        int from, to;
        
        tid = omp_get_thread_num();
        numt = omp_get_num_threads();
        from = (upper_bound / numt) * tid;
        to = (upper_bound / numt) * (tid + 1) - 1;
        
        if (tid == numt - 1)
            to = upper_bound - 1;
        
        for (i = from; i < to; i++)
        {
            //compute one iteration (i)
            int start = i;
            int end = i + 1;
            compute_iterations(start, end, results);
        }
    }
}


======================================
For dynamic i have tried something like this

void chunk_scheduling_function(const int start_count, const int upper_bound, int* results) {


       int numt, shared_lower_iteration_counter=start_count;

    for (int shared_lower_iteration_counter=start_count; shared_lower_iteration_counter<upper_bound;){

            #pragma omp parallel shared(shared_lower_iteration_counter)
            {

            int tid = omp_get_thread_num();
            int from,to;
            int chunk = 1000;



            #pragma omp critical
            {
            from= shared_lower_iteration_counter;                                      // 10, 1010
            to = ( shared_lower_iteration_counter + chunk );                           // 1010, 
            shared_lower_iteration_counter = shared_lower_iteration_counter + chunk;    // 1100  // critical is important while incrementing shared variable which decides next iteration

            }


            for(int i = from ; (i < to && i < upper_bound ); i++) {  // 10 to 1009 , i< upperbound prevents other threads from executing call
                int start = i;
                int end = i + 1;
                compute_iterations(start, end, results);
            }



        }

    }

}

Answer 1

This looks like a university assignment (and a very good one IMO), I will not provide the complete solution, instead I will provide what you should be looking for.

The static scheduler looks okey; Notwithstanding, it can be improved by taking into account the chunk size as well.

For the dynamic and guided schedulers, they can be implemented by using a variable (let us name it shared_iteration_counter) that will be marking the current loop iteration that should pick up next by the threads. Therefore, when a thread needs to request a new task to work with (i.e., a new loop iteration) it queries that variable for that. In pseudo code would look like the following:

int thread_current_iteration = shared_iteration_counter++;

while(thread_current_iteration < MAX_SIZE)
{
      // do work
      thread_current_iteration = shared_iteration_counter++;
}

The pseudo code is assuming chunk size of 1 (i.e., shared_iteration_counter++) you will have to adapt to your use-case. Now, because that variable will be shared among threads, and every thread will be updating it, you need to ensure mutual exclusion during the updates of that variable. Fortunately, OpenMP offers means to achieve that, for instance, using #pragma omp critical, explicitly locks, and atomic operations. The latter is the better option for your use-case:

#pragma omp atomic
shared_iteration_counter = shared_iteration_counter + 1;

For the guided scheduler:

Similar to dynamic scheduling, but the chunk size starts off large and decreases to better handle load imbalance between iterations. The optional chunk parameter specifies them minimum size chunk to use. By default the chunk size is approximately loop_count/number_of_threads.

In this case, not only you have to guarantee mutual exclusion of the variable that will be used to count the current loop iteration to be pick up by threads, but also guarantee mutual exclusion of the chunk size variable, since it also changes.

Without given it way too much bear in mind that you may need to considered how to deal with edge-cases such as your current thread_current_iteration= 1000 and your chunks_size=1000 with a MAX_SIZE=1500. Hence, thread_current_iteration + chunks_size > MAX_SIZE, but there is still 500 iterations to be computed.