Mejora de rendimiento de la transformada rápida de Fourier

Abstract

Este trabajo plantea cómo mejorar el rendimiento de la Transformada Rápida de Fourier FFT en su implementación recursiva haciendo uso del perfilado de código con la herramienta perf para obtener los cuellos de botella del algoritmo implementado en C. Consta de distintas iteraciones del proceso de mejora del código para solventar estos cuellos de botella. Posteriormente de estas primeras mejoras, se modifica el código para poderla ejecutar en distintas CPUs y así aprovechar los recursos de la máquina de pruebas, variando el número de CPUs utilizadas y comparando la ejecución entre estas. Finalmente para eliminar los cuellos de botella intrínsecos a esta implementación, se opta por una implementación iterativa FFT in-place a la que se le aplican las mejoras obtenidas en la implementación recursiva y se comparan estos resultados con los de la otra implementación.This work proposes improving the performance of the Fast Fourier Transform (FFT) in its recursive implementation by using code profiling with the perf tool to identify bottlenecks in the algorithm implemented in C. It involves several iterations of the code improvement process to address these bottlenecks. Following these initial improvements, the code is modified to enable execution on different CPUs to leverage the resources of the testing machine, varying the number of CPUs used and comparing the execution among them. Finally, to eliminate the intrinsic bottlenecks of this implementation, an iterative FFT in-place implementation is chosen, to which the improvements obtained in the recursive implementation are applied, and these results are compared with those of the other implementation.