Cache capacity and bandwidth
It is known heuristically that the cache-miss rate is proportional to the reciprocal of some root of the cache capacity. Recently, it was shown that this is because the probability of re-references to data is driven by a power law [31]. For many workloads, the square root is a good fit. Data in a cache is stored as cache lines, which are contiguous sequences of bytes, aligned on boundaries of some power of 2, for example, 64 bytes or 128 bytes, or even more. The reason for this is that reference patterns follow two orthogonal localities, so large chunks (cache lines) are used to capture these behaviors.
Spatial locality of reference is the phenomenon that if a program references a particular datum, then it is extremely likely that the program will also reference other data that are spatially close (by address) to the referenced datum; that is, it will reference nearby data. This is the rationale for bringing in 64 or 128 bytes instead of merely words (4 bytes). Misses caused by near-future references to nearby data (within 64 or 128 bytes) are obviated. Temporal locality of reference is the phenomenon that if a program references a particular datum, then it is extremely likely to re-reference that same datum again in the near future. This locality is the rationale for caching data in the first place; if it were not inherent to programs, caches would not work. Most real workloads exhibit both behaviors simultaneously.
Choosing the right line size in a cache is then an optimization problem in which spatial and temporal localities are traded against each other within a fixed-capacity cache. If a cache is partitioned into many short lines, the fact that there are many of them will capitalize on the temporal aspects of the reference behavior. If the cache is partitioned instead into a smaller number of larger lines, then less temporal context can be captured, but the longer lines provide more spatial context.
However, note that there are other effects of the choice of line size. A cache directory must have a directory entry per line. If the size of the cache is doubled, then the choice is either to keep the size of the directory (therefore, its tractability) intact by doubling the line size or to keep the line size intact and double the size of the directory. Since directory access time is considered sacrosanct in many machines, the trend is toward larger line sizes as cache sizes grow. (In reality, cache line sizes are not generally growing in commercial systems because of contention and potential software tuning problems. The argument just describes one of the incentives to grow the line size.)
An adverse effect of doubling the line size is that it will then take twice as long to transfer a line if the bandwidth is held constant. This can cause costly queuing delays if certain bus utilization thresholds are exceeded, since queuing delay has a severe nonlinearity as utilization increases. The time to transfer a line (measured in processor cycles) is called the “trailing edge” (TE) of a miss and is equal to the number of packets in the line (which is the line size divided by the bus width) times the transfer rate (processor clocks per bus clock). Note that the bus utilization is proportional to the TE, since from the perspective of the bus, the TE is the service time.
In fact, when measuring the performance of a system, the bus bandwidth and the cache capacity manifest as each other and are “mutually fungible” in the following obvious way. To the extent that a cache can be made larger, less bandwidth is required to sustain the cache contents, since those contents will persist longer in the cache. In addition, to the extent that the bandwidth can be increased, less cache capacity is required, since the bandwidth enables the cache to be more facile at quickly importing its contents.
However, because of the power law that governs the miss rate as a function of capacity, this “fungibility” between bandwidth and capacity is disproportionate, as we show below. The reason that this is an impending problem is that we are nearing reasonable electrical off-chip bandwidth limits (and these are area and power limits) and will likely hit them in a generation or two. Further down the road, optics has the potential to provide some relief, but it will likely not arrive in time to avoid the problem.
If we use T to represent performance (where T is the number of threads at a fixed speed), B to represent off-chip bandwidth, and C to represent cache capacity, the impending question will be, “If B cannot increase, what must we do to C to be able to double T (e.g., by adding cores, or threads, or virtual images, which is clearly the trend)?” Figure 5 shows the situation with T threads, B bandwidth, and C cache.
Figure 5
If we double T by merely putting two copies of this system on the same chip to get 2T (see Figure 6), then we also double C (to get 2C), and we double B (to get 2B). However, if we are at a bandwidth limit, we must hold B fixed. This means that we need to cut the original B in half. Because the miss rate varies as the square root of the cache capacity, cutting B in half requires quadrupling C for each {T, B, C}, in order to get two copies of {T, B/2, 4C}.
Figure 6
This means that when we are bandwidth limited, doubling T requires scaling the cache capacity by a factor of 8 (i.e., by 2 × 4C). Since the apparent trends in future scaling all involve increasing the number of threads, and since we are nearing bandwidth limits, this implies that we need a technology that can integrate more storage at an extremely high rate of scaling.
This is quite formidable and beyond the capacity of technology that follows Moore's Law.
)
