闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS450: Introduction to Parallel Programming

Assignment 6: Programming with OpenMP

2022

Preliminaries

You are expected to do your own work on all homework assignments. You may (and are encouraged to) engage in discussions with your classmates regarding the assignments, but speciﬁc details of a solution, including the solution itself, must always be your own work. See the academic dishonesty policy in the course syllabus.

Submission Instructions

You should turn in an electronic archive (.zip, .tar., .tgz, etc.). The archive must contain a single top- level directory called CS450 aX NAME, where “NAME” is your NAU username and “X” is the assignment number (e.g., CS450 a6 ab1234). Inside that directory you should have all your code (no binaries and other compiled code) and requested ﬁles, named exactly as speciﬁed in the questions below. In the event that I cannot compile your code, you may (or may not) receive an e-mail from me shortly after the assignment deadline. This depends on the nature of the compilation errors. If you do not promptly reply to the e-mail then you may receive a 0 on some of the programming components of the assignment. Because I want to avoid compilation problems, it is crucial that you use the software described in Assignment 0. Assignments need to be turned in via BBLearn.

Turn in a single pdf document that outlines the results of each question. If you were not able to solve a problem, please provide a brief write up (and screenshots as appropriate) that describes what you tried and why you think it does not work (or why you think it should work). You must provide this brief write up for each programming question in the assignment.

This pdf should be independent of the source code archive, but feel free to include a copy in the top level of that archive as well.

Make sure that you conﬁgured your virtual machine to use multiple cores. Otherwise, you will not be able to see any speedup.

Validation of All Questions

You are responsible for ensuring that your program is correct. There are no testing scripts for this assign- ment. You must determine how to ensure program correctness.

Work To Do

In this assignment, we take a look at matrix multiplications, a very common computation with a lot of potential for improvements. If you do not remember/do not know how to compute matrix multiplications, I invite you to look online. You can also ask me if you prefer. And I also encourage to ask for assistance if you need to. The idea in this assignment is that we have 4 matrices: A, B , C, and Result, and the computation we are trying to do is Result = A × B + C . For simplicity, we will only look at square matrices. Finally, the objective here is for you to ﬁnd several diﬀerent optimizations to improve the performance of the program. You are provided with the basic method to compute matrix multiplications (with an O(n3 ) complexity), that you can use as a blueprint for your optimizations. The idea is that you should ﬁnd an optimization, time it, ﬁnd another optimization built upon the previous one, etc. So overall, incrementally improve the performance of the basic algorithm. If you decide to parallelize your code, you should use OpenMP (and a #pragma omp parallel for at the right spot might actually consist of a ﬁrst optimization!). I recommend

you to take a look at the lectures that brieﬂy discuss matrix multiplication loops, and the lectures about programming for locality (think about blocking/caching).

Please keep the major versions that you try, I want to see how you went from the basic solution to your best one. You should be able to ﬁnd at least 3 optimizations. Thus, I expect to see for example 3 new functions in the code, each with diﬀerent/combined optimizations. Note that just using -O3 does not consist of an optimization. You may want to use -O2 or -O3 for other optimizations though. . . . As another indication, for a matrix size of 4096, the execution time in sequential is s 380s, s 50s using 8 threads/cores, and s 15s when adding other optimizations (but without -O3). These are the execution times on my machine, I do not expect your algorithm to execute in the same amount of time. However, I expect your algorithms to achieve similar speedups. Feel free to test your code on smaller matrices, but keep in mind that I will run tests on larger ones (such as 4096). So your code needs to work regardless of matrix size! Finally, there are many options for you to improve performance, so be creative!

Results

For each version of your matrix multiplication that you write, please report in the pdf ﬁle the execution time you achieve, using a matrix size of 4096, as well as the speedup over the previous version of the algorithm. You should also indicate in a few words what kind of optimization(s) you are using, and a few sentences explaining why you think it is performing better.

For example, you should write the results like that:

●Version 1 of the algorithm, function matrixMultiplyBasic, sequential, no optimization, matrix size = 4096, execution time = 376s.

●Version 2 of the algorithm, function matrixMultiplyVersion2, sequential, optimizations XYZ, matrix size = 4096, execution time = 286s.

●Etc.