#### CSci 415 - Homework #2

Due: Sept
19, 2017 Sept 20, 2017
by 5pm

#### Purpose:
to better understand important concepts from Chapter 2. This assignment is
worth 50 points.

Reading:
- Pacheco: Chapter 2 Sections 2.3-end. It's worth studying 2.6 again!
- King: Continue reviewing as needed: Chapters 3, 11, 12, 16, 17
(through 17.4)

**Warmup**. If you have a Dokuwiki account (say, from CS 276) make sure
you can log in. You should be able to reset the password if you've
forgotten. If you have **never** had a Dokuwiki account, go to the CS
415 page and **register** (link is at top of page). You will need
to wait until I've confirmed your registration before doing Problem 1.

Problems.

- (4 points) Set up your Wiki
page. Add a heading for
**Homework 1** (yes that's a 1 not a
2) and add your paragraphs for Problem 3 (concepts you were assigned)
there. This is so that everyone has access to these definitions. If you
turned in your only copy as part of your homework, put this up just as
soon as you get it back.

- (3+3 points)
**Speedup/Efficiency I**: Exercise 2.10 (a and b)

- (12 points)
**Speedup/Efficiency II: **Exercise 2.16(a). You can
write this program in C or Java. Make **n** and **p**
command-line arguments. Run this program first holding **n**
fixed at 20 and increasing values of **p**, then run with **p**
fixed at 16 for the increasing values of **n**. Use
Matplotlib to plot two graphs to help visualize what's happening, one
for speedups and the other for efficiencies. Use this to answer the
questions given. Save your graphs as HTML, but rather than post the
graphs, print them and attach to your code printout.

- (4 points)
**Scalability**: Exercise 2.20

- (8 + 8 points) Read the
**multicore** papers linked on the
Schedule for Tuesday 9/12. Write two to three paragraph summaries of
each.

- (8 points) Say we have this sorting
algorithm. Just considering the method
**quickSortRecursive**
(__and__ the methods it calls), determine which lines can be
parallelized (just using intuition right now, making educated guesses)
and count the number of lines which can be run in parallel, and the
number which must be sequential.

- Amdahl's law says if a fraction
**r **of a program
cannot be parallelized, the maximum speedup is **1/r**.
Determine the maximum speedup.
- Can we run the
**for** loops
in **main** in parallel? That
is, could we farm out each iteration to a different processor, if we
had enough?
- Will running this parallelized version on 16 cores (assume an
array with billions of elements) be worthwhile? Explain.
- Will running this parallelized version on 1024 cores (assume an
array with billions of elements) be worthwhile? Explain.

#### Deliverables

- Turn in your answers to written questions in class
** ***or*
in the box outside my door by 5:00 pm Wednesday **9/20**.

- Turn in a printout of your program code and graphs in the same way.