Prosjekt Optimalisering av FFT

Høst 2018

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

Det er kreves 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.

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

• Det er ikke tillatt å linke mot et eksternt bibliotek som beregner FFT-en for deg.
  • Det er heller ikke tillatt å kopiere kode fra andre steder inn i eget prosjekt. Koden som skrives skal være ens egen.
• Det er tillatt å danne grupper på maks to (2) studenter.
• Det er tillatt å endre på kompileringsflaggene.

Utgitt kode

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}

• all bygger alle kodefiler.
• fft.o bygger objektfilen for FFT kildekoden.
• test bygger den kjørbare filen ./test, bruk denne for å overbevise deg selv at koden din gjør det den skal gjøre.
• bench bygger den kjørbare filen ./bench, bruk denne for å teste hastigheten på koden din manuelt. Dette kan gjøre det enklere å se små forbedringer som blir borte på grafen.
• run er en kommando som bygger alt og plotter kjøretid. Ved feil se til at run.sh er kjørbar (chmod +x run.sh).
• clean fjerner ting som er laget av denne Makefile-en, kan ofte være nyttig hvis ting ikke oppfører seg som du forventer.

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

$ sudo apt -y install gawk gnuplot libfftw3-dev

Hvordan dokumentere en forbedring

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

• Hva er den foreslåtte forbedringen?
  • Hvorfor burde dette forbedre kjøretiden?
  • Hvilken teori underbygger denne påstanden?
• Hvordan skal dette implementeres (forklar kort uten kode)
  • Hvis forbedringen er avhengig av et parameter (f.eks antall tråder) identifiser disse og dokumenter hvilke du testet.
  • Hvorfor fungerer eller ikke fungerer enkelte parametere?
• Hvordan svarer den faktiske kjøretiden til forventningene på forhånd?
  • Hvis det er en forskjell, kan du forklare dette på bakgrunn av teorien fra boken? Bruk gjerne eksterne kilder hvis de forklarer forskjellen bedre.

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

$ make test

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

$ make all
$ ./run.sh no-alloc.dat

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

$ gnuplot plot.p

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

• I den naive algoritmen så opprettes og slettes minne for hver eneste rekursjon, dette kan forbedres ved å heller aksessere minne in og out ved hjelp av en ekstra stride parameter slik det er beskrevet her. Husk at i C-kode så kan vi endre minnepekere direkte ved å legge til et tall på pekeren. Legg også merke til at in og out aksesseres i forskjellige mønstre, in aksesseres [x0, x2s, x4s,…] og [xs, xs + 2s, xs + 4s,…], mens out aksesseres [x0, x1, x2,…] og [x n/2, x n/2 + 1, x n/2 +2,…].

• Twiddle-faktorene (variabel w i den naive koden) kan optimaliseres ved å “cache” verdiene som vi beregner mange ganger. Dokumenter spesielt baksiden ved å implementere denne forbedringen. For å konstruere en liste til å lagre disse verdiene trenger du malloc og free et eksempel på bruk finner du i fft.c.

• Rekursjon kan være fordelaktig for å opprettholde cache-lokalitet, at minne aksesseringen vår ikke “hopper” frem og tilbake, men å rekursere helt ned til 2 gjenstående verdier er kanskje ikke optimalt. Denne forbedringen burde ta hensyn til antall verdier det er plass til i “nærmeste” cache-linje. Kapittel 8 forklarer mer om minne og minneaksesering, tenk spesielt over hva som skjer hvis vi henter verdier fra RAM, gjør noen beregninger, henter nye verdier, gjør noen beregninger for å deretter hente de første verdiene en gang til for å gjøre nye beregninger. I tillegg kan det være greit å vite at RPi-en har 64-byte cache-linjer, 32 kB nivå 1 cache og 512 kB nivå 2 cache.

• Siden prosessoren i RPi inneholder 4 kjerner som alle kan utføre arbeid samtidig kan man fordele arbeidet enten ved hjelp av pthreads eller OpenMP. Her er det viktig å tenke på at det faktisk er en kostnad ved å dele oppgaven mellom kjernene så kanskje det ikke alltid lønner seg å gjøre denne optimaliseringen. Se kapittel 7.7.7 for ytterligere forklaring.

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.

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 see Wikipedia.