Fast and Practical Strassen's Matrix Multiplication using FPGAs

2024/06/04 by Afzal Ahmad, Ahmad, Afzal, Linfeng Du +2 · 1 citation
Computer Science · Engineering · #Numerical Methods and Algorithms #VLSI and FPGA Design Techniques #Digital Filter Design and Implementation

paper · pdf · doi:10.48550/arxiv.2406.02088

Abstract

Matrix multiplication is a cornerstone operation in a wide array of scientific fields, including machine learning and computer graphics. The standard algorithm for matrix multiplication has a complexity of O(n³) for n× n matrices. Strassen's algorithm improves this to O(n^2.807), but its practicality is limited for small to medium matrix sizes due to the large number of additions it introduces. This paper presents a novel FPGA-based implementation of Strassen's algorithm that achieves superior speed over an optimized General Matrix Multiply (GeMM) implementation for matrices as small as n=256. Our design, tested extensively on two high-performance FPGA accelerators (Alveo U50 and U280) across various data types, matches or surpasses the performance of a highly optimized baseline across a range of matrix sizes.

Cited by

• Exact Causal Attention with 10% Fewer Operations

Related

• Generating Families of Practical Fast Matrix Multiplication Algorithms
• Strassen's Matrix Multiplication Algorithm Is Still Faster
• Accelerating 128-bit Floating-Point Matrix Multiplication on FPGAs
• Implementing Strassen's Algorithm with CUTLASS on NVIDIA Volta GPUs
• Implementing Strassen's Algorithm with BLIS