Lab 4: Caches and Cache-Friendly Code

Programming Rules for Part 2

• Your code in trans.c must compile without warnings to receive credit.
• Your transpose function may not use recursion or any variant of malloc.
• Your transpose function may not modify array A. You may, however, do whatever you want with the contents of array B.
• You are allowed to define at most 12 local variables of type int per transpose function. This means 12 variables in scope at once. For example, the following code would be allowed:

  /* Note: function arguments are not counted as local variables */
  void func_ok(int x, int y) {
      int array1[8];
      if (x == y) {
          int array2[4];  // OK: 12 ints in scope
      } else {
          int array3[2];  // OK: 10 ints in scope
      }
  }

  But the following is not:

  void func_bad(int x, int y) {
      int array1[8];
      if (x == y) {
          int array2[2];  // OK: 10 ints in scope
          if (x > 0) {
              int array3[4];  // BAD: 14 ints in scope
                              // Even though this branch may not always run,
                              // the MAXIMUM number of local ints exceeds 12.
          }
      }
  }

  The reason for this restriction is that our testing code is not able to count references to the stack. We want you to limit your references to the stack and focus on the access patterns of the source and destination arrays.
• Your are permitted to use int arrays, but arrays DO count towards your 12 local ints. For example, if you have already declared 4 ints, you could declare an array of ints up to size 8.
• If you choose to use helper functions, you may not have more than 12 local variables on the stack at a time between your helper functions and your top level transpose function. For example, if your transpose declares 8 variables, and then you call a function which uses 4 variables, which calls another function which uses 2, you will have 14 variables on the stack, and you will be in violation of the rule.
• You are not allowed to side-step the previous rule by using any variables of type long or by using any bit tricks to store more than one value to a single variable.

Performance and Grading

We will evaluate the correctness and performance of your transpose_submit function on a cache with parameters s = 5 (index bits), E = 1 (associativity), k = 5 (offset bits) for 2 different-sized input matrices:

• 32 x 32 (M=32, N=32)
• 64 x 64 (M=64, N=64)

Your code must be functionally correct (i.e. produce the correct transposed matrix) to receive any performance points for a particular size. Your performance score for each matrix size scales linearly with the number of misses, m, up to some threshold:

• 32 x 32: 5 points if m ≤ 288, 0 points if m > 600
• 64 x 64: 5 points if m ≤ 1700, 0 points if m > 2400

Extra Credit

Extra credit will be awarded for code that results in fewer misses than the full score "baselines." For reference, there exist solutions with m as low as 259 (32 x 32) and 1052 (64 x 64).

Part 2 Testing

Transpose Testing (test-trans)

You can check the performance and correctness scores of your transpose function(s) by running test-trans, an executable generated by the given Makefile. Your final submission must go in the given transpose_submit function. However, we provide the ability to try out multiple implementations; see below for more details.

To test your code for a particular size:

$ make # run make each time you change your code
$ ./test-trans -M 32 -N 32

Function 0 (1 total)
Step 1: Validating and generating memory traces
Step 2: Evaluating performance (s=5, E=1, b=5)
func 0 (Transpose submission): hits:1766, misses:288, evictions:255

Summary for official submission (func 0): correctness=1 misses=288

The test program ran the solution function and printed out two pieces of information:

• The correctness of the solution. If 0, that means your function did not correctly compute the transposition of the matrix.
• The hit, miss and eviction counts. Your score is based only on the number of misses – lower is better.

To analyze where the cache hits and misses are coming from, you will need to examine saved trace files. test-trans saves the trace for the function i in the file trace.fi. To debug a particular function, simply run its trace through the reference simulator with the verbose option:

$ ./support/csim-ref -v -s 5 -E 1 -b 5 -t trace.f0
S 68312c,1 miss
L 683140,8 miss
L 683124,4 hit
L 683120,4 hit
L 603124,4 miss eviction
S 6431a0,4 miss
...

Each line denotes one or two memory accesses, using the following format:

operation address,size result

• The operation field denotes the type of memory access: "I" denotes an instruction load, "L" a data load, "S" a data store, and "M" a data modify (i.e., a data load followed by a data store). There is never a space before each "I". There is always a space before each "M", "L", and "S".
• The address field specifies a 64-bit hexadecimal memory address.
• The size field specifies the number of bytes accessed by the operation.
• The result field specifies the result of the memory access with regards to the cache.

Registering Multiple Transpose Functions

You can register up to 100 versions of the transpose function in your trans.c file for use in test-trans.c. Each transpose version has the following form:

/* Header comment */
char trans_simple_desc[] = "A simple transpose";
void trans_simple(int M, int N, int A[M][N], int B[N][M])
{
    /* your transpose code here */
}

To register a particular transpose function with the autograder, make a call in the registerFunctions routine in trans.c of the form:

registerTransFunction(trans_simple, trans_simple_desc);

At runtime, the autograder will evaluate each registered transpose function and print the results. Of course, one of the registered functions must be the transpose_submit function that you are submitting for credit:

registerTransFunction(transpose_submit, transpose_submit_desc);

See the default trans.c function for an example of how this works.

The following example has four different transpose functions registered and runs on a 32 x 32 matrix. Note that while it displays the results for each registered function, it still extracts the results for the official submission at the end.

$ make # run make each time you change your code
$ ./test-trans -M 32 -N 32
Step 1: Evaluating registered transpose funcs for correctness:
func 0 (Transpose submission): correctness: 1
func 1 (Simple row-wise scan transpose): correctness: 1
func 2 (column-wise scan transpose): correctness: 1
func 3 (using a zig-zag access pattern): correctness: 1
Step 2: Generating memory traces for registered transpose funcs.
Step 3: Evaluating performance of registered transpose funcs (s (Index Bits) = 5, E (Associativity) = 1, k (Offset Bits) = 5)
func 0 (Transpose submission): hits:1766, misses:288, evictions:255
func 1 (Simple row-wise scan transpose): hits:870, misses:1183, evictions:1151
func 2 (column-wise scan transpose): hits:870, misses:1183, evictions:1151
func 3 (using a zig-zag access pattern): hits:1076, misses:977, evictions:945
Summary for official submission (func 0): correctness=1 misses=288

Lab Score (grade_trans.py)

We have provided you with a driver program, called grade_trans.py, that performs an evaluation of your transpose code's correctness and performance for both matrix sizes – this is the same program your instructor will use to evaluate your submission! To run the driver, type:

$ make # run make each time you change your code
$ python3 grade_trans.py
Part B: Testing transpose function
Running ./test-trans -M 32 -N 32
Running ./test-trans -M 64 -N 64

Cache Lab summary:
                        Points   Max pts      Misses
Trans perf 32x32          5.00         5         288
Trans perf 64x64          5.00         5        1107
          Total points   10.00         1 

Rules Compliance (check_trans_vars)

As stated above, you will recieve NO POINTS for Part 2 if you violate the programming rules. To check for violations, run the following command:

$ ./check_trans_vars trans.c

If your code passes the checks, you will see the following:

$ ./check_trans_vars trans.c
Variables used by transpose_submit: 2
transpose_submit passes the programming rules checks.

If it fails, you will see something like this:

$ ./check_trans_vars trans.c
transpose_submit DOES NOT PASS the programming rules checks:
        - Maximum variable count exceeded (transpose_submit: 14)
        - Disallowed variable type(s) used: long

Resources

Cache Blocking

The cache blocking technique is introduced in Lecture 19 , so you can refer to those slides and recording. You can find different explanations in this textbook aside and this Intel post (using the term "Loop Blocking", instead). Here is an archived Intel post that may be useful too.

Cache Simulation

The cache simulator is available to help you get practice with and visualize different cache operations and mechanics. See the associated worksheet for more information.

Matrix Visualization

The matrix visualizer can help you visualize how matrices are laid out in memory, which may come in handy for Part 2. Just select the parameters of your matrix and you can hover over each matrix element and see its address.

The matrix visualizer purposely restricts you to small sizes to keep things digestible. If you'd like to see a more "realistic" visualization of the matrices for Part 2, see this image, which shows the last 2 bytes of the address of each cache block as they align to the 32x32 matricies. Red squares notate the start of a section that would fit in cache. Green lines divide individual integers, and black lines divide cache blocks.

Tips and Hints

Performance Tips

Struggling to reduce your misses? Consider the following:

• Only memory accesses to the heap are monitored. Just be careful not to break any programming rules!
• Since your transpose function is being evaluated on a direct-mapped cache, conflict misses are a potential problem. Think about the potential for conflict misses in your code, especially along the diagonal. Try to think of access patterns that will decrease the number of these conflict misses.

Programming Rules Tips

Algorithm breaking the programming rules? Consider the following:

• If you have variables specific to one case of an "if", you can declare the variable within that block and it will only count against your variable count for code in that part of the "if". Remember — you're only limited by the number of variables that exist at one time. You can declare variables within "if" statements and loops. This is especially helpful if you have different variables for the two matrix sizes.
• Use #define! These don't count against your variable total. You can declare constants using #define and use them wherever you want.
• Always use a constant integer size when declaring arrays. The variable rules checker will fail if you don't do this. For example, instead of this:

  int size = 5;
  int array[size]; // error: trans.c:24:9: Unable to process due to non-constant value "size" used in array declaration.
                   // Please use a constant integer as the array dimension.

  Do this:

  int array[5]; // OK!