CSE 160 Homework Assignment #3
Performance programming with matrix multiply
TO BE DONE IN TEAMS OF TWO
(15 points)

Due: Tuesday 10/28 at 9PM

Changelog

Introduction

In this assignment you'll implement the blocked matrix multiplication algorithm discussed in class, and carry out a set of experiments to assess the performance benefits of the algorithm compared with the unblocked algorithm, which is provided to you as A3.tgz.

You may use any machine you wish; you will know that you have reached the desired goal when performance of the blocked algorithm significantly outperforms (by at least a factor of 10) the unblocked algorithm. The provided code includes a microsecond timer, as well as verification code for a matrix multiplication problem with a known solution.

The Assignment

This assignment doesn't use pthreads, since your code will run on a single processor. Restructure the provided unblocked code to implement the blocked algorithm (Algorithm 3) described in the Demmel on-line reader. Be sure that your code is correct. Note that the provided code enables you to repeatedly execute matrix multiplication a designated number of times. This is necessary with smaller matrices, since it might not be possible to measure the running time reliably for a single matrix product.

Test your code for different values of N, repetition count, and blocking factor in order to build confidence in the correctness of your code. Note that, these values are input as positional command line arguments; see the code for the details.

Next, conduct a performance study. To do this, sweep over different values of N, starting, say, from 32 and working your way up in powers of 2 until the running time of the unblocked code takes about 15 or 20 seconds. Once you have done this, look at intermediate values in order to get a clearer picture of how performance changes with N and the blocking factor. To start with, let the blocking factor be N/2. You may reduce the blocking factor by halving it. Note the effect on performance. Is there a "sweet spot" (or spots) that minimize the running time for a fixed N?

Taking Timings

Use the provided Timer code that uses gettimeofday(). If you are working on a personal computer, shut down all open applications.

Take at least 3 timings for each combination of N and block size, and report the minimum timing. If you are having trouble getting consistent timings, especially if you are using ieng6 try running when the machine is quieter, repeat the runs several more times.

You'll need to use a large repetition count for smaller matrices say, 10⁴. As you decrease N, you'll need to figure out a schedule for decreasing the repetition count so that each run takes a second or two. As you increase N still further, you eventually set the repetition count to be one, and you will no longer be able to limit the running time to a second or two.

Once you have conducted your experiments, plot the comparative grind times for the blocked and unblocked algorithm. Why are the times comparable for smaller values of N? At what point do they diverge. Sample the values of N closely within the region where they diverge, and use this critical value of N to estimate highest level cache size of the machine. Remember, there are 3 arrays to be cached, A, B, and C.

Things you should turn in

Document your work in a well-written report which discusses your findings carefully. Your report should present a clear evaluation of the design of your code, including any bottlenecks in the implementation. Describe any special coding or tuned parameters. Provide pseudo-code listings for code you wrote. There is no need to provide pseudo-code for the provided unblocked matrix multiply code.

Provide all data you plotted in tabular form. This can exist as an appendix in your report.

Your report should cite any written works or software as appropriate in the text of the report. Citations should include any software you used that was written by someone else, or that was written by you for purposes other than this class.

As in the second assignment, run a suite of commands to identify the hardware and the environment you used to develop and run your code.

1. Identify the operating system: uname -a
2. Identify the machine you ran on: hostname
3. Identify your compiler and version number: g++ -v (If you aren’t using the Gnu C++ compiler, determine the command needed to generate the version information.)

Place all output from these commands in a file called config.out, e.g. by using the script command. If you know the hardware characteristics of your processor, that is, TLB, L1, L2, and (if present) L3 cache, list the information in the report, and cite the source, e.g. a URL.

As in the previous assignments, your turnin will consist of two parts. Turn in in a hard copy of your report in class on Thursday 10/30. Transmit your report electronically by the 9PM deadline on 10/28. Email a single archive file, e.g. .zip, .tgz, containing your writeup and source code. Be sure and delete all .o files and executables before creating the tar file. Email the archive file as an attachment to the following address:

Be sure to put the string cse160:A3 in the subject line and to use the email address above; not doing so may result in a penalty.

The name of your archive file should start with your login ID, e.g. baden.tgz. When your archive file is extracted, a new directory should be created with the name of your login ID. The directory should contain two subdirectories

At the top level of your directory there should be an ASCII file called README.txt, listing all the parts of your electronic submission. If you like, include a .html file called index.html at the top level. From there you can then link to a README file as well as the src and report directories.