Near-data processing scatters hundreds of small cores through a 3D-stacked memory network, and real-world skewed data then forces an ugly choice — run each task where its data lives and the hot-data units become 1.43× slower hotspots, or steal work for balance and remote traffic doubles — so ABNDP breaks the tradeoff with a co-design where each unit donates 1/64 of its DRAM as a cache whose contents may live only at a few deterministic, skew-mapped "camp locations" (making SRAM tags tiny, probing predictable, and coherence a bulk tag-clear), giving the hybrid scheduler multiple nearby placements for every hot datum to spread load without losing locality — 1.68× average speedup, 25% energy savings, and combined gains far beyond either technique alone.
The argument in one glance
-
Problem
Hundreds of cores inside the memory — and skewed data to feed them
Near-data processing (NDP) answers the memory wall by placing compute where data lives: small cores on the logic die of 3D-stacked memories, one per channel or vault. A realistic system has 16 stacks × 8 NDP units = 128 units (256 cores), each owning 512 MB of local DRAM, joined by a mesh of interconnects. Local accesses are cheap; remote ones cost hops. The catch is real-world data: graphs, sparse matrices, and embeddings follow power laws, so a few elements are touched by orders of magnitude more tasks than the rest.
-
What people did
Schedule by data, or steal for balance
The standard playbook offers two levers. Lowest-distance mapping runs each task at the unit minimizing total distance to all its data — the "near-data" philosophy taken literally. Work stealing lets idle units grab tasks from busy ones, dynamically leveling the load. Both are proven, simple, and widely used.
-
Why it fell short
The two levers pull opposite ways, and each prior system picks one
Measured on PageRank across 128 units: lowest-distance mapping trims interconnect hops 7% — and LOSES 14% performance, because the units holding hot vertices become hotspots, the busiest slowing 1.43× while others idle (and in a bulk-synchronous system, the slowest unit is the finish line). Work stealing recovers balance and gains 14% — while inflating remote accesses up to 2×, burning energy and latency. The root cause is structural: each datum lives in exactly one place, so "near the data" and "where there is slack" are usually different units. Every existing scheduler must sacrifice one goal for the other.
-
This paper's idea
Give hot data more places to be — then let the scheduler choose among them
ABNDP (Tsinghua) attacks the tradeoff's root: multiply the data's locations. Each unit donates 1/64 of its DRAM as a TRAVELLER CACHE whose discipline makes distributed caching affordable — every cacheline may be cached only at C=3 deterministic CAMP LOCATIONS (plus its home), one per localized group of units, with each group using a different address-bit mapping (skewed, like skewed-associative caches). Determinism keeps SRAM tags tiny (160 KB/unit, constant as the system scales) and probing single-shot; bulk-synchronous execution makes coherence a tag-clear. The co-designed HYBRID SCHEDULER scores every unit as cost_mem + B·cost_load — distance to nearest camp/home per datum, plus queued-work imbalance from periodically exchanged load info — with B derived from the topology (half the mesh diameter), not tuned. Result: 1.68× average (up to 2.19×) over the baseline, 24.6% average energy savings — and each technique alone captures only a fraction, because the cache exists to give the scheduler choices.
Why this problem is worth solving
an architectural paradigm that
moves compute to memory rather than data to compute: here,
energy-efficient cores on the logic die beneath 3D-stacked
DRAM (HMC/HBM-style), one “NDP unit” per memory
channel/vault. Local DRAM is reached over through-silicon
vias at hundreds of GB/s; other units’ memory requires
traversing intra-stack crossbars and an inter-stack mesh,
with cost growing per hop
The measured stakes frame the whole paper: against a 16-core host CPU, the baseline NDP system manages only 3.70× on these irregular workloads — a fraction of NDP’s headline potential, precisely because hotspots and remote traffic eat the gains. ABNDP’s fixes lift that to 6.29×. The tradeoff is not an implementation nuisance; it is the difference between NDP delivering on irregular data or not. And the paper’s resolution carries a lesson bigger than NDP: when placement constraints create a conflict, adding placement options — carefully, so metadata and coherence stay affordable — dissolves it.
What people did before, and where it broke
- Lowest-distance mapping (Tesseract-style and kin).
Minimize each task’s total distance to its data. Fewer hops
(−7%), worse performance (−14%): power-law hot elements
drag their home units into hotspots, and
makes the busiest unit everyone’s deadline.
the task model used by most NDP systems: tasks sharing a timestamp run in parallel against read-only inputs, updates apply in bulk at the timestamp’s end. The makespan of each phase is set by the LAST unit to finish — so one overloaded unit stalls all 128
- Work stealing. Idle units pull tasks from busy ones: +14% performance, but up to 2× interconnect hops, with matching energy and latency costs — stolen tasks execute far from their data by construction.
- Static partitioning. Analyze the input and pre-balance the mapping. Fragile against dynamic behavior, and even perfect balance cannot fix the underlying either/or: a hot element still lives in one place.
- Classic DRAM-cache designs. Processor-side DRAM caches (Alloy-style, tags-in-DRAM) assume two memory tiers and one cache; a 128-way distributed cache of peers breaks their metadata math — free placement would need per-unit knowledge of everyone’s contents, and tags-in-DRAM costs a measured 21% slowdown and +54% energy here.
- NUMA/NUCA-aware scheduling. Related in spirit, but NUMA systems have a handful of nodes and locality-rich workloads; 128 low-locality units need exact distance accounting and metadata discipline those designs never faced.
How ABNDP works
A cache designed to give the scheduler options
-
Task-based substrate (the baseline, already strong)
Swarm-like tasks carry a function, a bulk-synchronous timestamp, and a HINT listing the primary-data addresses the task will touch (hand-written or compiler-extracted via pragmas) plus an optional workload estimate. Per-unit hardware task queues and schedulers; hints drive EXACT prefetching into an SRAM buffer before a task runs. No global queue, no central scheduler.
-
Traveller Cache: camp locations new
Each unit reserves 1/64 of local DRAM (8 MB) as a cache for remote data — but a cacheline may be cached ONLY at C=3 camp locations plus its home. Units are partitioned into C+1=4 localized groups; in each group, one deterministic {unit, set} location — computed purely from the address — serves all that group's units. Sharing one copy per neighborhood multiplies reuse without multiplying copies.
-
Skewed mappings across groups new
Each group derives its camp unit ID from a DIFFERENT slice of the address bits — the skewed-associative trick lifted to system scale. Two hot elements that collide in one group's mapping likely spread apart in another's; and a task touching several data elements will likely find SOME group where its elements' camps sit close together. Measured: 12% fewer hops than identical mappings.
-
Metadata that stays small because placement is restricted new
Tags live in SRAM — feasible only because camps cap what can be cached where: the group structure drops the unit-ID bits from tags (15 → 10 bits), totaling 160 KB per unit (≈ the L1s), CONSTANT as stacks are added with C fixed. No unit tracks any other's contents; a requester always probes exactly its nearest camp (a small detour), continuing to the home on a miss, inserting probabilistically (60%) on the way back.
-
Coherence by construction, not protocol new
Bulk-synchronous semantics make primary data read-only within a timestamp: the cache holds only such data, writes bypass straight to home, and at each timestamp's end all cached data is dropped by clearing SRAM tags — no invalidation traffic, no writebacks, no directory. The execution model IS the coherence protocol.
-
Hybrid scheduler, co-designed with the cache new
For each task, score every unit: cost_mem (mean distance to each hint datum's nearest camp-or-home, using hardware constants D_local/D_intra/D_inter — the skewed groups are searched implicitly) plus B × cost_load (unit's queued work relative to average, from a background hierarchical exchange every 100K cycles — staleness is harmless). B = D_inter × half the mesh diameter: an idle unit may be up to half the network away and still win. Argmin picks the unit; hot data's multiple camps mean the argmin can spread load WITHOUT going remote.
The idea
The tradeoff exists because data has one address — so give it several. Every prior scheduler optimizes placement of tasks against fixed placement of data; ABNDP’s move is to make data placement plural. Once a hot vertex is cached at three camps spread across the machine, “near the data” describes four neighborhoods rather than one, and the scheduler can level load among them while every access stays short. The evaluation isolates exactly this synergy: hybrid scheduling without the cache gains 23% but pays 45% more hops (its balance choices are still remote); the cache without smart scheduling cuts hops 21% but leaves hotspots (nothing steers tasks to the camps); together they reach 68% — the cache manufactures the options, the scheduler spends them.
Restriction is what makes distributed caching affordable. A free-placement distributed DRAM cache dies of metadata: tracking who caches what across 128 peers costs storage and coherence traffic no logic die can pay. Camps invert the design: placement is deterministic from the address, so a requester needs zero remote knowledge — probe the one nearby camp, done — and tags shrink enough (160 KB) to live in SRAM, dodging the 21%-slowdown tags-in-DRAM tax. The skew across groups then recovers the flexibility that determinism seemed to surrender, spreading conflicts and clustering multi-datum tasks — the same mapping-permutation-as-free-dimension trick this site saw stripe allocator bitmaps across cache lines in persistent memory. And the execution model completes the frugality: bulk-synchronous read-only phases turn coherence into an end-of-phase tag clear.
Score with hardware constants, not tuned knobs. The scheduler’s cost model uses interconnect distances the hardware defines (D_local, D_intra, D_inter) and a single combining weight B derived from topology — half the mesh diameter — expressing a policy in units of hops: an idle unit may be that much farther than the best data location and still deserve the task. Load information travels lazily (100 K-cycle background exchanges; the ablation shows an 8× coarser interval costs nothing) because the score only needs to be roughly right. It is this site’s cheap-proxy lineage again: two interpretable terms, one derived constant, no training, no search.
A hot vertex’s day, before and after
PageRank on a power-law graph, 128 NDP units
Camp = one of C=3 deterministic cache locations for a cacheline (plus its home). Hint = task's declared data addresses. W_u = unit u's queued work. Numbers from the paper's zsim evaluation.
Step 1 of 6
Baseline: the celebrity vertex creates a hotspot
Vertex v has 100,000 in-neighbors; every one of their PageRank tasks reads v. Under lowest-distance mapping, all that work gravitates toward v's home unit, which runs 1.43× longer than average while distant units idle — and bulk synchrony makes everyone wait for it. Work stealing would drain the queue, but each stolen task then reads v remotely: hops double.
the tradeoff in one vertex: locality concentrates load; balance scatters accesses the slowest unit is the phase's finish line
Why it works
- Skewed data concentrates tasks at hot elements’ single homes → caching those elements at C spread-out camps multiplies the places their tasks can run cheaply → load spreads like work stealing while accesses stay one-probe local, dissolving rather than trading the conflict.
- Deterministic camp placement means the address IS the metadata → no remote-cache state, single-probe lookups, and SRAM tags at 160 KB per unit (constant with scale, with C fixed) → distributed DRAM caching becomes affordable where free placement or DRAM tags measurably fail.
- Different address-bit mappings per group decorrelate conflicts and placements → hot lines colliding in one group spread in another, and multi-datum tasks find some group clustering their camps → 12% fewer hops than identical mappings, and richer scheduling choices.
- Bulk-synchronous phases make primary data read-only while cached → writes bypass to home, phase end clears tags → the coherence cost of a 128-way distributed cache rounds to zero.
- The score’s two terms are measured in the same currency (hops) with B converting idleness into allowable distance → neither pure locality nor pure balance can win the argmin when it hurts the other → the scheduler lands on the frontier the two baselines only touch at endpoints.
What it costs
- Donated DRAM and extra insertions. 8 MB per unit (1/64) leaves the memory pool, and cache fills add DRAM writes — visible in the energy breakdown, repaid by interconnect savings but real.
- Hints are the contract. Tasks must declare their primary-data addresses (by hand or compiler pragmas); workloads whose accesses cannot be enumerated up front — data-dependent pointer chasing inside a task — fall back to weaker scheduling. The site has seen this shape before: predictability is the fuel.
- Wins require skew and sharing. k-means, with independent tasks on private data, shows no benefit — there was no tradeoff to dissolve. The gains scale with how power-law and multi-consumer the data is.
- Simulation, homogeneous, bulk-synchronous. Results are zsim models of general-purpose in-order NDP cores; accelerator-style units, fine-grained dataflow models (where bulk invalidation would not be free), and real silicon are all future work the authors flag.
- Scale’s last word. Even ABNDP gains under 15% moving from 128 to 512 units — remote access remains the fundamental tax of big NDP meshes; the paper improves the frontier without abolishing it.
The evaluation
Eight irregular workloads on real graphs and datasets, six system designs isolating each mechanism (baseline co-location, lowest-distance, +work-stealing, hybrid-scheduling-only, cache-only, full ABNDP) plus a host-CPU reference, with sensitivity sweeps over every design constant.
Ways to place tasks among 128 memory-side units
| Property | Lowest-distance mapping (locality first) | Work stealing (balance first) | ABNDP (Traveller Cache + hybrid scheduling) |
|---|---|---|---|
| Remote accesses (interconnect hops) | |||
| Load balance | Good: +14% performance from leveled queues | ||
| Metadata & coherence burden | None | None | |
| Performance / energy (vs co-location baseline) | |||
| Scaling to 512 units (8×8 stacks) | Degrades — hotspots worsen with more idle peers | Slight gains — remote costs grow with mesh diameter |
Check yourself
Check your understanding
1. Lowest-distance mapping reduces interconnect hops by 7% — yet DEGRADES end-to-end performance by 14%. Predict the mechanism.
2. Traveller Cache forbids free placement: a cacheline may be cached only at 3 deterministic camp locations. What does this restriction buy that makes a 128-way distributed DRAM cache viable at all?
3. Hybrid scheduling alone gains 23% (but +45% hops); Traveller Cache alone cuts hops 21% (but leaves hotspots). Together: +68% with near-minimal hops. Where does the super-additivity come from?
4. A 128-way distributed cache normally implies a coherence protocol — directories, invalidations, writebacks. ABNDP's coherence is a bulk tag-clear at each timestamp's end. What licenses this?
Sources
- ACM DL: ABNDP: Co-optimizing Data Access and Load Balance in Near-Data Processing — ASPLOS 2023 (open access)