Assignment 1 ECSE 420: Parallel Computing



Assignment 1
ECSE 420: Parallel Computing

Submission instructions: Students are to work in groups of two on the assignment.
Students must also submit a pdf file that contains the following information: student’s names,
student ids, instructions on how to run each file and the associated question solved. Students
are also expected to submit a zip file containing their source code. This code must compile and
run without error. The code must be well formatted, commented, and follow the google java
style guide. Source codes are provided for Questions 1 & 3; students just need to modify these
source codes. For more information, see the ECSE420AssignmentSubmissionInstructions.pdf in
the Assignment section on myCourses.
1. (24 marks) Matrix multiplication is a common operation in linear algebra. Suppose you have
multiple processors, so you can speed up a given matrix multiplication.
1.1. Modify the following method in the source code to Implement a matrix multiplication
public static double[][] sequentialMultiplyMatrix(double[][] a, double[][] b)
1.2. Modify the following method in the source code to Implement a matrix multiplication in
public static double[][] parallelMultiplyMatrix(double[][] a, double[][] b)
Expalin the parallel tasks defined in your code.
1.3. Add a method to the source code that measures the execution time for both sequential
and parallel matrix multiplication.
1.4. Vary the number of threads being used by the parallel method for matrix sizes of 2000
by 2000, and plot the execution time as a function of the number of threads.
1.5. Vary the size of the matrices being multiplied as (100 by 100, 200 by 200, 500 by 500,
1000 by 1000, 2000 by 2000, 4000 by 4000) and plot the execution time as a function of
matrix size for both parallel and sequential methods in one figure. Use the number of
threads for wich the parallel execution time in 1.4 is minimum.
1.6. For the generated graphs in 1.4 and 1.5 comment on their shape and possible reasons
for the observed behavior.
2. (8 marks) Write a program that demonstrates deadlock.
2.1. Explain under what conditions a deadlock could happen.
2.2. Discuss possible design solutions to avoid deadlock.
3. (16 marks) The dining philosopher’s problem was invented by E. W. Dijkstra, a concurrency
pioneer, to clarify the notions of deadlock and starvation freedom. Imagine five philosophers
who spend their lives just thinking and feasting. They sit around a circular table with five
chairs. The table has a big plate of rice. However, there are only five chopsticks (in the
original formulation forks) available, as shown in Fig. 1. Each philosopher thinks. When he
gets hungry, he sits down and picks up the two chopsticks that are closest to him. If a
philosopher can pick up both chopsticks, he can eat for a while. After a philosopher finishes
eating, he puts down the chopsticks and again starts to think.
Figure 1
3.1. Modify the class public class DiningPhilosophers in the source code to simulate the
behavior of the philosophers for any number n of them, where each philosopher is a
thread and the chopsticks are shared objects. Notice that you must prevent a situation
where two philosophers hold the same chopstick at the same time. Notice that in this
program philosophers should be eventually deadlocked.
3.2. Amend your program so that it never reaches a state where philosophers are
deadlocked, that is, it is never the case that each philosopher holds one chop- stick and
is stuck waiting for another to get the second chopstick. Explain your solution to avoid
3.3. Amend your program so that no philosopher ever starves. Explain your solution to avoid
4. (12 marks) Use Amdahl’s law to answer the following questions:
4.1. Suppose the sequential part of a program accounts for 40% of the program’s execution
time on a single processor. Find a limit for the overall speedup that can be achieved by
running the program on a multiprocessor machine.
4.2. Now suppose the sequential part accounts for 20% of the program’s computation time
(S = 0.2). Let sn be the program’s speedup on n processes, assuming the rest of the
program is perfectly parallelizable. Your boss tells you to double this speedup: the
revised program should have speedup s′n > sn*2. You advertise for a programmer to
replace the sequential part with an improved version that decreases percentage of the
sequential time -S- by a factor of k. What value of k should you require?
4.3. Suppose the sequential time percentage could be decreased three times, and when we
do so, the modified program takes half the time of the original on n processors. What

fraction of the overall execution time did the sequential part account for? Express your
answer as a function of n.
Total: 60 marks


There are no reviews yet.

Be the first to review “Assignment 1 ECSE 420: Parallel Computing”

Your email address will not be published.