Exercises for October 31

  • Exercise 1: Pipelining. Draw a diagram, like B&H Figure 4.42, p. 405, showing how the instructions in the "copying" function in copying.s flow through the F-D-E-M-W pipeline when n=5.

    How many cycles are used?

  • Exercise 2: Optimizing vector inner product. B&H Homework problem 5.15, p. 549.

  • Exercise 3: Matrix multiplication by block partitioning.

    Let c and r be integers, less than or equal to an integer n.

    Suppose we want to form C = A * B where A is an nxn matrix and B is an nxn matrix. Consider performing the multiplication by partitioning A into rxc blocks and partitioning B into cxr blocks and doing block multiplication. For example, we would form the top left rxr block of C by taking

  • the top left block of A times the top left block of B,
  • then adding the next block along the top of A times the next block down the left of B,
  • etc.

    • Write a function (C or Matlab, whichever is more comfortable) to perform matrix multiplication this way. Remember to include a "clean up" loop in case n/c or n/r is not an integer.

    Suppose n is fixed. How does the architecture of the computer affect how fast your function runs for different values of r and c?