Benchmark Fast Hadamdard VMI vs CCE

[MirkoDeVita98]

fast Walsh–Hadamard: VMI (fulltp) vs CCE

See #230

fulltp is a VMI (ptodsl) fast Walsh–Hadamard kernel. On cannsim it holds
CCE cycle-parity at every batch (aligned and flexible); on the real A5 device it
beats CCE by +4…+13% across N=32…2048. The one trade-off is batch granularity:
VMI needs the batch to tile evenly into its pipeline, so it is coarser-grained than
CCE — but still flexible (any chunk count).

The VMI design (in simple terms)

• VMI vs CCE. CCE is C++ that bisheng auto-schedules. VMI is raw .pto where we
  write the data movement, compute, and synchronization by hand, then ptoas
  lowers it. Hand-written sync buys control (and here, bandwidth) but must be laid out
  statically.
• What the kernel does. It transforms each row of a (batch, N) fp16 matrix in
  place (y = x @ H). The batch is split into G contiguous row-bands (one per
  core, G = grid). Each band is streamed through a 4-buffer / 32 KB pipeline: the
  band's rows are cut into fixed 32 KB chunks (CR = 16384/N rows each), processed
  in groups of 4 (quads), with a small tail for the leftover 1–3 chunks.
• Why it beats CCE. Each core streams one contiguous range of HBM. That
  sustains higher bandwidth than CCE's grid-stride access (where each core jumps
  around the batch), so on the memory-bound device VMI runs faster.

The batch-size constraint

The batch (number of rows) is cut into G equal bands, and each band into whole
32 KB chunks. So the batch must be a multiple of G · CR (CR = 16384/N):

kernel	batch must be a multiple of	granularity
fulltp	G · CR	any chunk count ≥ 1 (tail handles the remainder) — 4× finer
CCE	CR	any chunk count, no G factor (grid-stride, bisheng-pipelined)

So fulltp is tied to N and G: the quantum G·CR = G·(16384/N) shrinks as N
grows (grid=64: N=32 → multiples of 32768; N=256 → 4096; N=2048 → 512). Within that
quantum any batch works — aligned (chunks a multiple of 4, no tail) or flexible
(remainder handled by the tail).

Why CCE is finer. Its runtime grid-stride loop is auto-pipelined by bisheng, so it
only needs one-chunk alignment (CR) and no G factor. VMI's manual pipeline must
tile statically, so it pays the G factor — the price of the contiguous-DMA speedup.
The tail is what lets VMI avoid full's stricter 4-chunk rule at (near) zero cost.

Results

Simulation — cannsim cycles (grid=4, N=256; lower = faster)

nchunk = chunks per core; rem = nchunk % 4 (rem>0 = flexible, uses the tail).

batch	nchunk	rem	fulltp	cce	fulltp/cce	fullt (naive tail)
1024	4	0	6399	6465	0.99	6399
1280	5	1	8058	8030	1.00	9742 (1.21)
2048	8	0	12823	12863	1.00	12823
2304	9	1	14429	14474	1.00	16071 (1.11)
4096	16	0	25671	25751	1.00	25671
4352	17	1	27277	27490	0.99	28955 (1.05)
8192	32	0	51440	51632	1.00	51488
8448	33	1	52973	53138	1.00	54631 (1.03)

fulltp = CCE within ±1% everywhere. (fullt, a naive serial tail, is +3…+21% on the
flexible rows — the overlapped tail in fulltp erases that.)

On device — A5 (950DT) bandwidth GB/s (grid=64; higher = faster)

Aligned = nchunk 64 (rem 0); flexible = nchunk 65 (rem 1, a batch full rejects).
Copy floor (torch D2D = HBM ceiling) ≈ 3050 GB/s across N.

N	fulltp aligned	cce aligned	aligned	fulltp flexible	cce flexible	flexible
32	3170	2931	+8.2%	3174	2992	+6.1%
64	3153	2946	+7.0%	3218	2943	+9.3%
128	3194	2945	+8.5%	3166	2986	+6.0%
256	3201	2892	+10.7%	3157	2896	+9.0%
512	3020	2918	+3.5%	3041	2945	+3.3%
1024	2924	2827	+3.4%	2917	2818	+3.5%
2048	2740	2703	+1.3%	2706	2736	−1.1%

fulltp beats CCE at every N for both aligned and flexible batches (only exception:
N=2048 flexible, ≈parity). At small N fulltp even exceeds the copy floor (≈3050) —
contiguous DMA amortizes better than a plain copy — while CCE sits below it. The
margin shrinks toward N=2048, where all kernels converge on the HBM ceiling.

Bottom line

• Speed: cannsim cycle-parity with CCE; on device faster than CCE (+4…+13%) —
  from contiguous per-core DMA.
• Flexibility: batch must be a multiple of G·CR (tied to N and grid), any chunk
  count ≥ 1. Coarser than CCE's CR, but 4× finer than the old full, and it wins on
  bandwidth — the deliberate VMI trade-off.