Mejora de rendimiento de la transformada rápida de Fourier

MEJORA DEL RENDIMIENTO DE LA TRANSFORMADA RÁPIDA DE FOURIER TRABAJO FIN DE GRADO CURSO 2023-2024 AUTOR JESÚS ABAJO MAGRO DIRECTOR KATZALIN OLCOZ HERRERO GRADO EN INGENIERÍA INFORMÁTICA FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID MEJORA DEL RENDIMIENTO DE LA TRANSFORMADA RÁPIDA DE FOURIER IMPROVED FAST FOURIER TRANSFORM PERFORMANCE TRABAJO DE FIN DE GRADO EN INGENIERÍA INFORMÁTICA AUTOR JESÚS ABAJO MAGRO DIRECTOR KATZALIN OLCOZ HERRERO CONVOCATORIA: JUNIO 2024 GRADO EN INGENIERÍA INFORMÁTICA FACULTAD DE INFORMÁTICA UNIVERSIDAD COMPLUTENSE DE MADRID 24 DE MAYO DE 2024 III DEDICATORIA A mi familia y amigos por apoyarme y ayudarme durante estos años. V AGRADECIMIENTOS Quisiera agradecer a mi familia y amigos, por acompañarme en este camino de la carrera. Y a Katzalin, por aceptar ser mi tutora para este trabajo. VII RESUMEN Mejora del rendimiento de la transformada rápida de Fourier 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 inplace 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. Palabras clave C, FFT, Perfilado, Multihilo, Cuellos de Botella. XV ÍNDICE DE TABLAS Tabla 1: Aceleración fft_básico vs fft_complex_struct ........................................................ 23 Tabla 2: Aceleración fft_complex_struct vs fft_fread .......................................................... 27 Tabla 3: Aceleración fft_fread vs fft_sincos .......................................................................... 32 Tabla 4: Aceleración fft_sincos vs fft_2threads .................................................................... 41 Table 5: Aceleración fft_sincos vs fft_4threads..................................................................... 46 Table 6: Aceleración fft_básico vs fft_in-place_básico ....................................................... 54 Table 7: Aceleración fft_in-place_básico vs fft_in-place_mejorado.................................. 58 Tabla 8: Aceleración fft_mejorado vs fft_in-place_mejorado ............................................ 60 Tabla 9: Aceleración fft_4threads vs fft_in-place_mejorado .............................................. 62 1 Capítulo 1 - Introducción La Transformada Discreta de Fourier (DFT) se basa en el análisis de Fourier introducido por Jean Baptiste Joseph Fourier, un cientifico francés nacido en el 1768. Ésta transformada es capaz de describir cualquier señal periódica independientemente de su complejidad, usando series armónicas [1]. Haciendo uso de las propiedades de simetría trigonométrica y la periodicidad del factor de giro. 𝑊𝑁 (𝑘𝑁 2)= −𝑊𝑁 (𝑘) (Propiedad de simetría) 𝑊𝑁 (𝑘+𝑁)= −𝑊𝑁 (𝑘) (Propiedad de periodicidad) Estas propiedades eran conocidas mucho tiempo antes de la computación digital. Heideman et al. [2] remontó la primera aparición de la FFT hasta Gauss en el 1805. Gauss desarrolló un algoritmo para calcular la DFT equivalente al de CooleyTukey. Pero este, aún estando publicado por más de 150 años, no se le dió importancia hasta la publicación del artículo de Cooley-Tukey en 1965 [3] y se presentó como un algoritmo eficiente basado en divide y vencerás para computar la DFT, lo que da como resultado una complejidad de nlogn que es lo que hace tan interesante a este algoritmo. Las complejidades algorítmicas de n² y nlogn representan dos enfoques diferentes en cuanto a cómo aumentan el número de operaciones esenciales en un algoritmo a medida que crece el tamaño de la entrada, denotado por n. Cuando se observa el crecimiento computacional de estas complejidades, podemos notar una diferencia significativa. A medida que aumentamos n, la complejidad n² crece de manera cuadrática. Por otro lado, la complejidad nlogn crece de manera mucho más moderada. Por lo tanto, incluso para tamaños de entrada pequeños, como 1024, la diferencia en el número de operaciones esenciales entre algoritmos con complejidades n² y nlogn puede ser notable, pasaríamos de 1048576 de operaciones a 10240. Esto subraya la importancia de este algoritmo, especialmente cuando se 2 trabaja con conjuntos de datos grandes, ya que el impacto en el tiempo de ejecución puede ser significativo. 1.1.1 Transformada de Fourier (FT) Las transformadas son herramientas matemáticas utilizadas para representar una señal por conveniencia matemática y para extraer información relevante. Entre las diferentes transformadas matemáticas, la Transformada de Fourier se ha convertido en una herramienta matemática para descomponer cualquier función en senos y cosenos. Para calcular esta transformada se necesita procesar un número infinito de valores discretos, lo que no es práctico para la mayoría de aplicaciones. Por lo tanto se desarrolla una Transformada Discreta de Fourier (DFT) para transformar secuencias infinitas en secuencias finitas [4]. 1.1.2 Transformada Discreta de Fourier (DFT) La Transformada de Fourier descompone señales temporales complejas en componentes de frecuencia fácilmente entendibles y tiene una salida numérica compleja que preserva la amplitud y la fase de la señal en consideración. Aplicando la Transformada de Fourier a una señal discreta en el tiempo, se obtiene una señal que es continua y cíclica en el dominio de la frecuencia y se llama Transformada de Fourier en Tiempo Discreto (DTFT). La DFT se obtiene mediante el muestreo del dominio de frecuencia de DTFT. La Transformada Discreta de Fourier (DFT) es una herramienta computacional que permite el cálculo de la transformada de Fourier en una máquina digital. La DFT reemplaza la integral infinita de una señal continua en el tiempo x(t) por una suma finita. Cualquier señal en tiempo discreto puede expresarse como una serie de Fourier con N componentes de frecuencia [5]. 1.1.3 Transformada Rápida de Fourier (FFT) La Transformada Rápida de Fourier es un metodo sistemático de calcular la DFT y su inversa, que lo hace de una forma rápida [6]. La funcionalidad principal de la FFT es descomponer los datos de entrada en unos más pequeños 2/N, separando por las posiciones pares e impares de manera recursiva hasta llegar al base, una vez en este, se aplican las operaciones necesarias para obtener la transformada a cada uno de los 3 pasos intermedios, combinando estos hasta llegar al caso con todos los datos, en el que se obtiene la transformada. Este trabajo se va a centrar en hacer una mejora del rendimiento de la Transformada Rápida de Fourier (FFT, por sus siglas en inglés Fast Fourier Transform) en el lenguaje C. La FFT es un algoritmo eficiente que computa la Transformada de Fourier de una secuencia discreta de datos. Se va a trabajar en la implementación recursiva de ésta solventando los cuellos de botella: uso de la librería de complejos, la lectura de datos y el uso de las funciones de senos y cosenos. Estos cuellos de botella se van a obtener mediante el uso de la herramienta de perfilado perf más en concreto usando report & record . Posteriormente se va a trabajar con varias CPUs, las pertenecientes a la máquina de pruebas con las que se obtengan los mejores resultados temporales, después de hacer una prueba entre éstas. Finamente se va a probar la implementación iterativa, la FFT in-place, y se le van a aplicar las mejoras obtenidas en la implementación recursiva. Posterior a la obtención de estos datos, se va a realizar una comparación entre estas implementaciones mejoradas, dando indicaciones de cuál de ellas usar según la disponibilidad de recursos que se tengan. 1.2 Usos de la FFT Los dominios de uso de la FFT son muy extensos y diversos y van emergiendo muchos usos nuevos. En esta sección no se va a discutir de manera extensa el uso de la FFT en cada caso, ya que la descripción detallada de estos usos junto a sus respectivas implementaciones y la base teorica de estos están en las referecias citadas. Uno de los principales usos de la FFT es el análisis espectral de señales, ya que la principal funcionalidad de este algoritmo es el paso del dominio del tiempo real al dominio de frecuencia. Analizando el espectro de señales de entrada en el dominio de frecuencia los parámetros desconocidos en el dominio de tiempo como la freciencia, la amplitud y la fase de la señal pueden ser observados y analizados [7]. 4 La FFT es un bloque funcional importante en los sistemas de comunicación modernos, específicamente en aplicaciones de la multiplexación por división de frecuencias ortogonales (OFDM por sus siglas en inglés) que es una técnica de transmision que consiste en la multiplexación de un conjunto de ondas portadoras de diferentes frecuencias en la que cada una transporta información. Entre la que destacan el Broadcasting digital [8], la interoperabilidad mundial para acceso por microondas [9] los estándares IEEE 802.11 [10], y Long-Term evolution (Transmision LTE) [11]. También es usada en imágenes médicas [12] para el filtrado, análisis y recontrucción de imágenes. Entre estos entra la comparación de imagenes para comprobar si son similares (image matching) entre los que están el reconicimiento facial, reconocimiento del iris y reconocimento de la huella dactilar basado en la implementación de la correlación de fase (phase-only correlation (POC)) usando FFT bidimensionales [13]. Junto a estas, hay otras muchas maneras de aplicar la FFT mayormente realacionadas con tratamiento de señales, ondas e imágenes de las que se pueden destacar también la compresion de imagenes de fractales, analisis de la textura de la superficie, codificar audio para la recepción movil y reconocimiento facial en tres dimensiones entre otras [13]. La FFT es un algoritmo ampliamente utilizado en la actualidad, con numerosos casos de uso, y por lo tanto es importante conseguir implementaciones de este que sean óptimas y aprovechen los recursos disponibles del dispositivo, tanto como lograr una implementación óptima a nivel del lenguaje en el que se escriba. 1.3 Motivación y Objetivos La razón para haber decidido trabajar en la optimización de este algoritmo son los casos de usos del algoritmo y la importancia de hacerlo de manera eficiente, ya que este cumple con un rol indispensable en muchas aplicaciones como se ha mostrado en el apartado 1.2. Los objetivos principales de este trabajo son identificar y analizar las limitaciones presentes en las implementaciones de la Transformada Rápida de Fourier (FFT), con el 5 fin de detectar los posibles cuellos de botella que puedan afectar su rendimiento. A partir de esta evaluación, se busca realizar optimizaciones que permitan mejorar tanto el tiempo de ejecución como el rendimiento general de la FFT. Además, se pretende aprovechar al máximo los recursos disponibles en el dispositivo donde se realiza el cómputo, optimizando así la utilización de la memoria y la capacidad de procesamiento. 1.4 Plan de trabajo El plan de trabajo se estructura en varias fases para abordar de manera sistemática la optimización de la implementación de la Transformada Rápida de Fourier (FFT). A continuación se detalla el proceso: 1. Identificación y análisis de cuellos de botella El trabajo comienza con la búsqueda, implementación y análisis de los posibles cuellos de botella presentes en la implementación de la FFT seleccionada. Este proceso implica un perfilado del rendimiento para identificar las áreas que requieren mejoras. Se busca entender cómo estas limitaciones afectan el rendimiento general de la FFT y se procede a realizar iterativamente optimizaciones en base a estos hallazgos. 2. Optimización basada en recursos del dispositivo Una vez que se han optimizado los cuellos de botella identificados, se pasa a la siguiente fase, que implica observar y utilizar eficientemente los recursos disponibles en la máquina donde se realiza el cómputo. Esto incluye el análisis comparativo del uso de los distintos recursos disponibles, como la memoria y la capacidad de procesamiento, con el objetivo de acelerar el proceso de cómputo de la FFT. 3. Exploración de nuevas implementaciones y comparación Cuando se alcance un potencial límite en la mejora de la implementación actual, se procede a buscar nuevas implementaciones que puedan ofrecer un rendimiento mejorado. Se busca identificar alternativas que puedan beneficiarse de 6 las mejoras realizadas en la implementación previa. Se lleva a cabo una comparativa entre las distintas implementaciones para evaluar su eficacia y rendimiento. 4. Exposición de la implementación optimizada Finalmente, se expone una implementación del algoritmo de FFT que se ha optimizado para lograr el menor tiempo de ejecución posible. Se documentan los hallazgos, las técnicas utilizadas y los resultados obtenidos durante el proceso de optimización. Este plan de trabajo proporciona una guía estructurada para abordar de manera efectiva la mejora de rendimiento de la FFT, con el objetivo de mejorar su ejecución en una variedad de aplicaciones y entornos computacionales. 7 Capítulo 2 - Versión básica de la Fast Fourier Transform(FFT) En este capítulo se presentará la versión. Esta implementación inicial de la Transformada Rápida de Fourier (FFT) se basa en un algoritmo general obtenido de una fuente confiable 1 y utiliza la biblioteca complex.h de C para manejar números complejos. A partir de esta base, se ha desarrollado una implementación inicial del algoritmo de FFT, que incorpora la lógica fundamental de esta transformación. Este enfoque proporciona una sólida base para explorar y comprender los principios de la FFT y constituye un punto de partida valioso para futuras mejoras y optimizaciones. Junto a esto se va a exponer como ejecutar y probar las implementaciones además de las propiedades de la máquina en la que se van a realizar las pruebas. 2.1 Funcionalidad En este apartado se va a mostrar el programa completo sobre el que se van a realizar las primeras pruebas. Este consta en la lógica de la FFT, una función para la lectura de los datos, otra para mostrar los datos de entrada y los resultados después de aplicar la transformación y una comprobación de potencias de 2 (el algoritmo solo acepta entradas de este tipo). 1 https://cp-algorithms.com/algebra/fft.html 8 2.1.1 Main El flujo principal del programa se desarrolla en la función main como se muestra en la figura 1, donde se lleva a cabo lo siguiente: Se verifica que se haya proporcionado un único argumento de línea de comandos, que represente el tamaño de la entrada y que este sea una potencia de 2 con la función is_power_of_two(), esto es necesario para identificar cuál va a ser el archivo de entrada que se va a leer. En caso contrario, se muestra un mensaje de error y se termina la ejecución del programa. Se abre el archivo que contiene los datos de entrada con la función fopen() y se verifica si se pudo abrir correctamente para continuar con el programa. Se reserva memoria con la función malloc() para almacenar los datos de entrada y se inicializa con los datos leidos del archivo mediante la función init_complex_array(). Fig 1: FFT main 9 Se aplica la FFT a la señal y posteriormente se libera la memoria reservada con la función free(). La implementación permite también, para comprobar los resultados, imprimir por pantalla los datos leidos, antes y después de la ejecución del programa. Para activar esta funcionalidad, habría que descomentar las funciones print_vector() de antes y después de la llamada a fft() 2.1.2 Lógica de la FFT En la función fft() mostrada en la figura 2, se lleva a cabo el procesamiento lógico fundamental de la Transformada Rápida de Fourier (FFT). En esta función, se inicia con el caso base de la recursividad cuando el tamaño de la entrada es igual a 1. Para tamaños mayores, se divide la entrada en dos partes: las posiciones pares (pe) y las posiciones impares (po), las cuales se almacenan en el heap. Estas partes se inicializan en un bucle y se realizan llamadas recursivas en cada una de ellas. Fig 2: Lógica FFT 16 En la figura 9 se pueden observar los resultados obtenidos de la ejecución de la primera versión de la FFT con 2²² (4194304) datos de entrada (parte real de la onda, la imaginaria se genera sin leerla), que es el mayor tamaño de datos sobre el que se van a hacer las pruebas, ya que se obtiene un tiempo de ejecución razonable para observar los resultados y los cuellos de botella. La manera de conseguir que la CPU actúe al casi 100% de su capacidad (frecuencia), es poniendo a linux en modo performance. Todas las pruebas se van a realizar en este modo para obtener resultados sacando todo el potencial posible al procesador. Se ve también en la captura, que se ha utilizado unicamente una CPU al 99,5% de su capacidad. Todos los tiempos que se van a mostrar a lo largo del trabajo van a ser habiendo comentado las lineas de código que hacen que se muestren por pantalla tanto los datos iniciales como el resultado, ya que la entrada y la salida de datos generan una Fig 9: Perf stat fft_básico con 2²² datos de entrada 17 sobrecarga innecesaria en el programa. Estas funciones se van a utilizar para realizar la comprobación de los resultados exclusivamente. En la figura 10 se muestran los resultados de tiempo de ejecución total obtenidos del perf stat para los datos de prueba que proporcionan más información (los más grandes) para esta primera implementación de la FFT, se ve una progresión exponencial, lo cual es coherente, ya que cada vez que se duplican los datos a ejecutar, se duplican tambien las ejecuciones realizadas por el programa. 3.2 Perf record & report Estos dos comandos dentro de perf son complementarios, ya que record graba los eventos ocurridos durante la ejecución del programa sobre el que se aplica, y el report es capaz de mostrar los resultados obtenidos del grabado leyendo un archivo llamado perf.data, que es generado en el record. Estos son los comandos utilizados para poder realizar la lectura de la ejecución del programa: Fig 10: Tiempo de ejecución del algoritmo fft_básico 18 $ sudo taskset -c 0 perf record -g <nombre_salida> <potencia_de_2> $ sudo perf report -g En la figura 11 se muestran los resultados obtenidos al ejecutar estos dos comandos para el algoritmo fft_básico con 2²² datos de entrada. El 74,54% del tiempo de ejecución se ha empleado en la función main. De este salen todas las demás partes del programa. Fig 11: Record & report fft_básico 19 En orden de mayor a menor porcentaje de tiempo de ejecución, el primero que destaca es la propia función fft con un 49,21% de la cual solo está ejecutado el 34,31% causado por el gran número de llamadas recursivas. Dentro de esta función está toda la lógica del programa, en las que cabe destacar las multiplicaciones de complejos __muldc3 13,42% en el que la gran mayoría 11,48% está ejecutado sobre sí mismo, también el almacenamiento malloc 1,51% y la liberación _int_free 2,23% y finalmente las operaciones de cosenos __cos_fma 1,72% y senos __sin_fma 1,67%. El siguiente a destacar, es la lectura de los datos, compuesta de __isoc99_fscanf con un 23,36%, la cual llama a __vfscanf_internal con un 20,67%, función que no llama a otras. Añadido a esto tenemos __GI_____strtof_l_internal con un 11,80% y str_to_mpn.constprop.0 con un 4,66% que se encarga de la traducción de strings a floats y debido a que estamos leyendo los datos de un fichero regular. Fuera de estas dos funciones también caben destacar los fallos de página que se han producido por la inmensa cantidad de datos generados con la recursividad del algoritmo y la lectura de los datos iniciales, alcanzando un 2,47%. Lo que se puede observar de esta primera implementación es que hay dos principales posibles cuellos de botella que son la multiplicación de los complejos dentro de la función fft y la lectura de los datos de la memoria, sumando entre ellos el 36,78% dentro del 74,54% que ocupa el programa. Es decir, más del 50% de la ejecución. Por lo tanto en los capítulos siguientes se va a proceder a trabajar para reducir estos valores. 20 Capítulo 4 - Cambio de <complex.h> a struct{} complex En la primera toma de resultados, se observó un posible cuello de botella en las multiplicaciones realizadas en la función principal del programa fft(). Una posible solución a este problema es cambiar el uso de los complejos proporcionados por la librería complex.h a una estructura con dos números flotantes uno para la parte real y otro para la imaginaria (struct{float Re; float Im;} complex) y luego sustituir las multiplicaciones de complejos de librería por una multiplicación de los complejos de manera “manual”. Esta parte del código se ha obtenido de una implementación de la FFT de Mladen Victor Wickerhauser de su libro Mathematics for Multimedia [14], como se muestra en la figura 13. En la figura 12 se muestra como se hacían con complex.h. En estas dos implementaciones se realizan las mismas operaciones, pero en la figura 13 se hacen de manera manual las multiplicaciones de complejos. Fig 12: Operaciones fft_básico Fig 13: Operaciones fft_complex_struct 21 Fig 14: Perf stat fft_complex_struct Fig 15: Record & report fft_complex_struct 22 En las figuras 14 y 15 se ven los resultados de ejecutar el programa con la nueva estructura para los complejos realizando las multiplicaciones de manera manual, para 2²² datos de entrada. Revisando la captura del perf vemos que ya no se encuentra el __muldc3 y esto es coherente, ya que se han cambiado las multiplicaciones de complejos de la librería complex.h por las nativas de C, se puede ver un cambio debido a esto en la parte que corresponde a la ejecución de la función fft, antes ocupaba un 49.34% de la que un 34.31%, que corresponde a un 69,53% de la ejecución de la función se ejecutaba la fft. En esta nueva implementación se ve un cambio, ahora la ejecución de fft es de 42.87% de la que un 39.06%, que corresponde a un 91,11% de la ejecución de la función se ejecuta la fft, lo que nos indica que las multiplicaciones de los complejos están ejecutadas aquí. El porcentaje restante como se expuso en el capítulo anterior, son de senos, cosenos, malloc, free y fallos de página. Con este cambio se ha conseguido reducir el tiempo de ejecución, como se esperaba. Sin embargo la mejora no podia ser sustancial en reducción tiempo, ya que el problema __muldc3, solo ocupaba un 13,42% y no se podía eliminar completamente porque las multiplicaciones son necesarias para la correcta ejecución del algoritmo. Esta es la comparación de los resultados obtenidos, se ha pasado de 1,048s a 0,951s. Y podemos calcular la aceleración de la siguiente manera: Speedup=𝑇𝑖𝑒𝑚𝑝𝑜𝑖𝑛𝑖𝑐𝑖𝑎𝑙 𝑇𝑖𝑒𝑚𝑝𝑜𝑓𝑖𝑛𝑎𝑙 Speedup=1,048 0,951= 1,102 una aceleración del 10,2%. 23 Después de haber visto como calcular la aceleración entre las diferentes versiones del algoritmo, con los datos obtenidos se han creado estas tablas para mostrar la información más relevante (en la documentación del proyecto se encuentran todas las capturas de las que se han sacado los datos), se ve que la aceleración media desde 2¹⁵ entradas es de 1.151, un 15,1%. Fig 16: Record & report fft_complex_struct Tabla 1: Aceleración fft_básico vs fft_complex_struct 24 Capítulo 5 - Cambio de fscanf a fread En los dos capítulos anteriores se observa un cuello de botella que asciende a un 44,18% para la ejecución de la lectura de los datos dado por: __isoc99_fscanf con un 24,51% que contiene a __vfscanf_internal con un 22,52%, sumado a __GI_____strtof_l_internal con un 13,52% y str_to_mpn.constprop.0 con un 5,94%. Estos porcentajes de ejecución aún con la cantidad de datos tomados (máximo 2²²) llama suficiente la atención como para intentar buscar un alternativa mejor. En estos casos anteriores se hace con fscanf, que va leyendo uno a uno los datos de entrada, haciendo una llamada al sistema en cada lectura unitaria, lo que causa que esta implementación no sea óptima. La mejora realizada utiliza fread para poder realizar una única llamada al sistema y leer todos los datos a la vez. Esta mejora requiere de una serie de cambios en los datos de entrada/casos de prueba, ya que fread actúa en un solo bloque, pero necesita leer los datos en binario. Para esto se han creado unos programas para poder pasar los datos iniciales a binario (txt_to_bin.c) y otro para leer los datos (read_bin). Este último se implementa en cada programa sustituyendo el anterior modo de lectura. 25 Fig 17: Perf stat fft_fread Fig 18: Record & report fft_fread 32 A partir de los resultados obtenidos en esta iteración del código mostrados en la figura 23 y la tabla 3, cabe destacar, que casi todos los problemas de la implementación han sido resueltos, a falta de dos puntos clave, los fallos de página y la reserva de memoria mediante malloc. Los fallos de página se empiezan a observar a partir de entradas de datos de 2¹⁴ (16384) entradas, estos suponen un porcentaje alto en el cómputo total de la implementación. La relación en el cómputo global asciende al 7,17%, lo que de poder eliminarlo supondría una buena mejora a la implementación. Por otra parte, el uso de malloc y free producen también una sobrecarga en la implementación, pero son indispensables para su correcto funcionamiento. Si se prescindiera de ellos (así era una implementación base anterior a la primera mostrada en el documento), a partir de casos de entrada superiores a 2¹⁸ se producirían fallos de segmentación. Tabla 3: Aceleración fft_fread vs fft_sincos 33 Capítulo 7 - Paralelización con hilos Una vez resueltos los principales cuellos de botella de la implementación, se propone una nueva mejora, que consiste en utilizar más recursos de la máquina en la que se trabaja, en concreto las CPUs. La manera de aprovechar las distintas CPUs de la máquina de trabajo es a través de la creación de distintos hilos para intentar que la versión paralelizada del algoritmo sea más rápida. 7.1 Mejora a paralelización con 2 hilos En este apartado se van a mostrar los cambios necesarios en la implementación del algoritmo para ejecutarlo en 2 hilos, cada uno en un core. Este apartado es el que más cambios a nivel de código va a necesitar, por la manera de definir los hilos en C. 7.1.1 Función principal fft() Hasta la creación de la onda que guarda los casos de prueba el código sigue de la misma manera, pero, para poder hacer llamadas recursivas habiendo creado los hilos, hace falta cambiar la cabecera para introducirle los argumentos necesarios al hilo. typedef struct{complex *p; int size; int log2n;} thrd_arg ; Estos argumentos del hilo, son los mismos que tenía la cabecera en las otras implementaciones del algoritmo, pero agrupados en una estructura que se inicializa después de la creación de la onda en el main. 34 Una vez inicializada la estructura, se crea el primer hilo que ejecutará la función principal. Para esto es necesario seleccionar la CPU en la que se va a ejecutar, con la función CPU_SET() en la que el primer argumento es un entero que selecciona el número de la CPU en el que se va a ejecutar el hilo, introduciendo este valor en cpuset0. Posteriormente se crea el hilo llamando a la función fft con los argumentos previamente creados. La función setaffinity que se encarga de hacer que se migre el hilo a la CPU seleccionada y finalmente el join para esperar a que acabe la ejecución del hilo. Fig 24: Creación del primer hilo 35 En la figura 25 se muestra como se crea el segundo hilo, como se va a probar con 2, sólo se crea si el tamaño del la onda es igual al tamaño de la onda de entrada, es decir el caso en el que se hace la llamada desde el main y no en las llamadas recursivas. El resto del código sigue igual hasta el punto en el que se harían las llamadas recursivas, después de la separación de la onda en la parte de las posiciones pares e impares. Este segundo hilo se crea de la misma manera que el primero del main, pero para seleccionar una cpu distinta, se hace uso de un contador como variable global que permitirá la expansión a más CPUs. Finalmente se espera a que acabe la ejecución del hilo con el join. static int cpu_counter = 1; Se inicializa el contador a 1 para no tenerlo que iterar en la creación del primer hilo. Fig 25: Inicialización del segundo hilo 36 Por otra parte, en el resto de casos en los que el tamaño de la onda es menor al de la onda de entrada, se realiza la recursión de la misma manera que se hacía en el resto de implementaciones, pero creando la estructura con los argumentos de la función, como se muestra en la figura 26. Se ha comprobado que los resultados de ejecutar esta implementación con 2 hilos son los mismos que en las anteriores implementaciones. 7.2 Tipos de CPU y comparación en uso Como se expuso en el capítulo 2 la máquina en la que se desarrollan las pruebas contiene dos tipos distintos de CPU, los efficient y los performance, y se expresó que en todas las pruebas se iban a utilizar los de tipo performance, ya que llegan a mayor frecuencia. Aquí se va a exponer una comparativa entre los distintos cores 7.2.1 Performance CPUs en el mismo core En este apartado se va a exponer la mejora temporal que supone ejecutar esta implementación en dos performance CPUs dentro del mismo core (CPUs 0 y 1). Fig 26: Recursividad con los hilos creados 37 7.2.2 Performance CPUs en el diferente core En este apartado se va a exponer la mejora temporal que supone ejecutar esta implementación en dos performance CPUs en diferentes cores (CPUs 0 y 2). Fig 27: Perf stat fft_2threads en el mismo performance core Fig 28: Perf stat fft_2threads en el diferente performance core 38 7.2.3 Efficient CPUs en el mismo cluster En este apartado se va a exponer la mejora temporal que supone ejecutar esta implementación en dos performance CPUs dentro del mismo cluster (CPUs 12 y 13). Fig 29: Perf stat fft_2threads en el mismo efficient core 39 7.2.4 Efficient CPUs en el diferente cluster En este apartado se va a exponer la mejora temporal que supone ejecutar esta implementación en dos performance CPUs en diferentes clusters (CPUs 12 y 16). 7.2.5 Análisis de resultados Una vez probados todos los casos, podemos observar claramente cuál es la mejor manera de realizar el multithreading. Una clara diferencia respecto a los resultados de los capítulos anteriores, es el incremento que se ve en las CPUs utilizadas, que pasan de 1 a casi 2, lo que nos muestra que efectivamente, se está ejecutando en diferentes CPUs, aunque en ningún caso llega a 2 este valor. El primer descarte es la ejecución en cores Efficient que al tener menor frecuencia de reloj, iba a ser un resultado natural obtener peores tiempos de ejecución. Cabe destacar que el uso de dos cores de este tipo para hacer multithreading independientemente de estar en el mismo cluster o no, ha supuesto incluso un Fig 30: Perf stat fft_2threads en el diferente efficient core 40 empeoramiento respecto a la última implementación en un único hilo, habiendo sido hecha esta ejecución en un core Performance. El otro descarte observando los resultados, es la ejecución en dos CPUs Performance dentro del mismo core, esto es debido a como está estructurada la microarquitectura del procesador, que hace que estas dos CPUs compartan todos los recursos del core, y por lo tanto compiten entre ellas para utilizar los recursos, no aprovechando bien la paralelización del código. Finalmente, con la que se obtiene una considerable mejora es usando las CPUs de tipo Performance en cores distintos, ya que se utilizan las CPUs más potentes del procesador y no compiten entre ellas por los recursos. Fig 31: Resultados temporales fft_2threads 41 Tras la obtención de los resultados para los tamaños de entrada más relevantes mostrados en la figura 31 y la tabla 4 se observa una buena mejora temporal en todos los casos probados. Estos resultados son buenos, al haber tenido una mejora en todas las pruebas, pero cabe destacar, que al utilizar el doble de recursos, se espera una mejora más significativa que una media del 45,6% de mejora. Tabla 4: Aceleración fft_sincos vs fft_2threads 48 En este caso se observa que los cambios de contexto han aumentado hasta los 214 cuando con 4 hilos eran solo 30. También hay que tener en cuenta que el procesador de la máquina de pruebas no cuenta con los suficientes cores de tipo Performance para cubrir los 8 hilos, por lo que se ven contadores cpu_atom, que solo están presentes en las CPUs de tipo Efficient. Nuevamente se observa un aumento en los fallos de página también producido por el uso de más CPUs. Con estos datos tomados, es coherente que no haya habido una mejora significativa entre esta implementación y la de 4 hilos, en concreto ha habido una mejora temporal de una milésima, lo que en la práctica no supone ninguna mejora. Fig 36: Perf stat fft_8threads 49 Aquí se observa como se ha hecho uso de las 8 CPUs, CPU1(rojo), CPU3(amarillo), CPU5(verde), CPU7(azul), CPU9(magenta), CPU11(beige), CPU13(verde claro) y CPU15(azul oscuro). Se descarta el uso de esta mejora debido a los resultados obtenidos, en los que la mejora temporal es prácticamente nula en comparación a los recursos utilizados en su ejecución. Fig 37: Procesador ejecutando fft_8threads 50 Capítulo 8 - Solución de las reservas de memoria y los fallos de página usando la fft in-place En este capítulo se va a mostrar una nueva implementación de la fft, en la que por la manera de ejecutarse, solo requiere de una reserva de memoria para la onda, ya que se basa en reordenar los casos de una manera concreta para dejar de ser una implementación recursiva. Esto hace que se deje de tener que separar la onda en otras más pequeñas con las posiciones pares e impares para no tener que reservar la memoria en estos casos. El trabajar en la onda de entrada produce que estos datos se pierdan después de realizar la transformada. No se va a entrar mucho en el porque funciona de esta manera, la implementación pero se puede encontrar en este artículo 6 con su respectiva explicación detallada. Esta implementación nos ayuda a comparar la implementación final obtenida con una que va a perder la carga de malloc, free y gran parte de los fallos de página provocados por la creación de tantas ondas intermedias. Todas las mejoras realizadas en la fft de la primera implementación son aplicables a esta también exceptuando la creación de distintos hilos. 8.1 Implementación básica de la fft in-place En este apartado se va a mostrar una implementación de la fft in-place, sin aplicar las mejoras obtenidas en los capítulos anteriores para poder hacer posteriormente una comparación con una implementación con todas las mejoras. Se ha comprobado que los resultados de ejecutar esta implementación básica de la fft in-place son los mismos que en las implementaciones anteriores. 6 https://cp-algorithms.com/algebra/fft.html 51 En la figura 38 se muestra la implementación de la nueva función fft, en la que se observa que no hay inicializaciones de memoria para crear las ondas de pares e impares como en la implementación recursiva. En este caso se opta por una reordenación de los datos de entrada para que queden como si se hubiera hecho la recursión a través de intercambios de posiciones, junto a una marera ingeniosa de realizar las operaciones con los datos a traves de los tres bucles for que también imitan la recursión. Fig 38: Lógica fft_in-place básica 52 En la figura 39 se observan los resultados obtenidos de la ejecución del perf stat a esta implementación básica de la fft in-place. La gran diferencia de esta implementación, como se había adelantado al comienzo del capítulo, son los pocos fallos de página que se producen, debido a que se guarda la onda solo una vez. Se han pasado de unos 40000 fallos de página a 8000 respecto a las implementaciones anteriores sin hilos. Esto junto a no ejecutar tantos malloc y free, hace que la implemencación básica sea bastante más rápida que la fft básica pasando de 1,047s a 0,794s. Y podemos calcular la aceleración de la siguiente manera: Speedup=1,048 0,794= 1,318 una aceleración del 31,8% Fig 39: Perf stat fft_in-place_básico 53 En la figura 40 se muestran los resultados del perf record & report, en los que se observan los mismos problemas que en la ejecución de la fft básica. Gran parte del cómputo gastado en leer los datos, producido por el fscanf, mucha parte de la ejecución gastada en en las multiplicaciones de la librería de complejos, los fallos de página están presentes pero no suponen tanto tiempo en relación con lo demás y no se observar las operaciones de senos y cosenos por la misma razón. Fig 40: Record & report fft_in-place_básico 54 8.1.1 Comparación fft recursiva e in-place básicas A continuación se va a mostrar una comparación con las entradas de datos más relevantes entre la primera implementació de la fft y esta de la fft in-place. En estos resultados temporales se puede observar una mejora general en la mayoría de casos, haciendose más notable en los casos más grandes, producido por la eliminación de los fallos de página y las constantes reservas de memoria que ya no Fig 41: Resultados temporales fft_in-place_básico Table 6: Aceleración fft_básico vs fft_in-place_básico 55 están presentes en esta implementación y en los casos más grandes de la implementación recursiva aumentan mucho estos. 8.2 Implementación mejorada de la fft in-place En este apartado se van a mostrar los resultados de aplicar todas las mejoras obtenidas en las implementaciones de la fft sin aplicar las mejoras de hilos. El resumen de los cambios sería: Cambiar el uso de los complejos de la librería de C a una estructura de datos con parte real e imaginaria, cambiando las operaciones para que se realicen correctamente, de la misma manera que en la implementación recursiva. El cambio la manera de leer dos datos de fscanf a fread, haciendo la lectura de los datos desde archivos binarios, este cambio es igual que en la implementación recursiva de la fft, dentro de la función init_complex_array. Y finalmente dejar de calcular los senos y los cosenos en cada iteración, dejando estos valores precalculados en un array bidimensional y accediendo a ellos cuando se necesiten, esta parte también es igual que en la implementación recursiva. Se ha comprobado los resultados de ejecutar esta implementación con las mejoras de la fft in-place en la que se obtienen los mismos resultados que en las implementaciones anteriores. 56 En la figura 42 se muestran los resultados temporales obtenidos con la ejecución del perf stat, aplicando todas las mejoras realizadas para la fft. Los resultados son bastante satisfactorios pasando de 0,794s a 0,355s y aquí se muestra la aceleración obtenida tras las mejoras: Speedup=0,794 0,355= 2,236 una aceleración del 123,6%. Fig 42: Perf stat fft_in-place_mejorado 57 En la figura 43 se muestra la ejecución del perf record & report, han desaparecido todos los problemas que se obtenían de la anterior implementación sin las mejoras, estando prácticamente de manera integra el cómputo dentro de la función principal fft. En comparación con la implementación de la fft recursiva, se ve que los fallos de página se han reducido hasta un 2,5% de la ejecución, mientras que en la fft recursiva alcanzaron en la mejor implementación sin hilos un 7,17%. Por otra parte, las ejecuciones de malloc y free se han reducido hasta casi eliminarse, ya ni siquiera aparecen en el perf, por lo tanto su porcentaje de ejecución no llega al 0,21%. Este es un resultado razonable ya que solo se llama a estas funciones una vez para crear la onda inicial y luego liberar la memoria. Fig 43: Record & report fft_in-place_mejorado 64 la implementación para conseguir reducirlos. En este caso, se observó el factor limitante de los fallos de página junto a las reservas y liberaciones de memoria y se tuvo que buscar una implementación diferente para eliminarlos, mediante la fft inplace. A la cual se le han podido aplicar las mejoras realizadas en la implementación recursiva y así mejorar su rendimiento. Tras la realización de este trabajo se puede concluir con haber obtenido dos implementaciones con una mejora de rendimiento notable, útiles en distintos casos de uso. La primera implementación va dirigida para máquinas de trabajo con varias CPUs, esta es la implementación fft_threads, que es capaz de dividir la carga de trabajo entre las distintas CPUs del procesador para obtener los mejores resultados temporales posibles. Esta implementación es escalable para procesadores más potentes que la máquina de pruebas utilizada, realizando previamente un estudio de la máquina en la que se va a ejecutar para sacarle el mayor potencial. Por otra parte está la implementación fft_in-place que solventa los fallos de página y no utiliza tantas reservas de memoria, pero solo se ejecuta en una CPU por lo que puede ser temporalmente peor dependiendo de la máquina de pruebas, como es el caso de la máquina en la que se ha realizado este trabajo. La primera implementación contaba con una complejidad nlogn que es a lo máximo que se puede optar para realizar esta transformada, siendo una mejora de la Transformada Discreta de Fourier por fuerza bruta con una complejidad de n². Se puede afirmar que no solo basta con obtener una complejidad mejor para que el un algoritmo se ejecute de la manera más rápida posible, sino que también hay que aprovechar los recursos disponibles tanto en la máquina como del lenguaje seleccionado, ya que estos pueden generar una mejora sustancial. Trabajo Futuro En este trabajo, como en todos los trabajos de investigación, se deja aún cabida a la mejora, para que en un futuro se pueda seguir trabajando en este proyecto. Por su complejidad y falta de recursos, no se han podido llegar a realizar dentro de este, pero aquí se exponen las posibles líneas para seguir trabajando: 65 En este proyecto se ha optado por dar unas implementaciones que sean fácilmente portables entre distintos dispositivos mediante el uso del lenguaje C, que puede ser compilado en cualquier máquina. Pero, para obtener unos resultados potencialmente mejores, se podría trabajar con extensiones multimedia que soporte el dispositivo de pruebas. Este es un buen punto en el que continuar el trabajo debido a la carga que tiene el algoritmo en procesar operaciones repetidamente, que se podrían aprovechar de la ejecución en paralelo que proporcionan estas extensiones [Extensiones Multimedia al Lenguaje Máquina en Procesadores de Propósito General. Enrique F. Torres y Víctor Viñals]. Otro punto que se podría intentar solventar para no tener que cambiar a la implementación in-place, sería buscar alguna manera de traer los datos de memoria antes de ser necesitados por el programa para intentar eliminar o reducir los fallos de página. Esto daría una implementación multihilo mucho más eficiente. 66 BIBLIOGRAFÍA 1: Saribulut, L., Ahmet, T. E. K. E., & TÜMAY, M. “Fundamentals and literature review of Fourier transform in power quality issues. Journal of Electrical and Electronics Engineering Research”, 5(1), 9-22. 2013 2: Heideman MT, Johnson DH, Burrus CS, “ Gauss and the history of the fast Fourier transform, Archive for History of Exact Sciences”. Arch. Hist. Exact Sci. 34(3):265-277. 1985 3: James W. Cooley and John W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series” p 297-301 4: Ann Maria John, Kiran Khanna, Ritika R Prasad, Lakshmi G Pillai “A Review on Application of Fourier Transform in Image Restoration”. Page 389 5: Kuo SM, Lee BH. “Real-time digital signal processing implementations applications and experiments with the TMS320C55x”. John Wiley & Sons, Inc.2001, pp 173-217 6: jain, Anil K., “Fundamentals of digital image processing”, 1989 7: A.V. Oppenheim, R.W. Schafer, J.R. Buck et al., Discrete-Time Signal Processing vol2 8: Richard M. Jiang. "An area-efficient FFT architecture for OFDM digital video broadcasting" 9: Chih-Peng Fan, Mau-Shih Lee, Guo-An SuA. "Low Multiplier and Multiplication Costs 256-point FFT Implementation with Simplified Radix-24 SDF Architecture" 10: Taesang Cho, Hanho Lee, Jounsup Park, Chulgyun Park "A high-speed lowcomplexity modified radix-25 FFT processor for gigabit WPAN applications" 11: Sheng-Yeng, Kai-Ting, Chao-Ming, Yuan-Hao "Energy-efficient 128 2048/1536-point FFT processor with resource block mapping for 3GPP-LTE system" 12: Mohammad Nazmul Haque, Mohammad Shorif Uddin, M. Abdullah-Al-Wadud, Yoojin Chung "Fast reconstruction technique for medical images using graphics processing unit" 13: K.R. Rao , D.N. Kim , J.-J. Hwang Fast Fourier Transform - Algorithms and Applications 14: , https://www.math.wustl.edu/~victor/mfmm/fourier/fft.c, 67 APÉNDICES Apéndice A - Funciones auxiliares Para el correcto funcionamiento y ejecución de la FFT son necesarias una serie de funciones auxiliares utilizadas en el main para comprobar la entrada e inicializar los datos. Se van a exponer en orden de uso en el main. La función is_power_of_two realiza una comprobación para determinar si un número dado es una potencia de 2. Esta función recibe un entero n como argumento y devuelve un valor booleano, verdadero si n es una potencia de 2 y falso en caso contrario. En el return se observa la logica para comprobar eficientemente si el valor de entrada es potencia de 2. Esto se logra mediante el uso de una operación de bits. Se compara n con n - 1 utilizando el operador & (AND bit a bit). Si el resultado de esta operación es 0 y n es mayor que 0, entonces n tiene exactamente un bit establecido, lo que significa que es una potencia de 2. La función init_complex_array se encarga de inicializar un array de números complejos a partir de los datos leídos desde un archivo. Recibe tres argumentos: wave que es el array de números complejos que se va a inicializar, size que es un puntero a un entero que indica el tamaño del array, y file que es el puntero al archivo del cual se leerán los datos. 68 Dentro de la función, se utiliza un bucle for para iterar sobre cada elemento del array wave. En cada iteración, se utiliza la función fscanf() para leer un número de punto flotante del archivo file y se guarda en la variable num. Luego, se asigna este valor a la posición correspondiente del array wave, convirtiéndolo en un número complejo con parte imaginaria cero, utilizando la macro I de la biblioteca estándar de C. La función print_vector imprime en la consola los elementos de un vector de números complejos junto con un título que describe su contenido y su dimensión. Toma tres argumentos: title para el título del vector, p para el vector en sí y n para su dimensión. Utiliza un bucle para recorrer cada elemento del vector e imprime su parte real (creal()) e imaginaria (cimag()) en formato de número complejo. Esta función facilita la visualización del contenido del vector, lo que puede ser útil para entender y depurar el código que trabaja con números complejos. 69 Apéndice B - Obtención de gráficas y tablas utilizadas Para la obtención de las gráficas y la tablas, se ha utilizado un nootebook en Google Colab con las librerías de python pandas y matplotlib.pyplot. Ambas han sido generadas con los mismos datos que han sido recolectados de las ejecuciones del perf stat de cada una de las implementaciones y se han introducido los datos en un DataFrame de pandas de la siguiente manera: Aquí queda creada la estructura en la que se van a introducir los datos, definiendo los tamaños a los que se van a referir los datos obtenidos y dejando libre una parte para poner los tiempos de las implementeciones. De esta manera se han introducido los datos de cada una de las iteraciones del código. Posteriormente para crear la grafica y tabla correspondiente, habría que ejecutar los bloques de código que contuvieran los datos que se van a querer mostrar y posteriormente ejecutar las creaciones de la gráfica y la tabla. 70 Este es el código que genera las gráficas en el que se vecomo se define el tamaño de la salida, como rerorre las estructuras con los datos temporales creados y como finalmente se crea la tabla con todos sus atributos. Este es el código que genera las tablas con las aceleraciones, en el que se crea un pandas DataFrame con la estructura de los tiempos y los tamaños de entrada, posteriormente se genera una nueva entrada llamada aceleración que es la división entre las dos implementaciones sobre las que se quiere calcular la aceleración. Finalmente se seleccionan las columnas que queremos obtener en la salida, adecuando la nueva columna aceleration al formato de dotos los datos y se muestra la tabla de salida. 1 Introduction The Discrete Fourier Transform (DFT) is based on Fourier analysis introduced by Jean Baptiste Joseph Fourier, a French scientist born in 1768, to describe any periodic signal regardless of its complexity using harmonic series [1]. It makes use of the properties of trigonometric symmetry and the periodicity of the twiddle factor. 𝑊𝑁 (𝑘𝑁 2)= −𝑊𝑁 (𝑘) (Symmetry property) 𝑊𝑁 (𝑘+𝑁)= −𝑊𝑁 (𝑘) (Periodicity property) These properties were known long before digital computation. Heideman et al. [2] traced the first appearance of the FFT back to Gauss in 1805. Gauss developed an algorithm to compute the DFT equivalent to the Cooley-Tukey algorithm. However, despite being published for over 150 years, it did not gain significance until the publication of the Cooley-Tukey paper in 1965 [3]. It was presented as an efficient divide-and-conquer algorithm for computing the DFT, resulting in a complexity of nlogn, which is what makes this algorithm so interesting. The algorithmic complexities of n² and nlogn represent two different approaches to how the number of essential operations in an algorithm increases as the input size, denoted by n, grows. When observing the computational growth of these complexities, we can notice a significant difference. As we increase n, the complexity n² grows quadratically. On the other hand, the complexity nlogn grows much more moderately. Therefore, even for small input sizes, such as 1024, the difference in the number of essential operations between algorithms with n² and nlogn complexities can be notable, going from 1048576 operations to 10240. This underscores the importance of this algorithm, especially when working with large datasets, as the impact on execution time can be significant. 2 Fourier Transform (FT) Transforms are mathematical tools used to represent a signal for mathematical convenience and to extract relevant information. Among the various mathematical transforms, the Fourier Transform has become a crucial tool for decomposing any function into sines and cosines. To calculate this transform, an infinite number of discrete values must be processed, which is impractical for most applications. Therefore, the Discrete Fourier Transform (DFT) was developed to transform infinite sequences into finite sequences [4]. Discrete Fourier Transform (DFT) The Fourier Transform decomposes complex temporal signals into easily understandable frequency components and yields a complex numerical output that preserves the amplitude and phase of the signal in question. By applying the Fourier Transform to a discrete-time signal, a signal that is continuous and cyclical in the frequency domain is obtained, called the Discrete-Time Fourier Transform (DTFT). The DFT is obtained by sampling the frequency domain of the DTFT. The Discrete Fourier Transform (DFT) is a computational tool that allows the calculation of the Fourier transform on a digital machine. The DFT replaces the infinite integral of a continuoustime signal x(t) with a finite sum. Any discrete-time signal can be expressed as a Fourier series with N frequency components [5]. Fast Fourier Transform (FFT) The Fast Fourier Transform is a systematic method for quickly calculating the DFT and its inverse [6]. The primary functionality of the FFT is to decompose the input data into smaller 2/N parts, separating them by even and odd positions recursively until reaching the base case. Once at this point, the necessary operations are applied to obtain the transform at each intermediate step, combining these steps until reaching the case with all the data, at which the transform is obtained. This work will focus on improving the performance of the FFT in the C language. The FFT is an efficient algorithm that computes the Fourier Transform of a discrete data sequence. 3 The work will address the recursive implementation of the FFT by resolving bottlenecks: the use of the complex library, data reading, and the use of sine and cosine functions. These bottlenecks will be identified using the perf profiling tool, specifically using the report and record commands. Subsequently, the implementation will be tested on multiple CPUs from the test machine to determine which yields the best time results after conducting a comparative test. Finally, the iterative implementation, the in-place FFT, will be tested, and the improvements obtained in the recursive implementation will be applied to it. After obtaining these data, a comparison between these improved implementations will be made, providing recommendations on which to use based on the available resources. Uses of the FFT The applications of the FFT are vast and diverse, with many new uses continually emerging. This section will not extensively discuss the use of the FFT in each case, as the detailed description of these uses along with their respective implementations and theoretical foundations are covered in the cited references. One of the primary uses of the FFT is in spectral analysis of signals, as the main functionality of this algorithm is the transformation from the time domain to the frequency domain. By analyzing the spectrum of input signals in the frequency domain, unknown parameters in the time domain such as frequency, amplitude, and phase of the signal can be observed and analyzed [7]. The FFT is a crucial functional block in modern communication systems, specifically in applications of Orthogonal Frequency Division Multiplexing (OFDM), a transmission technique that involves multiplexing a set of carrier waves of different frequencies, each carrying information. Notable applications include digital broadcasting [8], Worldwide Interoperability for Microwave Access (WiMAX) [9], IEEE 802.11 standards [10], and Long-Term Evolution (LTE) transmission [11]. It is also used in medical imaging [12] for filtering, analysis, and image reconstruction. This includes image matching to check for similarities, such as facial