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 109-137. (Feel free to read the whole chapter if the material interests you.)

Instructions

Exercises

  1. (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. (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 a0 < a1 < a2 < a3 and b0 < b1 < b2 < b3.

    1. 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.

    2. If a comparison of two data values takes time t, how long does it take to merge the two arrays together using the traditional non-concurrent merge algorithm? How long does it take to merge the two arrays together using the concurrent network shown above? Explain each answer.

  3. (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.

  4. (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?

  5. (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)

    1. 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?

    2. 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.

  6. (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.

    1. 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.

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

    3. 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!)

  7. (2 pts) In class, we discussed a situation called deadlock which can cause a system to stop functioning.

    1. 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.

    2. 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.