Amadeus UPoW MatMul Specifications: Complete Technical Breakdown

Amadeus UPoW (Up-Proof-of-Work) uses a 16 × 16 matrix-multiplication kernel with K = 50,240, supporting three SIMD backends—scalar, AVX2, and AVX-512 VNNI—to compute proofs efficiently across different CPU capabilities. This article details the exact specifications, data layouts, and implementation paths found in the Amadeus node source code.

Matrix Dimensions and Data Types

The Amadeus UPoW MatMul operation multiplies two large rectangular matrices with fixed dimensions:

Matrix	Shape	Element Type	Memory Layout
A	16 × K	u8	Row-major (each row = K bytes)
B	K × 16	i8 (stored raw)	Row-major, transposed to 16 × K for computation
C	16 × 16	i32	Little-endian 4-byte words, consecutive

The constant K = 50,240 is defined in ex/native/rdb/src/upow.rs at line 5:

pub const K: usize = 50_240;

This yields matrix A as 16 × 50,240 bytes (803,840 bytes) and matrix B as 50,240 × 16 bytes (same total). The result matrix C occupies 1,024 bytes (C_BYTES = 1024), with the full solution including a 240-byte preamble totaling 1,264 bytes (SOL_SIZE = 1264) as defined at lines 7–9.

Solution Structure and Seed Expansion

The UPoW proof format follows a strict layout implemented in the compute function:

1. Preamble (240 bytes) — seed data fed into Blake3
2. Result matrix C (1,024 bytes) — the computed 16 × 16 i32 output

The seed expansion process derives both input matrices from a single Blake3 hash (lines 81–84):

// AB buffer contains concatenated A and B matrices
const AB_BYTES: usize = A_BYTES + B_BYTES; // 16*K + K*16 = 2*K*16

The first A_BYTES become matrix A (u8), the remainder become matrix B (i8).

Three Backend Implementations

Amadeus UPoW selects one of three MatMul backends at runtime based on CPU feature detection:

Scalar Backend (Baseline)

Detection: No AVX2 or AVX-512 features present.

Implementation: matmul_scalar at lines 67–79 — a triple-nested loop with explicit B-transpose preprocessing.

fn matmul_scalar(a: &[u8], bt: &[i8], out: &mut [u8]) {
    for i in 0..16 {
        let arow = &a[i * K..i * K + K];
        for j in 0..16 {
            let brow = &bt[j * K..j * K + K];
            let mut acc: i32 = 0;
            for k in 0..K {
                acc = acc.wrapping_add(arow[k] as i32 * brow[k] as i32);
            }
            store_c(out, i, j, acc);
        }
    }
}

The transpose_b function (lines 49–66) pre-converts B from K × 16 to 16 × K layout for cache-efficient access.

AVX2 Backend

Detection: is_x86_feature_detected!("avx2") returns true (lines 22–26).

Implementation: matmul_avx2_fused — processes 2 K-elements per _mm256_madd_epi16 instruction, keeping rows of C live in YMM registers.

The AVX2 path fuses the transpose into multiplication, eliminating a separate memory pass. The generic RT constant controls rows processed per loop (typically 8).

unsafe {
    matmul_avx2_fused::<8>(a, b_raw, &mut out);
}

AVX-512 VNNI Backend (Fastest)

Detection: All three features present: avx512f, avx512bw, avx512vnni (lines 22–24).

Implementation: matmul_avx512_fused — uses the VPDPBUSD instruction to perform 64 multiply-accumulate operations per instruction, processing 4 K-elements per loop iteration.

unsafe {
    matmul_avx512_fused(a, b_raw, &mut out);
}

This backend achieves approximately 2–4× speedup over AVX2 on supported CPUs according to source comments.

Helper Functions and Utilities

store_c (lines 44–47)

Writes a single i32 accumulator to the output buffer at position (i, j):

fn store_c(out: &mut [u8], i: usize, j: usize, val: i32) {
    let offset = (i * 16 + j) * 4;
    out[offset..offset + 4].copy_from_slice(&val.to_le_bytes());
}

transpose_b (lines 49–66)

Converts B from K × 16 column-major access pattern to 16 × K row-major, stored in scratch.bt: Vec<i8>.

Complete Usage Example

use amadeus_node::ex::native::rdb::upow::{
    matmul_scalar, matmul_avx2_fused, matmul_avx512_fused,
    transpose_b, Scratch, K, A_BYTES, C_BYTES
};

// Allocate workspace
let mut scratch = Scratch::new();
let a = &scratch.ab[0..A_BYTES];
let b_raw = &scratch.ab[A_BYTES..];
let mut out = vec![0u8; C_BYTES];

// Choose backend based on target CPU
#[cfg(target_arch = "x86_64")]
{
    if is_x86_feature_detected!("avx512vnni") {
        unsafe { matmul_avx512_fused(a, b_raw, &mut out); }
    } else if is_x86_feature_detected!("avx2") {
        unsafe { matmul_avx2_fused::<8>(a, b_raw, &mut out); }
    } else {
        transpose_b(b_raw, &mut scratch.bt);
        matmul_scalar(a, &scratch.bt, &mut out);
    }
}

Verification and Testing

The reference implementation matmul_reference in the test module ensures all backends produce bit-identical results. Run the test suite:

cargo test --manifest-path ex/native/rdb/Cargo.toml

The tests::backends_match_reference test validates correctness across scalar, AVX2, and AVX-512 VNNI paths.

Key Source Files

File	Purpose
ex/native/rdb/src/upow.rs	Core UPoW implementation: backend detection, compute API, and all three MatMul kernels
ex/native/rdb/src/upow.rs (test module)	Reference implementation and cross-backend verification tests

Summary

• Fixed dimensions: 16 × 50,240 × 16 multiplication with u8/i8 inputs and i32 output
• Three SIMD backends: Scalar (portable), AVX2 (2-wide), AVX-512 VNNI (4-wide with VPDPBUSD)
• Efficient memory layout: Fused transpose-multiplication for SIMD paths; explicit transpose for scalar
• Deterministic output: All backends verified against reference implementation
• Compact proof: 1,264-byte solution (240-byte seed + 1,024-byte result matrix)

Frequently Asked Questions

What is the value of K in Amadeus UPoW MatMul operations?

K = 50,240, a fixed constant defined at line 5 of ex/native/rdb/src/upow.rs. This dimension was chosen to balance computational workload against memory bandwidth, yielding approximately 16 million multiply-accumulate operations per proof.

Does Amadeus UPoW require AVX-512 to run?

No. The implementation falls back automatically to AVX2 or scalar backends based on runtime CPU feature detection. The scalar path requires only standard Rust with no SIMD intrinsics. AVX-512 VNNI provides the fastest path but is optional.

How does the AVX-512 VNNI backend achieve higher performance?

The matmul_avx512_fused function uses the VPDPBUSD instruction, which performs 8-bit dot product with accumulation into 32-bit results. Each instruction executes 64 multiply-accumulate operations, compared to 2 per AVX2 instruction. This 32× theoretical throughput increase, combined with 512-bit register width, delivers 2–4× real-world speedup over AVX2.

Where is the B matrix transposition performed?

For the scalar backend, transpose_b explicitly converts B to 16 × K layout before multiplication (lines 49–66). The AVX2 and AVX-512 backends fuse transposition into the multiplication loop, reading B in its original K × 16 layout while accessing A rows sequentially—eliminating a separate memory pass and improving cache efficiency.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}