Exploring Field-Programmable Gate Arrays and High-Level Synthesis to perform numerical linear algebra operations for High Performance Computing.

Abstract

Since the end of Dennard scaling, power consumption has become a primary constraint in computing hardware design because it no longer scales proportionally with transistor size. The push for increased performance has led manufacturers to develop multi-core devices, revolutionizing the field over the past few decades. Recently, the High Performance Computing field has focused on energy-efficient heterogeneous platforms, with Field-Programmable Gate Arrays (FPGAs) gaining attention due to their superior energy efficiency. Traditionally, FPGAs were excluded from mainstream software development due to the complex design process, but this is changing with the introduction of High-Level Synthesis (HLS) tools that generate hardware descriptions from standard programming languages like C++. Numerical Linear Algebra (NLA) traverses several disciplines of science and engineering and is crucial in scientific computing. Solving problems in these areas often involves basic NLA operations, which are typically the most computationally expensive steps. This thesis focuses on developing and evaluating NLA kernels using HLS tools on modern FPGA-based platforms. To support this, we set up a laboratory for measuring the performance and energy consumption of heterogeneous platforms. This step involves the acquisition and installation of FPGA-based acceleration platforms, along with the necessary development tools and infrastructure. The thesis evaluates the performance of FPGAs for both dense and sparse NLA operations using floating-point arithmetic, comparing the results against multi-core CPUs. The study begins with a review of the state-of-the-art in HLS implementations on FPGA. It then explores developments in two of the most prominent dense linear algebra kernels: matrix-vector multiplication (GEMV) and matrix-matrix multiplication (GEMM). Additionally, the thesis focuses on one of the key kernels in sparse linear algebra, sparse matrix-vector multiplication (SpMV). The findings indicate that while CPUs often outperform FPGAs in dense operations, FPGAs offer competitive energy efficiency. For sparse operations, FPGAs not only deliver competitive performance but also consistently demonstrate superior energy efficiency. A key aspect of maximizing kernel efficiency is exploring analytical tools to understand performance and guide the optimization process. The roofline model (RLM) is a well-known graphical tool that facilitates the analysis of computational performance and identifies primary bottlenecks. We propose a novel extension of the RLM for FPGAs to assist in the optimization of runtime and energy consumption for NLA kernels based on sparse blocked storage formats. We apply this extended model to our SpMV kernel with a block-sparse storage format. The final effort in this thesis focuses on the analysis and extension of AMD’s Vitis library for the SpMV operation, recognized as state-of-the-art in the field. Several optimizations and matrix preprocessing techniques were explored, leading to significant performance gains. Among these extensions, techniques were introduced that combine reducing block sizes (to minimize padding) with the concurrent processing of multiple blocks (to compensate for the reduced data processed per block). For single precision, the optimizations achieved an average speedup of 1.5× and a maximum of 3.7×. Furthermore, a custom SpMV kernel optimized for band matrices was developed, delivering substantial performance improvements over the Vitis kernel for these kind of matrices.

Desde el fin del escalamiento de Dennard, el consumo de potencia se ha convertido en una de las principales limitaciones en el diseño de hardware de cómputo, ya que no escala proporcionalmente con la reducción del tamaño del transistor. La búsqueda por mejorar el rendimiento de los procesadores ha llevado a los fabricantes a desarrollar dispositivos multinúcleo, revolucionando así el campo del hardware en las últimas décadas. Recientemente, la computación de alto rendimiento (HPC, por su sigla en inglés) se ha enfocado en el uso de plataformas heterogéneas, lo que ha causado que las FPGAs (Field-Programmable Gate Arrays) ganen atención debido a su superior eficiencia energética. Tradicionalmente, las FPGAs han permanecido excluidas del desarrollo de software convencional debido al complejo proceso de diseño, pero esto está cambiando con la introducción de herramientas de Síntesis de Alto Nivel (HLS, por su sigla en inglés) que permiten generar descripciones de hardware a partir de lenguajes de programación estándar como C++. El Álgebra Lineal Numérica (NLA, por su sigla en inglés) atraviesa varias disciplinas de la ciencia y la ingeniería y es crucial en la computación científica. Resolver problemas en estas áreas a menudo implica operaciones básicas de NLA, que suelen ser las etapas más costosas computacionalmente. Esta tesis se centra en desarrollar y evaluar núcleos de NLA utilizando herramientas HLS en plataformas de hardware modernas basadas en FPGAs. Para lograr esto, hemos desplegado un laboratorio para medir el rendimiento y el consumo de energía de plataformas heterogéneas. Este paso implica la adquisición e instalación de plataformas de aceleración basadas en FPGAs, junto con las herramientas de desarrollo e infraestructura necesarias. El estudio realizado evalúa el rendimiento de las FPGAs para operaciones de NLA densa y dispersa, utilizando aritmética de punto flotante. Para la evaluación se comparan los resultados contra la ejecución en CPUs multinúcleo. El trabajo incluye, en su primera etapa, la evaluación del estado del arte en implementaciones de HLS en FPGA. Luego se presentan desarrollos en dos de los núcleos de álgebra densa más representativos : multiplicación matriz-vector (GEMV) y multiplicación matriz-matriz (GEMM). Además, en la tesis se pone foco en uno de los núcleos más importantes de álgebra lineal dispersa, la multiplicación de matriz dispersa por vector (SpMV). Los resultados obtenidos indican que, para operaciones densas, las CPUs a menudo superan a las FPGAs; sin embargo, las FPGAs demuestran una eficiencia energética competitiva. En el caso de las operaciones dispersas, las FPGAs no sólo muestran un rendimiento competitivo, sino que también exhiben, en general, una superior eficiencia energética. Un aspecto clave para maximizar la eficiencia de los núcleos de aceleración es explorar herramientas analíticas para entender el rendimiento y guiar el proceso de optimización. El modelo roofline (RLM) es una herramienta gráfica ampliamente utilizada que facilita el análisis del rendimiento computacional y permite identificar los principales cuellos de botella. En el marco de la tesis se propone una extensión del RLM para FPGAs que asiste en la optimización del tiempo de ejecución y el consumo de energía para núcleos de NLA basados en formatos de representación a bloques para matrices dispersas. Por último, se aplica este modelo extendido a los núcleos SpMV desarrollados. El último esfuerzo en el marco de la tesis se basa en el estudio y extensión de la biblioteca Vitis de AMD para la operación SpMV, reconocida como el estado del arte en este campo. Se exploran diversas optimizaciones y técnicas de preprocesamiento de matrices, logrando mejoras significativas en el rendimiento. Entre las extensiones se exploran técnicas que conjugan reducir los tamaños de bloque (para disminuir el padding) junto con el procesamiento concurrente de varios bloques (para compensar la cantidad de datos procesados). En simple precisión se obtienen mejoras de 1.5× en promedio y de 3.7× de máximo. También se presenta el desarrollo de un núcleo SpMV específicamente optimizado para matrices de banda que ofrece amplias ganancias en performance sobre el núcleo de Vitis para esta clase de matrices.