Exjobbspresentation: From Algorithm to Hardware: Evaluation of Strassen-type 3x3 Fast Matrix Multiplication on FPGA

Fast matrix multiplication algorithms reduce the number of multiplication operations at the cost of additional additions, intermediate values, and more complex data dependencies. Whether this trade is profitable in hardware depends not only on arithmetic counts, but on how the resulting execution schedule interacts withfinite on-chip memory and with the throughput of the multiplication unit.

This thesis evaluates a rank-23 fast algorithm for 3 × 3 matrix multiplication against conventional tiled GEMM on FPGA. The workload is 384 × 384 matrix multiplication over F2, partitioned into a 3 × 3 grid of 128 × 128 tiles, where additions are bitwise XOR operations and tile products are computed by the Method of the Four Russians. Both algorithms are realized on a common hardware architecture and evaluated on a Zynq UltraScale+ MPSoC. The work is organized around three contributions. First, the input-side scheduling problem is formulated as a variant of the Red–Blue Pebble Game and solved exactly by an A⋆/branch-and-bound search, yielding execution schedules that are provably cost-optimal for the selected factorization at each on-chip cache capacity. Second, the two algorithms are compared at matched multiplication-unit parallelism, denoted Active-P, which isolates the effect of arithmetic throughput from that of the workload and the memory configuration. Third, the resulting performance crossover is characterized and attributed to specific mechanisms.

The reduction from 27 to 23 tile products translates almost fully into end-toend latency at low parallelism, giving a 14.2% reduction at Active-P = 4. The advantage erodes as the multiplication unit becomes faster, falling to 3.7% at Active-P = 8, and reverses beyond it, with the fast algorithm running 5.0% slower at Active-P = 16. Once multiplication is no longer the limiting stage, the fixed external data-transfer volume and the irregular operand-construction dependencies of the fast algorithm dominate the execution time, and its lower product count ceases to be an advantage.

Examinator: Thomas Johansson

Handledare: Paul Stankovski Wagner