Assignment#1

    1. In this problem, you will write a shared memory parallel program to solve a lower triangular system of equations Lx = y where L is an n n lower triangular matrix of reals and x; y are real-valued n 1 vectors. The problem is

to find x given L and y. Row i of a lower triangular matrix has zeroes in columns i + 1 to n 1 for 0 i n 1. Additionally, we will assume that no diagonal element of L is zero. The program will take an input file name, an output file name, and the number of threads from the command line exactly in that order. The first line of the input file specifies the value of n. The second line onward it lists the non-zero elements of L row-wise. The last line of the file lists the elements of y. I have included a sample file specifying the following L and y.
L =
21:0
2:2
0
3
; y =
24:53
:

1:0
0
0


4
2:3


43:0
4:1
1:35


7:25

Note that reading large matrices from the file may take a significant amount of time. So, for testing your program on large matrices quickly, you can initialize L and y with arbitrary values in your program. Please put this code in a clearly marked function named InitializeInput. Comment out the call to this function in your submission so that we can test your program with our input test files. The program should output the elements of x in the first line of the output file. The output file should not have any other lines. Please feel free to choose OpenMP or POSIX thread for your implementation. Hint: Do not invert L and then multiply by y. Use simpler ways of finding x. (10 points)

What to submit and how. For each question, submit the parallel program. Prepare a report describing your parallel algorithms, the optimizations you applied (if any) for improving performance, and the performance results. Please clearly specify in the report whether your program is written using OpenMP directives or POSIX thread libraries for each program.


1
For the first question, report results for at least five graph sizes. All five graphs must be complete graphs. For each graph, prepare a table showing how the measured time varies with the thread count (the range of thread count is left to you). Try to pick largish graphs that your program can run within reasonable time. Remember to specify the number of vertices in each graph clearly. Discuss the observed trends with explanation.

For the second question, report results for at least five values of n. For each n, prepare a table showing how the measured time varies with the thread count. Remember to specify the values of n clearly. Try to pick large n that your program can run within reasonable time. Discuss the observed trends with explanation.

Note that your marks will depend on how good your program is in terms of performance, how well the algorithm is described in the report, and the discussion on the results. In your measured time, do not include any time that is needed to allocate memory or initialize arrays. Please refer to the examples discussed in the class. You will not get any marks if your program does not compile or crashes during execution. Only the programs that compile and run to completion without any error will be considered for grading.

Please send your submission (two programs and a PDF report) via email to cs433submit2022@gmail.com with subject “Assignment#1 submission Group#X”. Replace X by your group number in the subject line.

















































2