Homework 1
Question 1
If 99.9% of your sequential program execution time is spent inside a loop that can be parallelized, what
is the maximum speedup you can achieve via parallelizing this loop?
Question 2
If a two-hour parallel program running on one thousand cores spends one hour in its parallel portion,
what is the scaled speedup of the program on one thousand cores?
Question 3
A parallel program achieves a speedup of 2 on 4 cores. Is it likely to achieve a speedup of 4 on 8 cores?
Question 4
A computer animation program generates feature movies frame-by-frame. Each frame can be generated
and written to its own file independently. If it takes 90 seconds to render a frame and 10 second to write
a frame into a file, what is the maximum speedup you can achieve if you have 100 single-processor
computers to use?
Question 5
Let n>f(p) denote the Isoefficiency relation of a parallel system and M(n) denote the amount of memory
for a problem of size n. Use the scalability function to rank the following parallel systems from most to
least scalable:
(a). f(p)=p and M(n)=n;
(b). f(p)=p and M(n)=n^2;
(c). f(p)=p*log(p) and M(n)=n;
(d). f(p)=p*log(p) and M(n)=n^2.
Question 6
Your program has an execution time of n^3 and uses n^2 bytes space when the problem size is n. You
have worked very hard to make it fully parallel and reduced the communication time to 𝟐𝟒𝒏𝟐𝒍𝒐𝒈𝟐
𝒑
on
p cores. If you want to achieve a speed up of 1000 with 1024 cores, what is the minimum memory each
core must have? If you have 1024 cores with 1 GB (2^30 bytes) memory per core, what is the maximum
speedup you can achieve?