15110 SUMMER SESSION ONE - 2013

Problem Set 9 - due Wednesday, June 19 at 10:30AM in class

Reading Assignment

Read chapter 4 of the book Blown To Bits, pages 109-137. (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 (A-N), and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(1 pt) Assume that the random number generator rand(n) is uniformly distributed. This means that the probability of generating any number between 0 and n-1 is the same.
Suppose that Alice simulates the roll of a pair of dice by defining the roll function below, calling it twice:
```
def roll()
    return rand(6) + 1
end
```
Bob realizes that the roll of a pair of dice results in a sum of 2 through 12, inclusive, so he simulates the roll of a pair of dice by defining the roll function below, calling it only once:
```
def roll()
    return rand(11) + 2
end
```
Are these equivalent in terms of their behavior over time as we generate roll after roll? Why or why not?
(1 pt) Consider three programs running simultaneously, each wanting access to the same three 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 three programs.
(2 pts) An operating system is a program that controls the operation of a computational device (computer, cell phone, game console, etc.).
1. An operating system contains a component called the kernel as shown below.
  
  (http://en.wikipedia.org/wiki/File:Kernel_Layout.svg)
  Based on the diagram, what role does the kernel play? Be specific. (HINT: Each arrow indicates that a specific layer communicates with the layer above or below it to request or receive something.)
2. Briefly explain how the operating system uses the principle of multitasking to run a number of programs "concurrently" on a device with a single processor core.
(1 pt) An image is simply an array of arrays of arrays of RGB values. For example, here is a 3 X 2 image consisting of a red and green pixel in the top row, a blue and white pixel in the middle row, and two black pixels in the bottom row:
```
[ [ [255,0,0] , [0,255,0] ],[ [0,0,255] , [255,255,255] ],[ [0,0,0] , [0,0,0] ] ]
```
We can remove the red components of an image using the following function in Ruby:
```
def remove_red(image)
  num_rows = image.length
  num_columns = image[0].length
  for row in 0..num_rows-1 do
    for column in 0..num_columns-1 do
      green = image[row][column][1]
      blue = image[row][column][2]
      image[row][column] = [0, green, blue]
    end
  end
  return nil
end
```
It is possible to accelerate the performance for the remove_red function 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?
(2 pts) A sorting network can also be drawn as a wire diagram, as shown below for a 6-element sorting network. Data enter from the left along the 6 horizontal lines and exit toward the right. Each vertical line represents a comparator with its inputs coming in from the left and outputs being sent out to the right. When two data values reach a comparator, they swap positions if the top value of the comparator is greater than the bottom value of the comparator.
1. Trace the operation of this sorting network on the inputs 8, 2, 9, 3, 0, 7 (from top to bottom). For each comparator write down the two numbers that leave the comparator to the right of the comparator, one per wire. For example, for the first comparator, it compares the 8 and 2 (which need to be swapped), sending out 2 along the top wire and 8 along the bottom wire. For the second comparator, it compares 8 and 9, sending out the 8 along the top wire and 9 along the bottom wire. Complete the rest of the wire diagram to show that this network sorts these 6 values.
2. In general, which comparisons in this diagram can be performed concurrently?
3. How many steps does it take to sort concurrently? How does this compare to the number of steps needed if we did each comparison sequentially (i.e. one at a time, non-concurrently)?
4. Do you recognize the sorting algorithm? What is it?
(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. Be specific.
(1 pt) At a university, a student club wants to send out an individualized invitation letter to 1000 faculty for an upcoming donor event. Each letter requires the following steps, in order:
```
1. Write a personal message to the faculty member on the inside of a card 
   (10 minutes).
2. Hand draw a scene with the club logo on the cover of the card with 
   colored pencils. (15 minutes)
3. Cut out and form a special envelope for the card out of a sheet of 
   premium paper. (3 minutes) 
4. Seal the card in the envelope with glue, look up and write the address 
   of the faculty member, and put a stamp on the card. (2 minutes)
```
1. If the club utilized the principle of pipelining and had four work stations, one for each step above, and one person to work at each workstation, how many minutes would it take to complete the 1000 invitations? How does this compare to one person completing the entire task? Show your work.
2. Can this task be completed even faster with four people concurrently? If so, explain how and compute the total amount of time needed to complete the task. If not, explain why.
(1 pt) Consider the following sorting network you saw in class:

Assume each comparator (i.e. the circles) takes time t to compare its two elements and output its results and that the time for a data value to go from one comparator to the next negligible. We wish to sort 1000 sets of 6 integers each.
1. If we sort one set of 6 integers completely before starting the next set, how long will it take to sort the 1000 sets in terms of t? Explain your answer. (Remember that some of the comparators are operating concurrently.)
2. If we use the principle of pipelining, how long will it take to sort the 1000 sets in terms of t? Explain your answer. (NOTE: To simplify the problem, assume there are some dummy comparators inserted into the network as shown below so that all results arrive at the output terminals at the same time.)