MAPS 7873 Assignment 1: OpenMP Programming You are asked to employ OMP threading techniques to implement a parallel-processing solution for the SortOut program seen in the Lab sessions with a view to improving the performance of the code. A C++ project file is provided as a starting point: MAPS sortOut for OMP Assignment.zip You should implement the six requirements described overleaf, and time them. A brief report describing your overall parallel design should be produced (using diagrams similar to those in the Lab sheets), and include your 'before parallel' and 'after parallel' timings for each of the listed requirements. For convenience consider outputting your timings to a separate .CSV or .TXT file in your program. The project provided has basic timing included - feel free to use the OMP versions of the performance timers (seen in the lab sessions). You should make use of both OpenMP constructs parallel for and parallel sections at least, using clauses appropriate to your design. Feel free to create more than one solution if you can see interesting alternatives. As the lab PCs in 9341 only have 4 threads available it is acceptable to implement this assignment using processors elsewhere in the University, most of which have 8 threads available - or on your laptop, home PC, etc, if these provide 8 or more threads. This may affect some of your design decisions. Your code will be run for checking purposes on this processor (my SHU computer): …so bear this in mind. You can use CPU-Z to check for the number of threads on your machine (as above), or use the OMP routine "omp_get_max_threads()" in your code. Note: You are not constrained to using the bubble sort method – you may choose another that may be more easily parallelised. It may also be useful to use a different method for the sort all task as this involves a much larger data set. Thinking about OMP's facilities and where they could be applied would be sensible when choosing sort algorithms. Nb. The bubble sort on all data took over 80 minutes on my PC! You can assume the numbers to be sorted are unsigned integers in the range 1 - 32,767. Requirements The tasks to be implemented and timed are as follows: 1. sortRows – sort each row of 1000 numbers in ascending order. 2. outputSortedRows – output the sorted rows as SortedRows.txt 3. calcMovingAve – calculate a 100 number moving integer average for each number in each sorted row (see below for the algorithm). 4. outputMovingAve – output the rows of moving averages as MovingAve.txt 5. sortAll – sort all of the data (all 2,000,000 numbers!) in ascending order. This can be done on the already row-sorted data, or on the initial data set. 6. outputSortedAll – output the 2,000,000 sorted numbers as SortedAll.txt For readability, output the numbers in order as 2,000 rows of 1,000 numbers. 7. Finally, output the combined times of all of these requirements as one figure. I will publish a time - ordered ranking for interest after benchmarking all submissions. Your mark won't be affected by your position! I will be awarding some sort of prize to the student gaining the fastest overall time! Note :If you wish to reduce the size of the data set for pragmatic testing reasons, that's OK, but the final timings must be on the original data set size. The algorithm for calcMovingAve for a set of n numbers stored in 'data' is: for i = 0 to (n – 1) if i <= n – 100 (check there are still 100 numbers left) then set m to 100 (ok, use 100 as limit) else set m to (n – i) (fewer than 100, use what's left as limit) end if set sum to 0 for j = i to (i + m - 1) sum = sum + data[j] next j movingAve[i] = sum/m next i Deadline: midnight (23.59pm) Tuesday 21st February, 2017 via Bb submission Assessment Criteria and Marking Scheme Total marks available: 100. Module weighting: 30%. Designs – 20 marks To obtain full marks, produce diagrams for your design showing task execution over time - use the block diagram style as in Lab 2 or the thread diagram style as in Lab 1. Your final diagrams should show the program tasks roughly in proportion to their times. Where a task has both serial and parallel elements, this should be clear in the diagram. Your diagrams should accurately reflect the structure and elapsed timings of your implementation. Your designs should not include elements that are peripheral to the requirements, e.g. do not include or time the function that randomises ('gets') the data or the function that outputs the times. Implementation – 60 marks To obtain full marks, implement your design to the best of your ability so that the requirements are met and notable speedups are achieved over the original. Your implementation should accurately reflect the structure of your designs. You should not include parallel techniques or constructs other than those provided by OMP. You may, of course, also optimise your code in other ways, using what you've learnt elsewhere, but these efforts won't accrue additional marks. Instrumentation, Timings and Explanation – 10 marks To obtain full marks, your code should be properly instrumented to time the six tasks outlined in the requirements, plus the overall time of the six tasks combined. Your program should output these to the console at least. Your design report should be well structured, and include the before and after timings claimed and the number of threads available on the processor used for testing. Surprising events such as slow downs, or unsolved crashes of your code should be mentioned and a possible explanation offered. You should not time elements that are peripheral to the requirements. You may wish to output timing data to a text file in addition to the console for convenience. Code Quality – 10 marks To obtain full marks, you code should be well-structured, liberally and accurately commented, and readable. The designs should be clearly reflected in the source code listings. Do not include unused functions or commented-out lines of code in your final submissions. Please always include your name and student number in the opening comments of any source code you produce. Blackboard Submission Requirements Please submit your designs and C++ source files to the MAPS Blackboard site (Assessment 2017/ Assessment 1), and name them as follows: : lastname_firstname_OMPdesigns.docx* lastname_firstname_OMPsortOut.cpp *or the file extension of whatever document type you have used. I would prefer it if I can read it without trouble, so please save as a PDF document if you're using an exotic word processor!