From Algorithm to Hardware: Evaluation of a Strassen-type algorithm for 3 × 3 Matrix Multiplication on FPGA
(2026) EITM02 20261Department of Electrical and Information Technology
- Abstract
- Fast matrix multiplication algorithms reduce the number of multiplication operations at the cost of additional additions, intermediate values, and more complex data dependencies. Their practical hardware efficiency therefore depends on both arithmetic cost and the ability of the memory and control system to supply operands efficiently.
This thesis evaluates a rank-23 fast algorithm for 3 × 3 matrix multiplication against conventional tiled general matrix multiplication (GeMM) on a field-programmable gate array (FPGA). The workload is a 384 × 384 matrix multiplication over F2, partitioned into 128 × 128 tiles. Both algorithms are implemented on a common architecture targeting an AMD Kria KV260 platform, with tile multiplication performed... (More) - Fast matrix multiplication algorithms reduce the number of multiplication operations at the cost of additional additions, intermediate values, and more complex data dependencies. Their practical hardware efficiency therefore depends on both arithmetic cost and the ability of the memory and control system to supply operands efficiently.
This thesis evaluates a rank-23 fast algorithm for 3 × 3 matrix multiplication against conventional tiled general matrix multiplication (GeMM) on a field-programmable gate array (FPGA). The workload is a 384 × 384 matrix multiplication over F2, partitioned into 128 × 128 tiles. Both algorithms are implemented on a common architecture targeting an AMD Kria KV260 platform, with tile multiplication performed by a four-bit-chunk multiplier inspired by the Method of the Four Russians for Matrix Multiplication (M4RM).
The input-side scheduling problem is formulated as a variant of the Red-Blue Pebble Game and optimized using an A⋆/branch-and-bound search. Under that model the search establishes that at least eleven tile slots of input cache are required to attain both the minimum raw-tile load count and the minimum input-side addition count. Among arithmetically cost-optimal schedules, the hardware implementation selects the candidate with the lowest estimated cycle count. The algorithms are compared at matched multiplication-unit parallelism, denoted as
Active-P , to isolate the effects of arithmetic throughput and memory behavior.
Measurements on the implemented accelerator show that the fast algorithm is advantageous when multiplication remains the dominant cost. At Active-P = 4, it reduces accelerator cycles by 13.9%. This advantage decreases to 3.7% at Active-P = 8 and reverses at Active-P = 16, where the fast algorithm requires 2.5% more cycles than GeMM. As multiplication becomes faster, data-transfer overhead and operand assembly stage increasingly dominate, causing the reduction in multiplication count to lose its performance benefit. (Less) - Popular Abstract
- Matrix multiplication is a basic operation used in many areas of modern computing, including image processing, machine learning, signal processing, and scientific simulation. The ordinary way to multiply two 3 × 3 matrices uses 27 multiplications. In 1976, Julian Laderman showed an algorithm that reduced this number to 23. However, this algorithm also requires more additions, more temporary values, and a complicated execution order that has to be carefully arranged.
This thesis investigates whether that reduction can produce a real advantage on an FPGA, a reconfigurable chip that can be tailored to a specific computation. A single hardware design was built to support both the ordinary method and the 23-multiplication method, allowing them... (More) - Matrix multiplication is a basic operation used in many areas of modern computing, including image processing, machine learning, signal processing, and scientific simulation. The ordinary way to multiply two 3 × 3 matrices uses 27 multiplications. In 1976, Julian Laderman showed an algorithm that reduced this number to 23. However, this algorithm also requires more additions, more temporary values, and a complicated execution order that has to be carefully arranged.
This thesis investigates whether that reduction can produce a real advantage on an FPGA, a reconfigurable chip that can be tailored to a specific computation. A single hardware design was built to support both the ordinary method and the 23-multiplication method, allowing them to be compared under the same conditions.
A major part of the work concerns scheduling: deciding the order of the 23 steps and which values should remain in the limited fast memory on the chip. An optimized schedule was found that avoids unnecessary data reloads and intermediate recomputation. The two methods were then compared across several multiplication-unit speeds to see how the performance changes as the arithmetic itself becomes faster.
The results show a clear crossover. When multiplication is relatively slow, the 23-multiplication method is about 14% faster. As the multiplier becomes faster, this advantage shrinks and eventually disappears; at the highest tested speed, the fast algorithm becomes slightly slower than the ordinary method. The reason is that the bottleneck moves from multiplication to data supply and operand preparation.
The main conclusion is simple: reducing the number of arithmetic operations does not automatically make a hardware design faster. The benefit is realized only when memory, data movement, and control can keep the computation supplied efficiently. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/student-papers/record/9251230
- author
- Luo, Yuxuan LU and Momand, Mirvais
- supervisor
- organization
- course
- EITM02 20261
- year
- 2026
- type
- H2 - Master's Degree (Two Years)
- subject
- keywords
- Fast matrix multiplication, Rank-23 algorithm, FPGA accelerator, Execution scheduling, GF(2)
- report number
- LU/LTH-EIT 2026-1190
- language
- English
- id
- 9251230
- date added to LUP
- 2026-09-17 10:09:07
- date last changed
- 2026-09-17 10:09:07
@misc{9251230,
abstract = {{Fast matrix multiplication algorithms reduce the number of multiplication operations at the cost of additional additions, intermediate values, and more complex data dependencies. Their practical hardware efficiency therefore depends on both arithmetic cost and the ability of the memory and control system to supply operands efficiently.
This thesis evaluates a rank-23 fast algorithm for 3 × 3 matrix multiplication against conventional tiled general matrix multiplication (GeMM) on a field-programmable gate array (FPGA). The workload is a 384 × 384 matrix multiplication over F2, partitioned into 128 × 128 tiles. Both algorithms are implemented on a common architecture targeting an AMD Kria KV260 platform, with tile multiplication performed by a four-bit-chunk multiplier inspired by the Method of the Four Russians for Matrix Multiplication (M4RM).
The input-side scheduling problem is formulated as a variant of the Red-Blue Pebble Game and optimized using an A⋆/branch-and-bound search. Under that model the search establishes that at least eleven tile slots of input cache are required to attain both the minimum raw-tile load count and the minimum input-side addition count. Among arithmetically cost-optimal schedules, the hardware implementation selects the candidate with the lowest estimated cycle count. The algorithms are compared at matched multiplication-unit parallelism, denoted as
Active-P , to isolate the effects of arithmetic throughput and memory behavior.
Measurements on the implemented accelerator show that the fast algorithm is advantageous when multiplication remains the dominant cost. At Active-P = 4, it reduces accelerator cycles by 13.9%. This advantage decreases to 3.7% at Active-P = 8 and reverses at Active-P = 16, where the fast algorithm requires 2.5% more cycles than GeMM. As multiplication becomes faster, data-transfer overhead and operand assembly stage increasingly dominate, causing the reduction in multiplication count to lose its performance benefit.}},
author = {{Luo, Yuxuan and Momand, Mirvais}},
language = {{eng}},
note = {{Student Paper}},
title = {{From Algorithm to Hardware: Evaluation of a Strassen-type algorithm for 3 × 3 Matrix Multiplication on FPGA}},
year = {{2026}},
}