()

Lab 1 Review

Question 1 Breakdown

Question 1 dealt with the execution of the matrix multiply code using TSCTest.cpp to measure clock cycles.

Why take several measurements?

  • Because we are running on shared machines and OS has interrupts.
  • It was unexpected that the machines were more heavily loaded than when Mattan ran the tests, resulting in more outside influence on the test runs.

Which measurements should you report? minimum, maximum, or mean?

  • Minimum or mean were acceptable if reasonable explanation was given.
  • The minimum represents a measurement with the least interference from the OS and other users.
  • The mean represents typical performance on a realistic machine that has OS interrupts and\or other users.

Why does the 32X32 matrix problem size perform much worse on the first measurement?

  • The first run warms up the cache for the runs after it; so, the first run does not benefit from having a warmed up cache.

How can you make the runs the same?

  1. Throw out the first run because it performs worse without a warmed up cache.
  2. Reallocate the cache memory each time. Several groups did this to begin with and did not see the difference between the 1st and subsequent runs.
  3. Flush the cache each run. This strategy is tricky to implement and requires use of explicit cache flush instructions to ensure a full flush.

Should you do it (make them the same)?

  • It depends on the usage because you could have a case where you rerun matrix multiplies several times with only a few values changed, so warming up the cache is a good and relevant thing to do.

Optimization

The following optimizations were done by the class overall:

  • registers
  • blocking
  • transpose B
  • transpose 1 block at a time
  • use SSE to get better register locality
  • prefetching + SWP
  • copying blocks

Register and blocking optimization were the most common and best optimizations to use. SSE was a good optimization, and transposing one block was unexpectedly good (more on this later).

Blocking Technique

The best technique was to block twice, once for the L1 cache and once for the L2 cache (and a third time for registers as explained below).

  • This minimizes misses from both caches.
  • L1 locality is important but small (~16KB).
  • L2 is 1MB, so it can hold more blocks.
  • Hierarchical blocking makes the transpose optimization irrelevant because ordering doesn’t matter when blocking.
  • Doing 2b3 computations results in 2b2 misses for bringing in blocks.
  • The transpose optimization unexpectedly had good performance, but the better performance occurred when hierarchical blocking was not used.

Register Optimization Techniques

  • Done explicitly when using SSE.
  • Unroll loops 4–32 iterations. Mattan expected an explanation why a specific number of iterations was chosen.
  • Explicitly optimize through SSE.
  • Basically another level of blocking but cannot do explicitly because of the compiler.

PIN Question

  • PIN’s dcache counts cache hits and misses. It was modified to have two levels of cache.
  • Correction to dcache: Multi-line accesses were only counted as one access total. To be correct, multi-line accesses should count one access for each line accessed.
  • Improvement to dcache: Dirty lines evicted from the L1 cache should go to the L2 cache. This affects energy consumption.

Counting Register Accesses

  • Method 1: Look at the assembly code.
  • Method 2: Estimate based on source code (C code).
  • Many groups had a large disparity in number of register accesses between algorithms, which was not expected.
  • The number of register accesses should not have been less than the number of computations.

Algorithm Trend in PIN

Cache oblivious should behave better when changing cache size than cache aware (that doesn’t change block size).

CACTI Energy

  • You should have explained what number you chose and why (from CACTI energy results).
  • Blocking should give an energy reduction.
  • Leakage energy goes down because execution time goes down.
  • Shorter execution time leads to more power consumption.

Analytical Modeling

You should have a model to compare with measurements to see if they are consistent. Inconsistencies means something went wrong, either with the model or the measurements.

{$ \begin{align} Locality &= \frac {number\_of\_accesses\_required\_for\_computation} {number\_of\_words\_from\_a\_level\_of\_storage} \end{align} $}

c += a * b breaks down into:

  • t = a * b
  • c = c + t
  • This results in 6n3 accesses.

{$ \begin{align} hit\_rate &= 1 - miss\_rate \end{align} $}, (miss rate is easier to compute)

{$ \begin{align} accesses &= 6b^2N \left(\frac {N^2}{b^2}\right) \end{align} $} across the blocks of C, each of size b2.

{$ \begin{align} misses &= (b^2 + 2bN) \left(\frac {N^2}{b^2}\right) \end{align} $}

To minimize misses, a small b should be used with a small cache and a large b should be use with a large cache.

{$ \begin{align} 3b^2 &= Z \end{align} $}, where Z is the cache size

If you consider line size, you just divide one of the factor of b misses by L.

Extension to multilevel memory hierarchy

  • The equation is the same.
  • The only thing that changes is the number of accesses to a level, which are the misses from the next higher level of memory.

{$ \begin{align} b &= \sqrt {\frac {Z}{3}} \end{align} $}

Therefore, {$ \begin{align} \frac {Z}{3} + 2 \left(\sqrt{\frac {Z}{b}}\right) \left(\frac {N^3}{\frac {Z}{3}}\right) \end{align} $}.

GPU Control Flow

See Slides for Examples

  • Think of threads as lanes of vector.
  • Masking allows you to enable/disable an instruction for a specific lane.
  • Masking allows control flow to diverge.

Control Flow Divergence

  • We would like to see all lanes executing in parallel.
  • However, they will not if control diverges.
  • The example in the slides shows that threads that satisfy the conditions of an “if” will execute in parallel. This example has execution that is between completely serial and fully parallel.

Mask Stack Enables Divergence

  • The mask stack allows nesting of control statements by saving enable masks when a control statement is encountered and restoring the saved mask when leaving the control statement body.
  • Initially, all lanes are enabled (all bits of the mask are equal to 1) and the mask stack is empty.
  • Lanes with a 1 in the mask get to execute, and lanes with a 0 don’t.
  • The slides have an animated example of how enable masks are saved and restored using the mask stack.
  • The stack and the enable mask are maintained by hardware.
  • Each SM has its own stack that can handle 4 deep nesting (i.e. the stack is 4 deep).
  • More than 4 deep nesting will probably not run.

Predication

  • Predicates can replace branches like “if” statements, by enabling/disabling specific instructions based on a conditional value calculated in each lane.
    • This is similar to explicitly calculating the enable mask with software.
  • Using predication will result in the same threads executing as divergence, except that predication executes both paths of branches.
    • Divergence only executes the chosen path, so if all lanes happen to go one way, you won’t waste computation by doing the other path.
  • The example in the slides shows how to do the same branching with predicates as with control divergence.