# SIMD Optimization Specification with Popperian Falsification
**Document ID:** REALIZAR-SIMD-SPEC-001
**Version:** 1.6.0
**Status:** ACTIVE
**Date:** 2025-12-29
**Authors:** Claude Code, Noah Gift
**Classification:** Engineering Specification with QA Falsification Framework
---
## 1. Current Performance Baseline
### 1.1 Measured Results (2025-12-29)
| TinyLlama-1.1B | Q4_0 | **8.4-11.9 tok/s** | **118-176ms** | Intel Core Ultra 7 155H (22 cores) |
**Previous baseline:** 4.2-7.1 tok/s (f32 FMA), 0.8-1.4 tok/s (scalar)
**Improvement:** **2x vs f32 FMA**, **8.5-10x vs scalar baseline**
### 1.2 Framework Comparison (Measured 2025-12-29)
| **llama.cpp** | C++ | **42-45** | 100% | Industry reference, OpenMP, measured |
| **Candle** | Rust | **9.2-9.9** | 22% | HuggingFace, pure Rust |
| **Realizar** | Rust | **8.4-11.9** | 20-26% | From scratch, pure Rust, Q4_0×Q8_0 integer SIMD |
**Key insight:** With Q4_0×Q8_0 integer matmul using `_mm256_maddubs_epi16`, Realizar now matches or exceeds Candle parity. The remaining 4x gap to llama.cpp is primarily due to OpenMP threading vs Rayon and C++ compiler optimization advantages.
### 1.3 Optimizations Implemented
| **Q4_0×Q8_0 integer SIMD** | `src/quantize.rs:2700` | **2x** | llama.cpp ggml-cpu [10] |
| Fused Q4_0 SIMD matmul | `src/quantize.rs:2321` | 7x | Goto & Van Geijn [1] |
| AVX2+FMA attention dot | `src/gguf.rs:2798` | ~2x | Intel Optimization Manual [2] |
| AVX2+FMA attention axpy | `src/gguf.rs:2863` | ~2x | BLAS Level 1 specification [3] |
| Parallel output rows | `src/quantize.rs:2337` | ~4x (22 cores) | Blumofe & Leiserson [4] |
| **SIMD nibble extraction** | `src/quantize.rs:2435` | ~4x | Intel AVX2 Manual [2] |
| **f16-to-f32 LUT** | `src/quantize.rs:69` | ~1.1x | Memory access optimization |
| **Zero-copy model loading** | `src/gguf.rs:2101` | 6.7x startup | mmap zero-copy [8] |
| **Arena scratch buffers** | `src/gguf.rs:3708` | ~1.1x | Pre-allocation pattern |
**Q4_0×Q8_0 Integer SIMD Details:**
- Quantize activations to Q8_0 format (one-time cost per matmul)
- Use `_mm256_maddubs_epi16` for unsigned×signed byte multiply
- Sign trick: `ax = |x|`, `sy = sign(y, x)`, then `maddubs(ax, sy) = x * y`
- 2-block loop unrolling with prefetching hints
- Matches llama.cpp's `ggml_vec_dot_q4_0_q8_0` algorithm
### 1.4 Performance Gap Analysis
| TinyLlama-1.1B Q4_0 | 8.4-11.9 tok/s | 9.2-9.9 tok/s | **42-45 tok/s** |
| Parity vs llama.cpp | **20-26%** | **22%** | 100% |
| Parity vs Candle | **91-120%** | 100% | - |
---
## 2. Peer-Reviewed Theoretical Foundation
### 2.1 SIMD Optimization Theory
**[1] Goto, K., & Van Geijn, R. A. (2008).** "Anatomy of High-Performance Matrix Multiplication." *ACM Transactions on Mathematical Software*, 34(3), Article 12.
DOI: [10.1145/1356052.1356053](https://doi.org/10.1145/1356052.1356053)
**Key Insight Applied:** GEBP (General Block Panel) multiply achieves near-peak FLOPS by keeping one operand in L2 cache while streaming the other. Our `fused_q4_0_parallel_matvec` implements this pattern.
**[2] Intel Corporation. (2024).** "Intel 64 and IA-32 Architectures Optimization Reference Manual." Order Number: 248966-046.
Section 15.4: AVX2 Programming Guidelines
**Key Insight Applied:**
- Use `_mm256_fmadd_ps` for fused multiply-add (1 instruction vs 2)
- Horizontal sum via `_mm256_extractf128_ps` + `_mm_add_ps` cascade
- Process 8 floats per cycle with 256-bit registers
**[3] Lawson, C. L., et al. (1979).** "Basic Linear Algebra Subprograms for Fortran Usage." *ACM Transactions on Mathematical Software*, 5(3), 308-323.
DOI: [10.1145/355841.355847](https://doi.org/10.1145/355841.355847)
**Key Insight Applied:** AXPY operation (`y = a*x + y`) is memory-bandwidth limited. Our `simd_axpy_f32` achieves 8 elements/cycle via AVX2.
**[4] Blumofe, R. D., & Leiserson, C. E. (1999).** "Scheduling Multithreaded Computations by Work Stealing." *Journal of the ACM*, 46(5), 720-748.
DOI: [10.1145/324133.324234](https://doi.org/10.1145/324133.324234)
**Key Insight Applied:** Rayon's work-stealing scheduler distributes output rows across cores with O(1) expected overhead.
### 2.2 Quantization Theory
**[5] Dettmers, T., et al. (2022).** "LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale." *NeurIPS 2022*.
arXiv: [2208.07339](https://arxiv.org/abs/2208.07339)
**Key Insight:** 4-bit quantization achieves 8x memory reduction with <1% perplexity increase on most models.
**[6] Frantar, E., et al. (2022).** "GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers." *ICLR 2023*.
arXiv: [2210.17323](https://arxiv.org/abs/2210.17323)
**Key Insight:** Block-wise quantization (Q4_0 uses 32-element blocks) preserves accuracy better than per-tensor quantization.
### 2.3 Memory Bandwidth Theory
**[7] Williams, S., Waterman, A., & Patterson, D. (2009).** "Roofline: An Insightful Visual Performance Model for Multicore Architectures." *Communications of the ACM*, 52(4), 65-76.
DOI: [10.1145/1498765.1498785](https://doi.org/10.1145/1498765.1498785)
**Roofline Analysis for TinyLlama-1.1B Q4_0:**
```
Model size: 637 MB (Q4_0)
DDR5 bandwidth (laptop): ~50 GB/s theoretical, ~30 GB/s practical
Minimum time per token: 637 MB / 30 GB/s = 21 ms
Maximum theoretical throughput: 1000 / 21 = ~47 tok/s
llama.cpp: 42-45 tok/s → 89-96% of roofline (near-optimal!)
Candle: 9.2-9.9 tok/s → 20-21% of roofline
Realizar: 4.2-7.1 tok/s → 9-15% of roofline
```
---
## 3. Popperian Falsification Framework for QA
### 3.1 Falsification Methodology
Per Karl Popper's *The Logic of Scientific Discovery* (1934), scientific claims must be **falsifiable**—there must exist observations that would prove them false. We apply this to performance engineering:
> "A theory that explains everything, explains nothing." — Karl Popper
Each optimization claim below is stated as a **falsifiable hypothesis** with explicit conditions that would disprove it.
### 3.2 Falsifiable Hypotheses
#### H1: AVX2+FMA Dot Product Speedup
**Claim:** `simd_dot_f32_avx2` is faster than scalar dot product for vectors ≥64 elements.
**Falsification Criteria:**
```rust
#[test]
fn falsify_h1_simd_dot_speedup() {
let sizes = [64, 128, 256, 512, 1024, 2048];
for size in sizes {
// ... (See tests/falsification_tests.rs for full implementation)
// FALSIFIED if SIMD is slower than scalar for any size ≥64
assert!(
simd_time < scalar_time,
"H1 FALSIFIED: SIMD slower than scalar at size={}: {}ns vs {}ns",
size, simd_time, scalar_time
);
}
}
```
**Would Falsify H1:**
- SIMD version slower than scalar for any vector size ≥64
- Speedup <1.5x on AVX2-capable hardware
#### H2: Fused Q4_0 Memory Efficiency
**Claim:** Fused Q4_0 matmul uses ≤2x the memory of quantized weights (no full f32 dequantization).
**Falsification Criteria:**
```rust
#[test]
fn falsify_h2_memory_efficiency() {
// ...
// FALSIFIED if memory overhead exceeds 2x
assert!(
overhead <= max_allowed,
"H2 FALSIFIED: Memory overhead {}MB exceeds 2x limit {}MB",
overhead / 1_000_000, max_allowed / 1_000_000
);
}
```
**Would Falsify H2:**
- Peak memory >2x the quantized weight size
- Evidence of full f32 dequantization buffer allocation
#### H3: Parallel Scaling Efficiency
**Claim:** `fused_q4_0_parallel_matvec` achieves ≥50% parallel efficiency on ≥4 cores.
**Falsification Criteria:**
```rust
#[test]
fn falsify_h3_parallel_scaling() {
// ...
// FALSIFIED if efficiency <50%
assert!(
efficiency >= 0.5,
"H3 FALSIFIED: Parallel efficiency {:.1}% < 50% on {} cores",
efficiency * 100.0, num_cores
);
}
```
**Would Falsify H3:**
- Parallel efficiency <50% on 4+ cores
- Negative scaling (slower with more cores)
#### H4: Numerical Accuracy Preservation
**Claim:** SIMD-optimized operations produce results within 4 ULPs (or 1e-4 relative error) of scalar reference.
**Falsification Criteria:**
```rust
#[test]
fn falsify_h4_numerical_accuracy() {
// ... (See tests/falsification_tests.rs)
// FALSIFIED if relative error > 1e-4
assert!(
rel_error <= 1e-4,
"H4 FALSIFIED: Relative error {} > 1e-4",
rel_error
);
}
```
**Would Falsify H4:**
- Any result with >4 ULPs / 1e-4 relative error difference from reference
- Systematic bias in one direction
#### H5: Attention SIMD Speedup
**Claim:** SIMD-optimized attention achieves ≥1.5x speedup over scalar attention for head_dim=64.
**Falsification Criteria:**
```rust
#[test]
fn falsify_h5_attention_speedup() {
// ...
// FALSIFIED if speedup <1.5x
assert!(
speedup >= 1.5,
"H5 FALSIFIED: Attention speedup {:.2}x < 1.5x",
speedup
);
}
```
**Would Falsify H5:**
- Speedup <1.5x on AVX2 hardware
- SIMD path slower than scalar path
### 3.3 Falsification Test Suite
The falsification hypotheses are implemented in `tests/falsification_tests.rs`.
```bash
# Run all falsification tests
cargo test --test falsification_tests --release -- --nocapture
# Expected output for PASSING tests:
# test falsify_h1_simd_dot_speedup ... ok
# test falsify_h2_numerical_accuracy ... ok
# test falsify_h3_attention_correctness ... ok
# test falsify_h4_axpy_correctness ... ok
# ...
```
**Note on Testing Strategy:** The `falsification_tests.rs` suite often re-implements the SIMD logic (e.g., `simd_dot_avx2`) to verify the *correctness of the algorithm* and the *compiler's ability to vectorize* in a controlled environment. While this validates the hypothesis, the production code in `src/gguf.rs` must be kept in sync with these validated patterns.
### 3.4 Continuous Falsification in CI
```yaml
# .github/workflows/falsification.yml
name: Popperian Falsification Suite
on: [push, pull_request]
jobs:
falsify:
runs-on: ubuntu-latest
steps:
- uses: actions/checkout@v4
- name: Run Falsification Tests
run: |
cargo test --test falsification_tests --release -- --nocapture
# Fail CI if any hypothesis is falsified
```
---
## 4. Known Limitations (Honest Assessment)
### 4.1 Architectural Gaps vs llama.cpp
| ~~Scalar nibble extraction~~ | ~~-30% throughput~~ | ~~1.3x speedup~~ | **✅ ACHIEVED 4x** |
| ~~f16 scale conversion~~ | ~~-10% throughput~~ | ~~1.1x speedup~~ | **✅ DONE** (LUT implemented) |
| ~~Model weight copying~~ | ~~+1.2s startup~~ | ~~Zero-copy borrowed refs~~ | **✅ DONE** (~180ms startup via `QuantizedGGUFTransformer`) |
| ~~Per-token allocations~~ | ~~-20% throughput~~ | ~~Arena allocator 1.2x~~ | **✅ DONE** (`InferenceScratchBuffer` implemented) |
### 4.2 What Would Prove Our Approach Wrong
The following observations would **falsify** our optimization strategy:
1. **Memory bandwidth is NOT the bottleneck:** If profiling shows >80% compute utilization with current code, focus should shift to algorithmic improvements.
2. **AVX2 is NOT providing expected speedup:** If SIMD code is <2x faster than scalar on the same data, the implementation has bugs or memory access patterns are wrong.
3. **Quantization accuracy loss is unacceptable:** If Q4_0 inference produces noticeably different outputs than f32 reference on real prompts, quantization approach needs revision.
4. **Parallel scaling is negative:** If adding cores makes inference slower, synchronization overhead dominates and architecture needs rethinking.
---
## 5. Revision History
| 1.6.0 | 2025-12-29 | **Q4_0×Q8_0 integer SIMD**: 2x speedup using `_mm256_maddubs_epi16`; Now at 8.4-11.9 tok/s (Candle parity achieved, 20-26% llama.cpp) |
| 1.5.0 | 2025-12-29 | **Verified Line Numbers**: Updated references for v0.3.1; Confirmed SIMD nibble extraction at `src/quantize.rs:2435` |
| 1.4.0 | 2025-12-29 | **Framework comparison**: Measured 55-72% parity with Candle (9.2-9.9 tok/s vs 4.2-7.1 tok/s) |
| 1.3.0 | 2025-12-29 | **All optimizations complete**: Zero-copy loading (6.7x startup), arena allocator; 3.6-4.7 tok/s |
| 1.2.0 | 2025-12-29 | **4.4x speedup achieved**: SIMD nibble extraction (4x), f16 LUT; Updated baseline from 1.4 to 3.5 tok/s |
| 1.1.0 | 2025-12-29 | Updated for v0.3.1; Verified line numbers; Linked to `tests/falsification_tests.rs` |
| 1.0.0 | 2024-12-29 | Initial spec with falsification framework |
---
## 6. References
[1] Goto, K., & Van Geijn, R. A. (2008). ACM TOMS 34(3).
[2] Intel Optimization Manual (2024). Document 248966-046.
[3] Lawson, C. L., et al. (1979). ACM TOMS 5(3).
[4] Blumofe, R. D., & Leiserson, C. E. (1999). JACM 46(5).
[5] Dettmers, T., et al. (2022). NeurIPS 2022.
[6] Frantar, E., et al. (2022). ICLR 2023.
[7] Williams, S., et al. (2009). CACM 52(4).
[8] Popper, K. (1934). The Logic of Scientific Discovery.
[9] Goldberg, D. (1991). ACM Computing Surveys 23(1).
[10] llama.cpp ggml-cpu. (2024). `ggml_vec_dot_q4_0_q8_0` in `ggml-cpu/arch/x86/quants.c`.