FLUD: A Scalable and Configurable Systolic Array Design for LU Decomposition on FPGAs

Lower-upper decomposition (LUD) is one of the most popular matrix factorization techniques in linear algebra and has been widely used in many scientific and engineering applications. While prior studies have investigated various strategies to accelerate block LUD on FPGAs for arbitrary input sizes, they often suffer from one or more of the following limitations: 1) excessive resource utilization due to separate PE (processing element) designs for different matrix blocks with diverse computation patterns; 2) excessive on-chip memory usage due to buffer-based designs; and 3) insufficient parallelism as only one-level parallelism (either row-level or iteration-level parallelism) was exploited due to complex dependencies. To address those limitations, we propose FLUD, a streamingbased systolic array design on the EPGA to accelerate block LUD, which shares the systolic array to accelerate different matrix blocks and exploits both column-level parallelism and iterationlevel parallelism. First, FLUD implements a configurable systolic array that is shared by different LUD blocks and scalable to arbitrary input sizes. To further optimize its hardware resource efficiency, FLUD groups a column of PEs together to replace their FIFO connections with lightweight registers and reduce multiple copies of local control logic inside each PE (for the purpose of resource sharing among different LUD blocks) into a global one. Moreover, FLUD devises a computation schedule to effectively share the highly-optimized systolic array design among the execution of different LUD blocks. Lastly, to enable fast design space exploration on a given FPGA platform, we develop an automation tool to automatically generate the optimized FLUD design in Vitis high-level synthesis (HLS), where users can configure the design size and data precision based on their needs. Experimental results demonstrate that FLUD achieves a peak throughput of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{4 2 7. 9 5}$</tex> GFLOPS for single-precision floatingpoint LUD, which is about <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$3 \times$</tex> faster than state-of-the-art FPGA design. Compared to the LAPACK library running on a 12 -core Xeon Silver 4214 CPU, FLUD achieves 4.71x higher throughput and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$10.25 x$</tex> better throughput/watt.