[SOLVED] data structure algorithm openmp parallel The object of this assessment is to implement an alternative loop scheduling algo- rithm in OpenMP.

The object of this assessment is to implement an alternative loop scheduling algo- rithm in OpenMP.

You are provided with a piece of code which contains two loops which have been par- allelised with OpenMP directives. Instead of using the work sharing loop directive, the loop is scheduled by hand using a parallel region. The implementation you are provided with corresponds to the STATIC schedule kind. The code measures the execution time for 1000 repetitions of each loop, and includes a verification test for each loop.

You should always compile the code with the -O3 option to ensure a high level of sequential optimisation, but you must not alter the routines which contain the body of the parallel loops.

We will use the term chunk in the same sense as in the OpenMP standard, i.e. a contiguous, non-empty subset of the iterations of a loop.

Affinity scheduling
Affinity scheduling can be described as follows:

Each thread is initially assigned a (contiguous) local set of iterations.

For a loop with n iterations, and p threads, each threads local set is initialised with (approximately) n/p iterations.

Every thread executes chunks of iterations whose size is a fraction 1/p of the remaining iterations its local set, until there are no more iterations left in its local set. (Note that once a chunk is assigned to a thread, that thread should complete all the iterations in the chunk.)

If a thread has finished the iterations in its local set, it determines the thread which has most remaining iterations (the most loaded thread) and executes a chunk of iterations whose size is a fraction 1/p of the remaining iterations in the most loaded threads local set.

Threads which have finished the iterations in their own local set repeat the previous step, until there are no more iterations remaining in any threads local set.

You should take great care with the implementation of this algorithm to ensure that threads are correctly synchronised and there are no race conditions.

Once you have implemented the algorithm, run your code on 1, 2, 4, 6, 8, 12 and 16 threads and compare the results to the best built-in OpenMP schedule which you determined in Part 1 of the coursework.

Report :
2. a description of your implementation of the affinity scheduling algorithm, with particular attention to the shared data structures used and how the threads are synchronised. (Note that this section must be comprehensible without reading the source code: using pseudocode is encouraged, however.)
3. a discussion of the results of running the affinity scheduling algorithm,