\documentclass[12pt,a4paper,finnish]{tutthesis}

\usepackage{icomma}
\usepackage{subfigure}

\usepackage{afterpage}
\usepackage{pslatex}
\usepackage[finnish]{babel} % tavutus suomeksi, vaihda jos eri kieli
\usepackage[hang,up,bf]{caption}% kuvatekstien kirjasinkoko ja asettelu
\renewcommand{\captionfont}{\em\normalsize}
\pagenumbering{Roman}

\usepackage{amsmath}
\usepackage{amsthm}

\usepackage{enumerate}
\usepackage{lastpage}
\usepackage{tikz}
\usepackage{pgfmath}
\usepackage{pgfplots}
\usetikzlibrary{matrix}
\usetikzlibrary{positioning}
\usetikzlibrary{calc}
\usetikzlibrary{backgrounds}
\usetikzlibrary{chains}
\usetikzlibrary{shapes.geometric}
\usetikzlibrary{fit}
\usetikzlibrary{snakes}
\usetikzlibrary{plotmarks}
\usepgfplotslibrary{dateplot}

\tikzset{help lines/.style={draw=black!15}}
\pgfplotsset{every axis/.style={grid=major,
    axis x line=bottom, axis y line=left},
    every axis y label/.style={
        at={(rel axis cs:0,1)}, anchor=south west, xshift=-2mm
    }
}
\pgfkeys{/pgf/number format/.cd,
    set thousands separator = {~}, set decimal separator = {,}
}

\usepackage{booktabs}
\setlength{\heavyrulewidth}{1.1pt}

\usepackage{hyperref}
\hypersetup{
    colorlinks,%
    citecolor=black,%
    filecolor=black,%
    linkcolor=black,%
    urlcolor=black,%
    bookmarksnumbered=true
}
\usepackage{cite}

\usepackage[number=none,style=list]{glossary}

\usepackage{float}
\newfloat{program}{bp}{lop}[chapter]
\floatname{program}{Listaus}

\newcommand{\code}[1]{\texttt{#1}}

% Pilkut matikkatilassa parempaan kohtaan
\let\oldprime\prime
\renewcommand{\prime}{\kern1pt\lower3pt\hbox{$\scriptstyle\oldprime$}}

% Subfiguren referenssit
\renewcommand{\thesubfigure}{\alph{subfigure}}
\makeatletter
%   \renewcommand{\p@subfigure}{}
  \renewcommand{\@thesubfigure}{\alph{subfigure})\hskip\subfiglabelskip}
\makeatother

\makeglossary

\renewcommand{\beforeglossary}{
    \setlength{\leftmargini}{4em}
    \begin{description}\labelwidth=4em \itemindent=0em
}

\newcommand{\addmglosb}[3]{\storeglosentry{#1}{sort={#1}, name={#2}, description={#3}}}
\newcommand{\addmglos}[2]{\storeglosentry{#1}{name={#1}, description={#2}}}
\newcommand{\addglos}[2]{\storeglosentry{#1}{name={#1}, description={\mbox{}\\#2}}}
\newcommand{\useglos}[1]{\useGlosentry{#1}{#1}}

\newcommand{\longbracetext}[1]{\text{\hbox to 0cm{\hss{#1}\hss}}}


\begin{document}
% Vähennetään ylenpalttista tavutusta
\hyphenpenalty=6000
\tolerance=2000

% Matikan rivitys
\relpenalty=1000
\binoppenalty=3000

\raggedbottom
\addtolength{\topskip}{0pt plus 3cm}

\pdfbookmark{Alkusivu}{Alkusivu}

\author{Petteri Aimonen}

\thispagestyle{empty}

\vspace*{-.5cm}\noindent
\includegraphics[width=8cm]{TTY_logo_suomi}

\vspace{6.8cm}

\noindent{\bf\large \textsf{Petteri Aimonen}}\\
{\bf\large \textsf{Videokuvan keskihajonnan laskennan nopeusoptimointi\\SSE2-käskykannan avulla}}\\
\textsf{Kandidaatintyö}

\vspace{6.7cm} % jos kaksi otsikkoriviä vaihda -> 6.7cm

\begin{flushright}
  
\begin{minipage}[c]{6.8cm}
\begin{spacing}{1.0}
\textsf{Tarkastaja: Erno Salminen}\\
\end{spacing}
\end{minipage}
\end{flushright}

\newpage
\pdfbookmark{Tiivistelmä}{Tiivistelmä}
\chapter*{TIIVISTELMÄ}
\begin{spacing}{1.0}
\textsf{TAMPEREEN TEKNILLINEN YLIOPISTO}\\
\textsf{Signaalinkäsittelyn ja tietoliikennetekniikan koulutusohjelma}\\
{\bf \textsf{PETTERI AIMONEN: Videokuvan keskihajonnan laskennan nopeusoptimointi SSE2-käskykannan avulla}}\\
\textsf{Kandidaatintyö, 51 sivua, ei liitesivuja}\\
\textsf{Toukokuu 2010}\\
\textsf{Pääaine: Digitaali- ja tietokonetekniikka}\\
\textsf{Tarkastajat: Erno Salminen}\\
\textsf{Avainsanat: SSE2-käskykanta, OpenMP, optimointi, nopeusoptimointi, konvoluutio, keskihajonta, prosenttipiste}\\
\end{spacing}

\noindent
Tämä kandidaatintyö käsittelee videokuvan käsittelyyn liittyvän algoritmin nopeuttamista.
Työn pohjana olevasta algoritmista on valmis prototyyppi, johon saavutettua nopeutta verrataan.
Algoritmin tarkoitus on mitata videokuvassa tapahtuvien muutosten suuruutta.
Algoritmi laskee videokuvasta pikselikohtaisen keskihajonnan edellisten kuvien ajalta, ja keskihajonnan arvoista prosenttipisteen. Lisäksi kuvat suodatetaan konvoluutiolla ennen laskentaa.

Optimoinnissa käytettiin prosessorin SSE2-käskykantaa (engl. Streaming SIMD Extensions~2), joka on eräs SIMD-periaatteen (engl. Single Instruction Multiple Data) toteutus. SSE2-käskyt suorittavat saman operaation usealle luvulle, jolloin prosessori pystyy käsittelemään tietoa nopeammin kuin yksi lukuarvo kerrallaan.
Lisäksi laskenta rinnakkaistettiin usealle prosessorille ja laskentatapaa parannettiin tutkimalla algoritmia matemaattisesti.

Mittaustulosten perusteella algoritmin nopeus noin kymmenkertaistui verrattuna aiempaan prototyyppiin.
Tämän vertailun lisäksi mittausten avulla tutkittiin nopeuden riippuvuutta kuvien koosta, liikkeen määrästä ja muista tekijöistä. Yhteenvedossa on esitetty projektin eteneminen, työmäärä ja eri optimointitapojen vaikutus.

\newpage
\pdfbookmark{Abstract}{Abstract}
\chapter*{ABSTRACT}
\begin{spacing}{1.0}
\textsf{TAMPERE UNIVERSITY OF TECHNOLOGY}\\
\textsf{Master's Degree Programme in Signal Processing and Communications Technology}\\
{\bf \textsf{PETTERI AIMONEN: Using SSE2 instruction set for speed optimizing the calculation of standard deviation from video image.}}\\
\textsf{Master of Science Thesis, 51 pages, no appendix pages}\\
\textsf{May 2010}\\
\textsf{Major: Digital and Computer Systems}\\
\textsf{Examiner: Erno Salminen}\\
\textsf{Keywords: SSE2 instruction set, OpenMP, optimizing, speed optimizing, convolution, standard deviation, percentile}\\
\end{spacing}

\noindent 
This Master of Science Thesis focuses on speeding up a video processing algorithm.
There is an existing prototype of the algorithm in question, which is used for comparing the achieved performance.
The purpose of the algorithm is to measure the amount of movement in video image.
The algorithm calculates the per-pixel standard deviation over a number of past frames in video image, and then calculates a specified percentile of the deviation results. Additionally, the images are filtered with convolution prior to other calculations.

The primary method used in optimizing is the SSE2 (Streaming SIMD Extensions~2) instruction set, which is an implementation of the SIMD (Single Instruction Multiple Data) principle. The SSE2 instructions perform the same operation to multiple values, so that the processor can process information more efficiently than when calculating a single value at a time. In addition, the calculation was parallelized to multiple processor cores and the algorithm was modified using mathematical insight.

Based on measurement results, the speed of the algorithm increased tenfold compared to the earlier prototype.
Measurements were also used to study the effect of image size, amount of movement and other factors on the speed. The conclusion presents the progress of the project, amount of work involved and the effect of various optimization methods.

% \newpage
% \pdfbookmark{Alkusanat}{Alkusanat}
% \chapter*{ALKUSANAT}

\newpage
\renewcommand\contentsname{Sisällys} % poista jos kieli muu kuin suomi
\pdfbookmark{Sisällys}{Sisällys}
\tableofcontents
%\newpage
%\listoffigures
%\listoftables
\newpage
\pdfbookmark{Termit ja symbolit}{Termit ja symbolit}
\renewcommand{\glossaryname}{Termit ja symbolit}
\printglossary


\newpage
\renewcommand{\chaptermark}[1]{\markboth{\thechapter. \ #1}{}}
\renewcommand{\sectionmark}[1]{\markright{}{}}
\lhead{\fancyplain{}{\leftmark}}

% Tästä alkaa varsinainen teksti
\pagenumbering{arabic}

\chapter{Johdanto}
\addglos{MPix/s}{Käsittelynopeudelle käytetty mittayksikkö, megapikseliä sekunnissa.}
\addglos{SSE2}{\emph{Streaming SIMD Extensions 2}, Intelin kehittämä käskykantalaajennos SIMD-laskentaa varten}
\addglos{SIMD}{\emph{Single Instruction Multiple Data}, prosessorien käskytyyppi jossa sama operaatio suoritetaan usealle luvulle yhdellä käskyllä}
Tämä kandidaatintyö käsittelee videokuvan käsittelyyn liittyvän algoritmin nopeuttamista. Työn pohjana on aiemmin suunniteltu algoritmi, josta on toimiva prototyyppi jonka toimintaa halutaan nopeuttaa. Käsiteltävän järjestelmän rakenne on esitetty kuvassa \ref{fig_ymparisto}.

\begin{figure}[htb]
\centering
\begin{tikzpicture}
[node distance=2mm]

\tikzstyle{innerblock} = [draw, text centered];
\tikzstyle{outerblock} = [draw, rounded corners];

\node [innerblock, text width=10em] (kaappaus) {Kuvan kaappaus kameralta reaaliajassa};
\node [innerblock, text width=10em, below=of kaappaus] (kasittely) {Toimenpiteet kuvassa tapahtuvien muutosten perusteella};
\node [text width=10em, text centered, above=of kaappaus] (softaotsikko) {\textbf{Sovellusohjelma}\\(toteutettu aiemmin)};
\node [outerblock, fit=(kaappaus) (kasittely) (softaotsikko)] (softabox) {};

\tikzset{node distance=5mm}

\node [innerblock, node distance=3cm, right=of kaappaus] (konvoluutio) {Konvoluutio\-suodatus};
\node [innerblock, node distance=3cm, right=of kasittely] (prosenttipiste) {Prosenttipiste};
\node [innerblock, right=of prosenttipiste] (keskihajonta) {Keskihajonta};
\node [coordinate] at ($(keskihajonta)!0.5!(prosenttipiste)$) (temp) {};
\node [text width=14em, text centered] at (softaotsikko-|temp) {\textbf{Algoritmikirjasto}\\(toteutetaan tässä työssä)};
\node [outerblock, fit=(softaotsikko.north-|konvoluutio.west) (kasittely.south-|keskihajonta.east)] (algobox) {};

\draw [->,thick] (kaappaus)--(konvoluutio) node [midway, above] {Kuva};
\draw [->,thick] (konvoluutio)-|(keskihajonta);
\draw [->,thick] (keskihajonta)--(prosenttipiste);
\draw [->,thick] (prosenttipiste)--(kasittely) node [midway, above] {Lukuarvo};
\end{tikzpicture}
\caption{Työssä toteutettavan algoritmikirjaston toimintaympäristö ja perusrakenne.}
\label{fig_ymparisto}
\end{figure}

Algoritmi koostuu kolmesta pääalueesta: kuvan konvoluutiosuodatuksesta, pikselikohtaisen keskihajonnan laskennasta sekä keskihajonnan halutun prosenttipisteen laskennasta. Laskenta on luonteeltaan helposti rinnakkaistuva, joten käytettäväksi menetelmiksi soveltuvat rinnakkaiseen laskentaan perustuvat \useglos{SSE2}-käskykanta (engl. Streaming SIMD Extensions 2) ja monen prosessoriytimen käyttö.

Aiempi prototyyppi on toteutettu erityistä signaalinkäsittelyn laskentaohjelmaa käyttäen.
Tässä työssä toteutettavasta versiosta halutaan yhteensopiva eri alustojen kanssa, joten toteutuskieleksi valittiin C. Eri toteutusalustasta huolimatta järjestelmän muihin osiin tehtävät muutokset on tarkoitus pitää vähäisinä, joten algoritmin rajapinta tehdään samanlaiseksi kuin prototyypissä.

Algoritmia käytetään perustasoisella uudella tietokoneella, jonka prosessori on esimerkiksi Intel Pentium Dual-Core E5300 2,60~GHz.
Aiemman prototyypin nopeus on ollut harmaasävykuvilla n. 10~MPix/s (megapikseliä sekunnissa).
Tavoitteena on saavuttaa optimoinnin jälkeen 40~MPix/s laskentanopeus.

Luvussa \ref{ch_menetelmät} esitellään lyhyesti optimoinnissa käytettävät menetelmät ja luvussa \ref{ch_esittely} käsitellyn algoritmin rakenne.
Kunkin algoritmin osa-alueen optimointi on esitelty luvuissa \ref{ch_konvoluutio}, \ref{ch_keskihajonta} ja \ref{ch_prosenttipiste}.
Luvussa \ref{ch_tulokset} on arvioitu toteutusta nopeusmittausten perusteella ja luvussa \ref{ch_yhteenveto} on yhteenveto tuloksista ja projektin etenemisestä.

\chapter{Käytettävät menetelmät}
\label{ch_menetelmät}

Tässä luvussa on esitelty käytettäväksi harkitut työkalut, kuten kääntäjä ja lisäkirjastot, sekä käytetyt optimointimenetelmät. Lisäkirjastoja tai näytönohjainlaskentaa ei lopulta käytetty toteutuksessa.

\section{Kääntäjät}
\addglos{Microsoft Visual C++}{Microsoftin C-kääntäjä Windows-alustalle}
\addglos{GCC}{\emph{GNU C Compiler}, GNU-projektin C-kääntäjä, joka on saatavilla usealle alustalle}
\addglos{OpenMP}{\emph{Open Multi-Processing}, usean kääntäjävalmistajan tukema rajapinta rinnakkaislaskentaan}
Algoritmi toteutetaan C-kielellä ja kääntäjinä käytetään \useglos{Microsoft Visual C++}:aa
sekä \useglos{GCC}:tä (engl. GNU C Compiler). Näin saavutetaan hyvä siirrettävyys eri alustoille pienellä työmäärällä, sillä kummassakin kääntäjässä on tuki \useglos{OpenMP}-rinnakkaislaskennalle (engl. Open Multi-Processing) sekä SSE2:n käytölle. Eroja on lähinnä joissakin syntaksiseikoissa.

\section{Apukirjastot}
On olemassa valmiita kirjastoja, jotka sisältävät optimoituja aliohjelmia yleisiin tarpeisiin.
Tällaisia ovat esimerkiksi Intel Integrated Performance Primitives ja liboil.
Valmiiden kirjastojen käyttö helpottaa ohjelmointia, ja on useissa tapauksissa järkevä vaihtoehto.

Tässä työssä ei kuitenkaan käytetty valmiita kirjastoja, sillä niistä olisi voitu hyödyntää lähinnä pelkkä konvoluutiolaskenta.
Muilta osin valmiiden kirjastojen käyttö olisi rajoittanut saavutettavaa nopeutta, sillä esimerkiksi kokonaislukulaskentaan tai liukuvan ikkunan käyttöön perustuvat menetelmät olisi ollut vaikea toteuttaa tehokkaasti.

\section{Kokonaislukulaskenta}
Kaikki nopeuskriittinen laskenta suoritetaan toteutuksessa kokonaisluvuilla.
Kokonaislukuoperaatiot ovat bittileveydestä ja käskystä riippuen noin 2--8 kertaa nopeampia kuin vastaavat liukulukuoperaatiot \cite[s. C-9, C-18]{intel_optimization}.

Kokonaislukulaskenta soveltuu tähän algoritmiin hyvin, sillä käsiteltävät pikseliarvot ovat joka tapauksessa kokonaislukuja.
Joissakin kohdissa kokonaislukujen käyttö vaatii kuitenkin erityistä huomiota lukualueiden ja pyöristyksen osalta.

\section{SSE2-käskykanta}
SSE2-käskykanta on työpöytätietokoneiden \emph{x86}-prosessoreiden käskykannan
laajennos, joka sisältää \useglos{SIMD}-käskyjä (engl. Single Instruction Multiple Data).
Nämä käskyt ovat käytettävissä Intelin prosessoreissa vuoden 2000 Pentium 4-mallista alkaen
\cite[s. 2-4]{intel_volume1},
sekä AMD:n prosessoreissa vuoden 2003 Opteron- ja Athlon 64 -malleista alkaen
\cite{amd_athlon64}\cite{amd_opteron}.

SIMD-käskyissä prosessori suorittaa yhdellä käskyllä saman operaation monelle
lukuarvolle, SSE2:n tapauksessa enimmillään 16 luvulle. Käsiteltävät luvut
on pakattu samaan 128-bittiseen rekisteriin, ja niiden bittimäärä voi olla
kokonaislukujen tapauksessa joko 8, 16 tai 32. Lisäksi SSE2 sisältää käskyjä
32- ja 64-bittisten liukulukujen käsittelyyn. Käsiteltävien lukujen määrä riippuu
suoraan niiden bittimäärästä, esimerkiksi 16-bittisiä lukuja voidaan käsitellä
8 luvun ryhmissä. Periaate on esitetty kuvassa \ref{fig_simd}.

\begin{figure}[htb]
\centering
\begin{tikzpicture}
[node distance=5mm]
\tikzstyle{register}=[matrix of nodes, inner sep=0mm,
    every node/.style={draw, minimum width=6.5mm, inner sep=1mm, font=\scriptsize}]

\matrix [register] (input1)
{
 10 & 20 & 30 & 40 & 50 & 60 & 70 & 80 & 90 & 100 & 110 & 120 & 130 & 140 & 150 & 160\\
};
\matrix [register, below=of input1] (input2)
{
 10 & 10 & 10 & 10    & 10 & 10 & 10 & 10    & 10 & 10 & 10 & 10    & 10 & 10 & 10 & 10 \\
};

\node [right=of input2] (sum) {SIMD-yhteenlasku};

\matrix [register, node distance=10mm, below=of input2] (result)
{
 20 & 30 & 40 & 50 & 60 & 70 & 80 & 90 & 100 & 110 & 120 & 130 & 140 & 150 & 160 & 170\\
};

\draw [->,thick] (input1)-|(sum);
\draw [->,thick] (input2)--(sum);
\draw [->,thick] (sum)|-(result);

\tikzset{node distance=0mm}
\node [above=of input1] {128-bittiset lähtörekisterit};
\node [above=of result] {128-bittinen tulosrekisteri};
\end{tikzpicture}
\caption{SIMD-laskennan periaate. SIMD-käskyt suorittavat saman operaation usealle luvulle.
Käsiteltävät luvut on pakattu yhteen rekisteriin, jonka leveys on SSE2-käskykannassa 128 bittiä.
Kuvassa luvut ovat 8-bittisiä, joten niitä mahtuu rekisteriin 16 kappaletta.}
\label{fig_simd}
\end{figure}

\subsection{Nopeusedut}
Laskenta on nopeampaa, kuin jos samat operaatiot suoritettaisiin jokaiselle
luvulle erikseen. Nopeusetu syntyy kahdesta tekijästä: laskennan rinnakkaisuudesta
ja pienemmästä määrästä käskyjen tulkintaa. SIMD-käskyissä laskutoimitusten rinnakkaistaminen
on tehokkaampaa kuin yksittäisillä käskyillä, koska niiden riippuvuussuhteita
ei tarvitse erikseen selvittää.

Saavutettava nopeusetu on merkittävä, sillä SSE2-käskyjen
suoritusnopeus on verrattavissa yksittäisten laskutoimitusten nopeuteen. Esimerkiksi
16-bittisen kertolaskun läpäisy (engl. throughput) on SSE2-käskyllä yksi käsky 4:ssä kellojaksossa ja yksittäisoperaationa
yksi käsky 2:ssa kellojaksossa\cite[s. C-30]{intel_optimization}. SSE2-käsky suorittaa saman kertolaskun 8 luvulle,
joten nopeus on nelinkertainen.

\subsection{Ongelmakohdat}
SSE2-käskyissä käytettävissä olevia operaatioita
on vähemmän kuin yksittäisillä luvuilla laskettaessa. Esimerkiksi jakolasku
puuttuu, joten se täytyy tarvittaessa suorittaa erikseen tai vakiojakajan
tapauksessa korvata kertolaskulla.

Käsiteltäessä useita lukuja kerrallaan ei voida myöskään käyttää tavanomaisia
päätösrakenteita lukujen vertailuun, sillä osa rekisterissä olevista luvuista voi täyttää ehdon
ja osa ei. Ellei päätösrakenteita voida karsia, täytyy kummankin haaran operaatiot
suorittaa kaikille luvuille ja yhdistää sitten lopulliseen tulokseen tulevat luvut
erityisellä käskyllä.

Lukujen bittileveys määrää sen, montako lukua voidaan käsitellä yhtäaikaisesti. Laskenta on nopeinta pienimmällä 8 bitin bittileveydellä, mutta joissain kohdissa käsiteltävien lukujen arvoalue vaatii 16 tai 32 bitin leveyden.
Parhaan nopeuden saavuttamiseksi voi olla tarpeen muuttaa luvut esimerkiksi 16-bittisiksi vasta keskellä laskutoimitusta, jolloin alkuosa voidaan suorittaa
nopeammin 8-bittisillä käskyillä. Useat muunnokset kuitenkin monimutkaistavat ohjelmakoodia.

\subsection{Kääntäjän tuki}
SSE2-käskyjä käytetään tässä työssä kääntäjän sisäänrakennettujen funktioiden
(engl. intrinsic functions) kautta.
Tämä vähentää ohjelmoijan työmäärää verrattuna assembler-koodiin, koska
kääntäjä pystyy itse hoitamaan muuttujien sijoittelun rekistereihin sekä
tekemään muita optimointeja koodille.
Ohjelmointi on silti huomattavasti työläämpää
kuin tavallisen C-koodin kirjoittaminen.
Listauksessa \ref{prg_sse2ex} on vertailtu tavallista ja SSE2-käskykantaa käyttävää ohjelmaa.

Jokainen funktio vastaa yhtä SSE2-käskyä, ja niitä kutsutaan vastaavasti kuin tavallisia funktioita.
Funktioiden kanssa käytetään erityistä \code{\_\_mm128i}-tietotyyppiä, joka kuvaa SSE2-rekistereitä.
Tätä tyyppiä ei voi suoraan käsitellä tavallisilla C-kielen operaatioilla, vaan tulokset täytyy tallentaa muistiin erillisellä käskyllä.

\begin{program}[p]
\caption{Sama funktio toteutettuna tavallisena C-kielisenä ohjelmana sekä SSE2-käskyillä.
Esitetty funktio summaa yhden rivin pikseleitä toiseen riviin, ja tallentaa tuloksen annettuun kohtaan muistissa. Käsiteltävät pikseliarvot ovat 8-bittisiä.
SSE2-käskyillä tehty toteutus on huomattavasti monimutkaisempi, ja vaatii lisäksi erillisen toteutuksen rivin loppuosaa varten.}
\label{prg_sse2ex}
\small
\begin{verbatim}
// Tavallinen C-toteutus
void summaa_rivi(uint8_t *rivi1, uint8_t *rivi2, uint8_t *tulos, int leveys)
{
    int x;
    // Summataan rivi1:n jokainen pikseli vastaavaan pikseliin rivi2:ssa.
    for (x = 0; x < leveys; x++)
    {
        tulos[x] = rivi1[x] + rivi2[x];
    }
}

// SSE2-toteutus
void summaa_rivi(uint8_t *rivi1, uint8_t *rivi2, uint8_t *tulos, int leveys)
{
    int x;
    // Käsitellään pikseleitä 16 tavun lohkoissa.
    for (x = 0; x <= leveys - 16; x += 16)
    {
        // Lähtöarvojen lataaminen muistista
        __m128i lohko1 = _mm_loadu_si128((__m128i*)(rivi1 + x));
        __m128i lohko2 = _mm_loadu_si128((__m128i*)(rivi2 + x));
        
        // Yhteenlasku
        __m128i tuloslohko = _mm_add_epi8(lohko1, lohko2);
        
        // Tuloksen tallennus
        _mm_storeu_si128((__m128i*)(tulos + x), tuloslohko);
    }
    
    // Jos leveys ei ole jaollinen 16:lla, käsitellään rivin loppuosa
    // erikseen.
    for (; x < leveys; x++)
    {
        tulos[x] = rivi1[x] + rivi2[x];
    }
}
\end{verbatim}
\end{program}
\afterpage{\clearpage}

\section{Rinnakkaislaskenta}
Nykyaikaisissa prosessoreissa on usein kaksi tai useampi suoritinydin. Näiden
hyödyntämiseksi laskenta täytyy rinnakkaistaa useampaan säikeeseen. Tämän
algoritmin yhteydessä se on yksinkertaista, sillä operaatiot ovat suurelta osin
toisistaan riippumattomia.

Algoritmi on rinnakkaistettu kuvan \ref{fig_parallel} mukaisesti siten, että jokainen kuva jaetaan eri säikeissä käsiteltäviin vaakasuoriin osiin. Kahden prosessoriytimen tapauksessa kumpikin ydin käsittelee siis puolet kuvasta.

OpenMP:n käyttämä jakotapa voidaan valita \code{schedule}-määreellä. Tässä työssä ja esimerkissä käytetään määrettä \code{schedule(static)}, joka jakaa silmukan arvoalueen samankokoisiin osiin ja käsittelee yhden osan kussakin säikeessä \cite[s.43]{openmp_spec}. Koska rivin käsittelyaika ei riipu merkittävästi rivin sisällöstä, kaikki säikeet valmistuvat yhtäaikaisesti. Jos käsittelyaika vaihtelisi enemmän, voitaisiin käyttää jakotapaa \code{schedule(dynamic)}, joka jakaa rivejä ajon aikana sitä mukaa kun säikeet ovat saaneet edelliset rivit käsiteltyä.

\begin{figure}[htb]
\centering
\begin{tikzpicture}
[x=0.05mm, y=0.05mm, node distance=1cm]
\draw [fill=black!5] (0,0) rectangle (640, 240);
\draw [fill=black!5] (0,240) rectangle (640, 480);
\draw [xshift=1mm,decorate, decoration={brace,amplitude=2mm}] (640,480) -- (640,0);

\node [right=1cm, text width=6em, text centered] at (640,240) (for) {OpenMP:n\\\code{for}-silmukka};
\node [above right=of for, xshift=1cm, draw] (core1) {1. säie};
\node [below right=of for, xshift=1cm, draw] (core2) {2. säie};

\node [above=0mm] at (320,480) {Kuva {\small ($640\times480$)}};

\draw [thick,->] ($(640,240)+(3mm,0)$) -- (for);
\draw [thick,->] (for) |- (core1) node [near end,above] {Rivit 1--240};
\draw [thick,->] (for) |- (core2) node [near end,below] {Rivit 241--480};
\end{tikzpicture}
\caption{Rinnakkaislaskennan toteutustapa tässä työssä. Kukin kuva jaetaan eri prosessoreilla käsiteltäviin vaakasuoriin osiin.}
\label{fig_parallel}
\end{figure}

Rinnakkaistus on toteutettu kääntäjän OpenMP-tuella \cite{gcc_openmp}\cite{msvc_openmp}. Etuna on hyvin helppo
käyttö sekä siirrettävyys eri alustoille. OpenMP:tä käytetään kääntäjän
\code{\#pragma}-lauseiden kautta, joilla määrätään esimerkiksi \code{for}-silmukka
jaettavaksi eri säikeisiin. Ohjelma toimii suoraan myös ilman OpenMP-tukea
käännettäessä, mutta käyttää tällöin vain yhtä prosessoria. Listauksessa \ref{prg_openmp} on esimerkki OpenMP:n käytöstä.

\begin{program}[htb]
\caption{Esimerkki OpenMP:n käytöstä \code{for}-silmukan rinnakkaistamiseen.
Tässä tapauksessa rinnakkaistus onnistuu pelkällä yhden rivin lisäyksellä.
Usein samoja muuttujia käytetään kuitenkin eri säikeistä, jolloin tarvitaan enemmän koodia.}
\label{prg_openmp}
\small
\begin{verbatim}
void summaa_kuvat(uint8_t *kuva1, uint8_t *kuva2, uint8_t *tulos,
                  int leveys, int korkeus)
{
    #pragma omp parallel for schedule(static)
    for (int y = 0; y < korkeus; y++)
    {
        // Kussakin säikeessä käydään läpi osa y:n arvoista.
        // Rinnakkaistus ei vaadi tässä tapauksessa koodiin mitään muutoksia,
        // sillä rivit ovat täysin riippumattomia toisistaan.
        summaa_rivi(kuva1 + y*leveys, kuva2 + y*leveys, tulos + y*leveys);
    }
}
\end{verbatim}
\end{program}

Säikeistyksen voi toteuttaa myös muilla tavoin, kuten \emph{pthreads}-kirjastolla,
mutta tämä on työläämpää ja virhealtista. On olemassa myös erityisiä
rinnakkaisohjelmointikieliä, joista on etua monimutkaisempien algoritmien
yhteydessä. Tämä algoritmi rinnakkaistuu kuitenkin hyvin yksinkertaisesti.

\section{Näytönohjainlaskenta}
Näytönohjaimessa on suuri määrä rinnakkaisia prosessoreita, jotka soveltuvat
erityisen hyvin tässä käsitellyn algoritmin kaltaiseen helposti rinnakkaistuvaan
laskentaan. Tällä hetkellä ongelmana on kuitenkin huono siirrettävyys eri
alustoille, kuten eri valmistajan näytönohjaimille.

Toimivuuden varmistamiseksi algoritmista täytyisi olla myös pääprosessorilla
ajettava versio, mikä kaksinkertaistaisi työmäärän. Nopeustavoitteet
saavutettiin ilman näytönohjainlaskennan hyödyntämistä, joten tähän ei käytetty
aikaa.

Tilanteeseen on tulossa parannusta OpenCL-kielen myötä \cite{opencl}. Sen avulla sama ohjelma
pystytään ajamaan sekä eri näytönohjaimilla että tarvittaessa myös tietokoneen
pääprosessorilla. Kielen kehitys on kuitenkin vielä alkuvaiheessa, ja SiSoftwaren \cite{sisoftware_opencl}
mittaustulosten mukaan suorituskyky pääprosessorilla on merkittävästi huonompi
kuin SSE2:a suoraan käytettäessä.

\section{Tarkistukset ja mittaukset}
Algoritmin aiempi prototyyppi on integroitu kiinteästi sovellusohjelmaan, joten sen käyttö optimoidun version tarkistamisessa olisi ollut työlästä.
Tästä syystä algoritmista tehtiin aluksi C-kielinen referenssitoteutus, jonka avulla voitiin varmistaa optimoidun version oikea toiminta.
Referenssitoteutusta verrattiin aluksi muutamassa testitapauksessa algoritmin matemaattiseen kuvaukseen, ja sitten usealla automaattisesti generoidulla testitapauksella optimoituun versioon.
Ideana on se, että virheiden esiintyminen selkeässä ja yksinkertaisessa referenssitoteutuksessa on epätodennäköisempää kuin optimoidussa versiossa.

Sovellusohjelman yleisimmin käyttämä tulos on keskihajonnan prosenttipiste, mutta pienet virheet välituloksissa eivät näy niin herkästi siinä.
Sen vuoksi algoritmin tarkistuksessa vertailut tehtiin lopputuloksen lisäksi välituloksille, eli konvoluution ja pikselikohtaisen keskihajonnan antamille taulukoille.

Optimoidun version nopeus määritettiin käyttäen C-kielistä testiohjelmaa, joka luki joukon still-kuvia muistiin ja suoritti sitten algoritmin niille. Sen sijaan aiemman prototyypin nopeutta ei pystytty tarkasti määrittämään, sillä sen erottaminen sovellusohjelmasta olisi ollut työlästä. Sen vuoksi vertailussa piti tyytyä pelkkään arvioon aiemmasta nopeudesta.


\chapter{Algoritmin esittely}
\label{ch_esittely}
\input{esittely.tex}

\chapter{Konvoluutiolaskenta}
\label{ch_konvoluutio}
\input{konvoluutio.tex}

\chapter{Keskihajonnan laskenta}
\label{ch_keskihajonta}
\input{keskihajonta.tex}

\chapter{Prosenttipisteen laskenta}
\label{ch_prosenttipiste}
\input{prosenttipiste.tex}

\chapter{Nopeusmittausten tulokset}
\label{ch_tulokset}
\input{tulokset.tex}

\chapter{Yhteenveto}
\label{ch_yhteenveto}

Toteutuksessa saavutettiin 134~MPix/s nopeus, mikä ylittää huomattavasti asetetun 40~MPix/s tavoitteen.
Tärkeimmät tiedot projektista on esitetty taulukossa \ref{tbl_perustiedot}.

\begin{table}[h]
\centering
\caption{Toteutetun projektin perustiedot.}
\label{tbl_perustiedot}
\begin{tabular}{lp{8cm}}
\toprule
Toteutuskieli & C \\
Tarkoitus & Muutosten tunnistaminen videokuvasta. \\
Käytetyt optimointimenetelmät & SSE2 ja OpenMP \\
\midrule
Työmäärä & \\
\hspace{1em} kirjaston toteutus & 70 tuntia \\
\hspace{1em} työn kirjoittaminen & 80 tuntia \\
Koodirivien määrä & \\
\hspace{1em} varsinainen toteutus & 1~685, josta ohjelmakoodia 1~091 riviä \\
\hspace{1em} referenssitoteutus & 538, josta ohjelmakoodia 414 riviä \\
\hspace{1em} testiohjelmat & 996, josta ohjelmakoodia 790 riviä \\
\midrule
Vahvuudet & Nopea toteutus vähäisillä riippuvuuksilla, toteuttaa tarkasti entisen rajapinnan.\\
Heikkoudet & Monimutkainen ohjelmakoodi, ei hyödynnä näytönohjainlaskentaa.\\
\bottomrule
\end{tabular}
\end{table}

Toteutetun kirjaston rivimäärä on 1~685, mikä on suhteellisen vähän. Referenssitoteutuksen rivimäärä on 538, joten optimointi vain kolminkertaisti sen, ja lisäksi suuri osa optimoidun version riveistä on kommentteja. Varsinaisen koodin määrä hieman yli kaksinkertaistui.
Pienestä rivimäärästä huolimatta erityisesti SSE2-käskykanta tekee toteutuksesta hieman vaikeaselkoisen.

Suurin nopeusetu saavutettiin SSE2-käskykannan käytöstä ja OpenMP-rinnakkaislaskennasta. Näistä OpenMP:n käyttöönotto oli erityisen helppoa, kun taas SSE2-käskykanta vaikutti laajasti koko toteutuksen rakenteeseen esimerkiksi kokonaislukulaskennan osalta. Käytetyt nopeutustekniikat ja niiden arvioidut hyödyt ja työmäärät on listattu taulukossa \ref{tbl_tekniikat}.

Taulukossa on mainittu myös kirjallisessa esityksessä vähemmän huomiota saanut ohjelmakoodin rakenteellinen parantelu. Tällä tarkoitetaan esimerkiksi turhien ehtolauseiden ja laskutoimitusten karsintaa.

\begin{table}[htb]
\caption{Eri nopeutustekniikoiden vertailu. Nopeusedut on arvioitu sen pohjalta, kuinka paljon suurempi lopullisen toteutuksen kokonaisaika olisi, jos yksittäinen tekniikka olisi jätetty käyttämättä.}
\label{tbl_tekniikat}
\begin{tabular}{p{5.5cm}rrl}
\toprule
Tekniikka & Nopeusetu & Työmäärä & Oletukset\\
\midrule
OpenMP & $2\times$ & 2~h & 2 prosessoriydintä\\
SSE2-käskykannan käyttö & $5\times$ & 20~h \\
Rakenteellinen parantelu & $2\times$ & 5~h \\
Erilliset käännökset & $2\times$ & 2~h \\
Konvoluution separointi & $1.5\times$ & 10~h & $5\times5$ kerneli\\
Keskihajonnan liukuva ikkuna & $2\times$ & 10~h & 10 kuvapuskuria\\
Prosenttipisteen histogrammi & $40\times$ & 5~h & Vertailu C:n \code{qsort}:iin\\
\bottomrule
\end{tabular}
\end{table}

Kuvassa \ref{fig_eteneminen} on esitetty projektin eteneminen algoritmin nopeuden ja kandidaatintyön sivumäärän perusteella. Varsinainen optimointi ja menetelmien valinta valmistui jo tammikuussa, mutta myöhemmin aikaa kului vielä toteutuksen testaukseen ja hienosäätöön.

\begin{figure}[!h]
\centering
\begin{tikzpicture}
[node distance=0mm]
\begin{axis}[
    date coordinates in=x, ymode=log,
    ymin = 0.1, ymax = 1000, width=13cm, xmin=2010-01-01, xmax=2010-06-01,
    xtick = {2010-01-01, 2010-02-01, 2010-03-01, 2010-04-01, 2010-05-01, 2010-06-01},
    xticklabels = {Tammikuu, Helmikuu, Maaliskuu, Huhtikuu, Toukokuu, },
    ytick = {0.01, 0.1, 1, 10, 100, 1000},
    yticklabels = {{0,01}, {0,1}, 1, 10, 100, 1000},
    ylabel = {Suoritusaika (ms)},
    x tick label as interval,
    clip = false
    ]
%     \addplot[mark=+] table[x=date, y=convolution] {plots/revisions};
%     \addplot[mark=x] table[x=date, y=deviation] {plots/revisions};
%     \addplot[mark=o] table[x=date, y=percentile] {plots/revisions};
    \addplot[mark=*, thick] table[x=date, y=total] {plots/revisions};
    
    \draw [thick] (axis cs: 2010-02-09,3.548) -- +(0,-1.3cm) node [at end,below]
        {\bf Algoritmin nopeus};
    
    \draw (axis cs: 2010-01-08,75.516) -- +(0,1cm) node [at end,above right=-2mm]
        {Valinta-algoritmi};
    
    \draw (axis cs: 2010-01-14,36.372) -- +(0,1cm) node [at end,above right=-2mm]
        {SSE2-konvoluutio};
    
    \draw (axis cs: 2010-01-20,9.308) -- +(0,1cm) node [at end,above right=-2mm]
        {Liukuva ikkuna, histogrammi};
    
    \draw (axis cs: 2010-01-23,3.188) -- +(0,1cm) node [at end,above right=-2mm]
        {SSE2-keskihajonta};
    
    \draw (axis cs: 2010-03-30,2.952) -- +(0,1cm) node [at end,above right=-2mm, text width=7em]
        {Erilliset käännökset jokaiselle pikselikoolle};
    
\end{axis}
\begin{axis}[
    date coordinates in=x,
    ymin = 0, ymax = 80, width=13cm, xmin=2010-01-01, xmax=2010-06-01,
    xticklabels = {},
    ylabel = {Sivumäärä},
    axis y line = right, axis x line = none,
    clip = false, scaled ticks = false, grid=none,
    every axis y label/.style={
        at={(rel axis cs:1,1)}, anchor=south east, xshift=2mm
    }
]

    \addplot[mark=square*, thick] table[x=date, y=docpages] {plots/revisions-doc};
    
    \draw [thick] (axis cs: 2010-05-05,32) -- +(0,-1.4cm) node [at end,below, text width=5em, text centered]
        {\bf Opinnäytetyön\\pituus};
\end{axis}
\end{tikzpicture}
\caption{Projektin eteneminen algoritmin nopeuden ja kandidaatintyön sivumäärän perusteella esitettynä.
Kuvaan on merkitty joidenkin optimointitekniikoiden toteutusajankohdat.}
\label{fig_eteneminen}
\end{figure}

Projekti eteni vaihtelevasti, mutta valmistui kuitenkin melko lyhyessä ajassa.
Vaikeimpia osuuksia olivat oikean toiminnan varmistaminen, separoituvan konvoluution toteutus sekä toimintaperiaatteiden selkeä esittäminen opinnäytetyössä.

Kokonaisuutena projekti oli onnistunut. Toteutettu kirjasto on toistaiseksi riittävän nopea, ja lisäksi tässä työssä on esitetty hyvä pohja mahdolliselle näytönohjainlaskennan toteutukselle tulevaisuudessa.

% lähdeluettelo
\newpage
\renewcommand{\bibname}{Lähteet} 

% seuraavia voi käyttää bibtex:n kanssa (edellyttää tiedoston kirjat.bib)
\bibliographystyle{ieeetr}
\bibliography{lahteet}
\addcontentsline{toc}{chapter}{Lähteet} % Lisää tämäkin sisällysluetteloon

\appendix
\renewcommand{\chaptername}{Liite}
% \chapter{Liitteitä}

\useglosentry{*}

\end{document}

