Increasing cache line size when cache and RAM don't work asynchrounsly

Question

I want to improve a processor design. It has a simple directly mapped cache, and I want to improve the hit rate. I've been working on increasing the cache line size from one data word to four, but since all accesses to the cache and RAM are currently blocking (I mean that the operation of the whole CPU is blocked when it's waiting for a data read or write), I think that I am merely shifting the delay that is needed to access the RAM to the moment that any data in the same cacheline is needed. If I am correct, this won't make the processor execute any faster (and probably only slower, since more data is transferred between cache and RAM).

Is this the case or am I overlooking something?

Answer 1

By not decoupling the activity of the memory from the activity of the CPU, you're throwing away most of the benefit of having a cache.

But based on how you've described your system so far, it sounds like your analysis is correct: Increasing the line size will in effect prefetch some of the data, but this will not result in any performance gain. In fact, it could result in a slight performance loss on those occasions when the prefetched data is never actually used — the time spent fetching it was simply wasted.

Answer 2

It is not clear to be whether you are thinking about going from an N x 1 word direct-mapped cache to a (for instance) N/2 x 2 word DM or to a N x 2 word DM cache. The first might improve sequential access a little, because the second word in a line acts as a prefetch-buffer. The second alternative will improve the hit rate significantly, but mainly because the cache size has been doubled.

Answer 3

The performance benefit of a larger cache block size depends on the bandwidth and latency of main memory and the workload. If memory latency and bandwidth are relatively high (e.g., the first word is available in 8 processor cycles and an additional word every cycle), then if the workload is using even half of the cache block before it is evicted then a four-word block will increase performance (stalling only for 11 cycles instead of 16). (Since many memory technologies have burst constraints, the benefit might be less if the memory controller has a buffer [so sequential accesses might hit in the buffer, not suffering the full memory access penalty] or more if the misses are to different chunks of memory and using the full burst increases effective memory bandwidth].)

If the cache is writeback, the extra cost of eviction must be considered. For example, if 50% of the words are dirty, then the average stall (for the two accesses that on average hit in the 4-word block) would change from 16 cycles to 20 cycles and from 11 cycles to 19.25 cycles (75% of the blocks would be dirty since half of the words used are dirty and half of the words in a cache line are used).

A writeback cache with single-word blocks would also not need to read the memory for whole-word writes on a cache miss.

(Writethrough no-allocate has some advantages for direct-mapped caches, if there is a write buffer. Combining a write buffer and victim cache may be useful.)

In a direct mapped cache, increasing the block size will also increase the conflict miss rate.How significant this will be depends on the workload (and even on the mapping of data).

Other possible cache improvements include providing a victim cache (effectively a tiny L2 cache), using higher associativity (way prediction might be used to provide direct-mapped speed on correct predictions), and providing a prefetch buffer. If memory latency is significant, then there do not have to be many hits in a victim cache or prefetch buffer to compensate for delaying memory access. (Speculatively accessing memory on a miss before checking the victim cache/prefetch buffer would reduce latency for misses in these auxiliary caches, but it could increase latency when a victim cache hit is followed immediately by a victim cache miss since the second access might have to wait for the first to-be-discarded memory access completes before starting its own.)

Another possibility to consider is specialized caches. For example, if stack accesses can be filtered out from the rest of the data cache, then conflict misses would be reduced while keeping the simplicity of direct mapped caches.

Incidentally, some forms of way prediction benefit from larger-than-word cache blocks because they can exploit the locality of reference.

Answer 4

The biggest advantage to having a larger cache-line size is that the complexity of a cache controller is often related primarily to the size of the tag buffer, which is in turn controlled by the number of lines. Doubling the size of each line thus doubles the amount of information that can be cached with a given size tag buffer. Were it not for cost, doubling the size of each cache line would often be inferior to having twice as many cache lines. If, however, quadrupling the size of each cache line (but keeping the same number) would cost the same as doubling the number of them (but keeping the same size), it's possible that the former would offer more "bang for the buck".

In general, if one is trying to get good performance from larger cache lines, one should have a couple bit for each addressable unit within a word, indicating whether that unit is empty, present and clean (matches what's in RAM), or present and dirty (only applicable for write-back caches). If any cache lines are not completely filled it may be useful to fetch their contents from RAM at times when the memory bus would otherwise be idle, but fetches the CPU is interested in should be given priority over those it isn't.

Incidentally, one advantage of write-through caches versus write-back is that it's possible to have any number of devices that have write-through caches share the bus without any code having to know about anybody's caches; all that's necessary to maintain coherency is logic to invalidate any lines that are hit by outside accesses. By contrast, when using a writeback cache it will be necessary to have devices keep track of that pieces of data are held in other devices' caches, to ensure that every device which has a block in its cache will get notified if someone else modifies it.

Answer 5

increasing the cache line size from one data word to four ... merely shifting the delay that is needed to access the RAM to the moment that any data in the same cacheline is needed. ... this won't make the processor execute any faster (and probably only slower, since more data is transferred between cache and RAM).

When the processor doesn't need the "extra" data fetched, then you are right; the time spent fetching that extra data is wasted, making the processor slower.

However, if the processor does need the "extra" data fetched, there are several ways larger cache lines can make the processor faster (with a fixed amount of data in the cache).

Any particular benchmark program, when repeatedly tested using a variety of cache line sizes (and a fixed amount of data in the cache), will give you some particular cache line size that is the optimum for that particular benchmark program -- but alas, different benchmark programs have different optimum cache line sizes. Programs that read bytes quasi-randomly, like ARC4, typically prefer shorter cache lines. Programs that read large blocks of data more-or-less sequentially typically prefer larger cache lines. It's a tradeoff.

Reading the same data in less time

• All DRAM and most other memory are faster reading data sequentially than random reads. If the CPU needs to read byte 1000 now, then byte 7007, and then 1001, even though you still have the same number of read memory cycles no matter how you shuffle the reads around, it often takes less wall-clock time to (a) read bytes 1000 and 1001 back-to-back in some sequential mode and then 7007 than it does to (b) do random reads.

• If you have a narrow memory data bus that requires several memory cycles to fill a cache line, a smart cache can read the desired byte from memory first, forward that to the CPU, and then fill in the rest of the cache line with "extra" data. The first read takes the same time as a small-cache-line system. In cases where the CPU can run entirely out of cache in parallel with the cache loading, a later read of the prefetched data is faster.

More data in the same amount of time

If you have or can change to a wide memory data bus ( for example, all Intel processors that fit the LGA-2011 Socket have 256 data pins, connecting to 256 data lines on the motherboard -- LGA-2011 Socket datasheet, section 6.1)

• If you can read a large cache line all at once, it takes the same amount of time to read that entire cache line as it does to read a single byte. So you might as well cache the full wide cache line, since it runs no slower even in the worst case, because occasionally the CPU may need some of that "extra" data later and then it doesn't need to wait.
• If you can write a large cache line all at once, and you use a write-back cache, it takes the same amount of time to write that wide cache line as it does to write a single byte or a full register. So you might as well use a wide cache line, since it runs no slower in the worst case, because occasionally the wide cache can "combine writes" and write out the full cache line all at once in one memory cycle rather than in pieces across 2 or more separate memory cycles.

Reading less data

• As Wouter van Ooijen pointed out, if you are actually increasing the amount of data in your cache by keeping the same tag bits but increasing the cache line size, that tends to increase the hit rate, making the system faster in almost all cases.