AI-Generated Hints for Problem #002

These are 5 alternative architectural approaches generated by AI.
They are starting points for your own design—not the answer!

Hint 1 (Run 1)

Title of Paper: "Speculative Prediction Cascades: Hiding Multi-Cycle Predictor Latency Through Selective Branch Outcome Sketching"

---

1. Root Cause Analysis

The fundamental tension arises from temporal asymmetry in prediction confidence: the fast predictor commits the pipeline to a path immediately, but the slow predictor—which could correct errors—arrives too late to prevent wasted work. The core issue is:

The pipeline treats branch prediction as a serial, reactive process rather than a parallel, speculative one.

The exponential blowup in naive early prediction stems from treating all intermediate branches as equally uncertain. However, branch outcomes exhibit strong spatial and temporal correlation—nearby branches in the same basic block region often share predictable patterns (e.g., loop bounds, correlated conditions). The root cause is the lack of a mechanism to selectively speculate on high-confidence branch chains while avoiding the combinatorial explosion of low-confidence paths.

---

2. The Mechanism: Speculative Prediction Cascade (SPC)

2.1 Key Insight

Instead of predicting all 2^N paths for N intermediate branches, we observe that:
1. Most branches have asymmetric confidence—one direction is far more likely
2. Branch sequences exhibit chain predictability—knowing one outcome constrains others
3. Only a small subset of "pivot branches" actually cause disagreements between fast/slow predictors

2.2 Hardware Structures

#### Structure 1: Branch Confidence Sketch Table (BCST)

• Organization: 2K entries, direct-mapped by branch PC[11:2]
• Entry Format:

  [3-bit saturating confidence counter | 1-bit dominant direction | 2-bit chain ID]
  `

Function: Tracks per-branch confidence. Branches with confidence ≥ 6 (of 7) are "sketchable"—their outcomes can be assumed without full prediction.
#### Structure 2: Cascade Prediction Buffer (CPB)

Organization: 8-entry fully-associative buffer
Entry Format:

  `
  [Fetch block PC (48b) | Branch mask (8b) | Sketched outcomes (8b) | 
   Cascade depth (3b) | Complex predictor tag (12b) | Valid bit]
  `

Function: Stores "sketched" predictions for upcoming fetch blocks, computed speculatively using high-confidence branches from BCST.
#### Structure 3: Selective Cascade Engine (SCE)

Components:
Cascade Walker: A 2-stage pipelined unit that traverses the predicted path
Confidence Filter: Combinational logic that gates cascade expansion
Outcome Composer: Merges sketched outcomes with complex predictor results

Operation Logic:

  `
  for each fetch block in cascade window (depth ≤ 4):
      branch_mask = BTB_lookup(block_PC)
      for each branch in branch_mask:
          conf = BCST[branch_PC]
          if conf.counter >= THRESHOLD:  // High confidence
              sketched_outcome[branch] = conf.dominant_dir
          else:  // Low confidence - STOP cascade
              mark_as_pivot_branch
              break cascade for this path
      if all branches sketched:
          advance to next_block_PC = compute_target(sketched_outcomes)
  `
#### Structure 4: Pivot Branch Tracker (PBT)

Organization: 16-entry CAM, indexed by complex predictor query tag
Entry Format:

  `
  [Query tag (12b) | Pivot PC (48b) | Cascade checkpoint (CPB index) | Age (4b)]
  `

Function: When the complex predictor returns, PBT identifies which cascade entries depend on that prediction. If the complex predictor disagrees with the sketch, only the affected cascade entries are invalidated—not the entire pipeline.
2.3 Microarchitectural Integration

Cycle 0: Fast predictor issues prediction P_fast
SCE begins cascade from P_fast target

Cycle 1: SCE sketches Block+1 using BCST confidence
CPB entry allocated for Block+1
Complex predictor query initiated for P_fast

Cycle 2: SCE sketches Block+2 (if Block+1 all high-confidence)
CPB entry allocated for Block+2

Cycle 3: Complex predictor returns for P_fast
CASE A: Agrees with P_fast → CPB entries validated, fetch continues
CASE B: Disagrees →

• Check PBT for cascade dependencies
• Invalidate only dependent CPB entries
• Redirect fetch (but preserve independent cascades)

Cycle 4+: Fetch uses validated CPB entries, hiding complex predictor latency

2.4 Critical Innovation: Partial Cascade Preservation
When a complex predictor override occurs, traditional designs flush everything. SPC introduces cascade checkpointing: if the override affects branch B at position 2 in a 4-deep cascade, but branches at positions 3-4 are on an independent control path (different chain ID in BCST), those predictions are preserved. This is detected via the chain ID field—branches with matching chain IDs are correlated; mismatched IDs indicate independence.
---
3. Why It Works: First-Principles Reasoning
Principle 1: Confidence Asymmetry Exploitation
Empirically, 70-80% of dynamic branches have >90% directional bias. BCST captures this, allowing the cascade to "skip" these branches without full prediction. The 3-bit counter provides hysteresis against transient mispredictions.
Principle 2: Latency Hiding Through Spatial Prefetching of Predictions
The complex predictor's latency is fixed (say, 3 cycles). By speculatively computing predictions for blocks 1-4 ahead, we convert a serial latency into parallel work. Even if 50% of cascades are invalidated, the other 50% represent pure latency hiding.
Principle 3: Selective Expansion Bounds Energy
The exponential blowup occurs when cascading through N uncertain branches (2^N paths). By stopping cascade expansion at the first low-confidence "pivot branch," we bound exploration to O(1) paths per cascade depth, with total work O(D) for depth D, not O(2^D).
Principle 4: Partial Preservation Reduces Flush Penalty
Traditional overrides discard all speculative work. Chain IDs enable fine-grained invalidation—if a cascade of 4 blocks has an override at block 1, but blocks 3-4 branch off a different control path (e.g., function call), they remain valid. This converts a 4-block flush into a 2-block flush.
---
4. Evaluation Plan
4.1 Baselines
| Baseline | Description |
|----------|-------------|
| Base-Serial | Traditional 2-level predictor (fast + slow), serial verification, full flush on override |
| Base-Parallel | Naive parallel prediction for N branches ahead (2^N energy) |
| Shotgun [ISCA'19 style] | Multiple BTB ports, predicts multiple paths but without confidence filtering |
| TAGE-SC-L | State-of-art predictor with longer pipeline, representing "just use better predictor" approach |
| SPC (Proposed) | Full mechanism with BCST, CPB, SCE, PBT |
| SPC-NoPartial | Ablation: SPC without partial cascade preservation |
| SPC-NoConfidence | Ablation: SPC cascading all branches regardless of confidence |
4.2 Metrics
| Category | Metric | Rationale |
|----------|--------|-----------|
| Performance | IPC, Frontend stall cycles | Primary benefit |
| Accuracy | Cascade hit rate, Partial preservation rate | Mechanism effectiveness |
| Energy | Predictions computed per cycle, BCST/CPB access energy | Verify no exponential blowup |
| Overhead | Area (mm² at 7nm), Storage (KB) | Practicality |
| Sensitivity | Performance vs. cascade depth, confidence threshold | Design space |
4.3 Methodology

Simulator: gem5 O3 CPU, modified frontend with SPC structures
Workloads:
SPEC CPU 2017 (rate and speed)
Google workloads (search, ads) for branch-heavy server code
Synthetic microbenchmarks (controlled branch density/correlation)
Configuration:
8-wide OoO, 256-entry ROB
Fast predictor: 1-cycle TAGE-lite
Complex predictor: 3-cycle TAGE-SC-L with loop predictor
Energy Model: McPAT + custom RTL synthesis for SPC structures
4.4 Key Experiments
1. Headline Performance: IPC improvement over Base-Serial across SPEC (expect 5-12% on branch-heavy workloads)
2. Energy Efficiency: Predictions/cycle vs. Base-Parallel (expect 10-50× reduction while maintaining 80%+ of performance benefit)
3. Cascade Depth Sensitivity: Sweep depth 1-6, show diminishing returns after 4 (justifies 8-entry CPB)
4. Confidence Threshold Sensitivity: Sweep threshold 4-7, show sweet spot at 6 (balances cascade length vs. accuracy)
5. Workload Characterization: Breakdown of where benefits come from (loop-heavy vs. irregular control flow)
6. Area/Power Overhead: RTL synthesis showing <0.5% core area, <1% power overhead
---
5. Expected Contributions
1. Novel Mechanism: First hardware design to exploit branch confidence asymmetry for selective cascade prediction
2. Theoretical Bound: Proof that SPC achieves O(D) work for depth-D cascades vs. O(2^D) for naive approaches
3. Practical Design: Complete RTL-level specification with area/power estimates
4. Comprehensive Evaluation: Demonstration of 8% average IPC gain on SPEC with <1% energy overhead
---
6. Potential Concerns and Mitigations
| Concern | Mitigation |
|---------|------------|
| BCST training time | Warm-start from profiling; 3-bit counters converge in ~1K instances |
| Chain ID accuracy | Conservative: default to same chain ID (safe but less preservation) |
| CPB capacity | 8 entries sufficient for 4-deep cascade × 2 parallel paths; LRU eviction |
| Complex predictor variability | PBT age field prioritizes older queries; timeout mechanism |
This mechanism addresses a fundamental frontend bottleneck through principled speculation, offering a compelling narrative for a top-tier architecture venue.
---
Hint 2 (Run 2)
Title of Paper: "Speculative Prediction Cascades: Hiding Multi-Cycle Predictor Latency Through Selective Branch Outcome Precomputation"
---
1. Root Cause Analysis
The fundamental tension in hierarchical branch prediction is a latency-accuracy tradeoff that manifests as a serial dependency chain:
1. Fast Predictor (L1): Single-cycle, low accuracy (~92-95%)
2. Complex Predictor (L2): Multi-cycle (3-5 cycles), high accuracy (~97-99%)
The root cause is that the L2 predictor's verification arrives after the pipeline has already fetched instructions based on L1's prediction. When L2 disagrees, we face a prediction correction penalty that:

Flushes speculatively fetched instructions
Creates a "fetch bubble" equivalent to L2's latency
Compounds during high branch density (branches every 5-7 instructions)
Critical Insight: The exponential blowup in naive early prediction stems from treating all future branches as equally uncertain. In reality, branch outcomes exhibit strong temporal and spatial correlation patterns that can be exploited to prune the prediction space dramatically.
---
2. The Mechanism: Speculative Prediction Cascades (SPC)
2.1 Core Innovation: Outcome-Conditioned Prediction Prefetching
Instead of computing predictions for all 2^N possible outcomes of N intermediate branches, SPC identifies high-confidence prediction chains and speculatively pre-computes only the most likely future prediction paths.
2.2 Hardware Structures
#### Structure 1: Branch Correlation Graph (BCG)
A hardware structure that captures dynamic branch outcome correlations.

┌─────────────────────────────────────────────────────┐
│ Branch Correlation Graph (BCG) - 2KB │
├─────────────────────────────────────────────────────┤
│ Entry Format (64 entries × 256 bits): │
│ ┌──────────┬──────────┬─────────────┬────────────┐ │
│ │ Source PC│ Target PC│ Correlation │ Confidence │ │
│ │ (48 bits)│ (48 bits)│ Matrix(128b)│ (32 bits) │ │
│ └──────────┴──────────┴─────────────┴────────────┘ │
│ │
│ Correlation Matrix: 4×4 grid encoding P(B_j|B_i) │
│ for outcomes {TT, TN, NT, NN} between branch pairs │
└─────────────────────────────────────────────────────┘

Update Logic: On every committed branch pair within a 32-instruction window, increment the corresponding correlation counter using saturating arithmetic.
#### Structure 2: Prediction Cascade Queue (PCQ)
A circular buffer storing pre-computed predictions for future branches.

┌─────────────────────────────────────────────────────┐
│ Prediction Cascade Queue (PCQ) - 512B │
├─────────────────────────────────────────────────────┤
│ 16 entries × 256 bits each: │
│ ┌────────┬──────────┬──────────┬────────┬────────┐ │
│ │Valid(1)│Branch PC │Prediction│Conf(8) │Cond(32)│ │
│ │ │(48 bits) │(1 bit) │ │ │ │
│ └────────┴──────────┴──────────┴────────┴────────┘ │
│ │
│ Cond: Bitmask of assumed outcomes for prior │
│ branches that this prediction depends on │
└─────────────────────────────────────────────────────┘

#### Structure 3: Cascade Prediction Engine (CPE)
A dedicated micro-engine that speculatively invokes the L2 predictor.

┌─────────────────────────────────────────────────────┐
│ Cascade Prediction Engine (CPE) │
├─────────────────────────────────────────────────────┤
│ Components: │
│ • Likelihood Estimator: Computes P(path) from BCG │
│ • Path Selector: Chooses top-K (K=2) likely paths │
│ • Shadow GHR: Maintains speculative global history │
│ • L2 Predictor Port: Time-multiplexed access │
│ │
│ Pipeline (3 stages): │
│ [Estimate] → [Select] → [Predict] │
│ ↓ ↓ ↓ │
│ BCG lookup Threshold L2 query │
│ (P > 0.7) │
└─────────────────────────────────────────────────────┘

2.3 Operation Flow
Phase 1: Cascade Initiation (Triggered on L1 prediction)

1. L1 predicts branch B_i at cycle T
2. CPE queries BCG for branches correlated with B_i
3. For each correlated branch B_j:
a. Compute P(B_j outcome | B_i outcome) from BCG
b. If P > threshold (0.7): add to cascade candidate list

Phase 2: Selective Path Exploration

1. Sort candidates by P(path) = ∏ P(B_k | B_{k-1})
2. Select top-2 paths (covers >90% of likely outcomes)
3. For each selected path:
a. Construct speculative GHR assuming path outcomes
b. Query L2 predictor with speculative GHR
c. Store result in PCQ with condition bitmask

Phase 3: Cascade Consumption

1. When L2 verifies/overrides L1 for branch B_i:
a. Check PCQ for entries conditioned on B_i
b. If actual outcome matches condition:

• Prediction is valid, use immediately (0-cycle L2 latency!)

c. If mismatch:

• Invalidate dependent PCQ entries
• Fall back to normal L2 query

2.4 Key Hardware Details
BCG Update Policy:

Update on commit (not speculation) to avoid pollution
Use 4-bit saturating counters with decay (decrement every 1K cycles)
Hash-indexed with PC XOR folded history
Energy Gating Logic:

verilog
// Only activate CPE when beneficial
wire cpe_enable = (branch_density > THRESHOLD) &&
(bcg_confidence > MIN_CONF) &&
(!backend_stall);

L2 Predictor Port Arbitration:

Normal L2 queries have strict priority
CPE uses idle cycles (typically 40-60% available)
Maximum 2 speculative queries per L1 prediction
---
3. Why It Works: First-Principles Reasoning
3.1 Exploiting Branch Correlation Structure
Observation 1: Branch outcomes are not independent. Studies show that ~70% of branches have at least one strongly correlated predecessor within a 32-instruction window.
Observation 2: The correlation structure is sparse and skewed. For a given branch, typically only 2-3 prior branches have meaningful correlation (P > 0.6).
Mathematical Justification:

Naive approach: Explore 2^N paths for N intermediate branches
SPC approach: Explore K paths where K = O(1) due to correlation pruning
Expected coverage: With K=2 paths, we cover E[P(correct)] > 0.85 of actual execution
3.2 Hiding Latency Through Temporal Decoupling
The L2 predictor's latency (L cycles) becomes invisible when:

T_cascade_initiate + L < T_branch_fetch

By initiating cascade predictions N branches ahead (where N ≥ L/avg_branch_distance), we ensure predictions are ready before needed.
3.3 Energy Efficiency Through Selectivity
Key Insight: We don't need to predict all branches early—only those where L1 is likely to be wrong.
Targeting Mechanism: The BCG naturally identifies branches where:
1. L1 and L2 historically disagree (tracked via confidence bits)
2. Outcome strongly depends on recent branch history
This reduces speculative L2 queries by 70-80% compared to naive prefetching.
---
4. Evaluation Plan
4.1 Simulation Infrastructure

Simulator: gem5 (O3CPU model) with custom branch predictor modifications
ISA: x86-64 and ARM (AArch64)
Core Configuration:
8-wide fetch/decode, 256-entry ROB
L1 Predictor: TAGE-SC-L (1-cycle)
L2 Predictor: Perceptron-based (4-cycle)
4.2 Baselines
| Baseline | Description |
|----------|-------------|
| B1: Serial Hierarchy | Standard L1→L2 with flush on override |
| B2: Decoupled Frontend | FDIP-style fetch-directed prefetching |
| B3: Dual-Path Fetch | Fetch both paths for low-confidence branches |
| B4: Prediction Overriding | BOOM-style pipeline with override support |
4.3 Benchmarks

SPEC CPU2017: Integer (high branch density) and FP (low density)
GAP Benchmark: Graph workloads with irregular control flow
CloudSuite: Server workloads (web serving, data analytics)
Synthetic Microbenchmarks: Controlled branch correlation patterns
4.4 Metrics
| Metric | Measurement |
|--------|-------------|
| IPC | Instructions per cycle (primary) |
| MPKI | Mispredictions per 1K instructions |
| Fetch Bubble Cycles | Cycles lost to L2 override flushes |
| Energy | Dynamic energy (predictor + CPE + PCQ) |
| Area | Silicon area overhead (synthesized to 7nm) |
| Coverage | % of L2 predictions served from PCQ |
| Accuracy | % of PCQ entries used correctly |
4.5 Sensitivity Studies
1. BCG Size: 32, 64, 128, 256 entries
2. PCQ Depth: 8, 16, 32 entries
3. Path Exploration Width (K): 1, 2, 3, 4
4. Confidence Threshold: 0.5, 0.6, 0.7, 0.8
5. L2 Latency: 2, 3, 4, 5 cycles
4.6 Expected Results
| Metric | Expected Improvement |
|--------|---------------------|
| IPC | +8-15% on branch-heavy workloads |
| Fetch Bubbles | -60-75% reduction |
| Energy Overhead | +3-5% (predictor subsystem) |
| Area Overhead | ~0.5% of core area |
---
5. Summary
Speculative Prediction Cascades (SPC) transforms the multi-cycle predictor latency problem from a serial bottleneck into a parallel, speculative operation by:
1. Learning branch correlation patterns in hardware (BCG)
2. Pruning the exponential path space to tractable size (CPE)
3. Prefetching high-confidence predictions before they're needed (PCQ)
The key novelty is recognizing that branch correlation sparsity makes selective early prediction both accurate and energy-efficient, avoiding the exponential blowup that makes naive approaches infeasible.
---
Hint 3 (Run 3)
Title of Paper: "SpecuLattice: Energy-Efficient Speculative Branch Prediction Through Selective Path Materialization"
---
1. Root Cause Analysis
The fundamental tension in hierarchical branch prediction stems from a temporal mismatch between prediction availability and verification latency. Let me trace the causality:
Primary Cause Chain:
1. Fast predictor (L1) provides direction in cycle 0
2. Complex predictor (L2) requires N cycles (typically 2-4) to generate its prediction
3. When L2 disagrees with L1, cycles 0 through N-1 of fetched instructions are invalid
4. Pipeline flush cost = N cycles × fetch bandwidth × branch density
Why Naive Speculation Fails:
To hide N cycles of L2 latency, we must predict N branches ahead. With B possible branches in the fetch window, naive full-path speculation requires 2^B predictions—exponential in both compute and energy.
The Unexploited Insight:
Not all speculative paths are equally likely, nor are all branches equally contentious between L1 and L2. The disagreement pattern between predictors exhibits temporal locality and is highly skewed—a small subset of branches causes the majority of overrides.
---
2. The Mechanism: SpecuLattice
2.1 Core Innovation: Disagreement-Guided Selective Path Materialization
Rather than speculating all paths or none, SpecuLattice selectively materializes only the most probable alternative paths based on learned disagreement patterns, organized as a lattice structure rather than a full binary tree.
2.2 Hardware Components
#### Component 1: Disagreement History Table (DHT)

Structure: 1024-entry direct-mapped table
Fields per entry:

• Tag [12 bits]: Partial PC
• Disagreement Counter [3 bits]: Saturating counter
• Override Direction [1 bit]: Which direction L2 typically chooses
• Confidence [2 bits]: How often override direction is correct
• Path Signature [8 bits]: Compressed history at disagreement

Total: ~3.25 KB

Function: Tracks which specific branches frequently cause L1→L2 overrides and the likely override direction.
#### Component 2: Speculative Path Buffer (SPB)

Structure: 4-entry fully-associative buffer
Fields per entry:

• Base PC [48 bits]
• Alternative Target [48 bits]
• Fetch Block Cache [256 bits]: Pre-decoded instruction bytes
• Path Validity Bitmap [4 bits]: Which downstream branches materialized
• L1 Prediction Snapshot [8 bits]

Total: ~184 bytes

Function: Holds pre-fetched alternative paths for high-disagreement branches, ready for instant swap on override.
#### Component 3: Lattice Path Selector (LPS)

Structure: Combinational logic + 16-entry CAM
Inputs:

• Current fetch PC
• DHT lookup results for next N branches
• Global branch history [12 bits]

Outputs:

• Up to 2 alternative path requests to SPB
• Priority encoding for path materialization

Function: Decides which alternative paths to speculatively prepare without exponential blowup.
#### Component 4: Rapid Path Switcher (RPS)

Structure: 2:1 mux network + register file

• Fetch address mux
• Instruction queue injection port
• Branch checkpoint restoration logic

Function: Enables single-cycle swap from L1-predicted path to pre-materialized alternative when L2 override occurs.
2.3 Operational Flow

Cycle 0:

• L1 predicts branch B at PC_x as TAKEN
• DHT lookup: B has disagreement_count=6, override_direction=NOT_TAKEN
• LPS triggers: "Materialize NOT_TAKEN path"

Cycle 1:

• Fetch continues on L1 path (TAKEN)
• SPB initiates alternative fetch for NOT_TAKEN target
• L2 predictor processing begins

Cycle 2:

• L1 path instructions enter decode
• SPB receives NOT_TAKEN path instructions
• L2 predictor still processing

Cycle 3:

• L2 returns: "NOT_TAKEN" (disagrees with L1)
• TRADITIONAL: Flush pipeline, restart fetch (3 cycle penalty)
• SPECULATTICE: RPS swaps to SPB entry, inject pre-fetched instructions

→ 0-cycle effective penalty, only 1-cycle mux delay

Cycle 4:

• DHT update: increment disagreement counter
• SPB entry deallocated

2.4 The Lattice Structure (Key Innovation)
Instead of a binary tree of all 2^N paths, we construct a sparse lattice:

Traditional Full Speculation (N=3 branches):
B1
/ \
B2 B2'
/ \ / \
B3 B3 B3 B3 → 8 paths, 8× energy

SpecuLattice Selective Materialization:
B1 (DHT: high disagreement)
/ \
[L1] [ALT] ← Only materialize alternative
|
B2 (DHT: low disagreement)
|
[L1 only] ← Don't speculate B2's alternative

→ 2 paths materialized, ~1.3× energy

Selection Policy (LPS Logic):

for each branch B in lookahead window:
if DHT[B].disagreement_count > THRESHOLD_HIGH:
if SPB.has_free_entry():
materialize(B, DHT[B].override_direction)
elif DHT[B].disagreement_count > THRESHOLD_MED:
if B is on critical path AND SPB.entries < 2:
materialize(B, DHT[B].override_direction)

2.5 Energy-Bounding Mechanism
Hard Limit: SPB size (4 entries) caps maximum speculation at 4 alternative paths regardless of branch density.
Adaptive Throttling:

Structure: 4-bit energy budget counter

• Decremented on each SPB allocation
• Incremented on each useful swap (correct alternative)
• When counter = 0: disable new materializations for 16 cycles

This creates a closed-loop energy control that naturally throttles speculation during low-benefit phases.
---
3. Why It Works: First-Principles Reasoning
Principle 1: Skewed Disagreement Distribution
Empirical observation: ~15% of static branches cause ~80% of L1→L2 overrides. By tracking disagreement history, we focus resources on the problematic minority.
Mathematical Justification:
Let D = set of high-disagreement branches, |D|/|B_total| ≈ 0.15
Coverage of overrides by D: P(override | B ∈ D) ≈ 0.80
Energy ratio vs. full speculation: |D|/2^N << 1 for N ≥ 3
Principle 2: Temporal Locality of Contention
Branches that cause overrides exhibit phase behavior—a branch contentious in cycle T is likely contentious in cycle T+k for small k. The DHT exploits this with saturating counters.
Principle 3: Asymmetric Path Value
The alternative path has value only if L2 overrides. Expected value:

E[value] = P(override) × (latency_saved) - (1-P(override)) × (energy_wasted)

By conditioning materialization on high P(override) branches, we maximize E[value].
Principle 4: Bandwidth Amortization
The SPB fetch of alternative paths can use:

Idle L1-I$ ports (during backend stalls)
Lower-priority fill buffer entries
Existing next-line prefetch bandwidth
This amortizes the bandwidth cost over cycles where it would otherwise be unused.
---
4. Evaluation Plan
4.1 Simulation Infrastructure
Simulator: gem5 O3 CPU model, modified with:

Configurable hierarchical branch predictor (TAGE-SC-L as L2)
SpecuLattice hardware models
Cycle-accurate energy modeling via McPAT integration
Workloads:

SPEC CPU2017 (rate and speed, all 43 benchmarks)
GAP benchmark suite (graph analytics)
CloudSuite (web serving, data analytics)
Synthetic microbenchmarks (controlled branch density)
4.2 Baselines
| Baseline | Description |
|----------|-------------|
| Ideal-L2 | L2 predictor with 0-cycle latency (upper bound) |
| Baseline-Hier | Standard hierarchical predictor, no speculation |
| TAGE-SC-L-Only | Single complex predictor, no hierarchy |
| Shotgun | Prior work: fetch from multiple targets [Seznec, ISCA'14] |
| Convergent Fetch | Prior work: reconvergence-based [Hilton, MICRO'09] |
4.3 Metrics
Performance:

IPC improvement over Baseline-Hier
Branch MPKI (mispredictions per kilo-instructions)
Frontend stall cycles (L2 override-induced)
% of Ideal-L2 performance recovered
Energy:

Total frontend energy (predictor + fetch + SPB)
Energy-Delay Product (EDP)
Energy per correct speculation vs. wasted speculation
Hardware Overhead:

Area (mm² at 7nm, synthesized RTL)
Storage budget breakdown
Critical path impact
4.4 Sensitivity Studies
1. DHT Size: 256 → 4096 entries
2. SPB Depth: 2 → 8 entries  
3. L2 Predictor Latency: 2 → 6 cycles
4. Disagreement Threshold: Sweep THRESHOLD_HIGH, THRESHOLD_MED
5. Branch Density: Synthetic workloads with 10%→40% branch frequency
4.5 Expected Results (Hypotheses)
| Metric | Expected Outcome |
|--------|------------------|
| IPC vs. Baseline-Hier | +8-15% on branch-heavy workloads |
| IPC vs. Ideal-L2 | Recover 60-75% of the gap |
| Energy vs. Full Speculation | 5-8× lower |
| EDP vs. Baseline-Hier | 10-18% improvement |
| Storage Overhead | <4 KB total |
4.6 Case Study Analysis
Deep Dive Workloads:
1. gcc (high branch density, irregular patterns)
2. mcf (pointer-chasing, hard-to-predict)
3. xalancbmk (virtual function calls, indirect branches)
For each: detailed breakdown of DHT hit rates, SPB utilization, useful swap ratio.
---
5. Summary
SpecuLattice resolves the hierarchical branch prediction latency bottleneck by introducing disagreement-guided selective path materialization. Rather than exponentially speculating all paths or accepting override penalties, it learns which branches are contentious and pre-fetches only their likely alternative paths.
Key Hardware Innovations:
1. Disagreement History Table (DHT) for learning override patterns
2. Speculative Path Buffer (SPB) for holding alternative paths
3. Lattice Path Selector (LPS) for energy-bounded path selection
4. Rapid Path Switcher (RPS) for single-cycle path swaps
Contribution to the Field:
This work demonstrates that the exponential speculation problem can be reduced to near-linear cost through learned selectivity, opening new design space for latency-tolerant high-accuracy prediction hierarchies.
---
Hint 4 (Run 4)
Paper Title: "Speculative Prediction Threading: Decoupled Branch Resolution via Architectural Prediction Futures"
---
1. Root Cause Analysis
The fundamental tension arises from a temporal mismatch between prediction availability and verification latency in hierarchical predictors. Let me decompose this:
First-Order Problem: The fast predictor (e.g., TAGE-L) provides cycle-0 predictions, but the slow predictor (e.g., perceptron, TAGE-SC-L with statistical corrector) requires 2-4 cycles. When they disagree, the pipeline has already fetched/decoded wrong-path instructions.
Second-Order Problem: The "obvious" solution—pre-computing predictions for future branches—hits an exponential wall. For a branch density of 1-in-5 instructions and a 4-cycle latency gap, we'd need predictions for ~4 unresolved branches, requiring 2^4 = 16 parallel prediction computations.
The Real Root Cause: Current designs treat prediction as a synchronous, demand-driven operation. Each fetch address triggers a fresh prediction lookup. This creates a fundamental serialization: we cannot begin predicting branch B until we know the outcome (predicted or resolved) of branch A.
Key Insight: Branch prediction exhibits significant temporal locality of predictability. The correlation patterns that make a branch predictable (history, path, address) often stabilize before we need the prediction. We're wasting this by computing predictions just-in-time.
---
2. The Mechanism: Speculative Prediction Threading (SPT)
2.1 Core Concept
SPT introduces a decoupled prediction thread that speculatively pre-computes slow predictions for branches before they're encountered in the fetch stream, using a novel Prediction Futures Table (PFT) that stores pre-computed predictions keyed by predicted global history signatures.
Instead of exponential speculation, SPT exploits a critical observation: the global history path is highly predictable. We speculatively "run ahead" the prediction state machine using the fast predictor's outputs as assumed branch outcomes.
2.2 Hardware Structures
#### Structure 1: Prediction Futures Table (PFT)

┌─────────────────────────────────────────────────────────────┐
│ PREDICTION FUTURES TABLE │
├──────────────┬─────────────┬──────────┬─────────┬──────────┤
│ History Hash │ Branch PC │ Slow Pred│ Conf │ Age/Valid│
│ (12 bits) │ (partial) │ (T/NT) │ (2 bits)│ (3 bits) │
├──────────────┼─────────────┼──────────┼─────────┼──────────┤
│ 0x3A7 │ 0x4F20 │ T │ High │ 2 │
│ 0x3A7 │ 0x5100 │ NT │ Med │ 1 │
│ ... │ ... │ ... │ ... │ ... │
└──────────────┴─────────────┴──────────┴─────────┴──────────┘
Entries: 1024 (4-way set-associative)
Total Size: ~4KB

Key Innovation: Entries are indexed by a speculative history hash, not the current architectural history. This allows lookups to proceed even when the actual history hasn't been established yet.
#### Structure 2: Speculative History Predictor (SHP)

┌────────────────────────────────────────────────────┐
│ SPECULATIVE HISTORY PREDICTOR │
│ │
│ Current GHR → Fast Predictor → Predicted GHR │
│ ↓ ↓ ↓ │
│ [GHR_0] ──────► [Branch_1] ────► [GHR_1] │
│ ↓ │
│ [Branch_2] ────► [GHR_2] │
│ ↓ │
│ [Branch_3] ────► [GHR_3] │
│ ↓ │
│ [Branch_4] ────► [GHR_4] │
└────────────────────────────────────────────────────┘
Lookahead Depth: 4 branches (configurable)

The SHP maintains a speculative branch sequence queue that tracks:

Predicted branch PCs (from BTB/ITTAGE)
Fast-predicted outcomes
Resulting speculative history states
#### Structure 3: Prediction Request Queue (PRQ)

┌─────────────────────────────────────────────┐
│ PREDICTION REQUEST QUEUE │
├──────────┬───────────┬──────────┬──────────┤
│ Spec GHR │ Branch PC │ Priority │ Status │
├──────────┼───────────┼──────────┼──────────┤
│ GHR_2 │ 0x5100 │ High │ Pending │
│ GHR_3 │ 0x5280 │ Med │ Computing│
│ GHR_4 │ 0x53A0 │ Low │ Done │
└──────────┴───────────┴──────────┴──────────┘
Depth: 8 entries

#### Structure 4: History Reconciliation Unit (HRU)

┌─────────────────────────────────────────────────────────┐
│ HISTORY RECONCILIATION UNIT │
│ │
│ Architectural GHR ←──┐ │
│ ↓ │ │
│ [Hash Function] ──────┼──► PFT Lookup │
│ ↓ │ │
│ [Match Detection] ────┘ │
│ ↓ │
│ [Prediction Selection]: Use PFT entry OR recompute │
└─────────────────────────────────────────────────────────┘

2.3 Operation Pipeline
#### Phase 1: Speculative History Projection (Cycle 0-1)

1. Fast predictor provides prediction for current branch
2. SHP updates speculative GHR assuming fast prediction is correct
3. BTB/ITTAGE provides next N likely branch PCs
4. For each future branch: compute speculative history hash

#### Phase 2: Asynchronous Slow Prediction (Cycles 1-4, background)

1. PRQ dispatches (branch_PC, spec_GHR) tuples to slow predictor
2. Slow predictor computes predictions using spec_GHR as context
3. Results written to PFT, indexed by spec_GHR hash + partial PC
4. Priority: branches closer in fetch distance computed first

#### Phase 3: Prediction Consumption (Cycle N, when branch encountered)

1. Fetch encounters branch at PC_x with architectural GHR_actual
2. HRU computes hash(GHR_actual)
3. PFT lookup: hash(GHR_actual) + PC_x
4. IF PFT hit AND spec_GHR matches:
→ Use pre-computed slow prediction (0-cycle latency!)
ELSE:
→ Fall back to demand slow prediction (original latency)

2.4 Handling Speculation Errors
When fast predictor is wrong:

┌────────────────────────────────────────────────────────────┐
│ MISPREDICTION RECOVERY │
│ │
│ 1. Branch resolves differently than fast prediction │
│ 2. All PFT entries with dependent spec_GHR are invalidated │
│ 3. SHP resets speculative state from corrected GHR │
│ 4. PRQ entries with invalid spec_GHR are squashed │
│ 5. New speculative projection begins from corrected point │
└────────────────────────────────────────────────────────────┘

Critical Optimization - Partial History Matching:
Instead of requiring exact GHR match, we use folded XOR hashing with a confidence threshold:

Match Score = popcount(hash(GHR_spec) XOR hash(GHR_actual))
IF Match_Score < Threshold: Accept prediction
ELSE: Recompute

This tolerates minor history divergence while maintaining prediction quality.
2.5 Energy-Efficient Speculation Control
The Exponential Problem Solved:

Traditional approach: 2^N predictions for N speculative branches
SPT approach: N predictions (linear) along the PREDICTED path

Why this works:

• Fast predictor accuracy: ~93-95%
• Probability of K consecutive correct fast predictions:
• K=4: 0.94^4 ≈ 78%
• We only need ONE path, not all paths
• Wrong path predictions are wasted, but:
• Only 1 prediction wasted per wrong fast prediction
• Amortized waste << exponential computation

Adaptive Lookahead Depth Controller:

┌─────────────────────────────────────────────────────────┐
│ ADAPTIVE LOOKAHEAD CONTROLLER │
│ │
│ Inputs: │
│ - PFT hit rate (last 1K branches) │
│ - Fast predictor confidence │
│ - Backend stall cycles │
│ - Power budget remaining │
│ │
│ Output: Lookahead depth ∈ {2, 3, 4, 5, 6} │
│ │
│ Policy: │
│ IF PFT_hit_rate > 80% AND power_ok: │
│ depth = min(depth + 1, 6) │
│ ELIF PFT_hit_rate < 50% OR power_critical: │
│ depth = max(depth - 1, 2) │
└─────────────────────────────────────────────────────────┘

---
3. Why It Works: First-Principles Reasoning
Principle 1: Predictability of Prediction Context
The global history register evolves deterministically given branch outcomes. If we can predict outcomes (which we can—that's what the fast predictor does), we can predict future history states. This transforms an exponential search into linear extrapolation.
Principle 2: Temporal Decoupling Hides Latency
By separating "when we compute predictions" from "when we need predictions," we convert a latency-critical path into a throughput problem. The slow predictor becomes a background process filling a cache (PFT) rather than a pipeline stall source.
Principle 3: Speculation Asymmetry
The cost of wrong speculation in SPT is additive (wasted prediction computations), not multiplicative (pipeline flushes). A wasted PFT entry costs ~10pJ; a pipeline flush costs ~1000pJ and dozens of cycles.
Principle 4: History Locality
Branch behavior is locally stable. The history context that makes branch B predictable at time T is likely similar to the context at time T+100 cycles. Pre-computed predictions remain valid across significant time windows.
Mathematical Justification

Let:
L = slow predictor latency (cycles)
B = average branches per cycle
α = fast predictor accuracy
β = slow predictor accuracy (β > α)
F = flush penalty (cycles)

Traditional hierarchical predictor:
Effective_CPI_penalty = (1-α) × (β-α) × F × B

With SPT (hit rate H):
Effective_CPI_penalty = (1-H) × (1-α) × (β-α) × F × B

If H = 0.85 (achievable with 4-branch lookahead):
Penalty reduction = 85%

---
4. Evaluation Plan
4.1 Simulation Infrastructure
Simulator: gem5 (O3CPU) with custom branch predictor modifications
ISA: ARM v8 / RISC-V (64-bit)
Core Configuration:

8-wide fetch/decode/rename
352-entry ROB
Tournament predictor baseline (TAGE-SC-L + perceptron corrector)
3-cycle slow predictor latency
4.2 Baseline Configurations
| Config | Description |
|--------|-------------|
| Base-Fast | Single-cycle TAGE-L only |
| Base-Hier | Hierarchical TAGE-SC-L (3-cycle verification) |
| Ideal-Hier | Hierarchical with 0-cycle verification (upper bound) |
| Fetch-Directed | Prior work: fetch-directed prefetching for predictors |
| SPT-Conservative | Our design, 2-branch lookahead |
| SPT-Aggressive | Our design, 4-branch lookahead |
| SPT-Adaptive | Our design, dynamic 2-6 branch lookahead |
4.3 Workloads
SPEC CPU2017 (rate):

Integer: gcc, mcf, xalancbmk, deepsjeng, leela, exchange2
FP: lbm, imagick, nab
Server Workloads:

OLTP (TPC-C on MySQL)
Key-Value (Redis, Memcached)
Web serving (Nginx + PHP)
Emerging Workloads:

Graph analytics (GAP benchmark)
ML inference (TensorFlow Lite)
4.4 Metrics
Performance:

IPC improvement over Base-Hier
Frontend stall cycles reduction
Effective branch MPKI
Efficiency:

Energy per instruction (McPAT + custom predictor models)
PFT hit rate
Speculation waste ratio (invalid PFT entries / total entries)
Sensitivity Studies:

Slow predictor latency (2, 3, 4, 5 cycles)
PFT size (512, 1K, 2K, 4K entries)
Lookahead depth (2-6 branches)
Fast predictor accuracy impact
4.5 Hardware Overhead Analysis
| Component | Size | Access Latency | Access Energy |
|-----------|------|----------------|---------------|
| PFT | 4KB | 1 cycle | ~15pJ |
| SHP | 256B | 1 cycle | ~3pJ |
| PRQ | 128B | 1 cycle | ~2pJ |
| HRU | ~2K gates | combinational | ~1pJ |
| Total | ~5KB | - | ~21pJ/access |
Compare to: L1I cache (32KB), BTB (4KB), TAGE tables (32KB)
SPT overhead: <5% of existing prediction infrastructure
4.6 Expected Results (Hypotheses)
1. H1: SPT-Adaptive achieves 85%+ of Ideal-Hier performance (within 5% IPC)
2. H2: PFT hit rate exceeds 80% for branch-intensive workloads
3. H3: Energy overhead < 3% of core dynamic power
4. H4: Benefit scales with slow predictor latency (higher latency → more benefit)
5. H5: Workloads with stable branch patterns (mcf, OLTP) show highest gains
---
5. Related Work Positioning
vs. Fetch-Directed Prefetching [Reinman et al.]: Focuses on instruction cache, not prediction computation. Orthogonal and composable.
vs. Speculative Threading [Sohi et al.]: Thread-level speculation for dependent computation. SPT applies similar decoupling to microarchitectural metadata.
vs. Runahead Execution [Mutlu et al.]: Runahead executes instructions speculatively; SPT only speculates on prediction metadata, far cheaper.
vs. Decoupled Access-Execute [Smith]: Classic decoupling for memory latency; SPT decouples prediction generation from consumption.
---
6. Potential Extensions (Future Work Section)
1. Cross-Core Prediction Sharing: In SMT/CMP, share PFT entries across threads with similar history patterns
2. Compiler-Assisted Lookahead: Static analysis identifies stable branch sequences for deeper speculation
3. Neural Prediction Integration: Use lightweight neural net to predict which future branches need slow prediction
---
This mechanism addresses the fundamental latency-accuracy tradeoff in hierarchical branch prediction through principled temporal decoupling, achieving near-ideal hierarchical predictor performance with bounded, linear energy overhead.
---
Hint 5 (Run 5)
Paper Title: "SpecuPath: Selective Speculative Path Exploration via Branch Correlation Mining for Hiding Hierarchical Predictor Latency"
---
1. Root Cause Analysis
The fundamental problem stems from a temporal asymmetry in hierarchical branch prediction architectures. The fast predictor (e.g., TAGE-SC-L base) provides cycle-1 predictions, while the complex predictor (e.g., neural predictor, perceptron) requires 3-5 cycles for verification. This creates a "prediction confidence gap" where:
1. Sequential Dependency Chain: To predict branch B[n], we need the resolved direction of B[n-1], B[n-2], etc. This creates an exponential fan-out problem (2^k paths for k unresolved branches).
2. The Real Bottleneck: The exponential explosion isn't inherent to the problem—it's a consequence of treating all branch outcomes as equally likely and independent. In reality, branches exhibit strong temporal and spatial correlations that dramatically reduce the effective prediction space.
3. Wasted Work: Current designs either (a) stall and waste frontend bandwidth, or (b) speculatively explore all paths and waste energy. Neither exploits the skewed probability distribution of actual execution paths.
---
2. The Mechanism: SpecuPath Architecture
Core Insight
Instead of exploring 2^k paths or waiting, we selectively pre-compute predictions for only the most probable path(s) using a lightweight Branch Correlation Predictor (BCP) that identifies which branches are highly predictable and which require expensive verification.
Hardware Components
#### 2.1 Branch Correlation Table (BCT)

Structure: 2K entries, direct-mapped by branch PC[11:2]
Entry Format (48 bits):
┌─────────────────────────────────────────────────────────┐
│ Tag[15:0] │ Conf[2:0] │ CorrVec[7:0] │ DomBr[12:0] │ Dir[1:0] │ Valid │
└─────────────────────────────────────────────────────────┘

Conf[2:0]: 3-bit saturating counter indicating prediction confidence
CorrVec[7:0]: Bit vector identifying which of the previous 8 branches this branch is correlated with
DomBr[12:0]: PC tag of the "dominating branch" whose outcome determines this branch
Dir[1:0]: Predicted direction given dominating branch outcome (00=T if DomT, 01=T if DomNT, 10=NT if DomT, 11=NT if DomNT)
#### 2.2 Speculative Path Buffer (SPB)

Structure: 4-entry circular buffer per thread
Entry Format (256 bits):
┌────────────────────────────────────────────────────────────────┐
│ PathID[3:0] │ BranchMask[15:0] │ GHR_snapshot[64:0] │ │
│ PrecomputedPred[15:0] │ ConfidenceMap[15:0] │ Energy_Budget[4:0]│
└────────────────────────────────────────────────────────────────┘

Stores pre-computed predictions for up to 16 branches ahead on the most likely path
ConfidenceMap: Per-branch confidence from BCT lookup
Energy_Budget: Remaining computation budget for this speculative path
#### 2.3 Selective Pre-computation Engine (SPE)

Hardware: 2-wide prediction pipeline, 3-cycle latency
┌─────────────────────────────────────────────────────────────┐
│ Stage 1: BCT Lookup + Correlation Check │
│ Stage 2: Conditional TAGE Access (only if Conf < threshold) │
│ Stage 3: Result Aggregation + SPB Update │
└─────────────────────────────────────────────────────────────┘

Key Innovation: The SPE skips complex predictor access for branches with high BCT confidence, reducing energy by 60-80% compared to naive pre-computation.
#### 2.4 Path Probability Estimator (PPE)

Structure: 64-entry CAM indexed by recent branch pattern
Entry Format (32 bits):
┌─────────────────────────────────────────────────────┐
│ Pattern[11:0] │ PathProb[7:0] │ AltProb[7:0] │ LRU[3:0] │
└─────────────────────────────────────────────────────┘

Tracks probability of the dominant path vs. alternatives
Used to decide whether to pre-compute 1 path (>85% confidence) or 2 paths (70-85%)
2.5 Operational Flow

Cycle 0: Fast predictor provides initial prediction P0
BCT lookup for next N branches in predicted path

Cycle 1: SPE begins selective pre-computation
PPE estimates path probability

Cycle 2: If PPE.prob > 85%: pre-compute single path
If 70% < PPE.prob < 85%: pre-compute 2 paths
Else: fall back to traditional stall-on-override

Cycle 3-5: Complex predictor verifies P0
SPE continues filling SPB with future predictions

Cycle 6+: If complex predictor agrees with P0:
→ Use SPB predictions immediately (0-cycle effective latency)
If complex predictor disagrees:
→ Check if SPB has pre-computed alternate path
→ If yes: switch to alternate path (1-cycle penalty vs. full flush)
→ If no: full pipeline flush (same as baseline)

2.6 Training Logic
The BCT is trained using lightweight correlation detection:

On branch resolution (PC, actual_direction, GHR):
1. entry = BCT[hash(PC)]
2. For each bit i in GHR[7:0]:
if (GHR[i] == actual_direction) for 4 consecutive instances:
entry.CorrVec[i] = 1
entry.DomBr = PC of branch i positions ago
3. Update entry.Conf based on prediction accuracy `

---

3. Why It Works: First-Principles Reasoning

3.1 Exploiting Branch Correlation Structure

Empirical Observation: In SPEC2017 and server workloads, 70-80% of branches have >90% correlation with at least one of the previous 8 branches. This is because:

• Loop branches correlate with loop counters
• If-else chains correlate with dominating conditions
• Function call patterns are repetitive

Mathematical Justification: Let p_i be the prediction confidence for branch i. For k consecutive branches:

• Naive exploration: Energy ∝ 2^k
• SpecuPath: Energy ∝ Σ(1/p_i) for high-confidence branches + 2^m for m low-confidence branches

When m << k (typical case), energy scales linearly rather than exponentially.

3.2 Breaking the Latency-Energy Tradeoff

Traditional approaches assume a zero-sum game between latency and energy. SpecuPath breaks this by:

1. Information Reuse: The BCT captures branch behavior patterns that the complex predictor computes repeatedly. By caching correlation information, we avoid redundant computation.

2. Selective Verification: Not all branches need complex predictor verification. The BCT confidence allows us to skip verification for highly predictable branches, using the complex predictor only where it adds value.

3. Probabilistic Pruning: The PPE focuses computation on likely paths. Even with 15% probability of the alternate path, we only double (not exponentially increase) computation.

3.3 Fundamental Limits

SpecuPath cannot help when:

• Branch outcomes are truly random (rare in real programs)
• Correlation patterns change faster than BCT can adapt (handled by confidence tracking)
• Backend redirects (cache misses, etc.) invalidate speculative state (unchanged from baseline)

---

4. Evaluation Plan

4.1 Simulation Infrastructure

• Simulator: ChampSim with modified frontend to model hierarchical predictors
• Cycle-accurate modeling: 8-wide OoO core, 256-entry ROB, 64KB L1I
• Branch Predictor Baseline: TAGE-SC-L (fast) + Neural Predictor (slow, 4-cycle)

4.2 Workloads

| Category | Benchmarks | Rationale |
|----------|------------|-----------|
| SPEC2017 INT | gcc, mcf, xalancbmk, deepsjeng | Branch-heavy, diverse patterns |
| SPEC2017 FP | lbm, cactusBSSN, imagick | Numeric, regular branches |
| Server | OLTP-Bench, Memcached, MySQL | Commercial workloads |
| Emerging | Graph500, GAPBS, MLPerf | Irregular access patterns |

4.3 Baselines

1. Baseline-Stall: Traditional hierarchical predictor with full flush on override
2. Baseline-AllPath: Naive exponential path exploration (energy upper bound)
3. BOOM-style: Decoupled frontend with limited speculation
4. TAGE-O (Oracle): Perfect fast predictor (performance upper bound)

4.4 Metrics

| Metric | Definition | Target |
|--------|------------|--------|
| IPC | Instructions per cycle | +8-15% vs. Baseline-Stall |
| MPKI | Mispredictions per 1K instructions | Unchanged (not improving accuracy) |
| Frontend Stalls | Cycles frontend is blocked | -40-60% reduction |
| Energy Overhead | Additional energy vs. Baseline-Stall | <5% (vs. 200%+ for AllPath) |
| Area Overhead | Additional silicon area | <2% of core |

4.5 Sensitivity Studies

1. BCT Size: 1K, 2K, 4K entries
2. SPB Depth: 2, 4, 8 entries
3. Complex Predictor Latency: 3, 4, 5, 6 cycles
4. Confidence Threshold: 80%, 85%, 90%, 95%
5. Correlation History Length: 4, 8, 12 branches

4.6 Case Studies

1. Deep Branch Chains: Analyze behavior on mcf (notoriously difficult)
2. Phase Changes: Measure BCT adaptation time during workload transitions
3. Energy Breakdown: Isolate contribution of each component

---

5. Expected Contributions

1. First hardware mechanism to exploit branch correlation for hiding hierarchical predictor latency without exponential energy cost

2. Novel Branch Correlation Table that captures inter-branch dependencies in a compact, hardware-friendly format

3. Selective Pre-computation Engine that provides a principled framework for trading accuracy for energy in speculative prediction

4. Comprehensive evaluation demonstrating practical benefits across diverse workloads

---

6. Risks and Mitigations

| Risk | Mitigation |
|------|------------|
| BCT pollution from noise | Confidence-based filtering; only high-confidence entries used |
| Area overhead | BCT can share SRAM with BTB; SPE reuses existing ALUs |
| Training overhead | Piggyback on existing branch resolution logic |
| Complexity | Modular design allows incremental adoption |

---

AI-Generated Hints for Problem #003

These are 5 alternative architectural approaches generated by AI.
They are starting points for your own design—not the answer!

Hint 1 (Run 1)

Paper Title: "FlashAttend: In-Flash Sparse Attention via Programmable Page-Level Compute Units for Edge LLM Inference"

---

1. Root Cause Analysis

The fundamental bottleneck stems from a bandwidth hierarchy mismatch in the memory-storage system:

| Level | Bandwidth | Capacity |
|-------|-----------|----------|
| DRAM | ~50-100 GB/s | 4-16 GB |
| SSD Controller ↔ Host | ~7 GB/s (PCIe 4.0 x4) | - |
| Flash Channels (aggregate) | ~40-80 GB/s | 256GB-2TB |
| Individual Flash Die | ~1-1.5 GB/s | 16-64 GB |

Critical Insight: The aggregate internal flash bandwidth (40-80 GB/s across 8-16 channels, each with 4-8 dies) is comparable to DRAM bandwidth, but this bandwidth is stranded because:

1. Serialization at SSD controller: All data must traverse the narrow PCIe/NVMe interface
2. Data movement for trivial compute: LLM inference performs simple MAC operations (1-2 ops/byte), yet we move entire weight matrices
3. Attention sparsity unexploited: Modern LLMs exhibit 90%+ attention sparsity, but dense weight reads dominate

The root cause is architectural: we treat storage as a passive data reservoir rather than a distributed compute fabric.

---

2. The Mechanism: FlashAttend Architecture

2.1 High-Level Concept

FlashAttend introduces Programmable Page-Level Compute Units (PPCUs) embedded within each flash channel controller, enabling in-situ sparse attention computation that exploits the full internal flash bandwidth while only transmitting compressed results across the PCIe interface.

2.2 Hardware Structures

#### A. Per-Channel Compute Unit (PPCU)

Each of the 8-16 flash channels is augmented with:

┌─────────────────────────────────────────────────────────┐
│                    PPCU (per channel)                    │
├─────────────────────────────────────────────────────────┤
│  ┌──────────────┐  ┌──────────────┐  ┌───────────────┐  │
│  │ Page Buffer  │  │ Sparse Index │  │ MAC Array     │  │
│  │ (32KB SRAM)  │  │ Table (SIT)  │  │ (16 FP16 MACs)│  │
│  │              │  │ (8KB CAM)    │  │               │  │
│  └──────┬───────┘  └──────┬───────┘  └───────┬───────┘  │
│         │                 │                  │          │
│  ┌──────┴─────────────────┴──────────────────┴───────┐  │
│  │           Micro-Sequencer (256 instructions)      │  │
│  └──────────────────────────┬────────────────────────┘  │
│                             │                           │
│  ┌──────────────────────────┴────────────────────────┐  │
│  │         Partial Sum Accumulator (2KB)             │  │
│  └───────────────────────────────────────────────────┘  │
└─────────────────────────────────────────────────────────┘

Component Details:

1. Page Buffer (32KB SRAM): Holds 2 flash pages (16KB each) for double-buffering during read-compute overlap

2. Sparse Index Table (SIT) - 8KB Content-Addressable Memory:

• Stores attention indices for top-k (k=128-512) relevant KV-cache entries
• Format: {token_id[16b], head_id[8b], score[16b], page_addr[24b]}
• Supports parallel 16-way lookup for batch processing

3. MAC Array: 16 FP16 multiply-accumulate units

• Optimized for vector-matrix operations
• Throughput: 32 GFLOPS @ 1GHz
• Supports BF16/INT8 with mode switching

4. Micro-Sequencer:

• 256-entry instruction buffer for attention kernels
• Instructions: LOAD_PAGE, SPARSE_LOOKUP, MAC_VEC, REDUCE, SEND_PARTIAL
• Programmed once per model deployment

5. Partial Sum Accumulator (2KB):

• Stores intermediate attention outputs before cross-channel reduction
• Supports atomic accumulation for multi-page spans

#### B. Global Coordination Unit (GCU)

Located in the SSD controller ASIC:

┌─────────────────────────────────────────────────────────┐
│                Global Coordination Unit                  │
├─────────────────────────────────────────────────────────┤
│  ┌────────────────┐  ┌─────────────────┐                │
│  │ Token Broadcast│  │ Sparsity Oracle │                │
│  │ Buffer (4KB)   │  │ (Predictor LUT) │                │
│  └────────┬───────┘  └────────┬────────┘                │
│           │                   │                         │
│  ┌────────┴───────────────────┴────────┐                │
│  │      Cross-Channel Reduction Tree    │                │
│  │      (16-input, pipelined adder)     │                │
│  └──────────────────┬───────────────────┘                │
│                     │                                    │
│  ┌──────────────────┴───────────────────┐                │
│  │    Result Compression Engine          │                │
│  │    (Top-k selection + quantization)   │                │
│  └───────────────────────────────────────┘                │
└─────────────────────────────────────────────────────────┘

Component Details:

1. Token Broadcast Buffer: Receives query vectors from host, broadcasts to all PPCUs simultaneously via dedicated sideband bus

2. Sparsity Oracle:

• 64KB lookup table mapping (layer_id, head_id, token_position) → predicted sparse attention pattern
• Updated periodically via host-side profiling
• Enables speculative page prefetch for predicted hot KV-cache entries

3. Cross-Channel Reduction Tree:

• Hierarchical adder tree collecting partial sums from 16 channels
• 4-stage pipeline, 1 cycle per stage
• Handles softmax normalization in final stage

4. Result Compression Engine:

• Selects top-k attention outputs
• Applies 8-bit quantization for PCIe transfer
• Achieves 8-16× bandwidth reduction vs. dense transfer

#### C. Data Layout: Attention-Aware Page Mapping

┌─────────────────────────────────────────────────────────┐
│              Flash Page Organization                     │
├─────────────────────────────────────────────────────────┤
│  Standard SSD:  [Block 0][Block 1]...[Block N]          │
│                 (Sequential, LBA-ordered)               │
│                                                         │
│  FlashAttend:   [Head 0, Tokens 0-63  ][Head 0, 64-127] │
│                 [Head 1, Tokens 0-63  ][Head 1, 64-127] │
│                 ...                                      │
│                 (Striped by attention head across dies)  │
│                                                         │
│  Page Internal: [K vectors (8KB)][V vectors (8KB)]      │
│                 (Co-located for single-page attention)   │
└─────────────────────────────────────────────────────────┘

Key Design Choice: KV-cache entries for the same attention head are striped across channels to enable parallel sparse lookups, while K and V vectors for the same tokens are co-located within pages to minimize page reads per attention computation.

2.3 Operation Flow

Phase 1: Sparse Pattern Prediction (Host-side)

1. Host computes query vector Q for current token
2. Host runs lightweight "attention predictor" MLP (1% of model size, in DRAM)
3. Predictor outputs top-k (k=256) candidate KV-cache indices per head
4. Host sends {Q, sparse_indices} to GCU via PCIe

Phase 2: Distributed In-Flash Attention (Storage-side)

1. GCU broadcasts Q to all PPCUs
2. GCU distributes sparse_indices to relevant PPCUs based on page mapping
3. Each PPCU:
   a. Issues flash reads for pages containing target KV entries
   b. Performs SIT lookup to extract exact offsets within pages
   c. Computes partial attention: softmax(Q·K^T)·V for local entries
   d. Sends partial sums to GCU
4. GCU reduction tree aggregates partial sums
5. GCU compresses result and sends to host

Phase 3: Residual Dense Fallback (Rare)

If attention entropy exceeds threshold (non-sparse layer):
1. GCU signals host for dense mode
2. Traditional page streaming with host-side compute
3. ~10% of layers require this fallback

2.4 Hardware Cost Estimation

| Component | Per-Channel | Total (16 ch) |
|-----------|-------------|---------------|
| PPCU SRAM | 42 KB | 672 KB |
| PPCU Logic | ~50K gates | ~800K gates |
| GCU | - | ~200K gates + 68KB SRAM |
| Total Area | - | ~3-4 mm² in 28nm |
| Power | ~50 mW | ~1W additional |

This represents <5% area overhead on a typical SSD controller die.

---

3. Why It Works: First-Principles Reasoning

3.1 Bandwidth Arbitrage

Principle: Exploit the bandwidth asymmetry between internal flash channels and external interface.

• Internal aggregate bandwidth: ~60 GB/s (16 channels × 4 GB/s each)
• External PCIe bandwidth: ~7 GB/s
• Arbitrage ratio: 8.5×

By computing attention in-situ, we convert:

• Before: Transfer 60 GB/s of raw KV-cache data → bottleneck at 7 GB/s PCIe
• After: Transfer ~0.5 GB/s of attention results → PCIe is sufficient

3.2 Sparsity Exploitation

Principle: LLM attention is inherently sparse; most attention weights are near-zero.

Empirical evidence from recent work (H2O, Scissorhands, StreamingLLM):

• 90-95% of attention mass concentrates on <5% of tokens
• Sparsity patterns are predictable from query vectors alone

FlashAttend exploits this by:
1. Only reading pages containing high-attention tokens
2. Reducing effective read amplification from O(sequence_length) to O(k) where k << sequence_length

3.3 Compute-Storage Co-location

Principle: Minimize data movement by placing compute at the data source.

For LLM inference with arithmetic intensity I = 1-2 ops/byte:

• Traditional: Move 1 byte, compute 1-2 ops, limited by memory bandwidth
• FlashAttend: Compute 1-2 ops in-flash, move only results

The MAC arrays in PPCUs are deliberately weak (32 GFLOPS total) because:
1. Flash read latency (~100μs) dominates anyway
2. We only need to keep up with flash page read rate
3. Stronger compute would be wasted waiting for flash

3.4 Latency Hiding via Pipelining

Principle: Flash read latency is high but throughput is achievable via pipelining.

Time →
Channel 0: [Read P0][Compute][Read P2][Compute]...
Channel 1: [Read P1][Compute][Read P3][Compute]...
...
Channel 15: [Read P15][Compute][Read P31][Compute]...

With 16 channels and double-buffering:

• Flash read latency: 100 μs
• Effective throughput: 16 pages / 100 μs = 2.5 GB/s per channel aggregate
• Compute overlaps completely with next read

---

4. Evaluation Plan

4.1 Baselines

| Baseline | Description |
|----------|-------------|
| CPU-Offload | Standard PyTorch with mmap, CPU inference |
| FlexGen | State-of-the-art offloading with compression |
| PowerInfer | Neuron-aware sparse offloading |
| DeepSpeed-Infinity | NVMe offloading with prefetching |
| CXL-Memory | Ideal CXL-attached memory expansion (upper bound) |
| SmartSSD | Samsung SmartSSD with near-storage FPGA |

4.2 Metrics

Primary Metrics:
1. Token Generation Throughput (tokens/second)
2. Time-to-First-Token Latency (TTFT, ms)
3. End-to-End Inference Latency (ms/query)

Secondary Metrics:
4. Energy Efficiency (tokens/Joule)
5. Storage Bandwidth Utilization (% of internal flash BW used)
6. PCIe Bandwidth Reduction (× vs. dense transfer)
7. Accuracy Preservation (perplexity delta vs. dense attention)

4.3 Workloads

| Model | Parameters | KV-Cache Size (4K context) |
|-------|------------|---------------------------|
| LLaMA-2-7B | 7B | ~2 GB |
| LLaMA-2-13B | 13B | ~4 GB |
| LLaMA-2-70B | 70B | ~20 GB |
| Mixtral-8x7B | 47B | ~12 GB |

Scenarios:

• Edge deployment: 8GB DRAM, 256GB NVMe SSD
• Extreme edge: 4GB DRAM, 128GB eMMC + FlashAttend
• Scaling study: Vary context length from 2K to 32K tokens

4.4 Experimental Setup

Simulation Infrastructure:
1. Cycle-accurate SSD simulator (modified MQSim) with PPCU model
2. Attention pattern traces from real LLM inference (LLaMA-2 on WikiText, MMLU)
3. RTL synthesis of PPCU for area/power estimation (Synopsys DC, 28nm)

Hardware Prototype (if feasible):
1. FPGA-based PPCU on Xilinx Alveo U280
2. OpenSSD platform with modified firmware
3. Real flash chips with interposer for PPCU insertion

4.5 Ablation Studies

1. Sparsity level sensitivity: Vary k from 64 to 1024
2. Channel count scaling: 4, 8, 16, 32 channels
3. Predictor accuracy impact: Oracle vs. learned predictor
4. Compute unit sizing: 8, 16, 32 MACs per PPCU
5. Page size impact: 4KB, 8KB, 16KB pages

4.6 Expected Results

Based on analytical modeling:

| Metric | FlexGen | FlashAttend | Improvement |
|--------|---------|-------------|-------------|
| Throughput (LLaMA-7B) | 0.8 tok/s | 12 tok/s | 15× |
| TTFT (LLaMA-7B) | 45 s | 3 s | 15× |
| Energy (LLaMA-7B) | 50 J/tok | 8 J/tok | 6× |
| PCIe BW used | 7 GB/s | 0.5 GB/s | 14× reduction |

---

5. Novelty Claims

1. First architecture to embed programmable compute units at the flash channel level (not controller level) for LLM inference
2. Novel sparse attention primitive designed for flash access patterns (page-granular, high-latency tolerant)
3. Co-designed data layout that enables parallel sparse KV-cache access across flash dies
4. Sparsity-aware bandwidth arbitrage that converts internal flash bandwidth advantage into inference speedup

---

6. Potential Concerns & Mitigations

| Concern | Mitigation |
|---------|------------|
| Flash endurance | Read-only KV-cache; writes only for model updates |
| Accuracy loss from sparsity | Adaptive k selection; fallback to dense for high-entropy layers |
| Programming complexity | Provide PyTorch custom op; compiler generates PPCU microcode |
| Manufacturing cost | <5% area overhead; can be optional SKU |
| Generalization beyond LLMs | Architecture supports any sparse matrix-vector workload |

---

This architecture represents a fundamental rethinking of the storage-compute boundary for memory-capacity-limited AI inference, transforming SSDs from passive data stores into active participants in the inference pipeline.

---

Hint 2 (Run 2)

Paper Title: "FlashFormer: In-Die Compute-Enabled Flash Architecture for Bandwidth-Unconstrained LLM Inference"

---

1. Root Cause Analysis

The fundamental bottleneck is a bandwidth wall at the flash die-to-controller interface, not the flash media itself.

First-Principles Breakdown:

1. The Arithmetic Intensity Problem: LLM inference during token generation is memory-bound with arithmetic intensity of ~1-2 FLOPs/byte. For a 7B parameter model (14GB in FP16), generating one token requires reading the entire model, demanding ~14GB of bandwidth per token.

2. The Bandwidth Hierarchy Collapse:

• DRAM bandwidth: ~50-100 GB/s
• SSD controller-to-host (PCIe 4.0 x4): ~7 GB/s
• Internal flash channel bandwidth: ~1.2 GB/s per channel × 8 channels = ~10 GB/s
• Per-die bandwidth: ~50-100 MB/s (the true bottleneck)

3. Why Near-Storage Processing Fails: Existing computational storage (e.g., Samsung SmartSSD) places compute at the controller level, which is still downstream of the channel bottleneck. Data must still traverse the narrow flash channels before reaching compute units.

Root Cause: The serialization point is the flash die I/O interface—compute must move inside the flash die to access the internal page buffer bandwidth (~1-10 GB/s per die) before serialization occurs.

---

2. The Mechanism: FlashFormer Architecture

2.1 Core Innovation: In-Die Matrix-Vector Unit (ID-MVU)

We propose embedding lightweight, fixed-function compute units within the flash die peripheral circuitry that operate directly on the page buffer contents before data exits the die.

2.2 Hardware Structures

#### A. Die-Level Compute Unit (Per Flash Die)

┌─────────────────────────────────────────────────────┐
│                    FLASH DIE                        │
│  ┌─────────────────────────────────────────────┐   │
│  │         NAND Array (Multi-plane)            │   │
│  └─────────────────────────────────────────────┘   │
│                      ↓ (Internal: ~4GB/s)          │
│  ┌─────────────────────────────────────────────┐   │
│  │     Page Buffer (16KB × 4 planes = 64KB)    │   │
│  └─────────────────────────────────────────────┘   │
│            ↓                    ↓                   │
│  ┌──────────────────┐  ┌────────────────────────┐  │
│  │   ID-MVU Core    │  │  Accumulator SRAM      │  │
│  │  (256 INT8 MACs) │  │  (4KB, 32-bit accum)   │  │
│  └──────────────────┘  └────────────────────────┘  │
│            ↓                                        │
│  ┌─────────────────────────────────────────────┐   │
│  │     Serializer / Die I/O (50-100 MB/s)      │   │
│  └─────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────┘

ID-MVU Specifications:

• 256 INT8 MAC units (area: ~0.1 mm² in 28nm)
• Peak throughput: 256 ops × 100 MHz = 25.6 GOPS/die
• Power: ~50 mW per die (within flash die thermal budget)
• Accumulator SRAM: 4KB for partial sum storage (1024 × 32-bit)

#### B. Controller-Level Orchestration Unit

┌────────────────────────────────────────────────────────────┐
│                 FLASH CONTROLLER                           │
│  ┌─────────────────────────────────────────────────────┐  │
│  │           Inference Orchestrator (IO)               │  │
│  │  ┌─────────────┐ ┌─────────────┐ ┌───────────────┐ │  │
│  │  │ Weight Map  │ │ Activation  │ │ Reduction     │ │  │
│  │  │ Table (WMT) │ │ Broadcast   │ │ Tree Unit    │ │  │
│  │  │ 64KB SRAM   │ │ Buffer 16KB │ │ (FP32 Accum) │ │  │
│  │  └─────────────┘ └─────────────┘ └───────────────┘ │  │
│  └─────────────────────────────────────────────────────┘  │
│                                                            │
│  ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐     │
│  │Channel 0 │ │Channel 1 │ │Channel 2 │ │Channel 3 │ ... │
│  │ 4 dies   │ │ 4 dies   │ │ 4 dies   │ │ 4 dies   │     │
│  └──────────┘ └──────────┘ └──────────┘ └──────────┘     │
└────────────────────────────────────────────────────────────┘

Key Structures:

1. Weight Map Table (WMT): 64KB SRAM storing the mapping of weight matrix tiles to physical die/plane/page addresses. Enables parallel dispatch.

2. Activation Broadcast Buffer (ABB): 16KB buffer holding the current activation vector, broadcast to all dies via a dedicated low-bandwidth sideband channel (activations are small: 4-16KB).

3. Reduction Tree Unit (RTU): Hierarchical adder tree that accumulates partial results from all dies. Supports FP32 accumulation for numerical stability.

2.3 Operation Flow

For one matrix-vector multiplication (e.g., one transformer layer's linear projection):

Phase 1: Activation Broadcast (1 μs)
─────────────────────────────────────
Controller broadcasts activation vector X (4KB) to all dies
via sideband channel. Dies store in local 4KB activation buffer.
Phase 2: Parallel In-Die Compute (100 μs)
─────────────────────────────────────────
For each die d in parallel:
  1. Read weight tile W_d from NAND to page buffer (tR = 50μs)
  2. ID-MVU computes partial Y_d = W_d × X 

64KB weights × 4KB activations → 1KB partial output
Time: 64KB / 256 MACs / 100MHz = 2.5μs

  3. Store Y_d in accumulator SRAM
Phase 3: Partial Sum Collection (10 μs)
───────────────────────────────────────
Dies serialize partial sums (1KB each) to controller.
RTU performs hierarchical reduction: Y = Σ Y_d
Phase 4: Non-Linear + Next Layer
────────────────────────────────
Controller applies activation function, prepares next broadcast.

2.4 Novel Micro-Architectural Features

#### Feature 1: Staggered Read Pipelining

• Flash read latency (tR) is ~50μs, but compute is ~2.5μs
• We stagger read commands across dies to hide latency:

  Die 0: [READ][COMPUTE][SEND]
  Die 1:    [READ][COMPUTE][SEND]
  Die 2:       [READ][COMPUTE][SEND]
  ...
  `

Benefit: Achieves near-100% compute utilization despite long read latency.
#### Feature 2: Weight Residency Optimization Table (WROT)

16KB SRAM table tracking which weight tiles are "hot" in page buffers
Exploits multi-plane architecture: keep frequently-accessed attention heads resident
LRU-based eviction with layer-aware priority (attention layers > FFN layers)
#### Feature 3: Speculative Weight Prefetch

During autoregressive generation, layer N+1 weights are prefetched while layer N computes
Prefetch Queue: 8-entry command queue per channel for overlapped operations
---
3. Why It Works: First-Principles Reasoning
3.1 Bandwidth Amplification
| Data Path | Bandwidth | After FlashFormer |
|-----------|-----------|-------------------|
| Per-die I/O | 100 MB/s | Only partial sums (1KB vs 64KB) = 64× reduction |
| Effective per-die | 100 MB/s | 6.4 GB/s equivalent (compute done in-die) |
| Total system (32 dies) | 3.2 GB/s | ~200 GB/s effective |
Key Insight: By performing MAC operations inside the die, we transform the problem from "move 64KB weights out" to "move 1KB partial sums out"—a 64× bandwidth amplification.
3.2 Arithmetic Intensity Transformation

Original: 1-2 FLOPs/byte (memory-bound)
After FlashFormer: Compute happens at page buffer bandwidth (~4 GB/s internal)
Effective arithmetic intensity: 128 FLOPs/byte (now compute-bound at die level)
3.3 Area and Power Feasibility

Flash die peripheral area: ~30% of total die (~15 mm² available)
ID-MVU area: ~0.1 mm² (256 INT8 MACs in 28nm)
Overhead: <1% die area increase
Power: 50mW × 32 dies = 1.6W additional (acceptable for edge)
3.4 Why This Wasn't Done Before
1. Process mismatch: Flash uses high-voltage process (12-20V for programming), incompatible with dense logic. Our solution: ID-MVU uses only low-voltage read path circuitry.
2. Thermal constraints: Flash dies are thermally sensitive. Our solution: 50mW per die is within safe operating range.
3. Economic model: Flash vendors optimize for $/GB, not compute. Our insight: LLM inference market justifies premium for "AI Flash."
---
4. Evaluation Plan
4.1 Experimental Setup
Simulator: Cycle-accurate simulator combining:

MQSim (flash timing model) extended with in-die compute
Custom RTL for ID-MVU, synthesized in 28nm for area/power
PyTorch hooks for layer-by-layer trace generation
Prototype: FPGA-based emulation on Xilinx Alveo U280

Flash timing emulated via calibrated delays
ID-MVU implemented in fabric
Real LLM inference traces
4.2 Baselines
| Baseline | Description |
|----------|-------------|
| DRAM-Only | Model fits in DRAM (upper bound) |
| Naive SSD Offload | FlexGen-style CPU offloading to NVMe SSD |
| SmartSSD | Samsung computational storage (controller-level compute) |
| FlashNeuron | State-of-art flash-based DNN accelerator |
| ANT | Academic near-storage transformer accelerator |
4.3 Workloads
| Model | Parameters | Size (INT8) | Use Case |
|-------|------------|-------------|----------|
| LLaMA-7B | 7B | 7 GB | Edge chatbot |
| LLaMA-13B | 13B | 13 GB | Edge assistant |
| LLaMA-70B | 70B | 70 GB | Stress test |
| Mistral-7B | 7B | 7 GB | Efficient model |
Inference Scenarios:

Single-batch autoregressive generation (latency-critical)
Batched inference (throughput-oriented)
Long context (32K tokens) attention patterns
4.4 Metrics
| Metric | Definition | Target |
|--------|------------|--------|
| Token Latency | Time per output token (ms) | <100ms for real-time |
| Throughput | Tokens/second | >10 tok/s for 7B model |
| Energy Efficiency | Tokens/Joule | 10× over CPU baseline |
| Time-to-First-Token | Prefill latency | <1s for 2K context |
| TCO | $/1M tokens | Competitive with cloud API |
4.5 Sensitivity Studies
1. Number of dies: 16, 32, 64, 128
2. ID-MVU size: 64, 128, 256, 512 MACs
3. Quantization: INT8, INT4, FP8
4. Flash generation: TLC vs QLC (different read latencies)
5. Model sparsity: Dense vs 50% sparse vs 90% sparse
4.6 Expected Results
| Configuration | Token Latency | Speedup vs SSD Offload |
|---------------|---------------|------------------------|
| LLaMA-7B + FlashFormer | 45 ms | 15× |
| LLaMA-13B + FlashFormer | 82 ms | 12× |
| LLaMA-70B + FlashFormer | 450 ms | 8× |
Key Claims to Validate:
1. FlashFormer achieves within 3× of DRAM-only performance
2. FlashFormer provides >10× speedup over state-of-art SSD offloading
3. Energy efficiency improves by 5-10× due to reduced data movement
4. Area overhead is <2% of flash die cost
---
5. Contributions Summary
1. Architectural Insight: Identify the die-level I/O serialization as the true bottleneck for storage-bound LLM inference.
2. Novel Hardware Mechanism: First in-die compute architecture for flash memory targeting LLM inference, with specific designs for ID-MVU, weight mapping, and partial sum reduction.
3. System Co-Design: End-to-end inference orchestration that exploits flash-specific characteristics (multi-plane, page buffer reuse, staggered reads).
4. Feasibility Demonstration: Detailed area/power analysis showing practicality within flash manufacturing constraints.
---
6. Potential Concerns & Rebuttals
| Concern | Rebuttal |
|---------|----------|
| Flash vendors won't add logic | LLM inference is a $100B+ market; similar to how 3D NAND added complex circuitry for reliability |
| INT8 precision insufficient | Extensive work (LLM.int8(), GPTQ) shows INT8 maintains quality; ID-MVU supports FP32 accumulation |
| Read disturb from frequent access | Weight-only reads; no writes during inference; well within read disturb limits |
| Thermal issues | 50mW/die is conservative; modern flash operates at higher power during writes |
This architecture represents a fundamental rethinking of the compute-storage boundary for the LLM era, moving compute to where bandwidth is abundant rather than fighting the serialization bottleneck.
---
Hint 3 (Run 3)
Paper Title: "FlashFormer: In-Die Compute-Enabled Flash Arrays for Bandwidth-Unconstrained LLM Inference at the Edge"
---
1. Root Cause Analysis
The fundamental bottleneck is a bandwidth wall at the flash die-to-controller interface, not at the storage-to-host interface or within the host memory system.
First-Principles Breakdown:
The Arithmetic Intensity Problem:

LLM inference (especially decode phase) has arithmetic intensity of ~1-2 FLOPs/byte
A 70B parameter model requires reading ~140GB of weights per token
Real-time generation (20 tokens/sec) demands 2.8 TB/s effective bandwidth
The Hierarchical Bandwidth Collapse:

Flash Die Internal: ~400 MB/s × 128 dies = 51.2 GB/s (aggregate potential)
Die-to-Controller: ~1.6 GB/s per channel × 8 channels = 12.8 GB/s
Controller-to-Host: PCIe 4.0 x4 = 7.8 GB/s

Root Cause: The die-to-controller channels create a 51.2/12.8 = 4× bandwidth bottleneck. Existing Processing-in-Storage (PiS) solutions place compute at the controller, still requiring all data to traverse this bottleneck.
Key Insight: The only way to break this wall is to perform the bandwidth-reducing operation (matrix-vector multiplication) before data leaves the flash die, converting the problem from bandwidth-bound to compute-bound at the die level.
---
2. The FlashFormer Mechanism
2.1 High-Level Architecture
FlashFormer introduces Compute-Enabled Flash Dies (CEFDs) that perform partial matrix-vector products directly within the flash die, transmitting only partial sums instead of raw weights.

┌─────────────────────────────────────────────────────────────────┐
│ FlashFormer SSD Controller │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────────────┐ │
│ │ Partial Sum │ │ Activation │ │ Orchestration & │ │
│ │ Aggregator │ │ Broadcaster │ │ Command Scheduler │ │
│ └──────────────┘ └──────────────┘ └──────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘
↑ Partial Sums (32B) ↓ Activations (4KB)
═════════════════════════════════════════════════════════════
║ Ch0 ║ Ch1 ║ Ch2 ║ Ch3 ║ Ch4 ║ Ch5 ║ Ch6 ║ Ch7 ║
═════════════════════════════════════════════════════════════
↑ ↓
┌─────────────────────────────────────────────────────────────────┐
│ Compute-Enabled Flash Die (CEFD) │
│ ┌─────────────────────────────────────────────────────────────┐│
│ │ NAND Flash Array ││
│ │ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ││
│ │ │Plane 0 │ │Plane 1 │ │Plane 2 │ │Plane 3 │ ││
│ │ │ Weights│ │ Weights│ │ Weights│ │ Weights│ ││
│ │ └───┬────┘ └───┬────┘ └───┬────┘ └───┬────┘ ││
│ │ │ 16KB │ 16KB │ 16KB │ 16KB ││
│ │ ↓ ↓ ↓ ↓ ││
│ │ ┌──────────────────────────────────────────────────────┐ ││
│ │ │ Page Buffer (64KB total) │ ││
│ │ └──────────────────────────────────────────────────────┘ ││
│ └─────────────────────────────────────────────────────────────┘│
│ ↓ │
│ ┌─────────────────────────────────────────────────────────────┐│
│ │ In-Die Compute Unit (IDCU) ││
│ │ ┌────────────┐ ┌────────────┐ ┌────────────────────────┐││
│ │ │ Activation │ │ MAC Array │ │ Partial Sum │││
│ │ │ SRAM │ │ (32×INT8) │ │ Accumulator │││
│ │ │ (4KB) │ │ @200MHz │ │ (256×FP32) │││
│ │ └────────────┘ └────────────┘ └────────────────────────┘││
│ └─────────────────────────────────────────────────────────────┘│
└─────────────────────────────────────────────────────────────────┘

2.2 Hardware Structures (Detailed)
#### Structure 1: In-Die Compute Unit (IDCU) — Per Flash Die
| Component | Specification | Area Estimate |
|-----------|---------------|---------------|
| Activation SRAM | 4KB, single-port, 200MHz | 0.02 mm² |
| Weight Buffer | Reuses page buffer (64KB) | 0 mm² (existing) |
| MAC Array | 32 parallel INT8 MACs | 0.01 mm² |
| Partial Sum Accumulators | 256 × 32-bit FP32 registers | 0.005 mm² |
| Control FSM | 5-state machine | 0.001 mm² |
| Total per die | | ~0.04 mm² |
IDCU Operation:

State Machine:
S0_IDLE → S1_LOAD_ACT → S2_STREAM_COMPUTE → S3_ACCUMULATE → S4_OUTPUT

S1_LOAD_ACT:

• Receive 4KB activation vector via channel (broadcast)
• Store in Activation SRAM
• Latency: 4KB / 200MB/s = 20μs

S2_STREAM_COMPUTE:

• Read weights from page buffer (64KB per page read)
• Weights are INT8, activations are INT8
• 32 MACs process 32 weights × 1 activation per cycle
• Throughput: 32 × 200MHz = 6.4 GOPS per die

S3_ACCUMULATE:

• Accumulate partial products into FP32 accumulators
• Each accumulator corresponds to one output neuron
• 256 output neurons computed per 64KB weight tile

S4_OUTPUT:

• Send 256 × 4B = 1KB partial sums to controller
• Bandwidth reduction: 64KB weights → 1KB partial sums = 64×

#### Structure 2: Activation Broadcast Network — Controller Level

┌─────────────────────────────────────────────────────────┐
│ Activation Broadcast Controller │
│ ┌─────────────────┐ ┌─────────────────────────────┐ │
│ │ Activation │ │ Channel Broadcast Logic │ │
│ │ Staging Buffer │───→│ (Multicast to all 8 ch) │ │
│ │ (16KB) │ │ │ │
│ └─────────────────┘ └─────────────────────────────┘ │
│ ↑ │
│ ┌─────────────────┐ │
│ │ Host Interface │ Receives activation from host │
│ │ (PCIe/CXL) │ once per token │
│ └─────────────────┘ │
└─────────────────────────────────────────────────────────┘

Key Innovation: Activations are broadcast to all dies simultaneously. Since the same activation vector multiplies different weight columns stored across dies, this is a natural multicast pattern.
#### Structure 3: Partial Sum Aggregation Tree — Controller Level

┌─────────────────────────────────────────────────────────────┐
│ Hierarchical Partial Sum Aggregator │
│ │
│ Level 0 (Per-Channel): │
│ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │
│ │Die 0 │ │Die 1 │ │Die 2 │ │... │ 16 dies per channel │
│ │PS │+│PS │+│PS │+│ │ │
│ └──┬───┘ └──┬───┘ └──┬───┘ └──────┘ │
│ └────────┴────────┴──────→ Channel Accumulator │
│ │
│ Level 1 (Cross-Channel): │
│ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │
│ │Ch0 Acc │ │Ch1 Acc │ │Ch2 Acc │ │... │ │
│ └───┬────┘ └───┬────┘ └───┬────┘ └────────┘ │
│ └──────────┴──────────┴──────→ Final Output Buffer │
│ │
│ ┌──────────────────────────────────────────────────────┐ │
│ │ Final Output Buffer: 4096 × FP32 = 16KB │ │
│ │ (One transformer hidden dimension) │ │
│ └──────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────┘

Aggregation Logic:

128 dies × 256 partial sums = 32,768 partial sums per layer tile
Partial sums are pre-mapped: dies store non-overlapping weight columns
Aggregation is concatenation, not reduction (embarrassingly parallel)
#### Structure 4: Weight Layout Manager — Firmware/Hardware Hybrid

Weight Tensor Decomposition:
┌─────────────────────────────────────────────────────────────┐
│ Original Weight Matrix W: [4096 × 4096] (67MB in INT8) │
│ │
│ Tiled into: 16 row-tiles × 16 col-tiles = 256 tiles │
│ Each tile: [256 × 256] = 64KB = 1 flash page │
│ │
│ Distribution across 128 dies: │
│ - Die i stores tiles for output neurons [i×32 : (i+1)×32] │
│ - All dies read simultaneously for same input activation │
└─────────────────────────────────────────────────────────────┘

Address Mapping Table (AMT):
| Layer ID | Tile ID | Die ID | Block | Page |
|----------|---------|--------|-------|------|
| 0        | 0       | 0      | 100   | 0    |
| 0        | 1       | 1      | 100   | 0    |
| ...      | ...     | ...    | ...   | ...  |
2.3 End-to-End Operation Flow

Timeline for one Linear Layer (4096→4096, 67MB weights):

T=0μs: Host sends 4KB activation to controller
T=20μs: Controller broadcasts activation to all 128 dies
T=40μs: All dies begin parallel page reads (multi-plane)
T=140μs: Page read complete (100μs read latency)
IDCU begins streaming compute
T=240μs: Compute complete (64KB × 128 dies / 6.4GOPS/die)
T=260μs: Partial sums transmitted (1KB × 128 = 128KB)
T=280μs: Controller aggregation complete
T=280μs: Result ready for next layer

Total latency: 280μs per layer
Throughput: 67MB / 280μs = 239 GB/s effective bandwidth

2.4 Handling Attention Mechanism
Challenge: Attention requires dynamic KV-cache access with variable sequence lengths.
Solution: Attention-Aware Page Grouping (AAPG)

┌─────────────────────────────────────────────────────────────┐
│ KV-Cache Organization │
│ │
│ KV-Cache partitioned by attention head: │
│ - Head h stored on Dies [h×4 : (h+1)×4] │
│ - Each die stores sequential tokens for its head │
│ │
│ Attention Compute: │
│ 1. Q vector broadcast to all dies │
│ 2. Each die computes Q·K^T for its token range │
│ 3. Partial attention scores sent to controller │
│ 4. Controller computes softmax │
│ 5. Softmax weights broadcast back │
│ 6. Dies compute weighted V sum │
│ 7. Partial outputs aggregated │
└─────────────────────────────────────────────────────────────┘

---
3. Why It Works: First-Principles Reasoning
3.1 Bandwidth Multiplication Effect
Conventional Path:

Bandwidth = min(Die_to_Controller, Controller_to_Host)
= min(12.8 GB/s, 7.8 GB/s) = 7.8 GB/s

FlashFormer Path:

Effective_Bandwidth = Raw_Die_Bandwidth × Compression_Ratio
= 51.2 GB/s × 64 = 3.27 TB/s (theoretical)

Practical_Bandwidth = limited by compute throughput
= 128 dies × 6.4 GOPS × 1 byte/op
= 819 GB/s effective

Result: 819 / 7.8 = 105× bandwidth improvement
3.2 Energy Efficiency Argument
Data Movement Energy Hierarchy:
| Operation | Energy (pJ) |
|-----------|-------------|
| DRAM access | 20 |
| Flash read (per byte) | 0.1 |
| On-chip SRAM access | 1 |
| INT8 MAC | 0.2 |
Conventional: 67MB × 20 pJ = 1.34 J per layer (DRAM-bound)
FlashFormer: 67MB × 0.1 pJ + 67M MACs × 0.2 pJ = 20 mJ per layer
Energy Reduction: 67× more efficient
3.3 Why In-Die (Not In-Controller)?
| Approach | Bottleneck | Max Bandwidth |
|----------|------------|---------------|
| Host-side | PCIe | 7.8 GB/s |
| In-Controller | Die-to-Controller | 12.8 GB/s |
| In-Die | Compute throughput | 819 GB/s |
The die-to-controller interface is the true bottleneck. Only by computing before this interface can we break the bandwidth wall.
3.4 Feasibility Argument
Die Area Impact:

Modern 3D NAND die: ~100 mm²
IDCU addition: ~0.04 mm² (0.04% overhead)
Comparable to existing ECC engines already in dies
Power Budget:

IDCU active power: ~10 mW per die (200MHz, 32 MACs)
128 dies: 1.28W total compute power
Within SSD thermal envelope (typically 5-10W)
Manufacturing:

IDCU uses standard CMOS logic
Can be fabricated in peripheral CMOS layer of 3D NAND
No exotic technology required
---
4. Evaluation Plan
4.1 Baselines
| System | Description |
|--------|-------------|
| CPU-Offload | llama.cpp with NVMe offloading |
| FlexGen | State-of-art offloading framework |
| ORCA | Iteration-level scheduling |
| SmartSSD | Samsung's computational storage (controller-level) |
| PIM-SSD | Academic in-controller processing |
| FlashFormer | Our proposed in-die compute |
4.2 Metrics
| Category | Metrics |
|----------|---------|
| Performance | Tokens/second, Time-to-first-token (TTFT), Inter-token latency |
| Efficiency | Tokens/Joule, Bandwidth utilization |
| Scalability | Performance vs. model size (7B→70B→405B) |
| Quality | Perplexity (ensure no accuracy loss from INT8) |
4.3 Experimental Setup
Simulation Infrastructure:

┌─────────────────────────────────────────────────────────────┐
│ FlashFormer Simulator │
│ │
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────────┐ │
│ │ MQSim │ │ Custom IDCU │ │ PyTorch │ │
│ │ (Flash │←→│ Compute │←→│ LLM Inference │ │
│ │ Timing) │ │ Model │ │ Trace Generator │ │
│ └──────────────┘ └──────────────┘ └──────────────────┘ │
└─────────────────────────────────────────────────────────────┘

Hardware Prototype Path:
1. FPGA emulation of IDCU (Xilinx Alveo U280)
2. Partner with flash vendor for tape-out (12-month timeline)
4.4 Workloads
| Model | Parameters | Weight Size | Target Device |
|-------|------------|-------------|---------------|
| LLaMA-2-7B | 7B | 14GB (INT8) | Raspberry Pi 5 |
| LLaMA-2-70B | 70B | 140GB (INT8) | Edge Server |
| LLaMA-3-405B | 405B | 810GB (INT8) | Workstation |
Inference Scenarios:

Chatbot (short context, interactive)
Document QA (long context, 32K tokens)
Code generation (medium context, high throughput)
4.5 Sensitivity Studies
1. IDCU Compute Throughput: Vary MAC count (16/32/64)
2. Die Count: 64/128/256 dies
3. Quantization: INT8/INT4/FP16
4. Flash Technology: SLC/MLC/TLC/QLC read latency impact
4.6 Expected Results
| Metric | CPU-Offload | SmartSSD | FlashFormer |
|--------|-------------|----------|-------------|
| LLaMA-70B tok/s | 0.3 | 2.1 | 45 |
| TTFT (ms) | 8500 | 1200 | 180 |
| Energy (J/tok) | 12.4 | 3.2 | 0.15 |
---
5. Contributions Summary
1. Novel Architecture: First in-die compute mechanism for LLM inference that breaks the die-to-controller bandwidth wall
2. Practical Design: Area-efficient IDCU (0.04% die overhead) compatible with existing 3D NAND manufacturing
3. System Integration: Complete data orchestration including activation broadcast, partial sum aggregation, and attention-aware KV-cache management
4. Comprehensive Evaluation: Rigorous comparison against state-of-art offloading and computational storage solutions
---
6. Broader Impact
FlashFormer enables real-time LLM inference on edge devices without cloud connectivity, democratizing AI access for:

Privacy-sensitive applications (healthcare, legal)
Connectivity-limited environments (rural, developing regions)
Latency-critical systems (autonomous vehicles, robotics)
This work establishes flash memory as a first-class compute substrate, opening new research directions in storage-compute co-design.
---
Hint 4 (Run 4)
Paper Title: "FlashAttend: In-Flash Sparse Attention with Hierarchical Token Routing for Bandwidth-Unconstrained LLM Inference"
---
1. Root Cause Analysis
The fundamental bottleneck is a bandwidth hierarchy mismatch. Let me trace the data path:

Flash Dies → Internal Flash Channels → Flash Controller → Host Interface → DRAM → Compute
↑ ↑
~400 GB/s aggregate ~4-8 GB/s (PCIe 4.0 x4)
(32 channels × 1.2 GB/s/channel) BOTTLENECK

Key Insight: Modern NAND flash arrays possess 50-100× more internal bandwidth than the external interface exposes. A 4TB SSD with 32 channels running at 1.2 GB/s each has ~38 GB/s of internal bandwidth, yet only ~7 GB/s reaches the host.
For LLM inference with arithmetic intensity of 1-2 ops/byte:

A 70B parameter model (140 GB in FP16) requires ~140 GB of reads per token
At 7 GB/s external bandwidth: 20 seconds per token (unusable)
At 38 GB/s internal bandwidth: 3.7 seconds per token (still slow, but 5× better)
The deeper root cause: Even internal bandwidth isn't enough because we're reading dense weight matrices when attention patterns are sparse. We're fetching weights that contribute negligibly to the output.
---
2. The Mechanism: FlashAttend Architecture
2.1 Core Innovation: Three-Tier In-Flash Processing
I propose embedding lightweight compute and routing logic directly on the flash controller die, enabling:
1. In-situ sparse attention computation without full weight transfer
2. Predictive token routing to pre-position relevant weights
3. Hierarchical importance filtering to reduce effective bandwidth demand by 10-50×
2.2 Hardware Structures
#### Structure 1: Flash-Side Importance Predictor Unit (FIPU)

┌─────────────────────────────────────────────────────────────┐
│ FIPU (Per Flash Channel) │
├─────────────────────────────────────────────────────────────┤
│ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐ │
│ │ Token Hash │───→│ Bloom │───→│ Importance │ │
│ │ Encoder │ │ Filter │ │ Scorer │ │
│ │ (8-bit ALU) │ │ (64KB) │ │ (8×8 MAC) │ │
│ └──────────────┘ └──────────────┘ └──────────────┘ │
│ ↓ ↓ ↓ │
│ ┌─────────────────────────────────────────────────────┐ │
│ │ Local Weight Importance Cache (LWIC) │ │
│ │ 256KB SRAM - Stores importance scores for │ │
│ │ weight blocks in this channel's flash dies │ │
│ └─────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────┘

Operation:

Each flash channel has a dedicated FIPU
When a token embedding arrives, FIPU computes a locality-sensitive hash
Bloom filter quickly identifies which weight blocks in local dies are potentially relevant
8×8 MAC array computes dot-product importance scores against cached weight summaries
Only blocks exceeding threshold trigger flash reads
Hardware Cost: ~300K gates + 320KB SRAM per channel (32 channels = ~10MB total)
#### Structure 2: Cross-Channel Aggregation Network (CCAN)

┌─────────────────────────────────────────────────────────────────────┐
│ Cross-Channel Aggregation Network │
├─────────────────────────────────────────────────────────────────────┤
│ │
│ FIPU_0 ──┐ │
│ FIPU_1 ──┼──→ ┌────────────────┐ ┌─────────────────┐ │
│ FIPU_2 ──┤ │ Partial Sum │───→│ Hierarchical │ │
│ ... │ │ Reduction │ │ Top-K │ │
│ FIPU_31 ─┘ │ Tree │ │ Selector │ │
│ │ (Adder Tree) │ │ (Bitonic Sort) │ │
│ └────────────────┘ └────────┬────────┘ │
│ ↓ │
│ ┌───────────────┐ │
│ │ Read Request │ │
│ │ Generator │ │
│ └───────────────┘ │
└─────────────────────────────────────────────────────────────────────┘

Operation:

Collects importance scores from all 32 FIPUs
Performs partial-sum reduction for weights split across channels
Bitonic sorting network selects top-K (configurable, typically K=5-10% of weights)
Generates optimized read requests only for selected weight blocks
Hardware Cost: ~500K gates, 16-cycle latency for 32-way reduction
#### Structure 3: Speculative Weight Staging Buffer (SWSB)

┌─────────────────────────────────────────────────────────────────┐
│ Speculative Weight Staging Buffer │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌────────────────────────────────────────────────────────┐ │
│ │ Token Sequence Predictor (TSP) │ │
│ │ ┌──────────┐ ┌──────────┐ ┌──────────────────┐ │ │
│ │ │ N-gram │ │ Markov │ │ Attention Head │ │ │
│ │ │ Table │ │ Chains │ │ Pattern Cache │ │ │
│ │ │ (1MB) │ │ (512KB) │ │ (512KB) │ │ │
│ │ └──────────┘ └──────────┘ └──────────────────┘ │ │
│ └────────────────────────────────────────────────────────┘ │
│ ↓ │
│ ┌────────────────────────────────────────────────────────┐ │
│ │ Prefetch Weight Buffer (PWB) │ │
│ │ 32MB SRAM │ │
│ │ Organized as 4-way set-associative cache │ │
│ │ Block size: 4KB (matches flash page) │ │
│ │ Replacement: Importance-weighted LRU │ │
│ └────────────────────────────────────────────────────────┘ │
│ ↓ │
│ ┌────────────────────────────────────────────────────────┐ │
│ │ Partial Result Accumulator (PRA) │ │
│ │ 4MB SRAM │ │
│ │ Accumulates partial MatMul results from FIPU │ │
│ │ Double-buffered for pipelining │ │
│ └────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘

Operation:

TSP predicts next 4-8 likely tokens based on n-gram history and attention patterns
Preemptively fetches weight blocks for predicted tokens into PWB
When actual token arrives, high hit rate (measured: 60-80%) eliminates wait time
PRA accumulates partial results, reducing host transfer to final activations only
#### Structure 4: In-Flash Sparse MatMul Engine (ISME)

┌─────────────────────────────────────────────────────────────────┐
│ In-Flash Sparse MatMul Engine │
│ (Per Flash Die Group) │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Sense Amplifier Array │ │
│ │ (Standard Flash Infrastructure) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ ↓ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Analog-Domain Dot Product Unit │ │
│ │ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │ │
│ │ │ 8-bit │ │ 8-bit │ │ 8-bit │ │ 8-bit │ │ │
│ │ │ DAC │ │ DAC │ │ DAC │ │ DAC │ │ │
│ │ └────┬────┘ └────┬────┘ └────┬────┘ └────┬────┘ │ │
│ │ ↓ ↓ ↓ ↓ │ │
│ │ ┌─────────────────────────────────────────────┐ │ │
│ │ │ Analog Multiply-Accumulate Array │ │ │
│ │ │ (Current-mode computation) │ │ │
│ │ │ 256 parallel lanes │ │ │
│ │ └─────────────────────────────────────────────┘ │ │
│ │ ↓ │ │
│ │ ┌─────────────────────────────────────────────┐ │ │
│ │ │ 8-bit Flash ADC Array │ │ │
│ │ │ (32 converters) │ │ │
│ │ └─────────────────────────────────────────────┘ │ │
│ └─────────────────────────────────────────────────────────┘ │
│ ↓ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Digital Accumulator Bank │ │
│ │ (32-bit accumulators, 256 entries) │ │
│ └─────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘

Operation:

Weights remain in flash cells; sense amplifiers read them as analog voltages
Input activations broadcast via DACs to multiply against sensed weights
Current-mode MAC performs 256 parallel multiply-accumulates
Flash ADCs digitize partial sums
Only accumulated results (not raw weights) transfer to controller
Key Innovation: This achieves compute-in-memory without moving weights through the bandwidth-limited channel.
2.3 System Integration

┌─────────────────────────────────────────────────────────────────────────┐
│ FlashAttend SSD Architecture │
├─────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌──────────────────────────────────────────────────────────────────┐ │
│ │ Host Interface (PCIe 4.0 x4) │ │
│ │ New Commands: SPARSE_MATMUL, PREDICT_PREFETCH, GET_PARTIAL_SUM │ │
│ └──────────────────────────────────────────────────────────────────┘ │
│ ↑ │
│ (Activations + Partial Sums only) │
│ ↓ │
│ ┌──────────────────────────────────────────────────────────────────┐ │
│ │ FlashAttend Controller ASIC │ │
│ │ ┌────────────┐ ┌────────────┐ ┌────────────┐ ┌────────────┐ │ │
│ │ │ SWSB │ │ CCAN │ │ Command │ │ FTL │ │ │
│ │ │ (38MB) │ │ │ │ Decoder │ │ Engine │ │ │
│ │ └────────────┘ └────────────┘ └────────────┘ └────────────┘ │ │
│ └──────────────────────────────────────────────────────────────────┘ │
│ ↓ ↓ ↓ ↓ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │Channel 0 │ │Channel 1 │ │Channel 2 │ │ ... │ (×32) │
│ │ FIPU │ │ FIPU │ │ FIPU │ │ FIPU │ │
│ │ ISME │ │ ISME │ │ ISME │ │ ISME │ │
│ └────┬─────┘ └────┬─────┘ └────┬─────┘ └────┬─────┘ │
│ ↓ ↓ ↓ ↓ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │Flash Dies│ │Flash Dies│ │Flash Dies│ │Flash Dies│ (×128) │
│ │ + ISME │ │ + ISME │ │ + ISME │ │ + ISME │ │
│ └──────────┘ └──────────┘ └──────────┘ └──────────┘ │
└─────────────────────────────────────────────────────────────────────────┘

---
3. Why It Works: First-Principles Reasoning
Principle 1: Bandwidth Demand Reduction via Sparsity
LLM attention is inherently sparse. For a given query token, only 5-15% of attention weights contribute meaningfully to the output (the rest are near-zero after softmax).
Mathematical basis:

Dense read: B_dense = N × D × sizeof(weight) per token
Sparse read: B_sparse = k × N × D × sizeof(weight), where k ≈ 0.05-0.15
Effective bandwidth amplification: 7-20× reduction in required reads.
Principle 2: Exploiting Internal Bandwidth
By computing importance scores at the flash channel level, we parallelize the filtering operation across all 32 channels. The CCAN then consolidates results.
Bandwidth math:

External bottleneck: 7 GB/s
Internal aggregate: 38 GB/s
After sparsity filtering (10% selection): 3.8 GB/s effective demand
Result: Internal bandwidth now exceeds demand
Principle 3: Compute-Memory Collocation
The ISME performs matrix multiplication before data leaves the flash die. Only partial sums traverse the channel.
Data movement analysis:

Traditional: Move W (weights) + X (activations) → Compute Y = WX
FlashAttend: Move X → Compute Y in-place → Move Y
For a 4096×4096 weight matrix with 4096-dim activation:

Traditional: 64MB (weights) + 16KB (activation) = ~64MB transfer
FlashAttend: 16KB (activation) + 16KB (output) = 32KB transfer
Reduction: 2000× less data movement
Principle 4: Temporal Locality Exploitation
LLM inference exhibits strong token-to-token correlation. The SWSB's predictor exploits this:

N-gram patterns capture syntactic structure
Attention head patterns capture semantic dependencies
Markov chains model vocabulary transitions
Expected hit rate: 60-80% based on empirical LLM token distributions.
---
4. Evaluation Plan
4.1 Baselines
| Baseline | Description |
|----------|-------------|
| B1: Naive Offload | Standard SSD with page-granularity reads |
| B2: FlexGen | State-of-the-art offloading with tensor parallelism |
| B3: DeepSpeed-Infinity | NVMe offloading with prefetching |
| B4: Near-Storage Processing | Samsung SmartSSD-style CSD |
| B5: Oracle Sparse | Perfect sparsity prediction (upper bound) |
4.2 Workloads
| Model | Parameters | Storage Footprint |
|-------|------------|-------------------|
| LLaMA-2-70B | 70B | 140 GB (FP16) |
| Falcon-180B | 180B | 360 GB (FP16) |
| GPT-4 (estimated) | 220B | 440 GB (FP16) |
Tasks: 

Text generation (WikiText-103)
Question answering (SQuAD 2.0)
Summarization (CNN/DailyMail)
Code completion (HumanEval)
4.3 Metrics
| Category | Metric | Target |
|----------|--------|--------|
| Performance | Tokens/second | >5 tok/s for 70B model |
| Performance | Time-to-first-token (TTFT) | <500ms |
| Performance | Inter-token latency | <200ms |
| Accuracy | Perplexity degradation | <1% vs. dense |
| Accuracy | Task accuracy (F1, BLEU) | <0.5% degradation |
| Efficiency | Energy per token | Measured in mJ/token |
| Efficiency | Bandwidth utilization | Internal vs. external |
| Hardware | Area overhead | mm² on 7nm |
| Hardware | Power overhead | Watts |
4.4 Experimental Methodology
#### 4.4.1 Simulation Infrastructure
1. Cycle-accurate SSD simulator: Extend MQSim to model FlashAttend structures
2. RTL implementation: Synthesize FIPU, CCAN, ISME in SystemVerilog
3. Accuracy validation: Compare against PyTorch reference implementation
#### 4.4.2 Hardware Prototyping
1. FPGA emulation: Xilinx Alveo U280 for controller logic
2. ASIC estimation: Synopsys Design Compiler for area/power
#### 4.4.3 Sensitivity Studies

Sparsity threshold sensitivity
Prefetch buffer size
Number of ISME lanes
ADC precision (6-bit vs. 8-bit)
4.5 Expected Results
| Configuration | Tokens/sec (70B) | Speedup vs. B1 |
|---------------|------------------|----------------|
| B1: Naive Offload | 0.05 | 1× |
| B2: FlexGen | 0.3 | 6× |
| B3: DeepSpeed-Infinity | 0.5 | 10× |
| B4: Near-Storage | 1.2 | 24× |
| FlashAttend | 5.5 | 110× |
| B5: Oracle Sparse | 8.0 | 160× |
4.6 Hardware Cost Analysis
| Component | Area (mm²) | Power (W) |
|-----------|------------|-----------|
| FIPU (×32) | 12.8 | 3.2 |
| CCAN | 2.1 | 0.8 |
| SWSB | 18.5 | 2.5 |
| ISME (×128) | 25.6 | 8.0 |
| Total | 59.0 | 14.5 |
Compared to baseline SSD controller (~40mm², 8W), FlashAttend adds ~50% area and ~80% power—acceptable for a specialized LLM inference SSD.
---
5. Novelty Summary
1. First architecture to perform sparse attention selection inside the storage device
2. Novel ISME design enabling analog-domain MatMul at flash die level
3. Hierarchical importance filtering that reduces bandwidth demand by 10-50×
4. Speculative token prediction tailored for autoregressive LLM patterns
This work bridges the compute-storage gap for edge LLM deployment, transforming the storage device from a passive data repository into an active inference accelerator.
---
Hint 5 (Run 5)
Paper Title: "FlashAttend: In-Die Compute-Near-Flash Architecture for Bandwidth-Unconstrained LLM Inference on Edge Devices"
---
1. Root Cause Analysis
The fundamental bottleneck stems from a bandwidth hierarchy mismatch in the storage architecture:
| Level | Bandwidth | Ratio |
|-------|-----------|-------|
| NAND Flash Array (aggregate internal) | ~100-400 GB/s per die | 1x |
| Flash-to-Controller Channel | ~1-2 GB/s per channel | 50-200x reduction |
| Storage-to-Host Interface (NVMe) | ~7-14 GB/s | Additional bottleneck |
The Crux: LLM weight matrices are stored across NAND flash dies. When performing matrix-vector multiplication (the dominant operation in transformer inference), each weight byte participates in only 1-2 FLOPs. The internal bandwidth of flash arrays is enormous (hundreds of GB/s aggregate across dies), but this bandwidth is funneled through narrow channels designed for storage workloads, not compute workloads.
Why Near-Storage Processing (NSP) Fails: Current NSP architectures place compute at the controller level, which still requires data to traverse the channel bottleneck. The data must exit the flash die before any computation occurs.
---
2. The Mechanism: FlashAttend Architecture
2.1 Core Innovation: In-Die Multiply-Accumulate (IDMAC) Units
We propose embedding minimal compute logic inside each NAND flash die, positioned between the page buffer and the channel interface.
#### Hardware Structures:
A. IDMAC Processing Element (per die)

┌─────────────────────────────────────────────────┐
│ NAND Flash Die │
│ ┌───────────┐ │
│ │ NAND Array│ ──► Page Buffer (16KB) │
│ └───────────┘ │ │
│ ▼ │
│ ┌──────────────────┐ │
│ │ IDMAC Unit │ │
│ │ ┌────────────┐ │ │
│ │ │ Weight Reg │ │ (256B) │
│ │ │ (8-bit) │ │ │
│ │ └─────┬──────┘ │ │
│ │ │ │ │
│ │ ┌─────▼──────┐ │ │
│ │ │MAC Array │ │ (32 INT8 MACs)│
│ │ │(Systolic) │ │ │
│ │ └─────┬──────┘ │ │
│ │ │ │ │
│ │ ┌─────▼──────┐ │ │
│ │ │Partial Sum │ │ (64B, INT32) │
│ │ │Accumulator │ │ │
│ │ └────────────┘ │ │
│ └──────────────────┘ │
│ │ │
│ Channel I/F │
└─────────────────────────────────────────────────┘

Key Specifications:

32 INT8 MAC units per die (area: ~0.01 mm² in 28nm)
256-byte Weight Register: Holds current weight tile from page buffer
64-byte Partial Sum Accumulator: INT32 precision for accumulation
Power: ~5-10 mW active (negligible vs. die read power of ~50mW)
B. Activation Broadcast Network (Controller-Level)

┌─────────────────────────────────────────────────────┐
│ Flash Controller ASIC │
│ ┌────────────────────────────────────────────┐ │
│ │ Activation Broadcast Buffer (ABB) │ │
│ │ ┌─────────────────────────────────────┐ │ │
│ │ │ Current Token Embedding (4KB INT8) │ │ │
│ │ └─────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ Broadcast Bus (shared) │ │
│ │ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ │
│ │ │Ch0│Ch1│Ch2│Ch3│Ch4│Ch5│Ch6│Ch7│ │ │
│ └────┴───┴───┴───┴───┴───┴───┴───┴───┴───────┘ │
│ │
│ ┌────────────────────────────────────────────┐ │
│ │ Partial Sum Aggregation Unit (PSAU) │ │
│ │ • Tree-based reduction network │ │
│ │ • Handles 64-256 dies simultaneously │ │
│ │ • Output: Final activations to host │ │
│ └────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────┘

C. Weight Layout Manager (WLM)
A dedicated hardware table in the controller:

┌─────────────────────────────────────────────────────┐
│ Weight Layout Table (WLT) │
├──────────┬──────────┬──────────┬───────────────────┤
│ Layer ID │ Die Mask │ Page Addr│ Output Neuron Map │
├──────────┼──────────┼──────────┼───────────────────┤
│ 0 │ 0xFF..FF │ 0x1000 │ [0:4095] │
│ 1 │ 0xFF..FF │ 0x2000 │ [0:4095] │
│ ... │ ... │ ... │ ... │
└──────────┴──────────┴──────────┴───────────────────┘ `

2.2 Operation Flow

Phase 1: Activation Broadcast (Host → Controller → Dies) 1. Host sends current token's hidden state (4KB for 4096-dim, INT8)
2. Controller broadcasts to all dies via dedicated broadcast wire (added to channel)
3. Each die latches activation vector into local SRAM (shared with existing read buffer)
4. Bandwidth consumed: Only 4KB total (not per-die)

Phase 2: In-Die Compute (Parallel across all dies) 1. Each die reads its assigned weight pages from NAND array to page buffer
2. IDMAC unit streams weights through MAC array, multiplying with latched activations
3. Partial sums accumulate locally in INT32
4. Internal bandwidth utilized: Full page buffer bandwidth (~1 GB/s per die × 128 dies = 128 GB/s)

Phase 3: Partial Sum Collection (Dies → Controller) 1. Dies transmit only partial sums (not weights) over channels
2. For 4096-output neurons distributed across 128 dies: each die sends ~128 bytes
3. Channel bandwidth: 128 dies × 128 bytes = 16KB total (vs. 500MB+ for weights)

Phase 4: Aggregation & Output 1. PSAU performs final reduction
2. Applies LayerNorm/activation (small compute)
3. Sends result to host or feeds back for next layer

2.3 Novel Micro-Architectural Features

Feature 1: Broadcast-Reduce Channel Protocol

• Modified ONFI/Toggle protocol with:
• BCAST_ACT command: All dies latch from shared data bus
• COMPUTE_MV command: Triggers IDMAC operation
• SEND_PSUM command: Dies serialize partial sums

Feature 2: Speculative Weight Prefetch

• IDMAC includes 2-deep page buffer (ping-pong)
• While computing on buffer A, prefetch next weight page to buffer B
• Hides NAND read latency (~50-100μs)

Feature 3: Dynamic Precision Controller

• Runtime-configurable precision: INT8, INT4, or mixed
• For attention scores (higher sensitivity): use INT8
• For FFN weights (more tolerant): use INT4
• Control bits embedded in WLT entries

---

3. Why It Works: First-Principles Reasoning

3.1 Bandwidth Arithmetic

Baseline (Weight Offloading to SSD):

• LLaMA-7B: ~7GB weights
• Per-token: Read all weights once = 7GB
• NVMe bandwidth: 7 GB/s → 1 token/second

FlashAttend:

• Activation broadcast: 4KB per layer × 32 layers = 128KB
• Partial sum collection: 16KB per layer × 32 layers = 512KB
• Total channel traffic: ~640KB per token
• Channel bandwidth: 7 GB/s → ~10,000 tokens/second theoretical
• Actual (limited by NAND read + compute): ~50-100 tokens/second

Speedup: 50-100×

3.2 Why This Wasn't Done Before

| Historical Barrier | Why Solvable Now |
|-------------------|------------------|
| NAND die area constraints | 28nm/14nm controllers allow 0.01mm² MAC arrays |
| 3D NAND complexity | Modern 3D NAND has larger peripheral area |
| LLM workload didn't exist | Transformer inference creates perfect use case |
| Channel protocol rigidity | Custom controllers (edge devices) allow protocol mods |

3.3 Energy Efficiency Argument

Data Movement Energy Hierarchy:

• DRAM access: ~20 pJ/bit
• Channel transfer: ~5 pJ/bit
• On-die SRAM access: ~0.5 pJ/bit
• MAC operation: ~0.1 pJ/op (INT8)

By keeping weights on-die and only moving activations/partial sums:

• Baseline: 7GB × 8 bits × 5 pJ = 280 mJ per token
• FlashAttend: 640KB × 8 bits × 5 pJ + compute = ~26 mJ per token
• Energy reduction: ~10×

---

4. Evaluation Plan

4.1 Experimental Setup

Simulation Infrastructure: 1. Cycle-accurate flash die simulator (modified from MQSim/SSDSim)

• Add IDMAC latency model
• Model page buffer contention

2. RTL implementation of IDMAC unit

• Synthesize in 28nm for area/power
• Verify with constrained random tests

3. System-level simulator

• Integrate with transformer model (PyTorch frontend)
• Model end-to-end token generation

FPGA Prototype:

• Xilinx Alveo U280 + custom flash daughter card
• Implement IDMAC logic in FPGA fabric
• Real flash chips (Micron 176L 3D NAND)

4.2 Baselines

| Baseline | Description |
|----------|-------------|
| CPU-SSD | Intel i7 + Samsung 990 Pro NVMe |
| FlashNeuron | ASPLOS'23 near-storage DNN accelerator |
| DeepUM | MICRO'22 unified memory for DNNs |
| IANUS | ISCA'22 in-storage processing |
| Ideal-DRAM | Full model in DRAM (upper bound) |

4.3 Workloads

| Model | Size | Hidden Dim | Context |
|-------|------|------------|---------|
| LLaMA-7B | 7GB | 4096 | 2048 |
| LLaMA-13B | 13GB | 5120 | 2048 |
| Mistral-7B | 7GB | 4096 | 8192 |
| OPT-30B | 30GB | 7168 | 2048 |

Workload Traces:

• WikiText-103 perplexity evaluation
• Chatbot conversation (variable length)
• Code completion (GitHub Copilot traces)

4.4 Metrics

Primary: 1. Tokens per second (throughput)
2. Time-to-first-token (latency)
3. Energy per token (mJ/token)

Secondary: 4. Die area overhead (% increase)
5. Channel utilization (% of theoretical)
6. Flash endurance impact (read disturb analysis)

Accuracy: 7. Perplexity delta vs. FP16 baseline (quantization impact)

4.5 Sensitivity Studies

1. Number of MAC units per die: 8, 16, 32, 64
2. Precision: INT8, INT4, mixed
3. Die count scaling: 32, 64, 128, 256 dies
4. Model sparsity: Dense vs. 50% sparse

4.6 Expected Results

| Metric | CPU-SSD | FlashNeuron | FlashAttend |
|--------|---------|-------------|-------------|
| Tokens/sec (7B) | 1-2 | 5-10 | 50-100 |
| Energy (mJ/tok) | 500+ | 200 | 25-50 |
| Area overhead | 0% | 5% (controller) | 8% (die+ctrl) |

---

5. Potential Concerns & Mitigations

| Concern | Mitigation |
|---------|------------|
| Flash vendor adoption | Target edge AI SoC vendors (Qualcomm, MediaTek) who control full stack |
| Thermal in 3D NAND | IDMAC duty cycle <10%; negligible thermal impact |
| Manufacturing cost | Amortized over millions of edge devices |
| Weight update for fine-tuning | LoRA adapters fit in DRAM; base model static |

---

6. Contributions Summary

1. First in-die compute architecture for LLM inference that breaks the channel bottleneck
2. Broadcast-reduce protocol for activation/partial-sum communication
3. Comprehensive evaluation showing 50-100× speedup over SSD offloading
4. RTL + FPGA prototype demonstrating feasibility

---

Target Venue: ISCA 2025 (Computer Architecture) or MICRO 2025 Collaboration Opportunity: Flash vendor (Samsung/Micron/SK Hynix) + Edge AI company

---

AI-Generated Hints for Problem #004

These are 5 alternative architectural approaches generated by AI.
They are starting points for your own design—not the answer!

Hint 1 (Run 1)

Paper Title: "ScoutGate: Near-Data Speculative Candidate Filtering for Memory-Efficient Vector Search"

---

1. Root Cause Analysis

The fundamental inefficiency stems from a temporal and spatial mismatch between the filtering decision point and the data fetch commitment:

Root Cause #1: Late Binding of Rejection Decisions

• The system commits to fetching a complete high-dimensional vector (e.g., 768-4096 floats = 3-16KB) before it can determine relevance
• Distance computation requires ALL dimensions, creating an all-or-nothing data dependency
• Rejection decisions arrive too late—after bandwidth and compute are already consumed

Root Cause #2: Semantic Information Loss at Memory Interface

• Memory controllers see vector fetches as opaque cache line requests
• No mechanism exists to communicate "conditional fetch" semantics
• The memory hierarchy cannot distinguish between vectors that will contribute to results vs. those that will be discarded

Root Cause #3: Dimensionality Curse in Filtering

• Early termination techniques (e.g., partial distance bounds) require sequential dimension access
• Modern memory systems optimize for bulk, not conditional streaming
• The probability of early rejection increases with dimensions, but so does the wasted fetch cost

---

2. The Mechanism: ScoutGate Architecture

2.1 Core Insight

Speculative Hierarchical Filtering: Decompose each vector into a compact "scout signature" that can predict rejection with high confidence using minimal data, enabling the memory subsystem to abort fetches before completion.

2.2 Hardware Components

#### Component A: Scout Signature Table (SST) — Near-Memory Structure

┌─────────────────────────────────────────────────────────┐
│                 SCOUT SIGNATURE TABLE                    │
│            (Co-located with Memory Controller)           │
├─────────────────────────────────────────────────────────┤
│ Entry Structure (per vector):                            │
│ ┌──────────┬────────────┬────────────┬────────────────┐ │
│ │ VectorID │ Centroid   │ Compressed │ Dimension      │ │
│ │ (32-bit) │ Distance   │ Signature  │ Variance Map   │ │
│ │          │ (16-bit)   │ (64-128B)  │ (32-bit mask)  │ │
│ └──────────┴────────────┴────────────┴────────────────┘ │
│                                                          │
│ Signature Encoding:                                      │
│ - Product Quantization codes (8-16 subspaces)           │
│ - Per-subspace: 8-bit centroid ID + 8-bit residual      │
│ - Total: 64-128 bytes vs. 3-16KB full vector            │
└─────────────────────────────────────────────────────────┘

Hardware Details:

• Capacity: 1M-16M entries (64-128MB SRAM, partitioned across memory channels)
• Organized as set-associative structure (16-way) indexed by vector ID hash
• Populated during index construction; updated on vector insertion via background DMA

#### Component B: Speculative Distance Unit (SDU) — Processing-in-Memory Logic

┌─────────────────────────────────────────────────────────┐
│            SPECULATIVE DISTANCE UNIT (SDU)               │
│              (Per Memory Channel, 3-stage pipeline)      │
├─────────────────────────────────────────────────────────┤
│                                                          │
│  Stage 1: Signature Fetch & Decode                       │
│  ┌─────────────────────────────────────────────────┐    │
│  │ SST Lookup → PQ Codebook ROM → Subspace Dists   │    │
│  └─────────────────────────────────────────────────┘    │
│              ↓                                           │
│  Stage 2: Approximate Distance Computation               │
│  ┌─────────────────────────────────────────────────┐    │
│  │ 16× Parallel Subspace Adders → ADC Distance     │    │
│  │ Variance-Weighted Confidence Estimator          │    │
│  └─────────────────────────────────────────────────┘    │
│              ↓                                           │
│  Stage 3: Gate Decision Logic                            │
│  ┌─────────────────────────────────────────────────┐    │
│  │ Compare: approx_dist vs. (threshold × margin)   │    │
│  │ Output: {FETCH_FULL, ABORT, DEFER_TO_RERANK}    │    │
│  └─────────────────────────────────────────────────┘    │
│                                                          │
│  Hardware: 16 INT8 MACs, 32KB Codebook ROM,             │
│            Comparator tree, 2-cycle latency              │
└─────────────────────────────────────────────────────────┘

#### Component C: Conditional Fetch Controller (CFC) — Memory Request Management

┌─────────────────────────────────────────────────────────┐
│          CONDITIONAL FETCH CONTROLLER (CFC)              │
├─────────────────────────────────────────────────────────┤
│                                                          │
│  New Memory Request Types:                               │
│  ┌──────────────────────────────────────────────────┐   │
│  │ SCOUT_PREFETCH: Fetch signature only (1 cycle)   │   │
│  │ CONDITIONAL_VECTOR: Full fetch, abortable        │   │
│  │ COMMITTED_VECTOR: Standard full fetch            │   │
│  └──────────────────────────────────────────────────┘   │
│                                                          │
│  Abort Logic:                                            │
│  ┌──────────────────────────────────────────────────┐   │
│  │ Pending Request Buffer (PRB): 64 entries         │   │
│  │ - Tracks in-flight CONDITIONAL_VECTOR requests   │   │
│  │ - Each entry: {ReqID, DRAM_row, bytes_fetched}   │   │
│  │                                                   │   │
│  │ On ABORT signal from SDU:                        │   │
│  │ - Cancel remaining burst transfers               │   │
│  │ - Release row buffer if no other pending reqs    │   │
│  │ - Reclaim memory bandwidth for next candidate    │   │
│  └──────────────────────────────────────────────────┘   │
│                                                          │
│  Bandwidth Reclamation:                                  │
│  - Average abort point: 15-25% of vector fetched        │
│  - Effective bandwidth amplification: 2.5-4×            │
└─────────────────────────────────────────────────────────┘

#### Component D: Adaptive Threshold Controller (ATC) — Runtime Calibration

┌─────────────────────────────────────────────────────────┐
│         ADAPTIVE THRESHOLD CONTROLLER (ATC)              │
├─────────────────────────────────────────────────────────┤
│                                                          │
│  Per-Query State:                                        │
│  ┌──────────────────────────────────────────────────┐   │
│  │ current_k_th_distance: Running k-th best dist    │   │
│  │ false_negative_counter: Vectors wrongly filtered │   │
│  │ margin_factor: Dynamic safety margin (1.1-1.5)   │   │
│  └──────────────────────────────────────────────────┘   │
│                                                          │
│  Feedback Loop (every 64 candidates):                    │
│  ┌──────────────────────────────────────────────────┐   │
│  │ IF false_negative_rate > 0.1%:                   │   │
│  │    margin_factor += 0.05                         │   │
│  │ ELIF filter_rate < 70%:                          │   │
│  │    margin_factor -= 0.02                         │   │
│  │                                                   │   │
│  │ Hardware: 16-bit counters, shift-add multiplier  │   │
│  └──────────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────────┘

2.3 System Integration & Data Flow

┌─────────────────────────────────────────────────────────────────────┐
│                        SCOUTGATE OPERATION FLOW                      │
├─────────────────────────────────────────────────────────────────────┤
│                                                                      │
│   CPU/Accelerator                Memory Controller         DRAM     │
│   ┌──────────┐                   ┌──────────────┐      ┌─────────┐ │
│   │ Query    │──SCOUT_BATCH────→│              │      │         │ │
│   │ Engine   │  {query_vec,     │    SST       │←────→│ Vector  │ │
│   │          │   candidate_IDs} │    ↓         │      │ Data    │ │
│   │          │                  │   SDU        │      │         │ │
│   │          │                  │    ↓         │      │         │ │
│   │          │                  │   CFC        │      │         │ │
│   │          │←─FILTERED_IDS────│              │      │         │ │
│   │          │  {pass_IDs,      │              │      │         │ │
│   │          │   approx_dists}  │              │      │         │ │
│   │          │                  │              │      │         │ │
│   │          │──COMMIT_FETCH───→│              │─────→│         │ │
│   │          │  {pass_IDs}      │              │      │         │ │
│   │          │←─VECTOR_DATA─────│              │←─────│         │ │
│   └──────────┘                  └──────────────┘      └─────────┘ │
│                                                                      │
│   Timeline (for 1000 candidates, k=100, 90% filtered):              │
│   ┌────────────────────────────────────────────────────────────┐    │
│   │ Baseline:  [████████████████████████████████████] 100%     │    │
│   │            Fetch all 1000 vectors = 1000× bandwidth        │    │
│   │                                                             │    │
│   │ ScoutGate: [██] Scout + [████] Full fetch                  │    │
│   │            1000× signature + 100× vector = ~15% bandwidth  │    │
│   └────────────────────────────────────────────────────────────┘    │
└─────────────────────────────────────────────────────────────────────┘

2.4 ISA Extensions

New Instructions:
┌────────────────────────────────────────────────────────────────┐
│ VSCOUT.BATCH  rs1, rs2, rd                                     │
│   rs1: Base address of query vector                            │
│   rs2: Base address of candidate ID array                      │
│   rd:  Destination for filtered ID bitmap                      │
│   Semantics: Initiates batch scouting, returns asynchronously  │
│                                                                 │
│ VSCOUT.SYNC   rd                                               │
│   rd:  Number of candidates that passed filtering              │
│   Semantics: Blocks until scouting complete                    │
│                                                                 │
│ VSCOUT.CONFIG imm                                              │
│   imm: Encoded {margin_factor, max_filter_rate, k_value}       │
│   Semantics: Configure ATC parameters                          │
└────────────────────────────────────────────────────────────────┘

---

3. Why It Works: First-Principles Reasoning

Principle 1: Information-Theoretic Efficiency

The key insight is that rejection decisions require far less information than acceptance decisions:

• To confirm a vector is in top-k: Need exact distance (all dimensions)
• To reject a vector: Only need to prove distance > current k-th best

Product quantization signatures preserve distance ordering with high probability while compressing 50-100×. The approximation error is bounded and one-sided (we add a safety margin), ensuring:

P(approx_dist > threshold | true_dist > threshold) > 99%

Principle 2: Bandwidth as the Fundamental Bottleneck

Memory bandwidth scales slower than compute (memory wall). By filtering at the memory interface:

• We convert the problem from bandwidth-bound to compute-bound
• Effective bandwidth = Physical bandwidth × (1 / fraction_fetched)
• With 90% filtering: 4× effective bandwidth amplification

Principle 3: Speculative Execution Applied to Data

Traditional speculation predicts control flow. ScoutGate speculates on data relevance:

• Scout signatures = branch predictors for data utility
• Conditional fetches = speculative instruction fetch
• Abort mechanism = branch misprediction recovery (but for data)

The key difference: data speculation has asymmetric costs. False negatives (missing a true top-k) are costly; false positives (fetching an unnecessary vector) only waste bandwidth. The adaptive margin handles this asymmetry.

Principle 4: Amdahl's Law on Wasted Work

If 90% of fetched data is wasted, eliminating this waste provides up to 10× speedup on the memory-bound portion. Even with overhead:

• Scout signature fetch: ~1% of full vector size
• SDU computation: Overlapped with memory latency
• Net improvement: 5-8× on memory traffic

---

4. Evaluation Plan

4.1 Experimental Infrastructure

Simulation Environment:

• Cycle-accurate simulator: gem5 + DRAMSim3 integration
• Memory model: DDR5-4800, 8 channels, 32GB capacity
• ScoutGate RTL: Synthesized in Verilog, integrated as gem5 memory controller modification

Real Hardware Validation:

• FPGA prototype: Xilinx Alveo U280 (HBM2 memory)
• Near-memory implementation using HBM's base die logic capacity

4.2 Baselines

| Baseline | Description |
|----------|-------------|
| CPU-Baseline | Intel Xeon (Sapphire Rapids) + FAISS HNSW |
| GPU-Baseline | NVIDIA A100 + RAFT library |
| PIM-Baseline | UPMEM PIM-enabled DIMM with distance computation |
| Software-Filter | CPU with software PQ pre-filtering (no HW support) |
| Oracle | Perfect filtering (lower bound on memory traffic) |

4.3 Workloads

| Dataset | Dimensions | Vectors | Vector Size | Use Case |
|---------|------------|---------|-------------|----------|
| SIFT1B | 128 | 1B | 512B | Image retrieval |
| Deep1B | 96 | 1B | 384B | Deep learning embeddings |
| SPACEV1B | 100 | 1B | 400B | Web search |
| OpenAI-5M | 1536 | 5M | 6KB | LLM embeddings |
| Custom-Synthetic | 256-4096 | 100M | 1-16KB | Dimension scaling |

4.4 Metrics

Primary Metrics: 1. Queries Per Second (QPS) at fixed recall@k (k=10, 100)
2. Memory Bandwidth Utilization (useful bytes / total bytes transferred)
3. Energy Efficiency (queries per Joule)

Secondary Metrics: 4. Recall Degradation vs. exact search (target: <1% loss)
5. Filter Accuracy (true positive rate of scout filtering)
6. Latency Distribution (P50, P99, P99.9)

Overhead Metrics: 7. Area Overhead (mm² for SST + SDU + CFC)
8. Power Overhead (mW for near-memory logic)
9. SST Memory Overhead (bytes per indexed vector)

4.5 Key Experiments

Experiment 1: End-to-End Performance

• Sweep k ∈ {10, 50, 100, 500}
• Measure QPS vs. recall tradeoff curve
• Compare all baselines

Experiment 2: Bandwidth Amplification

• Measure actual DRAM traffic with/without ScoutGate
• Vary dataset dimensionality to show scaling

Experiment 3: Sensitivity Analysis

• Signature size vs. filter accuracy
• Margin factor vs. recall/performance tradeoff
• SST capacity vs. hit rate

Experiment 4: Scalability

• Multi-channel scaling (1-8 channels)
• Dataset size scaling (1M to 1B vectors)

Experiment 5: Adaptive Threshold Effectiveness

• Compare fixed vs. adaptive margin
• Measure convergence speed and stability

4.6 Expected Results

| Metric | vs. CPU-Baseline | vs. GPU-Baseline |
|--------|------------------|------------------|
| QPS | 8-12× | 2-4× |
| Bandwidth Efficiency | 6-8× | 4-6× |
| Energy Efficiency | 15-20× | 5-8× |
| Recall@100 | -0.5% | -0.3% |

---

5. Summary

ScoutGate introduces a near-data speculative filtering paradigm that fundamentally restructures how vector search interacts with the memory hierarchy. By decomposing vectors into lightweight scout signatures and enabling conditional, abortable memory fetches, we transform a bandwidth-bound workload into a compute-bound one—achieving multiplicative improvements in throughput and energy efficiency while maintaining search quality guarantees.

The key novelty lies in treating data relevance as a speculative property that can be predicted and acted upon at the memory interface, before committing scarce bandwidth resources. This represents a new class of semantic-aware memory systems applicable beyond vector search to any workload with predictable data utility patterns.

---

Hint 2 (Run 2)

Paper Title: "ScoutFilter: A Near-Data Speculative Pruning Engine for Memory-Efficient Approximate Nearest Neighbor Search"

---

1. Root Cause Analysis

The fundamental inefficiency stems from a temporal mismatch between data fetch granularity and decision granularity:

The Core Problem

• Decision Point: Whether a candidate vector is "promising" can often be determined with high confidence using only a partial distance computation (first few dimensions)
• Data Fetch Point: Current architectures commit to fetching the entire vector (e.g., 512-1024 dimensions × 4 bytes = 2-4KB) before any filtering decision
• Wasted Work: The memory subsystem and compute units process ~90% of data that provides zero value to the final result

Why Software Solutions Fail

1. Dimensionality Reduction (PCA, random projections): Loses accuracy, still fetches full vectors for re-ranking
2. Product Quantization: Reduces memory footprint but still computes full distances on compressed codes
3. Early Termination Heuristics: CPU branch misprediction penalties and memory prefetcher confusion negate benefits

First-Principles Insight

Distance metrics (L2, cosine) are monotonically accumulating—partial sums provide probabilistic bounds on final distances. If a partial distance already exceeds the current k-th nearest neighbor threshold, the full computation is provably unnecessary.

---

2. The Mechanism: ScoutFilter Architecture

2.1 High-Level Concept

ScoutFilter introduces a near-memory speculative pruning unit that performs lightweight "scout" computations on partial vector data to predict (with high confidence) whether full vector fetch is warranted, before committing memory bandwidth.

2.2 Hardware Components

#### Component 1: Scout Probe Table (SPT)

┌─────────────────────────────────────────────────────────────┐
│ SCOUT PROBE TABLE (per memory channel, 256 entries)        │
├──────────┬───────────┬──────────────┬──────────────────────┤
│ Entry ID │ Query ID  │ Scout Vector │ Threshold Register   │
│ (8b)     │ (16b)     │ (64 dims×FP16)│ (FP32)              │
├──────────┼───────────┼──────────────┼──────────────────────┤
│ 0        │ Q_42      │ [0.23, ...]  │ 15.7                 │
│ ...      │ ...       │ ...          │ ...                  │
└──────────┴───────────┴──────────────┴──────────────────────┘

• Purpose: Caches the first D_scout dimensions of active query vectors
• Location: Inside the memory controller (near DRAM interface)
• Size: 256 entries × 128B = 32KB per channel

#### Component 2: Partial Distance Unit (PDU)

┌────────────────────────────────────────────────────────────────┐
│ PARTIAL DISTANCE UNIT (per memory channel)                     │
│                                                                │
│  ┌──────────────┐    ┌──────────────┐    ┌─────────────────┐  │
│  │ Scout Vector │───▶│ SIMD FMA     │───▶│ Accumulator     │  │
│  │ (from SPT)   │    │ (8-wide FP16)│    │ Bank (16 slots) │  │
│  └──────────────┘    └──────────────┘    └────────┬────────┘  │
│                                                    │           │
│  ┌──────────────┐    ┌──────────────┐             ▼           │
│  │ Candidate    │───▶│ Dimension    │    ┌─────────────────┐  │
│  │ Prefetch Buf │    │ Selector     │    │ Bound Estimator │  │
│  │ (64B line)   │    └──────────────┘    │ (Statistical)   │  │
│  └──────────────┘                        └────────┬────────┘  │
│                                                    │           │
│                                          ┌────────▼────────┐  │
│                                          │ Prune/Proceed   │  │
│                                          │ Decision Logic  │  │
│                                          └─────────────────┘  │
└────────────────────────────────────────────────────────────────┘

Specifications:

• Compute: 8-wide FP16 FMA units (64 ops/cycle for 64-dim scout)
• Latency: 8 cycles for scout distance computation
• Accumulator Bank: Tracks 16 in-flight candidate evaluations

#### Component 3: Bound Estimator Logic

Statistical Bound Computation:
─────────────────────────────
Given: partial_dist (over D_scout dimensions)
       threshold (current k-th NN distance)
       D_total (full dimensionality)
       D_scout (scout dimensions)
Lower Bound (deterministic):
  LB = partial_dist
Upper Bound (statistical, pre-characterized):
  UB = partial_dist × (D_total/D_scout) × scale_factor
  where scale_factor ∈ [1.0, 1.5] based on dataset statistics
Decision:
  IF LB > threshold × confidence_margin THEN PRUNE
  ELSE PROCEED with full fetch

#### Component 4: Fetch Gating Register File (FGRF)

┌─────────────────────────────────────────────────────────────┐
│ FETCH GATING REGISTER FILE (in Memory Controller)          │
├───────────┬────────────┬─────────────┬────────────────────┤
│ Candidate │ Scout      │ Decision    │ Remaining Fetch    │
│ Address   │ Status     │ (Prune/Go)  │ Addresses          │
├───────────┼────────────┼─────────────┼────────────────────┤
│ 0x1000    │ Complete   │ PRUNE       │ [cancelled]        │
│ 0x2000    │ Complete   │ PROCEED     │ 0x2040,0x2080,...  │
│ 0x3000    │ In-flight  │ PENDING     │ [held]             │
└───────────┴────────────┴─────────────┴────────────────────┘

• Purpose: Tracks outstanding vector fetches and gates subsequent cache line requests
• Key Innovation: Subsequent cache lines for a vector are speculatively held until scout decision completes

2.3 Operation Flow

Timeline for Single Candidate Vector Evaluation:
═══════════════════════════════════════════════════════════════
Cycle 0:    [Memory Controller receives candidate address A]
            │
Cycle 1-4:  [Fetch first cache line (64B) containing dims 0-15]
            │ (This is the "scout portion")
            │
Cycle 5-12: [PDU computes partial L2 distance using SPT query]
            │ Meanwhile: Prefetch requests for lines 2-N are HELD
            │
Cycle 13:   [Bound Estimator makes decision]
            │
            ├─── IF PRUNE: Cancel held prefetch requests
            │              Notify CPU: "Candidate A rejected"
            │              Memory bandwidth saved: (N-1) × 64B
            │
            └─── IF PROCEED: Release held prefetch requests
                            Full vector streams to cache normally

2.4 ISA Extensions

New Instructions for ScoutFilter Control
SCOUT.INIT  qreg, addr, dims    # Load query scout vector to SPT
                                 # qreg: query ID, addr: query vector
                                 # dims: number of scout dimensions
SCOUT.THRESH qreg, threshold    # Update pruning threshold for query
                                 # Called when k-NN heap updates
SCOUT.FETCH  qreg, cand_addr    # Initiate scout-gated fetch
                                 # Returns to completion buffer
SCOUT.CONF   margin             # Set confidence margin (0.8-1.0)

2.5 Microarchitectural Integration

┌─────────────────────────────────────────────────────────────────────┐
│                        SYSTEM INTEGRATION                           │
│                                                                     │
│  ┌─────────┐     ┌─────────┐     ┌──────────────────────────────┐ │
│  │   CPU   │────▶│   L3    │────▶│      Memory Controller       │ │
│  │ Cores   │     │ Cache   │     │  ┌────────────────────────┐  │ │
│  └─────────┘     └─────────┘     │  │    ScoutFilter Unit    │  │ │
│       │                          │  │  ┌─────┐ ┌─────┐       │  │ │
│       │ SCOUT.* instructions     │  │  │ SPT │ │ PDU │       │  │ │
│       └──────────────────────────┼──│  └─────┘ └─────┘       │  │ │
│                                  │  │  ┌─────┐ ┌─────┐       │  │ │
│                                  │  │  │FGRF │ │Bound│       │  │ │
│                                  │  │  └─────┘ └─────┘       │  │ │
│                                  │  └────────────────────────┘  │ │
│                                  └──────────────┬───────────────┘ │
│                                                 │                  │
│                                          ┌──────▼──────┐          │
│                                          │    DRAM     │          │
│                                          │   Channels  │          │
│                                          └─────────────┘          │
└─────────────────────────────────────────────────────────────────────┘

---

3. Why It Works: First-Principles Reasoning

3.1 Statistical Foundation

Theorem (Partial Distance Bound): For L2 distance with i.i.d. dimension contributions:

E[D_full] = E[D_partial] × (D_total / D_partial)
Var[D_full] ≈ Var[D_partial] × (D_total / D_partial)²

Implication: With D_scout = 64 out of D_total = 512:

• We observe 12.5% of dimensions
• Partial distance correlates strongly (ρ > 0.85) with full distance
• Vectors with partial distance > 1.3× threshold have >95% probability of exceeding threshold fully

3.2 Memory Bandwidth Arithmetic

Traditional Approach:

Fetch 1000 candidates × 2KB each = 2MB bandwidth
Compute 1000 full distances
Keep top-10 results
Efficiency: 1% of fetched data contributes to output
ScoutFilter Approach:

Fetch 1000 scout portions × 128B = 128KB bandwidth
Scout computation prunes 850 candidates (85% prune rate)
Fetch 150 full vectors × 2KB = 300KB bandwidth
Total: 428KB (4.7× bandwidth reduction)

3.3 Why Near-Memory Placement is Critical

1. Latency Hiding: Scout computation overlaps with DRAM row activation
2. Bandwidth Gating: Pruning decision made before consuming channel bandwidth
3. No Cache Pollution: Pruned vectors never enter cache hierarchy

3.4 Comparison to Software Alternatives

| Approach | Bandwidth Saved | Accuracy Loss | Hardware Cost |
|----------|-----------------|---------------|---------------|
| Software early-exit | ~20% (branch overhead) | 0% | 0 |
| PCA projection | ~50% (still fetches) | 2-5% | 0 |
| ScoutFilter | 75-85% | <0.5% | ~50K gates |

---

4. Evaluation Plan

4.1 Experimental Infrastructure

Simulator:

• Extend gem5 with custom memory controller model
• Cycle-accurate PDU and SPT models
• Integrate with Ramulator2 for DRAM timing

RTL Validation:

• Synthesize ScoutFilter unit in SystemVerilog
• Target: 2GHz at 7nm, measure area/power

4.2 Baselines

| Baseline | Description |
|----------|-------------|
| CPU-Baseline | Intel Xeon with AVX-512, FAISS library |
| GPU-Baseline | NVIDIA A100, RAFT library |
| PIM-Baseline | UPMEM-style processing-in-memory |
| Accelerator-Baseline | ANNA (MICRO'20), RecNMP (ISCA'20) |
| SW-EarlyExit | Software early termination heuristics |

4.3 Workloads

| Dataset | Vectors | Dimensions | Size | Domain |
|---------|---------|------------|------|--------|
| SIFT1B | 1B | 128 | 128GB | Image features |
| Deep1B | 1B | 96 | 96GB | Deep learning |
| SPACEV | 1B | 100 | 100GB | Web search |
| Text2Image | 100M | 768 | 300GB | Multimodal |
| Custom-Synthetic | Variable | 64-1024 | Variable | Stress test |

Query Patterns:

• Uniform random queries
• Clustered queries (hot spots)
• Adversarial queries (worst-case for pruning)

4.4 Metrics

Primary Metrics:
1. Throughput: Queries per second (QPS)
2. Memory Bandwidth Utilization: Effective vs. consumed
3. Recall@K: Accuracy preservation (target: >99% of baseline)
4. Energy Efficiency: Queries per Joule

Secondary Metrics:
1. Prune Rate: Fraction of candidates filtered by scout
2. False Negative Rate: Promising candidates incorrectly pruned
3. Area Overhead: mm² at 7nm
4. Latency Distribution: P50, P99, P99.9

4.5 Sensitivity Studies

1. Scout Dimension Sweep: D_scout ∈ {16, 32, 64, 128}
2. Confidence Margin: margin ∈ {0.7, 0.8, 0.9, 1.0}
3. Dataset Characteristics: Varying intrinsic dimensionality
4. K Values: K ∈ {1, 10, 100, 1000}
5. Threshold Update Frequency: Impact of stale thresholds

4.6 Expected Results

| Metric | vs. CPU | vs. GPU | vs. PIM |
|--------|---------|---------|---------|
| Throughput | 8-12× | 2-3× | 1.5-2× |
| Energy Efficiency | 15-20× | 5-8× | 2-3× |
| Bandwidth Reduction | 4-6× | 4-6× | 3-4× |
| Area Overhead | +3% MC | N/A | +8% |

---

5. Key Contributions Summary

1. Novel Observation: Partial distance computation provides high-confidence pruning signals for ANNS workloads

2. Hardware Mechanism: ScoutFilter—a near-memory speculative pruning engine with:

• Scout Probe Table for query caching
• Partial Distance Unit for lightweight computation
• Fetch Gating logic for bandwidth conservation

3. System Integration: Clean ISA extensions and memory controller integration requiring minimal silicon overhead (~50K gates)

4. Theoretical Foundation: Statistical bounds on partial-to-full distance correlation enabling aggressive yet safe pruning

---

6. Potential Extensions (Future Work)

• Adaptive Scout Dimensions: ML-based predictor for optimal D_scout per query
• Multi-Query Batching: Amortize SPT across query batches
• Hierarchical Scouting: Two-level scout (ultra-fast 16-dim, then 64-dim)
• CXL Integration: ScoutFilter as CXL Type-2 accelerator for disaggregated memory

---

Hint 3 (Run 3)

Paper Title: "ScoutFilter: A Near-Data Speculative Pruning Engine for Memory-Efficient Approximate Nearest Neighbor Search"

---

1. Root Cause Analysis

The fundamental inefficiency stems from a temporal mismatch between the decision point and the data commitment point in ANNS workloads.

First-Principles Breakdown:

1. Information Asymmetry: The decision to reject a candidate (which happens ~90% of the time) requires only a distance estimate, but current architectures commit to fetching the entire vector (512-2048 dimensions × 4 bytes = 2-8KB per vector) before any filtering decision can be made.

2. Bandwidth-Decision Coupling: The memory subsystem operates on a "fetch-then-decide" paradigm. The CPU/GPU cannot issue a conditional fetch that says "only continue if promising."

3. Locality Destruction: ANNS graph traversal (HNSW, NSG) exhibits pointer-chasing behavior with poor spatial locality. Prefetchers cannot help because the next access depends on distance calculations from current fetches.

4. Arithmetic Intensity Collapse: Distance computation (L2/cosine) is O(d) multiply-accumulates per vector, but with 90% waste, effective arithmetic intensity drops to ~0.1 FLOP/byte—firmly in the memory-bound regime.

The Core Insight: If we could make a high-confidence rejection decision using only a small prefix of each vector (e.g., first 32-64 dimensions), we could avoid fetching the remaining 90%+ of data for most candidates.

---

2. The Mechanism: ScoutFilter Architecture

2.1 Overview

ScoutFilter is a near-memory processing unit that performs speculative early-termination filtering using partial vector data, integrated between the memory controller and LLC. It exploits the statistical property that distance estimates from vector prefixes are strongly correlated with full distances.

2.2 Hardware Structures

#### A. Scout Probe Unit (SPU) — Per Memory Channel

┌─────────────────────────────────────────────────────────────┐
│                    SCOUT PROBE UNIT                         │
├─────────────────────────────────────────────────────────────┤
│  ┌──────────────────┐    ┌──────────────────────────────┐  │
│  │ Query Prefix     │    │ Prefix Distance Calculator   │  │
│  │ Register File    │    │ (8× FP32 MAC units)          │  │
│  │ (8 queries ×     │───▶│ Pipelined, 64-dim/cycle      │  │
│  │  64 dims × FP32) │    │                              │  │
│  └──────────────────┘    └──────────┬───────────────────┘  │
│                                     │                       │
│  ┌──────────────────┐               ▼                       │
│  │ Adaptive         │    ┌──────────────────────────────┐  │
│  │ Threshold Table  │───▶│ Speculation Decision Logic   │  │
│  │ (ATT)            │    │                              │  │
│  │ 256 entries      │    │ if (prefix_dist > threshold) │  │
│  │ {query_id,       │    │   PRUNE → cancel fetch       │  │
│  │  threshold,      │    │ else                         │  │
│  │  confidence}     │    │   PROCEED → full fetch       │  │
│  └──────────────────┘    └──────────┬───────────────────┘  │
│                                     │                       │
│  ┌──────────────────┐               ▼                       │
│  │ Mispredict       │    ┌──────────────────────────────┐  │
│  │ Recovery Buffer  │◀───│ Pruned Address Queue (PAQ)   │  │
│  │ (MRB)            │    │ 128 entries                  │  │
│  │ 64 entries       │    │ {addr, query_id, prefix_dist}│  │
│  └──────────────────┘    └──────────────────────────────┘  │
└─────────────────────────────────────────────────────────────┘

#### B. Memory Layout Transformation Unit (MLTU)

Vectors are stored in a prefix-separated layout:

Traditional Layout:      ScoutFilter Layout:
┌────────────────────┐   ┌─────────────┐ ┌─────────────────┐
│ V0[0:1023]         │   │ PREFIX BANK │ │ SUFFIX BANK     │
│ V1[0:1023]         │   │ V0[0:63]    │ │ V0[64:1023]     │
│ V2[0:1023]         │   │ V1[0:63]    │ │ V1[64:1023]     │
│ ...                │   │ V2[0:63]    │ │ V2[64:1023]     │
└────────────────────┘   └─────────────┘ └─────────────────┘
                         (64B aligned)   (Fetched on demand)

Hardware support:

• Prefix Bank Identifier (PBI): 4-bit field in page table entries marking prefix vs. suffix regions
• Dual-Pointer Descriptor: Each vector ID maps to {prefix_addr, suffix_addr} via a small on-chip translation buffer

#### C. Fetch Speculation Controller (FSC)

Located in the memory controller, manages the two-phase fetch protocol:

┌─────────────────────────────────────────────────────────────┐
│               FETCH SPECULATION CONTROLLER                  │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│  Phase 1: Prefix Fetch                                      │
│  ┌─────────────┐     ┌─────────────┐     ┌──────────────┐  │
│  │ Candidate   │────▶│ Prefix Addr │────▶│ Issue to     │  │
│  │ Queue       │     │ Generator   │     │ DRAM         │  │
│  │ (from CPU)  │     │             │     │              │  │
│  └─────────────┘     └─────────────┘     └──────────────┘  │
│                                                             │
│  Phase 2: Conditional Suffix Fetch                          │
│  ┌─────────────┐     ┌─────────────┐     ┌──────────────┐  │
│  │ SPU         │────▶│ Suffix Addr │────▶│ Issue to     │  │
│  │ PROCEED     │     │ Generator   │     │ DRAM (if     │  │
│  │ Signal      │     │             │     │ not pruned)  │  │
│  └─────────────┘     └─────────────┘     └──────────────┘  │
│                                                             │
│  Speculation Stats Register:                                │
│  {total_probes, prunes, mispredicts, suffix_fetches}       │
└─────────────────────────────────────────────────────────────┘

#### D. Adaptive Threshold Calibration Engine (ATCE)

A small state machine that dynamically adjusts pruning thresholds based on observed accuracy:

State Machine:
┌─────────┐    mispredict_rate > 5%    ┌─────────────┐
│ NORMAL  │ ─────────────────────────▶ │ CONSERVATIVE│
│ θ = θ₀  │                            │ θ = θ₀×1.2  │
└────┬────┘                            └──────┬──────┘
     │                                        │
     │ mispredict_rate < 1%                   │ stable for 1K probes
     │                                        │
     ▼                                        ▼
┌─────────────┐                        ┌─────────────┐
│ AGGRESSIVE  │ ◀───────────────────── │ RECOVERY    │
│ θ = θ₀×0.9  │    mispredict < 2%     │             │
└─────────────┘                        └─────────────┘
Hardware: 

3 counters per query context (probes, prunes, mispredicts)
Threshold update logic: θ_new = θ_old × (1 + α×(target_rate - observed_rate))

2.3 Operational Flow

Timeline for single candidate vector fetch:
Cycle 0-3:    CPU issues ANNS_FETCH(vector_id, query_id) instruction
              FSC extracts prefix_addr from translation buffer
              
Cycle 4-50:   DRAM fetches 64B prefix (standard DDR5 latency)
              
Cycle 51-55:  SPU receives prefix data
              Computes partial_distance = Σᵢ₌₀⁶³ (q[i] - v[i])²
              
Cycle 56:     SPU compares partial_distance against ATT[query_id].threshold
              
              IF partial_distance > threshold × scaling_factor:
                  → PRUNE: Log to PAQ, signal FSC to cancel suffix
                  → Return PRUNE_TOKEN to CPU (saves ~800B fetch)
              ELSE:
                  → PROCEED: FSC issues suffix fetch
                  
Cycle 57-110: (If PROCEED) DRAM fetches remaining 960B suffix
              
Cycle 111+:   Full vector available for precise distance computation

2.4 Mispredict Recovery Mechanism

When the final top-K results are computed, a verification pass checks if any pruned candidates might have qualified:

Recovery Protocol:
1. CPU maintains running k-th distance (D_k) during search
2. For each entry in PAQ where prefix_dist < D_k × safety_margin:

Issue recovery fetch for full vector
Recompute exact distance

3. Update results if any recovered vector qualifies
4. Increment mispredict counter for ATCE feedback

Hardware cost: 128-entry PAQ ≈ 2KB SRAM per memory channel

2.5 ISA Extensions

New Instructions:
┌────────────────────────────────────────────────────────────┐
│ ANNS_LOAD_QUERY  qreg, addr, dims    ; Load query prefix   │
│ ANNS_FETCH       vreg, vid, qid      ; Speculative fetch   │
│ ANNS_PRUNE_STAT  dest                ; Read prune stats    │
│ ANNS_SET_THRESH  qid, threshold      ; Set pruning thresh  │
│ ANNS_RECOVER     qid                 ; Trigger recovery    │
└────────────────────────────────────────────────────────────┘

---

3. Why It Works: First-Principles Reasoning

3.1 Statistical Foundation

Lemma (Prefix Distance Correlation): For high-dimensional vectors drawn from typical embedding distributions, the correlation between d-dimensional prefix distance and full D-dimensional distance is:

$$\rho(d_{prefix}, d_{full}) \approx \sqrt{\frac{d}{D}}$$

For d=64, D=1024: ρ ≈ 0.25. However, for rejection decisions, we only need the prefix distance to be a reliable lower bound with high probability.

Key Insight: If prefix_distance > threshold, the full distance is very likely to exceed the threshold as well (distances are additive across dimensions). The false negative rate (pruning a true neighbor) can be bounded:

$$P(\text{false prune}) \leq P(d_{suffix} < threshold - d_{prefix})$$

With proper threshold calibration, this is <2% for typical workloads.

3.2 Bandwidth Arithmetic

Before ScoutFilter:

• Candidates examined: 1000 per query
• Full vector size: 1024 dims × 4B = 4KB
• Total bandwidth: 1000 × 4KB = 4MB per query

After ScoutFilter (90% prune rate):

• Prefix fetches: 1000 × 64B = 64KB
• Suffix fetches: 100 × 960B = 96KB
• Total bandwidth: 160KB per query
• Bandwidth reduction: 25×

3.3 Latency Hiding

The two-phase fetch naturally pipelines:

• While SPU evaluates candidate N's prefix, DRAM fetches candidate N+1's prefix
• Suffix fetches for surviving candidates overlap with prefix evaluations
• Critical path only includes suffix fetch latency for true positives

3.4 Why Near-Memory Placement is Essential

1. Bandwidth amplification: If prefix data traveled to CPU for filtering, we'd still consume full memory channel bandwidth
2. Latency: Round-trip to CPU would add ~100 cycles, negating benefits
3. Energy: Data movement dominates; filtering at memory saves 10-100× energy per pruned vector

---

4. Evaluation Plan

4.1 Experimental Infrastructure

Simulator: Gem5 + DRAMSim3 with custom ScoutFilter module

• Model SPU as fixed-function accelerator attached to memory controller
• Extend memory controller with FSC state machine
• Implement prefix-separated memory layout in DRAMSim3

RTL Validation: Chisel implementation of SPU for area/power estimates

• Synthesize with 7nm standard cell library
• Target: <0.5mm² area, <100mW power per memory channel

4.2 Baselines

| Baseline | Description |
|----------|-------------|
| CPU-Baseline | Intel Xeon with AVX-512, HNSW implementation (FAISS) |
| GPU-Baseline | NVIDIA A100, RAFT library |
| PIM-Baseline | UPMEM-style processing-in-memory |
| Ideal-Filter | Oracle that knows which candidates to skip (upper bound) |
| Software-Prefix | CPU-based prefix filtering (no hardware support) |

4.3 Workloads

| Dataset | Dimensions | Vectors | Query Type |
|---------|------------|---------|------------|
| SIFT1B | 128 | 1B | Image similarity |
| Deep1B | 96 | 1B | Deep learning embeddings |
| SPACEV | 100 | 1.4B | Web search |
| Text2Image | 768 | 100M | Multi-modal |
| OpenAI-3 | 1536 | 10M | LLM embeddings |
| Synthetic | 64-4096 | 1M-1B | Controlled studies |

4.4 Metrics

Primary Metrics:
1. Queries Per Second (QPS) at fixed recall@10 = 0.95
2. Memory Bandwidth Utilization (GB/s consumed vs. available)
3. Energy per Query (pJ/query)

Secondary Metrics:
4. Recall Degradation vs. exact search
5. Prune Rate and Mispredict Rate 6. Latency Distribution (p50, p99)

Sensitivity Studies:
7. Prefix size (32, 64, 128 dimensions)
8. Dataset dimensionality impact
9. Index structure interaction (HNSW vs. IVF vs. DiskANN)
10. Threshold adaptation convergence time

4.5 Key Experiments

Experiment 1: End-to-End Performance

• Compare QPS across all baselines and datasets
• Hypothesis: ScoutFilter achieves 5-10× QPS improvement over CPU baseline

Experiment 2: Bandwidth Efficiency

• Measure actual DRAM bandwidth consumed per query
• Hypothesis: 15-25× bandwidth reduction with <2% recall loss

Experiment 3: Scalability

• Vary vector dimensionality from 64 to 4096
• Hypothesis: Benefits increase with dimensionality (more suffix to prune)

Experiment 4: Adaptation Dynamics

• Trace threshold evolution during workload shifts
• Hypothesis: ATCE converges within 1000 queries to optimal threshold

Experiment 5: Area/Power Analysis

• Report silicon cost from synthesis
• Hypothesis: <1% die area overhead, <5% power overhead

4.6 Expected Results Summary

| Metric | CPU Baseline | ScoutFilter | Improvement |
|--------|--------------|-------------|-------------|
| QPS (SIFT1B, R@10=0.95) | 1,200 | 8,500 | 7.1× |
| Bandwidth (GB/s/query) | 4.2 | 0.18 | 23× reduction |
| Energy (mJ/query) | 12.5 | 1.8 | 6.9× |
| Recall@10 | 0.950 | 0.948 | -0.2% |

---

5. Novelty Claims

1. First near-memory speculative pruning architecture for ANNS that exploits partial vector correlation
2. Two-phase fetch protocol with hardware support for conditional suffix retrieval
3. Adaptive threshold calibration that maintains accuracy guarantees under workload drift
4. Prefix-separated memory layout with minimal translation overhead

---

6. Potential Concerns & Mitigations

| Concern | Mitigation |
|---------|------------|
| Prefix correlation varies by dataset | ATCE adapts; fallback to conservative mode |
| Memory layout transformation cost | One-time preprocessing; amortized over billions of queries |
| Recovery overhead for mispredicts | PAQ bounds recovery fetches; <2% overhead in practice |
| Applicability to quantized vectors | Extend to PQ codes with sub-codebook prefixes |

---

Target Venue: ISCA 2025 / MICRO 2025

Estimated Contribution: This work bridges the gap between near-data processing and approximate algorithms, demonstrating that domain-specific speculation can achieve order-of-magnitude efficiency gains for emerging AI infrastructure workloads.

---

Hint 4 (Run 4)

Paper Title: "ScoutFilter: A Near-Data Progressive Refinement Engine for Memory-Efficient Approximate Nearest Neighbor Search"

---

1. Root Cause Analysis

The fundamental problem is a temporal-spatial mismatch between the decision point and the data fetch point in ANNS workloads.

First-Principles Breakdown:

1. Information Asymmetry: The full distance computation requires 100% of vector data, but the decision to reject a candidate often requires far less. In high-dimensional spaces (d=128-1024), the first few dimensions frequently provide sufficient signal to reject distant candidates with high confidence due to the statistical properties of distance accumulation.

2. All-or-Nothing Fetch Pattern: Current architectures treat vector fetches as atomic operations. A 512-dimensional float32 vector (2KB) is fetched entirely before any filtering decision, even though partial distance on the first 32 dimensions (128B) might already exceed the current k-th nearest neighbor threshold.

3. Wasted Memory Bandwidth Amplification: If 90% of candidates are rejected, then 90% of memory bandwidth is consumed fetching data that contributes zero useful work. This is a speculative fetch without early termination.

4. Compute-Memory Coupling: Traditional architectures couple the "fetch" and "compute" stages tightly, preventing early abandonment of unpromising candidates mid-stream.

---

2. The Mechanism: ScoutFilter Architecture

2.1 Core Concept: Progressive Refinement with Near-Data Early Exit

ScoutFilter introduces a two-tier filtering architecture with near-memory processing that performs speculative partial distance computation to enable early termination before full vector transfer.

2.2 Hardware Components

#### Component 1: Scout Signature Cache (SSC)

• Location: In the memory controller or HBM logic die
• Structure:
• Compact SRAM buffer: 256KB-1MB
• Stores "Scout Signatures" = first k dimensions (k=16-64) of each vector
• Organized as a direct-mapped cache indexed by vector ID
• Entry format: [VectorID (32b) | Signature (k×16b bfloat16) | Valid (1b)]
• Population: Lazy fill on first access; LRU eviction

#### Component 2: Near-Data Scout Processing Unit (SPU)

• Location: In memory controller or HBM base die (processing-in-memory style)
• Structure:
• 8-16 lightweight SIMD lanes (bfloat16 MAC units)
• Single-cycle partial L2 distance accumulator
• Threshold comparator register (τ_scout)
• Candidate queue (64-128 entries)
• Function: Computes partial distance on scout signatures before authorizing full vector fetch

#### Component 3: Adaptive Threshold Predictor (ATP)

• Location: Host-side or in memory controller
• Structure:
• Running statistics table: tracks partial-to-full distance correlation
• 4-entry confidence table per query batch
• Linear scaling predictor: τ_scout = α × τ_full × (k/d) where α is learned
• Function: Dynamically adjusts scout threshold to balance precision/recall vs. bandwidth savings

#### Component 4: Full Vector Fetch Controller (FVFC)

• Location: Memory controller
• Structure:
• Priority queue for "passed" candidates
• Streaming DMA engine with early-termination capability
• Progressive fetch state machine (fetches in 64B chunks)
• Function: Only initiates full fetch for candidates passing scout filter; can abort mid-fetch if running distance exceeds threshold

2.3 Operational Flow

┌─────────────────────────────────────────────────────────────────┐
│                      ScoutFilter Pipeline                        │
├─────────────────────────────────────────────────────────────────┤
│                                                                  │
│  Query Vector Q arrives                                          │
│         │                                                        │
│         ▼                                                        │
│  ┌──────────────┐     Scout Signature                           │
│  │ SSC Lookup   │────► Cache Hit? ───Yes──►┌─────────────┐      │
│  └──────────────┘           │              │    SPU      │      │
│         │ No                │              │ Partial Dist│      │
│         ▼                   │              │ Computation │      │
│  ┌──────────────┐          │              └──────┬──────┘      │
│  │Fetch Signature│◄─────────┘                     │              │
│  │(First k dims) │                                ▼              │
│  └──────────────┘                    ┌────────────────────┐     │
│         │                            │ d_partial > τ_scout?│     │
│         └───────────────────────────►└─────────┬──────────┘     │
│                                           │         │            │
│                                          Yes        No           │
│                                           │         │            │
│                                           ▼         ▼            │
│                                    ┌─────────┐ ┌──────────┐     │
│                                    │ REJECT  │ │Full Fetch│     │
│                                    │(No BW)  │ │+ Compute │     │
│                                    └─────────┘ └────┬─────┘     │
│                                                      │           │
│                                          Progressive Fetch       │
│                                          with Early Exit         │
│                                                      │           │
│                                                      ▼           │
│                                              Update Top-K        │
│                                              Update τ_full       │
│                                              Update τ_scout      │
└─────────────────────────────────────────────────────────────────┘

2.4 Key Micro-architectural Details

Scout Signature Selection Logic:

• Default: First k dimensions (exploits data layout locality)
• Advanced: Variance-weighted dimension selector (offline preprocessing stores indices of highest-variance dimensions)

SPU Partial Distance Computation:

Input: Q_scout[k], V_scout[k], τ_scout
Output: PASS/REJECT decision
Accumulator = 0
for i in 0 to k-1:
    diff = Q_scout[i] - V_scout[i]
    Accumulator += diff * diff
    // Early exit within scout computation
    if Accumulator > τ_scout:
        return REJECT
// Extrapolation check
projected_full = Accumulator  (d/k)  safety_margin
if projected_full > τ_full:
    return REJECT
    
return PASS

Progressive Full Fetch Protocol:

• FVFC fetches full vector in 64B chunks
• After each chunk, running distance updated
• If running_distance + minimum_possible_remaining > τ_full: ABORT fetch
• Reduces average bytes transferred even for "passed" candidates

---

3. Why It Works: First-Principles Reasoning

3.1 Statistical Foundation

Concentration of Measure in High Dimensions: In high-dimensional spaces, distances concentrate around their expected values. For random vectors, the variance of partial distance estimates decreases as O(1/k), meaning even k=32 dimensions provide a reliable estimate of the final distance ranking.

Mathematical Justification: For L2 distance with i.i.d. dimensions:

• E[D_full] = d × E[(q_i - v_i)²]
• E[D_partial] = k × E[(q_i - v_i)²]
• Therefore: E[D_full] = (d/k) × E[D_partial]

The partial distance is an unbiased estimator of the full distance, scaled by dimension ratio.

3.2 Bandwidth Savings Analysis

Model:

• Let p = probability a candidate passes scout filter
• Let f = false negative rate (candidates incorrectly rejected)
• Scout signature size: S_scout = k × sizeof(element)
• Full vector size: S_full = d × sizeof(element)

Bandwidth Consumption:

• Baseline: N_candidates × S_full
• ScoutFilter: N_candidates × S_scout + p × N_candidates × S_full

Savings Factor:

Savings = 1 - (S_scout/S_full + p)
        = 1 - (k/d + p)

With k=32, d=512, p=0.15 (85% filtered):
Savings = 1 - (0.0625 + 0.15) = 78.75% bandwidth reduction

3.3 Why Near-Data Placement is Critical

1. Latency Hiding: Scout computation overlaps with potential full-fetch initiation
2. Bandwidth Filtering: Rejected candidates never consume host-memory bandwidth
3. Memory Controller Integration: Leverages existing memory request queuing infrastructure

---

4. Evaluation Plan

4.1 Baselines

| Baseline | Description |
|----------|-------------|
| CPU-Baseline | Intel Xeon with AVX-512, FAISS/ScaNN library |
| GPU-Baseline | NVIDIA A100/H100 with RAFT/cuVS |
| PIM-Baseline | UPMEM-style processing-in-memory for ANNS |
| ADM (Prior Work) | Application-driven memory (if applicable) |
| SmartSSD | Near-storage compute baseline |
| Oracle-Filter | Perfect filtering (upper bound) |

4.2 Benchmarks

| Dataset | Dimensions | Vectors | Domain |
|---------|------------|---------|--------|
| SIFT1B | 128 | 1B | Image descriptors |
| Deep1B | 96 | 1B | Deep features |
| SPACEV | 100 | 1B | Web search |
| Text2Image | 200 | 1B | Multimodal |
| OpenAI-5M | 1536 | 5M | LLM embeddings |
| Synthetic | 256-2048 | Variable | Controlled study |

4.3 Metrics

Primary Metrics: 1. Queries Per Second (QPS) at fixed recall@10 = 0.95
2. Memory Bandwidth Utilization (GB/s consumed vs. available)
3. Bandwidth Efficiency: Useful bytes / Total bytes transferred
4. Energy per Query (pJ/query)

Secondary Metrics: 5. Recall@K Degradation vs. exact search (quality impact of filtering)
6. Latency Distribution (P50, P95, P99)
7. Scout Filter Hit Rate (SSC effectiveness)
8. False Negative Rate (incorrectly rejected true neighbors)

4.4 Sensitivity Studies

1. Scout Signature Size (k): Sweep k ∈ {8, 16, 32, 64, 128}
2. Threshold Aggressiveness (α): Trade-off recall vs. bandwidth
3. Vector Dimensionality: How savings scale with d
4. Workload Intensity: Varying batch sizes and concurrency
5. Dataset Characteristics: Clustered vs. uniform distributions

4.5 Simulation/Implementation Strategy

Cycle-Accurate Simulation:

• Ramulator2 or DRAMSim3 for memory system
• Custom SPU model integrated with memory controller
• gem5 for host processor

FPGA Prototype:

• Implement SPU on Xilinx Alveo U280 (HBM-attached FPGA)
• Demonstrate near-memory filtering concept
• Measure real power consumption

Analytical Model:

• Roofline analysis for bandwidth-bound characterization
• Queuing model for latency prediction

4.6 Expected Results

| Metric | Baseline (GPU) | ScoutFilter | Improvement |
|--------|----------------|-------------|-------------|
| QPS (Recall=0.95) | 10,000 | 45,000 | 4.5× |
| Memory BW Used | 900 GB/s | 250 GB/s | 3.6× reduction |
| Energy/Query | 100 μJ | 28 μJ | 3.6× |
| Bandwidth Efficiency | 10% | 72% | 7.2× |

---

5. Key Contributions Summary

1. Novel Near-Data Filtering Architecture: First hardware mechanism to perform speculative partial-distance filtering before full vector fetch in ANNS workloads.

2. Scout Signature Cache Design: Compact representation enabling 90%+ bandwidth savings with minimal area overhead.

3. Adaptive Threshold Prediction: Self-tuning mechanism that balances recall quality against bandwidth efficiency.

4. Progressive Fetch Protocol: Fine-grained early termination that reduces average transfer size even for candidates that pass initial filtering.

5. Comprehensive Evaluation: Demonstrates 3-5× throughput improvement on billion-scale vector search benchmarks.

---

6. Potential Extensions (Future Work)

• Learned Scout Signatures: Neural hash or PQ codes as scout representations
• Multi-Level Filtering: Coarse → Medium → Fine progressive refinement
• CXL Integration: ScoutFilter as CXL Type-2 accelerator for disaggregated memory
• Approximate Computing: Trading off exact distances for probabilistic filtering

---

Hint 5 (Run 5)

Title of Paper: "PRISM: Progressive Rejection through In-Memory Speculative Matching for Vector Search"

---

1. Root Cause Analysis

The fundamental inefficiency stems from a semantic mismatch between data granularity and decision granularity:

• Data Granularity: Memory systems fetch entire cache lines (64B) or larger DRAM bursts (64-256B), meaning a 768-dimensional float32 vector (3KB) requires dozens of memory transactions.
• Decision Granularity: The accept/reject decision for a candidate vector is binary and often determinable with high confidence from a small subset of dimensions.

Core Insight: Distance metrics (L2, cosine similarity) are monotonically accumulating—partial distance computed on k dimensions provides a statistical lower bound on the final distance. If this partial distance already exceeds a threshold (derived from the current k-th nearest neighbor), the candidate is provably rejectable without fetching remaining dimensions.

Current architectures cannot exploit this because:
1. Prefetchers fetch greedily: No mechanism to abort in-flight memory requests based on computation results
2. Memory hierarchy is fetch-centric: No facility to perform filtering at the memory interface
3. Computation is decoupled from memory: By the time partial distance is computed, full data is already fetched

---

2. The PRISM Mechanism: Hardware Micro-Architecture

2.1 Overview

PRISM introduces a Speculative Distance Accumulation Unit (SDAU) positioned between the last-level cache (LLC) and memory controller, enabling progressive candidate evaluation with early termination of memory transactions.

2.2 Hardware Structures

#### A. Candidate Tracking Table (CTT) — 64 entries

┌─────────────────────────────────────────────────────────────────┐
│ CTT Entry (128 bits)                                            │
├──────────┬──────────┬──────────┬──────────┬───────────┬─────────┤
│ Valid    │ CandID   │ BaseAddr │ DimFetch │ PartialDist│ State  │
│ (1b)     │ (16b)    │ (48b)    │ (12b)    │ (32b FP)   │ (3b)   │
└──────────┴──────────┴──────────┴──────────┴───────────┴─────────┘
State: ACTIVE | PENDING | REJECTED | GRADUATED

Each entry tracks an in-flight candidate vector being progressively evaluated.

#### B. Query Vector Register File (QVRF) — 4KB SRAM

• Holds the current query vector (up to 1024 dimensions × 32-bit)
• Partitioned into 16 dimension groups (64 dims each)
• Enables parallel partial distance computation

#### C. Threshold Register (TR)

• Holds dynamic rejection threshold τ (distance to current k-th nearest neighbor)
• Updated by core via memory-mapped register when heap is modified

#### D. Speculative Distance Unit (SDU) — Computation Logic

                    ┌─────────────────────────────┐
 From Memory ──────►│ Dimension Buffer (256B)     │
 Controller         │ ─────────────────────────── │
                    │ Partial Distance ALU        │
                    │ (8× FP32 fused subtract-sq) │
                    │ ─────────────────────────── │
                    │ Accumulator + Comparator    │──► Reject Signal
                    └─────────────────────────────┘

• 8-wide SIMD for dimension-parallel distance computation
• Fused subtract-square-accumulate pipeline (3 cycles)
• Comparator: If PartialDist > τ × α(DimFetch/TotalDim), emit REJECT

#### E. Memory Request Abort Controller (MRAC)

• Interfaces with memory controller's request queue
• On REJECT signal:
• Issues ABORT for outstanding requests to rejected candidate's address range
• Marks corresponding DRAM rows as deprioritized (not canceled if already in-flight to bank)

#### F. Dimension Importance Table (DIT) — 1KB SRAM

┌────────────────────────────────┐
│ DimGroup[i].Importance (8b)   │ × 16 groups
│ DimGroup[i].FetchOrder (4b)   │
└────────────────────────────────┘

• Stores learned/profiled importance scores per dimension group
• Reorders fetch sequence: High-variance dimensions fetched first (maximizes early rejection probability)
• Updated periodically via software hint instruction

2.3 Operation Flow

┌─────────────────────────────────────────────────────────────────────┐
│                         PRISM Pipeline                              │
├─────────────────────────────────────────────────────────────────────┤
│                                                                     │
│  1. INITIATE: Core issues PRISM_SEARCH(query_addr, cand_list_addr) │
│       ↓                                                             │
│  2. LOAD_QUERY: QVRF populated from query_addr                     │
│       ↓                                                             │
│  3. For each candidate in parallel (up to 64):                     │
│       │                                                             │
│       ├─► FETCH_GROUP[0]: Request dims 0-63 (or DIT-ordered)       │
│       │         ↓                                                   │
│       ├─► COMPUTE: SDU calculates partial L2 distance              │
│       │         ↓                                                   │
│       ├─► EVALUATE: PartialDist vs τ × confidence_bound(k/D)       │
│       │         ↓                                                   │
│       ├─► REJECT? ──Yes──► MRAC aborts remaining fetches           │
│       │         │          CTT[entry].State = REJECTED              │
│       │         No                                                  │
│       │         ↓                                                   │
│       └─► FETCH_GROUP[1]: Request dims 64-127...                   │
│                 (repeat until REJECTED or all dims fetched)         │
│       ↓                                                             │
│  4. GRADUATE: Non-rejected candidates forwarded to core            │
│               with full distance (computed incrementally)           │
│                                                                     │
└─────────────────────────────────────────────────────────────────────┘

2.4 Confidence-Adjusted Threshold Logic

Key innovation: The rejection threshold must account for statistical uncertainty when only partial dimensions are observed.

Rejection Criterion:

PartialDist(k dims) > τ × ConfidenceBound(k, D, σ²)

Where:

• τ = current k-NN threshold
• D = total dimensions
• k = dimensions fetched so far
• ConfidenceBound(k, D, σ²) = (k/D) - β × sqrt(k×(D-k)/(D²×(D-1))) × σ

This is derived from hypergeometric distribution properties—the partial sum of squared differences concentrates around (k/D) of the full distance.

Hardware Implementation:

• Pre-computed lookup table (256 entries) indexed by k/D ratio
• Configurable conservativeness parameter β (default: 3σ for <0.1% false rejections)

---

3. Why It Works: First-Principles Reasoning

3.1 Information-Theoretic Argument

Principle: Rejection is an asymmetric decision—false acceptance is recoverable (filter later), false rejection loses recall permanently.

PRISM exploits that for random high-dimensional vectors, partial L2 distance has provably low variance relative to mean:

• For D-dimensional vectors with i.i.d. components, the sum of k squared differences has variance O(k), while mean scales as O(k)
• Coefficient of variation = O(1/√k), meaning 16 dimensions provide ~75% confidence in relative ranking

3.2 Memory Bandwidth Arithmetic

Consider 768-dim vectors (3KB each), searching 10,000 candidates:

| Approach | Data Fetched | Effective BW |
|----------|--------------|--------------|
| Baseline | 30 MB | 30 MB |
| PRISM (90% rejected at 64 dims) | 0.9×10K×256B + 0.1×10K×3KB = 5.3 MB | 5.6× reduction |

3.3 Why Near-Memory Placement is Critical

Placing SDAU at LLC-Memory boundary:
1. Minimizes abort latency: Reject signal reaches memory controller in ~5 cycles (vs. ~100 cycles if computed at core)
2. Catches requests in queue: DRAM request queues hold 32-64 entries; early rejection prevents queue pollution
3. Enables bank-level parallelism: Different candidates map to different banks; rejection doesn't stall unrelated requests

---

4. Evaluation Plan

4.1 Baselines

| System | Description |
|--------|-------------|
| CPU-Baseline | Intel Xeon with AVX-512, FAISS HNSW |
| GPU-Baseline | NVIDIA A100, RAFT library |
| PIM-Baseline | UPMEM-style processing-in-memory |
| SQ-Baseline | Scalar Quantization (8-bit) + full scan |
| PQ-Baseline | Product Quantization with IVF |

4.2 Proposed System Variants

| Variant | Description |
|---------|-------------|
| PRISM-Full | Complete mechanism |
| PRISM-NoReorder | Without dimension importance reordering |
| PRISM-Static | Fixed threshold (no adaptive τ) |
| PRISM-Conservative | β=4 (lower false rejection risk) |

4.3 Workloads

| Dataset | Dimensions | Vectors | Domain |
|---------|------------|---------|--------|
| SIFT-1B | 128 | 1B | Image features |
| Deep-1B | 96 | 1B | CNN embeddings |
| Text2Image-1B | 200 | 1B | CLIP embeddings |
| OpenAI-Synthetic | 1536 | 100M | LLM embeddings |
| Cohere-Synthetic | 768 | 100M | Multilingual |

4.4 Metrics

Primary:

• Recall@k (k=1,10,100): Correctness validation
• Queries per Second (QPS): Throughput
• QPS/Watt: Energy efficiency
• Memory Bandwidth Utilization: Actual vs. theoretical

Secondary:

• Rejection Rate vs. Dimension Fetched: Characterizes early termination effectiveness
• False Rejection Rate: Validates statistical bounds
• Area Overhead: RTL synthesis for SDAU components
• Latency Distribution: P50, P99 query latency

4.5 Experimental Methodology

1. Simulation: gem5 + Ramulator2 with custom SDAU model
2. RTL Validation: Chisel implementation, synthesized at 1GHz (TSMC 7nm)
3. Analytical Model: Roofline analysis with bandwidth reduction factors
4. Sensitivity Studies:

• Dimension count (64 to 2048)
• CTT size (16 to 128 entries)
• Threshold conservativeness (β = 2 to 5)

4.6 Expected Results

| Metric | vs. CPU | vs. GPU | vs. PQ |
|--------|---------|---------|--------|
| QPS | 8-12× | 2-3× | 1.5-2× |
| QPS/Watt | 15-20× | 4-6× | 3-4× |
| Recall@10 | = | = | +5-8% |
| Memory BW | -70-85% | -60-75% | -40-50% |

---

5. Key Novelty Claims

1. First hardware mechanism for speculative distance computation with memory request abortion in vector search
2. Statistically-grounded early termination with provable false rejection bounds
3. Dimension importance-aware fetch reordering at the memory interface level
4. Co-design of memory controller and computation unit for near-data filtering

---

6. Paper Outline

1. Introduction & Motivation (Vector DB explosion, memory wall)
2. Background (ANNS algorithms, memory hierarchy, prior PIM work)
3. Key Insight (Partial distance concentration phenomenon)
4. PRISM Architecture (Detailed hardware structures)
5. Statistical Foundations (Confidence bound derivation)
6. Implementation (RTL, area/power estimates)
7. Evaluation
8. Related Work
9. Conclusion

Target Venue: ISCA 2025 / MICRO 2025

---

AI-Generated Hints for Problem #005

These are 5 alternative architectural approaches generated by AI.
They are starting points for your own design—not the answer!

Hint 1 (Run 1)

Paper Title: "NameSieve: Content-Addressable Filtering Logic in the SSD Controller for Near-Storage Key-Value Acceleration"

---

1. Root Cause Analysis

The fundamental problem stems from a semantic mismatch between the storage abstraction and application intent:

First-Principles Breakdown:

1. Block-Addressable Storage Model: SSDs expose a logical block address (LBA) interface, treating all data as opaque byte streams. The controller has zero semantic awareness of the data it stores.

2. Key-Value Access Pattern: NVP lookups require content-based filtering (match name → return value), but the storage stack forces address-based retrieval followed by host-side filtering.

3. Bandwidth Amplification: For a hash bucket or B-tree leaf containing N entries, retrieving one matching pair requires transferring all N entries across:

• Internal bandwidth: NAND flash → SSD DRAM buffer
• External bandwidth: SSD → PCIe/NVMe → Host DRAM
• Memory bandwidth: Host DRAM → CPU cache

4. The Core Inefficiency: The SSD controller already reads data into its internal DRAM buffer for ECC correction and wear-leveling—the data passes through programmable logic but is never inspected for content relevance.

---

2. The Mechanism: NameSieve Architecture

2.1 High-Level Concept

NameSieve augments the SSD controller with a programmable content-filtering pipeline positioned between the flash translation layer (FTL) and the host interface. It performs key matching in-situ within the SSD's internal DRAM buffer, transmitting only verified matches across the PCIe interface.

2.2 Hardware Structures

#### A. Key Signature Register File (KSRF)

• Structure: 16-entry register file, each entry containing:
• 64-byte key field (supports variable-length keys up to 64B)
• 8-bit key length field
• 4-bit match mode (exact, prefix, suffix, contains)
• 16-bit request tag (for associating responses)
• Purpose: Holds active query keys programmed by the host via memory-mapped NVMe admin commands
• Hardware Cost: ~1.1 KB SRAM

#### B. Streaming Comparison Engine (SCE)

• Structure: Pipelined SIMD comparator array
• 64 parallel byte comparators per lane
• 4 lanes operating concurrently (matches 4 KSRF entries simultaneously)
• 3-stage pipeline: Key extraction → Comparison → Result aggregation
• Operation: As data streams from NAND through the read buffer, SCE performs streaming comparison against registered keys
• Throughput: Matches internal NAND channel bandwidth (~1.6 GB/s per channel × 8 channels = 12.8 GB/s aggregate)
• Hardware Cost: ~15K gates per lane, 60K gates total

#### C. Record Boundary Detector (RBD)

• Structure: Programmable finite state machine with:
• 4-byte delimiter register (configurable record separator)
• 2-byte key-offset register (byte offset of key within record)
• 2-byte key-length-offset register (for variable-length key extraction)
• 2-byte value-offset register
• 16-byte format descriptor (supports common serializations: length-prefixed, null-terminated, fixed-width)
• Purpose: Parses the byte stream to identify record boundaries and extract key fields for comparison
• Hardware Cost: ~8K gates + 64B configuration SRAM

#### D. Match Aggregation Buffer (MAB)

• Structure: 64 KB dual-ported SRAM organized as:
• 256 entries × 256 bytes per entry
• Each entry: {request_tag[16b], record_data[2040b], valid[1b], overflow[1b]}
• Purpose: Accumulates matched records before DMA to host
• Operation: When SCE signals a match, the corresponding record is copied from the read buffer to MAB
• Hardware Cost: 64 KB SRAM + arbitration logic (~5K gates)

#### E. Filtered DMA Engine (FDE)

• Structure: Modified DMA controller with:
• Scatter-gather descriptor support for variable-length responses
• Completion queue entry generation with match count
• Backpressure signaling to SCE when MAB fills
• Integration: Replaces standard NVMe DMA path for NameSieve-tagged commands
• Hardware Cost: ~12K gates (incremental over baseline DMA)

2.3 Operation Flow

┌─────────────────────────────────────────────────────────────────┐
│                        HOST SYSTEM                               │
│  ┌──────────┐    ┌─────────────┐    ┌──────────────────────┐   │
│  │ App/KV   │───▶│ NVMe Driver │───▶│ Filtered Results     │   │
│  │ Store    │    │ (extended)  │    │ (matches only)       │   │
│  └──────────┘    └─────────────┘    └──────────────────────┘   │
└────────────────────────┬────────────────────────────────────────┘
                         │ PCIe/NVMe
┌────────────────────────▼────────────────────────────────────────┐
│                     SSD CONTROLLER                               │
│  ┌────────┐   ┌─────────────────────────────────────────────┐   │
│  │  KSRF  │──▶│              Streaming Comparison           │   │
│  │(16 keys)│  │                 Engine (SCE)                │   │
│  └────────┘   └──────────────────┬──────────────────────────┘   │
│                                  │ match signals                 │
│  ┌────────────────┐    ┌────────▼────────┐    ┌─────────────┐  │
│  │ Record Boundary│───▶│ Read Buffer     │───▶│ Match Agg.  │  │
│  │ Detector (RBD) │    │ (existing DRAM) │    │ Buffer(MAB) │  │
│  └────────────────┘    └─────────────────┘    └──────┬──────┘  │
│                                                       │         │
│  ┌─────────────────────────────────────────────────▼─────────┐ │
│  │              Filtered DMA Engine (FDE)                     │ │
│  └────────────────────────────────────────────────────────────┘ │
│                              │                                   │
│  ┌───────────────────────────▼───────────────────────────────┐  │
│  │                    NAND Flash Array                        │  │
│  │              (unchanged - standard FTL)                    │  │
│  └────────────────────────────────────────────────────────────┘  │
└─────────────────────────────────────────────────────────────────┘

2.4 Programming Interface (NVMe Extension)

// New NVMe Admin Command: NAMESIEVE_REGISTER_KEY (opcode 0xC0)
struct namesieve_register_cmd {
    uint8_t  opcode;           // 0xC0
    uint8_t  key_slot;         // 0-15
    uint8_t  match_mode;       // EXACT|PREFIX|SUFFIX|CONTAINS
    uint8_t  key_length;       // 1-64
    uint16_t request_tag;      // for response correlation
    uint8_t  reserved[2];
    uint64_t key_data[8];      // 64-byte key
};
// New NVMe I/O Command: NAMESIEVE_FILTERED_READ (opcode 0x82)
struct namesieve_read_cmd {
    uint8_t  opcode;           // 0x82
    uint8_t  flags;            // RETURN_ALL_MATCHES | RETURN_FIRST
    uint16_t key_mask;         // bitmask of KSRF slots to match against
    uint64_t start_lba;        // scan region start
    uint64_t num_blocks;       // scan region size
    uint64_t result_buffer;    // host DMA address for matches
    uint32_t max_results;      // limit on returned records
};

---

3. Why It Works: First-Principles Reasoning

3.1 Exploiting Existing Data Movement

Principle: Data already transits through the SSD controller's DRAM buffer for ECC decoding, read-retry handling, and caching. NameSieve piggybacks filtering on this mandatory data path with zero additional NAND reads.

Quantification: A 4TB SSD with 8 NAND channels sustains ~12.8 GB/s internal read bandwidth but only ~7 GB/s PCIe 4.0 x4 external bandwidth. NameSieve exploits this 1.8× internal bandwidth surplus for filtering.

3.2 Bandwidth Reduction Analysis

Selectivity Factor (σ): Fraction of records matching the query key.

| Scenario | Records Scanned | Baseline Transfer | NameSieve Transfer | Reduction |
|----------|-----------------|-------------------|--------------------| ----------|
| Point lookup (σ=10⁻⁶) | 1M | 256 MB | 256 B | 10⁶× |
| Range scan (σ=10⁻³) | 1M | 256 MB | 256 KB | 10³× |
| Bulk filter (σ=10⁻²) | 1M | 256 MB | 2.56 MB | 100× |

3.3 Latency Composition

Baseline Path:

T_baseline = T_nand_read + T_internal_xfer + T_pcie_xfer + T_host_filter
           = 80μs + 20μs + (256MB/7GB/s) + (256MB × cycles/byte)
           = 80μs + 20μs + 36.6ms + ~50ms
           ≈ 87ms for 1M record scan

NameSieve Path:

T_namesieve = T_nand_read + T_internal_xfer + T_filter + T_pcie_xfer(matches)
            = 80μs + 20μs + 0μs (pipelined) + (256B/7GB/s)
            ≈ 100μs for point lookup

Speedup: 870× for point lookups in large datasets.

3.4 Energy Efficiency

Key Insight: PCIe transfers dominate SSD energy consumption at ~5 pJ/bit, while SRAM comparisons cost ~0.1 pJ/bit.

Energy per Query:

• Baseline: 256MB × 8 bits × 5 pJ = 10.24 mJ
• NameSieve: 256MB × 8 bits × 0.1 pJ (compare) + 256B × 8 bits × 5 pJ (transfer) = 0.2 mJ + 10 nJ ≈ 0.2 mJ

Energy Reduction: ~50× for typical queries.

---

4. Evaluation Plan

4.1 Experimental Infrastructure

#### Hardware Prototype

• Platform: OpenSSD Cosmos+ board (Xilinx Zynq-7000 + custom FTL)
• Modification: Implement NameSieve in programmable logic (~15K LUTs estimated)
• Comparison Points:
• Baseline NVMe SSD (Samsung 980 Pro)
• Computational Storage prototype (Samsung SmartSSD)
• Software-emulated NameSieve (for validation)

#### Simulation

• Simulator: MQSim (extended with NameSieve controller model)
• Configuration: 8-channel, 4-way interleaved, 3D TLC NAND timing from Samsung V-NAND

4.2 Baselines

| System | Description |
|--------|-------------|
| NVMe-Baseline | Standard SSD + host-side filtering |
| SPDK-Optimized | Polled I/O with kernel bypass |
| RocksDB-Direct | LSM-tree with direct I/O |
| SmartSSD-ISP | Samsung's in-storage processing with ARM cores |
| Caribou | FPGA-based near-storage processing (OSDI'20) |
| LeapIO | Programmable storage with eBPF (ASPLOS'20) |

4.3 Workloads

| Workload | Description | Selectivity |
|----------|-------------|-------------|
| YCSB-A | 50% read, 50% update, Zipfian | Variable |
| YCSB-E | 95% scan, 5% insert | 10⁻³ - 10⁻¹ |
| Twitter-Cache | Production KV trace from Twitter | 10⁻⁶ |
| Facebook-ETC | Memcached trace from FB | 10⁻⁵ |
| TPC-H Q6 | Analytical filter query | 10⁻² |
| Synthetic-Sweep | Controlled selectivity 10⁻⁶ to 1 | Swept |

4.4 Metrics

| Category | Metric | Measurement Method |
|----------|--------|-------------------|
| Performance | Queries/second | End-to-end throughput |
| | 99th percentile latency | Histogram analysis |
| | Bandwidth utilization | PCIe analyzer + internal counters |
| Efficiency | Energy per query | Power meter integration |
| | Bandwidth amplification factor | Bytes read from NAND / Bytes transferred to host |
| Scalability | Throughput vs. dataset size | 100GB to 4TB datasets |
| | Throughput vs. key count | 1 to 16 concurrent keys |
| Overhead | Area cost | Post-synthesis gate count |
| | Controller latency overhead | Microbenchmark isolation |

4.5 Key Experiments

1. Selectivity Sensitivity: Sweep σ from 10⁻⁶ to 1, measure crossover point where NameSieve overhead exceeds benefit.

2. Multi-Key Batching: Evaluate throughput with 1, 4, 8, 16 concurrent registered keys.

3. Record Size Impact: Test with 64B, 256B, 1KB, 4KB records to understand RBD parsing overhead.

4. Mixed Workload: Interleave NameSieve queries with standard I/O to measure interference.

5. Endurance Study: Verify no impact on NAND wear (filtering is read-only).

4.6 Expected Results

| Experiment | Expected Outcome |
|------------|------------------|
| Point lookup (σ=10⁻⁶) | 500-1000× throughput improvement |
| Scan query (σ=10⁻³) | 100-500× throughput improvement |
| Energy efficiency | 30-50× reduction in J/query |
| Crossover selectivity | NameSieve beneficial when σ < 0.3 |
| Area overhead | <5% of typical SSD controller die area |

---

5. Novelty and Contributions

1. Architectural Contribution: First hardware mechanism for content-addressable filtering integrated into the SSD controller's read path, requiring no NAND-level modifications.

2. Interface Contribution: Backward-compatible NVMe extension preserving standard block semantics while enabling semantic filtering.

3. Systems Contribution: Demonstrates that computational storage can be achieved with minimal, fixed-function hardware rather than general-purpose cores.

4. Analytical Contribution: Formal model relating selectivity, record size, and bandwidth to predict NameSieve benefit.

---

6. Potential Limitations and Mitigations

| Limitation | Mitigation |
|------------|------------|
| Fixed 64B max key size | Hierarchical hashing for longer keys |
| 16 concurrent keys | Pipelined key rotation for larger batches |
| Sequential scan only | Integrate with FTL indexing for random access |
| Single-SSD scope | Extend to NVMe-oF for distributed filtering |

---

This work positions NameSieve as a minimal, high-impact augmentation to commodity SSD controllers, achieving order-of-magnitude improvements in key-value workload performance through principled near-data filtering.

---

Hint 2 (Run 2)

Paper Title: "SieveStore: Content-Addressable Filtering Logic in the Storage Controller for Near-Data Name-Value Pair Resolution"

---

1. Root Cause Analysis

The fundamental problem stems from a semantic mismatch between the storage abstraction layer and application-level data access patterns:

First-Principles Breakdown:

1. Block-Addressable Storage Paradigm: SSDs expose a Logical Block Address (LBA) interface, treating data as opaque byte sequences. The storage device has zero knowledge of the semantic content it stores.

2. Name-Value Pair Access Pattern: NVP lookups are inherently content-addressed—the application seeks data based on a key's value, not its physical location.

3. Amplification Triangle: This mismatch creates three compounding inefficiencies:

• Read Amplification: Multiple candidate blocks must be fetched to find one match
• Transfer Amplification: All candidates traverse the PCIe/NVMe interface
• Compute Amplification: Host CPU cycles wasted on filtering non-matches

4. Bandwidth Bottleneck Hierarchy: Internal NAND bandwidth (modern SSDs: 8-16 GB/s aggregate across channels) exceeds PCIe Gen4 x4 bandwidth (~7 GB/s), which exceeds useful data bandwidth by orders of magnitude for sparse matches.

The root cause is that filtering logic resides exclusively at the host, forcing all candidate data to cross the narrowest bandwidth bottleneck (host interface) before elimination.

---

2. The Mechanism: SieveStore Architecture

2.1 Core Innovation: In-Controller Programmable Match Unit (PMU)

SieveStore introduces a dedicated hardware filtering pipeline within the SSD controller that performs key-matching before data crosses the host interface.

2.2 Hardware Structures

#### A. Key Signature Cache (KSC)

┌─────────────────────────────────────────────────────────┐
│                  Key Signature Cache                     │
├──────────┬──────────┬──────────┬────────────────────────┤
│ Entry ID │ Key Hash │ Key Mask │ Match Action Config    │
│ (8 bits) │ (64 bits)│ (64 bits)│ (16 bits)              │
├──────────┼──────────┼──────────┼────────────────────────┤
│    0     │ 0xA3F... │ 0xFFF... │ RETURN_VALUE           │
│    1     │ 0x7B2... │ 0xFF0... │ RETURN_BLOCK           │
│   ...    │   ...    │   ...    │        ...             │
└──────────┴──────────┴──────────┴────────────────────────┘

• Capacity: 256 entries (configurable)
• Structure: Fully-associative CAM with parallel lookup
• Purpose: Stores pre-computed signatures of keys being searched
• Hardware: ~2KB SRAM + CAM match logic

#### B. Streaming Match Engine (SME)

                    ┌─────────────────────────────────┐
    From NAND       │     Streaming Match Engine      │
    Flash Channels  │                                 │
         │          │  ┌─────────┐    ┌───────────┐  │
         ▼          │  │ Key     │    │ Signature │  │
    ┌─────────┐     │  │ Extract │───▶│ Compute   │  │
    │ Page    │────▶│  │ Unit    │    │ (CRC64)   │  │
    │ Buffer  │     │  └─────────┘    └─────┬─────┘  │
    └─────────┘     │                       │        │
                    │                       ▼        │
                    │              ┌─────────────┐   │
                    │              │ CAM Lookup  │◀──┼── From KSC
                    │              │ (Parallel)  │   │
                    │              └──────┬──────┘   │
                    │                     │          │
                    │         ┌───────────┴────────┐ │
                    │         ▼                    ▼ │
                    │    ┌─────────┐         ┌──────┐│
                    │    │ Match   │         │ Drop ││
                    │    │ Queue   │         │      ││
                    │    └────┬────┘         └──────┘│
                    └─────────┼──────────────────────┘
                              ▼
                         To Host DMA

SME Pipeline Stages (5-stage, pipelined):
1. Key Extraction: Parses NVP format header, extracts key bytes
2. Signature Computation: CRC64 hash with configurable polynomial
3. CAM Lookup: Parallel match against all KSC entries
4. Decision Logic: Match → enqueue; No match → drop
5. Value Extraction: On match, extract associated value for transfer

Hardware Budget:

• Key Extractor: Configurable offset/length registers + byte shifter
• CRC64 Unit: 64-bit LFSR, ~500 gates
• CAM Array: 256×64-bit, ~50K gates
• Control Logic: ~10K gates
• Total: <100K gates, negligible vs. modern SSD controllers (millions of gates)

#### C. Format Descriptor Table (FDT)

┌────────────────────────────────────────────────────────────┐
│                  Format Descriptor Table                    │
├──────────┬────────────┬────────────┬───────────┬───────────┤
│ Format ID│ Key Offset │ Key Length │ Val Offset│ Val Length│
├──────────┼────────────┼────────────┼───────────┼───────────┤
│    0     │     0      │    16      │    16     │  Variable │
│    1     │     4      │    32      │    40     │    256    │
└──────────┴────────────┴────────────┴───────────┴───────────┘

• Purpose: Supports multiple NVP serialization formats
• Entries: 16 formats (covers RocksDB, LevelDB, Redis, custom)
• Hardware: 16×40-bit register file

#### D. Match Result Buffer (MRB)

• Structure: 64KB dual-port SRAM ring buffer
• Purpose: Stages matched values for DMA to host
• Features:
• Coalesces small values into larger DMA transfers
• Maintains ordering metadata for out-of-order completion

2.3 Operation Flow

┌─────────────────────────────────────────────────────────────────┐
│                        SieveStore Operation                      │
├─────────────────────────────────────────────────────────────────┤
│                                                                  │
│  1. HOST SETUP PHASE                                            │
│     ┌──────────┐    NVMe Vendor Command      ┌──────────────┐  │
│     │   Host   │ ──────────────────────────▶ │ SSD          │  │
│     │   CPU    │   "SIEVE_SEARCH" opcode     │ Controller   │  │
│     └──────────┘   + Key signatures          └──────────────┘  │
│                    + LBA range                                  │
│                    + Format ID                                  │
│                                                                  │
│  2. IN-STORAGE FILTERING PHASE                                  │
│     ┌────────┐    ┌────────┐    ┌────────┐    ┌────────┐       │
│     │ NAND   │───▶│ Page   │───▶│  SME   │───▶│  MRB   │       │
│     │Channel │    │ Buffer │    │Pipeline│    │        │       │
│     └────────┘    └────────┘    └────┬───┘    └───┬────┘       │
│                                      │            │             │
│                                      ▼            │             │
│                                 [Non-matches      │             │
│                                  Dropped]         │             │
│                                                   │             │
│  3. RESULT TRANSFER PHASE                         │             │
│     ┌──────────┐    PCIe DMA (Matches Only)  ┌───┴────┐        │
│     │   Host   │ ◀─────────────────────────  │  MRB   │        │
│     │  Memory  │                             └────────┘        │
│     └──────────┘                                               │
│                                                                  │
└─────────────────────────────────────────────────────────────────┘

2.4 NVMe Command Extension

New vendor-specific command: SIEVE_SEARCH (Opcode 0xC0)

struct sieve_search_cmd {
    uint8_t  opcode;           // 0xC0
    uint8_t  flags;            // Bit 0: exact_match, Bit 1: prefix_match
    uint16_t num_keys;         // Number of keys to search (1-256)
    uint64_t start_lba;        // Search range start
    uint64_t end_lba;          // Search range end
    uint8_t  format_id;        // Index into FDT
    uint64_t key_sigs[256];    // Pre-computed key signatures
    uint64_t result_buffer;    // Host DMA address for results
};

2.5 Handling Hash Collisions

Two-Phase Verification Protocol:
1. Phase 1 (In-Storage): Signature-based filtering (may have false positives)
2. Phase 2 (Host): Exact key comparison on transferred candidates

False Positive Rate: With 64-bit CRC and typical key distributions, FPR < 10⁻¹⁸ per comparison. For practical datasets, host verification is rarely needed.

---

3. Why It Works: First-Principles Reasoning

3.1 Bandwidth Hierarchy Exploitation

┌─────────────────────────────────────────────────────────────┐
│              Bandwidth Hierarchy (Modern SSD)                │
├─────────────────────────────────────────────────────────────┤
│                                                              │
│   NAND Aggregate BW:     ████████████████████  16 GB/s      │
│   Controller Internal:   ██████████████████    14 GB/s      │
│   PCIe Gen4 x4:          ███████              7 GB/s        │
│   Useful Data (1% hit):  █                    0.16 GB/s     │
│                                                              │
│   SieveStore transfers:  █                    ~0.16 GB/s    │
│   (Only matches)                                             │
│                                                              │
└─────────────────────────────────────────────────────────────┘

Key Insight: By filtering at the controller, we transform the bottleneck from "PCIe bandwidth" to "match rate × value size"—typically 10-100× improvement.

3.2 Compute-Storage Co-location Principle

The filtering operation (hash + compare) requires:

• Compute: ~100 cycles per key-value pair
• Data Movement: 0 bytes (data already in controller for NAND→DRAM transfer)

Performing this at the host requires:

• Compute: Same ~100 cycles
• Data Movement: Full KV pair across PCIe (latency + bandwidth cost)

Amdahl's Law Application: If 99% of data is non-matching, eliminating 99% of transfers provides up to 100× speedup on the I/O-bound portion.

3.3 Energy Efficiency

Energy per filtered byte:

Host path:    PCIe TX (5 pJ/bit) + DRAM write (10 pJ/bit) + CPU filter (50 pJ/op)

                  = ~15 pJ/bit + CPU overhead
  

SieveStore:   SRAM access (0.5 pJ/bit) + CAM lookup (2 pJ/op)

                  = ~2.5 pJ/bit
                  
  Energy reduction: ~6× per filtered byte

3.4 Latency Reduction

Traditional path:

NAND Read → Controller DRAM → PCIe TX → Host DRAM → CPU Cache → Filter → Result
   50μs          5μs            10μs        5μs        1μs      0.1μs
   Total: ~71μs per block, repeated for all candidates

SieveStore path:

NAND Read → Controller DRAM → SME Filter → PCIe TX (matches only) → Host DRAM
   50μs          5μs            0.5μs            10μs                  5μs
   Total: ~70μs, but only for matching blocks

For 1% hit rate over 1000 blocks: Traditional = 71ms, SieveStore = 0.7ms + 10×70μs = 1.4ms → 50× latency reduction

---

4. Evaluation Plan

4.1 Experimental Setup

#### Hardware Prototype Options:
1. FPGA-based SSD Controller (Primary)

• Platform: Xilinx Alveo U280 with OpenSSD firmware
• Implement SME as custom RTL block
• Interface: NVMe over PCIe Gen3 x4

2. Cycle-Accurate Simulation (Validation)

• Extend MQSim or FEMU with SieveStore logic
• Model NAND timing, controller pipeline, PCIe

3. Analytical Model (Scalability Studies)

• Queuing theory model for throughput bounds

#### Software Stack:

• Modified NVMe driver with SIEVE_SEARCH support
• Integration shims for RocksDB, Redis, custom KV stores

4.2 Baselines

| Baseline | Description |
|----------|-------------|
| Vanilla SSD | Standard NVMe read + host-side filtering |
| Smart SSD (Samsung) | ARM cores in SSD running filter code |
| Bloom Filter Index | Host-side Bloom filter to reduce reads |
| LSM Compaction | Optimized LSM tree with better locality |
| FPGA-NIC (NetSSD) | Network-attached storage with FPGA filter |

4.3 Workloads

| Workload | Description | Expected Selectivity |
|----------|-------------|---------------------|
| YCSB-A | 50% read, 50% update, Zipfian | 0.001% - 1% |
| YCSB-E | 95% scan, 5% insert | 1% - 10% |
| Twitter Cache | Real trace, power-law keys | 0.01% |
| Facebook ETC | Memcached trace | 0.1% |
| Synthetic Sweep | Controlled selectivity 0.001% - 50% | Variable |

4.4 Metrics

#### Primary Metrics:
1. Throughput (ops/sec): End-to-end lookup rate
2. Latency (μs): P50, P99, P99.9 lookup latency
3. Bandwidth Efficiency: Useful bytes / Total bytes transferred
4. Energy per Operation (μJ/op): Measured via power meters

#### Secondary Metrics:
5. Host CPU Utilization: Freed cycles for application
6. SSD Internal Bandwidth Utilization: Channel saturation
7. Hardware Overhead: Gates, power, area (from synthesis)

4.5 Experiments

#### Experiment 1: Throughput Scaling

• Variable: Dataset size (10GB - 1TB)
• Fixed: Key size (16B), Value size (256B), Selectivity (0.1%)
• Goal: Show SieveStore maintains throughput as data scales

#### Experiment 2: Selectivity Sensitivity

• Variable: Match selectivity (0.001% - 50%)
• Fixed: Dataset 100GB
• Goal: Identify crossover point where filtering overhead exceeds benefit

#### Experiment 3: Value Size Impact

• Variable: Value size (64B - 64KB)
• Fixed: Dataset 100GB, Selectivity 0.1%
• Goal: Show benefit increases with larger values

#### Experiment 4: Multi-Key Batch Efficiency

• Variable: Batch size (1 - 256 keys)
• Fixed: Dataset 100GB
• Goal: Demonstrate KSC parallelism benefits

#### Experiment 5: Energy Efficiency

• Metric: Operations per Joule
• Comparison: All baselines under iso-throughput conditions

#### Experiment 6: Real Application Integration

• System: RocksDB with SieveStore backend
• Workload: Production-like YCSB mix
• Metric: End-to-end application throughput, tail latency

4.6 Expected Results

| Metric | vs. Vanilla SSD | vs. Smart SSD |
|--------|-----------------|---------------|
| Throughput | 10-50× | 3-5× |
| P99 Latency | 20-100× lower | 5-10× lower |
| Energy/Op | 5-10× lower | 2-3× lower |
| BW Efficiency | 50-1000× | 10-50× |

4.7 Sensitivity Analysis

• Hash Function Choice: CRC64 vs. xxHash vs. MurmurHash
• KSC Size: 64 vs. 256 vs. 1024 entries
• Pipeline Depth: 3 vs. 5 vs. 7 stages
• Format Flexibility: Fixed vs. programmable key extraction

---

5. Novelty Claims

1. First dedicated hardware filtering unit in SSD controller for content-based data reduction (vs. general-purpose ARM cores in Smart SSDs)

2. CAM-based parallel key signature matching enabling O(1) lookup regardless of search key count

3. Format-agnostic key extraction via programmable descriptors, supporting diverse NVP serializations

4. Minimal hardware overhead (<100K gates) achieving order-of-magnitude improvements

5. NVMe-compatible command extension enabling transparent integration with existing storage stacks

---

6. Potential Concerns & Mitigations

| Concern | Mitigation |
|---------|------------|
| Hash collisions causing false positives | Two-phase verification; 64-bit hash provides negligible FPR |
| Limited KSC capacity | Batched queries; LRU replacement; host-side query scheduling |
| Format diversity | Programmable FDT covers common formats; extensible |
| Adoption barrier | NVMe vendor command is standard extension mechanism |
| Security (data leakage via timing) | Constant-time CAM lookup; optional encryption support |

---

This architecture transforms the storage device from a passive block server into an active participant in data retrieval, exploiting the fundamental insight that the cheapest byte to transfer is the one that never leaves the device.

---

Hint 3 (Run 3)

Paper Title: "SieveStore: Content-Addressable Filtering Logic in the Storage Controller for Near-Data Name-Value Pair Resolution"

---

1. Root Cause Analysis

The fundamental problem stems from a semantic mismatch between the storage interface abstraction and application-level data access patterns.

First-Principles Breakdown:

1. Block-Addressable Storage Paradigm: SSDs expose a logical block address (LBA) interface inherited from HDDs. This interface is location-based, not content-based. The storage device has no semantic understanding of what constitutes a "match."

2. Amplified Data Movement: For NVP lookups, the host must:

• Issue read commands for candidate blocks (based on hash buckets, B-tree leaves, etc.)
• Transfer entire candidate sets across PCIe/NVMe
• Perform string/key comparison in host DRAM
• Discard 90-99% of transferred data as non-matches

3. Bandwidth Bottleneck Location: The bottleneck exists at two points:

• Internal: NAND flash channels → SSD controller DRAM
• External: SSD controller → Host (PCIe Gen4/5: 8-16 GB/s)

4. Root Cause: The storage controller possesses the computational capability to perform simple comparisons but lacks (a) the interface to receive comparison predicates, and (b) the hardware structures to execute filtering inline with data movement.

---

2. The Mechanism: SieveStore Architecture

Overview

SieveStore introduces a Predicate Filtering Unit (PFU) integrated into the SSD controller's data path, enabling the host to offload key-matching logic to the storage device. Only matching NVP entries cross the host interface.

Hardware Components

#### 2.1 Predicate Register File (PRF)

┌─────────────────────────────────────────────────────┐
│  PREDICATE REGISTER FILE (PRF)                      │
├─────────┬──────────┬────────────┬──────────────────┤
│ Pred_ID │ Key_Hash │ Key_Bytes  │ Match_Mode       │
│ (4-bit) │ (64-bit) │ (0-256B)   │ (2-bit)          │
├─────────┼──────────┼────────────┼──────────────────┤
│   0     │ 0xA3F2.. │ "user_123" │ EXACT            │
│   1     │ 0xB1C4.. │ "session_" │ PREFIX           │
│   ...   │          │            │                  │
└─────────┴──────────┴────────────┴──────────────────┘
Capacity: 16 entries × 264 bytes = 4.2 KB SRAM

• Match Modes: EXACT (full key match), PREFIX (prefix match), HASH_ONLY (Bloom-filter style)
• Loaded via new NVMe admin command: PREDICATE_LOAD

#### 2.2 Inline Filtering Engine (IFE)
Positioned between the Flash Translation Layer (FTL) read buffer and the NVMe submission queue:

                    ┌─────────────────────────────────────┐
   NAND Flash       │         SSD CONTROLLER              │
   Channels         │                                     │
       │            │  ┌─────────┐    ┌───────────────┐   │
       ▼            │  │  FTL    │    │   PREDICATE   │   │
   ┌───────┐        │  │  Read   │───▶│   REGISTER    │   │
   │ Page  │───────▶│  │ Buffer  │    │   FILE (PRF)  │   │
   │ Buffer│        │  └────┬────┘    └───────┬───────┘   │
   └───────┘        │       │                 │           │
                    │       ▼                 ▼           │
                    │  ┌─────────────────────────────┐    │
                    │  │   INLINE FILTERING ENGINE   │    │
                    │  │  ┌───────┐  ┌───────────┐   │    │
                    │  │  │ Hash  │  │ Comparator│   │    │
                    │  │  │ Unit  │  │  Array    │   │    │
                    │  │  │(CRC64)│  │ (16-wide) │   │    │
                    │  │  └───┬───┘  └─────┬─────┘   │    │
                    │  │      └──────┬─────┘         │    │
                    │  │             ▼               │    │
                    │  │      ┌───────────┐          │    │
                    │  │      │  Match    │          │    │
                    │  │      │  Bitmap   │          │    │
                    │  │      └─────┬─────┘          │    │
                    │  └────────────┼────────────────┘    │
                    │               ▼                     │
                    │  ┌─────────────────────────────┐    │
                    │  │    OUTPUT COMPACTION UNIT   │    │
                    │  │   (Gather matching entries) │    │
                    │  └─────────────┬───────────────┘    │
                    │                │                    │
                    └────────────────┼────────────────────┘
                                     ▼
                              Host Interface
                               (PCIe/NVMe)

#### 2.3 IFE Microarchitecture Details

Hash Unit:

• 64-bit CRC polynomial computation
• Pipelined: 1 hash per cycle for 64-byte key chunks
• Area: ~5K gates

Comparator Array:

• 16 parallel byte-wise comparators (one per PRF entry)
• Each comparator: 256-byte SIMD comparison with early termination
• Implemented as 16 × 256-bit XOR + NOR reduction trees
• Area: ~20K gates per comparator

Match Bitmap Generator:

• 16-bit vector indicating which predicates matched
• Feeds into Output Compaction Unit

Output Compaction Unit (OCU):

• Streaming gather unit with 4KB staging buffer
• Packs only matching KV pairs into contiguous output
• Generates completion metadata: {Pred_ID, Offset, Length}[]

#### 2.4 NVMe Command Extensions

// New NVMe I/O Command: FILTERED_READ
struct nvme_filtered_read_cmd {
    uint8_t  opcode;           // 0x82 (vendor-specific)
    uint16_t command_id;
    uint32_t nsid;
    uint64_t slba;             // Starting LBA
    uint32_t nlb;              // Number of logical blocks
    uint16_t predicate_mask;   // Which PRF entries to apply
    uint8_t  filter_mode;      // AND/OR predicate combination
    uint64_t prp1, prp2;       // Output buffer (matches only)
    uint64_t metadata_prp;     // Match metadata output
};

#### 2.5 Data Format Awareness

SieveStore requires minimal format knowledge:

• Key-Length-Value (KLV) encoding: [2B key_len][key][4B val_len][value]
• Format descriptor loaded at initialization
• IFE parses inline during streaming read

---

3. Why It Works: First-Principles Reasoning

3.1 Bandwidth Amplification Elimination

Quantitative Model:

Let:

• $N$ = candidate entries to scan
• $S_{avg}$ = average entry size (key + value)
• $M$ = number of matches (typically $M \ll N$)
• $B_{ext}$ = external bandwidth (PCIe)
• $B_{int}$ = internal bandwidth (NAND channels)

Baseline Data Movement: $$D_{baseline} = N \times S_{avg}$$

SieveStore Data Movement: $$D_{sieve} = M \times S_{avg} + N \times S_{key}$$

Where $S_{key} \ll S_{avg}$ (keys processed internally, only matches transferred).

Reduction Factor: $$\frac{D_{baseline}}{D_{sieve}} \approx \frac{N}{M} \times \frac{S_{avg}}{S_{avg} + \frac{N-M}{M} \times S_{key}}$$

For typical NVP workloads ($N/M = 100$, $S_{avg} = 1KB$, $S_{key} = 32B$):
$$\text{Reduction} \approx 25-50\times$$

3.2 Latency Hiding Through Pipelining

• Hash computation overlaps with NAND read latency (~50-100μs)
• Comparison executes at DRAM speed (controller-side)
• No additional latency for non-matching entries

3.3 Energy Efficiency

• Data not transferred = energy saved (PCIe: ~5 pJ/bit)
• Filtering logic: ~100 mW (negligible vs. NAND array power)

3.4 Why In-Controller (Not In-NAND)

• NAND dies lack logic density for comparators
• Controller already has ARM cores + SRAM
• Unified filtering point for all channels

---

4. Evaluation Plan

4.1 Baselines

| System | Description |
|--------|-------------|
| Baseline-Host | Standard NVMe SSD + host-side filtering (RocksDB, LevelDB) |
| Baseline-ISP | In-Storage Processing with ARM cores (SmartSSD style) |
| Baseline-FPGA | Computational storage with FPGA filtering (Samsung SmartSSD) |
| SieveStore | Proposed hardware filtering unit |

4.2 Workloads

| Workload | Description | Selectivity |
|----------|-------------|-------------|
| YCSB-E | Range scans on key-value store | 0.1% - 5% |
| TPC-H Q6 | Filtered scan (adapted for NVP) | 2% |
| Social Graph | Friend-of-friend lookups | 0.01% |
| Log Analytics | Grep-style pattern matching | 0.5% |
| Genomics | K-mer exact matching | 0.001% |

4.3 Metrics

| Metric | Measurement Method |
|--------|-------------------|
| Throughput | Matched entries/second |
| Latency | P50/P99 lookup latency |
| Bandwidth Efficiency | Useful bytes / Total bytes transferred |
| Energy per Query | Joules/query (host + SSD) |
| Area Overhead | Gate count, mm² at 12nm |
| TCO Impact | $/query at scale |

4.4 Experimental Infrastructure

Simulation:

• MQSim (SSD simulator) extended with IFE model
• Cycle-accurate RTL for filtering engine (Verilog)
• Validated against real NVMe traces

Prototype:

• OpenSSD Cosmos+ platform (Xilinx FPGA-based SSD)
• IFE implemented in ~15K LUTs
• Real NVMe driver modifications (Linux kernel)

Sensitivity Studies:

• PRF size (4, 8, 16, 32 entries)
• Key size distribution impact
• Multi-tenant predicate sharing
• Interaction with SSD garbage collection

4.5 Expected Results

| Metric | Baseline | SieveStore | Improvement |
|--------|----------|------------|-------------|
| Throughput | 50K queries/s | 800K queries/s | 16× |
| P99 Latency | 12 ms | 0.8 ms | 15× |
| Bandwidth Util | 5% (useful) | 85% (useful) | 17× |
| Energy/Query | 2.1 mJ | 0.15 mJ | 14× |
| Area Overhead | - | 0.8 mm² | <3% of controller |

---

5. Novelty Claims

1. First hardware-level predicate filtering unit integrated into commodity SSD controller architecture
2. New NVMe command semantics for content-aware storage access
3. Output compaction mechanism that maintains streaming efficiency while filtering
4. Quantitative model for bandwidth amplification in NVP workloads with closed-form reduction bounds

---

6. Broader Impact

SieveStore represents a step toward semantically-aware storage interfaces that bridge the gap between application intent and physical data organization. The principles extend to:

• SQL pushdown for analytical databases
• Tensor filtering for ML inference serving
• Packet filtering for network-attached storage

---

Hint 4 (Run 4)

Automated Architectural Invention Report

Title of Paper

"NVP-Filter: Content-Aware In-Storage Filtering for Name-Value Pair Workloads via Programmable Hash-Match Engines"

Alternative: "Sifting at the Source: Near-Storage Bloom Filtering and Key-Match Acceleration for Data-Intensive KV Stores"

---

1. Root Cause Analysis

The Fundamental Problem

The architectural mismatch stems from a semantic gap between how data is organized (by physical block address) and how it is accessed (by content/key). Current storage interfaces (NVMe, SATA) expose only a location-based abstraction (LBA → data), forcing all content-aware filtering to occur after data traverses:

1. SSD internal bandwidth (NAND → controller DRAM)
2. PCIe/NVMe interface (SSD → host memory)
3. Memory hierarchy (DRAM → CPU caches)

For NVP lookups, the host requests candidate blocks based on hash bucket indices or range scans, but cannot express the predicate "only return blocks containing key K" to the storage device. This results in:

• Bandwidth amplification: Transferring N blocks to find 1 matching entry
• CPU cycles wasted: On filtering logic that could be offloaded
• Latency inflation: Serial dependency on data movement before filtering

First-Principles Insight

The key insight is that name matching is a deterministic, parallelizable operation that requires only:
1. A compact representation of the search key
2. Simple comparison logic (hash match + byte comparison)
3. Access to raw data before it crosses the storage interface

This logic is amenable to near-storage implementation because it requires minimal state, has high data locality, and can be expressed in fixed-function hardware.

---

2. The Mechanism: NVP-Filter Architecture

Overview

NVP-Filter introduces a programmable in-storage filtering layer between the Flash Translation Layer (FTL) and the host interface, consisting of three novel hardware structures:

┌─────────────────────────────────────────────────────────────────┐
│                     NVP-Filter SSD Controller                    │
├─────────────────────────────────────────────────────────────────┤
│  ┌──────────────┐  ┌──────────────────┐  ┌───────────────────┐  │
│  │ Key Register │  │  Bloom Filter    │  │  Match Engine     │  │
│  │    File      │──│  Bank Array      │──│  Array (MEA)      │  │
│  │   (KRF)      │  │    (BFB)         │  │                   │  │
│  └──────────────┘  └──────────────────┘  └───────────────────┘  │
│         │                   │                      │            │
│         ▼                   ▼                      ▼            │
│  ┌────────────────────────────────────────────────────────────┐ │
│  │              Filter Control Unit (FCU)                      │ │
│  └────────────────────────────────────────────────────────────┘ │
│                              │                                   │
├──────────────────────────────┼───────────────────────────────────┤
│                              ▼                                   │
│  ┌────────────────────────────────────────────────────────────┐ │
│  │           Standard FTL + NAND Interface                     │ │
│  └────────────────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────────────┘

Hardware Structure 1: Key Register File (KRF)

Purpose: Store active search keys for concurrent lookups

Implementation:

• 64 entries, each containing:
• key_hash[64b]: Precomputed hash of search key
• key_data[256B]: Full key content (variable length, max 256B)
• key_len[8b]: Actual key length
• query_id[8b]: Tag for response demultiplexing
• valid[1b]: Entry validity bit

Total Size: 64 × (64b + 2048b + 8b + 8b + 1b) ≈ 17 KB SRAM

Operation: Host issues FILTER_KEY_LOAD command via NVMe vendor-specific opcode, writing key material to KRF entry. Hardware computes key_hash using integrated hash unit.

Hardware Structure 2: Bloom Filter Bank Array (BFB)

Purpose: Rapid probabilistic pre-filtering to eliminate definite non-matches

Implementation:

• 8 parallel Bloom filter banks, each:
• 128 KB bit array (1M bits)
• 4 independent hash functions (H3 family, hardware-implemented)
• Partitioned by hash bucket range for parallelism

Total Size: 8 × 128 KB = 1 MB SRAM

Novelty: Filters are dynamically populated from metadata pages during normal I/O, not statically loaded. Each data page write updates the corresponding BFB partition via a shadow update queue.

Operation:

For each candidate page P read from NAND:
  bucket_id = P.header.hash_bucket
  bf_bank = BFB[bucket_id % 8]
  for each key K in KRF:
    if bf_bank.query(K.key_hash) == MAYBE_PRESENT:
      forward P to Match Engine Array
    else:
      discard P (definite non-match)

Hardware Structure 3: Match Engine Array (MEA)

Purpose: Exact key matching on pages that pass Bloom filter

Implementation:

• 16 parallel Match Engines (MEs), each containing:
• 4 KB page buffer: Holds one NAND page
• Key comparator: 256-bit wide SIMD comparator
• Offset scanner: FSM that parses NVP record format
• Result register: Stores {query_id, match_offset, value_ptr}

Per-ME Size: 4 KB buffer + ~2 KB logic ≈ 6 KB Total MEA Size: 16 × 6 KB = 96 KB

Operation:

For each page P forwarded from BFB:
  ME.load_page(P)
  for each record R in P:  // Hardware FSM parses format
    for each key K in KRF:
      if R.key_len == K.key_len:
        if SIMD_compare(R.key, K.key_data, K.key_len):
          emit MATCH(K.query_id, R.value_offset, R.value_len)

Hardware Structure 4: Filter Control Unit (FCU)

Purpose: Orchestration, command parsing, result aggregation

Implementation:

• Command decoder: Parses extended NVMe commands
• Scheduler: Assigns pages to MEs, manages KRF allocation
• Result aggregator: Coalesces matches, generates completion entries
• Statistics counters: Tracks filter efficiency for adaptive tuning

Key Registers:

• FCU_MODE[2b]: {BYPASS, BLOOM_ONLY, FULL_FILTER}
• FCU_STATS[256b]: Pages_read, pages_filtered, exact_matches, false_positives

New NVMe Command Interface

// Extended NVMe Command Structure
struct nvme_filter_read_cmd {
  uint8_t  opcode;        // 0xC0 (vendor-specific)
  uint8_t  flags;         // [0]: async, [1]: bloom_only
  uint16_t cid;           // Command ID
  uint32_t nsid;          // Namespace
  uint64_t slba;          // Starting LBA (hint for bucket range)
  uint32_t nlb;           // Number of logical blocks to scan
  uint64_t prp1;          // Result buffer pointer
  uint64_t prp2;          // Key buffer pointer (for bulk load)
  uint32_t key_mask;      // Bitmask of active KRF entries
  uint32_t rsvd;
};
// Completion Entry Extension
struct nvme_filter_completion {
  uint32_t dw0;           // Standard completion
  uint16_t match_count;   // Number of matches found
  uint16_t pages_scanned; // Total pages examined
  uint32_t filter_ratio;  // (pages_filtered / pages_read) × 1000
};

---

3. Why It Works: First-Principles Reasoning

Principle 1: Bandwidth Hierarchy Exploitation

NAND internal BW:    ~32 GB/s (8 channels × 4 GB/s)
Controller DRAM BW:  ~25 GB/s (DDR4-3200)
PCIe 4.0 x4 BW:      ~7 GB/s

Insight: By filtering at the controller, we exploit the 4.5× bandwidth advantage of internal paths over the host interface. For workloads with 90% filter selectivity, effective external bandwidth becomes 70 GB/s equivalent.

Principle 2: Bloom Filter Efficiency

For a Bloom filter with m bits, n elements, and k hash functions:

False positive rate ≈ (1 - e^(-kn/m))^k

With 1M bits per bank, 100K keys per partition, k=4:

FPR ≈ (1 - e^(-4×100000/1000000))^4 ≈ 1.5%

Result: 98.5% of non-matching pages eliminated before exact comparison, reducing MEA load by ~50× for typical workloads.

Principle 3: Parallelism Matching

The 16 Match Engines are sized to match the NAND read parallelism:

• 8 NAND channels × 2 planes = 16 concurrent page reads
• Each ME processes one page per ~10 µs (4KB @ 400 MB/s internal)
• Pipeline: Read(N) || Filter(N-1) || Compare(N-2)

Principle 4: Minimal State, Maximum Reuse

The KRF holds hot keys that exhibit temporal locality in NVP workloads. Studies show:

• Top 64 keys account for >80% of lookups in many KV stores
• Key registration amortizes over thousands of queries

---

4. Evaluation Plan

Experimental Setup

Hardware Prototype:

• FPGA-based SSD controller (Xilinx Alveo U280)
• Custom firmware on OpenSSD Cosmos+ platform
• 4× Samsung 970 EVO Plus NAND packages

Simulation:

• MQSim extended with filter pipeline model
• Cycle-accurate RTL simulation for MEA

Baselines

| System | Description |
|--------|-------------|
| Baseline-Host | Standard NVMe SSD + host-side filtering |
| Baseline-ISP | In-storage processing with ARM cores (Samsung SmartSSD) |
| BlueDBM | Prior near-storage KV work (ISCA'15) |
| INSIDER | Programmable SSD framework (ASPLOS'19) |
| NVP-Filter | Proposed mechanism |

Workloads

1. YCSB-KV: Workloads A-F on RocksDB/LevelDB
2. Twitter Cache: Production trace from Twitter Twemcache
3. Facebook ETC: Memcached trace from Facebook
4. Synthetic: Controlled key distribution (Zipf α = 0.5-1.5)

Metrics

| Metric | Definition |
|--------|------------|
| Throughput | Queries per second (QPS) |
| Latency | P50, P99, P999 query latency |
| Bandwidth Reduction | 1 - (bytes_to_host / bytes_from_NAND) |
| Energy Efficiency | Queries per Joule |
| Filter Effectiveness | True negative rate of Bloom stage |
| Area Overhead | mm² on 14nm process |
| Power Overhead | Watts at peak filtering load |

Key Experiments

Experiment 1: Throughput Scaling

• Vary dataset size from 64GB to 2TB
• Measure QPS for point lookups
• Expected: NVP-Filter maintains constant QPS; baselines degrade linearly

Experiment 2: Latency Distribution

• 10M queries under varying load (10%-90% saturation)
• CDF of latency
• Expected: 3-5× reduction in P99 latency

Experiment 3: Bandwidth Amplification

• Measure host-side bytes read per query
• Vary key selectivity (1/100 to 1/1M)
• Expected: 10-100× reduction in data movement

Experiment 4: Filter Sensitivity

• Vary Bloom filter size (256KB - 4MB)
• Vary KRF size (16 - 256 entries)
• Characterize knee in cost-benefit curve

Experiment 5: Area/Power Analysis

• Synthesize RTL to 14nm standard cells
• Compare against baseline controller
• Expected: <5% area overhead, <2W power increase

Expected Results Summary

| Metric | vs. Baseline-Host | vs. Baseline-ISP |
|--------|-------------------|------------------|
| Throughput | 8-15× | 2-4× |
| P99 Latency | 5-10× lower | 2-3× lower |
| BW Reduction | 50-100× | 10-20× |
| Energy/Query | 4-8× better | 1.5-2× better |

---

5. Novelty Claims

1. First fixed-function hardware for in-storage NVP filtering (vs. programmable ISP)
2. Dynamic Bloom filter population from metadata pages during normal I/O
3. Pipelined filter architecture matching NAND parallelism
4. NVMe command extension for predicate pushdown without OS changes

---

6. Potential Concerns & Mitigations

| Concern | Mitigation |
|---------|------------|
| Variable key/value sizes | FSM parser handles common formats (LevelDB, RocksDB SSTable) |
| Bloom filter staleness | Incremental update on write; periodic rebuild during GC |
| Security (key leakage) | KRF cleared on namespace detach; optional encryption |
| Generality | Programmable hash functions; configurable record format |

---

Conclusion: NVP-Filter addresses the fundamental bandwidth mismatch in NVP storage by introducing content-aware filtering hardware at the storage controller, achieving order-of-magnitude improvements in throughput and latency while requiring minimal silicon overhead.

---

Hint 5 (Run 5)

Title of Paper: "NameSieve: Near-Storage Content-Addressable Filtering for Bandwidth-Efficient Name-Value Pair Retrieval"

---

1. Root Cause Analysis

The fundamental issue is an architectural mismatch between data organization semantics and query semantics:

| Layer | Current Model | Required Model |
|-------|---------------|----------------|
| Storage | Block-addressed (LBA-based) | Content-addressed |
| Data Movement | Blind transfer (all candidate blocks) | Selective transfer (matches only) |
| Filtering Location | Host CPU (post-transfer) | Storage device (pre-transfer) |

The Root Cause: Traditional storage controllers are semantically blind—they understand physical addresses but not data content. When searching for a name N in a hash-based NVP store:

1. Hash function maps N to bucket(s) containing B candidate entries
2. All B entries must traverse: NAND→Controller→PCIe→Host DRAM→CPU
3. CPU filters to find the single match (or none)

This creates O(B) data movement for an O(1) logical operation, where B (bucket size) grows with dataset size and hash collision rates.

---

2. The Mechanism: NameSieve Architecture

2.1 High-Level Concept

NameSieve embeds a programmable content-filtering engine within the SSD controller that performs name matching before data crosses the device-host boundary. Only validated matches traverse the I/O interface.

2.2 Hardware Structures

#### Structure 1: Filter Descriptor Table (FDT)

┌─────────────────────────────────────────────────────────────┐
│ Filter Descriptor Table (FDT) - 64 entries, SRAM           │
├─────────┬──────────┬─────────────┬────────────┬────────────┤
│ FD_ID   │ Name_Hash│ Name_Offset │ Name_Length│ Match_Mode │
│ (6 bits)│ (64 bits)│ (16 bits)   │ (16 bits)  │ (4 bits)   │
├─────────┼──────────┼─────────────┼────────────┼────────────┤
│ 0       │ 0xA3F2...│ 0           │ 24         │ EXACT      │
│ 1       │ 0x7B1C...│ 8           │ 32         │ PREFIX     │
│ ...     │ ...      │ ...         │ ...        │ ...        │
└─────────────────────────────────────────────────────────────┘

• Name_Hash: 64-bit hash of target name for fast rejection
• Name_Offset: Byte offset of name field within NVP record
• Name_Length: Length of name to compare
• Match_Mode: EXACT, PREFIX, or RANGE comparison

#### Structure 2: Name Comparison Buffer (NCB)

┌────────────────────────────────────────────────────────────┐
│ Name Comparison Buffer - 4KB SRAM (holds target names)     │
├──────────────┬─────────────────────────────────────────────┤
│ Base Pointer │ Name Data (variable length, packed)         │
├──────────────┼─────────────────────────────────────────────┤
│ 0x000        │ "user:session:12345678\0"                   │
│ 0x018        │ "product:inventory:warehouse:NYC\0"         │
│ ...          │ ...                                         │
└────────────────────────────────────────────────────────────┘

#### Structure 3: Filter Processing Unit (FPU)

                    ┌─────────────────────────────────┐
                    │      Filter Processing Unit      │
                    │  (Placed between NAND and DRAM)  │
                    └─────────────────────────────────┘
                                    │
        ┌───────────────────────────┼───────────────────────────┐
        ▼                           ▼                           ▼
┌───────────────┐         ┌─────────────────┐         ┌─────────────────┐
│  Hash Compare │         │  String Compare │         │  Match Aggregator│
│    Engine     │         │     Engine      │         │                  │
├───────────────┤         ├─────────────────┤         ├─────────────────┤
│ • 4x parallel │         │ • 64B/cycle     │         │ • Bitmap output │
│   hash units  │         │   comparator    │         │ • Match counter │
│ • 1-cycle     │         │ • 8-stage       │         │ • DMA trigger   │
│   reject      │         │   pipeline      │         │                 │
└───────────────┘         └─────────────────┘         └─────────────────┘

Hash Compare Engine:

• Four 64-bit parallel comparators
• Computes rolling hash of incoming record's name field
• Fast rejection path: 1-cycle hash mismatch → discard record immediately

String Compare Engine:

• 64-byte wide SIMD comparator (using vectorized XOR + zero-detect)
• 8-stage pipeline: handles variable-length names up to 512 bytes
• Only activated when hash matches (reduces power consumption)

Match Aggregator:

• Maintains hit bitmap for multi-record queries
• Triggers selective DMA only for matched records

#### Structure 4: Selective Transfer Queue (STQ)

┌──────────────────────────────────────────────────────────────┐
│ Selective Transfer Queue - Circular Buffer, 256 entries      │
├────────┬──────────────┬────────────┬────────────┬───────────┤
│ Entry  │ Physical Page│ Offset     │ Length     │ FD_ID     │
├────────┼──────────────┼────────────┼────────────┼───────────┤
│ 0      │ 0x1A3F00     │ 2048       │ 256        │ 3         │
│ 1      │ 0x1A3F00     │ 3584       │ 128        │ 3         │
│ ...    │ ...          │ ...        │ ...        │ ...       │
└──────────────────────────────────────────────────────────────┘

• Only matched record locations are enqueued
• DMA engine fetches only these records to host

2.3 Data Flow

┌─────────────────────────────────────────────────────────────────────────┐
│                         NameSieve Data Flow                             │
│                                                                         │
│  ┌─────────┐    ┌─────────┐    ┌─────────────┐    ┌─────────────────┐  │
│  │  NAND   │───▶│  Flash  │───▶│   Filter    │───▶│  Match Buffer   │  │
│  │  Array  │    │  Buffer │    │  Processing │    │  (DRAM inside   │  │
│  │         │    │ (16KB)  │    │    Unit     │    │   controller)   │  │
│  └─────────┘    └─────────┘    └─────────────┘    └────────┬────────┘  │
│                                       │                     │           │
│                                       │ (discard            │ (matches  │
│                                       │  non-matches)       │  only)    │
│                                       ▼                     ▼           │
│                               ┌───────────────┐    ┌───────────────┐   │
│                               │   Bit Bucket  │    │   PCIe DMA    │   │
│                               │   (dropped)   │    │   to Host     │   │
│                               └───────────────┘    └───────────────┘   │
└─────────────────────────────────────────────────────────────────────────┘

2.4 New NVMe Command Extension

struct nvme_filter_read_cmd {
    uint8_t  opcode;           // 0x91 (vendor-specific)
    uint8_t  flags;
    uint16_t command_id;
    uint32_t nsid;
    uint64_t slba;             // Starting LBA of search region
    uint32_t nlb;              // Number of logical blocks to scan
    uint32_t filter_id;        // Index into FDT
    uint64_t name_ptr;         // Host address of name string
    uint16_t name_len;         // Length of name
    uint16_t record_size;      // Fixed record size (0 for variable)
    uint8_t  name_offset;      // Offset of name field in record
    uint8_t  reserved[3];
};

---

3. Why It Works: First-Principles Reasoning

Principle 1: Bandwidth Asymmetry Exploitation

| Interface | Bandwidth |
|-----------|-----------|
| Internal NAND channels (8-16 channels) | 4-8 GB/s |
| Controller internal bus | 8-16 GB/s |
| PCIe Gen4 x4 | ~7 GB/s |
| Filtering location impact | Critical |

Filtering inside the controller means:

• Internal bandwidth (abundant) absorbs the full scan
• External bandwidth (scarce) carries only matches
• Amplification factor = Dataset_size / Match_size (typically 100-10,000x)

Principle 2: Compute-Near-Data Efficiency

Energy cost of data movement vs. computation:

• Moving 64 bytes across PCIe: ~100 pJ
• Comparing 64 bytes in local SRAM: ~2 pJ
• 50x energy reduction per filtered record

Principle 3: Early Rejection via Hash Hierarchy

Two-stage filtering minimizes expensive string comparisons:
1. Stage 1 (Hash): 64-bit comparison → rejects 99.99% in 1 cycle
2. Stage 2 (String): Only ~0.01% reach expensive byte comparison

Expected operations per 1M records with 1 match:

• Hash comparisons: 1,000,000 (fast)
• String comparisons: ~100 (expensive but rare)

Principle 4: Semantic Interface Elevation

Traditional storage stack:

App → FS → Block Layer → NVMe Driver → SSD Controller → NAND
        [All layers are content-agnostic]

NameSieve stack:

App → NameSieve API → NVMe Filter Cmd → FPU → NAND
      [Content-awareness pushed into storage]

---

4. Evaluation Plan

4.1 Baselines

| System | Description |
|--------|-------------|
| Baseline-Host | Commodity NVMe SSD + Host CPU filtering |
| Baseline-GPU | NVMe + GPUDirect + GPU filtering |
| SmartSSD | Samsung SmartSSD with FPGA (software filter) |
| BPF-SSD | eBPF-based computational storage (XRP-style) |
| NameSieve | Proposed hardware mechanism |

4.2 Workloads

| Workload | Description | Dataset Size |
|----------|-------------|--------------|
| KV-Uniform | Synthetic, uniform key distribution | 256GB - 2TB |
| KV-Zipfian | Synthetic, skewed access pattern | 256GB - 2TB |
| RocksDB-YCSB | Real KV store, YCSB workloads A-F | 500GB |
| Redis-AOF | Redis append-only-file replay | 200GB |
| Graph-Property | Graph DB property lookups (Neo4j) | 1TB |

4.3 Metrics

| Category | Metrics |
|----------|---------|
| Performance | Query latency (P50, P99, P99.9), Throughput (queries/sec) |
| Bandwidth | Host I/O bandwidth utilization, Internal NAND read amplification |
| Energy | Joules per query, Total system power |
| Scalability | Performance vs. dataset size, Performance vs. selectivity |

4.4 Key Experiments

Experiment 1: Bandwidth Amplification

• Vary selectivity from 1/100 to 1/1,000,000
• Measure data transferred to host
• Expected: NameSieve achieves near-ideal (transfer ≈ match size)

Experiment 2: Latency Breakdown

• Microbenchmark single-key lookup latency
• Decompose: NAND read + Filter time + DMA time
• Expected: 2-5x latency reduction for cold queries

Experiment 3: Throughput Saturation

• Increase query rate until system saturates
• Identify bottleneck shift (host CPU → PCIe → NAND)
• Expected: 5-10x throughput improvement

Experiment 4: Energy Efficiency

• Measure system power during sustained workload
• Compute queries per Joule
• Expected: 10-30x improvement (less data movement)

Experiment 5: Sensitivity Analysis

• Vary: record size, name length, hash collision rate
• Identify sweet spots and pathological cases

4.5 Hardware Prototype Plan

| Phase | Implementation |
|-------|----------------|
| Phase 1 | Cycle-accurate simulator (gem5 + SSD model) |
| Phase 2 | FPGA prototype on OpenSSD platform |
| Phase 3 | ASIC synthesis for area/power estimates (45nm) |

4.6 Expected Results Summary

| Metric | Baseline-Host | NameSieve | Improvement |
|--------|---------------|-----------|-------------|
| P99 Latency (1TB scan) | 850 ms | 95 ms | 8.9x |
| Throughput (queries/s) | 1,200 | 12,500 | 10.4x |
| Host I/O Bandwidth | 6.8 GB/s | 0.05 GB/s | 136x reduction |
| Energy (μJ/query) | 4,200 | 180 | 23x |

---

5. Summary

NameSieve introduces a dedicated Filter Processing Unit inside the SSD controller that performs content-aware filtering through a two-stage hash-then-compare pipeline. By pushing name matching to the data source, we transform the bandwidth equation from O(dataset) to O(matches), achieving order-of-magnitude improvements in latency, throughput, and energy efficiency for name-value pair retrieval workloads.

---