Parallel Computation: Fast Matrix Multiply & Distributed Stencils

CSE 260 (Parallel Computation), UC San Diego, Fall 2025

Three performance-engineering projects at three levels of parallelism: SIMD vectorization on a single ARM core, thousands of threads on an NVIDIA GPU, and hundreds of processes across supercomputer nodes with MPI.

23.1 GFLOP/sARM SVE DGEMM, beating OpenBLAS (19.1) at N=2047
3.30 TFLOP/sCUDA SGEMM on a T4, ~63× over the naive kernel
273×MPI speedup on 384 cores (SDSC Expanse)

1. Matrix Multiplication with ARM SVE

Single-core double-precision GEMM on AWS Graviton

We wrote a cache-blocked DGEMM in the style of BLIS. The matrices are split into large tiles that fit in the L2 and L3 caches (MC=256, KC=128, NC=256). Each tile is packed into contiguous memory so the kernel reads it in order. A macro-kernel then hands each pair of packed sub-panels to a micro-kernel written with ARM SVE intrinsics.

Our kernelOpenBLASNaive
Performance (GFLOP/s) vs. matrix size N. Our kernel is faster than OpenBLAS for nearly every N ≥ 64.

How each optimization added up

StageApprox. GFLOP/s
Naive triple loop~1
Packing (BLIS-style, row-major)~6.5
First SVE micro-kernel~9–12
SVE, 4 then 8 rows of C at once16 → 18
8×8 register block in two passes~22–23
Parameter tuning (final)up to 23.1

2. Matrix Multiplication in CUDA

Single-precision GEMM on an NVIDIA T4 GPU

Each 16×16 block of 256 threads computes one 64×64 tile of C. The block loads tiles of A and B into shared memory, and neighboring threads read neighboring addresses so global-memory loads coalesce. Each thread then keeps a 4×4 block of C in registers, which gives it 16 independent accumulators (instruction-level parallelism). The inner loops are fully unrolled.

Our kernelcuBLAS
Performance (GFLOP/s) vs. N. Both curves zig-zag: sizes that are multiples of the tile width (for example 1024 and 1280) peak, and N+1 dips because of partial tiles and warp divergence.

Thread block size comparison (GFLOP/s)

NNaive8×816×1632×1632×8
25623.61,2291,518881827
51231.71,5522,7592,4122,125
102452.51,4053,2742,4872,199
1025–1,0562,6132,3852,119
2047–1,3523,1092,9112,620
204852.51,3573,2982,9692,576

A 16×16 block (256 threads, 8 full warps) was best at every size. An 8×8 block has only 2 warps and too little shared-memory reuse. 32×16 has 512 threads, which raises register pressure and lowers occupancy.

3. Distributed 2D Wave Simulation with MPI

5-point stencil wave solver on SDSC Expanse

The solver advances the 2D wave equation with a 5-point stencil and absorbing boundary conditions. The grid is split across a 2D Cartesian grid of MPI processes (MPI_Cart_create), and no process gets more than one extra row or column of work than any other.

Measured speedupIdeal (linear)
Strong scaling relative to 1 process. Problem sizes: N=1000 up to 16 processes, N=2000 for 16–128, N=4000 for 128–384. Efficiency falls from about 96% on 4 cores to about 71% on 384.

Strong scaling at large core counts (N = 4000)

CoresGeometryMpts/sGFLOP/sSpeedupEfficiency
1288×163,25929.391×71%
1928×245,45249.1152×79%
2568×326,77160.9189×74%
3848×489,77788.0273×71%

Process geometry matters

With the same 256 processes, the shape of the process grid changed throughput by 30%. C++ stores the grid row by row, so north–south ghost rows are contiguous while east–west ghost columns are strided and slower to send. Layouts that keep the strided edge short won, even over the square layout that minimizes total communication.

Geometry (256 cores, N=4000)Sub-blockMpts/s
16×16 (square)250 × 2504,307
64×463 × 10004,939
8×32500 × 1255,466
32×8125 × 5005,603

We also ran the solver on a 27-core Raspberry Pi cluster. Tripling the core count from 9 to 27 gave a 2.6× speedup at N=2000, but only 2.0× at N=1000: the cluster's Gigabit Ethernet needs larger per-process workloads to hide its latency.