Lab 1 — locality in a CPU

Out: 9/10/2007 Due:10/5/2007 ~~9/30/2007~~

In this lab we will use dense matrix-matrix multiplication to study the effects of locality on performance and power dissipation. Matrix multiplication is deceptively simple and actually offers many opportunities for optimization. We also learn about 3 tools that can help with architecture optimizations (performance counters, CACTI, and PIN).

You can use just about any computer to run this lab and instructions are provided for the linux??.ece.utexas.edu machines.

Emphasis and grading

This lab is about locality and matrix multiplication is used as a teaching example. The optimization possibilities for this application are almost endless, and it is not the intent that you try to explore them all. Rather, try to focus on those that are directly related to the teaching/learning goals of this class. Basically, effort placed in optimizations that are not locality optimizations will not be rewarded (in grading) as much as ideas related to locality, methodology, or tools introduced in this lab.

Grading will address all the specific questions that appear below as well as any additional comments or ideas you share.

We will grade using a 5-level scale (I expect the final class grades to be in the A — B range with more ‘A’s and ‘A-‘s than ‘B’s):

5	Truly remarkable work
4	Exceeded expectations (specifically with regards to learning goals
3	Met expectations
2	Did not meet all learning goals expected
1	Requires significant changes

Matrix multiplication

The following C code is the entire matrix multiplication program! We will only use the simple {$N^3$} algorithm in this lab.

#include <stdlib.h>
 
// define the matrix dimensions A is MxP, B is PxN, and C is MxN
#define M 512
#define N 512
#define P 512
 
// calculate C = AxB
// for each row of C
// for each column of C
      sum = 0.0f; // temporary value
// dot product of row from A and column from B
        sum += A[i][k]*B[k][j];
      }
      C[i][j] = sum;
    }
  }
}
 
// function to allocate a matrix on the heap
// creates an mXn matrix and returns the pointer.
//
// the matrices are in row-major order.
// assume some initialization of A and B
  // think of this as a library where A and B are
  // inputs in row-major format, and C is an output
  // in row-major.
Baseline matrix-matrix multiplication.

[$[Get Code]]

Part 1 — Optimizing Performance

In the first part of the lab we will try to improve the performance of the baseline version above on a uni-processor. Most of the performance to be gained is with locality optimizations, followed by converting the code to use modern processor’s short-vector SIMD units. We will focus on the locality part.

In order to improve performance we will need a good way to define and measure performance. We will use ‘GFLOPS’ (giga-FLOPS, billions of floating-point operations per second) as our measure of performance. To calculate the GFLOPS of our application we will need to measure the number of operations executed as well as the time spent in the calculation.

Measuring the number of operations in this case is very simple. All the computation occurs in line 15 and includes one addition and one multiplication in the inner-most loop, so the total number of computations is {$2 \times M \times N \times P$}. In general it is important to count the actual number of operations required by the algorithm when measuring performance and make sure not to include operations that were added as part of coding or optimization.

Measuring time is a bit more tricky because we cannot simply use the built-in OS time measurement because of accuracy issues. To allow more accurate measurements processors provide performance counters in the hardware that measure various events, such as cycles, instructions retired, branches, cache accesses, … We will use the performance counters to measure the number of cycles required by our application.

There are many measurement packages that use the performance-counters, and one of the best and best supported is PAPI developed at the University of Tennessee Knoxville. Unfortunately, using PAPI requires a kernel patch to linux, so we will use a more the limited interface shown here. You don’t have to read anything on this link, just follow the steps below.

Step 1

Download and unzip http://www.agner.org/optimize/testp.zip, then unzip TSCUni.zip and read TSCUni.txt. Usage is very simple and you simply insert the routine you want to time into TSCTest.cpp after the line containing:

// ###################### Test code here ######################

[$[Get Code]]

When using this tool, the #defines and matmul function itself should go towards the top of TSCTest.cpp and only main() (without the return statement) needs to be placed inside the test code.

Notice that when you run the timing harness you get several measurement results and all are in cycles.

Question 1

How many GFLOPS did the basic version achieve on your test machine? Please use three different matrix sizes: M=N=P=32 , M=N=P=512, and M=N=P=2048.

Things to address: What machine did you use? Why are several measurements taken? Which one(s) should you report? How did you convert from cycles to seconds and why did you do it that way?

Was there any significant difference between the two matrix sizes in terms of the trends in the timings of each measurement? Can you make them behave the same way with regards to timing variance? Should you do it? Please include any code you used.

Step 2

Now try to improve locality and hence performance. Please think of optimizing registers as well as the memory hierarchy. Try both cache-aware and cache-oblivious methods. You may want to consider larger datasets for this step of the lab to test your ideas.

The A, B, and C matrix formats are all row-major (even though they are just malloced for simplicity (think of this as a library interface). Anything you do to manipulate A and B should be counted for time and accesses (but not count towards instruction count for performance).

Question 2

What techniques that you used worked well and what didn’t make much of a difference? Why? Please address the different locality mechanisms in hardware when answering this question and document failed and successful techniques (only correct ones of course).

Part 2 — Estimating Power

As architects it is important for us to understand both the software costs (performance) and the hardware costs. Hardware costs are typically categorized as die area, complexity and power/energy. There are other costs to consider such as reliability, features, and so forth that are usually set by the usage model. We will only look at power/energy in this lab.

We discussed the effects locality has on power and energy in class. We will not attempt to develop a power model based on “first principles” and will instead use the excellent CACTI tool from HP Labs. CACTI models the hardware costs of caches and SRAMs and has an easy to use web interface: http://quid.hpl.hp.com:9081/cacti/.

To estimate the power and energy consumed by the matrix multiplication application we need to know both how much energy each access to a locality level takes and how many accesses are actually made to each level. To determine this we could use the hardware performance counters to measure cache accesses, but then we would not be able to explore the behavior as we change cache sizes. Therefore, we will use a simple cache simulator built on top of PIN, which is a dynamic hardware instrumentation tool.

Step 3

Download the PIN tool from http://rogue.colorado.edu/Wikipin/index.php/Downloads and untar it (you can use /tmp if you don’t have much quota left). The SimpleExamples directory contains dcache.cpp, which implements a one-level data cache. We want to have a 2-level cache model, which you can easily create by some artful copying and pasting. This is a good opportunity to learn how to modify existing tools to achieve your goals. Make sure you have some way of changing the cache parameters and sizes (you can just replicate the parameters of the L1 cache). For the cache model, please assume both caches are read- and write-allocate, write-back, and inclusive (this means allocate a line on any read or write miss, allocate in L2 on an L1 miss, and assume that a write-back from L1 never misses in L2 and doesn’t change its LRU). Note that the PIN tool will not work on some of the Linux distributions like the Latest 7.0.4 UBUNTU and OpenSuSe 10.2 but it works on RedHat Fedora core. The message you will get is this error message: “Can not load shared library libm.so.6”.

Once you have the two level model, verify it by running the following steps from within the SimpleExamples directory. Set the L1 parameters to (size=32KB, associativity=4, blcck size=16) and the L2 to (size=2048KB, associativity=16,block size=32).

make dcache
wget http://www.ece.utexas.edu/~merez/EE382V_Fa07/test_cache.c
wget http://www.ece.utexas.edu/~merez/EE382V_Fa07/test_cache.out
gcc -O3 test_cache.c -o test_cache
../Bin/pin -t dcache -- ./test_cache
diff dcache.out test_cache.out

[$[Get Code]]

If there are small differences in the numbers ignore them, but if not, one of us made a mistake.

You’re now ready to measure the locality in your matrix multiplication code. Just run you PIN dcache tool as for test_cache, but use your matrix multiplication program instead.

Question 3

Please fill in the table below with the number of references made to each locality level. For registers, just look at the number of accesses required for the actual computation, which you can calculate based on the code. Please use the exact implementations you did in the previous steps. For all the runs, please set the L1 associativity to 4 and the L2 associativity to 16. Some of these runs may take an hour or so.

To find out the cache parameters of the processor you are using just search for the specific model number on the web. Your processor model appears in Control Panel/System on Windows machines and in /proc/cpuinfo (text file) on Linux machines.

N=M=P	L1 Size	L1 Block	L2 Size	L2 Block	Original			Cache Aware			Cache Oblivious
					Regs	L1	L2	Regs	L1	L2	Regs	L1	L2
2048	Your processor params
2048	32	64	1024	128
512	8	32	256	64
512	1	32	128	64

Why do you think the results differ between the configurations and between the cache-aware and cache-oblivious implementation? Can you make the cache-aware and cache-oblivious behave similarly? If yes, please fill in another table for the new version(s).

Step 4

In this step we will use CACTI to estimate the potential power savings of locality optimizations. Use http://quid.hpl.hp.com:9081/cacti/ to fill in the table below. For registers, use a configuration of an SRAM of 128 entries of 32 bits each (this is not accurate, but gives a good sense of things). Use th e Pure RAM interface of http://quid.hpl.hp.com:9082/cacti/ for 32-bit registers with 1 input and one output port at 350K. Use 0.07 (70 for the register interface) as the technology, which is similar to the 65nm technology in use today.

	Size	Ways	Block	Access Energy
Your L1
Your L2
Registers	512	1	4
	32K	4	32
	8K	4	32
	1K	4	32
	1024K	16	64
	256K	16	64
	128K	16	64

Question 4

Now combine steps 3 and 4 together and calculate the energy savings in the table below. Fill in the cache-aware and cache-oblivious columns as fraction of original. What conclusions can you draw?

N=M=P	L1 Size	L1 Block	L2 Size	L2 Block
2048	Your processor params
2048	32	64	1024	128
512	8	32	256	64
512	1	32	128	64

Question 5

What is the reduction in power consumption (think about this carefully)?

Part 3 — Analytical Modeling

In the first two parts we looked at 2 of the 4 most common ways of doing architecture research: measurements on real machines where we have limited or no control over parameters, and simulation, which can be slow and does not scale well. In this part we’ll look at analytical modeling, which can be very useful to evaluate trends and look at scaling beyond the capabilities of simulators. The final common technique is prototyping.

Question 6

Derive formulae for the locality of the original, cache-aware, and cache-oblivious implementations for one level of locality. The formulae should represent what fraction of accesses (access = operand read or write) are serviced by a local store of a given capacity. Assume the matrix is much larger than the storage capacity.

Draw a graph of the locality of each of the three implementations as the amount of storage grows.

Question 7

Can you extend your model to a storage hierarchy (e.g., registers, L1, L2, memory)?