METAL: Caching Multi-level Indexes in Domain-Specific Architectures

Anagha Molakalmur Anil Kumar, Aditya Prasanna, Jonathan Balkind and Arrvindh Shriraman

Accelerators for sparse data — graphs, sparse matrices, database tables — use multi-level index structures to find the few nonzero values, which saves memory and bandwidth, but walking those indexes chases pointers through many nodes and thrashes an ordinary cache, so the accelerator stalls; this paper (Simon Fraser and UC Santa Barbara — Anagha M. Anil Kumar, Aditya Prasanna, Jonathan Balkind, Arrvindh Shriraman) presents METAL, which separates the reuse of the index's navigation metadata from the reuse of the actual data and caches the index specially — an IX-cache tagged by the key range each node covers, so a lookup can jump straight to a cached node near the answer instead of walking from the root, plus software reuse-pattern hints saying which nodes to keep or bypass — beating a streaming accelerator 7.8 times and a prior accelerator cache 2.4 times.

The argument in one glance

Problem

Sparse accelerators need indexes to find their data, but the indexes wreck the cache

Accelerators built for sparse data — sparse matrices, graphs, database tables where most entries are empty or absent — cannot afford to scan everything, so they use index data structures to jump straight to the few values that exist. A multi-level index, like a tree or a chained hash table, is space-efficient for sparse data and reduces the DRAM bandwidth the accelerator burns, provided the index's own accesses are reused well. That proviso is the trouble. Finding a value means walking the index: following pointers from the root node down through several levels, comparing keys and searching at each step, until you reach the entry. These walks are dynamic and data-dependent — where you go next depends on the data — so they chase pointers all over memory. On an ordinary cache this pointer-chasing walk-and-search inflates the working set and thrashes the cache, so the accelerator spends its time stalling on index accesses rather than computing.
What people did

Add a normal address-tagged cache in front of the index

The standard response is to put a conventional cache between the accelerator and DRAM, hoping the index nodes it touches stay resident and get reused. That cache is organized the usual way: each cache line is tagged by its memory address, and a lookup checks whether the address it wants is present. If the index nodes fit and are reused, the cache absorbs the traffic.
Why it fell short

The address-tagged cache is exactly why index walks thrash

The paper's key observation is that the cache organization itself causes the thrashing. An address-tagged cache treats an index node as just another block of bytes at some address, so to answer a lookup it must actually fetch every node along the walk, one address at a time, from root to leaf. Nothing lets it skip ahead. And because it caches whatever addresses are touched, the many index nodes from many different walks pile up and evict each other, inflating the working set. The cache also cannot tell the index's navigation metadata — the nodes you walk through — apart from the actual data values, so it lumps their very different reuse behaviors together and manages both badly. The generic cache is blind to the structure of an index, so it makes the index's worst traits worse.
This paper's idea

Cache the index by key range, and hint which nodes to keep

METAL is a caching idiom that lets sparse accelerators use indexes well by decoupling the reuse of the index metadata from the reuse of the data and optimizing each on its own. Its first piece is the IX-cache, a cache that inverts the usual organization: instead of tagging a line by its address, it tags an index node by the key range it covers, so the accelerator probes the cache with the key it is looking for and, on a hit, restarts its walk from a cached node already close to the answer — short-circuiting the walk from the root and, more importantly, shrinking the working set. Range tags also let the cache trade off wide upper-level nodes that reach many keys against narrow lower-level nodes that cut walk latency. Its second piece is reuse patterns: a small interface by which software tells the cache, in terms of the index's structure (ranges, levels), which nodes to insert and which to bypass as it traverses different regions. Together these beat a streaming accelerator by 7.8 times, an address-cache by 4.1 times, and the prior best accelerator cache by 2.4 times, cutting DRAM energy 1.6 times.

Why this problem is worth solving

Indexes are how sparse accelerators avoid drowning in empty data, so making them cheap to traverse is central.

Sparse data is data where most possible entries are absent — a sparse matrix that is mostly zeros, a graph where each node connects to only a few others, a database column where a query matches few rows. A domain-specific accelerator processing such data cannot iterate over the whole dense space; it must find the entries that actually exist, and it does that with an index data structure. A multi-level index — a tree such as a B+Tree, or a hash table with chaining — maps a key to the location of its value by organizing keys hierarchically, so a lookup descends a few levels rather than scanning everything. This is doubly valuable to an accelerator: the index is far more space-efficient than storing the dense layout, and it reduces the DRAM bandwidth consumed, because you fetch only the relevant entries rather than streaming past mountains of zeros. That bandwidth saving matters enormously, since memory bandwidth is usually the accelerator’s scarcest resource. But the saving is conditional on managing the reuse of the index itself, because traversing an index generates its own memory traffic — the nodes you walk through — and if that traffic is not reused efficiently, it can cost more than it saves. So the index is both the accelerator’s way of coping with sparsity and a new access pattern that must be made cache-friendly, which is exactly the tension METAL addresses.

The reason ordinary caches fail here is that an index access looks nothing like the accesses caches were designed for.

A cache works well when accesses have locality: you touch an address, and you or a neighbor touches it or a nearby one again soon. Index walks violate this in several ways at once. First, they are dynamic and data-dependent: which node you visit next is determined by the key and the data, so the sequence of addresses is unpredictable and different every lookup. Second, they chase pointers: each node holds pointers to the next level, so a walk hops across scattered memory locations with no spatial locality. Third, they walk-and-search: to find a key you must visit every level from the root down, so a single lookup touches many nodes, and across many lookups the union of all the nodes touched — the working set — is large and keeps churning, so the nodes evict one another. An address-tagged cache is helpless against this because it can only cache and match exact addresses; it cannot recognize that a node it already holds covers the key being sought, so it cannot skip the redundant upper levels of the walk, and it cannot distinguish the frequently-reused navigation structure from the data values it guards. The consequence is that the very mechanism meant to save bandwidth becomes a cache-thrashing liability, and the paper’s insight is that this is a property of the cache’s organization, not of indexes as such, so a differently-organized cache can fix it.

What people did before, and where it broke

Streaming accelerators over dense or sorted layouts. Avoid indexes entirely by streaming through data in order. Where it broke. For sparse data this streams past enormous amounts of absent or irrelevant entries, wasting DRAM bandwidth, which is exactly what indexes exist to avoid; METAL beats this streaming approach by 7.8 times.
A conventional address-tagged cache in front of the index. Cache index nodes by their memory address like any other data. Where it broke. It must fetch every node along each walk since it can only match exact addresses, and it lets index nodes from many walks thrash each other, inflating the working set; METAL beats it by 4.1 times.
Lumping index metadata and data in one cache. Treat the navigation structure and the actual values uniformly in a single cache. Where it broke. Metadata and data have very different reuse behavior, so managing them together caches the wrong things and evicts the useful ones, a mismanagement METAL fixes by decoupling the two.
A prior domain-specific-architecture cache. The previous best accelerator cache tuned for the workload. Where it broke. It still could not short-circuit index walks or let software express structure-aware caching, so it left performance and energy on the table; METAL beats it by 2.4 times and cuts DRAM energy by 1.6 times.
The gap. No cache organization let an accelerator probe an index by key so a lookup could resume from a cached node near the answer, trade node reach against walk latency, and let software steer insertion and bypass by the index’s structure — the combination needed to make multi-level indexes cache-friendly on a sparse accelerator.

How METAL works

Turning a pointer-chasing index walk into a short-circuited, structure-aware cache lookup

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Separate the index’s navigation from its data, because they are reused for different reasons. The foundational move in METAL is to stop treating an index lookup as a single opaque stream of memory accesses and instead split it into two kinds of reuse with different characters: the metadata — the tree or hash nodes you walk through to navigate — and the data — the actual values those nodes eventually point to. The navigation structure, especially its upper levels, is revisited constantly across lookups, while the data at the bottom may be touched once and never again. A generic cache mixes these together and manages both by the same address-based policy, so it caches the wrong things and evicts the useful ones, which is why index walks thrash. METAL decouples them and optimizes the index-metadata caching on its own, so the reusable navigation structure is kept while the transient data is not allowed to evict it. Recognizing that a data structure’s access stream contains distinct reuse populations that a uniform cache policy handles badly, and managing them by their real reuse rather than a single heuristic, is the same locality-shaping discipline the dynamic reflexive tiling work for sparse data covered elsewhere on this site is built on, reorganizing how sparse accesses are grouped so that what will be reused is actually kept. METAL applies that idea to the split between an index’s structure and its contents.

Tag the cache by what you are searching for, not where it lives, so you can skip ahead. The reason an address-tagged cache cannot help an index walk is that it can only answer “do I have the block at this exact address,” which forces the accelerator to fetch every node from root to leaf because it never knows in advance which addresses a walk will need. The IX-cache inverts this: it tags each cached index node by the range of keys the node covers, and the accelerator probes it with the key it is looking for. Now a hit means something far more useful — “I already hold a node that covers your key” — so the walk can resume from that cached node, closer to the leaf, skipping the upper levels entirely. This short-circuiting reduces walk latency, but its deeper benefit is a smaller working set, because the accelerator no longer needs the whole path resident. It costs a bit more energy per lookup to compare against ranges rather than exact addresses, but the drop in the number of accesses more than pays for it. Turning a multi-level pointer-chasing traversal into a direct cache hit that lands you near the target, rather than replaying every level, is exactly the trick the work on making page walks single-access cache hits covered elsewhere on this site performs for virtual-memory translation, collapsing a hierarchical walk into one lookup. METAL brings that collapse to arbitrary application indexes via key-range tags.

Let the key space express caching policy, since the walk is dynamic but the structure is regular. The final idea confronts a paradox: index walks are dynamic and data-dependent, so you cannot know the addresses in advance, yet you still want to control what gets cached. METAL resolves it by observing that although the addresses are unpredictable, the index’s structure is regular and affine — nodes have levels, ranges, and a predictable shape — so caching preferences can be expressed on those structural features and mapped to concrete addresses only at runtime. Reuse patterns are that interface: software describes, in terms of ranges and levels, which nodes to insert and which to bypass as the accelerator moves through different index regions, choosing where on the reach-versus-latency spectrum to sit for the algorithm at hand. A scan and a join, for instance, want opposite policies, and a reuse pattern lets each ask for the right one without the cache having to guess. Exposing a small, structure-aware interface so that software can steer a hardware cache using the high-level shape of the data rather than raw addresses is the same hardware-software co-design stance the specialized sparse-computation processor work covered elsewhere on this site takes, giving software a way to communicate access intent to specialized hardware. METAL’s reuse patterns are how the accelerator’s knowledge of its index becomes cache policy.

Following an index lookup through METAL

Looking up a key in a B+Tree with the IX-cache and a level reuse pattern

A trace, drawn from the paper's example, of how METAL short-circuits an index walk and manages what it caches.

Step 1 of 5

A software reuse pattern sets the caching policy

For this algorithm, software supplies a reuse pattern expressed on the index structure — say, a level pattern that targets level 2 of the B+Tree. This tells the IX-cache to insert level-2 nodes and bypass others as the accelerator walks, matching the reuse the algorithm actually has.

The pattern is affine over the index (levels, ranges), so it applies even though individual walks are dynamic.

Why it works

Range tags let one probe skip the redundant walk. An address cache must fetch every node from root to leaf because it matches only exact addresses → but tagging nodes by key range lets a key-probe find a covering node directly → so the walk resumes near the leaf and fetches far fewer nodes.
Short-circuiting shrinks the working set, not just latency. Replaying every level keeps the whole path resident and churning → but restarting from a cached node means the upper levels need not stay resident → so the working set drops and the cache stops thrashing.
Decoupling metadata from data caches the reusable part. A uniform cache lets one-off data evict the constantly-revisited navigation structure → but optimizing index-metadata reuse separately keeps the structure resident → so the frequently-walked upper index is not displaced by transient values.
Reach-versus-latency tuning fits the algorithm. No single caching level suits every access pattern → but range tags let METAL cache wide upper nodes for reach or narrow lower nodes for low latency → so scans get short-circuiting and joins get reach, each optimized.
Structure-aware hints steer a dynamic walk. The addresses a walk visits are unpredictable, so the hardware cannot pre-decide what to keep → but reuse patterns express insert-and-bypass on the index’s affine features mapped at runtime → so software encodes the right policy despite the dynamism, freeing space for higher reach.

What it costs (trade-offs and scope)

Range-tag matching costs more per access than address matching. Comparing a key against a stored range is more work than an exact address match, so each IX-cache lookup uses more energy than a conventional cache hit; METAL comes out ahead only because short-circuiting cuts the number of accesses enough to more than offset the per-access cost.
It needs custom cache hardware and a software interface. METAL is a hardware-software co-design: it requires the IX-cache with range tags built into the accelerator and a reuse-pattern interface that software must use to express caching intent, so it is an architectural template to integrate, not a transparent drop-in for an existing cache.
The benefit depends on the software choosing good reuse patterns. The reach-versus-latency trade-off and the insert/bypass decisions are steered by the reuse pattern, so a mis-specified pattern for a workload could cache the wrong levels; the gains assume the pattern matches the algorithm’s actual access structure.
It targets multi-level indexed structures on sparse accelerators. METAL is for domain-specific architectures that traverse tree- or chained-hash indexes over sparse data; workloads without such indexed access, or general-purpose CPUs, are outside its intended scope, and the range-tag idea presumes a key-ordered index structure.
Evidence is four accelerators and specific applications. The 7.8-times, 4.1-times, 2.4-times, and 1.6-times figures are across four integrated accelerators (Gorgon, Capstan, Aurochs, Widx) on applications including data analytics, database scans, graph processing, spatial analysis, and sparse matrix algebra; results depend on the index depth, key distribution, and algorithm, and other designs or workloads could differ.

The evaluation

Caching multi-level index walks on a sparse accelerator

Property	Address-tagged cache	Prior DSA cache	METAL
How index nodes are tagged
Can skip upper levels of a walk
Separates metadata from data reuse
Software can steer caching
Reported outcome

A comparison drawn from the paper. METAL is integrated into four accelerators (Gorgon, Capstan, Aurochs, Widx) and evaluated on data analytics, database scans, graph processing, spatial analysis, and sparse matrix algebra; the 7.8-times, 4.1-times, 2.4-times, and 1.6-times figures are the paper's reported gains over streaming, an address-cache, the prior DSA cache, and prior DRAM energy respectively.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The full paper text was available (an author copy from a co-author’s site), so this account of the mechanism — why sparse accelerators need indexes and why index walks thrash an address-tagged cache, METAL’s decoupling of index-metadata reuse from data reuse, the IX-cache that tags nodes by key range to short-circuit walks from a cached covering node, the reach-versus-walk-latency trade-off between caching wide upper-level nodes and narrow lower-level nodes, and the reuse-pattern interface that lets software steer insertion and bypass on the index’s affine structure — follows the paper’s own description. The headline numbers are the paper’s reported results: METAL improves performance over streaming accelerators by 7.8 times, over address-caches by 4.1 times, and over the prior state-of-the-art accelerator cache by 2.4 times, and reduces DRAM energy by 1.6 times, integrated into four accelerators (Gorgon, Capstan, Aurochs, Widx) across data analytics, database scans, graph processing, spatial analysis, and sparse matrix algebra. Those figures depend on the index structure, key distributions, algorithms, and baselines evaluated; range-tag matching costs more per access, and the gains rely on well-chosen reuse patterns. Exact per-benchmark numbers, the IX-cache microarchitecture, and the three reuse patterns should be read from the paper itself.

Background

Why sparse computing keeps fighting the memory system

It helps to see METAL as one skirmish in a long war between sparse computation and the memory hierarchy. Caches, prefetchers, and the whole memory system were designed around dense, regular, sequential access — the pattern of streaming through an array or a matrix in order, where locality is abundant and the hardware can predict what comes next. Sparse computation is the opposite: its data is scattered, its accesses are indirect and data-dependent, and to find anything it must follow indexes and pointers through irregular structures. This mismatch is why sparse workloads chronically underperform on hardware tuned for dense ones, and it is why a whole subfield of computer architecture builds specialized accelerators and memory structures for sparsity. But even those accelerators inherit the problem the moment they use an index, because an index is itself an irregular, pointer-chasing structure that the underlying cache was never built for. METAL’s insight is that the fix is not a faster generic cache but a cache that understands the structure it is holding — that knows an index node covers a range of keys and can be searched by key. That recognition that the memory hierarchy must be made aware of the irregular structure of sparse data, rather than treated as a generic byte store, is the same conviction the specialized sparse-computation architecture work covered elsewhere on this site is built on, redesigning the hardware around how sparse data is actually organized and accessed. METAL extends it from the sparse data itself to the indexes used to navigate it.

If you remember only three things

1. Domain-specific accelerators for sparse data (sparse matrices, graphs, database tables) use multi-level index structures to locate the few values that exist, which saves space and DRAM bandwidth; but traversing an index means walking from root to leaf, chasing pointers through dynamic, data-dependent accesses that walk-and-search — inflating the working set and thrashing an ordinary cache, so the accelerator stalls on index traffic. The paper's key observation is that the cache organization itself, which tags lines by memory address, is what makes index walks cache-hostile.
2. METAL is a portable caching idiom that decouples the reuse of the index's navigation metadata from the reuse of the data and optimizes each separately, via two pieces. The IX-cache inverts a normal cache by tagging each index node with the key range it covers, so the accelerator probes with a key and, on a hit, restarts its walk from a cached node close to the answer — short-circuiting the upper levels and, chiefly, shrinking the working set — while range tags let it trade wide upper-level nodes (maximizing reach) against narrow lower-level nodes (minimizing walk latency). Reuse patterns are a software interface expressing, on the index's affine structure (ranges, levels), which nodes to insert and which to bypass, so software steers the cache despite the walk being dynamic.
3. Integrated into four accelerators (Gorgon, Capstan, Aurochs, Widx) across data analytics, database scans, graph processing, spatial analysis, and sparse matrix algebra, METAL improves performance over streaming accelerators by 7.8 times, over address-caches by 4.1 times, and over the prior best accelerator cache by 2.4 times, and cuts DRAM energy by 1.6 times. Range-tag matching costs more per access (offset by fewer accesses), it requires custom cache hardware plus the reuse-pattern interface, its gains depend on well-chosen patterns, and it targets key-ordered multi-level indexes on sparse accelerators.

Check yourself

Check your understanding

1. Why do multi-level index walks thrash a conventional cache on a sparse accelerator?
2. What is the IX-cache and how does it help?
3. What is the "reach versus walk-latency" trade-off, and how do reuse patterns address the dynamism of walks?
4. What are METAL's main results and requirements?

Sources

The paper is “METAL: Caching Multi-level Indexes in Domain-Specific Architectures” by Anagha M. Anil Kumar, Aditya Prasanna, and Arrvindh Shriraman (Simon Fraser University) and Jonathan Balkind (UC Santa Barbara), published at ASPLOS 2024 (Volume 2), DOI 10.1145/3620665.3640402.

This explainer is based on the paper’s full text, obtained from an author copy on a co-author’s site (jbalkind.github.io). The account of the mechanism — why domain-specific architectures for sparse data need index data structures and how their dynamic, pointer-chasing walk-and-search accesses thrash an address-tagged cache because the cache organization itself is the culprit; METAL’s decoupling of index-metadata reuse from data reuse and independent optimization of each; the IX-cache that inverts the address-cache by tagging index nodes with their covered key range so the accelerator probes with keys and, on a hit, restarts the walk from a cached node closer to the leaf, short-circuiting the walk and reducing the working set; the trade-off between caching wider upper-level nodes to maximize reach and narrower lower-level nodes to minimize walk latency (with scans preferring short-circuiting and joins preferring reach); and the reuse-pattern interface through which software expresses cache insertion and bypass on the index’s affine structure (ranges, levels) mapped to addresses at runtime, with three generalized reuse patterns — follows the paper’s own description. The reported results cited here are the paper’s own: METAL improves performance over streaming accelerators by 7.8 times, over address-caches by 4.1 times, and over the prior state-of-the-art accelerator cache by 2.4 times, and reduces DRAM energy by 1.6 times, integrated into four accelerators (Gorgon, Capstan, Aurochs, Widx) across data analytics, database scans, graph processing, spatial analysis, and sparse matrix algebra. Exact per-benchmark numbers, the IX-cache microarchitecture, and the three reuse patterns should be read from the paper itself.