In Assignment 1, you need to tackle the programming tasks as described below using C and OpenMP; you must not use C++. You also need to write a report on your work.
Gaussian elimination with partial pivoting is a technique used to solve a system of linear equations. It adds multiples of each row to later rows to transform the matrix into triangular matrices L and U. Partial pivoting technique is applied to make the algorithm stable; that is, in each elimination iteration, rows are swapped so that the leading element A(i,i) is the largest in the leading column to prevent division by zero. A serial pseudocode is given below.
In this assignment there are two programming tasks.
Task 1: Revise a simple program gepp_0.c for Gaussian elimination with partial pivoting to significantly improve its performance by using both blocking and loop unrolling techniques.
In your implementation:
• Your program needs to ask for N (i.e., the size of the matrix) as a user defined parameter;
• The block size b is set to 4 and the loop unrolling factor is also set to 4;
• Your main program must conduct a self-check for correctness; i.e., perform a basic
Gaussian elimination with partial pivoting as done in gepp_0.c and your revised version using both blocking and loop unrolling techniques with the same input data set.
• To evaluate the performance of your program, you must use the gcc optimization option flag -O3; i.e., compile your program using gcc -O3.
Task 2: Revise the program you have done for task 1 by adding OpenMP directives and clauses to make it efficiently solve the same problem on a parallel shared-memory computing platform.
In your implementation:
• Your program needs to ask for N and T (i.e., the number of threads to be created in executing your program) as user defined parameters;
• After the parallel computation, your main program must conduct a self-check for correctness; i.e., perform a sequential computation using the same data set and then compare the result of this computation with the parallel computation result.• To compile your program, use gcc -fopenmp -O3.
Your programs must be able to be compiled and run on Microsoft Azure Virtual Machines.
Otherwise, marks will be heavily deducted.
Report: You must write a report. The report should be concise, clear (3-6 A4 pages) and
contain the following sections for each task:
1. Problem definition and requirements
2. Algorithm design and implementation
3. Testing and performance evaluation
4. Discussion
5. Known issues in the program
6. Manual (e.g. how to compile and run the program, input and output)
Your assignments will be marked on correctness of results, the efficiency of your algorithm, program logic and readability, and quality of your report.
You MUST attempt this assignment individually.
AI use policy: You are permitted to use Artificial Intelligence (AI) tools to help you develop your programs and write your report. You are required to complete and submit the “Acknowledgement of AI Use Form”, even if you do not use AI tools at all. You will not lose marks for using AI tools as long as you correctly acknowledge your use of them.
Submission Requirements
1. Your submission must be made by 11:59pm on Friday, 12 April, 2024 (Sydney time).
2. Create a tar or zip file that contains your makefile and source files (e.g., .c and .h files) and “Acknowledgement of AI Use Form”. DO NOT INCLUDE ANY OBJECT OR BINARY FILES.
• Submit only one .tar or .zip file to the “Assignment 1 code submission inbox”.
3. Save your report in pdf format.
• Submit your report to the “Assignment 1 report submission inbox”.
Failure to follow these submission requirements may lead to loss of marks.