Stacked memory gets its enormous bandwidth from having many independent channels rather than faster ones, so you only see that bandwidth if consecutive accesses land on different channels — which depends entirely on how physical addresses are chopped into channel, bank and row bits, a decision made once at boot for the whole machine. This paper (Wisconsin and Penn) measures a 20-fold throughput collapse from a stride the mapping did not anticipate, and lets a program choose a different mapping per data structure, on real FPGA hardware with a modified Linux.
The argument in one glance
-
Problem
The bandwidth is in the channels, and only if you use them all
Stacked memory reaches roughly 960 gigabytes per second per socket against about 102 for conventional memory, and it does so by being wide rather than fast — many independent channels operating in parallel. That is a different bargain from the memory everyone optimised for. A modern processor might have four conventional channels with 2-kilobyte rows; a socket with stacked memory has 32 channels with 256-byte rows. Eight times the parallelism, and eight times less room inside each row, which means the old tricks of exploiting locality within a row matter far less and spreading across channels matters far more.
-
What people did
Interleave addresses across channels and be done
Which channel an address lands on is decided by the address mapping in the memory controller, which chops a flat physical address into channel, bank, row and column fields. The standard arrangement picks that layout once, at boot, from the memory configuration, and sends consecutive cache blocks to consecutive channels. For a program walking through memory sequentially this is exactly right — every consecutive access hits a different channel, and the full bandwidth is available.
-
Why it fell short
One mapping cannot suit every stride
A program striding through an array does not generate consecutive addresses, and if its stride happens to line up with the bits the mapping uses for channel selection, every request lands on the same channel. Measured on real hardware, moving from a stride of one cache line to sixteen collapses throughput by twenty times, and at a stride of thirty-two only a single channel of thirty-two is doing anything. Worse, a mapping tuned for one stride is wrong for another, and a real program has several data structures with different patterns running at once.
-
This paper's idea
Let the program say, per data structure, how it will be used
This paper (Wisconsin and Penn — Jialiang Zhang, Michael Swift and Jing Li) points out that the fact needed to choose a mapping — how a particular array will be traversed — is known in the program and lost by the time an address reaches the memory controller. So they build a path for it: an allocator that associates a mapping with each allocation, a small hardware table that records which mapping applies to which region of memory, and a rule that keeps the whole thing correct with two constraints on how the kernel hands out pages.
Why this problem is worth solving
The parallelism that matters here is not the one that mattered before, and that
inversion is the root of everything else.
Memory offers
parallelism at three levels: across CHANNELS, across banks within a channel, and
within a row of a bank. Conventional memory has few channels and large rows, so
decades of optimisation went into row-level and bank-level parallelism — keeping a
row open and reading many columns from it. Stacked memory inverts the shape.
Vertical stacking with through-silicon vias gives 1024 pins per stack, and a socket
can hold 32 independent channels against four, while each row shrinks from 2
kilobytes to 256 bytes. Channel parallelism runs to 16 or 32 while bank parallelism
is around 8 and row parallelism around 4, and only the channels are genuinely
independent — accesses to different banks of one channel, or different columns of
one row, still serialise on shared resources. So throughput rises linearly with
channels used and only sub-linearly with columns used
Which channel an access reaches is a decision that happens far from where the
relevant knowledge lives.
Getting data
into memory takes two translations. The first, virtual to physical, is the familiar
one managed by the operating system at page granularity. The second, physical to
HARDWARE address, is done inside the memory controller and turns a flat address
into a position in a three-dimensional structure of channels, banks and rows by
slicing the address into bit fields. That slicing is the address mapping, and it is
normally fixed at boot for the whole machine. Its quality depends entirely on the
access pattern: if a program strides by exactly the amount that leaves the channel
bits unchanged, every access it makes goes to one channel. The standard technique
for choosing a mapping is to profile which address bits change most often and use
those for channel selection — but the measurements here show the peak of that
distribution MOVES as the stride changes, so the best mapping for one pattern is
the wrong mapping for another
What people did before, and where it broke
- Pick a mapping at boot and interleave across channels. Firmware reads the memory configuration and chooses a layout that sends consecutive cache blocks to consecutive channels.
- But it only suits sequential access. A stride of sixteen cache lines drops throughput twentyfold, and a stride of thirty-two leaves one channel of thirty-two carrying everything.
- Choose the mapping more cleverly in hardware. Profile which address bits vary most and assign those to channel selection, or hash many bits together to spread entropy into the channel field.
- But it is still one mapping for everything. The bit that varies most depends on the stride, so a globally optimal choice is a compromise between patterns that want different answers.
- Control placement from software with page colouring. The operating system can choose which physical frame backs a virtual page, which does let different data structures be treated differently.
- But the granularity is a page, and this needs cache lines. Spreading concurrent requests across channels means controlling placement at 64 bytes, and shrinking pages to 64 bytes would be ruinous.
- Predict access patterns in the memory controller. Watch the physical address stream and adapt.
- But a physical address stream has no structure. It shows a local window of activity and cannot tell which data structure a reference belongs to, which is the level the pattern actually exists at.
- The gap. Hardware can place at the right granularity but knows nothing about the program; software knows about the program but can only place at page granularity. Neither side is missing effort — they are missing each other.
How the program’s knowledge reaches the memory controller
Building a channel for a fact that used to die at the abstraction boundary
-
Choose one address mapping at boot for the whole machine
Firmware inspects the memory configuration and fixes how physical addresses are sliced into channel, bank, row and column fields, interleaving consecutive cache blocks across channels. This is what commercial systems do, and it is the baseline everything is measured against.
-
Establish that the right mapping depends on the access pattern new
Sweep strides on real hardware and watch throughput collapse twentyfold. Then show that the bit-variation profile used to choose a mapping shifts as the stride changes, and that a single mapping chosen for a mix of patterns loses to choosing independently per pattern.
-
Find that only a handful of variables matter new
Profile standard benchmarks and count how many distinct data structures they allocate — up to nearly fifty thousand in one case. Then count how many account for eighty percent of memory references, and find it is tens, and that those few are individually enormous. Tracking them in hardware becomes affordable.
-
Separate the granularity of management from the granularity of placement new
Assign mappings to coarse regions of a couple of megabytes, and allocate individual data structures within a region. The mapping is recorded once per region, but it still controls placement at cache-line granularity, which is the whole point. Region size is independent of page size.
-
Add two small hardware structures and two allocator rules new
A unit in the memory controller that computes the hardware address from the physical one under a chosen mapping, and a small table recording which mapping applies to which region. Correctness needs only that a region hold one mapping, which follows from two constraints on how pages and frames are handed out.
-
Learn the patterns rather than making the programmer state them new
Attribute each memory reference back to the allocation that produced it, then cluster the resulting per-variable patterns into as many groups as the hardware table can hold. A fast clustering method for simple programs, and a slower learned one for programs with many distinct behaviours.
The idea
The fact that decides the answer exists in the program and dies before it arrives. How an array is going to be walked is a property of that array, visible in the source, stable across the program’s life. By the time a request reaches the memory controller it is a physical address, stripped of any indication of which data structure it belongs to — which is why hardware schemes that watch the address stream can only see a local window and cannot distinguish one structure’s pattern from another’s. Meanwhile the operating system does know which allocation a page belongs to, but its only lever on placement is which physical frame backs a virtual page, and that lever moves in 4-kilobyte steps when the decision that matters is made at 64 bytes. So the paper builds the missing conduit: an allocator that records an intended mapping alongside each allocation, a kernel that groups same-mapping allocations into contiguous regions, and a small table the memory controller consults to learn which mapping applies. Nothing here discovers new information — it transports information that already existed to the one place that could act on it. Recognising that a decision is being made badly because the knowledge required sits on the wrong side of an interface, and building a narrow path for it rather than inferring it downstream, is the same the-answer-was-written-down-elsewhere move covered elsewhere on this site where a constraint a program already implies is relocated to the component that can enforce it.
Manage coarsely, place finely, and the trade-off dissolves. The apparent impasse is that hardware-only schemes get cache-line placement with one global mapping, while page colouring gets per-structure treatment at page granularity, and neither can have both — shrinking pages to cache-line size to get fine control would be catastrophic. The resolution is that these are two different granularities being conflated. What has to be fine is placement: which channel a given 64-byte block lands on. What can be coarse is management: how often the system needs to record a decision. So mappings are attached to 2-megabyte regions, individual data structures are allocated within a region, and the region grows and shrinks a whole region at a time. A single table entry then governs the placement of tens of thousands of cache lines, which is why the whole structure fits in 67 kilobytes of memory and about 2 percent of processor area. Correctness comes almost free from the same decoupling, since keeping the high-order address bits that identify a region untouched by the mapping guarantees a physical address still corresponds to exactly one hardware address. Splitting a granularity that looked like one parameter into the thing that must be fine and the thing that must merely be tracked is the same decouple-the-two-rates move covered elsewhere on this site where a system escapes an apparent trade-off by noticing two quantities had been tied together for no reason.
A heavy-tailed distribution is what makes the bookkeeping affordable. The scheme only works if the number of distinct mappings in flight is small, and there is no obvious reason it should be — one profiled benchmark allocates nearly fifty thousand distinct variables. What the measurements find is the familiar shape: count only the variables responsible for eighty percent of memory references and the number drops to tens, and those few are individually enormous, hundreds of megabytes each. One benchmark has 7,268 variables of which a single 910-megabyte one dominates. That concentration is what makes a small hardware table sufficient, and it is also why the automated pattern-selection step is a clustering problem rather than an enumeration: group the major variables into as many behaviour classes as the table can hold, with a cheap method when the program is simple and a learned representation when it is not. The authors are candid that this is a quality-versus-time knob rather than a solved problem. Relying on a small high-traffic subset to carry most of the benefit, so that per-item bookkeeping stays cheap, is the same concentration-makes-it-tractable argument covered elsewhere on this site where a handful of hot items account for most of the work and can therefore be treated specially.
Watching a stride destroy the bandwidth
From a twentyfold throughput collapse to a per-data-structure mapping
Measured on an FPGA prototype with two stacked memory stacks providing 32 channels, a four-core RISC-V processor and a modified Linux.
Step 1 of 5
Sweep the stride and watch the channels go idle
Read memory with strides of one, two, four, eight and sixteen cache lines using the default mapping shipped with the memory controller. Throughput falls by a factor of twenty going from stride one to stride sixteen, because the address bits the mapping uses to select a channel stop changing. At a stride of thirty-two, exactly one channel of thirty-two carries the traffic.
the failure is not gradual, since a stride that leaves the channel bits fixed serialises everything onto one channel regardless of how many exist throughput rises linearly with channels used but only sub-linearly with columns used within a row, so this is the parallelism that matters
Why it works
- Stacked memory has many channels and small rows → throughput depends on spreading concurrent accesses across channels rather than exploiting locality within a row → so the address mapping, which decides channel assignment, becomes the dominant performance lever.
- A stride that leaves the channel-selecting bits unchanged funnels everything onto one channel → the best mapping differs per access pattern → so any single global mapping is a compromise, not a tuning failure.
- Access pattern is a property of a data structure known in the source → passing it through the allocator to a hardware table preserves it → giving the memory controller information a physical address stream cannot contain.
- Placement must be fine but bookkeeping need not be → attaching mappings to 2-megabyte regions rather than pages → so one table entry governs tens of thousands of cache lines and the table fits in 67 kilobytes.
- A few variables carry most references and are individually huge → a small number of distinct mappings suffices → which is why clustering patterns into a handful of groups loses little.
What it costs (trade-offs and scope)
- It needs the pattern to be identified. Programmers can state it for simple strides, but anything else relies on a profiling and clustering pipeline whose quality the authors present as a time-versus-accuracy knob.
- Profiling is heavyweight. Attributing references to allocations requires two passes, one intercepting every heap allocation to capture call stacks and one collecting physical addresses with program counters.
- Memory gets partitioned by mapping. Separate allocator pools per mapping cause internal fragmentation, measured at 6.25 percent in one configuration, bounded by the number of patterns rather than the number of regions.
- The evaluation is an FPGA at 200 megahertz. A four-core soft processor with small caches, which is the honest way to run a full stack including a modified kernel, but is not a production part.
- The clever alternative barely helps. A theoretically perfect hashing function for address mapping yields under 3 percent, which the authors report rather than pursue.
The evaluation
Everything runs on a real prototype rather than a simulator: a four-core RISC-V processor with near-memory accelerators on an FPGA attached to 8 gigabytes of stacked memory, booting a modified Linux with a modified C library, which is what makes the allocator and kernel changes meaningful rather than assumed. The comparison spans the whole design space — the default mapping, a single global mapping chosen by bit-variation profiling over a workload mix, a hashing-based mapping that needs no profiling, and then per-structure mappings with patterns chosen by hand, by clustering, and by a learned representation.
| Property | One global mapping in hardware | Page colouring in software | Per-region mapping, co-designed |
|---|---|---|---|
| Granularity of control | |||
| Different treatment per data structure | |||
| What it knows about the program | |||
| Behaviour on a mix of strides | |||
| Cost |
Check yourself
Check your understanding
1. Stacked memory offers roughly ten times the bandwidth of conventional memory, yet a simple change in access stride can cost twenty times the throughput. Predict why the shape of the memory makes it so fragile.
2. Hardware can place data at cache-line granularity but uses one global mapping; software can distinguish data structures but only places at page granularity. Predict how the paper escapes that trade-off.
3. Giving each data structure its own mapping requires the hardware to track them. Predict why that does not explode, given that one profiled program allocates nearly fifty thousand distinct variables.
4. The paper reports that a theoretically perfect hashing function for address mapping buys under 3 percent. Predict what that tells you about where the gains come from.
Sources
- Jialiang Zhang, Michael Swift and Jing (Jane) Li. “Software-Defined Address Mapping: A Case on 3D Memory.” ASPLOS 2022, Lausanne. University of Wisconsin-Madison and University of Pennsylvania. DOI 10.1145/3503222.3507774.
- Full text of the paper was used for this explainer, including the channel parallelism and address mapping background in Section 2, the three motivating experiments on stride sensitivity, mixed patterns and variable-level statistics in Section 3, the chunk-based mapping design and its correctness argument in Section 4, the architectural support in Section 5, the allocator changes and the profiling and clustering pipeline for pattern selection in Section 6, and the prototype description and results across standard, data-intensive and accelerator workloads in Section 7.