15110 Fall 2011 [Cortina/von Ronne]
Written Homework 9  due Friday, November 11 in class
Reading Assignment
Read chapter 4 of the book
Blown To Bits, pages 109137. (Feel free to read the whole chapter
if the material interests you.)
Instructions

Type or neatly write the answers to the following problems.

Please STAPLE your homework before you hand it in.

On the first page of your homework, include your name,
andrew ID, lab section (AN), and the assignment number.

You must hand in your homework at the start of class on the given due date.
Exercises
 (1 pt)
In the Blown To Bits reading, you learned how Google handles a
search query for the World Wide Web. Describe one way how Google uses
concurrency (parallelism) based on your reading.
 (2 pts)
Consider the 4x4 merge sorting network shown below. It consists of a set
of comparators. Each comparator sends the smaller of A or B to its
L output and the larger of A or B to its H output. Assume that
a_{0} < a_{1} < a_{2} < a_{3}
and
b_{0} < b_{1} < b_{2} < b_{3}.

Show how the arrays a = [3, 7, 9, 14] and b = [2, 8, 10, 12] are sorted
in this network by showing the path of each data value through the
network. That is, draw the network and write down where each data value
is along each edge of the network as it passes through each stage.

If a comparison of two data values takes time t, how long does it
take to merge the two arrays together using the traditional
nonconcurrent merge
algorithm? How long does it take to merge the two arrays together using
the concurrent network shown above? Explain each answer.
 (1 pt)
Assume the 4 X 4 merge network from problem 1 is represented
abstractly as shown below:
Draw a picture of an 8 X 8 merge network using this abstraction.
 (1 pt)
It is possible to accelerate the performance for the remove_red
function from the introduction of Programming Assignment 7 by modifying
it to perform the work on the different pixels concurrently instead of
following the ordering given by the loops. Could the same be done for
the problem of implementing a function that returns an array of n
pseudorandom numbers generated using a linear congruential generator?
Why or why not?
 (1 pt)
At a furniture factory, a bookcase is manufactured using the following
four steps in sequence:
1. Cut the wood pieces (30 minutes)
2. Sand and stain the wood pieces (50 minutes)
3. Drill pilot holes for all screws (20 minutes)
4. Screw pieces together to assemble bookcase (10 minutes)

If one bookcase is made at a time, and the factory wants to make 600
bookcases, how many minutes would it take to complete this task?

If the factory utilized pipelining and had four work stations, one for
each step above, how many minutes would it take to complete this task?
Show your work.
 (2 pts)
Consider the sorting network shown below that sorts 6 data values.
Each circle is a comparator like those discussed
in class. The value that is smaller exits from the top right and the
value that is larger exits from the bottom right.
The input data values are not necessarily
sorted.

Explain clearly and concisely why the maximum data value must always
end up in bottom box on the output side of the network,
no matter what position it starts in on the input
side of the network. NOTE: Do not write out all six different
scenarios that can occur. Instead, think about where the maximum must
be at each stage of the network.

If each compator takes time t to compute its output, how long
does it take to compute the final output of this network concurrently?

If we wanted to use this network for 10 sets of 6 data values, what is the
minimum amount of time that it will take to compute the final output for
all 10 sets of data, as a function of t? (HINT: Think pipelining!)
 (2 pts)
In class, we discussed a situation called deadlock which can cause a
system to stop functioning.

Consider a main road (shown running left to right) with two side roads.
All roads have single lanes in each direction.
Explain how deadlock can occur on the main road. Draw a picture to help
illustrate your answer.

Consider two programs running simultaneously, each wanting access to the
same two databases. When a program accesses one database, it locks it so
another program cannot use it. Once the program is done using the
database, it unlocks the database. If a program tries to access a database
and it is locked, it waits until it is unlocked. Explain how deadlock can
occur for these two programs.