Discuss the parallel performance of the lu factorization

Assignment Help Theory of Computation
Reference no: EM13923511

You are provided with a program matrix_serial . c to solve a linear system of equations Ax = b. The code includes routines to initialize A and b, compute the LU factorization of A, and solve triangular systems with lower and upper triangular matrices. The main program uses these routines to compute the solution of the system Ax = b by computing A = LU, and solving Ly = b for y, followed by Ux = y for x. Instructions to compile and execute the code are included in the file.

You need to parallelize the routines for computing LU factorization and solving the triangular systems using pthreads. The file should be named matrix . c.

1. You need to parallelize the routines for computing LU factorization and solving the triangular systems using pthreads. The file should be named matrix . c. A total of 20 points are reserved for performance of the code: speedup obtained by the multithreaded code and the overall execution time will be considered when awarding these points.

2. Execute the code for n= 212 with p chosen to be 2k, for k = 0, 1,...,6. Plot execution time versus p to demonstrate how time varies with the number of threads. Use logarithmic scale for the x-axis. Plot speedup versus p to demonstrate the change in speedup with p.

3. Discuss the parallel performance of the LU factorization routine and the triangular solver routines. Comment on the observed performance and the possible reasons for the observations.

4. You will receive bonus points equal to the amount the sum of speedups observed in the following routines - LU factorization, lower triangular solve, and upper triangular solve - exceeds 2.0. Speedup is computed as the speed improvement achieved by each routine over the execution time of the routine reported by matrix_serial . c for a single run. Bonus points are subject to a maximum of 10 points. Total speedup value will be rounded. Individual routine speedup values lower than 1.0 will be raised to 1.0 to compute bonus points. For example, a speedup of 3.5, 2.1, and 0.7, respectively, in the three routines is awarded 5 bonus points. In your submission, you need to specify the input arguments to the executable that produce the best speedup. Also indicate the speedup you observe in each of the routines. Compilation will be done using icc with default optimization.

Attachment:- hw4.txt

Reference no: EM13923511

Write negative binary numbers in sign and magnitude

The first part of this unit introduces the material to be studied later. In addition to getting an overview of the material in the first part of the course, you should be ab

How much can you improve on these upper bounds

FIT2014 - Assignment - Legal and almost-legal positions can be counted using the scheme and How much can you improve on these upper bounds? In particular, can you reduce the

Test coupled with real users views of the product

Explain the importance of having a test coupled with real users' views of the product at the end of the development effort, even if it is the test of a prototype and not the

Construct a diagram to map the arguments

Construct a diagram to map the arguments about a moral claim that you have identified and write an essay, which maps closely to the diagram that you constructed in Step 1.

Determine if system in a safe state-share nine tape drives

There are four processes that are going to share nine tape drives. Their current and maximum number of allocation numbers. Is system in a safe state? Explain why or why not?

Subset-sum problem

Calculate some number x= Sum - 2K. Create new set A by add x to the set B {b1, b2,....., bn} U {x}, where the summation now is B+x. it is possible to split the numbers in A in

Write turing machine algorithm to perform a unary decrement

Write a Turing machine algorithm to perform a unary decrement. Assume that the input number may be 0, in which case a single 0 should be output on the tape to signify that t

Construct a turing machine to compute the product

Construct a turing machine to compute the product x*y of any two positive integers x and y. Assume that the inputs x and y are represented in unary and are separated by a si

Reviews

Write a Review

 
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd