Lygegretus algoritmai difuzijos lygtims spresti.tex

\documentclass{VUMIFPSkursinis}
\usepackage{physics}
\usepackage{algorithmicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{bm}
\usepackage{caption}
\usepackage{color}
\usepackage{float}
\usepackage{graphicx,stackengine,scalerel}
\usepackage{listings}
\usepackage{subfig}
\usepackage{array}
\usepackage{wrapfig}
\usepackage{tabu}
\usepackage{ tipa }
\usepackage{amsmath}


\university{Vilniaus universitetas}
\faculty{Matematikos ir informatikos fakultetas}
\department{}
\papertype{Bakalauro baigiamasis darbas}
\title{Lygiagretūs algoritmai difuzijos lygtims spręsti}
\titleineng{Parallel Algorithms for Solving Diffusion Equations}
\status{4 kurso 3 grupės studentas}
\author{Matas Savickis}
\supervisor{Rokas Astrauskas, J. Asist.}
\reviewer{Algirdas Lančinskas, Doc., Dr.}


\date{Vilnius – \the\year}

\bibliography{bibliografija}

\begin{document}

\maketitle

\sectionnonum{Padėka}
\begin{itemize}
\item{Noriu padėkoti savo šeimai už pasitikėjimą ir moralinį palaikymą per visus metus praleistus studijuojant.}
\item{Noriu padėkoti savo darbo vadovui Rokui Astrauskui už skirtą laiką ir pagalbą rašant šį darbą. Geresnio vadovo negalėčiau prašyti.}
\end{itemize}
\pagebreak

\sectionnonum{Santrauka lietuvių kalba}
Skenuojančio elektrocheminio mikroskopo veikimas aprašomas naudojantis dalinėmis diferencialinėmis lygtimis difuzijos procesams modeliuoti.
Kadangi šioms lygtims nėra analitinio sprendimo, jas aproksimuojame skaitinių metodų lygtimis \cite{NumAnal}.
Siekiant gauti tikslų rezultatą reikia atlikti daug skaičiavimų, kurie gali užtrukti ilgai, todėl yra tikslinga ieškoti būdų pagreitinti skaičiavimus.
Šiame darbe bus ieškoma būdų kaip naudojantis lygiagrečiais algoritmais pagreitinti modelio skaičiavimą.
Lygiagretūs algoritmai buvo rašomi naudojant MPI realizaciją: mpi4py Python programavimo kalba. 
Pagrindinis darbo tikslas yra rasti optimalų lygiagretų algoritmą modeliuoti deguonies koncentraciją susidarančią atliekant eksperimentus su skenuojančiu elektrocheminiu mikroskopu (angl. SECM).


Atliekant eksperimentus, buvo naudojamasi VU MIF Paskirstytų skaičiavimų tinklu ir lokaliais autoriaus resursais.
Buvo įgyvendinti du lygiagretūs algoritmai: vienmatis ir dvimatis.
Lokalioje aplinkoje skaičiavimams buvo naudojamasi iki 5 branduolių, o MIF klasteryje iki 50 branduolių.
Darbe buvo sėkmingai pagreitinti skaičiavimai taikant literatūroje aprašytus algoritmus\cite{Lygeg}.
Nustatyta, kad vienmatis algoritmas yra optimaliausias būdas lygiagretinti skaičiavimams.
Vienmatis algoritmas buvo greičiausias tiek lokalioje tiek ir MIF klasterio aplinkoje.

Raktiniai žodžiai: Lygiagretūs skaičiavimai, dalinės diferencialinės lygtys, Laplaso lygtys, difuzijos lygtis, šilumos perdavimo lygtis.
\pagebreak

\sectionnonum{Santrauka anglų kalba (Summary)}
The operation of a sequential electrochemical microscope is described using partial differential equations to model diffusion processes. 
Since there is no analytical solution to these equations, we approximate them to the equations of numerical methods.
Achieving an accurate result requires a lot of calculations that can take a long time, so it makes sense to look for ways to speed up the calculations.
This paper will look at ways to speed up the computation of the model using parallel algorithms.
Parallel algorithms were written using the MPI implementation: mpi4py in the Python programming language.
The main goal of the work is to find an optimal parallel algorithm to model the oxygen concentration generated by experiments with a scanning electrochemical microscope (SECM).


The experiments used the VU MIF Distributed Computing Network and the author's local resources.
Two parallel algorithms were implemented: one-dimentional and two-dimentional
Up to 5 cores were used for computations in the local environment, and up to 50 cores in the MIF cluster.
The calculations were successfully accelerated using the algorithms described in the literature \ cite {Lygeg}.
The one-dimensional algorithm has been found to be the most optimal way to parallelize the calculations.
The one-dimensiona algorithm was the fastest in both the local and MIF cluster environments.


Keywords: Parallel calculations, partial differential equations, Laplace equations, diffusion equation, heat transfer equation.
\pagebreak

\tableofcontents

\pagebreak

\sectionnonum{Įvadas}
Šiame darbe bus ieškomas optimalus lygiagretusis algoritmas norint modeliuoti skenuojantį elektroninį mikroskopą \cite{Astr}.
Darbe bus atliekami eksperimentai su skirtingais lygiagrečiaisiais algoritmais \cite{Lygeg} naudojant MIF VU paskirstytų skaičiavimų centro \cite{Mif} resursus bei atliekant skaičiavimus lokalioje aplinkoje.
Norint atlikti tikslius difuzijos lygčių skaičiavimus tenka laukti nemažai laiko \cite{Pois} kol skaičiavimai baigiasi, todėl sunku greitai įvertinti modelio tikslumą ir atlikti pakeitimus.
Teorinėje literatūroje yra aprašyti keli algoritmai \cite{Lygeg}, kuriais naudojantis galima lygiagretinti difuzijos procesų skaičiavimus.
Šis darbas siekia įvertinti lygiagrečių algoritmų spartą ir jų savybes.
Tikimasi, kad darbas bus naudingas Vilniaus universiteto (VU) Matematikos ir informatikos fakulteto (MIF) mokslininkų bendradarbiavimui su Vilniaus universiteto Chemijos ir geomokslų fakultetu tolimesniems Skenuojančio elektrocheminio mikroskopo modeliavimo tyrimams \cite{Astr}.


Darbe yra išsikeliamos keturios pagrindinės užduotys:
\begin{enumerate}
\item{Matematinių lygčių ir Skaitinių metodų algoritmų, reikalingų tyrimui, apibrėžimas.}
\item{Realaus SECM modelio sudarymas.}
\item{Lygiagrečių algoritmų apibrėžimas.}
\item{Optimalaus lygiagretaus algoritmo suradimas ir realizacija.}
\item{Lygiagrečių skaičiavimų eksperimentai lokalioje aplinkoje.}
\item{Lygiagrečių skaičiavimų naudojant MIF paskirstyto skaičiavimo centro resursus.}
\end{enumerate}
Darbas yra suskirstytas į tris dėstymo skyrius.
\begin{enumerate}
\item{Dalinės diferencialinės lygtys difuzijos lygtims spręsti ir skaitinių metodų algoritmai}
\item{SECM modelio sudarymas}
\item{Lygiagretūs algoritmai difuzijos lygtims spręsti}
\end{enumerate}


Pirmame dėstymo skyriuje (Dalinės diferencialinės lygtys difuzijos lygtims spręsti ir skaitinių metodų algoritmai) bus įvedamos matematinės uždavinio formuluotės.
Bus apibrėžiamas trimatis (3D) Puasono dalinės diferencialinės lygties atvejis, lygtis bus pertvarkoma į dvimatę (2D) Laplaso lygtį.
Laplaso lygčiai bus apibrėžta skaičiavimo sritis.
Apibrėžus matematines lygtis bus pereita prie skaitinių metodų algoritmų.
Darbe bus pasirinkta analizuoti Baigtinio skirtumo metodą (angl. Finite difference method).
Bus užrašoma matematinė Baigtinio skirtumo formuluotė.
Šis formuluotė pradžioje bus pateikta bet kokio dydžio dvimačiam (2D) kūnui skaičiuoti ir paskui bus pertvarkoma į vienetinio kūno lygtį paprastesniems skaičiavimams atlikti.
Matematinė ir skaitinė dalis bus paremta knyga ,,Numerical Analyis Eighth Edition" kurią parašė Richard L. Burden ir J. Douglas Faires. \cite{NumAnal}.
Toliau bus realizuojamas skaitinis algoritmas.
Realizacijai bus naudojama Python 2 programavimo kalba \cite{Py} ir matematinė biblioteka NumPy \cite{Np}.
Užrašysime konkretų algoritmą lygčiai skaičiuoti, pateiksime grafinę skaičiavimų reprezentaciją.
Skyriaus gale skaičiavimus vienetiniam kūnui laisvai pasirinksime kraštines sąlygas tam kad vizualiai įsitikintume ar algoritmas veikia korektiškai.


Antrajame dėstymo skyriuje (SECM modelio sudarymas) bus aprašomas Skenuojančio elektrocheminio mikroskopo veikimo principas, kokios dalys sudaro SECM, kokie procesai vyksta dirbant su SECM ir kuo tai susiję su pirmame skyriuje apibrėžtomis difuzijos lygtimis.
Skyriuje bus diskutuojama kuo yra naudingi tyrimai su SECM, kokiais tyrimais bus remiamasi šiame darbe ir kuo šis darbas gali būti naudingas tolimesniam VU Matematikos ir informatikos fakulteto bendradarbiavimui su VU Chemijos ir geomokslų fakultetu.
Šiame skyriuje bus apibrėžiamas SECM modelis, kraštinės modelio reikšmės tiek konstantų tiek funkcijų pavidalu, kraštinių funkcijos sąlygų aproksimavimo metodas bei tikslumo reikšmės.
Skyriuje bus remiamasi Felikso Ivanausko, Ingos Morkvenaitės–Vilkoncienė, Roko Astrausko bei Arūno Ramanavičiaus darbu ,,Modelling of Scanning Electrochemical Microscopy at Redox
Competition Mode Using Diffusion and Reaction Equations", Roko Astrausko pranešimo ,,Difuzijos ir reakcijos procesų elektrocheminėje mikroskopijoje matematinis modeliavimas" užrašais, bei prieš tai paminėta knyga ,,Numerical analysis Eighth Edition" \cite{NumAnal}
Skyriaus pabaigoje pateiksime skaičiavimų grafikus gautus naudojant skirtingas, skyriuje apibrėžtas, kraštines sąlygas.
Bus pasirinktas vienas modelis, kuris bus naudojamas skaičiavimams paskutiniame dėstymo skyriuje.


Trečiajame dėstymo skyriuje (Lygiagretūs algoritmai difuzijos lygtims spręsti) bus nagrinėjami lygiagretūs algoritmai.
Skyriaus pradžioje apibrėšime Amdahlo dėsnį, kokių rezultatų tikimasi pasiekti realizavus lygiagrečius algoritmus ir kas yra žinučių apsikeitimo protokolas MPI.
Toliau bus apibrėžiama pati lygiagrečių skaičiavimų architektūra su pagrindiniu branduoliu ir skaičiavimo branduoliais.
Aprašysime du lygiagrečius algoritmus, vienmatį (1D) ir dvimatį (2D), kuriuos realizuosime naudodamiesi Python programavimo kalbos MPI realizacija mpi4py.
Toliau bus atliekami eksperimentai naudojant autoriaus lokalią sistemą bei MIF paskirstytų skaičiavimų centro resursais (MIF klasteris). 
Trumpai pristatysime tiek lokalios aplinkos tiek ir MIF klasterio specifikaciją.
Pateiksime eksperimentų, atliktų skirtingose aplinkose, rezultatus ir padiskutuosime apie gautus rezultatus.
Šiame skyriuje bus remiamasi Raimondo Čiegio knyga ,,Lygiagretieji skaičiavimai" \cite{Lygeg}, Barry Wilkinson ir Michael Allen knyga ,,Parallel Programming Techniques and Applications Using Networked Workstations and Parallel Computers Second Edition" \cite{Par}, bei mpi4py dokumentacija \cite{Mpi}


Darbo pabaigoje reziumuosime kas buvo nuveikta šiame darbe, gauti rezultatai bei išvados ir kokia linkme būtų galima tęsti šį darbą. 
\pagebreak
\section{Puasono dalinės diferencialinės lygtys ir skaitiniai algoritmai}
\subsection{Puasono dalinės diferencialinės lygtys}
Poskyrį pradėsime apibrėždami pagrindinę matematinę lygtį, kuri bus šio darbo pagrindas.
Literatūroje \cite{NumAnal} yra aprašoma Dalinė diferencialinė Puasono (angl. Poisson) lygtis (1) skirta skaičiuoti trijų dimensijų (3D) difuzijos procesus.
\begin{equation}
\frac{\partial^{2} u}{\partial x^{2}} (x, y, z) + \frac{\partial^{2} u}{\partial y^{2}} (x, y, z) + \frac{\partial^{2} u}{\partial z^{2}} (x, y, z) = f(x, y, z)
\end{equation}



Šiame darbe modeliuosime dvejose dimensijose, todėl iš formulės galime panaikinti $z$ ašį ir gauti dviejų dimensijų (2D) lygtį (2).
\begin{equation}
\frac{\partial^{2} u}{\partial x^{2}} (x, y) + \frac{\partial^{2} u}{\partial y^{2}} (x, y) = f(x,y)
\end{equation}


Dešinėje lygties (2) pusėje $f(x,y)$ rodo, kad sistemoje egzistuoja vidinis difuzijos šaltinis.
Šiame darbe bus modeliuojamos tik kraštinės sąlygos ir vidinių difuzijos šaltinių neturėsime, todėl $f(x,y) = 0$.
Gauname dviejų dimensijų(2D) difuzijos lygtį(3).

\begin{equation}
\frac{\partial^{2} u}{\partial x^{2}} (x, y) + \frac{\partial^{2} u}{\partial y^{2}} (x, y) = 0
\end{equation}
Difuzijos lygtyje (3) $u(x,y)$ žymi tinklo taško reikšmę, kuri priklauso racionaliųjų skaičių aibei.
Lygtyje (3) $x^2$ žymi tinklo ilgį, o $y^2$ tinklo plotį.

Apibrėžkime tinklą.
Tinklas yra koordinačių sistema padalinta į įsivaizduojamus stačiakampius gretasienius, kurių viduje yra taškas turintis savo reikšmę.

\begin{figure}[H]
\centering
\includegraphics[scale=1]{img/NM}
\caption{Tinklas koordinačių sistemoje} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Apibrėžkime tinklo ilgį $h$ ir plotį $k$.
\begin{equation}
h = \frac{(b - a)}{n}
\end{equation}
\begin{equation}
k = \frac{(d - c)}{m}
\end{equation}
\subsection{Skaitinių metodai difuzijos lygtims spręsti}
Šiame poskyryje kalbėsime apie būdus, kaip galima aproksimuoti praeitame poskyryje apibrėžtą difuzijos lygtį.
Skaitinių metodų literatūroje \cite{NumAnal} aprašomas baigtinio skirtumų (angl. Finite difference) metodas, kurį taikant, galime aproksimuoti difuzijos lygtį (3).
Pagrindinė baigtinio skirtumų metodo formulė dviejų dimensijų lygčiai skaičiuoti yra:

\begin{equation}
\frac{u(x_{ i + 1} , y_j) - 2u(x_{ i } , y_j) + u(x_{ i - 1} , y_j)}{h^{2}} + \frac{u(x_{ i } , y_{ j + 1}) - 2u(x_{ i } , y_j) + u(x_{ i } , y_{j - 1})}{k^{2}} = 0
\end{equation}

Šioje formulėje $u(x_i,y_j)$ žymį tinklo taško reikšmę.
$h^2$ ir $k^2$ žymi tinklo ilgį ir plotį kaip ir buvo apibrėžtą praeitame poskyryje (4, 5).
Šią lygtį (6) galime pertvarkyti, kad vienoje lygybės pusėje gautume taško esančio koordinatėje $u(x_i , y_j)$ reikšmę.

\begin{equation}
\frac{k^2 \Big(u(x_{ i + 1} , y_j) + u(x_{ i - 1} , y_j)\Big) + h^2\Big(u(x_{ i } , y_{ j + 1}) + u(x_{ i } , y_{j - 1})\Big)}{2 (h^2 + k^2)} = u(x_{ i } , y_j)
\end{equation}


Jeigu skaičiavimuose mums nesvarbus tinklo dydis galime tinklo ilgio ir pločio reikšmes priskirti vienetui $h=1$ ir $k=1$ taip gaudami lygtį
\begin{equation}
\frac{u(x_{ i + 1} , y_j) + u(x_{ i - 1} , y_j) + u(x_{ i } , y_{ j + 1}) + u(x_{ i } , y_{j - 1})}{4} = u(x_{ i } , y_j)
\end{equation}

Iš formulės matome, kad norėdami rasti konkretaus taško reikšmę tinkle mums reikia sudėti kaimyninių taškų reikšmes ir padalinti iš keturių.

\begin{figure}[H]
\centering
\includegraphics[scale=0.7]{img/poossonBaseAlgo}
\caption{Tinklo taško reikšmės skaičiavimas. Rodyklės rodo kurias reikšmes reikia sudėti, spalvoti apskritimai rodo skirtingas kraštinių sąlygų reikšmes.} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}
Atlikdami difuzijos skaičiavimus mes įsivaizduojame, kad į skaičiuojamą sritį skirtingomis koncentracijomis patenka kažkokia medžiaga.
Medžiagos koncentraciją galime apibrėžti konstantine reikšme arba funkcija.
Konstantinės reikšmės atveju krašte esančius tinklo taškus nustatome tik vieną kartą ir jie nekinta.
Funkcinės reikšmės atveju kraštinė sąlyga gali keistis skaičiavimo metu.
Diagramoje (2 pav.) vaizduojamas tinklas, kur mėlyna, žalia, geltona ir purpurine spalvomis parodytos skirtingos kraštinės sąlygos, o norint gauti vieno tašo reikšmę rodyklėmis pavaizduotos reikmės, kurias reikia sudėti ir padalinti iš keturių.
\subsection{Baigtinio skirtumų metodo algoritmas}
Šiame poskyryje užrašysime algoritmą kuriuo naudodamiesi atliksime skaičiavimus.
Skaičiavimus vykdysime iteratyviai iki tol, kol bus pasiektas norimas skaičiavimų tikslumas.
Tikslumą arba norimą paklaidą apibrėšime kaip naujų tinklo reikšmių skirtumą nuo senų tinklo reikšmių (8). 
\begin{equation}
maksimali\_paklaida(\frac{naujas\_tinklas - senas\_tinklas}{naujas\_tinklas} * 100)
\end{equation}
Senas tinklo reikšmes vadinsime tas reikšmes kurios buvo prieš atliekant iteraciją, o naujas tinklo reikšmes laikysime tas kurias gausime atlikę iteraciją.
Skaičiavimai bus atliekami taip:
\begin{enumerate}
\item{Nustatome tinklo kraštines sąlygas.}
\item{Kiekvienam vidiniam tinklo taškui pritaikome baigtinių skirtumų formulę (7).}
\item{Palyginame senas tinklo reikšmes su naujomis, kad gautume paklaidą.}
\item{Jeigu norima paklaida pasiekta, skaičiavimus nutraukiame.}
\item{Jeigu reikia pakeičiame kraštines sąlygas (funkcija kaip kraštinė sąlyga).}
\item{Grįžtame į pirmą žingsnį.}
\end{enumerate}
\subsection{Baigtinio skirtumų metodo algoritmo realizacija}
Šiame poskyryje pakalbėsime apie baigtinio skirtumų metodo realizaciją naudojant Python 2 ir NumPy biblioteką.
Algoritmas aprašytas praeitame skyriuje sako, kad norint rasti vidinio tinklo taško reikšmę turime sudėti kaimyninius jo taškus (2 pav.).
Vietoj to, kad skaičiuotume kiekvieno taško reikšmę atskirai, mes pasinaudosime NumPy biblioteka ir iškarto imsime keturias matricas atitinkančias keturias kaimyninius tinklo taškus (3 pav.) ir visas reikiamas aritmetines operacijas vykdysime matricai, o ne atskiriems tinklo taškams, taip smarkiai padidindami skaičiavimų greitį palyginus su algoritmu įgyvendinti naudojant tik vidinius Python funkcionalumus. 
Grafike spalvotais punktyriniais kvadratais pavaizduotos keturios kaimyninių reikšmių matricos.
\begin{figure}[H]
\centering
\includegraphics[scale=0.7]{img/PoissonBestAlgo}
\caption{Skaičiavimo algoritmo vizualizacija taikant NumPy biblioteką. Punktyrais žymimos atskirtos matricos.} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Norėdami pasitikrinti ar gauname tinkamas reikšmes įvykdykime skaičiavimą.
Kraštinėms sąlygoms nustatykime keturias konstantines reikšmes $C_1=700$, $C_2=200$, $C_3=0$ $C_4=400$, o tikslumo koeficientą nustatykime $0,001\%$.
Kraštinės sąlygos nustatytos laisvai pasirenkant reikšmes, tikslumo koeficientas paimtas iš mokslinių darbų \cite{Astr} \cite{Pois} ir lygiagrečių skaičiavimų literatūros \cite{Lygeg}
Atlikus skaičiavimus su šiomis reikšmėmis gauname rezultatą

\begin{figure}[H]
\centering
\includegraphics[scale=1]{img/1x1}
\caption{Difuzijos modeliavimas su laisvai pasirinktom kraštinėm sąlygom. Vienetinioo dydžio kūnas.} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}


Iš rezultato vizualiai galime matyti, kad mūsų algoritmas veikia korektiškai, sritys kuriose difuzijos kraštinės reikšmės buvo didesnės artėjant į centrą po truputį mažėjo, vidury diagramos susidarė vidutinės reikšmės.
Tolesniuose skyriuose naudosime tą patį $0,001\%$ paklaidos koeficientą.






\pagebreak

\section{SECM modelio sudarymas}
\subsection{Skenuojantis elektrocheminis mikroskopas}
\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{img/sem}
\caption{SECM schema} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Skenuojanti elektrocheminė mikroskopija yra metodas, kai naudojant mažos apimties elektrodą, kuriuo teka elektros srovė, yra matuojamos mėginio patalpinto į tirpalą paviršiaus charakteristikos.
Elektrodas gali judėti aukštyn, žemyn arba palaikyti vienodą aukšti ir judėti vienoje plokštumoje.
Skenuojančiu elektrocheminiu mikroskopu galima matuoti sąveikas tarp skysčio ir kieto kūno, skysčio ir dujų bei skysčio ir skysčio.
SECM gali būti naudojamas tirti kieto kūno paviršiaus topografiją ir reaktyvumą.
Tyrimai atlikti naudojant SECM padėjo vystyti medžiagų mokslą ir daryti įvairius atradimus nanotechnologijų šakose.
Šiuo tyrimu bus siekiama papildyti jau vykdytus Vilniaus universiteto mokslininkų darbus SECM modeliavime.
\subsection{SECM modelio sudarymas}
Šiame skyriuje sudarysime sudėtingesnį difuzijos modelį, kuris atitiktų VU mokslininkų jau atliktus modeliavimo tyrimus \cite{Astr}.
Apibrėšime konstantines ir funkcines kraštines sąlygas siekdami modeliuoti deguonies difuzijos procesus naudojantis SECM.
Modelis susidarys iš keturių pagrindinių elementų:
\begin{enumerate}
\item{Konstanta – tinklo sritis kurioje pastoviu būdu bus pus įleidžiamas deguonis.}
\item{Izoliuota – tinklo sritis kurioje nevyksta difuzijos procesai.}
\item{Elektrodas – tinklo sritis, kuri kontaktuoja su elektrodu ir įgauną pastovią konstantinę reikšmę.}
\item{Reakcijos sritis – tinklo pagrindo sritis kurioje deguonis sąveikauja su eksperimento objektu. Šioje srityje įvyksta cheminės reakcijos todėl reikšmė yra kintama.}
\end{enumerate}
Grafiškai modelį galime pavaizduoti taip
\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{img/astrausko}
\caption{SECM modelis su kraštinėmis sąlygomis} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}
Modelio ilgiai iš reikšmės yra paimtos iš VU mokslininkų darbo \cite{Astr}
\begin{enumerate}
\item{Ilgis – $k = 80\mu m$}
\item{Plotis – $h = 40\mu m$}
\item{Elektrodo ilgis – $l = 5\mu m$ }
\item{Deguonies padavimas – $O_2 = 253\mu mol/L$}
\end{enumerate}
Sudarytame modelyje elektrodas yra priartėjęs prie pagrindo, kairys modelio šonas ir dalis viršaus yra izoliuota ir kairėje pusėje yra įleidžiamas deguonis.
Grafiko apačioje vyksta cheminės reakcijos.
Izoliuotoje srityje difuzija nevyksta, šią sritį modeliuosime funkcijos išvestinę prilyginę nuliui (9).
\begin{equation}
\frac{\partial C}{\partial y}( x, y = 0) = 0
\end{equation}
Izoliuotos srities aproksimacijai naudosime patį paprasčiausią aproksimacijos būdą, kuris yra aprašytas literatūroje \cite{NumAnal} (10).
\begin{equation}
f'(x) =\frac {f(x + h) - f(x)}{h}
\end{equation}
Pagrindui modeliuoti naudosime dvi funkcijas:
\begin{equation}
f(x) = k \abs{\sin \frac{\pi x}{a}}
\end{equation}
Šioje lygtyje kintamasis $k$ yra greičio konstanta, skaičiavimuose laikysime, kad $k = 100$.
\begin{equation}
f(x) = \begin{cases}
k, & \text{x \textepsilon \vspace{10 mm} ląstelė}.\\
0, & \text{x \textepsilon \vspace{10 mm} tarpas}.
\end{cases}
\end{equation}
Antroji lygtis (12) yra laiptinė, kuri pagrindą padalina į sritis, kurių reikšmės bus 0 arba $k$.
Taikant šią funkciją prilyginsime $k=100$.
Atliekant šiuos skaičiavimus taikysime anksčiau aprašytą skaitinių metodų lygtį, kuri atsižvelgia į modelio dydį (7).
Skaičiavimai bus vykdomi tol kol bus pasiekta $0.001\%$ paklaidos riba.
Tinklui nustatysime 320000 taškų, arba 400 taškų pločio ir 800 taškų ilgį.
\subsection{Modeliavimo rezultatai}
Atlikus skaičiavimus gauname dvi diagramas:
\begin{figure}[H]
\centering
\includegraphics[scale=1]{img/sinusoid}
\caption{Sinusoidinė funkcija} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}
\begin{figure}[H]
\centering
\includegraphics[scale=1]{img/stepFunc}
\caption{Laiptinė funkcija} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Vizualiai galime matyti, kad skaičiavimai įvyko sėkmingai.
Grafikų viršuje ir kairėje pusėje matome izoliuotą sritį kurioje nevyko difuzijos procesas, todėl tos dalys nedarė įtakos deguonies pasiskirstymui.
Kairėje pusėje viršuje matome modeliuotą elektrodo sritį kurioje nebuvo deguonies, tačiau vykstant difuzijai deguonies sritis priartėjo prie elektrodo srities.
Apatinėje dalyje matome, kaip vyko deguonies pasiskirstymas taikant sinusoidinę (7 pav.) ir laiptinę (8 pav.) funkcijas.
Funkcijos modeliuoti pagrindo sritį buvo pasirinktos laisvai siekiant parodyti, kad modelis veiktų korektiškai nurodant tikslesnes, labiau realius procesus atitinkančias funkcijas.
Lokalioje aplinkoje skaičiavimai truko 49 minutes 15 sekundžių, o MIF klasteryje skaičiavimai truko 1 valandą 35 minutes ir 26 sekundes.
Kuriant sudėtingesnius modelius, kuriuose būtų daugiau tinklo taško ir sudėtingesnės kraštinės sąlygos skaičiavimai truktų dar ilgiau, todėl yra prasminga ieškoti būdų kaip pagreitinti skaičiavimus.
Trečiame dėstymo skyriuje naudosime modelį su sinusoidine funkcija realizuodami lygiagrečius algoritmus ir vykdydami eksperimentus siekdami pagreitinti skaičiavimus.


\pagebreak

\section{Lygiagretūs algoritmai difuzijos lygtims spręsti}
\subsection{Lygiagrečių skaičiavimų teorija}
Šiame skyriuje realizuosime lygiagrečius algoritmus siekdami pagreitinti modelio skaičiavimą.
Prieš pradėdami algoritmų realizavimą turime žinoti, kokio skaičiavimų pagreitėjimo galime tikėtis.
Lygiagrečių skaičiavimų teorijoje yra formulė (14) pasakanti galimą skaičiavimų pagreitėjimą.
Ši formulė vadinasi Amdahlo dėsniu.
\begin{equation}
S_p = \frac{1}{(1 - r) + \frac{r}{p}}
\end{equation}
Šioje formulėje:
\begin{itemize}
\item{$S_p$ – Teorinis visos užduoties vykdymo pagreitėjimas.}
\item{$r$ – užduoties dalis, kurią galima apskaičiuoti lygiagrečiai.}
\item{$1-r$ – užduoties dalis, kurios negalima skaičiuoti lygiagrečiai.}
\item{$p$ – branduolių skaičius.}
\end{itemize}

Naudojantis Amdahlo dėsniu ir žinant kuri programos dalis gali būti skaičiuojama lygiagrečiai galime pasakyti koks yra maksimalus teorinis pagreitėjimas su tam tikru branduolių skaičiumi.
Amdahlo dėsnis taip pat teigia, kad didžiausias įmanomas pagreitėjimas yra 20 kartų greitesnis veikimas negu vykdant užduotį naudojant vieną branduolį:

\begin{equation}
\frac{1}{1-r} = 20 
\end{equation}

Iš Amdahlo dėsnio gauname grafiką; pagreitėjimas priklauso nuo užduoties dalies kurią galimą vykdyti lygiagrečiai (9 pav.).
\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{img/amdahl}
\caption{Amdahlo dėsnis} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

\subsection{Lygiagrečių algoritmų realizacijos}
Šiame skyriuje aptarsime lygiagrečius algoritmus, kuriuos naudosime paspartinti difuzijos procesų skaičiavimams ir architektūrą, kurią naudosime žinutėms siųsti.
Darbe naudosime du lygiagrečius algoritmus aprašytus literatūroje \cite{Lygeg}.
Algoritmai bus realizuojami Python 2 programavimo kalbą ir MPI realizacija mpi4py.

Skaičiavimams vykdyti naudosime paprastą architektūrą sistemos branduolius padalinę į dvi esmines grupes:
\begin{enumerate}
\item{Pagrindinis branduolys – jo paskirtis yra išsiųsti atitinkamus tinklo taškus skaičiavimo branduoliams ir sugrupuoti rezultatus gautus skaičiavimo branduoliams baigus darbą.}
\item{Skaičiavimo branduoliai – jų paskirtis yra gauti pradinę informaciją iš pagrindinio branduolio, atlikti skaičiavimus iki kol bus pasiekta reikiama paklaida, išsiųsti tarpinius duomenis kaimyniniams skaičiavimo branduoliams ir grąžinti suskaičiuotus rezultatus.}
\end{enumerate}


\begin{figure}[H]
\centering
\includegraphics[scale=1]{img/mpiArch}
\caption{Žinučių siuntimo architektūra} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Pirmas algoritmas, kurį realizuosime yra „vienmatis diskrečiojo tinklo padalijimas“ \cite{Lygeg}.
Tinklą padalijame į N lygių dalių, kur N yra kiek naudosime skaičiavimo branduolių.
Pagrindinis branduolys perduoda pradinę informaciją skaičiavimo branduoliams.
Kiekvienas skaičiuojantis branduolys išsiunčia kaimyniniams branduoliams pirmą ir paskutinę savo tinklo eilutę. 
Tokiu būdu kiekvienas branduolys gauna papildomų fiktyviųjų duomenų, kuriuos naudoją skaičiavimams kaip kraštinę sąlygą.
Po kiekvienos iteracijos vyksta duomenų apsikeitimas ir naujų fiktyvių kraštinių sąlygų sudarymas.
Skaičiavimai ir apsikeitimai vyksta tol, kol visi skaičiavimo branduoliai pasiekia reikiamą tikslumą.
Vienam branduoliui pasiekus reikiamą tikslumą jis išsiunčia rezultatus į pagrindinį branduolį.
Jeigu kaimyniniai branduoliai dar nebaigė darbo jis ir toliau siunčia jiems tą pačią informaciją iki kol kaimyniniai branduoliai taip pat pasieks reikiamą paklaidą ir baigs darbą.

\begin{figure}[H]
\centering
\includegraphics[scale=0.5]{img/1xn}
\caption{Vienmatis lygiagretusis algoritmas.} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Antras algoritmas, kurį įgyvendinsime yra „dvimatis tinklo padalijimo algoritmas“.
Algoritmas skirsis nuo vienmačio tuo, kaip padalinsime tinklą į lygias dalis.
Tinklas bus dalinamas NxM lygių stačiakampių.
Kaip ir vienmatyje algoritme po kiekvienos iteracijos skaičiuojantys branduoliai apsikeis ir sudarys naujas fiktyvias kraštines sąlygas.

\begin{figure}[H]
\centering
\includegraphics[scale=0.6]{img/nxn}
\caption{Dvimatis lygiagretusis algoritmas.} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

\subsection{Skaičiavimų aplinkos}
Skaičiavimai bus vykdomi dviejuose aplinkose: lokalioje ir MIF paskirstytų skaičiavimų tinklo aplinkoje.


Lokali aplinka:
\begin{itemize}
\item{Procesorius – ADM Ryzen 5 1600X, 6 branduoliai}
\item{Operatyvioji atmintis – 32GB DDRM4 1330Hz}
\item{Operacinė sistema – Linux Ubuntu 20.04 LTS, naudojant VirtualBox 6.1.6}
\item{Kietasis diskas – HDD 500GB}
\end{itemize}


MIF paskirstytų skaičiavimų centras tinklas:
\begin{itemize}
\item{Procesorius – 2x Intel Xeon X5650 2.66GHz = 12 cores}
\item{Operatyvioji atmintis – 24 GB}
\item{Operacinė sistema – Linux Debian}
\item{Kietasis diskas – 160GB}
\end{itemize}

\subsection{Skaičiavimų rezultatai}
Pirma skaičiavimus atlikome lokalioje aplinkoje.
Skaičiavimai buvo atlikti taikant sinusoidinį pagrindo modelį.
Skaičiavimų parametrai buvo pasirinkti tokie kaip antrajame skyriuje:
\begin{itemize}
\item{Tinklo ilgis – 800 taškų.}
\item{Tinklo plotis – 400 taškų.}
\item{Tikslumas – 0,001\%}
\item{Vykdymo laikas – trijų skaičiavimų laikų aritmetinis vidurkis.}
\end{itemize} 

Atlikę skaičiavimus gauname (13 pav.), kad nenaudojant lygiagrečių algoritmų skaičiavimai trunka 49 minutes 15 sekundžių.
Pradėjus taikyti lygiagrečius algoritmus skaičiavimo laikas sėkmingai pradėjo mažėti.
Grafike raudona linija žymi teoriškai greičiausią įmanomą laiką laikant, kad lygiagreti uždavinio dalis yra 95 procentai.
Ta pati teorinė reikšmė bus ir kitose šio skyriaus diagramose.
Taikant vienmatį algoritmą pavyko skaičiavimo greitį sumažinti iki 18 minučių ir 26 sekundžių naudojant 5 skaičiavimo branduolius, o taikant dvimatį algoritmą skaičiavimo greitį pavyko sumažinti iki 25 minučių ir 52 sekundžių naudojant 4 skaičiavimo branduolius.
Taigi gavome, kad vienmatis algoritmas yra greitesnis negu dvimatis. Tai atitinka literatūroje aprašomą algoritmų įgyvendinimą, nes skaičiavimų pagreitėjimas naudojant dvimatį algoritmą prasidėtų tik nuo 9 skaičiavimo branduolių.
Grafike matome, kad nuo 6 branduolių ribos skaičiavimai pradeda lėtėti.
Taip nutinka dėl to, nes sistemoje nepakanka laisvų branduolių, todėl priskyrus daugiau branduolių negu yra sistemoje vienas branduolys pradeda atlikti dvi užduotis, todėl skaičiavimai sulėtėja.

\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{img/bendrasL}
\caption{Skaičiavimo laikas lokalioje aplinkoje} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Vykdant skaičiavimus MIF klasteryje naudosimės tais pačiais skaičiavimo modeliais ir parametrais.
Atliekant skaičiavimus naudojant tik vieną branduolį skaičiavimo laikas yra 1 valanda 35 minutės 26 sekundės.
Toks skaičiavimo greitis yra tikslus, nes lokalios aplinkos vieno branduolio pajėgumas yra didesnis negu MIF klasterio.
Klasterio privalumai yra galimybė naudoti didelį branduolių skaičių.


Atliekant skaičiavimus taikant vienmatį algoritmą gauname smarkų sulėtėjimą iki 7 minučių 23 sekundžių naudojant 10 klasterio branduolių, toliau stebime tolygų lėtėjimą iki 1 minutės 30 sekundžių naudojant 40 klasterio branduolių ir paskui skaičiavimo greitis praktiškai nebekinta.


\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{img/1xnK}
\caption{Skaičiavimo greitis taikant vienmatis algoritmą MIF klasteryje} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Panašią pagreitėjimo kreivę matome ir taikydami dvimatį algoritmą, skaičiavimai smarkiai sulėtėja iki 11 minučių 47 sekundžių naudojant branduolių, toliau lėtėja tolygiai iki 2 minučių 20 sekundžių naudojant 45 branduolius, toliau skaičiavimai praktiškai nebegreitėja.

\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{img/nxnK}
\caption{Skaičiavimo greitis taikant dvimatį algoritmą MIF klasteryje} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Taigi matome, kad vienmatis algoritmas buvo greitesnis tiek vykdant skaičiavimus lokalioje aplinkoje tiek ir klasteryje.


\begin{figure}[H]
\centering
\includegraphics[scale=0.7]{img/bendrasK}
\caption{Bendras MIF klasterio skaičiavimų grafikas} % Antraštė įterpiama po paveikslėlio
\label{img:text}
\end{figure}

Eksperimentiniai rezultatai neatitinka teorijoje aprašytų ir tikėtųsi rezultatų, taip galėjo įvyktį dėl NumPy bibliotekos.

\pagebreak


\sectionnonum{Rezultatai}
Darbe buvo pasiekti šie rezultatai:
\begin{enumerate}
\item{Apibrėžtos ir paaiškintos matematinės lygtys ir skaitinių metodų algoritmai skirti difuzijos lygčių skaičiavimui.}
\item{Sudarytas SECM naudojanti Vilniaus universiteto mokslininkų darbu \cite{Astr}}
\item{Apibrėžti ir paaiškinti lygiagretūs algoritmai skirti difuzijos lygčių skaičiavimo pagreitinimui.}
\item{Surastas ir realizuotas optimalus vienmatis lygiagretus algoritmas.}
\item{Atlikti eksperimentai lokalioje aplinkoje ir nustatyta, kad optimaliam skaičiavimui negalima naudoti daugiau branduolių negu yra sistemoje ir surastas optimalus lygiagretus algoritmas – vienmatis.}
\item{Atlikti eksperimentai MIF klasteryje ir nustatymas optimalus vienmatis algoritmas skaičiavimams MIF klasteryje}
\end{enumerate}

\pagebreak


\sectionnonum{Išvados}
	Darbe pavyko sėkmingai identifikuoti matematines lygtis ir skaitinius metodus skirtus difuzijos procesui modeliuoti.
	Darbe atkartotas VU mokslininkų darbe\cite{Astr} taikytas SECM modelis.
	Pavyko sudaryti lankstų modelį, kuriame būtų galima skaičiuoti ir paralelizuoti kitus modelius su skirtingomis kraštinėmis sąlygomis.
	

	Naudojantis literatūroje aprašytais algoritmais\cite{Lygeg} buvo sėkmingai sutrumpintas skaičiavimų laikas.
	Vykdant skaičiavimus lokalioje aplinkoje modelio vykdymo laikas naudojant 1 branduolį buvo sutrumpinas nuo 49 minučių ir 15 sekundžių iki 10 minučių ir 16 sekundžių naudojant 5 branduolius.
	Mif klasteryje pavyko skaičiavimus pagreitinti nuo 1 valandos 35 minučių ir 26 sekundžių iki 1 minutės 30 sekundžių.
	Abiem skaičiavimo atvėjais gavome, kad optimalus lygiagretus algoritmas yra vienmatis algoritmas, kuriame tinklas yra dalijamas juostomis.


	Ateityje būtų galima analizuoti NumPy optimizacijų įtaką skaičiavimams ir skirtingus skaitinius metodus bei lygiagrečius algoritmus.
	
	
	
\pagebreak

\printbibliography[heading=bibintoc]
\pagebreak
\end{document}