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) 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.