NDS: Programmer-Free Offload of High-Performance Near Data Strands

1 Introduction

• Current NDP systems often require programmer-visible data movement, new offload APIs, compiler or ISA support, or NDP-specific data layouts.These requirements complicate using NDP in business- and science-critical applications with memory-bound kernels.Source: §1 · p. 1
• NDS asks whether hardware can transparently identify useful regular loops in unmodified binaries and offload them when execution conditions make near-data processing profitable.The target is a constrained class of repeated loops; unsupported or low-benefit loops remain on the host.Source: §1 · p. 1
• NDS observes host execution, records templates for qualifying loops, then instantiates parallel strands and uses runtime information to schedule work for near-data cores.The host's out-of-order execution exposes iteration counts, addresses, dependence behavior, and micro-ops; NDS falls back to host execution when a loop diverges or fails safety checks.Source: §1 · p. 1
• The framework addresses loop detection, strand creation, page movement and coherence, and higher-ILP scheduling for in-order near-data cores.Offload must account for detection, template storage, movement, coherence, MMU/OS handoff, and fallback costs.Source: §1 · p. 1
• Across 12 kernels, NDS detects all dynamically observed loops and improves performance by 3.14× geomean over a host baseline and 1.82× geomean over 8-core host-parallel variants.It identifies 12 inner-loop and 3 outer-loop offload candidates.Source: §1 · p. 2

2.1 NDP Approaches and Hardware

• NDP approaches differ in computation mode, placement, offload granularity, and compute generality, choices that shape available bandwidth and the software/hardware contract.NDS targets processing-in-memory with a simple in-order core associated with each DRAM bank, offloading entire loop regions.Source: §2.1 · p. 2, Locations of Computations · p. 2, Computation Offload Granularity · p. 2

2.2 Loops as NDP-Offload Candidates

• Repeated regular loops are NDS's first target because predictable control, analyzable memory behavior, and reuse support transparent offload and setup-cost amortization.The scope excludes pointer chasing, irregular graph traversal, non-constant strides, deeply data-dependent control, and short loops with little reuse.Source: §2.2 · p. 2

2.3 Hardware-Centric Offloading Scheme

• NDS uses runtime hardware observation to accept loops it can validate cheaply, map data before offload, and fall back to host execution when conditions are unmet.The runtime view includes dynamic paths, host-generated micro-ops, addresses, and repeated loop behavior.Source: §2.3 · p. 2

3.1 Overview

• The framework comprises strand detection, strand analysis, parallelization and template generation, data marshaling, and strand execution.The SAE observes simple loops with deterministic iteration spaces, supported operations, regular memory accesses, high data affinity, and enough expected parallelism to amortize offload costs.Source: §3.1 · p. 3
• On a template match, the host pauses at the loop boundary while the LOU assigns iterations and pages to NDCores, supplies live-ins and bounds, and resumes the host after completion.Dependence and placement checks finish before launch, so NDS strands are not speculative.Source: §3.1 · p. 3
• Figure 3 traces a candidate from detection and profiling to final verification and LOU data marshaling.The framework uses five components to carry out this process.Source: §3.1 · p. 3

3.2 Strand Detection

• The detector monitors dispatched μops for either a forward branch followed by an unconditional backward jump or a backward branch, recording the final branch target as the Loop Start IP.After the branch commits at the end of the first iteration, the FSM promotes the loop to a candidate and signals the LAE to profile it.Source: §3.2 · p. 3

3.3 Strand Analysis

• The SAE records loop-body metadata during a bounded profiling run, then analyzes it after that instance executes, off the normal execution critical path.Captured metadata includes opcode classes, register dependences, live-in values, issue order, memory addresses, and loop-branch information; candidates exceeding template or supported-operation limits are dropped.Source: §3.3 · p. 4
• The LAE checks template and NDCore resource limits, verifies constant memory strides in the MAT, and tests whether the iteration space is deterministic.All μops must be supported, and the loop body, live-in values, and registers must fit their respective limits.Source: §3.3 · p. 4
• The iteration-space check traces loop-closing branch and compare dependences to identify the loop variable, limit, and update operation.Figure 5 presents a case where the analysis passes, while Figure 6 shows a failure case.Source: §3.3 · p. 4

3.4 Template Generation

• NDS creates a template only from a loop candidate that successfully completes its profiling run.The LOU uses templates to verify and orchestrate offloads on later invocations.Source: §3.4 · p. 4
• The LHT stores the invariant loop body, μop schedule, loop controls, memory-access descriptors, and live-in version key, while the VVS holds version-specific live-ins, strides, and loop limit.The LST records the Loop Start IP so later invocations can locate the template.Source: §3.4 · p. 4
• At dispatch, an LST hit tags a possible loop start; after the branch commits, the LHT supplies the version key and an exact match against the VVS selects the template to offload.A version miss can be profiled as a new version if resources allow; otherwise, execution stays on the host.Source: §3.4 · p. 4

3.5 Loop Orchestration and Data Marshaling

• Because each NDCore can access only its attached bank, the LOU maps iterations and pages to banks at page granularity and sends placement intent through the host MMU/OS path.That path allocates or migrates pages and updates mappings; if the mapping cannot be committed safely, NDS aborts before launch and runs the loop on the host.Source: §3.5 · p. 5
• The mapper gives each written page one owning bank during an offload, while read-only pages may be replicated; four page states encode host management, shared reads, replicated reads, or unique writes.The states are HOST, SHARED, REP, and UNIQUE.Source: §3.5 · p. 5
• The LOU estimates a store-page quota per bank, walks iterations to identify touched pages, and selects banks using existing write ownership, work balance, replication cost, and quota.It places touched pages in the selected bank and assigns newly written pages to that bank.Source: §3.5 · p. 5
• Page-level ownership serializes RAW and WAW dependences by co-locating dependent work, while independent write-page regions can run on different banks.Read-only pages may be replicated; patterns that cannot be represented safely by the page-level model fall back to host execution.Source: §3.5 · p. 5
• Initial marshaling is heaviest because it places pages into required states and banks; later invocations can reuse placement unless intervening host execution dirties replicated pages.The recorded placements and bank assignments support estimates of marshaling cost and NDCore launch work.Source: §3.5 · p. 5

3.6 High-ILP Schedules

• Dependent μops within x86 instructions leave in-order cores with very low ILP, and compilers cannot remove these stalls at instruction granularity.This motivates hardware μop scheduling using the host’s observed out-of-order issue behavior.Source: §3.6 · p. 5
• The SAE records the host’s μop issue order across I iterations and uses it to create an NDCore schedule that separates dependent μops.Interleaving more iterations may raise performance but increases template size.Source: §3.6 · p. 6
• The resulting strand has more ILP than typical in-order execution, making higher issue width more effective for NDCores.The paper presents higher issue width as a way to amplify the introspective schedule’s impact.Source: §3.6 · p. 6
• The schedule preserves register dependences, and memory operations are reordered only when MAT descriptors validate non-overlap.Ambiguous aliases preserve program order or send the candidate to host execution.Source: §3.6 · p. 6

3.7 Supporting Coherence Between Offloads

• At a matching Loop-Start commit, the host pauses and the LOU acquires ownership of pages the strands may access.Ownership returns to the host after all strands complete, and host cache lines must be refetched or revalidated before later access.Source: §3.7 · p. 6
• Before offload, NDS flushes or invalidates host cache lines and refreshes replicated pages dirtied by intervening host execution.This gives each NDCore a consistent starting view without refreshing every replicated page.Source: §3.7 · p. 6
• During NDCore execution, the host cannot access acquired pages; SHARED and REP pages are read-only, while each UNIQUE page has one NDCore writer.These page states define the permitted access pattern during execution.Source: §3.7 · p. 6
• The modeled offload is blocking and assumes stable physical mappings with no concurrent host access to acquired pages.Mid-offload interrupts, context switches, post-launch recovery, and arbitrary architectural live-outs are outside the model; host fallback occurs only before launch.Source: §3.7 · p. 6

3.8 Supporting Nested Loops

• A single offload for an entire loop nest avoids potential redundant back-to-back offloads and can reduce costs for subsequent outer iterations.The benefit comes from improving loop orchestration.Source: §3.8 · p. 6
• During profiling, the SAE tags a candidate containing another loop as an outer loop and stores only its dispatched micro-ops.Nesting is rejected when outer-loop stores target live-in registers or addresses not associated with a loop variable.Source: §3.8 · p. 6
• The orchestrator tracks memory strides so it can co-locate pages and iterations across all nesting levels using the same logic.Figure 8 depicts a two-level iteration space organized into strands and partitioned across four banks; the blue bank executes at most nine iterations.Source: §3.8 · p. 6

4.1 Implementation Details

• The host-side control frontend occupies 0.037 mm2, including 0.016 mm2 of modeled metadata storage, and the LOU scratchpad limits the number of distinct templates available during a program run.The area estimate combines synthesized control logic with technology-specific macro models; the SAE provisions 512 micro-op entries for a logical maximum 500-micro-op loop body.Source: §4.1 · p. 6, Loop Orchestration Unit · pp. 7–8, Strand Analysis Engine · p. 7

4.2 Modeling the Hardware

• The model compares host execution with near-data execution, using assumed DRAM latencies of about 45 ns for the host and 30 ns for an NDCore.Configurations include in-order, out-of-order, and Smart Schedule operation, with beefy host resources or wimpy near-bank resources.Source: §4.2 · p. 8, Table 3 · p. 8

4.3 Workloads

• The workloads cover STREAM, Splash-3, and Polybench kernels, plus Multi-Head Attention in llama2.c using TinyLlama-1.1B.For the LLM workload, the measured interval is the time to produce the 2048th token.Source: §4.3 · p. 8, Table 4 · p. 8

4.4 Simulation Setup

• Sniper measures full kernels and isolated inner loops, with out-of-order traces used to generate SAE and LOU inputs and modified schedules used for Smart Schedule runs.The setup estimates page-movement cost from reported CPU-DPU bandwidth and applies a modeled worst-case cache flush cost of 308 μs per offload.Source: §4.4 · p. 8

5.1 Strand Detection and Analysis

• SAE detects all loops matching the branch patterns; of 33 detected loops, 12 inner and 3 outer pass offloadability and parallelizability checks, while 14 are rejected as not parallelizable and 4 as not offloadable.Every workload exposes at least one inner-loop candidate; rejection reasons include unsafe page mapping, dependence conflicts, template limits, or insufficient work to amortize overhead.Source: Figure 9 · p. 8, §5.1 · p. 9

5.2 Effect of Smart Schedules and Issue Width

• On STREAM-ADD, Smart Schedule raises performance from 0.24× to 0.34–0.46× of OoO; issue width 2 gives a 1.45× average benefit over width 1, versus 1.56× at width 4.SS+ consistently improves over the simpler policy, and the remaining evaluations use SS+ with width 2.Source: §5.2 · p. 9

5.3 Location and Type of Execution

• NDP beefy runtime is 1.16× the host beefy baseline; wimpy OoO and plain in-order NDCore runtimes are 8.84× and 15.31×, while SS+ brings in-order runtime to 10.99×.SS+ gives a 1.39× geomean speedup over plain in-order execution; bank-level parallelism provides additional scaling to outperform host execution.Source: §5.3 · p. 9

5.4 Effect of Parallelism

• STREAM Copy, Scale, Add, and Triad achieve 13.23×, 11.88×, 12.43×, and 9.23× speedups, while substantial non-offloaded work bounds whole-kernel gains under Amdahl’s law.The selected loop accounts for 17.5% of Gemver execution, 21.4% of Jacob CP, 30.8% of Jacob NCP, and 36.7% of Jacobi 2D.Source: §5.4 · p. 9
• NDS uses 202 effective NDCores on average, ranging from 11.7 for Jacobi 2D and 64 for MHA to about 254 for STREAM; original page allocation prevents perfect bank alignment before first offload.Jacobi 2D and MHA are the two workloads where NDS trails the 8-core host-parallel baseline.Source: §5.4 · p. 9

5.5 Amortizing Offload Costs

• NDS is most effective for repeated regular loops, where template and page-movement costs can be reused across dynamic invocations.Better OS or runtime page-placement support could further improve transparent NDP performance without changing the binary.Source: §5.5 · pp. 9–10

5.4 Effect of Parallelism

• 3.14× geomean speedup over the OoO host and 1.82× geomean speedup over 8-core host-parallel variants; NDS outperforms host-parallel execution on 10 of 12 workloads.Figure 11 presents the normalized execution-time comparison across parallelism configurations.Source: §5.4 · p. 9, Figure 11 · p. 10

5.5 Amortizing Offload Costs

• Initial page movement averages 56.3% of one-call offload time, but falls below useful loop execution within 8 repeated invocations for every workload and within 4 for 9 of 12.At 64 invocations, initial movement averages 3.9% and useful loop execution 95.2% of offload time; cache flushes contribute less than 1% on average.Source: §5.5 · p. 9, Figure 12 · p. 10

Support for strand detection

• Prior strand-detection proposals often rely on offline profiling or source access, whereas NDS uses lightweight in-flight detection focused on loops.Some compiler-based loop techniques also require software-stack changes or may add execution overhead.Source: §6 · p. 10

Support for NDP

• Many NDP proposals specialize hardware or workloads, rely on programmer involvement, or suggest ISA extensions; NDS targets loop offload without ISA changes.The framework may also couple to other proposals’ infrastructure to broaden the strands it can support.Source: §6 · p. 10

Support for efficient in-order execution

• NDS learns host execution patterns to improve in-order NDCores, using loops’ regularity to condense traces and support micro-op-level scheduling.The paper distinguishes this loop-focused approach from prior trace-cache and execution-pattern techniques.Source: §6 · p. 11

• NDS automatically identifies, validates, parallelizes, and offloads program parts at runtime for near-memory execution.Source: §7 · p. 11
• Smart instruction scheduling and data-marshaling-aware parallelization help NDS extract high near-data-processing performance on simple loops.Source: §7 · p. 11
• NDS is effective for dense linear algebra and strided arrays but excludes complex data-dependent control flow and non-constant access strides.The modeled design also excludes mid-offload interrupts and context switches, post-launch recovery, and arbitrary architectural live-outs.Source: §7 · p. 11