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

The object of this assessment is to implement an alternative loop scheduling algorithm in OpenMP.
You are provided with a piece of code which contains two loops which have been parallelised 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.
The code can be found on the course pages on Learn. You may choose to work with either the C (loops2.c) or Fortran 90 (loops2.f90)version.
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.
1

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.
Submission
You are required to submit the following:
A written report.
(Guideline length: 7-10 pages including figures and tables.)
Source code.
The deadline for both report and source code is 16:00 on Friday 29th November 2019.
Your report should contain the following sections:
a short introduction
a description of your implementation of the affinity scheduling algorithm, withparticular 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.)
a discussion of the results of running the affinity scheduling algorithm, including appropriate graphs and/or figures
some brief conclusions
Your report should not contain any background material.
The code will be marked on design and readability as well as correctness and performance.
2