8
$\begingroup$

In "LU, QR and Cholesky Factorizations using Vector Capabilities of GPUs", by Vasily Volkov and James Demmel, there is an interesting way to interpret the latencies, line sizes, and page sizes of a cache from a graph like this:

Figure 1 from the paper

Apparently, the line size is where the the cache begins to plateau (about 32 bytes in this example). Where did that come from?

And how do we know that the page size is where the second plateau begins for global memory?

Furthermore, why do the latencies eventually go down with a large enough stride length? Shouldn't they keep increasing?

If this actually works, and it seems to, that'd be awesome because we can get a lot of undocumented data about the cache of a GPU.

$\endgroup$
  • $\begingroup$ John, I hope I've answered your question helpfully. Could you please edit your question to give it a slightly more meaningful/searchable title, as well as give a proper reference and citation to the paper you are citing? It is considered fairly poor form in science and mathematics (and this site) to use an image from a paper without listing the authors and title. $\endgroup$ – Aron Ahmadia Apr 24 '13 at 13:16
8
$\begingroup$

If this actually works, and it seems to, that'd be awesome because we can get a lot of undocumented data about the cache of a GPU.

A frustrating aspect of high performance computing research is digging through all the undocumented instruction sets and architecture features when trying to tune code. In HPC, the proof is in the benchmark, whether it is High Performance Linpack or STREAMS. I'm not sure this is "awesome", but it is definitely how high performance processing units are assessed and evaluated.

Apparently, the line size is where the the cache begins to plateau (about 32 bytes in this example). Where did that come from?

You seem to be familiar with the performance concepts of the cache hierarchy, described as the "memory mountain" in Bryant and O'Hallaron's Computer Systems: A Programmer's Perspective, but your question indicates a lack of deep understanding of how each level of cache itself works.

memory mountain

Recall that a cache contains "lines" of data, that is strips of contiguous memory that are harmonized with a memory location somewhere in the main store. When accessing memory within a line, we have a cache "hit", and the latency associated with retrieving this memory is called the latency for that particular cache. For example a 10 cycle L1 cache latency indicates that every time the memory address requested is already in one of the L1 cache lines, we will expect to retrieve it in 10 cycles.

As you can see from the description of the pointer chasing benchmark, it takes strides of a fixed length through memory. NB: This benchmark would NOT work as expected in the many modern CPUs that feature "stream-detecting" prefetch units that do not behave like simple caches.

It makes sense then, that the first noticeable performance plateau (starting from stride 1), is a stride that gets no reuse from previous cache misses. How long does a stride have to be before it steps completely past the previously retrieved cache line? The length of the cache line!

And how do we know that the page size is where the second plateau begins for global memory?

Similarly, the next plateau of stepping beyond reuse will be when the memory page managed by the operating system has to be swapped with each memory access. The memory page size, unlike cache line size, is normally a parameter that can be set or managed by the programmer.

Furthermore, why do the latencies eventually go down with a large enough stride length? Shouldn't they keep increasing

This is definitely the most interesting part of your question, and it explains how the authors postulate the cache structure (associativity and number of sets) based on the information they have previously gleaned (size of cache lines) and the size of the working set of data they are striding over. Recall from the experimental setup that the strides "wrap around" the array. For a large enough stride, the total amount of array data that needs to be held in the cache (the so-called working set), is smaller because more of the data in the array is being skipped. To illustrate this, you can imagine a person continuously running up and down a set of stairs, only taking every 4th step. This person is touching less total steps than somebody taking every 2 steps. This idea is somewhat awkwardly stated in the paper:

When the stride is very large, working set decreases until it again fits in the cache, this time producing conflict misses if cache is not fully associative.

As Bill Barth mentions in his answer, the authors state how they make these calculations in the paper:

The data in Fig. 1 suggests a fully associative 16-entry TLB (no TLB overhead for 128MB array, 8MB stride), a 20-way set associative L1 cache (20KB array at 1KB stride fits in L1), and a 24-way set associative L2 cache (back to L2 hit latency for 768KB array, 32KB stride). These are the effective numbers and the real implementation might be different. Six 4-way set-associative L2 caches match this data as well.

$\endgroup$
0
$\begingroup$

I'd say that the paragraph on page 3 that begins "A larger latency indicates more cache misses." explains most of what you're asking pretty well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.