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.
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.
