Weighted Associative Memory (WAM) is an experimental software prototype for testing a predictive memory architecture. It asks whether a dynamically weighted, trie-like graph over memory-access sequences can predict future accesses accurately enough to hide cache/DRAM latency.
This is a research simulator, not a hardware design and not a claim of a novel invention.
The native ChampSim evaluation is complete. The final authorized follow-up replaced the 256-entry direct-mapped WAM table with a 64-set × 4-way set-associative table, preserving 256 total entries, H16 alignment, the confidence threshold, the hash function, the prefetch policy, and the fixed 5M-instruction warmup / 10M-instruction simulation window.
The result was negative:
| Metric | DirectMappedWAM | SetAssociativeWAM |
|---|---|---|
| Logical state bytes | 8,448 | 8,512 |
| Context hit rate | 0.387% | 0.189% |
| Shadow H16 accuracy | 0.000% | 0.000% |
| Shadow H16 coverage | 0.000% | 0.000% |
| Geomean IPC speedup | 1.000× | 1.000× |
Across ten native traces, the chronological H16 oracle reached 32.616% accuracy with 37.526% coverage, but neither online WAM variant generated a prediction. Four-way associativity did not recover the lost state: unresolved all-ways conflict loss was 99.662%, compared with 99.466% direct-map alias loss. NativeSPP reached 1.120× geomean IPC speedup in the same frozen comparison.
The final classification is A — Aliasing hypothesis falsified and the research decision is:
RESEARCH_DECISION = STOP
No delta variant or further hardware work is justified by this evidence. The complete data-derived report, CSV artifacts, per-trace ChampSim outputs, and plots are in results/set_associative_wam/, with the main conclusion in report.md. The implementation is retained for reproducibility; this repository is archived and is no longer under active development.
Conventional cache logic primarily asks whether an address is already present. WAM adds a bounded sequence context:
recent access prefix -> likely next access(es)
ROOT
├── A
│ └── B [0.81]
│ ├── C [0.93]
│ └── X [0.07]
└── D
└── B [1.00]
The predictor stores fixed-size counters and normalized weights on outgoing edges. A lookup follows at most context_depth addresses and ranks only the matched node's small child set. There is no neural network, embedding, external service, or whole-trie scan.
trace -> workload/pipeline -> predictor training
-> bounded context lookup -> top-K predictions
|
v
L1 LRU cache <- prefetch <- L2 <- DRAM
|
v
cycle accounting + metrics
The package is split into small modules:
wam.trie: weighted prefix graph, frequency and exponential-moving-average updates, thresholded prediction, storage estimate.wam.predictor: weighted trie plus Markov-1 and next-line baselines.wam.cacheandwam.hierarchy: LRU caches and configurable L1/L2/DRAM cycle accounting.wam.simulator: demand accesses, prefetch cost, duplicate/useful/unused prefetch accounting, cache pollution, bandwidth, prediction accuracy, and speedup.wam.workloads: sequential, repeating, branching, context-sensitive, and random deterministic traces.wam.experiment: comparison table and context-depth/threshold sweeps.wam.visualization: four optional matplotlib plots.
Python 3.10+ is required.
python -m pip install -e '.[dev]'
python -m pytest
python -m wam.experiment
python -m wam.experiment --length 2000 --plot-dir artifacts/plots
python -m wam.benchmarkThe original MVP experiment has a deliberately simple hierarchy:
L1: 64 entries, 4 cycles
L2: 256 entries, 12 cycles
DRAM: unlimited, 100 cycles
The original MVP simulator charges 1 cycle to issue a prefetch and 8 bandwidth bytes per non-duplicate address by default. The research simulator additionally models DRAM completion latency, outstanding-request limits, late arrivals, and configurable L1/L2/L3 destinations.
The experiment runner compares:
None: LRU hierarchy with no prefetching.NextLine:X -> X + 1.Markov-1: the most frequent next address for the current address.WeightedTrie: a depth-2 weighted context trie with a 0.05 confidence threshold.
It reports total accesses, L1/L2 hit rates, average latency, top-1/top-K prediction accuracy, speedup, prefetch precision, and coverage. The simulator additionally records DRAM accesses, useful/unused/duplicate prefetches, incorrect predictions, bandwidth, prefetch-caused evictions, latency saved by useful prefetches, and the net benefit:
net latency benefit = latency saved by useful prefetches
- cost of unused prefetches
The predictive system can therefore lose: low-confidence predictions consume cycles and cache capacity, and may evict useful lines.
python -m wam.benchmark runs the serious comparative experiment. It replays identical traces against a no-prefetch L1/L2/L3/DRAM control, next-line prefetching, a confidence-based stride prefetcher, first-order Markov prediction, and weighted trie depths 1, 2, 3, 4, and 8.
The benchmark uses a chronological 70/30 split by default. Predictors are trained only on the first portion and frozen during evaluation. The same simulator also supports online learning (learning=True) and emits a learning curve. No trace shuffling is performed.
The research hierarchy defaults to 64-byte cache lines and configurable 4/12/40/150-cycle L1/L2/L3/DRAM parameters. Prefetches are outstanding requests rather than instantaneous cache inserts: they have a completion time, can arrive late, consume bounded outstanding-request slots, and can cause cache pollution. Predictor lookup/update cycles are included in effective cycles.
The command writes:
results/
├── summary.csv # mean/std across trials
├── detailed_results.csv # one row per workload/system/trial
├── sweep.csv # depth, threshold, EMA, top-K, destination sweeps
├── ablation.csv # depth/threshold/EMA/no-prefetch ablations
├── learning_curve.csv # online accuracy/latency over prefixes
├── break_even.csv # accuracy vs speedup at two DRAM latencies
├── config.json
├── report.md # data-derived verdict and limitations
└── plots/ # 11 matplotlib figures
Use a different trace length or a plain-text trace file:
python -m wam.benchmark --length 2000 --trials 10
python -m wam.benchmark --trace path/to/trace.txt
python -m wam.diagnostics --output results/diagnosticsTrace files contain one integer or hexadecimal byte address per line. Blank lines and # comments are accepted. wam.traces.iter_addresses is streaming, so large files need not be loaded unless an experiment explicitly requires a chronological split. Traces can be generated with Valgrind/Lackey, Intel Pin, DynamoRIO, or perf and converted to this one-address-per-line format; those tools are not test dependencies.
The generated report is deliberately allowed to conclude that WAM loses. In particular, sequential and constant-stride streams should favor conventional prefetchers, random streams should punish speculative state, and deeper contexts should pay storage and lookup costs unless the workload contains repeatable higher-order structure. The report identifies WAM wins/losses, the best depth and threshold, warm-up, storage, maximum speedup, geometric-mean speedup, break-even accuracy, and the next recommended experiment.
python -m wam.diagnostics preserves the primary benchmark and writes a separate higher-order diagnostic set. It verifies depth-2 and depth-4 discrimination with regression tests, instruments exact/fallback/unseen context matches, measures context support and reuse, sweeps repetition density and trace lengths through one million accesses, compares WAM against flat Markov-N tables, and evaluates pruning, support-based confidence, entropy gating, and empirical context-oracle accuracy. Its context_diagnostics.md is a diagnostic conclusion, not an optimized headline result.
python -m wam.horizon_analysis tests whether accurate higher-order predictions arrive early enough to overlap memory latency. It compares direct horizon WAM, recursive traversal, direct Markov-N, and perfect Oracle-H1 through Oracle-H32 configurations under the same hierarchy. It records lead time, slack, late/partial/fully hidden misses, compute gaps, DRAM latency, bandwidth limits, failure buckets, and long higher-order accuracy at 100K and 1M accesses. Results are isolated in results/horizon_analysis/ so earlier evidence remains reproducible.
python -m wam.hardware_feasibility evaluates whether the horizon benefit survives an explicit predictor cost model. It separates lookup latency from issue interval, supports serial and overlapped/pipelined lookup, queues and port pressure, deferred/batched updates, fixed hash tables, integer counters, context signatures, prediction-result caches, fallback/candidate-selection costs, and a normalized energy proxy. The default run prioritizes DirectWAM-H16 and repeats key sweeps at H8/H32 in the latency table.
The experiment writes a new results/hardware_feasibility/ directory containing latency, throughput, overlap, architecture, storage-budget, counter-width, hash-collision, update, batching, energy, tolerance, and microarchitecture CSVs, a feasibility matrix, plots, config.json, and a data-derived report.md. IdealWAM is a zero-cost direct-WAM upper bound; Oracle is reported separately and is not treated as implementable hardware. Hash-table replacement is approximated by deterministic bucket aliasing, and energy values are normalized comparative units rather than silicon estimates.
python3 -m wam.real_trace_evaluation --trace-dir traces --output results/real_trace_evaluation is the next comparative phase. It consumes only externally captured data-address traces and compares DirectWAM-H8/H16/H32, bounded hashed contexts, recursive WAM, Markov-N, VLDP-style delta history, SPP-style recursive paths, GMC-style multi-order deltas, stride, next-line, and a simple hybrid under chronological splits and equal 2–64 KB budgets. It records context entropy/reuse, direct-horizon oracle opportunity, phase stability, miss-only training, storage/latency costs, and the requested predictor result tables and plots.
The reproducible native workloads are in benchmarks/; build them with scripts/build_benchmarks.sh. scripts/check_trace_tools.sh reports whether Valgrind/Lackey, Intel Pin, DynamoRIO, or perf is installed, and scripts/convert_trace.py converts explicit external data-address records to one hexadecimal address per line. On this host no supported binary tracer was available, so scripts/capture_source_traces.sh provides the documented source-instrumented fallback: wrappers log actual allocated data addresses at benchmark load/store sites, with raw logs and per-trace metadata. These traces are labeled source_instrumented, not binary traces. The committed real-trace report records the bounded representative results and remaining binary/cross-seed limitations.
python3 -m wam.hybrid_analysis --trace-dir traces/source_instrumented/loads --output results/hybrid_analysis audits the current GMC-style proxy before comparing it with WAM. The study uses chronological phase windows, WindowOracle and StaticPerWorkloadOracle ceilings, confidence/recent-performance/entropy selectors, disagreement analysis, direct-H16 vs H1/recursive comparisons, selector overhead, and equal-total-budget WAM-sidecar splits. The current run covers all 37 captured workload/seed traces with a bounded 10K prefix and samples up to three early/middle/late windows per measured size; the exact cap and unmeasured window sizes are recorded in results/hybrid_analysis/config.json and report.md.
The important motivating trace is:
A, B, X, C, B, Y, A, B, X, C, B, Y, ...
B -> ? is ambiguous to a first-order predictor. A depth-2 trie can learn (A,B) -> X and (C,B) -> Y. The CLI's context-depth sweep writes accuracy_vs_context_depth.png and includes estimated nodes/edges/bytes so accuracy can be viewed alongside predictor growth.
Exact values depend on trace length, cache configuration, and random seeds. A representative run has this shape:
Workload Predictor L1 hit L2 hit Avg cyc Top-1 Speedup Prec. Cover.
-----------------------------------------------------------------------------------------
Sequential None ... ... ... ... 1.00x ... ...
Sequential NextLine ... ... ... ... >1.00x ... ...
Contextual Markov-1 ... ... ... ... modest ... ...
Contextual WeightedTrie ... ... ... ... higher ... ...
Random WeightedTrie ... ... ... ... may fall below 1.00x ...
The ellipses are intentional: the runner is the source of truth for the current configuration rather than a hard-coded benchmark claim.
This MVP models entries, not cache lines or bytes; assumes one outstanding operation at a time; does not model overlap, queues, coherence, virtual addresses, replacement policies beyond LRU, or real DRAM bandwidth. Prefetch cost is a configurable cycle charge rather than a detailed bus model. The predictor is trained on a prefix and evaluated on a later suffix in the experiment runner to avoid direct test-trace leakage.
Future work could use fixed-width saturating counters, quantized weights, bounded fan-out tables, compact child indices, parallel comparators, confidence decay, multi-step speculative traversal, and traces from real programs. Each should be evaluated against storage, lookup energy, bandwidth, pollution, and latency rather than accuracy alone.