• Author / Uploaded
• Raúl Suquinagua

• Categories
• Algoritmos
• Unidad Central de procesamiento
• Microprocesador
• Ingeniería Electrónica
• Electrónica digital

Citation preview

Implementac´ıon De FFT En Chips DSP Teor´ıa y Pr´actica Suquinagua Ra´ul [email protected]

Resumen—Se trata el problema de c´omo influye los diferentes chips desarrollados en el comportamiento de los algoritmos y su eficiencia. Adem´as se dar´a algunos consejos para optimizar en ciertos procesos y sobre las consideraciones estructurales. Palabras Clave—Algoritmo,Chips,Diagrama de flujo, Diezmado, Twiddle Factor.

I.

´ I NTRODUCCI ON

Como en todo algoritmo se desea conocer la complejidad computacional, en la transformada r´apida de Fourier (FFT), se lo determina mediante el n´umero de operaciones matem´aticas que toma en realizar el proceso, en algunos casos se considera solamente las operaciones de multiplicaci´on [1] y al considerar esto, se hace mucho m´as f´acil calcular te´oricamente el n´umero de operaciones [2]. Actualmente, el avance de la tecnolog´ıa ha influido en el dise˜no del algoritmos: mientras que en los a˜nos 60 y principios del 70 el inter´es se centraba en disminuir el n´umero de multiplicaciones, estos avances han revelado que tambi´en son de importancia fundamental el n´umero de sumas y de accesos a memoria . Algunos procesadores modernos incluyen un m´odulo optimizado para el c´alculo por hardware de la DTF [3].

para un algoritmo radix-2 est´a dado por: N 2 log2 N

→ multiplicaciones complejas

N log2 N → sumas complejas El diezmado en tiempo, por otro lado, son algoritmos en las cuales la descomposici´on es basado en descomposiciones de secuencias x(n), a trav´es de sub-secuencias peque˜nas sucesivas [4]. Por ejemplo consideremos un caso especial en donde N es potencia de 2, nosotros podemos considerar calcular X(k) separando x(n) en N/2 secuencias consistiendo en n´umeros par de puntos y numero impar de puntos de x(n) por lo tanto: P P X(k) = neven x(n)WNnk + nodd x(n)WNnk X(k) = G(k) + WNk H(k) En la Figura 1(a) se puede observar la mariposa DIF, mientras que la mariposa DIT se muestra en la Figura 1(b). Se puede ver que los twiddle factors est´an denotados por: e–j2πQ/N en donde Q es un n´umero entero entre 0 ≤ Q ≤ (N/2) − 1

En este art´ıculo se aborda sobre las caracter´ısticas de los procesadores DSP existentes, as´ı como sus diferentes arquitecturas. Vamos a ver que ciertos procesadores son pr´acticos para ciertos algoritmos y para otros no, todo esto depende de los ciclos de instrucci´on que se ocupa para hacer la FFT. Hay 3 tipos de algoritmos que vamos a analizar: Radix-2 (R2), Radix-4 (R4) y Split-Radix (SP) (el Radix es el tama˜no de la descomposici´on de la FFT). Para esto describimos las propiedades que conllevan, diferencias y generalidades para decidir cr´ıticamente que algoritmo implementar. II.

D IFERENCIA ENTRE DIEZMADO EN TIEMPO (DIT) Y DIEZMADO EN FRECUENCIA (DIF)

Antes de presentar los algoritmos de FFT, tenemos que comprender los tipos de configuraci´on de mariposas simples usadas en los algoritmos.

Figura 1. Mariposas DIF y DIT [9].

III. III-A.

Radix-2

Es la m´ınima parte en que se puede dividir la FFT, esta consta de una mariposa con dos entradas y dos salidas (ver Figura 2).

Como sabemos en los diagramas de flujo de FFTs con sus arreglos de operaciones pueden se implementados de diferentes formas las operaciones mariposa, pero los m´as o´ ptimos son las mariposas de multiplicaci´on compleja simple. Diezmado en frecuencia es llamado debido a que las muestras de frecuencia se calculan por separado en grupos alternativos [3]. El costo computacional

T IPO DE ALGORITMOS .

Figura 2. Radix-2.

III-B.

Radix-4

La mariposa de un algoritmo radix-4 consta de cuatro entradas y cuatro salidas (ver Figura 3). La longitud FFT es 4M , Donde M es el n´umero de etapas. Una etapa es un medio de radix-2. Los radix4 FFT requieren s´olo un 75 % de mayor n´umero de multiplicaciones complejas que las radix-2 FFT [4].

que influye es el paralelismo de operaciones, es decir, cuantas operaciones simultaneas puede realizar. Al pasar el tiempo los integrados DSP han tenido muchas mejoras, un gran avance fue que el tiempo en que se demoraba en realizar una multiplicaci´on fue la misma que un ciclo de instrucci´on. Luego se realiz´o dos extracciones de memoria simult´aneamente, lo que logr´o una gran convergencia del algoritmo. Y la capacidad de realizar paralelamente una suma y una resta [2]. MCU es para representar X · Y + U . C ARACTER´I STICAS DE LOS PROCESADORES DSP

Tabla II.

Figura 3. Radix-4.

III-C.

Split-Radix

El algoritmo Split-Radix es una fusi´on de Radix2 y Radix-4, en t´erminos de DFTs de longitud N/2 y dos mas peque˜nas de longitud N/4.

Clasificaci´on −

Operaciones AU y k

Recuperaci´on simult´anea

Ejemplos −

TIPO I.0

MPY o ADD o SUB

No posible

TMS32010

TIPO I.1

Mismas I.0

1

TIPO II.1

MPY o ADD o SUB o MAC

1

ADSP2100

TIPO II.2

Mismas II.1

2

PCB5011

TIPO III.2

MPY k ADD o MPY k SUB

2

TMS320C30

TIPO IV.2

Mismas III.2 o MPY k ADDSUB

2

DSP96002

Figura 4. Split-Radix.

IV.

P ROPIEDADES DE LOS ALGORITMOS

Para poder implementar o escoger un buen algoritmo es esencial saber las propiedades que tiene cada uno de ellos, en este caso vamos a analizar: el n´umero de operaciones de cada algoritmo, acceso a operandos, la ponderaci´on de factor y n´umero de mariposas(ver Tabla I). Tabla I.

P ROPIEDADES DE ALGORITMOS FFT

Tipo −

Operaciones Reales M P Y \ ADD

Operaciones De Recuperaci´on DAT A \ T F

R2

4\6

8\2

SR

8 \ 16

16 \ 4

R4

12 \ 22

16 \ 6

´ DE LOS INTEGRADOS CLASIFICACI ON

DSP

Existen diferentes integrados para este prop´osito, pero estos se clasifican de acuerdo a la rapidez de procesamiento, por lo tanto la arquitectura ser´a diferente para cada dispositivo, un factor muy importante

´ AN ALISIS DE DIFERENTES ALGORITMOS

En el punto anterior vimos las caracter´ısticas principales de los procesadores, pero depende de que algoritmo utilicemos para saber su rendimiento, en este punto vamos a analizar diferentes situaciones.

VI-A.

Vamos a ver en el siguiente punto que el rendimiento de la transformada depende mucho del paralelismo de las propiedades de los algoritmos. V.

VI.

Consideraciones para elegir procesadores

Hay que prestar mucha atenci´on a la Figura 6, ya que aqu´ı se puede observar los ciclos que toma en realizar un proceso para las diferentes categor´ıas de los procesadores, por ejemplo si escogemos el procesador m´as potente(ver Figura 5) vemos que en el caso del radix-2 ocupa 16 mariposas, en el radix-4 14 mariposas y en el split-radix ocupa solamente 13.3 mariposas, entonces se ve claramente que el algoritmo SR es el mejor para utilizar. Hay que tomar en cuenta que en el caso de los procesadores tipo II-2 vemos que la mejor opci´on es el algoritmo radix-2 dado que en el diezmado en tiempo tiene menor n´umero de mariposas que los dem´as.

Tabla III.

T WIDDLE FACTORS S IMPLES

N/4 WN

PM 2 i=2

N/2i

−

PM 4 i=2

Figura 5. N´umero y tipo de instrucciones.

VI-B.

consideraciones en la arquitectura

La rapidez de ejecuci´on de un algoritmo depende de gran medida de la arquitectura del procesador. Tenemos tres categor´ıas: El primer caso es el m´as simple, con un solo acumulador y u´ nico bus de datos. El resultado de la operaci´on debe estar en el acumulador e inmediatamente enviarlo por el bus [2], esto genera congesti´on consecuentemente demora y eso es lo que precisamente queremos evitar, los primeros procesadores funcionan as´ı. En la segunda categor´ıa ya contamos con varios acumuladores, esto de alguna manera disminuye la carga de procesamiento, pero existe una categor´ıa m´as que logra un gran rendimiento. En la u´ ltima categor´ıa se cuenta con acumuladores como en el caso anterior, pero adem´as se cuenta con varios buses y unidades aritm´eticas [2] lo que posibilita un gran nivel de procesamiento de datos haciendo uso de pocos recursos. VII.

´ OPTIMIZACI ON

N/4i

N/8

WN

PM 2 i=3

N/2i

N −3−(−1)M 2 6

PM 4 i=3

N/4i

3N/8

WN

PM 2 i=3

N/2i

N −3−(−1)M 2 6

PM 4 i=3

N/4i

n´umero de operaciones. Hay que tomar en cuenta que las mariposas especiales (ahorra n´umero de operaciones) es diferente para cada algoritmo. Por ejemplo si procesamos 1024 puntos sin realizar ninguna optimizaci´on en Radix-2 con un procesador tipo I tendremos un total de 96160 operaciones, con optimizaci´on, en cambio este resultado se reduce a 77500 operaciones. La u´ ltima etapa consiste en un conjunto de bucles anidados para inicializar contadores y varios registros, entonces al colocar un solo contador que realice esta funci´on logramos una reducci´on de carga estructural del 30 al 40 % [2]. VII-A.

Reducci´on del TF

Consideremos primeramente la generaci´on de Twiddle Factors mediante: sin(2πk/n)k = 1, 2, · · · , N/4 Por lo que el limite inferior es N/4 pero este tama˜no peque˜no requiere gran cantidad de direccionamiento, por otro lado si hacemos el an´alisis para todo el periodo N o para la mitad del periodo N/2 reduce el costo computacional significativamente [2]. Ahora vamos a analizar una reducci´on del n´umero de TF para el caso del Radix-2, mediante la relaci´on de los TF. primeramente vamos a analizar la figura de abajo:

Podemos reducir el costo computacional, analizando los patrones de la operaciones, como por ejemplo analizar las propiedades del Twiddle Factor [5]: k+N/2

Simetria : WN = −WNk k+N P erioricidad : WN = WNk Tambi´en vemos que hay Twiddle Factors (TF) especiales, por su simplicidad, por ejemplo para el caso del Radix-4 se observa: Nk

k WN4 = exp(−j kπ 2 ) = (−j) 2N k 4

WN = exp(−jkπ) = (−1)k 3N k k WN 4 = exp(−j 3kπ 2 ) = (j)

Figura 6. Relaciones TFs

Debido a que analizamos tres algoritmos, en la tabla I se observa los factores simples de cada caso. En la primera fila vemos los factores del Radix-2, en la segunda fila para Split-Radix y la u´ ltima fila Radix-4 :

Vemos que para cada coeficiente, el del lado opuesto es el mismo pero cambiado de signo, es decir, WNk → −WNk por lo tanto podemos reducir el c´alculo a la mitad y consecuentemente aumentar el n´umero de punteros de direccionamiento.

Podemos juntar las dos primeras etapas del diezmado en tiempo en una sola para ahorrar el m´aximo

Ahora para reducir a´un m´as el n´umero de coeficientes calculados, tomamos N/2 n´umeros

N/4

WN

´ TABLA RECUPERACI ON

Tabla IV.

complejos y los combinamos en parejas, lo cual difieren un factor de:

k WN max

k≤

Wk

= −j

WNk = cos(2πk/N ) − jsin(2πk/N ), para

−jM N max − k 4

k = 0, 1, · · · , N4 − 1

−jM ∗

k− N max 4

Entonces el primer TF del par es:

−M ∗N max

−k

2

k+N/4 WN

-

= −jWNk

−Mk− N max 2

= −sin(2πk/N ) − jcos(2πk/N ), para

jM ∗3N max 4

−k

N max 8

N max 4 3N max 8 N max 2

N max 8