CAMAL

I wanted to take a shot at learning aspects of machine learning whilst utilizing my knowledge of compilers in whatever way I could. This is quite a primitive simulator, not utilizing many of the mainline optimizations such as multi-core designs, sparsity, simulated memory, energy consumption analysis, etc.. These capabilities can be found in a project called SCALE-sim which provided me with most of the guidance and inspiration for this project. In the future I may attempt to emulate some of those features, particularly sparsity, as well as retrieve some architecture specific results. The current iteration is architecture agnostic and utilizes a simple analytical model (IMITFU) for measuring speed and utilization compared against a scalar CPU's capabilities of computing 1 MAC per cycle. meaning speedup here is measured simply by dividing the product of the dimensions over the total number of cycles. Regardless, it was a fun, short learning project and I will likely do more of these in the future. Beyond this point I will give a rundown of the results I got given varying input data.

What this is

CAMAL is a combo of a cycle-accurate simulator of a systolic-array matrix accelerator (word salad), and a compiler that lowers a GEMM onto it. It measures what the accelerator buys you, how much the scheduling work adds on top, and where the cycles go when the array sits idle. Every number here comes from the simulator's own counter. the harness is bench.cpp, and running ./bench.sh regenerates the CSV and charts

This is a v1. The only optimization it applies is double-buffering (naive vs pipelined), there isnt a cache/weight reuse system, theres only one DMA engine, a fixed k-tile depth, no tiling search, no dataflow selection, etc.. so the results I received are somewhat of a floor to be improved upon.

the machine

An R×C grid of MAC cells, tiles of the two operands(weights and activations) are streamed in from a scratchpad mem space, each cell holds an accumulator and adds one val per cycle. A single DMA engine moves data between main mem and the spad. Functional execution and timing are computed separately (but values are always same), and the cycle count is derived from a simple cost model plus a two-queue (DMA / compute) scheduler.

The compiler

The hardware will only ever run one R×C×KT tile, so a 32×32×64 GEMM wouldnt fit, so lower() was made to turn arbitrary GEMMs (M, N, K) into a legal inst stream for the array by tiling the loop nest(imporved cache locality), generating 2D-DMA addresses and strides, handling partial edge tiles, and accumulating partial sums. It also has a pipelined mode that assigns the next k-tile to a different scratch bank (ping-pong by parity) so its load overlaps the current matmul, meaning same instructions - same data(simd), but differing bank choices which lets the hardware run a load and a compute at the same time, giving us 1.57x.

Method

• Scalar-CPU as baseline is analytic instead of using numpy, so a scalar machine doing the same GEMM at one MAC per cycle costs M*N*K cycles, so speedup_vs_cpu = (M*N*K) / total_cycles. On an 8×8 array the ceiling is R*C = 64 MACs/cycle, so 64× is the highest speedup achievable.

• Utilization degrades utilization = useful_MACs / (R*C*total_cycles):

  utilization = busy_frac × eff_busy

  busy_frac = fraction of time array runs at all (the rest is waiting on dma)

  eff_busy = how efficient it is while running, where the systolic fill/drain ramp is the only loss

  for Kt=8 on a 8×8 array a matmul does 8 useful cycles but takes 8 + 8 + 8 - 2 = 22, so eff_busy = 8/22 = 0.364

Results

Accel compared to CPU

shape (M×N×K)	total cycles	busy	util	speedup vs CPU
8×8×8	76	29.0%	10.5%	6.7×
8×8×64	272	64.7%	23.5%	15.1×
16×16×64	1088	64.7%	23.5%	15.1×
32×32×64	4352	64.7%	23.5%	15.1×
32×32×128	7936	71.0%	25.8%	16.5×

util vs array size

Same GEMM (32×32×64), array swept 4×4 -> 32×32. Utilization falls as array grows because eff_busy collapses as fill/drain ramp (R+C-2) grows while K stays fixed at 64(word salad again)

array	total cycles	busy_frac	eff_busy	utilization	speedup vs CPU
4×4	20352	35.2%	57.1%	20.1%	3.2×
8×8	6816	41.3%	36.4%	15.0%	9.6×
16×16	2664	45.7%	21.1%	9.6%	24.6×
32×32	1242	45.1%	11.4%	5.2%	52.8×

Bigger arrays finish far faster (52.8x > 3.2x) but each cell is idle more of its ramp. implying thata large array needs a large K to stay moving

scheduling

Double buffering ping pongs the A/B scratch banks by k-tile parity, so the load of the next tile overlaps the matmul of the current one.

shape	sched	total	busy_frac	eff_busy	util	speedup
8×8×64	naive	426	41.3%	36.4%	15.0%	—
8×8×64	pipelined	272	64.7%	36.4%	23.5%	1.57×
8×8×128	naive	826	42.6%	36.4%	15.5%	—
8×8×128	pipelined	496	71.0%	36.4%	25.8%	1.67×

Scheduling recovers some idle time (busy 41% -> 65%) but doesnt help increase the 36.4% fill/drain ceiling, so the improvemnet is ~1.57x and grows with K

Limitations (and what each one costs)

This is a v1(and may stay this way) but here are current issues to be improved

• Fixed KT
• Single DMA engine => the array waits on one serial load/store queue
• No weight reuse in lowering => why OS and WS tie
• Util counts teh full array => partial tiles inflate it