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

• 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

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}

• 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 fra boken 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 se Wikipedia.