Prosjekt Optimalisering av FFT

H?st 2019

Oppgave

I dette prosjektet skal vi bli bedre kjent med arkitekturen p? Raspberry Pi 3 Model B+ (RPi) ved ? forst? og forbedre en Fast Fourier Transform (FFT) algoritme (en kort forklaring av hva en Fourier Transformasjon er finner du nederst i dette dokumentet).

For ? kunne utnytte den fulle prosessorkraften til en datamaskin er det viktig ? kjenne til hvordan forskjellige aspekter av prosessoren jobber sammen. F.eks. s? hjelper det lite om en prosessor kan legge sammen 100 tall p? en gang hvis ikke vi kan laste inn 100 tall mellom utregninger. Det er derfor viktig ? kjenne til hvordan prosessoren jobber sammen med minne (RAM og cache) slik at vi kan designe utregningene v?re for maksimal utnyttelse. Det er ogs? viktig ? forst? algoritmen som skal implementeres slik at vi kan redusere antall beregninger, kanskje vi kan regne ut verdier som brukes om igjen og om igjen p? forh?nd for ? redusere antall operasjoner som prosessoren trenger ? gj?re.

I den utgitte koden vil du finne en naiv implementasjon av en radix-2 FFT samt at vi har benyttet oss av et eksternt bibliotek (FFTW) for ? beregne FFT-er av forskjellige st?rrelser. Oppgaven er ? gj?re inkrementelle forbedringer p? den naive l?sningen og dokumentere disse forbedringene. FFTW er tatt med slik at man kan sammenligne seg selv med en state-of-the-art algoritme, det forventes ikke at noen klarer ? konkurrere med FFTW, men bruk det som en motivasjon.

Resultatet av prosjektet er en rapport som dokumenterer forbedringene som er gjort, se seksjon under for hvordan dette burde skrives. Prosjektet blir bed?mt p? bakgrunn av rapporten og ikke C-kode eller faktisk oppn?dd kj?retid. Hver gruppe (eller student) m? ogs? i l?pet av uke 44 m?te opp p? gruppetime og vise frem prosjektet. Form?let med dette er at vi skal kunne sjekke at dere faktisk har forst?tt forbedringene dere foresl?r samt at det er deres egen kode.

Det er forventet at alle pr?ver minst et av forslagene skissert nedenfor, samt skriver teoretisk (trenger ikke ? implementere forbedringen, men skriv om hvorfor det teoretisk burde fungere) om et annet forslag. For ? motivere litt ekstra s? kommer det ogs? til ? v?re en konkurranse om beste kj?retid.

Rapporten skal tilslutt leveres in som en PDF sammen med kildekoden din. Husk ogs? ? m?te opp p? gruppetime i l?pet av uke 44.

Konkurranse

For ? motivere litt ekstra vil vi i tillegg til prosjektet arrangere en liten konkurranse. Vinneren er den med best kj?retid over forskjellige st?rrelser av FFT-er. De samme reglene gjelder for konkurransen som for prosjektet, ingen eksterne biblioteker, men uten om det s? kan alle kapabiliteter p? RPi-en utnyttes. Den eller de med best kj?retid vil bli bel?nnet med en liten premie.

Begrensninger

Utgitt kode

Lenke til utgitt kildekode

I koden s? vil du finne en header fil (fft.h) som beskriver hvordan fft_compute skal se ut (hvilke parametere den tar inn og hva den returnerer). Det er ogs? lagt ved en naive implementasjon i fft.c, dette er den filen som du skal endre. I test.c finner du koden vi bruker for ? teste at utregningen din er korrekt, mens i bench.c finner du kode som tester hastigheten til utregningene. Vi har lagt ved noen programsnutter i run.sh og plot.p som brukes til ? teste og plotte resultatene, mer om de er forklart i Plotte forbedringer under. Tilslutt har vi lagt ved en Makefile som kan brukes til ? bygge koden din.

Makefile inneholder f?lgende kommandoer du kan kj?re med make ${COMMAND}

I tillegg til den utgitte koden vil du trenge f?lgende programmer

Hvordan dokumentere en forbedring

For ? dokumentere en forbedring s? er det ?nskelig at man tenker over f?lgende punkter.

Hvis du skal skrive teoretisk om en forbedring s? kan du hoppe over implementasjon (men dokumenter parametere!), og faktiske kj?retidsforskjeller. Merk at ved teoretisk forklaring forventes det mer av teksten s? det er viktig ? underbygge p?stander med teori fra boken og gjerne eksterne kilder.

Plotte forbedringer

For ? helpe litt har vi lagt ved noen programsnutter som kan benyttes for ? kompilere og lage grafer av kj?retiden.

For plotting s? kan man benytte seg av make run for ? generere et plot f?r man starter, denne kommandoen passer p? at alt er kompilert ogs? kj?rer den koden din sammen med FFTW. Denne kommandoen vil s? kj?re programmet run.sh som f?rst tester at koden din gir riktig svar f?r den deretter tester programmet ditt, og FFTW, p? mer utfordrende st?rrelser av FFT-er. Kj?retiden fra disse st?rrelsene blir lagret i en fil f?r plot.p (et gnuplot program) kj?res og produserer et PNG bilde. For ? gj?re det enklere ? sammenligne forbedringene som gj?res s? tar run.sh inn et argument, filnavnet hvor kj?retider skal lagres. Tanker er at n?r en forbedring er implementert s? kan man gj?re run.sh p? nytt og utvide plotte sitt.

Eksempel

La oss si at det f?rste vi gj?r er ? implementere forbedringen fjerning av allokeringer. F?rst m? vi faktisk implementere endringer, mens vi holder p? med dette kan vi bruke make til ? bygge koden v?r samt bygge testkode, vi kan kj?re f?lgende kommando for ? bygge koden v?r samt testkode

Dette bygger koden v?r og en kj?rbar fil ved navn test, dette programmet brukes for ? teste at koden din er riktig, du kan kj?re det med ./test 1024. Hvis alt er riktig forteller programmet deg at den ikke finner noen feil. Det neste vi kan gj?re er derfor ? benchmarke programmet v?rt. Dette gj?res ved ? f?rst bygge benchmarkkoden og deretter kj?re run.sh manuelt, som f?lgende

Dette vil skape en tekstfil med tiden det tok ? beregne FFT-er uten allokering. Det siste vi trenger ? gj?re er ? endre p? gnuplot programmet slik at det ogs? viser en linje for den nye datafilen v?r. Nederst i plot.p finner vi f?lgende linjer

plot "time.dat" using 1:2 title "FFTW", \
     "time.dat" using 1:3 title "Naive"

Endre dette til ? v?re

plot "time.dat" using 1:2 title "FFTW", \
     "time.dat" using 1:3 title "Naive", \
     "no-alloc.dat" using 1:3 title "No allocation"

Legg merke til at vi la til et , og en \ samt den nye linjen som forteller gnuplot at den skal bruke data fra den nye filen v?r for ? tegne grafen. Kj?r gnuplot p? nytt med f?lgende kommando

PNG filen blir da overskrevet med den nye grafen og du kan visuelt inspisere hvor stor kj?retidsforskjell din forbedring har gitt.

I rapporten burde en slik graf v?re lagt ved for ? vise forskjellen i forbedringene dine. Hvis du har flere forbedringer er det fint med en linje per forbedring (forbedringene kan selvsagt v?re kumulative, slik at linje 1 viser uten allokering, linje 2 viser uten allokering + forh?ndsutregnet twiddle faktorer, osv.).

Forslag til forbedringer

Fouriertransformasjon

En fouriertransformasjon forvandler et signal i tids-domenet om til et signal i frekvens-domenet. Dette betyr at vi kan m?let et signal over en gitt tidsperiode for deretter ? dekomponere signalet inn i hvilke frekvenser signalet best?r av.

Visuell forklaring av en Fourier Transformasjon
Visuell forklaring av en Fourier Transformasjon

P? bildet over er transformasjonen visualisert. P? venstre side kan vi se at et signal m?lt over tid best?r av summen av tre sinus-b?lger (markert i lilla som enkelt streker). Dette signalet (r?dt) blir s? dekomponert til ? vise hvor i frekvensspekteret de st?rste sinus-b?lgene eksisterer (bl?tt frekvensspekter).

Beskrivelsen av en fouriertransformasjon over er kort og ment til ? gi en magef?lelse p? algoritmen som jobbes med i dette prosjektet. Man trenger ikke ? intimt forst? hva en fouriertransformasjon er for ? kunne fullf?re prosjektet. For mer informasjon se Wikipedia.