Optimización de algoritmos para computación científica sobre arquitecturas heterogéneas

Abstract

Un esquema muy usado en la computación científica se conoce como computación con esténcil. Es el núcleo central de algoritmos de álgebra lineal, ecuaciones diferenciales parciales (EDP) y procesamiento de imágenes. Sin embargo, el desempeño de los algoritmos basados en esténcil, está limitado por la notable diferencia entre el máximo rendimiento de procesamiento y el máximo ancho de banda de memoria en los sistemas multinúcleo y unidades de computación gráfica (GPU). Por esta razón el estudio de métodos para su optimización ha sido de gran interés. Algunos métodos se basan en la optimización del empleo de memoria, sobre los cuales se han desarrollado diversos trabajos en sistemas basados en CPU y arquitecturas heterogéneas. Debido a que con estos métodos de optimización persisten limitaciones en el rendimiento, algunos autores han propuesto esquemas para sistemas basados en arreglos de compuertas programables en campo (FPGA). En esta tesis doctoral se presentan dos metodologías para la optimización de arquitecturas basadas en FPGA para la computación con esténcil. Para algunas arquitecturas el diseño se realiza a nivel de hardware con base en el modelo de Glushkov utilizando VHDL. En otros casos se realiza codiseño hardware/software utilizando herramientas de síntesis de alto nivel. Como casos de estudio se propone la implementación y evaluación de rendimiento de una arquitectura basada en esténcil para la aproximación a la solución de problemas de propagación de calor modelados con la ecuación de calor unidimensional y la ecuación de Laplace bidimensional. Se proponen transformaciones en las arquitecturas y códigos basados en esténcil para el mejoramiento del desempeño en la ejecución del algoritmo con relación a una implementación base. En el caso de implementación con la herramimenta de síntesis de alto nivel se definen parámetros asociados al tamaño del dominio de la solución y directivas de optimización, para la determinación del efecto en el desempe

A scheme widely used in scientific computing is known as stencil computation. It is the central kernel of linear algebra algorithms, partial differential equations (PDE) and image processing. However, the performance of stencil-based algorithms is limited by the remarkable difference between maximum throughput and maximum memory bandwidth in multi-core systems and graphics computing units (GPUs). For this reason the study of methods for its optimization has been of great interest. Some methods are based on optimizing the use of memory, on which various jobs have been developed in CPU-based systems and heterogeneous architectures. Because these optimization methods persist with performance limitations, some authors have proposed schemes for systems based on programmable field gate arrays (FPGA). In this thesis, two methodologies for the optimization of FPGA-based architectures for stencil computing are presented. For some architectures the design is done at the hardware level based on the Glushkov model using VHDL. In other cases, hardware/software co-design is carried out using high-level synthesis tools. As a case study, the implementation and performance evaluation of a stencil-based architecture is proposed for the approximation to the solution of heat propagation problems modeled with the one-dimensional heat equation and the two-dimensional Laplace equation