Análisis de rendimiento de un algoritmo de diagonalización de matrices por el método de Jacobi sobre una arquitectura multicore

Abstract

El objetivo general de este trabajo es mostrar la aceleración en el tiempo de cómputo que se obtiene al paralelizar el algoritmo de diagonalización de matrices simétricas por el método de Jacobi, de forma de aprovechar el paralelismo a nivel de thread que provee la arquitectura multicore actual. Los temas a abordar abarcan el análisis del problema, el estudio de distintas implementaciones del algoritmo secuencial y optimizaciones posibles, la adaptación de dicho algoritmo para hacer uso de una implementación de la API BLAS (Basic Linear Algebra Subprograms) optimizada para la arquitectura subyacente, y la implementación de un algoritmo paralelo utilizando la herramienta de programación sobre memoria compartida OpenMP. El método de Jacobi para diagonalizar matrices simétricas tiene aplicaciones en áreas como biometría, visión artificial, procesamiento digital de señales, entre otros. A medida que el volumen de datos de entrada se incrementa, la cantidad de tiempo requerido para el cómputo aumenta en forma significativa. La combinación de librerías de álgebra lineal optimizadas para la arquitectura subyacente, junto con la potencia que brinda un multicore y una herramienta adecuada de programación paralela para dicha arquitectura permitirá reducir el tiempo de ejecución. Este trabajo pretende aportar un análisis del rendimiento (speed up, eficiencia) obtenido por el algoritmo paralelo propuesto sobre una arquitectura multicore, a medida que se incrementa el volumen de datos de entrada (tamaño de la matriz) y al aumentar la cantidad de threads/cores.