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 amilia y amigos po apoya me y ayuda me du an e es os años. V AGRADECIMIENTOS Quisie a ag adece a mi amilia y amigos, po acompaña me en es e camino de la ca e a. Y a Ka zalin, po acep a se mi u o a pa a es e abajo. VII RESUMEN Mejo a del endimien o de la ans o mada ápida de Fou ie Es e abajo plan ea cómo mejo a el endimien o de la T ans o mada Rápida de Fou ie FFT en su implemen ación ecu si a haciendo uso del pe ilado de código con la he amien a pe pa a ob ene los cuellos de bo ella del algo i mo implemen ado en C. Cons a de dis in as i e aciones del p oceso de mejo a del código pa a sol en a es os cuellos de bo ella. Pos e io men e de es as p ime as mejo as, se modi ica el código pa a pode la ejecu a en dis in as CPUs y así ap o echa los ecu sos de la máquina de p uebas, a iando el núme o de CPUs u ilizadas y compa ando la ejecución en e es as. Finalmen e pa a elimina los cuellos de bo ella in ínsecos a es a implemen ación, se op a po una implemen ación i e a i a FFT in- place a la que se le aplican las mejo as ob enidas en la implemen ación ecu si a y se compa an es os esul ados con los de la o a implemen ación. Palab as cla e C, FFT, Pe ilado, Mul ihilo, Cuellos de Bo ella. XV ÍNDICE DE TABLAS Tabla 1: Acele ación _básico s _complex_s uc ........................................................ 23 Tabla 2: Acele ación _complex_s uc s _ ead .......................................................... 27 Tabla 3: Acele ación _ ead s _sincos .......................................................................... 32 Tabla 4: Acele ación _sincos s _2 h eads .................................................................... 41 Table 5: Acele ación _sincos s _4 h eads..................................................................... 46 Table 6: Acele ación _básico s _in-place_básico ....................................................... 54 Table 7: Acele ación _in-place_básico s _in-place_mejo ado.................................. 58 Tabla 8: Acele ación _mejo ado s _in-place_mejo ado ............................................ 60 Tabla 9: Acele ación _4 h eads s _in-place_mejo ado .............................................. 62 1 Capí ulo 1 - In oducción La T ans o mada Disc e a de Fou ie (DFT) se basa en el análisis de Fou ie in oducido po Jean Bap is e Joseph Fou ie , un cien i ico ancés nacido en el 1768. És a ans o mada es capaz de desc ibi cualquie señal pe iódica independien emen e de su complejidad, usando se ies a mónicas [1]. Haciendo uso de las p opiedades de sime ía igonomé ica y la pe iodicidad del ac o de gi o. 𝑊𝑁 (𝑘𝑁 2)= −𝑊𝑁 (𝑘) (P opiedad de sime ía) 𝑊𝑁 (𝑘+𝑁)= −𝑊𝑁 (𝑘) (P opiedad de pe iodicidad) Es as p opiedades e an conocidas mucho iempo an es de la compu ación digi al. Heideman e al. [2] emon ó la p ime a apa ición de la FFT has a Gauss en el 1805. Gauss desa olló un algo i mo pa a calcula la DFT equi alen e al de Cooley- Tukey. Pe o es e, aún es ando publicado po más de 150 años, no se le dió impo ancia has a la publicación del a ículo de Cooley-Tukey en 1965 [3] y se p esen ó como un algo i mo e icien e basado en di ide y ence ás pa a compu a la DFT, lo que da como esul ado una complejidad de nlogn que es lo que hace an in e esan e a es e algo i mo. Las complejidades algo í micas de n² y nlogn ep esen an dos en oques di e en es en cuan o a cómo aumen an el núme o de ope aciones esenciales en un algo i mo a medida que c ece el amaño de la en ada, deno ado po n. Cuando se obse a el c ecimien o compu acional de es as complejidades, podemos no a una di e encia signi ica i a. A medida que aumen amos n, la complejidad n² c ece de mane a cuad á ica. Po o o lado, la complejidad nlogn c ece de mane a mucho más mode ada. Po lo an o, incluso pa a amaños de en ada pequeños, como 1024, la di e encia en el núme o de ope aciones esenciales en e algo i mos con complejidades n² y nlogn puede se no able, pasa íamos de 1048576 de ope aciones a 10240. Es o sub aya la impo ancia de es e algo i mo, especialmen e cuando se 2 abaja con conjun os de da os g andes, ya que el impac o en el iempo de ejecución puede se signi ica i o. 1.1.1 T ans o mada de Fou ie (FT) Las ans o madas son he amien as ma emá icas u ilizadas pa a ep esen a una señal po con eniencia ma emá ica y pa a ex ae in o mación ele an e. En e las di e en es ans o madas ma emá icas, la T ans o mada de Fou ie se ha con e ido en una he amien a ma emá ica pa a descompone cualquie unción en senos y cosenos. Pa a calcula es a ans o mada se necesi a p ocesa un núme o in ini o de alo es disc e os, lo que no es p ác ico pa a la mayo ía de aplicaciones. Po lo an o se desa olla una T ans o mada Disc e a de Fou ie (DFT) pa a ans o ma secuencias in ini as en secuencias ini as [4]. 1.1.2 T ans o mada Disc e a de Fou ie (DFT) La T ans o mada de Fou ie descompone señales empo ales complejas en componen es de ecuencia ácilmen e en endibles y iene una salida numé ica compleja que p ese a la ampli ud y la ase de la señal en conside ación. Aplicando la T ans o mada de Fou ie a una señal disc e a en el iempo, se ob iene una señal que es con inua y cíclica en el dominio de la ecuencia y se llama T ans o mada de Fou ie en Tiempo Disc e o (DTFT). La DFT se ob iene median e el mues eo del dominio de ecuencia de DTFT. La T ans o mada Disc e a de Fou ie (DFT) es una he amien a compu acional que pe mi e el cálculo de la ans o mada de Fou ie en una máquina digi al. La DFT eemplaza la in eg al in ini a de una señal con inua en el iempo x( ) po una suma ini a. Cualquie señal en iempo disc e o puede exp esa se como una se ie de Fou ie con N componen es de ecuencia [5]. 1.1.3 T ans o mada Rápida de Fou ie (FFT) La T ans o mada Rápida de Fou ie es un me odo sis emá ico de calcula la DFT y su in e sa, que lo hace de una o ma ápida [6]. La uncionalidad p incipal de la FFT es descompone los da os de en ada en unos más pequeños 2/N, sepa ando po las posiciones pa es e impa es de mane a ecu si a has a llega al base, una ez en es e, se aplican las ope aciones necesa ias pa a ob ene la ans o mada a cada uno de los 3 pasos in e medios, combinando es os has a llega al caso con odos los da os, en el que se ob iene la ans o mada. Es e abajo se a a cen a en hace una mejo a del endimien o de la T ans o mada Rápida de Fou ie (FFT, po sus siglas en inglés Fas Fou ie T ans o m) en el lenguaje C. La FFT es un algo i mo e icien e que compu a la T ans o mada de Fou ie de una secuencia disc e a de da os. Se a a abaja en la implemen ación ecu si a de és a sol en ando los cuellos de bo ella: uso de la lib e ía de complejos, la lec u a de da os y el uso de las unciones de senos y cosenos. Es os cuellos de bo ella se an a ob ene median e el uso de la he amien a de pe ilado pe más en conc e o usando epo & eco d . Pos e io men e se a a abaja con a ias CPUs, las pe enecien es a la máquina de p uebas con las que se ob engan los mejo es esul ados empo ales, después de hace una p ueba en e és as. Finamen e se a a p oba la implemen ación i e a i a, la FFT in-place, y se le an a aplica las mejo as ob enidas en la implemen ación ecu si a. Pos e io a la ob ención de es os da os, se a a ealiza una compa ación en e es as implemen aciones mejo adas, dando indicaciones de cuál de ellas usa según la disponibilidad de ecu sos que se engan. 1.2 Usos de la FFT Los dominios de uso de la FFT son muy ex ensos y di e sos y an eme giendo muchos usos nue os. En es a sección no se a a discu i de mane a ex ensa el uso de la FFT en cada caso, ya que la desc ipción de allada de es os usos jun o a sus espec i as implemen aciones y la base eo ica de es os es án en las e e ecias ci adas. Uno de los p incipales usos de la FFT es el análisis espec al de señales, ya que la p incipal uncionalidad de es e algo i mo es el paso del dominio del iempo eal al dominio de ecuencia. Analizando el espec o de señales de en ada en el dominio de ecuencia los pa áme os desconocidos en el dominio de iempo como la eciencia, la ampli ud y la ase de la señal pueden se obse ados y analizados [7]. 4 La FFT es un bloque uncional impo an e en los sis emas de comunicación mode nos, especí icamen e en aplicaciones de la mul iplexación po di isión de ecuencias o ogonales (OFDM po sus siglas en inglés) que es una écnica de ansmision que consis e en la mul iplexación de un conjun o de ondas po ado as de di e en es ecuencias en la que cada una anspo a in o mación. En e la que des acan el B oadcas ing digi al [8], la in e ope abilidad mundial pa a acceso po mic oondas [9] los es ánda es IEEE 802.11 [10], y Long-Te m e olu ion (T ansmision LTE) [11]. También es usada en imágenes médicas [12] pa a el il ado, análisis y econ ucción de imágenes. En e es os en a la compa ación de imagenes pa a comp oba si son simila es (image ma ching) en e los que es án el econicimien o acial, econocimien o del i is y econocimen o de la huella dac ila basado en la implemen ación de la co elación de ase (phase-only co ela ion (POC)) usando FFT bidimensionales [13]. Jun o a es as, hay o as muchas mane as de aplica la FFT mayo men e ealacionadas con a amien o de señales, ondas e imágenes de las que se pueden des aca ambién la comp esion de imagenes de ac ales, analisis de la ex u a de la supe icie, codi ica audio pa a la ecepción mo il y econocimien o acial en es dimensiones en e o as [13]. La FFT es un algo i mo ampliamen e u ilizado en la ac ualidad, con nume osos casos de uso, y po lo an o es impo an e consegui implemen aciones de es e que sean óp imas y ap o echen los ecu sos disponibles del disposi i o, an o como log a una implemen ación óp ima a ni el del lenguaje en el que se esc iba. 1.3 Mo i ación y Obje i os La azón pa a habe decidido abaja en la op imización de es e algo i mo son los casos de usos del algo i mo y la impo ancia de hace lo de mane a e icien e, ya que es e cumple con un ol indispensable en muchas aplicaciones como se ha mos ado en el apa ado 1.2. Los obje i os p incipales de es e abajo son iden i ica y analiza las limi aciones p esen es en las implemen aciones de la T ans o mada Rápida de Fou ie (FFT), con el 5 in de de ec a los posibles cuellos de bo ella que puedan a ec a su endimien o. A pa i de es a e aluación, se busca ealiza op imizaciones que pe mi an mejo a an o el iempo de ejecución como el endimien o gene al de la FFT. Además, se p e ende ap o echa al máximo los ecu sos disponibles en el disposi i o donde se ealiza el cómpu o, op imizando así la u ilización de la memo ia y la capacidad de p ocesamien o. 1.4 Plan de abajo El plan de abajo se es uc u a en a ias ases pa a abo da de mane a sis emá ica la op imización de la implemen ación de la T ans o mada Rápida de Fou ie (FFT). A con inuación se de alla el p oceso: 1. Iden i icación y análisis de cuellos de bo ella El abajo comienza con la búsqueda, implemen ación y análisis de los posibles cuellos de bo ella p esen es en la implemen ación de la FFT seleccionada. Es e p oceso implica un pe ilado del endimien o pa a iden i ica las á eas que equie en mejo as. Se busca en ende cómo es as limi aciones a ec an el endimien o gene al de la FFT y se p ocede a ealiza i e a i amen e op imizaciones en base a es os hallazgos. 2. Op imización basada en ecu sos del disposi i o Una ez que se han op imizado los cuellos de bo ella iden i icados, se pasa a la siguien e ase, que implica obse a y u iliza e icien emen e los ecu sos disponibles en la máquina donde se ealiza el cómpu o. Es o incluye el análisis compa a i o del uso de los dis in os ecu sos disponibles, como la memo ia y la capacidad de p ocesamien o, con el obje i o de acele a el p oceso de cómpu o de la FFT. 3. Explo ación de nue as implemen aciones y compa ación Cuando se alcance un po encial lími e en la mejo a de la implemen ación ac ual, se p ocede a busca nue as implemen aciones que puedan o ece un endimien o mejo ado. Se busca iden i ica al e na i as que puedan bene icia se de 6 las mejo as ealizadas en la implemen ación p e ia. Se lle a a cabo una compa a i a en e las dis in as implemen aciones pa a e alua su e icacia y endimien o. 4. Exposición de la implemen ación op imizada Finalmen e, se expone una implemen ación del algo i mo de FFT que se ha op imizado pa a log a el meno iempo de ejecución posible. Se documen an los hallazgos, las écnicas u ilizadas y los esul ados ob enidos du an e el p oceso de op imización. Es e plan de abajo p opo ciona una guía es uc u ada pa a abo da de mane a e ec i a la mejo a de endimien o de la FFT, con el obje i o de mejo a su ejecución en una a iedad de aplicaciones y en o nos compu acionales. 7 Capí ulo 2 - Ve sión básica de la Fas Fou ie T ans o m(FFT) En es e capí ulo se p esen a á la e sión. Es a implemen ación inicial de la T ans o mada Rápida de Fou ie (FFT) se basa en un algo i mo gene al ob enido de una uen e con iable 1 y u iliza la biblio eca complex.h de C pa a maneja núme os complejos. A pa i de es a base, se ha desa ollado una implemen ación inicial del algo i mo de FFT, que inco po a la lógica undamen al de es a ans o mación. Es e en oque p opo ciona una sólida base pa a explo a y comp ende los p incipios de la FFT y cons i uye un pun o de pa ida alioso pa a u u as mejo as y op imizaciones. Jun o a es o se a a expone como ejecu a y p oba las implemen aciones además de las p opiedades de la máquina en la que se an a ealiza las p uebas. 2.1 Funcionalidad En es e apa ado se a a mos a el p og ama comple o sob e el que se an a ealiza las p ime as p uebas. Es e cons a en la lógica de la FFT, una unción pa a la lec u a de los da os, o a pa a mos a los da os de en ada y los esul ados después de aplica la ans o mación y una comp obación de po encias de 2 (el algo i mo solo acep a en adas de es e ipo). 1 h ps://cp-algo i hms.com/algeb a/ .h ml 8 2.1.1 Main El lujo p incipal del p og ama se desa olla en la unción main como se mues a en la igu a 1, donde se lle a a cabo lo siguien e: Se e i ica que se haya p opo cionado un único a gumen o de línea de comandos, que ep esen e el amaño de la en ada y que es e sea una po encia de 2 con la unción is_powe _o _ wo(), es o es necesa io pa a iden i ica cuál a a se el a chi o de en ada que se a a lee . En caso con a io, se mues a un mensaje de e o y se e mina la ejecución del p og ama. Se ab e el a chi o que con iene los da os de en ada con la unción open() y se e i ica si se pudo ab i co ec amen e pa a con inua con el p og ama. Se ese a memo ia con la unción malloc() pa a almacena los da os de en ada y se inicializa con los da os leidos del a chi o median e la unción ini _complex_a ay(). Fig 1: FFT main 9 Se aplica la FFT a la señal y pos e io men e se libe a la memo ia ese ada con la unción ee(). La implemen ación pe mi e ambién, pa a comp oba los esul ados, imp imi po pan alla los da os leidos, an es y después de la ejecución del p og ama. Pa a ac i a es a uncionalidad, hab ía que descomen a las unciones p in _ ec o () de an es y después de la llamada a () 2.1.2 Lógica de la FFT En la unción () mos ada en la igu a 2, se lle a a cabo el p ocesamien o lógico undamen al de la T ans o mada Rápida de Fou ie (FFT). En es a unción, se inicia con el caso base de la ecu si idad cuando el amaño de la en ada es igual a 1. Pa a amaños mayo es, se di ide la en ada en dos pa es: las posiciones pa es (pe) y las posiciones impa es (po), las cuales se almacenan en el heap. Es as pa es se inicializan en un bucle y se ealizan llamadas ecu si as en cada una de ellas. Fig 2: Lógica FFT 16 En la igu a 9 se pueden obse a los esul ados ob enidos de la ejecución de la p ime a e sión de la FFT con 2²² (4194304) da os de en ada (pa e eal de la onda, la imagina ia se gene a sin lee la), que es el mayo amaño de da os sob e el que se an a hace las p uebas, ya que se ob iene un iempo de ejecución azonable pa a obse a los esul ados y los cuellos de bo ella. La mane a de consegui que la CPU ac úe al casi 100% de su capacidad ( ecuencia), es poniendo a linux en modo pe o mance. Todas las p uebas se an a ealiza en es e modo pa a ob ene esul ados sacando odo el po encial posible al p ocesado . Se e ambién en la cap u a, que se ha u ilizado unicamen e una CPU al 99,5% de su capacidad. Todos los iempos que se an a mos a a lo la go del abajo an a se habiendo comen ado las lineas de código que hacen que se mues en po pan alla an o los da os iniciales como el esul ado, ya que la en ada y la salida de da os gene an una Fig 9: Pe s a _básico con 2²² da os de en ada 17 sob eca ga innecesa ia en el p og ama. Es as unciones se an a u iliza pa a ealiza la comp obación de los esul ados exclusi amen e. En la igu a 10 se mues an los esul ados de iempo de ejecución o al ob enidos del pe s a pa a los da os de p ueba que p opo cionan más in o mación (los más g andes) pa a es a p ime a implemen ación de la FFT, se e una p og esión exponencial, lo cual es cohe en e, ya que cada ez que se duplican los da os a ejecu a , se duplican ambien las ejecuciones ealizadas po el p og ama. 3.2 Pe eco d & epo Es os dos comandos den o de pe son complemen a ios, ya que eco d g aba los e en os ocu idos du an e la ejecución del p og ama sob e el que se aplica, y el epo es capaz de mos a los esul ados ob enidos del g abado leyendo un a chi o llamado pe .da a, que es gene ado en el eco d. Es os son los comandos u ilizados pa a pode ealiza la lec u a de la ejecución del p og ama: Fig 10: Tiempo de ejecución del algo i mo _básico 18 $ sudo askse -c 0 pe eco d -g <nomb e_salida> <po encia_de_2> $ sudo pe epo -g En la igu a 11 se mues an los esul ados ob enidos al ejecu a es os dos comandos pa a el algo i mo _básico con 2²² da os de en ada. El 74,54% del iempo de ejecución se ha empleado en la unción main. De es e salen odas las demás pa es del p og ama. Fig 11: Reco d & epo _básico 19 En o den de mayo a meno po cen aje de iempo de ejecución, el p ime o que des aca es la p opia unción con un 49,21% de la cual solo es á ejecu ado el 34,31% causado po el g an núme o de llamadas ecu si as. Den o de es a unción es á oda la lógica del p og ama, en las que cabe des aca las mul iplicaciones de complejos __muldc3 13,42% en el que la g an mayo ía 11,48% es á ejecu ado sob e sí mismo, ambién el almacenamien o malloc 1,51% y la libe ación _in _ ee 2,23% y inalmen e las ope aciones de cosenos __cos_ ma 1,72% y senos __sin_ ma 1,67%. El siguien e a des aca , es la lec u a de los da os, compues a de __isoc99_ scan con un 23,36%, la cual llama a __ scan _in e nal con un 20,67%, unción que no llama a o as. Añadido a es o enemos __GI_____s o _l_in e nal con un 11,80% y s _ o_mpn.cons p op.0 con un 4,66% que se enca ga de la aducción de s ings a loa s y debido a que es amos leyendo los da os de un iche o egula . Fue a de es as dos unciones ambién caben des aca los allos de página que se han p oducido po la inmensa can idad de da os gene ados con la ecu si idad del algo i mo y la lec u a de los da os iniciales, alcanzando un 2,47%. Lo que se puede obse a de es a p ime a implemen ación es que hay dos p incipales posibles cuellos de bo ella que son la mul iplicación de los complejos den o de la unción y la lec u a de los da os de la memo ia, sumando en e ellos el 36,78% den o del 74,54% que ocupa el p og ama. Es deci , más del 50% de la ejecución. Po lo an o en los capí ulos siguien es se a a p ocede a abaja pa a educi es os alo es. 20 Capí ulo 4 - Cambio de <complex.h> a s uc {} complex En la p ime a oma de esul ados, se obse ó un posible cuello de bo ella en las mul iplicaciones ealizadas en la unción p incipal del p og ama (). Una posible solución a es e p oblema es cambia el uso de los complejos p opo cionados po la lib e ía complex.h a una es uc u a con dos núme os lo an es uno pa a la pa e eal y o o pa a la imagina ia (s uc { loa Re; loa Im;} complex) y luego sus i ui las mul iplicaciones de complejos de lib e ía po una mul iplicación de los complejos de mane a “manual”. Es a pa e del código se ha ob enido de una implemen ación de la FFT de Mladen Vic o Wicke hause de su lib o Ma hema ics o Mul imedia [14], como se mues a en la igu a 13. En la igu a 12 se mues a como se hacían con complex.h. En es as dos implemen aciones se ealizan las mismas ope aciones, pe o en la igu a 13 se hacen de mane a manual las mul iplicaciones de complejos. Fig 12: Ope aciones _básico Fig 13: Ope aciones _complex_s uc 21 Fig 14: Pe s a _complex_s uc Fig 15: Reco d & epo _complex_s uc 22 En las igu as 14 y 15 se en los esul ados de ejecu a el p og ama con la nue a es uc u a pa a los complejos ealizando las mul iplicaciones de mane a manual, pa a 2²² da os de en ada. Re isando la cap u a del pe emos que ya no se encuen a el __muldc3 y es o es cohe en e, ya que se han cambiado las mul iplicaciones de complejos de la lib e ía complex.h po las na i as de C, se puede e un cambio debido a es o en la pa e que co esponde a la ejecución de la unción , an es ocupaba un 49.34% de la que un 34.31%, que co esponde a un 69,53% de la ejecución de la unción se ejecu aba la . En es a nue a implemen ación se e un cambio, aho a la ejecución de es de 42.87% de la que un 39.06%, que co esponde a un 91,11% de la ejecución de la unción se ejecu a la , lo que nos indica que las mul iplicaciones de los complejos es án ejecu adas aquí. El po cen aje es an e como se expuso en el capí ulo an e io , son de senos, cosenos, malloc, ee y allos de página. Con es e cambio se ha conseguido educi el iempo de ejecución, como se espe aba. Sin emba go la mejo a no podia se sus ancial en educción iempo, ya que el p oblema __muldc3, solo ocupaba un 13,42% y no se podía elimina comple amen e po que las mul iplicaciones son necesa ias pa a la co ec a ejecución del algo i mo. Es a es la compa ación de los esul ados ob enidos, se ha pasado de 1,048s a 0,951s. Y podemos calcula la acele ación de la siguien e mane a: Speedup=𝑇𝑖𝑒𝑚𝑝𝑜𝑖𝑛𝑖𝑐𝑖𝑎𝑙 𝑇𝑖𝑒𝑚𝑝𝑜𝑓𝑖𝑛𝑎𝑙 Speedup=1,048 0,951= 1,102 una acele ación del 10,2%. 23 Después de habe is o como calcula la acele ación en e las di e en es e siones del algo i mo, con los da os ob enidos se han c eado es as ablas pa a mos a la in o mación más ele an e (en la documen ación del p oyec o se encuen an odas las cap u as de las que se han sacado los da os), se e que la acele ación media desde 2¹⁵ en adas es de 1.151, un 15,1%. Fig 16: Reco d & epo _complex_s uc Tabla 1: Acele ación _básico s _complex_s uc 24 Capí ulo 5 - Cambio de scan a ead En los dos capí ulos an e io es se obse a un cuello de bo ella que asciende a un 44,18% pa a la ejecución de la lec u a de los da os dado po : __isoc99_ scan con un 24,51% que con iene a __ scan _in e nal con un 22,52%, sumado a __GI_____s o _l_in e nal con un 13,52% y s _ o_mpn.cons p op.0 con un 5,94%. Es os po cen ajes de ejecución aún con la can idad de da os omados (máximo 2²²) llama su icien e la a ención como pa a in en a busca un al e na i a mejo . En es os casos an e io es se hace con scan , que a leyendo uno a uno los da os de en ada, haciendo una llamada al sis ema en cada lec u a uni a ia, lo que causa que es a implemen ación no sea óp ima. La mejo a ealizada u iliza ead pa a pode ealiza una única llamada al sis ema y lee odos los da os a la ez. Es a mejo a equie e de una se ie de cambios en los da os de en ada/casos de p ueba, ya que ead ac úa en un solo bloque, pe o necesi a lee los da os en bina io. Pa a es o se han c eado unos p og amas pa a pode pasa los da os iniciales a bina io ( x _ o_bin.c) y o o pa a lee los da os ( ead_bin). Es e úl imo se implemen a en cada p og ama sus i uyendo el an e io modo de lec u a. 25 Fig 17: Pe s a _ ead Fig 18: Reco d & epo _ ead 32 A pa i de los esul ados ob enidos en es a i e ación del código mos ados en la igu a 23 y la abla 3, cabe des aca , que casi odos los p oblemas de la implemen ación han sido esuel os, a al a de dos pun os cla e, los allos de página y la ese a de memo ia median e malloc. Los allos de página se empiezan a obse a a pa i de en adas de da os de 2¹⁴ (16384) en adas, es os suponen un po cen aje al o en el cómpu o o al de la implemen ación. La elación en el cómpu o global asciende al 7,17%, lo que de pode elimina lo supond ía una buena mejo a a la implemen ación. Po o a pa e, el uso de malloc y ee p oducen ambién una sob eca ga en la implemen ación, pe o son indispensables pa a su co ec o uncionamien o. Si se p escindie a de ellos (así e a una implemen ación base an e io a la p ime a mos ada en el documen o), a pa i de casos de en ada supe io es a 2¹⁸ se p oduci ían allos de segmen ación. Tabla 3: Acele ación _ ead s _sincos 33 Capí ulo 7 - Pa alelización con hilos Una ez esuel os los p incipales cuellos de bo ella de la implemen ación, se p opone una nue a mejo a, que consis e en u iliza más ecu sos de la máquina en la que se abaja, en conc e o las CPUs. La mane a de ap o echa las dis in as CPUs de la máquina de abajo es a a és de la c eación de dis in os hilos pa a in en a que la e sión pa alelizada del algo i mo sea más ápida. 7.1 Mejo a a pa alelización con 2 hilos En es e apa ado se an a mos a los cambios necesa ios en la implemen ación del algo i mo pa a ejecu a lo en 2 hilos, cada uno en un co e. Es e apa ado es el que más cambios a ni el de código a a necesi a , po la mane a de de ini los hilos en C. 7.1.1 Función p incipal () Has a la c eación de la onda que gua da los casos de p ueba el código sigue de la misma mane a, pe o, pa a pode hace llamadas ecu si as habiendo c eado los hilos, hace al a cambia la cabece a pa a in oduci le los a gumen os necesa ios al hilo. ypede s uc {complex *p; in size; in log2n;} h d_a g ; Es os a gumen os del hilo, son los mismos que enía la cabece a en las o as implemen aciones del algo i mo, pe o ag upados en una es uc u a que se inicializa después de la c eación de la onda en el main. 34 Una ez inicializada la es uc u a, se c ea el p ime hilo que ejecu a á la unción p incipal. Pa a es o es necesa io selecciona la CPU en la que se a a ejecu a , con la unción CPU_SET() en la que el p ime a gumen o es un en e o que selecciona el núme o de la CPU en el que se a a ejecu a el hilo, in oduciendo es e alo en cpuse 0. Pos e io men e se c ea el hilo llamando a la unción con los a gumen os p e iamen e c eados. La unción se a ini y que se enca ga de hace que se mig e el hilo a la CPU seleccionada y inalmen e el join pa a espe a a que acabe la ejecución del hilo. Fig 24: C eación del p ime hilo 35 En la igu a 25 se mues a como se c ea el segundo hilo, como se a a p oba con 2, sólo se c ea si el amaño del la onda es igual al amaño de la onda de en ada, es deci el caso en el que se hace la llamada desde el main y no en las llamadas ecu si as. El es o del código sigue igual has a el pun o en el que se ha ían las llamadas ecu si as, después de la sepa ación de la onda en la pa e de las posiciones pa es e impa es. Es e segundo hilo se c ea de la misma mane a que el p ime o del main, pe o pa a selecciona una cpu dis in a, se hace uso de un con ado como a iable global que pe mi i á la expansión a más CPUs. Finalmen e se espe a a que acabe la ejecución del hilo con el join. s a ic in cpu_coun e = 1; Se inicializa el con ado a 1 pa a no ene lo que i e a en la c eación del p ime hilo. Fig 25: Inicialización del segundo hilo 36 Po o a pa e, en el es o de casos en los que el amaño de la onda es meno al de la onda de en ada, se ealiza la ecu sión de la misma mane a que se hacía en el es o de implemen aciones, pe o c eando la es uc u a con los a gumen os de la unción, como se mues a en la igu a 26. Se ha comp obado que los esul ados de ejecu a es a implemen ación con 2 hilos son los mismos que en las an e io es implemen aciones. 7.2 Tipos de CPU y compa ación en uso Como se expuso en el capí ulo 2 la máquina en la que se desa ollan las p uebas con iene dos ipos dis in os de CPU, los e icien y los pe o mance, y se exp esó que en odas las p uebas se iban a u iliza los de ipo pe o mance, ya que llegan a mayo ecuencia. Aquí se a a expone una compa a i a en e los dis in os co es 7.2.1 Pe o mance CPUs en el mismo co e En es e apa ado se a a expone la mejo a empo al que supone ejecu a es a implemen ación en dos pe o mance CPUs den o del mismo co e (CPUs 0 y 1). Fig 26: Recu si idad con los hilos c eados 37 7.2.2 Pe o mance CPUs en el di e en e co e En es e apa ado se a a expone la mejo a empo al que supone ejecu a es a implemen ación en dos pe o mance CPUs en di e en es co es (CPUs 0 y 2). Fig 27: Pe s a _2 h eads en el mismo pe o mance co e Fig 28: Pe s a _2 h eads en el di e en e pe o mance co e 38 7.2.3 E icien CPUs en el mismo clus e En es e apa ado se a a expone la mejo a empo al que supone ejecu a es a implemen ación en dos pe o mance CPUs den o del mismo clus e (CPUs 12 y 13). Fig 29: Pe s a _2 h eads en el mismo e icien co e 39 7.2.4 E icien CPUs en el di e en e clus e En es e apa ado se a a expone la mejo a empo al que supone ejecu a es a implemen ación en dos pe o mance CPUs en di e en es clus e s (CPUs 12 y 16). 7.2.5 Análisis de esul ados Una ez p obados odos los casos, podemos obse a cla amen e cuál es la mejo mane a de ealiza el mul i h eading. Una cla a di e encia espec o a los esul ados de los capí ulos an e io es, es el inc emen o que se e en las CPUs u ilizadas, que pasan de 1 a casi 2, lo que nos mues a que e ec i amen e, se es á ejecu ando en di e en es CPUs, aunque en ningún caso llega a 2 es e alo . El p ime desca e es la ejecución en co es E icien que al ene meno ecuencia de eloj, iba a se un esul ado na u al ob ene peo es iempos de ejecución. Cabe des aca que el uso de dos co es de es e ipo pa a hace mul i h eading independien emen e de es a en el mismo clus e o no, ha supues o incluso un Fig 30: Pe s a _2 h eads en el di e en e e icien co e 40 empeo amien o espec o a la úl ima implemen ación en un único hilo, habiendo sido hecha es a ejecución en un co e Pe o mance. El o o desca e obse ando los esul ados, es la ejecución en dos CPUs Pe o mance den o del mismo co e, es o es debido a como es á es uc u ada la mic oa qui ec u a del p ocesado , que hace que es as dos CPUs compa an odos los ecu sos del co e, y po lo an o compi en en e ellas pa a u iliza los ecu sos, no ap o echando bien la pa alelización del código. Finalmen e, con la que se ob iene una conside able mejo a es usando las CPUs de ipo Pe o mance en co es dis in os, ya que se u ilizan las CPUs más po en es del p ocesado y no compi en en e ellas po los ecu sos. Fig 31: Resul ados empo ales _2 h eads 41 T as la ob ención de los esul ados pa a los amaños de en ada más ele an es mos ados en la igu a 31 y la abla 4 se obse a una buena mejo a empo al en odos los casos p obados. Es os esul ados son buenos, al habe enido una mejo a en odas las p uebas, pe o cabe des aca , que al u iliza el doble de ecu sos, se espe a una mejo a más signi ica i a que una media del 45,6% de mejo a. Tabla 4: Acele ación _sincos s _2 h eads 48 En es e caso se obse a que los cambios de con ex o han aumen ado has a los 214 cuando con 4 hilos e an solo 30. También hay que ene en cuen a que el p ocesado de la máquina de p uebas no cuen a con los su icien es co es de ipo Pe o mance pa a cub i los 8 hilos, po lo que se en con ado es cpu_a om, que solo es án p esen es en las CPUs de ipo E icien . Nue amen e se obse a un aumen o en los allos de página ambién p oducido po el uso de más CPUs. Con es os da os omados, es cohe en e que no haya habido una mejo a signi ica i a en e es a implemen ación y la de 4 hilos, en conc e o ha habido una mejo a empo al de una milésima, lo que en la p ác ica no supone ninguna mejo a. Fig 36: Pe s a _8 h eads 49 Aquí se obse a como se ha hecho uso de las 8 CPUs, CPU1( ojo), CPU3(ama illo), CPU5( e de), CPU7(azul), CPU9(magen a), CPU11(beige), CPU13( e de cla o) y CPU15(azul oscu o). Se desca a el uso de es a mejo a debido a los esul ados ob enidos, en los que la mejo a empo al es p ác icamen e nula en compa ación a los ecu sos u ilizados en su ejecución. Fig 37: P ocesado ejecu ando _8 h eads 50 Capí ulo 8 - Solución de las ese as de memo ia y los allos de página usando la in-place En es e capí ulo se a a mos a una nue a implemen ación de la , en la que po la mane a de ejecu a se, solo equie e de una ese a de memo ia pa a la onda, ya que se basa en eo dena los casos de una mane a conc e a pa a deja de se una implemen ación ecu si a. Es o hace que se deje de ene que sepa a la onda en o as más pequeñas con las posiciones pa es e impa es pa a no ene que ese a la memo ia en es os casos. El abaja en la onda de en ada p oduce que es os da os se pie dan después de ealiza la ans o mada. No se a a en a mucho en el po que unciona de es a mane a, la implemen ación pe o se puede encon a en es e a ículo 6 con su espec i a explicación de allada. Es a implemen ación nos ayuda a compa a la implemen ación inal ob enida con una que a a pe de la ca ga de malloc, ee y g an pa e de los allos de página p o ocados po la c eación de an as ondas in e medias. Todas las mejo as ealizadas en la de la p ime a implemen ación son aplicables a es a ambién excep uando la c eación de dis in os hilos. 8.1 Implemen ación básica de la in-place En es e apa ado se a a mos a una implemen ación de la in-place, sin aplica las mejo as ob enidas en los capí ulos an e io es pa a pode hace pos e io men e una compa ación con una implemen ación con odas las mejo as. Se ha comp obado que los esul ados de ejecu a es a implemen ación básica de la in-place son los mismos que en las implemen aciones an e io es. 6 h ps://cp-algo i hms.com/algeb a/ .h ml 51 En la igu a 38 se mues a la implemen ación de la nue a unción , en la que se obse a que no hay inicializaciones de memo ia pa a c ea las ondas de pa es e impa es como en la implemen ación ecu si a. En es e caso se op a po una eo denación de los da os de en ada pa a que queden como si se hubie a hecho la ecu sión a a és de in e cambios de posiciones, jun o a una ma e a ingeniosa de ealiza las ope aciones con los da os a a es de los es bucles o que ambién imi an la ecu sión. Fig 38: Lógica _in-place básica 52 En la igu a 39 se obse an los esul ados ob enidos de la ejecución del pe s a a es a implemen ación básica de la in-place. La g an di e encia de es a implemen ación, como se había adelan ado al comienzo del capí ulo, son los pocos allos de página que se p oducen, debido a que se gua da la onda solo una ez. Se han pasado de unos 40000 allos de página a 8000 espec o a las implemen aciones an e io es sin hilos. Es o jun o a no ejecu a an os malloc y ee, hace que la implemencación básica sea bas an e más ápida que la básica pasando de 1,047s a 0,794s. Y podemos calcula la acele ación de la siguien e mane a: Speedup=1,048 0,794= 1,318 una acele ación del 31,8% Fig 39: Pe s a _in-place_básico 53 En la igu a 40 se mues an los esul ados del pe eco d & epo , en los que se obse an los mismos p oblemas que en la ejecución de la básica. G an pa e del cómpu o gas ado en lee los da os, p oducido po el scan , mucha pa e de la ejecución gas ada en en las mul iplicaciones de la lib e ía de complejos, los allos de página es án p esen es pe o no suponen an o iempo en elación con lo demás y no se obse a las ope aciones de senos y cosenos po la misma azón. Fig 40: Reco d & epo _in-place_básico 54 8.1.1 Compa ación ecu si a e in-place básicas A con inuación se a a mos a una compa ación con las en adas de da os más ele an es en e la p ime a implemen ació de la y es a de la in-place. En es os esul ados empo ales se puede obse a una mejo a gene al en la mayo ía de casos, haciendose más no able en los casos más g andes, p oducido po la eliminación de los allos de página y las cons an es ese as de memo ia que ya no Fig 41: Resul ados empo ales _in-place_básico Table 6: Acele ación _básico s _in-place_básico 55 es án p esen es en es a implemen ación y en los casos más g andes de la implemen ación ecu si a aumen an mucho es os. 8.2 Implemen ación mejo ada de la in-place En es e apa ado se an a mos a los esul ados de aplica odas las mejo as ob enidas en las implemen aciones de la sin aplica las mejo as de hilos. El esumen de los cambios se ía: Cambia el uso de los complejos de la lib e ía de C a una es uc u a de da os con pa e eal e imagina ia, cambiando las ope aciones pa a que se ealicen co ec amen e, de la misma mane a que en la implemen ación ecu si a. El cambio la mane a de lee dos da os de scan a ead, haciendo la lec u a de los da os desde a chi os bina ios, es e cambio es igual que en la implemen ación ecu si a de la , den o de la unción ini _complex_a ay. Y inalmen e deja de calcula los senos y los cosenos en cada i e ación, dejando es os alo es p ecalculados en un a ay bidimensional y accediendo a ellos cuando se necesi en, es a pa e ambién es igual que en la implemen ación ecu si a. Se ha comp obado los esul ados de ejecu a es a implemen ación con las mejo as de la in-place en la que se ob ienen los mismos esul ados que en las implemen aciones an e io es. 56 En la igu a 42 se mues an los esul ados empo ales ob enidos con la ejecución del pe s a , aplicando odas las mejo as ealizadas pa a la . Los esul ados son bas an e sa is ac o ios pasando de 0,794s a 0,355s y aquí se mues a la acele ación ob enida as las mejo as: Speedup=0,794 0,355= 2,236 una acele ación del 123,6%. Fig 42: Pe s a _in-place_mejo ado 57 En la igu a 43 se mues a la ejecución del pe eco d & epo , han desapa ecido odos los p oblemas que se ob enían de la an e io implemen ación sin las mejo as, es ando p ác icamen e de mane a in eg a el cómpu o den o de la unción p incipal . En compa ación con la implemen ación de la ecu si a, se e que los allos de página se han educido has a un 2,5% de la ejecución, mien as que en la ecu si a alcanza on en la mejo implemen ación sin hilos un 7,17%. Po o a pa e, las ejecuciones de malloc y ee se han educido has a casi elimina se, ya ni siquie a apa ecen en el pe , po lo an o su po cen aje de ejecución no llega al 0,21%. Es e es un esul ado azonable ya que solo se llama a es as unciones una ez pa a c ea la onda inicial y luego libe a la memo ia. Fig 43: Reco d & epo _in-place_mejo ado 64 la implemen ación pa a consegui educi los. En es e caso, se obse ó el ac o limi an e de los allos de página jun o a las ese as y libe aciones de memo ia y se u o que busca una implemen ación di e en e pa a elimina los, median e la in- place. A la cual se le han podido aplica las mejo as ealizadas en la implemen ación ecu si a y así mejo a su endimien o. T as la ealización de es e abajo se puede conclui con habe ob enido dos implemen aciones con una mejo a de endimien o no able, ú iles en dis in os casos de uso. La p ime a implemen ación a di igida pa a máquinas de abajo con a ias CPUs, es a es la implemen ación _ h eads, que es capaz de di idi la ca ga de abajo en e las dis in as CPUs del p ocesado pa a ob ene los mejo es esul ados empo ales posibles. Es a implemen ación es escalable pa a p ocesado es más po en es que la máquina de p uebas u ilizada, ealizando p e iamen e un es udio de la máquina en la que se a a ejecu a pa a saca le el mayo po encial. Po o a pa e es á la implemen ación _in-place que sol en a los allos de página y no u iliza an as ese as de memo ia, pe o solo se ejecu a en una CPU po lo que puede se empo almen e peo dependiendo de la máquina de p uebas, como es el caso de la máquina en la que se ha ealizado es e abajo. La p ime a implemen ación con aba con una complejidad nlogn que es a lo máximo que se puede op a pa a ealiza es a ans o mada, siendo una mejo a de la T ans o mada Disc e a de Fou ie po ue za b u a con una complejidad de n². Se puede a i ma que no solo bas a con ob ene una complejidad mejo pa a que el un algo i mo se ejecu e de la mane a más ápida posible, sino que ambién hay que ap o echa los ecu sos disponibles an o en la máquina como del lenguaje seleccionado, ya que es os pueden gene a una mejo a sus ancial. T abajo Fu u o En es e abajo, como en odos los abajos de in es igación, se deja aún cabida a la mejo a, pa a que en un u u o se pueda segui abajando en es e p oyec o. Po su complejidad y al a de ecu sos, no se han podido llega a ealiza den o de es e, pe o aquí se exponen las posibles líneas pa a segui abajando: 65 En es e p oyec o se ha op ado po da unas implemen aciones que sean ácilmen e po ables en e dis in os disposi i os median e el uso del lenguaje C, que puede se compilado en cualquie máquina. Pe o, pa a ob ene unos esul ados po encialmen e mejo es, se pod ía abaja con ex ensiones mul imedia que sopo e el disposi i o de p uebas. Es e es un buen pun o en el que con inua el abajo debido a la ca ga que iene el algo i mo en p ocesa ope aciones epe idamen e, que se pod ían ap o echa de la ejecución en pa alelo que p opo cionan es as ex ensiones [Ex ensiones Mul imedia al Lenguaje Máquina en P ocesado es de P opósi o Gene al. En ique F. To es y Víc o Viñals]. O o pun o que se pod ía in en a sol en a pa a no ene que cambia a la implemen ación in-place, se ía busca alguna mane a de ae los da os de memo ia an es de se necesi ados po el p og ama pa a in en a elimina o educi los allos de página. Es o da ía una implemen ación mul ihilo mucho más e icien e. 66 BIBLIOGRAFÍA 1: Sa ibulu , L., Ahme , T. E. K. E., & TÜMAY, M. “Fundamen als and li e a u e e iew o Fou ie ans o m in powe quali y issues. Jou nal o Elec ical and Elec onics Enginee ing Resea ch”, 5(1), 9-22. 2013 2: Heideman MT, Johnson DH, Bu us CS, “ Gauss and he his o y o he as Fou ie ans o m, A chi e o His o y o Exac Sciences”. A ch. His . Exac Sci. 34(3):265-277. 1985 3: James W. Cooley and John W. Tukey, “An Algo i hm o he Machine Calcula ion o Complex Fou ie Se ies” p 297-301 4: Ann Ma ia John, Ki an Khanna, Ri ika R P asad, Lakshmi G Pillai “A Re iew on Applica ion o Fou ie T ans o m in Image Res o a ion”. Page 389 5: Kuo SM, Lee BH. “Real- ime digi al signal p ocessing implemen a ions applica ions and expe imen s wi h he TMS320C55x”. John Wiley & Sons, Inc.2001, pp 173-217 6: jain, Anil K., “Fundamen als o digi al image p ocessing”, 1989 7: A.V. Oppenheim, R.W. Scha e , J.R. Buck e al., Disc e e-Time Signal P ocessing ol2 8: Richa d M. Jiang. "An a ea-e icien FFT a chi ec u e o OFDM digi al ideo b oadcas ing" 9: Chih-Peng Fan, Mau-Shih Lee, Guo-An SuA. "Low Mul iplie and Mul iplica ion Cos s 256-poin FFT Implemen a ion wi h Simpli ied Radix-24 SDF A chi ec u e" 10: Taesang Cho, Hanho Lee, Jounsup Pa k, Chulgyun Pa k "A high-speed low- complexi y modi ied adix-25 FFT p ocesso o gigabi WPAN applica ions" 11: Sheng-Yeng, Kai-Ting, Chao-Ming, Yuan-Hao "Ene gy-e icien 128 2048/1536-poin FFT p ocesso wi h esou ce block mapping o 3GPP-LTE sys em" 12: Mohammad Nazmul Haque, Mohammad Sho i Uddin, M. Abdullah-Al-Wadud, Yoojin Chung "Fas econs uc ion echnique o medical images using g aphics p ocessing uni " 13: K.R. Rao , D.N. Kim , J.-J. Hwang Fas Fou ie T ans o m - Algo i hms and Applica ions 14: , h ps://www.ma h.wus l.edu/~ ic o /m mm/ ou ie / .c, 67 APÉNDICES Apéndice A - Funciones auxilia es Pa a el co ec o uncionamien o y ejecución de la FFT son necesa ias una se ie de unciones auxilia es u ilizadas en el main pa a comp oba la en ada e inicializa los da os. Se an a expone en o den de uso en el main. La unción is_powe _o _ wo ealiza una comp obación pa a de e mina si un núme o dado es una po encia de 2. Es a unción ecibe un en e o n como a gumen o y de uel e un alo booleano, e dade o si n es una po encia de 2 y also en caso con a io. En el e u n se obse a la logica pa a comp oba e icien emen e si el alo de en ada es po encia de 2. Es o se log a median e el uso de una ope ación de bi s. Se compa a n con n - 1 u ilizando el ope ado & (AND bi a bi ). Si el esul ado de es a ope ación es 0 y n es mayo que 0, en onces n iene exac amen e un bi es ablecido, lo que signi ica que es una po encia de 2. La unción ini _complex_a ay se enca ga de inicializa un a ay de núme os complejos a pa i de los da os leídos desde un a chi o. Recibe es a gumen os: wa e que es el a ay de núme os complejos que se a a inicializa , size que es un pun e o a un en e o que indica el amaño del a ay, y ile que es el pun e o al a chi o del cual se lee án los da os. 68 Den o de la unción, se u iliza un bucle o pa a i e a sob e cada elemen o del a ay wa e. En cada i e ación, se u iliza la unción scan () pa a lee un núme o de pun o lo an e del a chi o ile y se gua da en la a iable num. Luego, se asigna es e alo a la posición co espondien e del a ay wa e, con i iéndolo en un núme o complejo con pa e imagina ia ce o, u ilizando la mac o I de la biblio eca es ánda de C. La unción p in _ ec o imp ime en la consola los elemen os de un ec o de núme os complejos jun o con un í ulo que desc ibe su con enido y su dimensión. Toma es a gumen os: i le pa a el í ulo del ec o , p pa a el ec o en sí y n pa a su dimensión. U iliza un bucle pa a eco e cada elemen o del ec o e imp ime su pa e eal (c eal()) e imagina ia (cimag()) en o ma o de núme o complejo. Es a unción acili a la isualización del con enido del ec o , lo que puede se ú il pa a en ende y depu a el código que abaja con núme os complejos. 69 Apéndice B - Ob ención de g á icas y ablas u ilizadas Pa a la ob ención de las g á icas y la ablas, se ha u ilizado un noo ebook en Google Colab con las lib e ías de py hon pandas y ma plo lib.pyplo . Ambas han sido gene adas con los mismos da os que han sido ecolec ados de las ejecuciones del pe s a de cada una de las implemen aciones y se han in oducido los da os en un Da aF ame de pandas de la siguien e mane a: Aquí queda c eada la es uc u a en la que se an a in oduci los da os, de iniendo los amaños a los que se an a e e i los da os ob enidos y dejando lib e una pa e pa a pone los iempos de las implemen eciones. De es a mane a se han in oducido los da os de cada una de las i e aciones del código. Pos e io men e pa a c ea la g a ica y abla co espondien e, hab ía que ejecu a los bloques de código que con u ie an los da os que se an a que e mos a y pos e io men e ejecu a las c eaciones de la g á ica y la abla. 70 Es e es el código que gene a las g á icas en el que se ecomo se de ine el amaño de la salida, como e o e las es uc u as con los da os empo ales c eados y como inalmen e se c ea la abla con odos sus a ibu os. Es e es el código que gene a las ablas con las acele aciones, en el que se c ea un pandas Da aF ame con la es uc u a de los iempos y los amaños de en ada, pos e io men e se gene a una nue a en ada llamada acele ación que es la di isión en e las dos implemen aciones sob e las que se quie e calcula la acele ación. Finalmen e se seleccionan las columnas que que emos ob ene en la salida, adecuando la nue a columna acele a ion al o ma o de do os los da os y se mues a la abla de salida. 1 In oduc ion The Disc e e Fou ie T ans o m (DFT) is based on Fou ie analysis in oduced by Jean Bap is e Joseph Fou ie , a F ench scien is bo n in 1768, o desc ibe any pe iodic signal ega dless o i s complexi y using ha monic se ies [1]. I makes use o he p ope ies o igonome ic symme y and he pe iodici y o he widdle ac o . 𝑊𝑁 (𝑘𝑁 2)= −𝑊𝑁 (𝑘) (Symme y p ope y) 𝑊𝑁 (𝑘+𝑁)= −𝑊𝑁 (𝑘) (Pe iodici y p ope y) These p ope ies we e known long be o e digi al compu a ion. Heideman e al. [2] aced he i s appea ance o he FFT back o Gauss in 1805. Gauss de eloped an algo i hm o compu e he DFT equi alen o he Cooley-Tukey algo i hm. Howe e , despi e being published o o e 150 yea s, i did no gain signi icance un il he publica ion o he Cooley-Tukey pape in 1965 [3]. I was p esen ed as an e icien di ide-and-conque algo i hm o compu ing he DFT, esul ing in a complexi y o nlogn, which is wha makes his algo i hm so in e es ing. The algo i hmic complexi ies o n² and nlogn ep esen wo di e en app oaches o how he numbe o essen ial ope a ions in an algo i hm inc eases as he inpu size, deno ed by n, g ows. When obse ing he compu a ional g ow h o hese complexi ies, we can no ice a signi ican di e ence. As we inc ease n, he complexi y n² g ows quad a ically. On he o he hand, he complexi y nlogn g ows much mo e mode a ely. The e o e, e en o small inpu sizes, such as 1024, he di e ence in he numbe o essen ial ope a ions be ween algo i hms wi h n² and nlogn complexi ies can be no able, going om 1048576 ope a ions o 10240. This unde sco es he impo ance o his algo i hm, especially when wo king wi h la ge da ase s, as he impac on execu ion ime can be signi ican . 2 Fou ie T ans o m (FT) T ans o ms a e ma hema ical ools used o ep esen a signal o ma hema ical con enience and o ex ac ele an in o ma ion. Among he a ious ma hema ical ans o ms, he Fou ie T ans o m has become a c ucial ool o decomposing any unc ion in o sines and cosines. To calcula e his ans o m, an in ini e numbe o disc e e alues mus be p ocessed, which is imp ac ical o mos applica ions. The e o e, he Disc e e Fou ie T ans o m (DFT) was de eloped o ans o m in ini e sequences in o ini e sequences [4]. Disc e e Fou ie T ans o m (DFT) The Fou ie T ans o m decomposes complex empo al signals in o easily unde s andable equency componen s and yields a complex nume ical ou pu ha p ese es he ampli ude and phase o he signal in ques ion. By applying he Fou ie T ans o m o a disc e e- ime signal, a signal ha is con inuous and cyclical in he equency domain is ob ained, called he Disc e e-Time Fou ie T ans o m (DTFT). The DFT is ob ained by sampling he equency domain o he DTFT. The Disc e e Fou ie T ans o m (DFT) is a compu a ional ool ha allows he calcula ion o he Fou ie ans o m on a digi al machine. The DFT eplaces he in ini e in eg al o a con inuous- ime signal x( ) wi h a ini e sum. Any disc e e- ime signal can be exp essed as a Fou ie se ies wi h N equency componen s [5]. Fas Fou ie T ans o m (FFT) The Fas Fou ie T ans o m is a sys ema ic me hod o quickly calcula ing he DFT and i s in e se [6]. The p ima y unc ionali y o he FFT is o decompose he inpu da a in o smalle 2/N pa s, sepa a ing hem by e en and odd posi ions ecu si ely un il eaching he base case. Once a his poin , he necessa y ope a ions a e applied o ob ain he ans o m a each in e media e s ep, combining hese s eps un il eaching he case wi h all he da a, a which he ans o m is ob ained. This wo k will ocus on imp o ing he pe o mance o he FFT in he C language. The FFT is an e icien algo i hm ha compu es he Fou ie T ans o m o a disc e e da a sequence. 3 The wo k will add ess he ecu si e implemen a ion o he FFT by esol ing bo lenecks: he use o he complex lib a y, da a eading, and he use o sine and cosine unc ions. These bo lenecks will be iden i ied using he pe p o iling ool, speci ically using he epo and eco d commands. Subsequen ly, he implemen a ion will be es ed on mul iple CPUs om he es machine o de e mine which yields he bes ime esul s a e conduc ing a compa a i e es . Finally, he i e a i e implemen a ion, he in-place FFT, will be es ed, and he imp o emen s ob ained in he ecu si e implemen a ion will be applied o i . A e ob aining hese da a, a compa ison be ween hese imp o ed implemen a ions will be made, p o iding ecommenda ions on which o use based on he a ailable esou ces. Uses o he FFT The applica ions o he FFT a e as and di e se, wi h many new uses con inually eme ging. This sec ion will no ex ensi ely discuss he use o he FFT in each case, as he de ailed desc ip ion o hese uses along wi h hei espec i e implemen a ions and heo e ical ounda ions a e co e ed in he ci ed e e ences. One o he p ima y uses o he FFT is in spec al analysis o signals, as he main unc ionali y o his algo i hm is he ans o ma ion om he ime domain o he equency domain. By analyzing he spec um o inpu signals in he equency domain, unknown pa ame e s in he ime domain such as equency, ampli ude, and phase o he signal can be obse ed and analyzed [7]. The FFT is a c ucial unc ional block in mode n communica ion sys ems, speci ically in applica ions o O hogonal F equency Di ision Mul iplexing (OFDM), a ansmission echnique ha in ol es mul iplexing a se o ca ie wa es o di e en equencies, each ca ying in o ma ion. No able applica ions include digi al b oadcas ing [8], Wo ldwide In e ope abili y o Mic owa e Access (WiMAX) [9], IEEE 802.11 s anda ds [10], and Long-Te m E olu ion (LTE) ansmission [11]. I is also used in medical imaging [12] o il e ing, analysis, and image econs uc ion. This includes image ma ching o check o simila i ies, such as acial