In "Concurrent Support of Multiple Page Sizes On a Skewed Associative TLB" (2004; PDF), André Seznec proposed using overlaid ways with different indexing functions with guaranteed avoidance of bank conflicts. This mechanism allows TLB look-ups for multiple page sizes to be done in parallel without the overheads of CAM-based TLBs or the capacity mis-match issues of a separate TLB for each size. (TANSTAAFL: This comes at the cost of reduced associativity for each page size and does not work well with a wide range of page sizes where less significant bits can not be used by all page sizes to determine the bank.)

I have termed multiple indexing functions sharing a single memory array "overlaying", though there might be a better name.

Mohsen Sharifi and Behrouz Zolfaghari proposed using multiple indexing functions with a single bank to reduce conflict misses ("YAARC: yet another approach to further reducing the rate of conflict misses", 2007, PDF)

"Skewed Compressed Caches" (Somayeh Sardashti et al., 2014; PDF) exploits unified storage to avoid conflict misses when a superblock of memory has variable compressibility.

(The merged-associative TLB proposed in Arkaprava Basu's PhD dissertation "Revisiting Virtual Memory" (2013; PDF 6.5MB) allows the OS to specify a page size by virtual address ranges that exclusively use that page size so that all banks of the TLB can be indexed in parallel. This does not overlay the banks, though it could be trivially extended to do so; similarly page-size prediction could be used (as probably presented in "Prediction-based superpage-friendly TLB designs", Misel-Myrto Papadopoulou et al., 2015, showing the similarity to hash-rehash).)

Despite the fact that Seznec proposed the idea over a decade ago, I have not found other explorations of its utility. Are there any other proposed uses for this mechanism of overlaying ways?


The following possible uses come to mind, though I am not aware of any academic exploration of these ideas.

Way Dueling

One possible use is to extend the range of set-dueling. Presented in Moinuddin K. Qureshi et al.'s "Adaptive Insertion Policies for High Performance Caching" (2007), the "Set Dueling mechanism dedicates a few sets of the cache to each of the two competing policies and uses the policy that performs better on the dedicated sets for the remaining follower sets." By linking policies with ways in an overlaid skewed associative cache the number of entries monitored can be extended without sacrificing capacity available to a given policy (though the associativity linked to a policy would be lower).

The number of policy-bound entries in a way could also be adjusted dynamically to trade off training sensitivity with associativity of the preferred policy. It is not clear if competition for the same entries would also have benefits; the degree of sharing of monitored entries could also be adjusted dynamically.

Indirect Jump Target Predictor

In predicting indirect jump targets, some jumps are best predicted simply using the jump instruction address, some jumps are better predicted with history information included in the indexing. This is very similar to André Seznec's original TLB proposal in allowing capacity sharing with different indexing methods while not requiring reprobing (though reprobing could supplement the number of indexing methods, possibly filtered with information from the first probing). More than one non-null sets of history information could be used, and direct jump targets could be included along with single-target indirect jumps.

More specific predictions might be favored, making the instruction-address-based indexed prediction a default prediction.

Virtual Non-Temporal Cache

With overlaid skewed associativity, it could be practical to associate one or more ways with non-temporal access and use indexing functions for such ways which induce conflicts. For example, by simply dropping bits 6..11 of the block number (indexing by bits 0..5,12..N), a 64-block region would conflict with itself 64-times in a stream. (By XORing specific middle and least significant bits, streams with power-of-two block-strides could be allocated densely while still providing self-conflict across groups of blocks.)

Such would have the advantage over a dedicated non-temporal cache of allowing the capacity to be used more flexibly and the advantage of potentially lower semi-reserved capacity compared to LRU placement of non-temporal data in a traditionally indexed cache (where effectively an entire way worth of data would be allocated to a stream of non-temporal data).

Since different ways (and different portions thereof) could have different degrees of inducing conflicts and less conflicting ways could be selectively used, the amount of capacity allowed to a stream could be somewhat flexible and conflicts between streams might be more easily managed.

While conflict-inducing indexing could be used with isolated ways, overlaying would allow capacity to be used more flexibly and allows conflict between ways to push out data that will not be re-referenced.

Variably aligned Blocks

By associating different ways with different alignments of cache blocks, larger blocks can be more practical when there is significant spatial locality but the chunk of data that is accessed together does not start at a highly aligned address. Such could facilitate the use of larger blocks with less unused capacity. Larger blocks can reduce tag overhead and increase the accuracy of way prediction (or the utility of way memoization).

Such might be especially useful for instruction caches (benefitting more from spatial locality and being more friendly to way prediction/memoization), especially branch target instruction caches. Certain trace-oriented pre-decode optimizations might be made more practical by reducing the number of entry points within a cache block. A smaller (faster, more energy-efficient) portion of an instruction cache could be preferentially used for branch targets, avoiding redirection delay like a BTIC but allowing the capacity to be used for non-branch target blocks.

(For data caches, unaligned storage might be useful for something like a signature cache, reducing the disadvantage of non-CAM tags.???)

Similarly, a branch target instruction cache placed after the instruction cache could exploit variable alignment of function entry points without the tag overhead of using multiple smaller blocks.

Stride-based Data Mapping

Similar to using ways to map to different alignments, it would also be possible to have different ways use different subblock strides. For example, a way could map data within a block such that alternating words are excluded, not only increasing utilized capacity when stride-of-two accesses are used but also potentially facilitating fixed-stride SIMD loads and stores.

It might even be practical to support configurable power-of-two strides as long as the stride does not change often.

(A data trace cache might benefit from both supporting different alignments and different chunk compositions (e.g., 32-bit address offset/compressed address vs. 64-bit address, address only vs. address plus N bytes of data). This ties in with intra-block NUMA.)

Binding storage-type to way groups

In a unified cache, one group of ways could be dedicated to instructions and another to data. Such grouping of ways would facilitate lower associativity in at least initial look-up.

This could also be applied to metadata interpretation, different ways storing different types of metadata. For example, some ways could use ECC (requiring read-modify-write on sub-word stores) and some use parity (for lower-overhead sub-word stores, but lower reliability); such could interact with storage reliability where, e.g., ECC-using blocks in high reliability SRAM might allow greater voltage reduction and parity-protected ways might only allocate clean blocks to less reliable SRAM arrays.

Way-based block size

While conventional non-overlaid caches could associate a tag with a pair of storage blocks, using additional ways dedicated to larger blocks would tend to require fewer tag checks. Skewed indexing, especially when overlaid, would reduce conflict increase from clumping of cached data have more spatial locality. In any case, extra tags could be used for dataless inclusion or other metadata, though the increased flexibility of allocation with overlaying would tend to increase opportunities for such alternative uses.

Variable Characteristics of Storage

By overlaying ways, a portion of each way can be mapped to a section of cache which provides faster (or more energy-efficient) access or different amounts of metadata (different types of metadata was mentioned earlier).

By increasing the independence of cache properties and data address via overlaid skewed associaitity, more direct indexing could be used while still supporting differences in characteristics of specific storage locations.

While not as flexible in allocation as a traditional Non-Uniform Cache Architecture (which uses a layer of indirection), such might make NUCA techniques more applicable to L1 caches. (The problem of scheduling dependent operations given variable L1 cache latency would still need to be addressed. In addition, the aliasing issues of L1 skewed associativity would have to be handled.)

(The way indication itself can provide some metadata when ways are reserved for or biased toward specific uses or policies.)

It might also be practical to have portions of the cache (whether specific ways or sections of various ways) use subblock NUCA where a portion of blocks have faster access (e.g., to accelerate pointer-chasing code). While always using fast subblock allocation (with different subblocks being selected by way and/or address) could be implemented in a somewhat straightforward way, variable allocation of fast storage (e.g., where 64-byte blocks might be mapped to four fast 16-byte storage units, one fast storage unit and three slow ones, or four slow storage units) would seem to be difficult.

Such separation could be accomplished in non-overlaid cache by the same association of way/address with cache characteristic, but flexibility of allocation would be lower.

Further Disconnecting Associativity and Capacity

With overlaying, conflict increasing squeezing of portions of ways can be mapped to different storage sections in different ways and accesses from different ways can compete for a given entry.

Partial overlaying provides another dimension of design flexibility. For example, a two-way associative cache might map one way such that half maps to an isolated section and half to an overlaid section and map the other way with its own isolated section (and the common shared section). This kind of partial overlapping might be useful for a Knapsack-like cache ("Knapsack: A Zero-Cycle Memory Hierarchy Component", Todd M. Austin et al., 1993) where a part of the storage could be dedicated to a restricted caching while another part can be used for other accesses as well (e.g., a two-way associative section could be used traditionally while also allowing the Knapsack region to be larger and somewhat sparse in the higher addresses; the amount of contention and the replacement preferences could be somewhat flexibly designed [some similarity might be noted to Brannon Batson and T. N. Vijaykumar's "Reactive-Associative Caches"]).

Isolated ways can provide separation of associativity and capacity by having some ways be smaller than others. However, overlaying provides slightly more flexibility in allocation of capacity. With isolated ways, a given block will always be in a higher conflict section (though this can be compensated by increasing the associativity of the smaller section).

Potentially Greater Virtual Machine Isolation

By overlaying and using different indexing functions for different virtual machines, cache capacity might be more readily provided to virtual machines with less side channel information being communicated.

Traditional skewed associativity with per-VM indexing adjustment would provide most of this benefit, but overlaying provides a little more flexibility in placement and in what mappings can conflict for different pairs of virtual machines.

Multithreading Conflict Containment

Partial overlaying could be used to isolate a portion of the data associated with a thread while still providing substantial capacity sharing. Such would provide more flexible allocation than assigning a traditional way or ways to a thread-specific storage area.

Partial overlaying would facilitate having higher associativity in a subset of cache, which could be advantageous in storage shared by more threads or used for allocations more likely to induce conflict misses or for which conflict misses are more expensive.

In a clustered design, overlaying could be useful for biasing placement to reduce inter-cluster communication when threads are biased or exclusively allocated to particular clusters.

Way Prediction Implications

While skewed associativity may increase the accuracy of partial-tag-based and recency-based way prediction (because spatially local blocks are likely to be mapped to different indexes for different address regions), overlaying may provide a slight further benefit.

(Likewise, biasing allocation to improve way prediction should increase the miss rate less with skewed associativity and especially overlaid skewed associativity than with simple modulo indexing.)

Defect and Block-locking Tolerance

While not a mechanism, it might be worth noting that using overlaying would reduce the impact of excluding certain blocks from allocation choices. While traditional skewed associativity increases conflict resistance in such cases, overlaying would provide a further benefit.

Similarly, locking a chunk of cache could provide the implementation simplicity of traditional way locking with less reduction in effective associativity. (As a side note, mapping a chunk of cache to a specific address to form a scratchpad memory would free the associated tag memory for other uses. For example, half normal size blocks could be supported for part of the remaining cache; overlaid skewed associativity might facilitate flexible allocation of small blocks.)

Reduced indirection overhead for NUCA

Using overlaying would allow different addresses to map to the same block, potentially avoiding the traditional indirection of traditional NUCA while still allowing substantial flexibility in allocation of cache entries into faster storage. Lack of indirection would facilitate placing tags closer to data clusters, at least for the faster storage area (it may be desirable to co-locate all tags to provide faster miss determination, though a cache shared by multiple cores or even just multiple access paths (e.g., instruction vs. data) might have distinct fast storage with associated tags). Even if indirection is used, overlaying would reduce the costs of less general indirection, reducing metadata storage overhead and potentially access latency.

A fixed but different slice for each way would have similar benefits in terms of allowing different addresses to be placed in fast storage with quick lookup, but overlaying increases allocation flexibility.

  • $\begingroup$ I am providing this answer both to share some ideas that came to me and to encourage others to answer even if they do not have publication references. I am unlikely to ever evaluate any of the above ideas, so others should feel free to do so. $\endgroup$ Apr 30 '19 at 0:05

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.