\addglos{MPix}{Kuvan koon yksikkö, megapikseli eli miljoona pikseliä.}

Algoritmin nopeutta arvioitiin eri alustoilla ja testikuvilla suoritettujen nopeusmittausten perusteella.
Nopeutta verrattiin aiempaan prototyyppiin, referenssitoteutukseen sekä julkaistuihin mittauksiin joidenkin laskentakirjastojen nopeuksista.

\section{Mittaustavat}
Toteutettua kirjastoa testattiin lyhyen C-kielisen testiohjelman avulla. Aiemman prototyypin nopeus pystyttiin vain arvioimaan, koska sen liittäminen testiohjelmaan olisi ollut vaikeaa. Lisäksi testauksessa käytettiin \code{perf}-ohjelmaa \cite{perf}\cite{perfwiki}, jolla pystyttiin tarkastelemaan prosessorin toimintaa tarkemmin.

\subsection{Testikuvat}
Testikuvina käytettiin digitaalikameran sarjavalotuksella otettua kuvasarjaa sekuntikellosta. Nämä kuvat muunnettiin kutakin testiä varten oikeaan kokoon ja värimuotoon.

\subsection{Testiohjelma}
Toteutetun optimoidun version sekä referenssitoteutuksen nopeus mitattiin C-kielisen testiohjelman avulla.
Testiohjelma lataa muistiin annetut kuvat ja suorittaa sitten algoritmin näille kuville.
Algoritmin käyttämä aika mitataan Linux-alustalla \code{gettimeofday}-funktiolla sekä Windows-alustalla \code{QueryPerformanceCounter}-funktiolla.

Kummankin mittaustavan tarkkuus on noin mikrosekunnin suuruusluokkaa ja kutsun käyttämä aika joitakin kymmeniä mikrosekunteja. Mittaukseen kulunut aika ei siis vaikuta merkittävästi algoritmin ajankäyttöön, joka on useita millisekunteja. Mittausten tarkkuus riippuu jonkin verran käytetystä alustasta, ja funktioissa voi esiintyä joskus ongelmia \cite{lee}. Tämän työn yhteydessä ei kuitenkaan tarvittu kovin suurta tarkkuutta, joten eri mittaustapojen analysointiin ei käytetty aikaa.

Testiohjelmaa käytettäessä käsiteltävät on ladattu valmiiksi muistiin algoritmia varten. Tämä vastaa todellista käyttötilannetta, jossa kuva olisi muistissa kameralta lukemisen jälkeen.

\subsection{Prototyypin arviointi}
\addglos{fps}{\emph{Frames Per Second} eli kuvaa sekunnissa, käsittelynopeudelle käytetty mittayksikkö.}
Mittausohjelman liittäminen aiempaan prototyyppiin olisi ollut työlästä, koska se on kiinteästi integroitu sovellusohjelmaan.
Sen vuoksi prototyypin nopeus piti arvioida sovellusohjelman nopeuden perusteella.

Kuvaa analysoitaessa suurin osa sovellusohjelman ajasta kului algoritmin suorittamiseen. Suurimmaksi nopeudeksi $320\times240$ pikselin kuvilla havaittiin 120~\useglos{fps}. Esimerkiksi $640\times480$ pikselin kuvilla sovellus pystyi enää noin 40~\useglos{fps} nopeuteen. Tämän perusteella prototyypin nopeudeksi arvioitiin 10--20~MPix/s. Nopeus pätee 8-bittisille harmaasävykuville, joka on ainoa prototyypin tukema kuvamuoto.

\subsection{Laskentajärjestyksen tehokkuuden arviointi}
Prosessorin välimuistin, liukuhihnan ja muiden osien tehokas käyttö voi vaikuttaa merkittävästi ohjelman nopeuteen.
Näitä arvioitiin Linuxin perf-työkalun avulla.
Työkalu hyödyntää Intelin prosessoreissa olevia performance monitoring events \cite[s. B-1]{intel_optimization} -laskureita. Nämä laskurit on integroitu suoraan prosessoriytimeen, joten niiden käyttö ei vaikuta ohjelman suoritukseen. Laskurien avulla saadaan tieto esimerkiksi siitä, montako ehdollista hyppyä ennustettiin väärin.

Tärkein tarkoitus näissä mittauksissa oli se, ettei toteutukseen jäisi mitään helposti korjattavaa pullonkaulaa. Jos esimerkiksi jossain kohdassa olisi havaittu suuri määrä välimuistista puuttuvia muistihakuja, olisi se voitu korjata lisäämällä sopiva käsky tiedon esihakemiseksi välimuistiin.

\subsection{Mittausten toisto}
Muiden sovellusten ja kuvadatan vaihtelun vaikutusten poistamiseksi jokainen testi ajettiin n. 200 kertaa, ja tuloksista otettiin mediaani. Keskiarvoa ei käytetty, sillä muiden ohjelmien vaatima aika voi hidastaa algoritmia hetkellisesti paljonkin. Tällöin keskiarvo vääristyisi ylöspäin.

Todellisen käytön kannalta on olennaista, kuinka nopeasti algoritmi toimii kuormitetulla koneella keskimäärin, toisin sanoen myös muiden ohjelmien vaikutus huomioiden. Ympäristöä on kuitenkin hyvin vaikea vakioida juuri tiettyyn kuormaan, joten se jätettiin pois näistä mittauksista.

\section{Laitteisto}
Varsinainen testi- ja käyttölaitteisto on pöytäkone, jossa on Windows~XP käyttöjärjestelmänä ja Intel Pentium Dual-Core E5300 2,60~GHz suoritin.
Lisäksi testit ajettiin samalla laitteistolla Ubuntu 9.10 -Linux-alustalla.

Liikkeen määrän, kuvan koon ja kääntäjäparametrien vaikutuksen sekä laskentajärjestyksen tehokkuuden arvioitiin käytetyt testit suoritettiin kannettavalla tietokoneella, jonka käyttöjärjestelmä on Debian GNU/Linux 5.0.4 ja suoritin Intel Core2 Duo T7300 2,00~GHz. Tarkemmat tiedot kummastakin laitteistosta ovat taulukossa \ref{tbl_hardware}.

\begin{table}[htb]
\caption{Mittauksissa käytetyt testilaitteistot.}
\label{tbl_hardware}
\begin{tabular}{l|rr}
\toprule
&Testilaite 1 (pöytäkone) & Testilaite 2 (kannettava)\\
\midrule
Suoritin & Intel Pentium Dual-Core E5300 & Intel Core2 Duo T7300\\
Kellotaajuus & 2,60~GHz & 2,00~GHz \\
Välimuisti & 2048~KiB & 4096~KiB \\
Keskusmuisti & 3~GiB & 2~GiB \\
Muistiväylän nopeus & 800~MHz & 800~MHz \\
\bottomrule
\end{tabular}
\end{table}

\section{Tulokset}
Mittaustulokset on järjestetty aliluvuiksi tarkastellun ominaisuuden mukaan. Ensimmäisessä osassa verrataan algoritmin eri toteutuksia toisiinsa, ja lopuissa keskitytään tässä työssä toteutettuun versioon.

\subsection{Toteutukset}
Työssä käsitellystä algoritmista on olemassa yhteensä kolme toteutusta: aiempi prototyyppi, sekä tässä työssä tehdyt referenssitoteutus ja optimoitu toteutus. Näiden nopeudet yhdellä testikuvasarjalla on esitetty taulukossa \ref{tbl_implementations}.

\begin{table}[htb]
\centering
\caption{Algoritmin eri toteutusten nopeudet. Testissä on käytetty $640\times480$ pikselin kokoisia 8-bittisiä harmaasävykuvia, viittä kuvapuskuria ja $3\times3$-sumennusta konvoluutiokernelinä.}
\label{tbl_implementations}
\begin{tabular}{lrrr}
\toprule
& Aiempi prototyyppi & Referenssitoteutus & Optimoitu toteutus \\
\midrule
Konvoluutio & -- & 54,4~ms & 1,1~ms \\
Keskihajonta & -- & 31,2~ms & 1,2~ms \\
Prosenttipiste & -- & 85,9~ms & 0,1~ms \\
\midrule
Yhteensä & -- & 171,5~ms & 2,3~ms \\
& n.10--20~MPix/s & 1,8~MPix/s & 134~MPix/s \\
\bottomrule
\end{tabular}
\end{table}

Taulukosta havaitaan, että referenssitoteutus on hitain ja optimoitu toteutus vastaavasti nopein. Erot eri toteutusten välillä ovat kymmenkertaisia, joten järjestys on selkeä vaikkei prototyypin nopeutta tunneta tarkasti.

Prototyypin nopeus verrattuna referenssitoteutukseen selittyy sillä, että prototyypin käyttämässä ohjelmointiympäristössä on valmiina nopea konvoluutiototeutus. Lisäksi referenssitoteutuksessa on useita ehtolauseita eri kuvaformaatteja varten, mitä aiempi prototyyppi ei tue.

Selkein ero referenssitoteutuksen ja optimoidun toteutuksen suhteellisissa ajoissa on prosenttipisteen hakemiseen kuluvassa ajassa. Referenssitoteutus käyttää C:n \code{qsort}-funktiota taulukon lajitteluun, kun taas optimoidussa toteutuksessa prosenttipiste haetaan histogrammista. Histogrammitaulukon läpikäynti on hyvin nopeaa, sillä sen koko on pieni suhteessa kuvien pikselimäärään.

Osatulosten laskenta-aikoja tarkasteltaessa on kuitenkin otettava huomioon, että optimoidussa toteutuksessa konvoluution yhteydessä suoritetaan myös keskihajonnan summien päivitys, ja keskihajonnan laskennan yhteydessä kerätään samalla histogrammitaulukko.

\subsection{Alustat ja kääntäjät}
Nopeuden riippuvuutta käytetystä kääntäjästä, käyttöjärjestelmästä ja laitteistosta testattiin samalla testikuvasarjalla kuin yllä toteutusten yhteydessä. Tulokset on esitetty kuvaajassa \ref{fig_platforms} sekä taulukossa \ref{tbl_platforms}.

\begin{figure}[h]
\newcommand{\makeboxes}[4]{
    \draw [convolution] (#1,0) rectangle +($(4mm,#2) + (0,#3) + (0,#4)$);
    \draw [deviation] (#1,0) rectangle +($(4mm,#3) + (0,#4)$);
    \draw [percentile] (#1,0) rectangle +(4mm,#4);
}

\newcommand{\makelabels}[4]{
    \draw [thick] ($(#1,0) + 0.5*(4mm,#2) + (0,#3) + (0,#4)$) -- +(1.5cm,0)
        node [at end, right] {Konvoluutio};
    \draw [thick] ($(#1,0) + 0.5*(4mm,#3) + (0,#4)$) -- +(1.5cm,0)
        node [at end, right] {Keskihajonta};
    \draw [thick] ($(#1,0) + 0.5*(4mm,#4) $) -- +(1.5cm,0)
        node [at end, right] {Prosenttipiste};
}
\centering
\begin{tikzpicture}
[x=2.5cm, y=1cm, node distance=0mm]
\tikzstyle{box}=[draw, thick, xshift=-2mm]
\tikzstyle{convolution}=[box, fill=white]
\tikzstyle{deviation}=[box, fill=black!30]
\tikzstyle{percentile}=[box, fill=black!70]
\tikzstyle{brace}=[decorate, decoration={brace,mirror,amplitude=2mm,raise=-2mm}]

\draw [xstep=1,ystep=0.5,help lines] (0,0) grid (4,5);
\draw (0,0) -- (4,0);
\draw [->] (0,0) -- (0,5.1);

\foreach \y in {0,1,2,3,4,5}
    \draw (0, \y) -- (-1mm, \y) node [left] {\y};

\node [above right, xshift=-2mm] at (0,5) {Suoritusaika (ms)};

\node [below, text width=5em, text centered] at (0.5,0) {Windows\\MSVC};
\node [below, text width=5em, text centered] at (1.5,0) {Windows\\MingW32};
\node [below, text width=5em, text centered] at (2.5,0) {Ubuntu\\GCC};
\node [below, text width=5em, text centered] at (3.5,0) {Debian\\GCC};
\draw [brace] (0,-12mm) -- (2.99,-12mm) node [midway,below] {Testilaite 1};
\draw [brace] (3.01,-12mm) -- (4,-12mm) node [midway,below] {Testilaite 2};

\makeboxes{0.5} {1.082} {1.210} {0.117};
\makeboxes{1.5} {1.181} {1.184} {0.045};
\makeboxes{2.5} {0.885} {0.950} {0.061};
\makeboxes{3.5} {1.095} {1.071} {0.055};

\makelabels{3.5} {1.095} {1.071} {0.055};

\begin{scope}
\clip (0,0) rectangle (4,5);
\path [xshift=1.25cm] plot [mark=+, only marks] file {plots/time-msvc};
\path [xshift=3.75cm] plot [mark=+, only marks] file {plots/time-mingw};
\draw [xshift=6.25cm] plot [mark=+, only marks] file {plots/time-ubuntu};
\draw [xshift=8.75cm] plot [mark=+, only marks] file {plots/time-acer};
\end{scope}
\end{tikzpicture}
\caption{Algoritmista toteutetun optimoidun version suoritusaika kuvaa kohti eri alustoilla ajettuna.
Kuvassa on esitetty eri osa-alueiden ajankäyttö.
Risteillä on merkitty kokonaissuoritusaika 20 mittauksesta, mikä havainnollistaa tulosten vaihteluväliä.}
\label{fig_platforms}
\end{figure}

\begin{table}[htb]
\centering
\caption{Optimoidun toteutuksen nopeus eri kääntäjillä ja alustoilla käytettynä.}
\label{tbl_platforms}
\begin{tabular}{rllrr}
\toprule
Testilaite & Käyttöjärjestelmä & Kääntäjä & Laskenta-aika & Nopeus \\
&&&(ms)&(MPix/s)\\
\midrule
1 & Windows XP & Microsoft Visual C++ & 2,3 & 134 \\
1 & Windows XP & MingW32 (GCC) & 2,2 & 139 \\
1 & Ubuntu Linux & GCC & 2,0 & 156 \\
2 & Debian GNU/Linux & GCC & 2,3 & 135\\
\bottomrule
\end{tabular}
\end{table}

Taulukon tulosten perusteella erot eri alustojen välillä ovat pieniä.
Testilaitteen 1 tulokset Ubuntussa olivat hieman muita paremmat, mutta ero selittynee taustakuorman määrällä. Ubuntu oli käynnistetty CD-levyltä eikä siten sisältänyt mitään ylimääräisiä ohjelmia, kun taas Windows oli ollut jo aiemmin käytössä ja taustalla oli muitakin ohjelmia.


\subsection{Liikkeen määrä}
Algoritmin nopeuden riippumista kuvien sisällöstä arvioitiin eri määrän muutoksia sisältävillä testikuvasarjoilla. Käytetyssä kuvasarjassa oli kymmenen kuvaa, joissa oli pohjana sama valokuva. Joka toisessa kuvassa tietty prosenttimäärä kuvan pikseleistä oli muutettu mustaksi. Kuvassa \ref{fig_changesize} on esitetty suoritusajan riippuvuus muutosten suuruudesta.

\begin{figure}[h]
\centering
\begin{tikzpicture}

\begin{axis}[x=1mm, y=2cm, ymin=0, ymax=3, xmax=101,
    ytick={0,0.5,1,1.5,2,2.5,3}, yticklabels={0,,1,,2,,3}, clip=false,
    ylabel={Suoritusaika (ms)}, xlabel={Muuttuvien pikselien osuus (\%)}]
% \node [above right, xshift=-5mm] at (0,3) {Suoritusaika (ms)};
% \node [below, yshift=-6mm] at (50,0) {Muuttuvien pikselien osuus (\%)};

\addplot [very thick] plot table [x index=0, y index=1] {plots/changesize};
\draw [thick] (current plot end) -- +(.5cm,-0.1cm) node [at end, right] {Konvoluutio};

\addplot [very thick] plot table [x index=0, y index=2] {plots/changesize};
\draw [thick] ($(current plot end) + (-9.8cm,0.1cm)$) -- ($(current plot end) + (0,.1cm)$) -- ($(current plot end) + (0.5cm,.2cm)$) node [at end, right] {Keskihajonta};

\addplot [very thick] plot table [x index=0, y index=3] {plots/changesize};
\draw [thick] (current plot end) -- +(.5cm,0) node [at end, right] {Prosenttipiste};

\addplot [very thick] plot table [x index=0, y index=4] {plots/changesize};
\draw [thick] (current plot end) -- +(.5cm,0) node [at end, right] {Kokonaisaika};

\end{axis}
\end{tikzpicture}
\caption{Algoritmin osa-alueiden suoritusaika kuvaa kohti, kun kuvassa tapahtuvien muutosten suuruus vaihtelee. Testissä haettu prosenttipiste oli 95~\%.}
\label{fig_changesize}
\end{figure}

Tulosten perusteella konvoluution suoritusaika ei riipu muutosten suuruudesta. Tämä oli odotettavissa, sillä konvoluutiossa tehdyt operaatiot eivät ole riippuvaisia kuvan sisällöstä.

Keskihajonnan ajankäytössä puolestaan on erikoinen 0.1~ms nousu pienimmillä muutosmäärillä. Tälle ei löytynyt mitään selkeää selitystä, mutta syy liittynee jotenkin prosessorin sisäiseen toimintaan juuri tässä tapauksessa. Ilmiö ei toistu, jos OpenMP-rinnakkaistus tai kääntäjän optimoinnit on kytketty pois.

Prosenttipisteen hakuun kuluva aika nousee selkeästi muutosten ylittäessä 5~\%. Tätä pienemmillä arvoilla haku päättyy heti histogrammin alkuun, eli pieniä varianssin arvoja vastaavaan kohtaan. Kun yli 5~\%:lla pikseleistä on suuri varianssin arvo, on myös 95~\% prosenttipisteen arvo suuri ja haku päättyy vasta histogrammitaulukon loppuosassa.

Algoritmin kokonaisajassa vaihtelut ovat kuitenkin pieniä. Algoritmin suoritusaika ei siten riipu merkittävästi testikuvasarjan sisällöstä.

\subsection{Kuvan koko}
Algoritmin suoritusaika on oletettavasti lineaarisesti riippuvainen kuvan sisältämien pikselien määrästä.
Sen vuoksi hyödyllisempää on tarkastella MPix/s-yksiköissä esitetyn nopeuden vaihtelua suhteessa kuvan kokoon.
Tulokset on esitetty kuvassa \ref{fig_imagesize}.

\begin{figure}[htb!]
\centering
\begin{tikzpicture}
\begin{semilogxaxis}[x=1cm, y=0.15mm, name=first,
    ymin = 0, ymax=400, xmax=101,
    ytick = {0, 100, 200, 300, 400},
    xtick = {0.01, 0.1, 1, 10, 100},
    xticklabels = { },
    ylabel={Laskentanopeus (MPix/s)}, clip=false
]
\addplot[mark=+,thick] plot table [x index=0, y index=1] {plots/imagesize};
\draw [thick] (current plot end) -- +(1cm,0) node [at end, right] {Konvoluutio};
\addplot[mark=x,thick] plot table [x index=0, y index=2] {plots/imagesize};
\draw [thick] (current plot end) -- +(1cm,0) node [at end, right] {Keskihajonta};
\addplot[mark=*,thick] plot table [x index=0, y index=4] {plots/imagesize};
\draw [thick] (current plot end) -- +(1cm,0) node [at end, right] {Yhteensä};
\end{semilogxaxis}
\begin{semilogxaxis}
[
    at={(first.south)}, anchor=north, yshift=-1cm,
    x=1cm, y=10cm,
    ymin = 0, ymax=0.2, xmax=101,
    ytick = {0,0.1,0.2}, yticklabels={{0,0}, {0,1}, {0,2}},
    xtick = {0.01, 0.1, 1, 10, 100},
    xticklabels = {{0,01}, {0,1}, 1, 10, 100},
    ylabel={Suoritusaika (ms)}, xlabel={Kuvan koko (MPix)}, clip=false,
    every axis x label/.style={at={(ticklabel cs:1,2mm), anchor=near ticklabel}, xshift=-10mm}
]
\addplot[mark=o,thick] plot table [x index=0, y index=3] {plots/imagesize};
\draw [thick] (current plot end) -- +(1cm,0) node [at end, right] {Prosenttipiste};

\draw [help lines] (axis cs: 0.0768,0) -- +(0,-0.5cm) node [at end, below] {$320\times240$};
\draw [help lines] (axis cs: 0.307,0) -- +(0,-1cm) node [at end, below] {$640\times480$};
\draw [help lines] (axis cs: 2.0736,0) -- +(0,-1.5cm) node [at end, below] {$1920\times1080$};
\end{semilogxaxis}
\end{tikzpicture}
\caption{Algoritmin suoritusaika ja nopeus eri kokoisilla neliön muotoisilla harmaasävykuvilla. Sivun pituus on testipisteissä jaollinen 16:lla.
Konvoluution ja keskihajonnan suoritusaika on likimain suoraan verrannollinen kuvan kokoon, minkä vuoksi niiden nopeus on esitetty MPix/s-yksikössä.
Prosenttipisteen suoritusaika taas on likimain vakio.}
\label{fig_imagesize}
\end{figure}

Kuvaajan perusteella algoritmin kokonaissuoritusnopeus on yli 0,1~megapikselin kuvilla likimain vakio.
Pienikokoisilla kuvilla suoritusnopeus laskee, mikä johtuu luultavasti lähinnä reunatarkistuksiin kuluvasta ajasta ja kiinteäaikaisista toimenpiteistä, kuten säikeiden käynnistyksestä.
Osa-alueiden suhteelliset nopeudet kuitenkin vaihtelevat myös suurikokoisilla kuvilla.

Konvoluutio hidastuu kuvakoon ylittäessä 1~MPix. Tämä johtuu luultavasti ensimmäisen tason välimuistin täyttymisestä, sillä konvoluutio tarvitsee laskennassa nykyisen rivin lisäksi myös edellisiä ja seuraavia rivejä. Rivin pituuden kasvaessa kaikki tarvittavat rivit eivät mahdu yhtäaikaisesti välimuistiin.

Keskihajonta puolestaan nopeutuu suurikokoisilla kuvilla. Välimuistin täyttyminen ei vaikuta yhtä merkittävästi keskihajonnan laskentaan, koska summataulukoista tarvitaan aina kerrallaan vain yhtä riviä.
Laskennassa on kuitenkin joitakin kiinteäaikaisia osuuksia: histogrammitaulukon alustus nollaksi vie noin 0,2~ms, ja lisäksi aikaa kuluu säikeiden käynnistykseen.
Kuvakoon kasvaessa kiinteäaikaisten toimintojen osuudet per pikseli pienenevät, mistä aiheutuu havaittu nopeutuminen.

Prosenttipisteen hakuun kuluva aika nousee kuvakoon kasvaessa. Histogrammitaulukon koko on kuitenkin vakio, joten sen läpikäyntiin kuluvan ajan ei pitäisi muuttua.
Todennäköisin selitys havaitulle muutokselle on välimuistin täyttyminen. Pienikokoisilla kuvilla histogrammitaulukko pysyy välimuistissa kokonaan, koska muuta tietoa on vähän.
Suurilla kuvilla keskihajontaa laskettaessa harvinaisempia varianssin arvoja vastaavat histogrammitaulukon arvot poistuvat välimuistista, jolloin prosenttipisteen haku kestää kauemmin.

\subsection{Kuvan leveys}
Algoritmi käsittelee kuvaa 16 tavun lohkoissa, joten jos kuvan leveys ei ole jaollinen 16:lla, joudutaan jokaisen rivin lopussa suorittamaan erikoistapaus tätä varten.
Lisäksi prosessorin muistihaut ovat tehokkaimpia, kun muistiosoite on jaollinen 4:llä tavulla, eli 32 bitillä. Tämä aiheutuu dataväylän leveydestä.
Kuvassa \ref{fig_imagewidth} on esitetty laskenta-aika suhteessa kuvan leveyteen.

\begin{figure}[htb!]
\centering
\begin{tikzpicture}

\begin{axis}[x=5mm, y=1cm, ymin=0, ymax=4,
    ytick={0,0.5,1,1.5,2,2.5,3,3.5,4}, yticklabels={0,,1,,2,,3,,4}, clip=false,
    ylabel={Suoritusaika (ms)}, xlabel={Kuvan leveys (pikseliä)}]
\addplot [mark=+, thick] plot table [x index=0, y index=1] {plots/imagewidth};
\draw [thick] (current plot end) -- +(.5cm,0) node [at end, right, yshift=1mm] {Konvoluutio};

\addplot [mark=x, thick] plot table [x index=0, y index=2] {plots/imagewidth};
\draw [thick] (current plot end) -- +(.5cm,0) node [at end, right, yshift=-1mm] {Keskihajonta};

\addplot [mark=o, thick] plot table [x index=0, y index=3] {plots/imagewidth};
\draw [thick] (current plot end) -- +(.5cm,0) node [at end, right] {Prosenttipiste};

\addplot [mark=*, thick] plot table [x index=0, y index=4] {plots/imagewidth};
\draw [thick] (current plot end) -- +(.5cm,0) node [at end, right] {Kokonaisaika};
\end{axis}
\end{tikzpicture}
\caption{Algoritmin suoritusajan riippuvuus kuvan leveydestä. Testi on suoritettu harmaasävykuvilla, eli kuvan leveys on samalla yhden rivin koko tavuissa.}
\label{fig_imagewidth}
\end{figure}

Kuvaajan perusteella suurin vaikutus on leveyden parillisuudella.
Sen sijaan ero 8:lla ja 16:lla jaollisten leveyksien välillä on pieni.
Tämän perusteella suurin vaikutus on muistihakujen osoitteilla, johon verrattuna SSE2-lohkojen tasan meneminen ei merkitse paljoa.
Tämä on ymmärrettävää, sillä muistihaut vaikuttavat jokaisen pikselin käsittelyyn, kun taas lohkojen tasan meneminen vaikuttaa vain rivin lopussa.

Konvoluution yhteydessä suoritetaan aina muistihakuja myös parittomista osoitteista. Sen vuoksi jatko-optimoinnissa voitaisiin arvioida, nopeutuisiko laskenta lataamalla lohkot aina tasan jaollisista osoitteista. Tällöin lataamisen jälkeen lohkoa täytyisi muokata vielä bittisiirroilla.

\subsection{Kuvatyypit}
Taulukossa \ref{tbl_imagetype} on esitetty algoritmin nopeus eri kuvatyypeillä.
Keskihajonnan ja prosenttipisteen suoritusaika riippuu siitä, kuinka monelle värikanaville sovellusohjelma haluaa keskihajonnan laskea.
Konvoluutio taas suoritetaan aina kaikille värikanaville.

\begin{table}[h]
\centering
\caption{Algoritmin nopeus eri kuvatyypeillä. Testikuvan koko oli $640\times480$.}
\label{tbl_imagetype}
\begin{tabular}{lrrrr}
\toprule
Kuvatyyppi & Konvoluutio & Keskihajonta & Prosenttipiste & Yhteensä \\
 & (ms) & (ms) & (ms) & (ms) \\
\midrule
Harmaasävy & 1,1 & 1,2 & 0,05 & 2,4 \\
RGB24 & 4,9 & $3\cdot2,2$ & $3\cdot0,05$ & 11,7 \\
(A)RGB32 & 5,3 & $4\cdot2,2$ & $4\cdot0,03$ & 14,2 \\
\bottomrule
\end{tabular}
\end{table}

Taulukon perusteella suoritusaika kuusinkertaistuu RGB32-kuvilla harmaasävykuviin verrattuna.
Pelkästään kuvan koosta odotettavissa oleva muutos olisi nelinkertaistuminen, joten algoritmi hidastuu yllättävän paljon.
Keskihajonnan osalta hidastuminen johtuu luultavasti siitä, että keskihajonta lasketaan erikseen jokaiselle värikanavalle.
Tällöin summataulukot täytyy käydä läpi pätkittäin, koska eri värikanavien pikseliarvot ovat limittäin.

\subsection{Kääntäjäparametrit}
Eri kääntäjäoptimointien vaikutus algoritmin nopeuteen on esitetty taulukossa \ref{tbl_gccopts}.
Testit on suoritettu GCC:llä, ja muissa testeissä käytetyt käännösparametrit ovat taulukon viimeinen eli nopein vaihtoehto.

\begin{table}[h]
\centering
\caption{Algoritmin nopeus GCC:n eri käännösparametreilla. Kaikissa kohdissa on lisäksi mukana \code{-march=pentium4} SSE2-käskyjen käyttöönsaamiseksi.}
\label{tbl_gccopts}
\begin{tabular}{lrrrr}
\toprule
Kääntäjän parametrit & Konvoluutio & Keskihajonta & Prosenttipiste & Yhteensä \\
 & (ms) & (ms) & (ms) & (ms) \\
\midrule
\code{-O0} & 22,3 & 13,5 & 0,19 & 36,4 \\
\code{-O1} & 2,3 & 3,2 & 0,11 & 6,1 \\
\code{-O2} & 2,2 & 2,6 & 0,10 & 5,0 \\
\code{-O3} & 2,2 & 2,2 & 0,06 & 4,5 \\
\code{-O3 -fopenmp} & 1,1 & 1,2 & 0,05 & 2,4 \\
\bottomrule
\end{tabular}
\end{table}

Kääntäjän optimoinneilla on selvä vaikutus algoritmin nopeuteen. Eniten nopeutuu konvoluutio, mikä onkin ohjelmakoodin kannalta monimutkaisin osuus. Merkittävä osa nopeutuksesta \code{-O0} ja \code{-O1} -tasojen välillä johtuu luultavasti \code{inline}-funktioista, joita koodissa on käytetty sen selkeyttämiseksi.
Kun optimoinnit on kytketty pois \code{-O0}:lla, kuluu huomattavasti aikaa näiden apufunktioiden kutsumiseen.

Rinnakkaistamisen kytkeminen päälle \code{-fopenmp}:llä lähes kaksinkertaistaa nopeuden. Algoritmi siis rinnakkaistuu tehokkaasti, ja hyödyntää molemmat prosessoriytimet.

\subsection{Laskentajärjestys}
Taulukossa \ref{tbl_events} on esitetty mittaustulokset, joiden perusteella arvioitiin algoritmin tehokkuutta välimuistin ja hyppyjen ennustuksen kannalta. Tuloksissa ei havaittu merkittäviä ongelmakohtia, joten muutoksia mittaustulosten perusteella ei tehty.

\addglos{L2-välimuisti}{Prosessorin toisen tason välimuisti. Intelin nykyisissä prosessoreissa se on samalla myös viimeisen tason välimuisti, eli siitä puuttuvat muistihaut viedään ulkoiselle muistille.}
\begin{table}[h]
\centering
\caption{Prosessorin tapahtumalaskureiden avulla mitatut tiedot ohjelman suorituksesta.
Testissä käytettiin kymmentä $640\times480$ harmaasävykuvaa, eli suoritusaika oli 24~ms.}
\label{tbl_events}
\begin{tabular}{lr}
\toprule
Tapahtuma & Lukumäärä \\
\midrule
Kellojaksot & 101~500~000\\
\midrule
Muistihaut yhteensä & 63~850~000\\
Muistihaut L2-välimuistista & 935~000\\
Muistihaut, jotka puuttuvat L2-välimuistista & 9~180\\
\midrule
Ehdolliset hypyt & 17~300~000\\
Väärin ennustetut hypyt & 103~680\\
\bottomrule
\end{tabular}
\end{table}

Viimeisen tason välimuistista puuttuvat muistihaut aiheuttavat sen, että prosessori joutuu odottamaan tiedon hakemista ulkoisesta muistista.
Tämä on hidasta verrattuna prosessorin normaaliin suoritusnopeuteen.
Testatulla prosessorilla, jossa on 800~MHz muistiväylä ja 2~GHz kellotaajuus, ulkoisen muistin käsittely vie noin 70 prosessorin kellojaksoa \cite[s. 2-59]{intel_optimization}.
Lisäksi viimeisen tason välimuistin käsittely vie 14 kellojaksoa.

Taulukon muistihakuihin kuluva aika on siis
$(935~000\cdot14 + 9~180\cdot70)/(2\text{ GHz})\approx6,9\text{ ms}$.
Tämä on melko suuri osuus 24~ms kokonaissuoritusajasta, mutta muistihakujen viivettä on mahdoton poistaa täysin.
Siksi muistihakujen jatko-optimoinnilla ei pystyttäisi saavuttamaan kovin merkittävää nopeutusta suhteessa työmäärään.

Korkean tason ohjelmointikielten ehtorakenteet, kuten \code{if}-lauseet, toteutetaan ehdollisilla hyppykäskyillä.
Prosessorit pyrkivät ennustamaan nämä hypyt edellisten suorituskertojen perusteella, jotta prosessorin liukuhihna toimisi tehokkaasti. Testatulla prosessorilla liukuhihna on 18 käskyn pituinen \cite[s. 2-7]{intel_optimization}, joten väärin ennustettuun hyppyyn kuluva aika on enimmillään 18 kellojakson suuruusluokkaa \cite[s. 2-39]{intel_optimization}.

Taulukon hyppyihin kuluva aika on $(103~680\cdot18)/(2\text{ GHz})\approx0,9\text{ ms}$.
Tämä aika on lähes olematon suhteessa kokonaissuoritusaikaan, joten hyppyjen optimoiminen ei ole tässä tapauksessa hyödyllistä.

\section{Tulosten vertailua}
Algoritmin nopeutta voi arvioida vertaamalla sitä esimerkiksi Intel Integrated Performance Primitives -kirjaston nopeuteen. Intelin kirjastossa on toteutukset keskihajonnan ja konvoluution laskentaan, joita voitaisiin verrata vastaaviin osuuksiin tässä työssä. Vertailun suorittaminen vaatisi kuitenkin sopivan testiohjelman rakentamisen, joten sitä ei tämän työn puitteissa tehty.

NVidian CUDA on näytönohjainlaskentaan tarkoitettu kirjasto. NVidia on julkaissut esimerkin sen avulla toteutetusta konvoluutiosta \cite{cuda_convolution}. Siinä RGB-kuville saavutettu nopeus $3\times3$-kernelillä oli noin 2~000~MPix/s. Tässä työssä tehdyn konvoluutioalgoritmin nopeus RGB-kuvilla on 63~MPix/s, mutta lukuun sisältyy myös varianssin summapuskurien päivitys.
Joka tapauksessa näytönohjainlaskennalla pystyttäisiin selvästi nopeuttamaan algoritmia, ainoana haittapuolena huono yhteensopivuus eri laitteistojen kanssa.
