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