The microbenchmark

(note: the code used to generate the data in this notebook and the data itself can be found on github.)

The microbenchmark that I used is quite simple. It allocates a chunk of memory, then issues memory requests to that memory. By varying the amount of memory allocated and the stride between each memory access, you can control the cache's effect. For instance, if the size of the allocated memory is less than or equal to the cache size, we would expect the entire array to fit in the cache and every access to hit in the cache, experiencing only the cache hit latency. Alternatively, if the allocated memory was larger than the cache, and we used a stride equal to the cache line size, we would expect every access to miss in the cache, experiencing the cache miss latency on every access.

Although the benchmark is simple, things are complicated by prefetching, multi-level caches, TLBs, replacement policies, etc. Some of these are relatively easy to overcome (we can trick the prefetcher by pointer chasing, for instance). Other things, like replacement policies other than LRU, cause the data to be more noisy or to not follow the model laid out by Saavedra et. al exactly.

In the data below, I've tried to explain as much as I can about why we see the data, but there are still some holes in my understanding.

Baseline data

This first set of data uses the GPU to initialize the data (i.e. the data is touched by the GPU before the test is performed). It also uses the default Linux allocator, which uses transparent huge pages (THP) in this case.

data = pd.read_csv(urlbase+'data-thp-gpu.csv', usecols=(4,5,6), skipinitialspace=True)
figure(figsize=(12,6.66))
title('Init on GPU with THP')
for i in range(12,33):
    plt(2**i, data=data)
legend(loc='upper right')
xscale('log', basex=2)
grid(b=True, which='major')
xlabel('stride')
ylabel('time (ns)')
annotTHP()
tight_layout()

Starting on the left (and with smaller inputs):

• The first array size which experiences L1 misses (the first teal line) is 2¹⁵
  • This implies that the L1 cache capacity is < 32 KB, likely 16 KB.
  • Since the latency changes from 300ns to 525ns, we can also infer that the L1 miss latency is 225ns. This may seem like a very high miss latency; however, it's not out of the realm of possibility for GPU caches. I've found similar numbers for both NVIDIA and AMD discrete GPUs.
  • Also, the stride at which the latency is a maximum for the 2¹⁵ line is 64 bytes, which implies a 64 byte line. The reason we know it's the line size is that until we stride at the line size or above, the cache misses are partially amortized by hitting multiple times within the same cache block.
• Next, the next array size (2¹⁶) seems to have a significantly different latency for each access.
  • I believe this is the L2 miss latency, which is much smaller than the L1 miss latency at only 50ns. I assume that this L2 miss latency is actually the DRAM latency. If this is the case, the 50ns is quite reasonable. In discrete GPUs, the DRAM latency is much higher, but 50ns is reasonable for DDR3.
  • However, I do not believe that the L2 cache is only 32 KB. It wouldn't make much sense to include if it was so small. What I believe is going on here (and I've yet to develop a test to confirm this hypothesis) is that the L2 has a 512 byte "line size", or as it's likely implemented, 8 banks and the banks are addressed by simple address slicing. If this is true, then the L2 is actually 256 KB, a much more reasonable size.
• Nothing else interesting happens until we get to arrays larger than 2²⁷. At this point, we start missing in another level of cache. It's likely that this "cache" is actually the TLB.
  • Since there is an increase in latency for 2²⁷ and it doesn't level off until 2²⁸, it is likely the TLB reach is between these two sizes (64 MB and 128 MB).
  • Looking at the 2²⁸ line, and the ones after it, we see that latency levels off after a stride of 2²¹ or 2 MB. Interestingly, this is the large page size for x86-64. Thus, it seems that the GPU is using huge pages... cool!
  • If we use this page size of 2 MB, then the 64 MB to 128 MB reach implies that the TLB has 32 to 64 entries. This is quite reasonable for a modern TLB. An interesting question is whether this TLB is local to the compute unit, or if it's shared between many compute units on the GPU. This could be the local TLB, or it could be the IOMMU TLB.
  • Finally, we can see that the TLB miss latency is quite large, almost 500ns. Again, this is quite reasonable, especially if we assume that a TLB miss will take 1-4 memory accesses. (Well, 1-3 in this case since the GPU is using 2 MB pages).

GPU data without THP

Next we are going to look at what happens with the same test if we disable THP. This forces the GPU to use 4 KB pages. Though, interestingly, looking at the data, the GPU uses 32 KB pages even though the underlying page size is 4 KB!

Let's look at the data. It's generated using exactly the same methods as before.

data = pd.read_csv(urlbase+'data-nothp-gpu.csv', usecols=(4,5,6), skipinitialspace=True)
figure(figsize=(12,6.66))
title('Init on GPU without THP')
for i in range(12,33):
    plt(2**i, data=data)
legend(loc='upper right')
xscale('log', basex=2)
grid(b=True, which='major')
xlabel('stride')
ylabel('time (ns)')
annotNoTHP()
tight_layout()

Most of this data is the same as when using THP. The main difference is that we can see TLB misses with a much small array than in the previous data and that there are two TLB "line sizes".

• Looking at the first level TLB, we see the line size is 32 KB. This actually isn't that strange of a "page" size. It's 8 4 KB pages, which happens to be the number of page translations that can fit in one 64 byte cache line. My hypothesis is that the GPU is using something like a sub-blocked TLB.
• Interestingly, this TLB seems huge (2048 32 KB entries), especially if we compare it to the TLB in the first data. Since it's so big, my guess is that it's at the IOMMU and shared by the whole GPU, not a per-CU TLB. Additionally, there may be more sub-blocking going on all the way up to the 2 MB page size. Sub-blocking up to 2 MB pages lines up with the previous THP data the best. If the used 2 MB super-blocks then it would have 64 entries, which lines up with the L1 TLB in the previous data (which we found to be 64-128 entries).
• Next, we again see the 2 MB page, but this time only for arrays larger than 512 MB. I find this quite strange that we didn't see this level of TLB in the previous data that had only 2 MB pages. It seems that this "L2 TLB", whatever it is, has an additional miss penalty not seen in the previous data. Assuming this TLB uses 2 MB pages, then it would have 256 entries.

I'm honestly not too sure what exactly is going on here. The data is pretty clear that there's two levels of TLB, but I'm not sure how these TLB levels relate to the TLB in the first set of data with 2 MB pages.

CPU first touch

Next, we're going to look at what happens when the GPU doesn't touch the data before the test is performed. For this test, I used the CPU to initialize the data and then performed the test on the GPU. Below we have the data both when THP is enabled and disabled. Since there aren't too many new data points in these two graphs I'll talk about them together below the graphs.

data = pd.read_csv(urlbase+'data-thp-cpu.csv', usecols=(4,5,6), skipinitialspace=True)
figure(figsize=(12,6.66))
title('Init on CPU with THP')
for i in range(12,33):
    plt(2**i, data=data)
legend(loc='upper right')
xscale('log', basex=2)
grid(b=True, which='major')
xlabel('stride')
ylabel('time (ns)')
annotTHP()
tight_layout()

data = pd.read_csv(urlbase+'data-nothp-cpu.csv', usecols=(4,5,6), skipinitialspace=True)
figure(figsize=(12,6.66))
title('Init on CPU without THP')
for i in range(12,33):
    plt(2**i, data=data)
legend(loc='upper right')
xscale('log', basex=2)
grid(b=True, which='major')
xlabel('stride')
ylabel('time (ns)')
annotNoTHP()
tight_layout()

The key difference between these two graphs and the first two (where the data was first initialized on the GPU) is for arrays of sizes 512 MB and above we see some pretty strange data. The way I interpret this data, and I may be totally wrong about this, is that the GPU caches are disabled. I believe this is true because of the latency seen using the word (4 byte) stride. Even in this case, when you would expect to get intra-block hits, the latency equal to the cache miss latency.

Although disabling the GPU caches really hurts performance for this microbenchmark, it may make sense for real applications. Maybe the runtime is somehow detecting that the data is written by the CPU and assumes that if the GPU wants up to date data that the highest performance option is to disable the caches (rather than rely on cache coherence).

I have considered other possibilities, like 1 GB pages, page faults, etc. But I can't come up with any other reason other than the above for this data.