0
$\begingroup$

Assuming we have a single-level (L1) cache and main memory, what are some of the advantages and disadvantages of having a larger cache block size (considering average memory access time).

The only ones I can think of are that a larger block size could increase the hit rate when adjacent memory locations are accessed, i.e. good for spatial locality. I can't think of any other advantages; are there?

As for disadvantages, I assume that having a larger block size increases the cache size, thereby increasing cost (since L1 cache is expensive), but I can't see any disadvantages relating to average memory access time. Are there?

$\endgroup$
2
$\begingroup$

An increased block size is indeed good for spacial locality.

On the other hand, a large block size increases the possibility of fragmentation and false sharing (in multiprocessor system).

Another way of thinking about this problem is if your cache size is fixed (based on cost, etc.), and you are changing the block size. In this case, as you increase your cache block size, accessing adjacent memory locations will have more hits (spacial locality), but there is a disadvantage considering temporal locality. Consider the extreme case, in which the cache has one block. Of course, this would be good for spacial locality, but it is terrible for a program repeatedly accessing two memory locations that are at least one full block size away from each other. The cache will miss every time.

EDIT

Consider this: you have a process with data in consecutive memory locations "A" through "H" of size "1." You have a warm cache of size "4" (ignoring compulsory misses, the misses/repeat below are average case) and an LRU cache replacement policy.

Let the cache block size be 4 (the "largest" block size case).

  • For repeated, in-order memory accesses A-H, this cache has 2 misses/repeat.
  • For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 4 misses/repeat.
  • For repeated, out-of-order memory accesses A, B, E, F, this cache has 2 misses/repeat.
  • For repeated, random memory accesses A, E, B, F, this cache has 4 misses/repeat.

Let the cache block size be 1 (the "smallest" block size case).

  • For repeated, in-order memory accesses A-H, this cache has 8 misses/repeat.
  • For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 8 misses/repeat.
  • For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
  • For repeated, random memory accesses A, E, B, F, this cache has 0 misses/repeat.

Let the cache block size be 2 (the "optimal" block size case).

  • For repeated, in-order memory accesses A-H, this cache has 4 misses/repeat.
  • For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 4 misses/repeat.
  • For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
  • For repeated, random memory accesses A, E, B, F, this cache has 2 misses/repeat.

The "largest" block size case is best for repeated, in-order memory accesses (best for spacial locality) and worst for repeated, random memory accesses (worst for temporal locality).

The "smallest" block size case is worst for repeated, in-order memory accesses (worst for spacial locality) and best for repeated, random memory accesses (best for temporal locality). It is good for out-of-order memory accesses, depending on the size of the working set.

The "optimal" block size case is good for repeated, in-order memory accesses and good for repeated, random memory accesses, but it is not the "best" for either case.

$\endgroup$
  • $\begingroup$ wouldn't that also be the case if the blocks were normal size, with the main difference being that smaller blocks have a smaller miss penalty $\endgroup$ – dmnte May 16 '16 at 16:08
  • $\begingroup$ What do you mean by "that?" "Larger" block sizes suffer from an increased possibility of fragmentation and false sharing, and they are (relative to a "smaller" block sizes) bad for temporal locality (assuming a fixed cache size). $\endgroup$ – user50991 May 16 '16 at 16:42
  • $\begingroup$ I have edited my answer to include a simple example. $\endgroup$ – user50991 May 16 '16 at 18:21
1
$\begingroup$

Increasing the cache line size while keeping the number of lines constant increases the cache size at massively increased cost. Not something I'd count as disadvantage, you get what you pay for.

I'd assume a fixed cache size, therefore fewer lines. Which is bad if cache lines are only partially used.

$\endgroup$
1
$\begingroup$

Advantages

The advantages of larger block size include: smaller tag storage (or larger cache capacity for a given tag storage budget), greater bandwidth efficiency, memory error correction code efficiency, potentially improved way prediction/memoization, potentially larger access bandwidth, effective prefetching under sufficient spatial locality in the reference stream, and reduced coherence directory overhead (and potentially reduced coherence traffic overhead).

Smaller tags (doubling block size halves the number of tags and removes one bit per tag) can be a significant consideration if tag access latency or storage capacity is a significant concern. In the past (and for huge off-chip caches) greatly reducing the number of tags can make the difference between fitting the tags on chip (with latency and pin-count benefits) and having tags off-chip. Larger cache size (under constrained tag storage) and lower tag access latency have obvious benefits for average memory access time. (Obviously, at extremely small block sizes, the total storage overhead for tags may noticeably impact data capacity.)

(The size of an off-chip cache could also be chosen after processor chip manufacture with little additional hardware cost in the processor chip, previously not uncommon for off-chip L2 caches. Incidentally, doubling block size would also allow doubling the cacheable memory address space with the same tags.)

Greater bandwidth efficiency comes from knowing that a larger chunk of memory will be retrieved. With a given DRAM burst length, the size of an access constraints the width of the interface. (An implementation could always fetch the adjacent cache block of data to gain the advantage for reads at a lower capacity cost, storing such in a small prefetch buffer. Writeback would be more complicated but they are less common and writeback bandwidth constrained workloads would tend to have spatial locality that could be exploited by checking for adjacent blocks.)

ECC encoding is more efficient given a larger block size. While this would not effect the L1 overhead since L1 would handle sub-block writes, the overhead in memory for a given amount of correction would be lower. Fetch size can also impact the practicality of chip-scale redudancy (e.g., IBM's ChipKill). A wider interface can use more DRAM chips with the same commodity bit width and burst length, reducing the overhead to provide a given level of correction even when an entire DRAM chip is unreliable because the fraction of information coming from one chip is less. Memory ECC encoding is typically over chunks smaller than blocks, but extending the encoding beyond fetch units is more complex and adds overhead (in theory, information required for correction could be shared over more than one chunk, requiring writebacks to have larger granularity).

A larger block size can also improve way prediction accuracy by reducing choice (all chunks within a cache block that would be separate cache blocks with a smaller block size are in the same way by definition) and exposing greater spatial locality (this improves warm-up and hit rate in some predictors). For partial virtual tag way predictors, larger block sizes increase the number of tag bits available for a given storage budget (which is constrained by latency), increasing accuracy. Way prediction can provide lower access latency. Way memoization for streaming accesses (most instruction cache accesses with modest fetch width and a significant number of data accesses) will be available for more accesses before the way changes.

Larger block size also facilitates higher access bandwidth by facilitating a larger number of banks within the same cache block. By using what is effectively single-cycle tag memoization, any banks within a block can supply data with only a single tag check; a larger block increases the chance that more than one access will be within the block. This does not decrease the latency of an individual access but allows more accesses to be started earlier, reducing the effective average memory access time.

The advantage of effective prefetching under adequate spatial locality of access is the commonly presented advantage. This advantage is reduced given prefetching which can dynamically exploit spatial locality when present without the storage overhead of larger blocks.

The storage overhead for directory-based coherence is also reduced with a larger block size. Full directories store the coherence state for each block, often by tracking it for each memory block, so using a larger block obviously reduces the relative overhead. Similarly, caching directory entries becomes more effective. (Coherence traffic may also be reduced due to spatial locality. As with prefetching, smaller blocks can be used while dynamically choosing larger coherence requests to reduce the number of requests on the network. False sharing increases coherence traffic.)

(Software invalidation of large cacheable regions may also be faster with larger blocks as fewer blocks need to be explicity invalidated.)

Disadvantages

The disadvantages of larger block size include: wasted bandwidth and storage under lower spatial locality, false sharing issues, high latency if early use is not supported, and higher conflict rate.

Memory bandwidth is wasted when data that is fetched is not used and when data that was not modified is written back to memory (or unnecessarily fetched under read for ownership). With a larger block size, both of these are more likely to occur because spatial locality of accesses is limited. Cache capacity is wasted when data is fetched but not used (for reasonable size blocks, tag storage is much less than data storage, so increased tag overhead with small blocks is generally not significant in terms of total storage capacity).

Under invalidation-based coherence protocols, cache blocks are invalidated when a write is made anywhere with the block by another agent. With larger blocks, more of the block will be invalidated. This false sharing is effectively an expression of limits of spatial locality of writes in a multithread context. This issue can be reduce using sectored cache blocks so that only the sector is invalidated. While traditional sectoring would waste capacity when a significant number of sub-blocks are invalid, larger cache blocks with sectoring may be a good choice. (Sectoring can also facilitate software compatibility when cache block size was exposed.) In theory, instruction and data cache false sharing is also possible, though writes to active code space are discouraged in modern high performance systems.

If the entire cache block must be loaded before any values from it are used, then a larger cache block (with constant bandwidth) will increase miss latency. (In theory, if multiple cache blocks could be fetched from memory in parallel, the fill latency could also impact effective bandwidth if separate buffers were not provided for each potential ongoing fill. Sometimes miss handling might be stalled waiting for a block fill to complete and to free buffer entry; this would be more likely to happen with longer fill latency.)

A larger block size tends to increase the number of conflict misses; with a smaller number of sets, the chance of multiple near-in-time access having the same index is higher. Ironically, spatial locality of access can increase the rate of conflicts under traditional indexing because if one access conflicts, nearby accesses are also likely to conflict. (Skewed associativity could reduce this effect.)

Overview

With larger caches, the conflict misses from larger blocks are less common because either the number of sets is increased (so the chance of indices matching is lower) or the number of ways is increased (so matching indices are less likely to evict a useful cache block). The larger access latency of larger caches also reduces the latency penalty of higher associativity. In addition, larger caches increase the residency time of a block which tends to increase the spatial locality.

With even the simplest implementation of prefetching (loading all the blocks equivalent to a larger block), the spatial locality based hit rate benefit of larger block sizes effectively disappears while retaining finer-grained replacement choice (and coherence invalidation).

(For L2+ caches, which are not considered in this question, tag storage size can be a significant consideration since such caches are typically accessed with tag-data phasing and farther caches are not probed until a miss is determined. Smaller tag storage then means lower hit latency and lower miss determination latency. In addition, if the tag storage less area-efficient, the cost of tag storage becomes more significant; the SRAM tags with DRAM data storage in some IBM POWER L3 caches is a case where smaller bit count tag storage has a greater benefit.)

64 bytes appears to be a fairly settled block size for "general purpose" L1 caches in part from the commoditization of 64-bit memory interfaces with DRAM burst length of 8 (and software optimizations based on this size) but also matching reasonably well "typical" spatial locality for "typical" capacity L1 caches. Some server-oriented processors use larger blocks in part because larger capacity last-level caches are often helpful (having closer matching of L1 and L2 block sizes can be helpful) and because spatial locality may be more common. Some GPUs use larger L1 cache blocks, presumably to support greater memory bandwidth and access bandwidth with the common case also having considerable spatial locality with weak temporal locality (streaming accesses or nearly so).

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