Кули-Тукијев алгоритам

Кули-Тукијев алгоритам (енгл. Cooley-Tukey algorithm) је најчешће коришћен алгоритам за израчунавање брзе Фуријеове трансформације (енгл. The Fast Fourier Transformation). Алгоритам је први пут објављен 1969. од стране Џејмса Кулија и Џона Тукија у чланку “Брза Фуријеова трансформација I њене примене'” (енгл. The Fast Fourier Transformationa and its Applications). Алгоритам је заснован на принципу “завади па владај” (енгл. divide–and–conquer) и функционише тако што израчунава дискретну Фуријеову трансформацију целе улазне секвенце користећи дискретну Фуријеову трансформацију подсеквенци улазне секвенце.

Историја Цоолеy-Тукеy алгоритма

Овај алгоритам, укључујући његову рекурзивну примену, измислио је Карл Фридрих Гаус око 1805. године, који га је користио за интерполацију трајекторија астероида Палас и Јуно, али његов рад није био широко препознатљив (објављен је само постхумно и на нео-латинском језику). ^[1]^[2] Међутим, Гаус није анализирао асимптотску временску сложеност алгоритма. Разне ограничене форме су такође откривене неколико пута током 19. и почетка 20. века. ФФТ је постао популаран након што су Џејмс Кули из ИБМ-а и Џон Тјуки са Принстона објавили је рад 1965. године у коме је алгоритам детаљно описан, као и поступак како га практично изводити на рачунару. ^[3]

Тјуки је, наводно, дошао до идеје о алгоритму током састанка Саветодавног Одбора за научне студије председника Кенедија о начину откривања тестова нуклеарног оружја у Совјетском Савезу користећи сеизмометре лоциране изван земље. Ови сензори би генерисали сеизмолошке временске серије. Међутим, анализа ових података захтевала би брзе алгоритме за израчунавање ДФТ због броја сензора и дужине времена. Овај задатак је био критичан за ратификацију предложене забране нуклеарног тестирања, тако да би се било каква кршења могла открити без потребе за посетом совјетских објеката. ^[4]^[5] Још један учесник на том састанку, Ричард Гарвин из ИБМ-а, препознао је потенцијал метода и ставио Тјукија у контакт са Кулијем, иако је био сигуран да Кули није знао првобитну сврху. Уместо тога, Кулију је речено да је то потребно за одређивање периодичности спин оријентација у 3-D кристалу Хелијум-3. Кули и Тјуки су касније објавили свој заједнички чланак, а широко усвајање је брзо уследило због истовременог развоја Аналогно-дигиталних претварача способних за узорковање брзином до 300 кХз.

Чињеница да је Гаус описао исти алгоритам (иако без анализе његовог асимптотског временског трошка) није препозната до неколико година након издања рада Кулија и Тјукија 1965-е. Њихов рад је цитиран као инспирација при раду I.Ј. Гуда на ономе што се данас назива ФФТ заснован на простим чиниоцима (енг. Приме-фацтор ФФТ алгоритам, ПФА); иако је алгоритам Гуда првобитно сматран еквивалентом Кули-Тјуки алгоритму, брзо се схватило да је ПФА сасвим другачији алгоритам (ради само за величине које имају узајамно просте факторе и ослања се на Кинеску теорему о остацима, за разлику од Кули-Тјукијеве која ради са било којим величинама). ^[2] Тхеир папер цитед ас инспиратион онлy тхе wорк бy I. Ј. Гоод он wхат ис ноw цаллед тхе приме-фацтор ФФТ алгоритхм (ПФА);^[3] алтхоугх Гоод'с алгоритхм wас инитиаллy тхоугхт то бе еqуивалент то тхе Цоолеy–Тукеy алгоритхм, ит wас qуицклy реализед тхат ПФА ис а qуите дифферент алгоритхм (онлy wоркинг фор сизес тхат хаве релативелy приме фацторс анд релyинг он тхе Цхинесе Ремаиндер Тхеорем, унлике тхе суппорт фор анy цомпосите сизе ин Цоолеy–Тукеy).^[6]

О алгоритмима за брзу Фуријеову трансформацију

Алгоритми за израчунавање брзе Фуријеове трансформације се користе за израчунавање Фуријеове трансформације за дату улазну секвенцу. Дискретна фуријеова трансформација трансформише дискретни импулсни сигнал из временског домена у домен фреквенције. Брза Фуријеова трансформација се користи у много различитих сфера, укјучујући дигиталну обраду сигнала, телекомуникације, и анализу звучног сигнала. Временска сложеност алгоритма брзе Фуријеове трансформације на стандардним микропроцесорским системима са фон Нојмановом архитектуром је $O(NlogN)$ . Убрзана варијанта алгоритма ради у временској сложености $O(logN)$ . Иако је временска сложеност убрзаног алгоритма значајно мања него сложеност стандардног алгоритма, треба имати у виду чињеницу да апликације за убрзање користе Маxелеx ДФЕ технологију, која има неке разлике у поређењу са стандардним фон Нојмановим моделом програмирања.^{[појаснити]} Такође, треба узети у обзир да је, приликом коришћења Маxелер ДФЕ технологије за убрзање апликације, потребно одређено време за пренос података на и из ДФЕ-а. Са друге стране, Маxелер ДФЕ системи имају предност да могу да израчунавају резултате при сваком циклусу сата, након периода поцетне латентности, стварањем хардверских путева. Ова особина омогућује адекватним апликацијама да постигну знацајна убрзања корисцењем Маxелер ДФЕ система.

Преглед различитих алгоритама за брзу Фуријеову трансформацију

Постоји много других алгоритама који рачунају брзу Фуријеову трансформацију (ФФТ), а који се разликују од Кули-Тјуки алгоритма, као што су: Брунов ФФТ алгоритам, Ридеров ФФТ алгоритам, Виноградов ФФТ алгоритам, ФФТ алгоритам заснован на простим чиниоцима, I Блустајнов ФФТ алгоритам. Ови алгоритми користе различите математичке методе да израчунају брзу Фуријеову трансформацију. Коришћене математичке методе варирају од теорије бројева, преко нумеричке математике, до теорије графова. Сви ови алгоритми имају једну заједничку особину: да им је временска сложеност $O(NlogN)$ када су покренути на процесору. Иако не постоје докази да је немогуће конструисати брзи алгоритам са мањом временском сложеношћу од $O(NlogN)$ , такав алгоритам ипак до сада још није конструисан.

Упоређивање перформанси великог броја алгоритама који рачунају брзу Фуријеову трансформацију је направљено од стране Матеа Фригоа и Стивена Г. Џонсона са Масачусетског технолошког института у САД-у. У њиховим истраживањима коришћене су имплементације различитих аутора, написане у периоду дужем од 35 година. Експерименти су изврсавани на различитим архитектурама рацунара. Треба нагласити да су Фриго и Џонсон у експериментима користили само једнопроцесорско језгро у мултипроцесорским системима. Слика 1 је графичка репрезентација података са Фриговог и Џонсоновог експеримента, и приказује поређење између перформаси различитих алгоритама за рачунање брзе Фуријеове трансформације за комплексну улазну секвенцу у зависности од дужине улазне секвенце. Експеримент је изведен на Intel Xeon 3.60 GHz Pentium 4 (Prescott) микропроцесору. Вредности на Y-оси показују брзину алгоритама представљење у Мфлопс-има. Вредност Мфлопс-а се израцунава из средње вредности времена извршавања алгоритма користећи следећу формулу:

мфлопс = 5Нлог_{2}(Н)/(тиме фор оне ФФТ ин мицросецондс)

Слика 1. Графички приказ података из једног од експеримената које су урадили Маттео Фриго и Стевен Г. Јохнсон.

Радиx 2 Цоолеy-Тукеy алгоритам

Радиx 2 Цоолеy-Тукеy алгоритам се састоји од следећих корака:

Улазна секвенца се дели на две подсеквенце. Елементи улазне секвенце са парним индексима чине једну секвенцу, а елементи са непарним индексима чине другу секвенцу.
Израчунај дискретну Фуријеову трансформацију за обе секвенце
Засновано на дискретној Фуријеовој трансформацији подсеквенци, израчунај дискретну Фуријеову трансформацију целе улазне секвенце

Слика 2. Графичка илустрација алгоритма радиx 2. Ова илустрација показује како функционише радиx 2 алгоритам за улазну секвенцу дужине 8. Улазна секвенца подијељена је на две подсеквенце. Прва подсеквенца састоји се од елемената са парним индексима; друга подсеквенца састоји се од елемената са непарним индексима. Илустрација приказује како се дискретна Фоуриерова трансформација целокупне секвенце израчунава из дискретних Фоуриерових трансформација њених подсеквенци.

Математичка основа алгоритма

Дискретна Фуријеова трансформација целе улазне секвенце може бити израчуната помоћу дискретне Фуријеове трансформације подсеквенци парних и непарних елемената на следећи начин:

{\begin{matrix}X_{k}&=&\sum \limits _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\\&=&\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N}}(2m)k}+\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N}}(2m+1)k}\\&=&\sum \limits _{m=0}^{N/2-1}x_{2m}e^{-{\frac {2\pi i}{N/2}}2mk}+e^{-{\frac {2\pi i}{N}}k}\sum \limits _{m=0}^{N/2-1}x_{2m+1}e^{-{\frac {2\pi i}{N/2}}mk}\end{matrix}}

где индекс к иде од 0 до н-1. Прва сума у последњем изразу представља дискретну Фуријеову трансформацију парне подсеквенце, док друга сума представља дискретну Фуријеову трансформацију непарне подсеквенце. Ако означимо прву суму са $E_{k}$ , другу суму са $O_{k}$ , и $e^{-2\pi /N}$ као $W_{n}^{k}$ , добијамо следећу формулу:

{\begin{matrix}X_{k}&=&E_{k}+W_{N}^{k}O_{k}\end{matrix}}

Због особина периодичности дискретне Фуријеове трансформације, важе следеће две једначине:

{\begin{matrix}E_{k+{\frac {N}{2}}}&=&E_{k}\\O_{k+{\frac {N}{2}}}&=&O_{k}\end{matrix}}

Због особина Ојлерове формуле, следеће две једначине су тачне:

{\begin{matrix}e^{-{\frac {2\pi i}{N}}(k+N/2)}&=&e^{-{\frac {2\pi i}{N}}k}\\W_{N}^{k}&=&-W_{N}^{k}\end{matrix}}

Комбинацијом претходних једначина са формулама за израчунавање дискретне Фуријеове трансформације, добијамо коначну формулу која нам омогућује имплементацију алгоритма који се користи за израчунавање дискретне Фуријеове трансформације улазне секвенце помоћу подсеквенци парних и непарних чланова:

{\begin{matrix}X_{k}&=&E_{k}+W_{N}^{k}O_{k}&,k=0...N/2\\X_{k+{\frac {N}{2}}}&=&E_{k}-W_{N}^{k}O_{k}&,k=0...N/2\end{matrix}}

Имплементације Цоолеy-Тукеy алгоритма

Оригинална имплементација алгоритма Цоолеy-Тукеy је итеративна радиx 2 имплементација. Имплементација има оптималну временску сложеност $O(NlogN)$ , где је $N$ број података у улазној секвенци. Просторна сложеност првобитне имплементације је Матх > О(1) </math>. Засновано на формулама из претходног одељка, може се конструисати следећи рекурзиван алгоритам за израчунавање дискретне Фуријеове трансформације:

Псеудо код Радиx 2 Цоолеy-Тукеy Алгоритма

У псеудокоду, ова процедура би могла бити написана на следећи начин: ^[7]

X_0,...,N−1 ← fft_radix2(x):      
    ;specijalan slučaj kada je dužina ulazne sekvence jednaka jedan
    if N = 1 then
        X₀ ← x₀                                      
    else
     
     ;diskretna Furijeova transformacija parne podsekvence
        X_{0,...,N/2−1} ← fft_radix2(even_elements(x))             
     
     ;diskretna Furijeova transformacija neparne podsekvence
       X_N_/2,...,N−1 ← fft_radix2(odd_elements(x))           
        
      ;izračunava diskretnu Furijeovu transformaciju sekvence
      ;pomoću diskretne Furijeove transformacije neparnih i parnih podsekvenci
         
          for k = 0 to N/2−1                           
            t ← X_k
            X_k ← t + exp(−2πi k/N) X_k_+N/2
            X_k_+N/2 ← t − exp(−2πi k/N) X_k_+N/2
        endfor
    endif

Имплементација Цоолеy-Тукеy алгоритма у C++

Имплементација алгоритма у програмском језику C++ има оптималну временску сложеност $O(NlogN)$ , где је Н број улазних тачака улазне секвенце. Просторна сложеност је $O(1)$

/* fft.cpp
 * 
 * Implementacija 
 * Cooley-Tukey rekurzivnog  FFT algoritma.
 * Kompilacija se vrši pomoću GNU/GCC kompilatora na sledeći način:
 *
 * g++ -o fft fft.cpp -lm
 *
 * Pokretanje izvršnog fajla se vrši sledećom naredbom:
 * ./fft
 *
 */

#include <complex>
#include <stdio.h>

using namespace std;

// odvaja parne/neparne elemente u donju/gornju polovinu niza redom.
// Usled "leptir" kombinacija, ispostavlja se da je ovo najjednostavniji način
// da se obavi posao bez pretvaranja pogrešnih elemenata

void separate (complex<double>* a, int n) {
    complex<double>* b = new complex<double>[n/2];  // get temp heap storage
    for(int i=0; i<n/2; i++)    // kopira sve neparne elemente na heap memoriju
        b[i] = a[i*2+1];
    for(int i=0; i<n/2; i++)    // kopira sve parne elemente na nižu polovinu niza a[
        a[i] = a[i*2];
    for(int i=0; i<n/2; i++)    // kopira sve neparne elemente (sa heap-a) na višu polovinu niza a[]
        a[i+n/2] = b[i];
    delete[] b;                 // oslobađa heap
}

// N mora biti deljivo sa dva, u suprotnom stvari mogu poći po zlu.
// U algoritmu nema provere ovog uslova.
//
// Na N ulaznih podataka u nizu X[] je primenjena brza Furijeova transformacija, 
//i rezultati ostaju u X[] 
//
// Samo prvih N/2 rezultata u X[] su rešenje brze Furijeove transformacije ulazne sekvence.

void fft2 (complex<double>* X, int N) {
    if(N < 2) {
        // Izlaz iz rekurzije.
        // Ovde se ništa ne dešava, jer je već X[0] = X[0]
    } else {
        separate(X,N);      // svi parni u nižu polovinu, svi neparni u višu polovinu niza
        fft2(X,     N/2);   // rekurzivno se obrađuju parni elementi
        fft2(X+N/2, N/2);   // rekurzivno se obrađuju neparni elementi
        // kombinuju se rezultati obe polovine niza rekurzivno
        for(int k=0; k<N/2; k++) {
            complex<double> e = X[k    ];   // parni
            complex<double> o = X[k+N/2];   // neparni
                         
            complex<double> w = exp( complex<double>(0,-2.*M_PI*k/N) );
            X[k    ] = e + w * o;
            X[k+N/2] = e - w * o;
        }
    }
}

// test program i main funkcija
int main () {
    const int nSamples = 64;
    double nSeconds = 1.0;                      // ukupno vreme izvršavanja programa
    double sampleRate = nSamples / nSeconds;    // n Hz = n / second 
    double freqResolution = sampleRate / nSamples; // frekvencija izvršavanja koraka u FFT resultatu
    complex<double> x[nSamples];                // lokacija za smeštanje ulaznih podataka
    complex<double> X[nSamples];                // lokacija za smeštanje obradjenih FFT podataka
    const int nFreqs = 5;
    double freq[nFreqs] = { 2, 5, 11, 17, 29 }; // poznate frekvencije za testiranje
    
    // generiše podatke za test primer
    for(int i=0; i<nSamples; i++) {
        x[i] = complex<double>(0.,0.);
        // postavi vrednosti sinusoida u x[]
        for(int j=0; j<nFreqs; j++)
            x[i] += sin( 2*M_PI*freq[j]*i/nSamples );
        X[i] = x[i];        // kopiraj u X[] podatke obradjene brzom Furijeovom transformacijom i rezultate
    }
    // izracunaj brzu Furijeovu transformaciju za ove podatke
    fft2(X,nSamples);
    
    printf("  n\tx[]\tX[]\tf\n");       // stampanje rezultata
    // loop to print values
    for(int i=0; i<nSamples; i++) {
        printf("% 3d\t%+.3f\t%+.3f\t%g\n",
            i, x[i].real(), abs(X[i]), i*freqResolution );
    }
}

// eof

Анализа убрзане верзије Цоолеy-Тукеy ФФТ алгоритма

Слично као и оригиналне ЦПУ имплементације Цоолеy-Тукеy алгоритма, убрзана верзија састоји се од преуређивања реда елемената улазне секвенце на окренути битовски редослед.

Убрзање се рачуна следећом формулом:

$\eta ={\frac {T_{cpu}}{T_{max}}}$

$T_{cpu}$ представља време које је потребно да се израчунавање изврши на ЦПУ-у, а $T_{max}$ представља време које је потребно да се израчунавање изврши на Маxелер ДФЕ-у.

Детаљи имплементације

Код кернела за рачунање ФФТ прима параметар Н који представља број чворова улазне секвенце.^[8] Овај кернел има две улазне и две излазне секвенце података. Те две излазне секвенце се користе за трансфер реалног и имагинарног дела улазне секвенце тачака. Ове секвенце су типа АрраyТyпе који је дефинисан на следећи начин:


DFEType floatType = dfeFloat(8, 24);
DFEArrayType<DFEVar> arrayType =

   new DFEArrayType<DFEVar>(floatType, n);

Коефицијенти $W_{n}^{k}$ се израчунавају током компилације, и не користе се као хардверске константе.

Коришћење ДФЕ за израчунавање ФФТ

МаxЦомпилер генерише заглавље ФФТ.х које садржи следећи метод:


FFT(

  int number_of_input_sequences,

  float *imag_in,

  float *real_

  in,

  float *imag_out,

  float '''*real_out'''
  
 );

Позивањем овог метода из C/C++ кода, шаљу се подаци са ЦПУ-а на ДФЕ, врши се израчунавање ФФТ-а на ДФЕ-у и резултат се шаље назад ЦПУ-у. За МаxЦомпилер, да би генерисао заглавље ФФТ.х, СлиЦ опција мора бити укључена.

МаxЈ код Кернела који израчунава ФФТ


import com.maxeler.maxcompiler.v2.kernelcompiler.Kernel;
import com.maxeler.maxcompiler.v2.kernelcompiler.KernelParameters;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.base.DFEType;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.base.DFEVar;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.composite.DFEArray;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.composite.DFEArrayType;

class FFTKernel extends Kernel {

   private static final DFEType floatType = dfeFloat(8, 24);

   protected FFTKernel(KernelParameters parameters, int n) {
     super(parameters);

     DFEArrayType < DFEVar > arrayType =

        new DFEArrayType < DFEVar > (floatType, n);
     
     DFEArray < DFEVar > in_real = io.input(“in_real”, arrayType);
     DFEArray < DFEVar > in_imag = io.input(“in_imag”, arrayType);



     int log_n = Integer.numberOfTrailingZeros(n);


     DFEVar[][] real = new DFEVar[log_n + 1][n];
     DFEVar[][] imag = new DFEVar[log_n + 1][n];


     for (int i = 0; i < n; i++) {
        int j = Integer.reverse(i) >>> (32 - log_n);

        real[0][i] = in_real[j];
        imag[0][i] = in_imag[j];
     }


     for (int i = 1, log_i = 0; i < n; i *= 2, log_i++) {
        for (int k = 0; k < i; k++) {
           float w_real = (float) Math.cos(-2 * Math.PI * k / (i * 2));
           float w_imag = (float) Math.sin(-2 * Math.PI * k / (i * 2));


        for (int j = 0; j < n; j += i * 2) {
           DFEVar temp_real =
              real[log_i][j + k + i] * w_real - imag[log_i][j + k + i] * w_imag;
           DFEVar temp_imag =
              real[log_i][j + k + i] * w_imag + imag[log_i][j + k + i] * w_real;

           real[log_i+ 1][j + k + i] = real[log_i][j + k] - temp_real;
           imag[log_i+ 1][j + k + i] = imag[log_i][j + k] - temp_imag;


           real[log_i+ 1][j + k] = real[log_i][j + k] + temp_real;
           imag[log_i+ 1][j + k] = imag[log_i][j + k] + temp_imag;
        }
     }
   }

   DFEArray < DFEVar > out_real = arrayType.newInstance(this);

   for (int i = 0; i < n; i++)
     out_real[i] <= = real[log_n][i];

   io.output(“out_real”, out_real, arrayType);

   DFEArray < DFEVar > out_imag = arrayType.newInstance(this);


   for (int i = 0; i < n; i++)
     out_imag[i] <== imag[log_n][i];

   io.output(“out_imag”, out_imag, arrayType);
   }
}

МаxЈ код Цоолеy-Тукеy Радиx-2 Алгоритма


package fft;

import com.maxeler.maxcompiler.v2.build.EngineParameters;
import com.maxeler.maxcompiler.v2.managers.custom.CustomManager;
import com.maxeler.maxcompiler.v2.managers.custom.DFELink;
import com.maxeler.maxcompiler.v2.managers.custom.blocks.KernelBlock;
import com.maxeler.maxcompiler.v2.managers.custom.stdlib.Max3RingConnection;
import com.maxeler.maxcompiler.v2.managers.custom.stdlib.MaxRingBidirectionalStream;
import com.maxeler.maxcompiler.v2.managers.engine_interfaces.CPUTypes;
import com.maxeler.maxcompiler.v2.managers.engine_interfaces.EngineInterface;
import com.maxeler.maxcompiler.v2.managers.engine_interfaces.InterfaceParam;


public class FFTManager extends CustomManager {

public FFTManager(EngineParameters engineParameters, int n) {
super(engineParameters);
KernelBlock bitreversePhase = addKernel(
new BitReverseKernel(makeKernelParameters(“BitreversePhase”), n));


KernelBlock fftPhase = addKernel(
new FFTKernel(makeKernelParameters(“FFTPhase”), n, 0, Integer.numberOfTrailingZeros(n)/2, false, true));


DFELink in_real = addStreamFromCPU(“in_real”);
DFELink in_imag = addStreamFromCPU(“in_imag”);


bitreversePhase.getInput(“in_real”) <== in_real;
bitreversePhase.getInput(“in_imag”) <== in_imag;


fftPhase.getInput(“in_real”) <== bitreversePhase.getOutput(“out_real”);
fftPhase.getInput(“in_imag”) <== bitreversePhase.getOutput(“out_imag”);


MaxRingBidirectionalStream real_ring = addMaxRingBidirectionalStream(“realRingStream”,
Max3RingConnection.MAXRING_A);
MaxRingBidirectionalStream imag_ring = addMaxRingBidirectionalStream(“imagRingStream”,
Max3RingConnection.MAXRING_A);


fftPhase.getInput(“in_real_dummy”) <== real_ring.getLinkFromRemoteDFE();
fftPhase.getInput(“in_imag_dummy”) <== imag_ring.getLinkFromRemoteDFE();


real_ring.getLinkToRemoteDFE() <== fftPhase.getOutput(“out_real”);
imag_ring.getLinkToRemoteDFE() <== fftPhase.getOutput(“out_imag”);
}



static EngineInterface interfaceDefault (int n) {

EngineInterface ei = new EngineInterface();
InterfaceParam size = ei.addParam(“dataSize”, CPUTypes.UINT64);


ei.setTicks(“FFTPhase”, size);
ei.setTicks(“BitreversePhase”, size);


ei.setStream(“in_real”, CPUTypes.FLOAT, size * n * CPUTypes.FLOAT.sizeInBytes());
ei.setStream(“in_imag”, CPUTypes.FLOAT, size * n * CPUTypes.FLOAT.sizeInBytes());
return ei ;
}



public static void main(String[] args) {
EngineParameters params = new EngineParameters(args);
int n = Integer.parseInt(System.getenv(“n”));
System.out.println(n);


FFTManager manager = new FFTManager(params, n);

  //manager.setIO(IOType.ALL_CPU);
manager.addMaxFileConstant(“n”, n);
manager.createSLiCinterface(interfaceDefault(n));

  //manager.getBuildConfig().setBuildEffort(Effort.LOW);
manager.getBuildConfig().setMPPRCostTableSearchRange(1, 3);
manager.getBuildConfig().setMPPRParallelism(3);


manager.build();
}
}

МаxЈ код за окретање битова

package fft;
import com.maxeler.maxcompiler.v2.kernelcompiler.Kernel;
import com.maxeler.maxcompiler.v2.kernelcompiler.KernelParameters;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.base.DFEType;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.base.DFEVar;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.composite.DFEArray;
import com.maxeler.maxcompiler.v2.kernelcompiler.types.composite.DFEArrayType;


class BitReverseKernel extends Kernel {


private static final DFEType floatType = dfeFloat(8,24);


protected BitReverseKernel(KernelParameters parameters, int n) {
super(parameters);


DFEArrayType<DFEVar> arrayType = new DFEArrayType<DFEVar>(floatType, n);


DFEArray<DFEVar> in_real = io.input(“in_real”, arrayType);
DFEArray<DFEVar> in_imag = io.input(“in_imag”, arrayType);


int log_n = Integer.numberOfTrailingZeros(n);


DFEVar[] real = new DFEVar[n];
DFEVar[] imag = new DFEVar[n];


for(int i = 0; i < n; i++) {
int j = Integer.reverse(i) >>> (32 - log_n);

  real[i] = in_real[j];
  imag[i] = in_imag[j];
}


DFEArray<DFEVar> out_real = arrayType.newInstance(this);


for (int i = 0; i < n; i++)
out_real[i] <== real[i];

io.output(“out_real”, out_real, arrayType);

DFEArray<DFEVar> out_imag = arrayType.newInstance(this);


for (int i = 0; i < n; i++)
out_imag[i] <== imag[i];
io.output(“out_imag”, out_imag, arrayType);

}
}

Закључак

Извођени експерименти^{[који? ]} су показали да убрзана имплементација има очекиване перформансе и да то даје еквивалентне резултате оригиналној имплементацији. Перформансе убрзане апликације су превазишле перформансе друге јавно доступне имплементације брзе Фуријеове трансформације. Због ограниченог броја хардверских ресурса на Маxелер картици која се користи за наше експерименте, нисмо успели да генеришемо битстреам за израчунавање брзог Фоуриеровог трансформирања улазних секвенци са више од 32 тачке. На бољим Маxелер машинама, као што је МАКС4 (Маиа или Цориа), могуће је генерисати битстреам који израчунава брзу Фоуриерову трансформацију дуже улазне секвенце.

Због својстава алгоритма радиx 2, могуће је направити хибридно рјешење које ће користити и ЦПУ и Маxелер ДФЕ за израчунавање брзе Фоуриерове трансформације. ЦПУ део апликације би поделио проблем на мање проблеме који би, зависно од њихове величине, били решени на ДФЕ-у или поново подељени.

Очекује се, а изведени експерименти потврђују, да постоји повећање постигнутог убрзања с повећањем броја елемената улазне секвенце. Убрзање се повећава јер се иницијална латенција имплементације ДФЕ-а повећава спорије од латенције имплементације ЦПУ-а. Такође, приликом извршавања вишеструких прорачуна, након периода почетне латенције, имплементација ДФЕ-а даје резултате на сваком тактном циклусу док имплементација ЦПУ има исту латенцију за израчунавање сваког резултата.

Да би се постигло убрзање коришћењем убрзане имплементације потребно је извршити више узастопних прорачуна брзе Фуријеове трансформације. Број узастопних прорачуна потребних за извођење, у циљу постизања убрзање у поређењу са оригиналном имплементацијом ЦПУ-а, зависи од броја тачака у улазној секвенци.

Референце

^ Гаусс, Царл Фриедрицх, "Тхеориа интерполатионис метходо нова трацтата^{[мртва веза]}", Wерке, Банд 3, 265–327 (Кöниглицхе Геселлсцхафт дер Wиссенсцхафтен, Гöттинген, 1866)
^ ^а ^б Хеидеман, M. Т., D. Х. Јохнсон, анд C. С. Буррус, "Гаусс анд тхе хисторy оф тхе фаст Фоуриер трансформ," ИЕЕЕ АССП Магазине, 1, (4), 14–21 (1984)
^ ^а ^б Цоолеy, Јамес W.; Тукеy, Јохн W. (1965). „Ан алгоритхм фор тхе мацхине цалцулатион оф цомплеx Фоуриер сериес”. Матх. Цомпут. 19: 297—301. дои:10.2307/2003354.
^ Цоолеy, Јамес W.; Леwис, Петер А. W.; Wелцх, Петер D. (1967). „Хисторицал нотес он тхе фаст Фоуриер трансформ”. ИЕЕЕ Транс. он Аудио анд Елецтроацоустицс. 15 (2): 76—79. дои:10.1109/тау.1967.1161903.
^ Роцкморе, Даниел Н. , Цомпут. Сци. Енг. 2 (1), 60 (2000). Тхе ФФТ — ан алгоритхм тхе wхоле фамилy цан усе Специал иссуе он "топ тен алгоритхмс оф тхе центурy "„Арцхивед цопy” (ПДФ). Архивирано из оригинала (ПДФ) 2009-04-07. г. Приступљено 2009-03-31.
^ Јамес W. Цоолеy, Петер А. W. Леwис, анд Петер W. Wелцх, "Хисторицал нотес он тхе фаст Фоуриер трансформ," Проц. ИЕЕЕ, вол. 55 (но. 10), п. 1675–1677 (1967).
^ С. Г. Јохнсон анд M. Фриго, "Имплементинг ФФТс ин працтице," ин Фаст Фоуриер Трансформс (C. С. Буррус, ед.), цх. 11, Рице Университy, Хоустон ТX: Цоннеxионс, Септембер 2008.
^ Милутиновиц, V., Салом, Ј., Трифуновиц, Н., Гиорги, Р., "Гуиде то ДатаФлоw СуперЦомпутинг," Спрингер, 2015.

Спољашње везе

Радиx-2 Дециматион ин Тиме ФФТ Алгоритхм
Радиx-2 Дециматион ин Фреqуенцy ФФТ Алгоритхм
а симпле, педагогицал радиx-2 Цоолеy–Тукеy ФФТ алгоритхм ин C++.
КИССФФТ: а симпле миxед-радиx Цоолеy–Тукеy имплементатион ин C (опен соурце)

[1] Гаусс, Царл Фриедрицх, "Тхеориа интерполатионис метходо нова трацтата^{[мртва веза]}", Wерке, Банд 3, 265–327 (Кöниглицхе Геселлсцхафт дер Wиссенсцхафтен, Гöттинген, 1866)

[Heideman84-2] а ^б Хеидеман, M. Т., D. Х. Јохнсон, анд C. С. Буррус, "Гаусс анд тхе хисторy оф тхе фаст Фоуриер трансформ," ИЕЕЕ АССП Магазине, 1, (4), 14–21 (1984)

[CooleyTukey65-3] а ^б Цоолеy, Јамес W.; Тукеy, Јохн W. (1965). „Ан алгоритхм фор тхе мацхине цалцулатион оф цомплеx Фоуриер сериес”. Матх. Цомпут. 19: 297—301. дои:10.2307/2003354.

[4] Цоолеy, Јамес W.; Леwис, Петер А. W.; Wелцх, Петер D. (1967). „Хисторицал нотес он тхе фаст Фоуриер трансформ”. ИЕЕЕ Транс. он Аудио анд Елецтроацоустицс. 15 (2): 76—79. дои:10.1109/тау.1967.1161903.

[5] Роцкморе, Даниел Н. , Цомпут. Сци. Енг. 2 (1), 60 (2000). Тхе ФФТ — ан алгоритхм тхе wхоле фамилy цан усе Специал иссуе он "топ тен алгоритхмс оф тхе центурy "„Арцхивед цопy” (ПДФ). Архивирано из оригинала (ПДФ) 2009-04-07. г. Приступљено 2009-03-31.

[6] Јамес W. Цоолеy, Петер А. W. Леwис, анд Петер W. Wелцх, "Хисторицал нотес он тхе фаст Фоуриер трансформ," Проц. ИЕЕЕ, вол. 55 (но. 10), п. 1675–1677 (1967).

[7] С. Г. Јохнсон анд M. Фриго, "Имплементинг ФФТс ин працтице," ин Фаст Фоуриер Трансформс (C. С. Буррус, ед.), цх. 11, Рице Университy, Хоустон ТX: Цоннеxионс, Септембер 2008.

[8] Милутиновиц, V., Салом, Ј., Трифуновиц, Н., Гиорги, Р., "Гуиде то ДатаФлоw СуперЦомпутинг," Спрингер, 2015.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]