From 17d1891ee5feec4f52ef9c51bfa60b78f0bd14c2 Mon Sep 17 00:00:00 2001 From: couturie Date: Wed, 24 Jul 2013 22:12:52 +0200 Subject: [PATCH] ch zulu --- BookGPU/BookGPU.tex | 1 + BookGPU/Chapters/chapter3/biblio3.bib | 46 +++- BookGPU/Chapters/chapter3/ch3.aux | 116 ++++---- BookGPU/Chapters/chapter3/ch3.tex | 253 +++++++++--------- .../chapter3/code/kernMedianForget1pix3.cu | 3 +- .../chapter3/code/kernMedianForget1pix3.cu~ | 56 +--- .../chapter3/code/kernMedianRegTri9.cu | 6 +- .../chapter3/code/kernMedianRegTri9.cu~ | 2 +- .../Chapters/chapter3/code/medianGeneric.cu | 2 +- .../Chapters/chapter3/code/medianGeneric.cu~ | 30 ++- BookGPU/Chapters/chapter3/img/debitPlot1.pdf | Bin 16071 -> 16067 bytes BookGPU/Chapters/chapter3/img/debitPlot2.pdf | Bin 16016 -> 16060 bytes BookGPU/Chapters/chapter4/biblio4.bib | 6 +- BookGPU/Chapters/chapter4/ch4.tex | 246 ++++++++--------- 14 files changed, 389 insertions(+), 378 deletions(-) diff --git a/BookGPU/BookGPU.tex b/BookGPU/BookGPU.tex index 3202b3b..90baace 100755 --- a/BookGPU/BookGPU.tex +++ b/BookGPU/BookGPU.tex @@ -37,6 +37,7 @@ \usepackage{commath} \usepackage{numprint} \usepackage{placeins} +%\usepackage{float} %\usepackage{lmodern} %% \usepackage{listings} %% \usepackage{subfigure} diff --git a/BookGPU/Chapters/chapter3/biblio3.bib b/BookGPU/Chapters/chapter3/biblio3.bib index 219118b..7cf9431 100755 --- a/BookGPU/Chapters/chapter3/biblio3.bib +++ b/BookGPU/Chapters/chapter3/biblio3.bib @@ -332,7 +332,9 @@ doi = {10.1109/NSSMIC.2009.5402323}, issn = {1095-7863}, keywords = {CUDA-based BVM filter; NVIDIA compute unified device architecture; O(M In M) computational complexity; O(M2) computational complexity; branchless vectorized median filter; computerised tomography; data-level parallelism; fast accessing scheme; high performance median filtering; memory layout; modern commodity graphics processing units; pivot median filter; vectorized median computation; biology computing; computerised tomography; medical image processing}, - month = {24 2009-nov. 1}, + year = {2009}, + month = {November}, + day = {24}, pages = {4142--4147}, title = {High performance median filtering using commodity graphics hardware}, year = {2009} @@ -351,12 +353,13 @@ @INPROCEEDINGS{6036776, author={Perrot, G. and Domas, S. and Couturier, R. and Bertaux, N.}, -booktitle={Computer and Information Technology (CIT), 2011 IEEE 11th International Conference on}, title={GPU Implementation of a Region Based Algorithm for Large Images Segmentation}, +booktitle={2011 IEEE 11th International Conference on Computer and Information Technology (CIT)}, +title={GPU Implementation of a Region Based Algorithm for Large Images Segmentation}, year={2011}, -month={31 2011-sept. 2}, +month={Sept.}, volume={}, number={}, -pages={291 -298}, +pages={291-298}, keywords={GPU implementation;Nvidia GPU architecture;algorithmic optimization;graphical processing units;image computing;image segmentation;image size;multicore CPU;multithreaded execution capability;region based algorithm;region-based active contour technique;snake algorithm;computer graphic equipment;coprocessors;image enhancement;image segmentation;multi-threading;multiprocessing systems;optimisation;}, doi={10.1109/CIT.2011.60}, ISSN={},} @@ -372,8 +375,9 @@ year = 1977 @INPROCEEDINGS{5402362, author={Kachelriess, M.}, booktitle={Nuclear Science Symposium Conference Record (NSS/MIC), 2009 IEEE}, title={Branchless vectorized median filtering}, -year={2009}, -month={24 2009-nov. 1}, +year = {2009}, +month = {November}, +day = {24}, volume={}, number={}, pages={4099 -4105}, @@ -383,7 +387,7 @@ ISSN={1095-7863},} @article{Weiss:2006:FMB:1141911.1141918, - author = {Weiss, B}, + author = {Weiss, B.}, title = {Fast median and bilateral filtering}, journal = {ACM Trans. Graph.}, issue_date = {July 2006}, @@ -451,12 +455,13 @@ ISSN={1520-6149},} @ARTICLE{4287006, author={Perreault, S. and Hebert, P.}, -journal={Image Processing, IEEE Transactions on}, title={Median Filtering in Constant Time}, +journal={IEEE Transactions on Image Processing} , +title={Median Filtering in Constant Time}, year={2007}, -month={sept. }, +month={Sept.}, volume={16}, number={9}, -pages={2389 -2394}, +pages={2389-2394}, keywords={algorithmic runtime complexity;filter kernel radius;image processing;median filtering algorithm;computational complexity;filtering theory;image processing;median filters;Algorithms;Computer Graphics;Image Enhancement;Image Interpretation, Computer-Assisted;Numerical Analysis, Computer-Assisted;Reproducibility of Results;Sensitivity and Specificity;Time Factors;User-Computer Interface;}, doi={10.1109/TIP.2007.902329}, ISSN={1057-7149},} @@ -466,7 +471,7 @@ author={Y. Wu and M. Eghbali and J. Ou and R. Lu and L. Toro and E. Stefani}, journal={Biophysical Journal}, title={Quantitative determination of spatial protein-protein correlations in fluorescence confocal microscopy.}, year={2010}, -month={feb. }, +month={Feb. }, volume={98}, number={3}, pages={493-504}, @@ -476,20 +481,22 @@ doi={10.1016/j.bpj.2009.10.037}, year={2012}, issn={1939-8018}, journal={Journal of Signal Processing Systems}, +volume={71}, +number={3}, doi={10.1007/s11265-012-0715-1}, title={Highly Parallelable Bidimensional Median Filter for Modern Parallel Programming Models}, url={http://dx.doi.org/10.1007/s11265-012-0715-1}, publisher={Springer US}, keywords={Nonlinear filters; Parallel algorithms; Image processing}, author={Sánchez, R. M. and Rodríguez, P. A.}, -pages={1-15}, +pages={221-235}, language={English} } @inproceedings{Batcher:1968:SNA:1468075.1468121, author = {Batcher, K. E.}, title = {Sorting networks and their applications}, - booktitle = {Proceedings of the April 30--May 2, 1968, spring joint computer conference}, + booktitle = {Proceedings of the April 30--May 2, 1968, Spring Joint Computer Conference}, series = {AFIPS '68 (Spring)}, year = {1968}, location = {Atlantic City, New Jersey}, @@ -506,4 +513,17 @@ language={English} author={Cormen, Thomas H and Leiserson, Charles E and Rivest, Ronald L and Stein, Clifford}, year={2001}, publisher={MIT press} +} +@article{median_zul, +year={2013}, +issn={1939-8018}, +journal={Journal of Signal Processing Systems}, +doi={10.1007/s11265-013-0799-2}, +title={Fine-tuned High-speed Implementation of a GPU-based Median Filter}, +url={http://dx.doi.org/10.1007/s11265-013-0799-2}, +publisher={Springer US}, +keywords={Median; Filter; GPU}, +author={Perrot, G. and Domas, S. and Couturier, R.}, +pages={1-6}, +language={English} } \ No newline at end of file diff --git a/BookGPU/Chapters/chapter3/ch3.aux b/BookGPU/Chapters/chapter3/ch3.aux index 69d76c6..0fb9a0d 100644 --- a/BookGPU/Chapters/chapter3/ch3.aux +++ b/BookGPU/Chapters/chapter3/ch3.aux @@ -4,18 +4,18 @@ \@writefile{toc}{\contentsline {chapter}{\numberline {3}Setting up the environnement.}{25}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\newlabel{algo:memcopy:H2D}{{7}{25}} -\newlabel{algo:memcopy:kernel}{{8}{25}} -\newlabel{algo:memcopy:D2H}{{9}{25}} -\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces Global memory management on CPU and GPU sides.\relax }}{25}} -\newlabel{algo:memcopy}{{1}{25}} -\@writefile{toc}{\contentsline {section}{\numberline {3.1}Data transfers, memory management.}{26}} +\@writefile{toc}{\contentsline {section}{\numberline {3.1}Data transfers, memory management.}{25}} +\newlabel{algo:memcopy:H2D}{{7}{26}} +\newlabel{algo:memcopy:kernel}{{8}{26}} +\newlabel{algo:memcopy:D2H}{{9}{26}} +\@writefile{loa}{\contentsline {algocf}{\numberline {1}{\ignorespaces global memory management on CPU and GPU sides\relax }}{26}} +\newlabel{algo:memcopy}{{1}{26}} \newlabel{lst:main1}{{3.1}{27}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.1}Generic main.cu file used to launch CUDA kernels}{27}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.1}generic main.cu file used to launch CUDA kernels}{27}} \newlabel{lst:fkern1}{{3.2}{27}} \@writefile{lol}{\contentsline {lstlisting}{\numberline {3.2}fast\_kernels.cu file featuring one kernel skeleton}{27}} \newlabel{lst:mkfile}{{3.3}{28}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.3}Generic Makefile based on those provided by NV SDK}{28}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {3.3}generic makefile based on those provided by NVIDIA SDK}{28}} \@writefile{toc}{\contentsline {section}{\numberline {3.2}Performance measurements}{28}} \newlabel{lst:chronos}{{3.4}{28}} \@writefile{lol}{\contentsline {lstlisting}{\numberline {3.4}Time measurement technique using cutil functions}{28}} @@ -27,69 +27,69 @@ \@writefile{toc}{\contentsline {section}{\numberline {4.1}Introduction}{31}} \@writefile{toc}{\contentsline {section}{\numberline {4.2}Median filtering}{32}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.2.1}Basic principles}{32}} -\@writefile{toc}{\contentsline {subsection}{\numberline {4.2.2}A naive implementation}{32}} -\newlabel{img:sap_example_ref}{{4.1(a)}{33}} -\newlabel{sub@img:sap_example_ref}{{(a)}{33}} -\newlabel{img:sap_example_med3}{{4.1(b)}{33}} -\newlabel{sub@img:sap_example_med3}{{(b)}{33}} -\newlabel{img:sap_example_med5}{{4.1(c)}{33}} -\newlabel{sub@img:sap_example_med5}{{(c)}{33}} -\newlabel{img:sap_example_med3_it2}{{4.1(d)}{33}} -\newlabel{sub@img:sap_example_med3_it2}{{(d)}{33}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.1}{\ignorespaces Example of median filtering, applied to salt \& pepper noise reduction.\relax }}{33}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Airplane image, corrupted by salt and pepper noise of density 0.25}}}{33}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Image denoised by a $3\times 3$ median filter}}}{33}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Image denoised by a $5\times 5$ median filter}}}{33}} -\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Image denoised by 2 iterations of a $3\times 3$ median filter}}}{33}} -\newlabel{fig:sap_examples}{{4.1}{33}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.1}{\ignorespaces Example of 5x5 median filtering\relax }}{32}} +\newlabel{fig:median_1}{{4.1}{32}} +\newlabel{algoMedianGeneric}{{2}{33}} +\newlabel{algoMedianGeneric:memcpyH2D}{{1}{33}} +\newlabel{algoMedianGeneric:cptstart}{{3}{33}} +\newlabel{algoMedianGeneric:cptend}{{5}{33}} +\newlabel{algoMedianGeneric:memcpyD2H}{{7}{33}} +\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces generic n$\times $n median filter\relax }}{33}} +\@writefile{toc}{\contentsline {subsection}{\numberline {4.2.2}A naive implementation}{33}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.2}{\ignorespaces Illustration of window overlapping in 5x5 median filtering\relax }}{34}} +\newlabel{fig:median_overlap}{{4.2}{34}} \newlabel{lst:medianGeneric}{{4.1}{34}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.1}Generic CUDA kernel achieving median filtering}{34}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.2}{\ignorespaces Example of 5x5 median filtering\relax }}{35}} -\newlabel{fig:median_1}{{4.2}{35}} -\newlabel{algoMedianGeneric}{{2}{35}} -\newlabel{algoMedianGeneric:memcpyH2D}{{1}{35}} -\newlabel{algoMedianGeneric:cptstart}{{3}{35}} -\newlabel{algoMedianGeneric:cptend}{{5}{35}} -\newlabel{algoMedianGeneric:memcpyD2H}{{7}{35}} -\@writefile{loa}{\contentsline {algocf}{\numberline {2}{\ignorespaces generic n$\times $n median filter\relax }}{35}} -\@writefile{toc}{\contentsline {section}{\numberline {4.3}NVidia GPU tuning recipes}{35}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.3}{\ignorespaces Illustration of window overlapping in 5x5 median filtering\relax }}{36}} -\newlabel{fig:median_overlap}{{4.3}{36}} -\@writefile{lot}{\contentsline {table}{\numberline {4.1}{\ignorespaces Performance results of \texttt {kernel medianR}. \relax }}{36}} -\newlabel{tab:medianHisto1}{{4.1}{36}} -\@writefile{toc}{\contentsline {section}{\numberline {4.4}A 3$\times $3 median filter: using registers }{37}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.1}generic CUDA kernel achieving median filtering}{34}} +\@writefile{lot}{\contentsline {table}{\numberline {4.1}{\ignorespaces Performance results of \texttt {kernel medianR}. \relax }}{35}} +\newlabel{tab:medianHisto1}{{4.1}{35}} +\@writefile{toc}{\contentsline {section}{\numberline {4.3}NVIDIA GPU tuning recipes}{35}} +\newlabel{img:sap_example_ref}{{4.3(a)}{36}} +\newlabel{sub@img:sap_example_ref}{{(a)}{36}} +\newlabel{img:sap_example_med3}{{4.3(b)}{36}} +\newlabel{sub@img:sap_example_med3}{{(b)}{36}} +\newlabel{img:sap_example_med5}{{4.3(c)}{36}} +\newlabel{sub@img:sap_example_med5}{{(c)}{36}} +\newlabel{img:sap_example_med3_it2}{{4.3(d)}{36}} +\newlabel{sub@img:sap_example_med3_it2}{{(d)}{36}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.3}{\ignorespaces Example of median filtering, applied to salt and pepper noise reduction.\relax }}{36}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Airplane image, corrupted by salt and pepper noise of density 0.25}}}{36}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Image denoised by a $3\times 3$ median filter}}}{36}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Image denoised by a $5\times 5$ median filter}}}{36}} +\@writefile{lof}{\contentsline {subfigure}{\numberline{(d)}{\ignorespaces {Image denoised by 2 iterations of a $3\times 3$ median filter}}}{36}} +\newlabel{fig:sap_examples}{{4.3}{36}} +\@writefile{toc}{\contentsline {section}{\numberline {4.4}A 3$\times $3 median filter: using registers}{37}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.4.1}The simplest way}{37}} \newlabel{lst:kernelMedian3RegTri9}{{4.2}{38}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.2}3$\times $3 median filter kernel using one register per neighborhood pixel and bubble sort}{38}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.2}$3\times 3$ median filter kernel using one register per neighborhood pixel and bubble sort}{38}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.4.2}Further optimization}{38}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.4}{\ignorespaces Comparison of pixel throughputs on GPU C2070 and CPU for generic median, 3$\times $3 median register-only and \textit {libJacket}.\relax }}{39}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.4}{\ignorespaces Comparison of pixel throughputs for CPU generic median, CPU 3$\times $3 median register-only with bubble sort, GPU generic median, GPU 3$\times $3 median register-only with bubble sort, and GPU libJacket.}}{39}} \newlabel{fig:compMedians1}{{4.4}{39}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {4.4.2.1}Reducing register count }{39}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.5}{\ignorespaces Forgetful selection with the minimal element register count. Illustration for 3$\times $3 pixel window represented in a row and supposed sorted.\relax }}{40}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.5}{\ignorespaces Forgetful selection with the minimal element register count. Illustration for $3\times 3$ pixel window represented in a row and supposed sorted.\relax }}{40}} \newlabel{fig:forgetful_selection}{{4.5}{40}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.6}{\ignorespaces Determination of the Median value by the forgetful selection process, applied to a $3\times 3$ neighborhood window.\relax }}{41}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.6}{\ignorespaces Determination of the median value by the \textit {forgetful selection} process, applied to a $3\times 3$ neighborhood window.\relax }}{41}} \newlabel{fig:forgetful3}{{4.6}{41}} -\newlabel{lst:medianForget1pix3}{{4.3}{41}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.3}3$\times $3 median filter kernel using the minimum register count of 6 to find the median value by forgetful selection method. The optimal thread block size is 128 on GTX280 and 256 on C2070.}{41}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.7}{\ignorespaces First iteration of the $5\times 5$ selection process, with $k_{25}=14$, which shows how Instruction Level Parallelism is maximized by the use of an incomplete sorting network.}}{41}} +\newlabel{fig:bitonic}{{4.7}{41}} +\newlabel{lst:medianForget1pix3}{{4.3}{42}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.3}3$\times $3 median filter kernel using the minimum register count of 6 to find the median value by forgetful selection method. The optimal thread block size is 128 on GTX280 and 256 on C2070}{42}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {4.4.2.2}More data output per thread}{42}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.7}{\ignorespaces Illustration of how window overlapping is used to combine 2 pixel selections in a 3$\times $3 median kernel.\relax }}{42}} -\newlabel{fig:median3_overlap}{{4.7}{42}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.8}{\ignorespaces Illustration of how window overlapping is used to combine 2 pixel selections in a $3\times 3$ median kernel.\relax }}{43}} +\newlabel{fig:median3_overlap}{{4.8}{43}} \newlabel{lst:medianForget2pix3}{{4.4}{43}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.4}3$\times $3 median filter kernel processing 2 output pixel values per thread using combined forgetful selection.}{43}} -\@writefile{toc}{\contentsline {section}{\numberline {4.5}A 5$\times $5 and more median filter }{43}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.8}{\ignorespaces Comparison of pixel throughput on GPU C2070 for the different 3$\times $3 median kernels.\relax }}{44}} -\newlabel{fig:compMedians2}{{4.8}{44}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.4}$3\times 3$ median filter kernel processing 2 output pixel values per thread using combined forgetful selection}{43}} +\@writefile{toc}{\contentsline {section}{\numberline {4.5}A 5$\times $5 and more median filter }{44}} \newlabel{sec:median5}{{4.5.1}{44}} \@writefile{toc}{\contentsline {subsection}{\numberline {4.5.1}A register-only 5$\times $5 median filter }{44}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.9}{\ignorespaces Reducing register count in a 5$\times $5 register-only median kernel outputting 2 pixels simultaneously.}}{45}} -\newlabel{fig:median5overlap}{{4.9}{45}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.10}{\ignorespaces First iteration of the $5\times 5$ selection process, with $k_{25}=14$, which shows how Instruction Level Parallelism is maximized by the use of an incomplete sorting network.}}{45}} -\newlabel{fig:bitonic}{{4.10}{45}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.9}{\ignorespaces Comparison of pixel throughput on GPU C2070 for the different 3$\times $3 median kernels.\relax }}{45}} +\newlabel{fig:compMedians2}{{4.9}{45}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.10}{\ignorespaces Reducing register count in a 5$\times $5 register-only median kernel outputting 2 pixels simultaneously.}}{45}} +\newlabel{fig:median5overlap}{{4.10}{45}} \newlabel{lst:medianForget2pix5}{{4.5}{46}} -\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.5}kernel 5$\times $5 median filter processing 2 output pixel values per thread by a combined forgetfull selection.}{46}} +\@writefile{lol}{\contentsline {lstlisting}{\numberline {4.5}kernel 5$\times $5 median filter processing 2 output pixel values per thread by a combined forgetfull selection}{46}} \@writefile{lot}{\contentsline {table}{\numberline {4.2}{\ignorespaces Performance of various 5$\times $5 median kernel implementations, applied on 4096$\times $4096 pixel image with C2070 GPU card.\relax }}{47}} \newlabel{tab:median5comp}{{4.2}{47}} -\@writefile{toc}{\contentsline {subsection}{\numberline {4.5.2}Fast approximated n$\times $n median filter }{47}} +\@writefile{toc}{\contentsline {subsection}{\numberline {4.5.2}Fast approximated $n\times n$ median filter }{47}} \@writefile{lot}{\contentsline {table}{\numberline {4.3}{\ignorespaces Measured performance of one generic pseudo-separable median kernel applied to 4096$\times $4096 pixel image with various window sizes.\relax }}{48}} \newlabel{tab:medianSeparable}{{4.3}{48}} \newlabel{img:sap_example_ref}{{4.11(a)}{49}} @@ -100,7 +100,7 @@ \newlabel{sub@img:sap_example_sep_med5}{{(c)}{49}} \newlabel{img:sap_example_sep_med3_it2}{{4.11(d)}{49}} \newlabel{sub@img:sap_example_sep_med3_it2}{{(d)}{49}} -\@writefile{lof}{\contentsline {figure}{\numberline {4.11}{\ignorespaces Example of separable median filtering (smoother), applied to salt \& pepper noise reduction.\relax }}{49}} +\@writefile{lof}{\contentsline {figure}{\numberline {4.11}{\ignorespaces Example of separable median filtering (smoother), applied to salt and pepper noise reduction.\relax }}{49}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(a)}{\ignorespaces {Airplane image, corrupted with by salt and pepper noise of density 0.25}}}{49}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(b)}{\ignorespaces {Image denoised by a $3\times 3$ separable smoother}}}{49}} \@writefile{lof}{\contentsline {subfigure}{\numberline{(c)}{\ignorespaces {Image denoised by a $5\times 5$ separable smoother}}}{49}} @@ -114,7 +114,7 @@ \setcounter{enumi}{3} \setcounter{enumii}{0} \setcounter{enumiii}{0} -\setcounter{enumiv}{11} +\setcounter{enumiv}{12} \setcounter{footnote}{0} \setcounter{mpfootnote}{0} \setcounter{part}{2} diff --git a/BookGPU/Chapters/chapter3/ch3.tex b/BookGPU/Chapters/chapter3/ch3.tex index 6a5181b..64709ea 100755 --- a/BookGPU/Chapters/chapter3/ch3.tex +++ b/BookGPU/Chapters/chapter3/ch3.tex @@ -15,8 +15,18 @@ Obviously, our code originally accepts various image dimensions and can process However, so as to propose concise and more readable code, we will assume the following limitations: 16~bit-coded gray-level input images whose dimensions $H\times W$ are multiples of 512 pixels. +\section{Data transfers, memory management.} +This section deals with the following issues: +\begin{enumerate} +\item Data transfer from CPU memory to GPU global memory: several GPU memory areas are available as destination memory but the 2D caching mechanism of texture memory, \index{memory~hierarchy!texture~memory} specifically designed for fetching neighboring pixels, is currently the fastest way to fetch gray-level pixel values inside a kernel computation. This has led us to choose \textbf{texture memory} as primary GPU memory area for input images. +\item Data fetching from GPU global memory to kernel local memory: as said above, we use texture memory. \index{memory~hierarchy!texture~memory} Depending on which process is run, texture data is used either by direct fetching in kernel local memory or through a prefetching \index{prefetching} in shared memory. \index{memory~hierarchy!shared~memory} +\item Data outputting from kernels to GPU memory: there is actually no alternative to global memory, as kernels cannot directly write into texture memory and as copying from texture to CPU memory would not be faster than from simple global memory. +\item Data transfer from GPU global memory to CPU memory: it can be drastically accelerated by use of \textbf{pinned memory}, \index{memory~hierarchy!pinned~memory} keeping in mind it has to be used sparingly. +\end{enumerate} +Algorithm \ref{algo:memcopy} summarizes all the above considerations and describes how data are handled in our examples. For more information on how to handle the different types of GPU memory, we suggest referring to the CUDA programmer's guide. + \begin{algorithm} -\SetNlSty{}{}{:} +%\SetNlSty{}{}{:} allocate and populate CPU memory \textbf{h\_in}\; allocate CPU pinned-memory \textbf{h\_out}\; allocate GPU global memory \textbf{d\_out}\; @@ -26,119 +36,81 @@ However, so as to propose concise and more readable code, we will assume the fol copy data from \textbf{h\_in} to \textbf{array\_img\_in}\label{algo:memcopy:H2D}\; kernel\kl gridDim,blockDim\kr()\tcc*[f]{outputs to d\_out}\label{algo:memcopy:kernel}\; copy data from \textbf{d\_out} to \textbf{h\_out} \label{algo:memcopy:D2H}\; -\caption{Global memory management on CPU and GPU sides.} +\caption{global memory management on CPU and GPU sides} \label{algo:memcopy} \end{algorithm} -\section{Data transfers, memory management.} -This section deals with the following issues: -\begin{enumerate} -\item Data transfer from CPU memory to GPU global memory: several GPU memory areas are available as destination memory but the 2-D caching mechanism of texture memory \index{memory~hierarchy!texture~memory}, specifically designed for fetching neighboring pixels, is currently the fastest way to fetch gray-level pixel values inside a kernel computation. This has led us to choose \textbf{texture memory} as primary GPU memory area for input images. -\item Data fetching from GPU global memory to kernel local memory: as said above, we use texture memory. \index{memory~hierarchy!texture~memory} Depending on which process is run, texture data is used either by direct fetching in kernel local memory or through a prefetching \index{prefetching} in shared memory \index{memory~hierarchy!shared~memory}. -\item Data outputting from kernels to GPU memory: there is actually no alternative to global memory, as kernels can not directly write into texture memory and as copying from texture to CPU memory would not be faster than from simple global memory. -\item Data transfer from GPU global memory to CPU memory: it can be drastically accelerated by use of \textbf{pinned memory}, \index{memory~hierarchy!pinned~memory} keeping in mind it has to be used sparingly. -\end{enumerate} -Algorithm \ref{algo:memcopy} summarizes all the above considerations and describes how data are handled in our examples. For more information on how to handle the different types of GPU memory, we suggest to refer to the CUDA programmer's guide. -At debug stage, for simplicity's sake, we use the \textbf{cutil} \index{Cutil library} library supplied by the NVidia development kit (SDK). Thus, in order to easily implement our examples, we suggest readers to download and to install the latest NVidia-SDK (ours is SDK4.0), create a new directory \textit{SDK-root-dir/C/src/fast\_kernels} and adapt the generic \textit{Makefile} that can be found in each sub-directory of \textit{SDK-root-dir/C/src/}. Then, only two more files will be enough to have a fully operational environnement: \textit{main.cu} and \textit{fast\_kernels.cu}. +At debug stage, for simplicity's sake, we use the \textbf{cutil} \index{Cutil library} library supplied by the NVIDIA software development kit (SDK). Thus, in order to easily implement our examples, we suggest readers download and install the latest NVIDIA-SDK (ours is SDK4.0), create a new directory \textit{SDK-root-dir/C/src/fast\_kernels} and adapt the generic \textit{Makefile} that can be found in each subdirectory of \textit{SDK-root-dir/C/src/}. Then, only two more files will be needed to have a fully operational environnement: \textit{main.cu} and \textit{fast\_kernels.cu}. Listings \ref{lst:main1}, \ref{lst:fkern1} and \ref{lst:mkfile} implement all the above considerations minimally, while remaining functional. The main file of Listing \ref{lst:main1} is a simplified version of our actual main file. -It has to be noticed that cutil functions \texttt{cutLoadPGMi} \index{Cutil library!cutLoadPGMi} and \texttt{cutSavePGMi} \index{Cutil library!cutSavePGMi} only operate on unsigned integer data. As data is coded in short integer format for performance reasons, the use of these functions involves casting data after loading and before saving. This may be overcome by use of a different library. Actually, our choice was to modify the above mentioned cutil functions. +It has to be noted that functions \texttt{cutLoadPGMi} \index{Cutil library!cutLoadPGMi} and \texttt{cutSavePGMi} \index{Cutil library!cutSavePGMi} of the \textbf{cutil} library operate only on unsigned integer data. As data is coded in short integer format for performance reasons, the use of these functions involves one data cast after loading and before saving. This may be overcome by use of a different library. Actually, our choice was to modify the above mentioned cutil functions. Listing \ref{lst:fkern1} gives a minimal kernel skeleton that will serve as the basis for all other kernels. Lines 5 and 6 determine the coordinates $(i, j)$ of the pixel to be processed, each pixel being associated to one thread. -The instruction in line 8 combines writing the output gray-level value into global memory and fetching the input gray-level value from 2-D texture memory. +The instruction in line 8 combines writing the output gray-level value into global memory and fetching the input gray-level value from 2D texture memory. The Makefile given in Listing \ref{lst:mkfile} shows how to adapt examples given in SDK. -\lstinputlisting[label={lst:main1},caption=Generic main.cu file used to launch CUDA kernels]{Chapters/chapter3/code/mainSkel.cu} +\lstinputlisting[label={lst:main1},caption=generic main.cu file used to launch CUDA kernels]{Chapters/chapter3/code/mainSkel.cu} \lstinputlisting[label={lst:fkern1},caption=fast\_kernels.cu file featuring one kernel skeleton]{Chapters/chapter3/code/kernSkel.cu} -\lstinputlisting[label={lst:mkfile},caption=Generic Makefile based on those provided by NV SDK]{Chapters/chapter3/code/Makefile} +\lstinputlisting[label={lst:mkfile},caption=generic makefile based on those provided by NVIDIA SDK]{Chapters/chapter3/code/Makefile} \section{Performance measurements} -As our goal is to design very fast implementations of basic image processing algorithms, we need to make quite accurate time-measurements, within the order of magnitude of $0.01~ms$. Again, the easiest way of doing so is to use the helper functions of the cutil library. As usual, as the durations we are measuring are short and possibly subject to non neglectable variations, a good practice is to measure multiple executions and issue the mean runtime. All time results given in this chapter have been obtained through 1000 calls to each kernel. +As our goal is to design very fast implementations of basic image processing algorithms, we need to make quite accurate time-measurements, within the order of magnitude of $0.01$~ms. Again, the easiest way of doing so is to use the helper functions of the \textbf{cutil} library. As usual, because the durations we are measuring are short and possibly subject to non negligible variations, a good practice is to measure multiple executions and report the mean runtime. All time results given in this chapter have been obtained through 1000 calls to each kernel. -Listing \ref{lst:chronos} shows how to use the dedicated cutil functions \index{Cutil library!Timer usage}. Timer declaration and creation only need to be performed once while reset, start and stop can be used as often as necessary. Synchronization is mandatory before stopping the timer (Line 7), to avoid runtime measurement being biased. +Listing \ref{lst:chronos} shows how to use the dedicated \textbf{cutil} functions \index{Cutil library!Timer usage}. Timer declaration and creation need to be performed only once while reset, start and stop functions can be used as often as necessary. Synchronization is mandatory before stopping the timer (Line 7), to avoid runtime measurement being biased. \lstinputlisting[label={lst:chronos},caption=Time measurement technique using cutil functions]{Chapters/chapter3/code/exChronos.cu} -In an attempt to provide relevant speedup values, we either implemented CPU versions of the algorithms studied, or used the values found in existing literature. Still, the large number and diversity of hardware platforms and GPU cards makes it impossible to benchmark every possible combination and significant differences may occur between the speedups we announce and those obtained with different devices. As a reference, our developing platform details as follows: +In an attempt to provide relevant speedup values, we either implemented CPU versions of the algorithms studied or used the values found in existing literature. Still, the large number and diversity of hardware platforms and GPU cards makes it impossible to benchmark every possible combination and significant differences may occur between the speedups we report and those obtained with different devices. As a reference, our developing platform details as follows: \begin{itemize} -\item CPU codes run on: +\item CPU codes run on \begin{itemize} \item \textbf{Xeon}: a recent and very efficient Quad Core Xeon E31245 at 3.3GHz-8GByte RAM running Linux kernel 3.2. \end{itemize} -\item GPU codes run on: +\item GPU codes run on \begin{itemize} - \item \textbf{C2070}: Nvidia Tesla C2070 hosted by a PC QuadCore Xeon E5620 at 2.4GHz-12GByte RAM, running Linux kernel 2.6.18 - \item \textbf{GTX280}: NVidia GeForce GTX 280 hosted by a PC QuadCore Xeon X5482 at 3.20GHz-4GByte RAM, running Linux kernel 2.6.32 + \item \textbf{C2070}: NVIDIA Tesla C2070 hosted by a PC QuadCore Xeon E5620 at 2.4GHz-12GByte RAM, running Linux kernel 2.6.18 + \item \textbf{GTX280}: NVIDIA GeForce GTX 280 hosted by a PC QuadCore Xeon X5482 at 3.20GHz-4GByte RAM, running Linux kernel 2.6.32 \end{itemize} \end{itemize} -All kernels have also been tested with various image sizes from 512$\times$512 to 4096$\times$4096 pixels. This allows to guess runtime dependancy over image size. +All kernels have also been tested with various image sizes from 512$\times$512 to 4096$\times$4096 pixels. This allows estimating runtime dependancy over image size. Last, like many authors, we chose to use the pixel throughput value of each process in Mega Pixels per second (MP/s) as a performance indicator, including data transfers and kernel runtimes. -In order to estimate the potential for improvement of each kernel, a reference throughput measurement, involving identity kernel of Listing \ref{lst:fkern1}, was performed. As this kernel only fetches input values from texture memory and outputs them to global memory without doing any computation, it represents the smallest, thus fastest, possible process and is taken as the reference throughput value (100\%). The same measurement was performed on CPU, with a maximum effective pixel throughput of 130~Mpixel per second. On GPU, depending on grid parameters it amounts to 800~MPixels/s on GTX280 and 1300~Mpixels/s on C2070. +In order to estimate the potential for improvement of each kernel, a reference throughput measurement, involving the identity kernel of Listing \ref{lst:fkern1}, was performed. As this kernel only fetches input values from texture memory and outputs them to global memory without doing any computation, it represents the smallest, thus fastest, possible process and is taken as the reference throughput value (100\%). The same measurement was performed on CPU, with a maximum effective pixel throughput of $130~MP/s$. On GPU, depending on grid parameters this measurement was $800~MP/s$ on GTX280 and $1300~MP/s$ on C2070. \chapterauthor{Gilles Perrot}{Femto-ST Institute, University of Franche-Comte, France} \chapter{Implementing a fast median filter} \section{Introduction} -Median filtering is a well-known method used in a wide range of application frameworks as well as a standalone filter especially for \textit{salt and pepper} denoising. It is able to highly reduce power of noise without blurring edges too much. That is actually why we originally focused on this filtering technique as a preprocessing stage when we were in the process of designing a GPU implementation of one region-based image segmentation algorithm \cite{6036776}. +Median filtering is a well-known method used in a wide range of application frameworks as well as a standalone filter especially for \textit{salt and pepper} denoising. It is able to greatly reduce the power of noise without blurring edges too much. That is actually why we originally focused on this filtering technique as a preprocessing stage when we were in the process of designing a GPU implementation of one region-based image segmentation algorithm \cite{6036776}. -First introduced by Tukey in \cite{tukey77}, it has been widely studied since then, and many researchers have proposed efficient implementations of it, adapted to various hypothesis, architectures and processors. -Originally, its main drawbacks were its compute complexity, its non linearity and its data-dependent runtime. Several researchers have addressed these issues and designed, for example, efficient histogram-based median filter with predictible runtimes \cite{Huang:1981:TDS:539567, Weiss:2006:FMB:1179352.1141918}. +First introduced by Tukey in \cite{tukey77}, it has been widely studied since then, and many researchers have proposed efficient implementations of it, adapted to various hypotheses, architectures and processors. +Originally, its main drawbacks were its compute complexity, its nonlinearity and its data-dependent runtime. Several researchers have addressed these issues and designed, for example, efficient histogram-based median filters with predictible runtimes \cite{Huang:1981:TDS:539567, Weiss:2006:FMB:1179352.1141918}. -More recently, the advent of GPUs opened new perspectives in terms of image processing performance, and some researchers managed to take advantage of the new graphic capabilities: in that respect, we can cite the Branchless Vectorized Median filter (BVM) \cite{5402362, chen09} which allows very interesting runtimes on CUDA-enabled devices but, as far as we know, the fastest implementation to date is the histogram-based PCMF median filter \cite{Sanchez-2-2012}. +More recently, the advent of GPUs opened new perspectives in terms of image processing performance, and some researchers managed to take advantage of the new graphics capabilities: in that respect, we can cite the Branchless Vectorized Median (BVM) filter \cite{5402362, chen09} which allows very interesting runtimes on CUDA-enabled devices but, as far as we know, the fastest implementation to date is the histogram-based PCMF median filter \cite{Sanchez-2-2012}. -Some of the following implementations feature very fast runtimes; They are targeted on Nvidia Tesla GPU (Fermi architecture, compute capability 2.x) but may easily be adapted to other models e.g. those of compute capability 1.3. +Some of the following implementations feature very fast runtimes. They are targeted on NVIDIA Tesla GPU (Fermi architecture, compute capability 2.x) but may easily be adapted to other models, e.g., those of compute capability 1.3. -The fastest ones are based on one efficient parallel implementation of the BVM algorithm described in \cite{mcguire2008median}, improving its performance through fine tuning of its implementation. +The fastest ones are based on one efficient parallel implementation of the BVM algorithm described in \cite{mcguire2008median}, improving its performance through fine tuning of its implementation as presented in \cite{median_zul} and detailed in the following sections. \section{Median filtering} \subsection{Basic principles} -Designing a 2-D median filter basically consists in defining a square window $H(i,j)$ for each pixel $I(i,j)$ of the input image, containing $n\times n$ pixels and centered on $I(i,j)$. The output value $I'(i,j)$ is the median value of the gray level values of the $n\times n$ pixels of $H(i,j)$. Figure \ref{fig:median_1} illustrates this principle with an example of a 5x5 median filter applied on pixel $I(5,6)$. The output value is the median value of the 25 values of the dark gray window centered on pixel $I(5,6)$. -Figure \ref{fig:sap_examples} shows an example of a $512\times 512$ pixel image, corrupted by a \textit{salt and pepper} noise and the denoised versions, output respectively by a $3\times 3$, a $5\times 5$ and a 2 iterations $3\times 3 $ median filter. -\begin{figure} -\centering - \subfigure[Airplane image, corrupted by salt and pepper noise of density 0.25]{\label{img:sap_example_ref} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25.png}}\qquad - \subfigure[Image denoised by a $3\times 3$ median filter]{\label{img:sap_example_med3} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_med3.png}}\\ - \subfigure[Image denoised by a $5\times 5$ median filter]{\label{img:sap_example_med5} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_med5.png}}\qquad - \subfigure[Image denoised by 2 iterations of a $3\times 3$ median filter]{\label{img:sap_example_med3_it2} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_med3_it2.png}}\\ - \caption{Example of median filtering, applied to salt \& pepper noise reduction.} - \label{fig:sap_examples} -\end{figure} - - The generic filtering method is given by Algorithm \ref{algoMedianGeneric}. After the data transfer stage of the first line, which copies data from CPU memory to GPU texture memory, the actual median computing occurs, before the final transfer which copies data back to CPU memory at the last line. Obviously, one key issue is the selection method that identifies the median value. But, as shown in figure \ref{fig:median_overlap}, since two neighboring pixels share part of the values to be sorted, a second key issue is how to rule redundancy between consecutive positions of the running window $H(i,j)$. -As mentioned earlier, the selection of the median value can be performed by more than one technique, using either histogram-based or sorting methods, each of them having its own benefits and drawbacks as will be discussed further down. - -\subsection{A naive implementation} -As a reference, Listing \ref{lst:medianGeneric} gives a simple, not to say simplistic implementation of a CUDA kernel (\texttt{kernel\_medianR}) achieving generic $n\times n$ histogram-based median filtering. Its runtime has a very low data dependency, but this implementation does not suit very well GPU architecture. Each pixel loads the whole of its $n\times n$ neighborhood meaning that one pixel is loaded multiple times inside one single thread block, and above all, the use of a local vector (histogram[]) considerably downgrades performance, as the compiler automatically stores such vectors in local memory (slow) \index{memory~hierarchy!local~memory}. - -Table \ref{tab:medianHisto1} displays measured runtimes of \texttt{kernel\_medianR} and pixel throughputs for each GPU version and for both CPU and GPU implementations. Usual window sizes of $3\times 3$, $5\times 5$ and $7\times 7$ are shown. Though some specific applications require larger window sizes and dedicated algorithms, such small square window sizes are most widely used in general purpose image processing. GPU runtimes have been obtained with a grid of 64-thread blocks. This block size, is a good compromise in this case. - -The first observation to make when analysing results of Table \ref{tab:medianHisto1} is that, on CPU, window size has almost no influence on the effective pixel throughput. -Since inner loops that fill the histogram vector contain very few fetching instructions (from 9 to 49, depending on the window size), it is not surprising to note their neglectable impact compared to outer loops that fetch image pixels (from 256k to 16M instructions). -One could be tempted to claim that CPU has no chance to win, which is not so obvious as it highly depends on what kind of algorithm is run and above all, how it is implemented. To illustrate this, we can notice that, despite a maximum effective throughput potential that is almost five times higher, measured GTX280 throughput values sometimes prove slower than CPU values, as shown in Table \ref{tab:medianHisto1}. - - -\lstinputlisting[label={lst:medianGeneric},caption=Generic CUDA kernel achieving median filtering]{Chapters/chapter3/code/medianGeneric.cu} - - -On the GPU's side, we note high dependence on window size due to the redundancy induced by the multiple fetches of each pixel inside each block, becoming higher with the window size as illustrated by Figure \ref{fig:median_overlap}. On C2070 card, thanks to a more efficient caching mechanism, this effect is lesser. On GPUs, dependency over image size is low, and due to slightly more efficient data transfers when copying larger data amounts, pixel throughputs increases with image size. As an example, transferring a 4096$\times$4096 pixel image (32~MBytes) is a bit faster than transferring 64 times a 512$\times$512 pixel image (0.5~MBytes). - -%% mettre l'eau à la bouche - -\begin{figure} +Designing a 2D median filter basically consists of defining a square window $H(i,j)$ for each pixel $I(i,j)$ of the input image, containing $n\times n$ pixels and centered on $I(i,j)$. The output value $I'(i,j)$ is the median value of the gray-level values of the $n\times n$ pixels of $H(i,j)$. Figure \ref{fig:median_1} illustrates this principle with an example of a 5x5 median filter applied on pixel $I(5,6)$. The output value is the median value of the 25 values of the dark gray window centered on pixel $I(5,6)$. +\begin{figure}[b] \centering \includegraphics[width=8cm]{Chapters/chapter3/img/median_1.png} \caption{Example of 5x5 median filtering} \label{fig:median_1} \end{figure} +Figure \ref{fig:sap_examples} shows an example of a $512\times 512$ pixel image, corrupted by a \textit{salt and pepper} noise and the denoised versions, output respectively by a $3\times 3$, a $5\times 5$, and 2 iterations of a $3\times 3$ median filter. + The generic filtering method is given by Algorithm \ref{algoMedianGeneric}. After the data transfer stage of the first line, which copies data from CPU memory to GPU texture memory, the actual median computing occurs, before the final transfer which copies data back to CPU memory at the last line. Obviously, one key issue is the selection method that identifies the median value. But, as shown in Figure \ref{fig:median_overlap}, since two neighboring pixels share part of the values to be sorted, a second key issue is how to rule redundancy between consecutive positions of the running window $H(i,j)$. \begin{algorithm} %\SetNlSty{}{}{:} % \SetLine @@ -152,8 +124,19 @@ On the GPU's side, we note high dependence on window size due to the redundancy copy data from GPU global memory to CPU memory\label{algoMedianGeneric:memcpyD2H}\; \caption{\label{algoMedianGeneric}generic n$\times$n median filter} \end{algorithm} +As mentioned earlier, the selection of the median value can be performed by more than one technique, using either histogram-based or sorting methods, each having its own benefits and drawbacks as will be discussed further down. -\begin{figure} +\subsection{A naive implementation} +As a reference, Listing \ref{lst:medianGeneric} gives a simple, not to say simplistic, implementation of a CUDA kernel (\texttt{kernel\_medianR}) achieving generic $n\times n$ histogram-based median filtering. Its runtime has a very low data dependency, but this implementation does not suit GPU architecture very well. Each pixel loads the whole of its $n\times n$ neighborhood, meaning that one pixel is loaded multiple times inside one single thread block, and even more time-consuming, the use of a local vector (histogram[]) considerably downgrades performance, as the compiler automatically stores such vectors in local memory (slow) \index{memory~hierarchy!local~memory}. + +Table \ref{tab:medianHisto1} displays measured runtimes of \texttt{kernel\_medianR} and pixel throughputs for each GPU version (C2070 and GTX480 targets) and for both CPU and GPU implementations. Usual window sizes of $3\times 3$, $5\times 5$, and $7\times 7$ are shown. Though some specific applications require larger window sizes and dedicated algorithms, such small square window sizes are most widely used in general purpose image processing. GPU runtimes have been obtained with a grid of 64-thread blocks. + +The first observation to make when analysing results of Table \ref{tab:medianHisto1} is that, on CPU, window size has almost no influence on the effective pixel throughput. +Since inner loops that fill the histogram vector contain very few fetching instructions (from 9 to 49, depending on the window size), it is not surprising to note their negligible impact compared to outer loops that fetch image pixels (from 256k to 16M instructions). +One could be tempted to claim that CPU has no chance to win, which is not so obvious as it highly depends on what kind of algorithm is run and, above all, how it is implemented. To illustrate this, we can observe that, despite a maximum effective throughput potential that is almost five times higher, measured GTX280 throughput values sometimes prove slower than CPU values, as shown in Table \ref{tab:medianHisto1}. + +On the GPU's side, we note high dependence on window size due to the redundancy induced by the multiple fetches of each pixel inside each block, becoming higher with the window size. Figure \ref{fig:median_overlap} shows for example that two $5\times 5$ windows, centered on two neighbor pixels share at least 16 pixels. On C2070 card, thanks to a more efficient caching mechanism, this effect is less. On GPUs, dependency on image size is low, and due to slightly more efficient data transfers when copying larger data amounts, pixel throughputs increases with image size. As an example, transferring a 4096$\times$4096 pixel image (32~MBytes) is a bit faster than transferring a 512$\times$512 pixel image (0.5~MBytes) 64 times. +\begin{figure}[h] \centering \includegraphics[width=5cm]{Chapters/chapter3/img/median_overlap.png} \caption{Illustration of window overlapping in 5x5 median filtering} @@ -161,6 +144,8 @@ copy data from GPU global memory to CPU memory\label{algoMedianGeneric:memcpyD2H \end{figure} +\lstinputlisting[label={lst:medianGeneric},caption=generic CUDA kernel achieving median filtering]{Chapters/chapter3/code/medianGeneric.cu} + \begin{table}[h] %\newcolumntype{I}{!{\vrule width 1.5pt}} \newlength\savedwidth @@ -174,7 +159,7 @@ copy data from GPU global memory to CPU memory\label{algoMedianGeneric:memcpyD2H {\tiny \begin{tabular}{|c|l||c|c|c|c|c|c|c|c|c|} \hline -\multicolumn{2}{|l||}{Processor} & \multicolumn{3}{c|}{\textbf{GTX280}} & \multicolumn{3}{c|}{\textbf{C2070}} & \multicolumn{3}{c|}{\textbf{Xeon}} \\ \hline +\multicolumn{2}{|l||}{Processor} & \multicolumn{3}{c|}{\textbf{GTX280}} & \multicolumn{3}{c|}{\textbf{C2070}} & \multicolumn{3}{c|}{\textbf{CPU (Xeon)}} \\ \hline \multicolumn{2}{|l||}{\shortstack{Performances$\rightarrow$\\sizes (pixels)$\downarrow$}} & \shortstack{t\\(ms)}& \shortstack{output\\(MP/s)}& \shortstack{rate\\\% }&\shortstack{t\\(ms)}& \shortstack{output\\(MP/s)}& \shortstack{rate\\\% }&\shortstack{t\\(ms)}& \shortstack{output\\(MP/s)}& \shortstack{rate\\\% } \\ \whline \multirow{3}{*}{\rotatebox{90}{512$^2$}} &3$\times$3&11.50 &22 &2.2 &7.58 &33 &3.4 & 19.25& 14&11\\ &5$\times$5&19.10 &14 &1.3 &8.60 &30 &3.0 &18.49 &14 &11\\ @@ -194,43 +179,53 @@ copy data from GPU global memory to CPU memory\label{algoMedianGeneric:memcpyD2H \label{tab:medianHisto1} \end{table} -\section{NVidia GPU tuning recipes} -When designing GPU code, besides thinking of the actual data computing process, one must choose the memory type into which to store temporary data. Three types of GPU memory are available: +\begin{figure}[t] +\centering + \subfigure[Airplane image, corrupted by salt and pepper noise of density 0.25]{\label{img:sap_example_ref} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25.png}}\qquad + \subfigure[Image denoised by a $3\times 3$ median filter]{\label{img:sap_example_med3} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_med3.png}}\\ + \subfigure[Image denoised by a $5\times 5$ median filter]{\label{img:sap_example_med5} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_med5.png}}\qquad + \subfigure[Image denoised by 2 iterations of a $3\times 3$ median filter]{\label{img:sap_example_med3_it2} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_med3_it2.png}}\\ + \caption{Example of median filtering, applied to salt and pepper noise reduction.} + \label{fig:sap_examples} +\end{figure} + +\section{NVIDIA GPU tuning recipes} +When designing GPU code, besides thinking of the actual data computing process, one must choose the memory type in which to store temporary data. Three types of GPU memory are available: \begin{enumerate} -\item \textbf{Global memory, the most versatile:} \index{memory~hierarchy!global~memory}\\Offers the largest storing space and global scope but is slowest (400-800 clock cycles latency). \textbf{Texture memory} is physically included into it, but allows access through an efficient 2-D caching mechanism. -\item \textbf{Registers, the fastest:} \index{memory~hierarchy!registers}\\Allow access wihtout latency, but only 63 registers are available per thread (thread scope), with a maximum of 32K per Symetric Multiprocessor (SM) \index{register count}. -\item \textbf{Shared memory, a complex compromise:} \index{memory~hierarchy!shared~memory}\\All threads in one block can access 48~KBytes of shared memory, which is faster than global memory (\~20 cycles latency) but slower than registers. -However, bank conflicts can occur if two threads of a warp try to access data stored in one single memory bank. In such cases, the parallel process is re-serialized which may cause significant performance decrease. One easy way to avoid it is to ensure that two consecutive threads in one block always access 32-bit data at two consecutive adresses. +\item \textbf{Global memory, the most versatile:} \index{memory~hierarchy!global~memory}\\Offers the largest storing space and global scope but is the slowest (400 to 800 clock cycles latency). \textbf{Texture memory} is physically included into it, but allows access through an efficient 2D caching mechanism. +\item \textbf{Registers, the fastest:} \index{memory~hierarchy!registers}\\Allow access without latency, but only 63 registers are available per thread (thread scope), with a maximum of 32K per Streaming Multiprocessor (SM). \index{register count} +\item \textbf{Shared memory, a complex compromise:} \index{memory~hierarchy!shared~memory}\\All threads in one block can access $48~KBytes$ of shared memory, which is faster than global memory (20 clock cycles latency) but slower than registers. +However, bank conflicts can occur if two threads of a warp try to access data stored in one single memory bank. In such cases, the parallel process is serialized which may cause significant performance decrease. One easy way to avoid this is to ensure that two consecutive threads in one block always access 32-bit data at two consecutive addresses. \end{enumerate} -\noindent As observed earlier, designing a median filter GPU implementation using only global memory is fairly straightforward, but its performance remains quite low even if it is faster than CPU. -To overcome this, the most frequent choice made in efficient implementations found in literature is to use shared memory. Such option implies prefetching \index{prefetching}data prior to doing the actual computations, a relevant choice, as each pixel of an image belongs to n$\times$n different neighborhoods. Thus, it can be expected that fetching each gray-level value from global memory only once should be more efficient than doing it each time it is required. One of the most efficient implementations using shared memory is presented in \cite{5402362}. In the case of the generic kernel of Listing \ref{lst:medianGeneric}, using shared memory without further optimization would not bring valuable speedup because that would just move redundancy from texture to shared memory fetching and would generate bank conflicts. For information, we wrote such a version of the generic median kernel and our measurements showed a speedup of around 3\% (as an example: 32ms for 5$\times$5 median on a 1024$^2$ pixel image, i.e. 33~Mpixel/s ). +As observed earlier, designing a median filter GPU implementation using only global memory is fairly straightforward, but its performance remains quite low even if it is faster than CPU. +To overcome this, the most frequent choice made in efficient implementations found in literature is to use shared memory. Such option implies prefetching \index{prefetching}data prior to doing the actual computations, a relevant choice, as each pixel of an image belongs to $n^2$ different neighborhoods. Thus, it can be expected that fetching each gray-level value from global memory only once should be more efficient than doing it each time it is required. One of the most efficient implementations using shared memory is presented in \cite{5402362}. In the case of the generic kernel of Listing \ref{lst:medianGeneric}, using shared memory without further optimization would not bring valuable speedup because that would just move redundancy from texture to shared memory fetching and would generate bank conflicts. For information, we wrote such a version of the generic median kernel and our measurements showed a speedup of around 3\% (as an example, $32~ms$ for $5\times 5$ median on a 1024$^2$ pixel image, i.e., $33~MP/s$ ). -As for registers, designing a generic median filter that would only use that type of memory seems difficult, due to the above mentioned 63 register-per-thread limitation \index{register count}. +As for registers, designing a generic median filter that would use only that type of memory seems difficult, due to the above mentioned 63 register-per-thread limitation. \index{register count} Yet, nothing forbids us to design fixed-size filters, each of them specific to one of the most popular window sizes. It might be worth the effort as dramatic increase in performance could be expected. -Another track to follow in order to improve performance of GPU implementations consists in hiding latencies generated by arithmetic instruction calls and memory accesses. Both can be partially hidden by introducing Instruction-Level Parallelism \index{Instruction-Level Parallelism}(ILP) and by increasing the data count output by each thread. Though such techniques may seem to break the NVidia occupancy paradigm, they can lead to dramatically higher data throughput values. +Another track to follow in order to improve performance of GPU implementations consists of hiding latencies generated by arithmetic instruction calls and memory accesses. Both can be partially hidden by introducing Instruction-Level Parallelism \index{Instruction-Level Parallelism}(ILP) and by increasing the data count outputted by each thread. Though such techniques may seem to break the NVIDIA occupancy paradigm, they can lead to dramatically higher data throughput values. The following sections illustrate these ideas and detail the design of the fastest CUDA median filter known to date. -\section{A 3$\times$3 median filter: using registers } +\section{A 3$\times$3 median filter: using registers} Designing a median filter dedicated to the smallest possible square window size is a good challenge to start using registers. -One first issue is that the exclusive use of registers forbids us to implement a naive histogram-based method. In a \textit{8-bit gray level pixel per thread} rule, each histogram requires one 256-element vector to store its values, i.e. four times the maximum register count allowed per thread (63)\index{register count}. Considering that a 3$\times$3 median filter involves only 9 pixel values per thread, it seem obvious they can be sorted within the 63-register limit. +One first issue is that the exclusive use of registers forbids us to implement a naive histogram-based method. In a \textit{8-bit gray-level pixel per thread} rule, each histogram requires one 256-element vector to store its values, i.e., more than four times the maximum register count allowed per thread (63).\index{register count} Considering that a $3\times 3$ median filter involves only 9 pixel values per thread, it seem obvious they can be sorted within the 63-register limit. \subsection{The simplest way} -In the case of a 3$\times$3 median filter, the simplest solution consists in associating one register to each gray-level value, then sorting those 9 values and selecting the fifth one, i.e. the median value. For such a small amount of data to sort, a simple selection method is well indicated. As shown in Listing \ref{lst:kernelMedian3RegTri9} (\texttt{kernelMedian3RegSort9()}), the constraint of only using registers leads to adopt an unusual manner of coding. However, results are persuasive: runtimes are divided by around 120 on GTX280 and 80 on C2070, while only reduced by a 3.5 factor on CPU. -The diagram of Figure \ref{fig:compMedians1} summarizes these first results, obtained with a block size of 128 threads on GTX280 and 256 on C2070. Only C2070 throughputs are shown and compared to CPU results. We included the maximum effective pixel throughput in order to see the improvement potential of the different implementations. We also introduced throughputd achieved by \textit{libJacket}, a commercial implementation, as it was the fastest known implementation of a 3$\times$3 median filter to date, as illustrated in \cite{chen09}. One of the authors of libJacket kindly posted the CUDA code of its 3$\times$3 median filter, that we inserted into our own coding structure. The algorithm itself is quite similar to ours, but running it in our own environement produced higher throughput values than those published in \cite{chen09}, not due to different hardware capabilities between our GTX280 and the GTX260 used in the paper, but to the way we perform memory transfers and to our register-only method of storing temporary data. +In the case of a 3$\times$3 median filter, the simplest solution consists of associating one register to each gray-level value, then sorting those 9 values and selecting the fifth one, i.e., the median value. For such a small amount of data to sort, a simple selection method is well indicated. As shown in Listing \ref{lst:kernelMedian3RegTri9} (\texttt{kernel\_Median3RegSort9()}), the constraint of using only registers forces the adoption of an unusual manner of coding. However, results are persuasive: runtimes are divided by around 120 on GTX280 and 80 on C2070, while only reduced by a 3.5 factor on CPU (CPU median3 bubble sort). +The diagram of Figure \ref{fig:compMedians1} summarizes these first results for C2070, obtained with a block size of 256 threads, and Xeon CPU. We included the maximum effective pixel throughput in order to see the improvement potential of the different implementations. We also introduced throughput achieved by libJacket, a commercial implementation, as it was the fastest known implementation of a $3\times 3$ median filter to date, as illustrated in \cite{chen09}. One of the authors of libJacket kindly posted the CUDA code of its $3\times 3$ median filter, which we inserted into our own coding structure. The algorithm itself is quite similar to ours, but running it in our own environement produced higher throughput values than those published in \cite{chen09}, not due to different hardware capabilities between our GTX280 and the GTX260 those authors used, but due to the way we perform memory transfers and our register-only method of storing temporary data. -\lstinputlisting[label={lst:kernelMedian3RegTri9},caption= 3$\times$3 median filter kernel using one register per neighborhood pixel and bubble sort]{Chapters/chapter3/code/kernMedianRegTri9.cu} +\lstinputlisting[label={lst:kernelMedian3RegTri9},caption= $3\times 3$ median filter kernel using one register per neighborhood pixel and bubble sort]{Chapters/chapter3/code/kernMedianRegTri9.cu} \begin{figure} \centering \includegraphics[width=15cm]{Chapters/chapter3/img/debitPlot1.pdf} - \caption{Comparison of pixel throughputs on GPU C2070 and CPU for generic median, 3$\times$3 median register-only and \textit{libJacket}.} + \caption[Comparison of pixel throughputs for CPU generic median, CPU 3$\times$3 median register-only with bubble sort, GPU generic median, GPU 3$\times$3 median register-only with bubble sort, and GPU libJacket.]{Comparison of pixel throughputs for CPU generic median, CPU 3$\times$3 median register-only with bubble sort, GPU generic median, GPU 3$\times$3 median register-only with bubble sort, and GPU libJacket. The GPU is the C2070 card and the CPU is the Xeon processor. The maximum effective C2070 throughput is also shown.} \label{fig:compMedians1} \end{figure} \subsection{Further optimization} -Running the above register-only 3$\times$3 median filter through the NVidia CUDA profiler teaches us that the memory throughput achieved by the kernel remains quite low. To improve this, two methods can be used: +Running the above register-only 3$\times$3 median filter through the NVIDIA CUDA profiler teaches us that the memory throughput achieved by the kernel remains quite low. To improve this, two methods can be used: \begin{itemize} \item increasing the number of concurrent threads, which can be achieved by reducing the number of registers used by each thread. \item having each thread process more data which can be achieved at thread level by processing and outputting the gray-level value of two pixels or more. @@ -238,57 +233,68 @@ Running the above register-only 3$\times$3 median filter through the NVidia CUDA \subsubsection{Reducing register count \index{register count}} -Our current kernel (\texttt{kernelMedian3RegSort9}) uses one register per gray-level value, which amounts to 9 registers for the entire 3$\times$3 window. -This count can be reduced by use of an iterative sorting process called \textit{forgetful selection}, where both \textit{extrema} are eliminated at each sorting stage, until only 3 elements remain. The question is to find out the minimal register count $k_{n^2}$ that allows the selection of the median amoung $n^2$ values. The answer can be evaluated considering that, when eliminating the maximum and the minimum values, one has to make sure not to eliminate the global median value. Such a situation is illustrated in Figure \ref{fig:forgetful_selection} for a 3$\times$3 median filter. For better comprehension, the 9 elements of the 3$\times$3 pixel window have been represented in a row. -\begin{figure} - \centering - \includegraphics[width=6cm]{Chapters/chapter3/img/forgetful_selection.png} - \caption{Forgetful selection with the minimal element register count. Illustration for 3$\times$3 pixel window represented in a row and supposed sorted.} - \label{fig:forgetful_selection} -\end{figure} -We must remember that, in the fully sorted vector, the median value will have the middle index \textit{i.e.} $\lfloor n^2/2\rfloor$. -Moreover, assuming that both \textit{extrema} are eliminated from the first $k$ elements and that the global median is one of them would mean that: +Our current kernel (\texttt{kernel\_Median3RegSort9}) uses one register per gray-level value, which amounts to 9 registers for the entire 3$\times$3 window. +This count can be reduced by use of an iterative sorting process called \textit{forgetful selection}, where both \textit{extrema} are eliminated at each sorting stage, until only 3 elements remain. The question is to learn the minimal register count $k_{n^2}$ that allows the selection of the median amoung $n^2$ values. The answer can be evaluated considering that, when eliminating the maximum and the minimum values, one has to make sure not to eliminate the global median value. Such a situation is illustrated in Figure \ref{fig:forgetful_selection} for a $3\times 3$ median filter. For better comprehension, the 9 elements of the $3\times 3$ pixel window have been represented in a row. + +We must remember that by definition, in the fully sorted vector, the median value will have the middle index, i.e., $\lfloor n^2/2\rfloor$. +Moreover, assuming that both \textit{extrema} are eliminated from the first $k$ elements and that the global median is one of them would mean that \begin{itemize} \item if the global median was the minimum among the $k$ elements, then at least $k-1$ elements would have a higher index. Considering the above median definition, at least $k-1$ elements should also have a lower index in the entire vector. \item if the global median was the maximum among the $k$ elements, then at least $k-1$ elements would have a lower index. Considering the above median definition, at least $k-1$ elements should also have a higher index in the entire vector. -\end{itemize} + Therefore, the number $k$ of elements that are part of the first selection stage can be defined by the condition $$n^2-k \leq \lfloor \frac{n^2}{2} \rfloor -1$$ -which leads to: +which leads to $$k_{n^2}=\lceil \frac{n^2}{2}\rceil+1 $$ + This rule can be applied to the first eliminating stage and remains true with the next ones as each stage suppresses exactly two values, one above and one below the median value. -In our 3$\times$3 pixel window example, the minimum register count becomes $k_9=\lceil 9/2\rceil+1 = 6$. +In our $3\times 3$ pixel window example, the minimum register count becomes $k_9=\lceil 9/2\rceil+1 = 6$. This iterative process is illustrated in Figure \ref{fig:forgetful3}, where it achieves one entire $3\times 3$ median selection, beginning with $k_9=6$ elements. + +The \textit{forgetful selection} method, used in \cite{mcguire2008median}, does not imply full sorting of values, but only selecting minimum and maximum values, which, at the price of a few iteration steps ($n^2-k$), reduces arithmetic complexity. +Listing \ref{lst:medianForget1pix3} details this process where forgetful selection is achieved by use of simple 2-value swapping function ($s()$, lines 1 to 5) that swaps input values if necessary, so as to achieve the first steps of an incomplete sorting network \cite{Batcher:1968:SNA:1468075.1468121}. Moreover, whenever possible, in order to increase the ILP, \index{Instruction-Level Parallelism} successive calls to $s()$ are done with independant elements as arguments. This is illustrated by the macro definitions of lines 7 to 12 and by Figure \ref{fig:bitonic} which details the first iteration of the $5\times 5$ selection, starting with $k_{25}=14$ elements. +\begin{figure}[b] + \centering + \includegraphics[width=6cm]{Chapters/chapter3/img/forgetful_selection.png} + \caption{Forgetful selection with the minimal element register count. Illustration for $3\times 3$ pixel window represented in a row and supposed sorted.} + \label{fig:forgetful_selection} +\end{figure} \begin{figure} \centering \includegraphics[width=5cm]{Chapters/chapter3/img/forgetful_selectionb.png} - \caption{Determination of the Median value by the forgetful selection process, applied to a $3\times 3$ neighborhood window.} + \caption{Determination of the median value by the \textit{forgetful selection} process, applied to a $3\times 3$ neighborhood window.} \label{fig:forgetful3} \end{figure} - +\end{itemize} -The \textit{forgetful selection} method, used in \cite{mcguire2008median}, does not imply full sorting of values, but only selecting minimum and maximum values, which, at the price of a few iteration steps ($n^2-k$), reduces arithmetic complexity. -Listing \ref{lst:medianForget1pix3} details this process where forgetful selection is achieved by use of simple 2-value swapping function ($s()$, lines 1 to 5) that swaps input values if necessary, so as to achieve the first steps of an incomplete sorting network \cite{Batcher:1968:SNA:1468075.1468121}. Moreover, whenever possible, in order to increase the Instruction-Level Parallelism \index{Instruction-Level Parallelism}, successive calls to $s()$ are done with independant elements as arguments. This is illustrated by the macro definitions of lines 7 to 14 and by Figure \ref{fig:bitonic} which details the first iteration of the $5\times 5$ selection, starting with $k_{25}=14$ elements. +\begin{figure} + \centering + \includegraphics[width=6cm]{Chapters/chapter3/img/fig3.jpg} + \caption[First iteration of the $5\times 5$ selection process, with $k_{25}=14$, which shows how Instruction Level Parallelism is maximized by the use of an incomplete sorting network.]{First iteration of the $5\times 5$ selection process, with $k_{25}=14$, which shows how Instruction Level Parallelism is maximized by the use of an incomplete sorting network. Arrows represent the result of the swapping function, with the lower value at the starting point and the higher value at the end point.} + \label{fig:bitonic} +\end{figure} + +\lstinputlisting[label={lst:medianForget1pix3},caption= 3$\times$3 median filter kernel using the minimum register count of 6 to find the median value by forgetful selection method. The optimal thread block size is 128 on GTX280 and 256 on C2070]{Chapters/chapter3/code/kernMedianForget1pix3.cu} -\lstinputlisting[label={lst:medianForget1pix3},caption= 3$\times$3 median filter kernel using the minimum register count of 6 to find the median value by forgetful selection method. The optimal thread block size is 128 on GTX280 and 256 on C2070. ]{Chapters/chapter3/code/kernMedianForget1pix3.cu} +Our such modified kernel provides significantly improved runtimes: an average speedup of 16\% is obtained, and pixel throughput reaches around $1000~MP/s$ on C2070. -Our such modified kernel provides significantly improved runtimes: a speedup of around 16\% is obtained, and pixel throughput reaches around 1000~MPixel/s on C2070. \subsubsection{More data output per thread} -In the case of a kernel achieving an effective memory throughput value far from the GPU peak value, and if enough threads are run, another technique may help hiding memory latency and thus leverage performance: make sure that each thread generates multiple pixel outputs.\\ -Attentive readers could remark that it would increase the register count per thread, which can be compensated by dividing thread block size accordingly, thus allowing to keep the same register count per block. -Moreover, it is now possible to take advantage of window overlapping, first illustrated In Figure \ref{fig:median_overlap}, and further detailed in Figure \ref{fig:median3_overlap}. As the selection is first processed on the first 6 gray-level values, i.e. exactly the number of pixels that overlap between the neighborhoods of two adjacent center pixels, 6 texture fetches and one \texttt{minmax6} selection per thread can be saved. There again, some speedup can be expected through our modified kernel source code presented in Listing \ref{lst:medianForget2pix3}. One important difference with previous versions lies in the way pixel coordinates are computed from thread indexes. As each thread has to process two pixels, the number of threads in each block is divided by 2, while the grid size remains unchanged. Consequently, in our kernel code, each thread whose block-related coordinates are $(tx, ty)$ will be in charge of processing pixels of block-related coordinates $(2tx, ty)$ and $(2tx+1, ty)$; lines 5 and 6 implement this. +In the case of a kernel achieving an effective memory throughput value far from the GPU peak value, and if enough threads are run, another technique may help with hiding memory latency and thus leverage performance: making sure that each thread generates multiple pixel outputs. + +Attentive readers could remark that it would increase the register count per thread, which can be compensated by dividing thread block size accordingly, thus keeping the same register count per block. +Moreover, it is now possible to take advantage of window overlapping, first illustrated in Figure \ref{fig:median_overlap}, and further detailed in Figure \ref{fig:median3_overlap}. As the selection is first processed on the first 6 gray-level values, i.e., exactly the number of pixels that overlap between the neighborhoods of two adjacent center pixels, 6 texture fetches, and one \texttt{minmax6} selection per thread can be saved. There again, some speedup can be expected through our modified kernel source code presented in Listing \ref{lst:medianForget2pix3}. One important difference from previous versions lies in the way pixel coordinates are computed from thread indexes. As each thread has to process two pixels, the number of threads in each block is divided by 2, while the grid size remains unchanged. Consequently, in our kernel code, each thread whose block-related coordinates are $(tx, ty)$ will be in charge of processing pixels of block-related coordinates $(2tx, ty)$ and $(2tx+1, ty)$; lines 5 and 6 implement this. \begin{figure} \centering \includegraphics[width=4cm]{Chapters/chapter3/img/median3_overlap.png} - \caption{Illustration of how window overlapping is used to combine 2 pixel selections in a 3$\times$3 median kernel.} + \caption{Illustration of how window overlapping is used to combine 2 pixel selections in a $3\times 3$ median kernel.} \label{fig:median3_overlap} \end{figure} -\lstinputlisting[label={lst:medianForget2pix3},caption=3$\times$3 median filter kernel processing 2 output pixel values per thread using combined forgetful selection.]{Chapters/chapter3/code/kernMedian2pix3.cu} +\lstinputlisting[label={lst:medianForget2pix3},caption=$3\times 3$ median filter kernel processing 2 output pixel values per thread using combined forgetful selection]{Chapters/chapter3/code/kernMedian2pix3.cu} -Running this $3\times 3$ kernel saves another 10\% runtime, as shown in Figure \ref{fig:compMedians2} and provides the best peak pixel throughput value known so far on C2070: 1155~Mpixel/s which is 86\% the maximum effective throughput. +Running this $3\times 3$ kernel saves another 10\% runtime, as shown in Figure \ref{fig:compMedians2} and provides the best peak pixel throughput value known so far on the C2070: $1155~MP/s$ which is 86\% of the maximum effective throughput. \begin{figure} \centering @@ -298,11 +304,11 @@ Running this $3\times 3$ kernel saves another 10\% runtime, as shown in Figure \ \end{figure} \section{A 5$\times$5 and more median filter } -Considering the maximum register count allowed per thread (63) and trying to push this technique to its limit potentially allows designing up to 9$\times$9 median filters. Such maximum would actually use $k_{81}=\lceil 81/2\rceil+1 = 42$ registers per thread plus 9, used by the compiler to complete arithmetic operations and 9 more when outputting 2 pixels per thread. This leads to a total register count of 60, which would limit the number of concurrent threads per block. Our measurements show that this technique is still worth using for the 7$\times$7 median. As for larger window sizes, one option could be using shared memory. +Considering the maximum register count allowed per thread (63) and trying to push this technique to its limit potentially allows designing up to 9$\times$9 median filters. Such maximum would actually use $k_{81}=\lceil 81/2\rceil+1 = 42$ registers per thread plus 9, used by the compiler to complete arithmetic operations, and 9 more when outputting 2 pixels per thread. This leads to a total register count of 60, which would limit the number of concurrent threads per block. As for larger window sizes, one option could be using shared memory. The next two sections will first detail the particular case of the 5$\times$5 median through register-only method and eventually a generic kernel for larger window sizes. \subsection{A register-only 5$\times$5 median filter \label{sec:median5}} -The minimum register count required to apply the forgetful selection method to a 5$\times$5 median filter is $k_{25}=\lceil 25/2\rceil+1 = 14$. Moreover, two adjacent overlapping windows share 20 pixels ($n^2-one\_column$) so that, when processing 2 pixels simultaneously, a count of 7 common selection stages can be carried out from the first selection stage with 14 common values to the processing of the last common value. That allows to limit register count to 22 per thread. Figure \ref{fig:median5overlap} describes the distribution of overlapping pixels, implemented in Listing \ref{lst:medianForget2pix5}: common selection stages take place from line 25 to line 37, while the remaining separate selection stages occur between lines 45 and 62 after the separation of line 40. +The minimum register count required to apply the forgetful selection method to a 5$\times$5 median filter is $k_{25}=\lceil 25/2\rceil+1 = 14$. Moreover, two adjacent overlapping windows share 20 pixels ($n^2-one\_column$) so that, when processing 2 pixels simultaneously, a count of 7 common selection stages can be carried out from the first selection stage with 14 common values to the processing of the last common value. This allows limiting register count to 22 per thread. Figure \ref{fig:median5overlap} describes the distribution of overlapping pixels, implemented in Listing \ref{lst:medianForget2pix5}: common selection stages take place from line 25 to line 37, while the remaining separate selection stages occur between lines 45 and 62 after the separation of line 40. \begin{figure} \centering \includegraphics[width=6cm]{Chapters/chapter3/img/median5_overlap4.png} @@ -310,14 +316,7 @@ The minimum register count required to apply the forgetful selection method to a \label{fig:median5overlap} \end{figure} -\begin{figure} - \centering - \includegraphics[width=6cm]{Chapters/chapter3/img/fig3.jpg} - \caption[First iteration of the $5\times 5$ selection process, with $k_{25}=14$, which shows how Instruction Level Parallelism is maximized by the use of an incomplete sorting network.]{First iteration of the $5\times 5$ selection process, with $k_{25}=14$, which shows how Instruction Level Parallelism is maximized by the use of an incomplete sorting network. Arrows represent the result of the swapping function, with the lowest value at the starting point and the highest value at the end point.} - \label{fig:bitonic} -\end{figure} - -\lstinputlisting[label={lst:medianForget2pix5},caption=kernel 5$\times$5 median filter processing 2 output pixel values per thread by a combined forgetfull selection.]{Chapters/chapter3/code/kernMedian2pix5.cu} +\lstinputlisting[label={lst:medianForget2pix5},caption=kernel 5$\times$5 median filter processing 2 output pixel values per thread by a combined forgetfull selection]{Chapters/chapter3/code/kernMedian2pix5.cu} Timing results follow the same variations with image size as in previously presented kernels. That is why Table \ref{tab:median5comp} shows only throughput values obtained for C2070 card and 4096$\times$4096 pixel image. @@ -340,23 +339,23 @@ Timing results follow the same variations with image size as in previously prese \label{tab:median5comp} \end{table} -\subsection{Fast approximated n$\times$n median filter } -Large window median filters are less widespread and used in more specific fields, such as digital microscopy where, for example, background estimation of images is achieved through $64\times 64$ or $128\times 128$ median filters \cite{Wu2010}. In such cases, a possible technique is to split median selection into two separate 1-D stages: one in the vertical direction and the other in the horizontal direction. Image processing specialists may object that this method does not select the actual median value. This is true but, in the case of large window sizes and \textit{real-life} images, the so selected value is statistically near the actual median value and often represents an acceptable approximation. Such a filter is sometimes called \textit{smoother}. +\subsection{Fast approximated $n\times n$ median filter } +Large window median filters are less widespread but are used in more specific fields, such as digital microscopy where, for example, background estimation of images is achieved through $64\times 64$ or $128\times 128$ median filters \cite{Wu2010}. In such cases, a possible technique is to split median selection into two separate 1D stages: one in the vertical direction and the other in the horizontal direction. Image processing specialists may object that this method does not select the actual median value. This is true but, in the case of large window sizes and \textit{real-life} images, the value selected in this manner is statistically near the actual median value and often represents an acceptable approximation. Such a filter is sometimes called a \textit{smoother}. As explained earlier in this section, the use of large window median filters rules out register-only implementation, -which suggests to privilege the use of shared memory. The 1-D operation almost completely avoids bank conflicts in shared memory accesses. -Furthermore, the above-described forgetful selection method cannot be used anymore, as too many registers would be required.\\Instead, the Torben Morgensen sorting algorithm is used, as its required register count is both low and constant, and avoids the use of a local vector, unlike histogram-based methods. +which favors the use of shared memory. The 1D operation almost completely avoids bank conflicts in shared memory accesses. +Furthermore, the above-described forgetful selection method cannot be used anymore, as too many registers would be required. Instead, the Torben Morgensen sorting algorithm is used, as its required register count is both low and constant, and avoids the use of a local vector, unlike histogram-based methods. -Listing \ref{lst:medianSeparable} presents a kernel code that implements the above considerations and achieves a 1-D vertical $n \times 1$ median filter. The shared memory vector is declared as \texttt{extern} (Line 16) as its size is determined at runtime and passed to the kernel call as an argument. Lines 20 to 29 perform data prefetching, including the $2n$-row halo ($n$ at the bottom and $n$ at the top of each block). Then one synchronization barrier is mandatory (line 31) to ensure that all needed data is ready prior to its use by the different threads. -Torben Morgensen sorting takes place between lines 37 and 71 and eventually, the transposed output value is stored in global memory at line 73. Outputting the transposed image in global memory saves time and allows to re-use the same kernel to achieve the second step, e.g 1-D horizontal $n \times 1$ median filtering. The final transpose is done at transfer time, when copying data from GPU to CPU memory, which once more saves time while actually generates the expected image. -It has to be noticed that this smoother, unlike the technique we proposed for fixed-size median filters, can not be considered as a state-of-the-art technique, as for example the one presented in \cite{4287006}. However, it may be considered as a good, easy to use and efficient alternative as confirmed by the results presented in Table \ref{tab:medianSeparable}. Pixel throughput values achieved by our kernel, though not constant with window size, remain very competitive if window size is kept under $120\times 120$ pixels, especially when outputting 2 pixels per thread (in \cite{4287006}, pixel throughput is around 7MP/s). -Figure \ref{fig:sap_examples2} shows an example of a $512\times 512$ pixel image, corrupted by a \textit{salt and pepper} noise and the denoised versions, output respectively by a $3\times 3$, a $5\times 5$ and a $55\times 55 $ separable smoother. +Listing \ref{lst:medianSeparable} presents a kernel code that implements the above considerations and achieves a 1D vertical $n \times 1$ median filter. The shared memory vector is declared as \texttt{extern} (Line 16) as its size is determined at runtime and passed to the kernel call as an argument. Lines 20 to 29 perform data prefetching, including the $2n$-row halo ($n$ at the bottom and $n$ at the top of each block). Then one synchronization barrier is mandatory (line 31) to ensure that all needed data is ready prior to its use by the different threads. +Torben Morgensen sorting takes place between lines 37 and 66 and eventually, the transposed output value is stored in global memory at line 69. Outputting the transposed image in global memory saves time and allows to reuse the same kernel to achieve the second step, e.g 1D horizontal $n \times 1$ median filtering. +It has to be noticed that this smoother, unlike the technique we proposed for fixed-size median filters, cannot be considered as a state-of-the-art technique as, for example, the one presented in \cite{4287006}. However, it may be considered as a good, easy to use and efficient alternative as confirmed by the results presented in Table \ref{tab:medianSeparable}. Pixel throughput values achieved by our kernel, though not constant with window size, remain very competitive if window size is kept under $120\times 120$ pixels, especially when outputting 2 pixels per thread (in \cite{4287006}, pixel throughput is around 7MP/s). +Figure \ref{fig:sap_examples2} shows an example of a $512\times 512$ pixel image, corrupted by a \textit{salt and pepper} noise, and the denoised versions, outputted respectively by a $3\times 3$, a $5\times 5$, and a $55\times 55 $ separable smoother. \begin{figure} \subfigure[Airplane image, corrupted with by salt and pepper noise of density 0.25]{\label{img:sap_example_ref} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25.png}}\qquad \subfigure[Image denoised by a $3\times 3$ separable smoother]{\label{img:sap_example_sep_med3} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_sep_med3.png}}\\ \subfigure[Image denoised by a $5\times 5$ separable smoother]{\label{img:sap_example_sep_med5} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_sep_med5.png}}\qquad \subfigure[Image background estimation by a $55\times 55$ separable smoother]{\label{img:sap_example_sep_med3_it2} \includegraphics[width=5cm]{Chapters/chapter3/img/airplane_sap25_sep_med111.png}}\\ - \caption{Example of separable median filtering (smoother), applied to salt \& pepper noise reduction.} + \caption{Example of separable median filtering (smoother), applied to salt and pepper noise reduction.} \label{fig:sap_examples2} \end{figure} diff --git a/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu b/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu index a34d784..5a04bd2 100755 --- a/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu +++ b/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu @@ -11,8 +11,7 @@ __device__ inline void s(int* a, int* b) #define minmax5(a, b, c, d, e) s(a, b); s(c, d); min3(a, c, e); max3(b, d, e); #define minmax6(a, b, c, d, e, f) s(a,d); s(b, e); s(c, f); min3(a, b, c); max3(d, e, f); -__global__ void kernel_medianForget1pix3( short *output, - int i_dim, int j_dim) +__global__ void kernel_medianForget1pix3( short *output, int i_dim, int j_dim) { int j = __mul24(blockIdx.x,blockDim.x) + threadIdx.x ; int i = __mul24(blockIdx.y,blockDim.y) + threadIdx.y ; diff --git a/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu~ b/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu~ index c842715..a34d784 100755 --- a/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu~ +++ b/BookGPU/Chapters/chapter3/code/kernMedianForget1pix3.cu~ @@ -1,13 +1,7 @@ __device__ inline void s(int* a, int* b) -{ - +{ int tmp ; - if (*a > *b) - { - tmp = *b ; - *b = *a ; - *a = tmp ; - } + if (*a > *b) { tmp = *b; *b = *a; *a = tmp;} } #define min3(a, b, c) s(a, b); s(a, c); @@ -17,52 +11,28 @@ __device__ inline void s(int* a, int* b) #define minmax5(a, b, c, d, e) s(a, b); s(c, d); min3(a, c, e); max3(b, d, e); #define minmax6(a, b, c, d, e, f) s(a,d); s(b, e); s(c, f); min3(a, b, c); max3(d, e, f); -__global__ void kernel_median3( short *output, int i_dim, int j_dim) +__global__ void kernel_medianForget1pix3( short *output, + int i_dim, int j_dim) { - - // coordonnees absolues du point int j = __mul24(blockIdx.x,blockDim.x) + threadIdx.x ; int i = __mul24(blockIdx.y,blockDim.y) + threadIdx.y ; - - /************************************************************************** - * tri(s) - **************************************************************************/ int a0, a1, a2, a3, a4, a5 ; - /******************************************************************************** - * les six premieres valeurs (suffisant pour median 3x3 par forgetfull selection) - ********************************************************************************/ - a0 = tex2D(tex_img_ins, j-1, i-1) ; + a0 = tex2D(tex_img_ins, j-1, i-1) ; // first 6 values a1 = tex2D(tex_img_ins, j, i-1) ; a2 = tex2D(tex_img_ins, j+1, i-1) ; a3 = tex2D(tex_img_ins, j-1, i) ; a4 = tex2D(tex_img_ins, j, i) ; a5 = tex2D(tex_img_ins, j+1, i) ; + minmax6(&a0, &a1, &a2, &a3, &a4, &a5);//min->a0 max->a5 + a5 = tex2D(tex_img_in, j-1, i+1) ; //next value in a5 + minmax5(&a1, &a2, &a3, &a4, &a5) ; //min->a1 max->a5 + a5 = tex2D(tex_img_ins, j, i+1) ; //next value in a5 + minmax4(&a2, &a3, &a4, &a5) ; //min->a1 max->a5 + a5 = tex2D(tex_img_ins, j+1, i+1) ; //next value in a5 + minmax3(&a3, &a4, &a5) ; //min->a1 max->a5 - //min max aux extremites - minmax6(&a0, &a1, &a2, &a3, &a4, &a5) ; - - /******************************************** - * les deux valeurs suivantes aux extremites - ********************************************/ - a5 = tex2D(tex_img_in, j-1, i+1) ; - - minmax5(&a1, &a2, &a3, &a4, &a5) ; - - /******************************************** - * la derniere valeur a la fin - ********************************************/ - - a5 = tex2D(tex_img_ins, j, i+1) ; - - minmax4(&a2, &a3, &a4, &a5) ; - - a5 = tex2D(tex_img_ins, j+1, i+1) ; - minmax3(&a3, &a4, &a5) ; - - - //median au milieu ! - output[ __mul24(i, j_dim) +j ] = a4 ; + output[ __mul24(i, j_dim) +j ] = a4 ; //middle value } diff --git a/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu b/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu index 29922a3..c613706 100755 --- a/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu +++ b/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu @@ -8,9 +8,9 @@ __global__ void kernel_Median3RegSort9( short *output, a0 = tex2D(tex_img_ins, j-1, i-1) ; // fetching values a1 = tex2D(tex_img_ins, j , i-1) ; a2 = tex2D(tex_img_ins, j+1, i-1) ; - a3 = tex2D(tex_img_ins, j-1, i) ; - a4 = tex2D(tex_img_ins, j , i) ; - a5 = tex2D(tex_img_ins, j+1, i) ; + a3 = tex2D(tex_img_ins, j-1, i ) ; + a4 = tex2D(tex_img_ins, j , i ) ; + a5 = tex2D(tex_img_ins, j+1, i ) ; a6 = tex2D(tex_img_ins, j-1, i+1) ; a7 = tex2D(tex_img_ins, j , i+1) ; a8 = tex2D(tex_img_ins, j+1, i+1) ; diff --git a/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu~ b/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu~ index 363b181..29922a3 100755 --- a/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu~ +++ b/BookGPU/Chapters/chapter3/code/kernMedianRegTri9.cu~ @@ -1,4 +1,4 @@ -__global__ void kernel_Median3RegTri9( short *output, +__global__ void kernel_Median3RegSort9( short *output, int i_dim, int j_dim) { int j = __mul24(blockIdx.x,blockDim.x) + threadIdx.x ; diff --git a/BookGPU/Chapters/chapter3/code/medianGeneric.cu b/BookGPU/Chapters/chapter3/code/medianGeneric.cu index bf41842..dff2a92 100755 --- a/BookGPU/Chapters/chapter3/code/medianGeneric.cu +++ b/BookGPU/Chapters/chapter3/code/medianGeneric.cu @@ -18,7 +18,7 @@ __global__ void kernel_medianR( short *output, for(ic=0; ic<256; ic++) { cpt += histogram[ ic ] ; - // selection of 50% percentile + // selection of the median value if ( cpt > ((2*r+1)*(2*r+1))>>1 ) break ; } output[ __mul24(i, j_dim) +j ] = ic ; diff --git a/BookGPU/Chapters/chapter3/code/medianGeneric.cu~ b/BookGPU/Chapters/chapter3/code/medianGeneric.cu~ index 7280904..bf41842 100755 --- a/BookGPU/Chapters/chapter3/code/medianGeneric.cu~ +++ b/BookGPU/Chapters/chapter3/code/medianGeneric.cu~ @@ -1,11 +1,25 @@ -__device__ inline void s(int* a, int* b) -{ +__global__ void kernel_medianR( short *output, + int i_dim, int j_dim, int r) +{ + // absolute coordinates of the center pixel + int j = __mul24(blockIdx.x,blockDim.x) + threadIdx.x ; + int i = __mul24(blockIdx.y,blockDim.y) + threadIdx.y ; - int tmp ; - if (*a > *b) + short cpt, ic, jc ; + short histogram[256] ; // 8 bit image + // zeroing histogram data + for (ic =0; ic<256; ic++) histogram[ ic ]=0 ; + // histogram filling + for(ic=i-r; ic<=i+r; ic++ ) + for(jc=j-r; jc<=j+r; jc++) + histogram[ tex2D(tex_img_ins, jc, ic) ]++ ; + // histogram parsing + cpt = 0 ; + for(ic=0; ic<256; ic++) { - tmp = *b ; - *b = *a ; - *a = tmp ; - } + cpt += histogram[ ic ] ; + // selection of 50% percentile + if ( cpt > ((2*r+1)*(2*r+1))>>1 ) break ; + } + output[ __mul24(i, j_dim) +j ] = ic ; } diff --git a/BookGPU/Chapters/chapter3/img/debitPlot1.pdf b/BookGPU/Chapters/chapter3/img/debitPlot1.pdf index 9cd73d06e4b68ca59437c127ed0598312b22e1ee..a4794f4eeec3b4d02567e2c8898744b3f7b5669e 100644 GIT binary patch delta 8177 zcmZWtRZtv^t}gEGu8S90WO0g9+^sm2B4u%x#ogTsrC4EcDMc13Ufiv?7l*~|{^va1 z`A=SwNxmdsW-@umU|?@x@&yJ62;>vw6A}Q`KZqhiMiQx8E+oyTJ|UGE_HSXKW7~ne zf~gVF+uz|z?C8jZ($+3Fk1Hq3vh*(x?XV_b25fuAQGns=!= zpVGbX!<@U$=)Bet{2uv-rPfcG(68Vxy{Fr7*IV#y;_KTksngHLz0c<459{GGh4=gW zht3elr=29xZd4@cFT4+jz1-4lm@ifq=a@&)f}dqyV2?+jnc8w8<7j-!IUe1(d^boeg-+3SC{-& zZaXUY%A>irvnmSI{*b)}!I#b!7x7>M0$GNvo*-)33KV|CQ>z%VlYF5S)!&%X1sxor z6Gc~I#rXaqV{sG|t2Dgo}# zdfz6{#t=mNi8E-+u~cG;iYM8p-F2w;ag?dcM~7PtRer^tuwG^+Ma4wylj^8R{3-(p zCHXVh^xohyn(`Y~PJh=$bZme9jQ_HaoV?4i)Uos`q9{n%E@@*?;(`FuF|H9`~j(P$;SEp&}V=7s>OjW}t%`+^&L{!;X{;|8obk1$D zd_mlAzv{Vsyy_`%JVzJsM)N0B+2qI}_W%7z>5mU!j9P zyX6AEL@r#f+@X30)%^A7u9zT6qzp=X5l;Q7sk2-rrQZ~mtG99lA5`4bjtgk}GGqUH zo4iE5oI)k+%O=JM_DJ>;gn)VX!bPN@Ok6UXvSe= zrq+;-<}j6csrh#Nyof@T&fOHCJ*HmS(Wb>nAgXGz`8j<^=&T`pJb@5{v0RECvI0jV zcB!%azE>LgUbvSy)2=Lb`>Au5w`rDlYM&yL?;l2#W^=swS(IfEu4~n3C?#sH(WoGH zNogdziiCBUyKxL`Lb%30iopu7k)e40o{0in^CfzKk94g>BJR!ikcs7V6!9+ed!Ihk zQ(AB5APaUq?(zm9^Q71OZe!r%^-v`j`z2&gRN_VWIRvf8duDs0{fsW+j4EzyS#nSQ zCqp8W^s?|Nj&nIAb}BOKcXr-Sd<7u4WScRYO^N{7quTWMR8+hgw;%iQ+hPE=h_HY} zm?M~2TN#7fKd0fFT&b=HF(|zx{osq5k(TNL1L#ygy()bav9{t^EB1tl8te;Ie!mk7 zZv58KEHZr0u~Nn6-8*-hAQNShByv}*B^*R~m>)R6YU&I5)z6YF+2H$y zWcM?eDJ*pIcBz2aj>foB!x=vybp97t}fgWpLgo& znE*V-wC)$#YF0&nyBr#b)Z=kI)BO~HNKqYRGd5{w-vq)+b1hBh+=NiS;y-Mf?4Gf| zumFeGwOZN{Bmlzk^zSDh$~6u3iF}HDoNf}fnkyjA#Okmw^c(RSp0-Ba6m%mU$-y{< zcP48;Q{zbCKQ(s>x^##O*rx{7vw338wI`l&9G(|F0HihPfF+hPe8fKug>65%BDY|A zrqdJ=W^DbIhxYR9N2^mo-EW}VDqgO#BGd2VRVMa{vwJV8s;r0a>$(F_(O~v$QEI)} zVV02AhpN=)2r3-Wh=7!|PbiJ1PkCK2@x==S%8y zhw(p=2Z5{k4fT{HbkY8eaReT|!?fNgREVrUXDmUH4)$p}88@^k^P%omdLm2DfM5xY ze}My9;HQr$`R4ZE8{mEeRgGvO@MN<;woq8%!u-*0-#sI&TqeCEE)WX<2K$XzuId)j zgh)D#uUP8%gABf{RJu`v&NTj*5G}l0`8!t$3*}DH@b^qJB``QsUYq?STk}C)53-ru z!nd#;80o&8;ed$NDXFI?={l`nytgs!HNFDX^)C^U(K;x3#Y%Tb|841h>>YWhS2>LnUGoC%IPKgWLC4jUhvhi!6&jD!=oPrz0L8_UkosG7(Dr7(BVI$Yy$)XzrE=%*3@?@LF6P zPtoMV<=J)-sfrt*w(wCf45~2ZMdgYN(%ReH%4=|V)k&_-{NVj&P14O7Zb0z6dp{`2 zi+MG{an|xu?rPWs@7a->BI*LM+J0=8*DStxLU0dHzMs)g z>-UmSV=WN)Vw+#0#r*x2=j%Ho<#V)+z?Hz;0{_#%Ga}1yO$>Pk6B-dVdD%*p?EdPD^ z#MPe~7^cc*Rk%9l@ptInxgvgG&lXypL+6AQU$wfpBUPz8H_x^ki|JRma&`$hLNS-m z7(%5ip=~LaHDXGO4Yw^?3jbnD^h{1^n1I>Z5E(>GL+i)m4Ij<%h6LS=<}^w{ZbvEB zY5^pouo-^7L$8z)WJ%^jHw|^4d_U8OaBrNb^-jO*lP8t?3G+az?Uq_A4u5eW&u-i1 zWn9(%#7`iii{ba20W7TB7X{%GRA6N~Bq638M+zWTf@q&l?1UC3;y<;@G{t`YAg&%-y|_e4#Qg*A&8yXVH~7f3N(4 z$$|C=2coCS;2j(-TofCe4_?u=r$VA{S%L(+;L0z&FN8iGr#Joq2^$o%;ZO3k>{zJn zM(2lU)HV-xgS=QUO<%G*ZuIfinp3&0#=>WX{$V8_x9Q#KpRl!!o2QPEQf+$y@a)+P$>|V$pMN_siZV#eeUSlLzx!=a;J-Hnh483-fowJNn8Vssj+PO_ zJ8?cA%PMvE&-QQX1}m@wPgr*)O)xD8^$H~eA0{n7w6DP2cHlStVIc%rI<;ipdLZ%- z%hcQpF{Py;4Aa3!&9GIKDD@yK--rE2#?U9d8`q_5 zV|>j$3&hy?nAp_^`rCYi8~vqd%(mX{FW=c=o`Fxv_!6JMC&@;+j8QRRVU}ZauCcEk7Xs}GJ#+pB-lQP34Ikz9C7LZ5Zc=2Cnsge@ zt)oTuJcKPKJG>*$!TT9X-|Xb{r66P`Ev@>k_F;?ih{N1lr`|zSRELsM#*VlVWx>f! zDC@N`q*__8ZG}O-Kuq( zSb4ffLpE`7D_~07OJ}KU>+ZYmcgRNql-2Wx5KQDxU9>To=qf1e&vcT>Bb8%&7WA}Y z-W;?vR8HVuZ-&Z@2|n0r^~knRFrLP z*nY4gD6}Z#=49itW&*HtmG1+~2hu~eF*{2{2S^qQI5IH+PH%tQf zxa*KGC+g?Hyr^j{{_`AJI(@4Xn1UV`KIaDOA#!qH?5vqYH2# zi|i5^sJk#rlOODdSt*A#g{>VmwP;6vi3sv1dB?_%2QcpL1U|@e&{p7$FxHaJC6k^q zs`ShZl7J_*pk^h;cxE6P8=s~aq0h$RFRRz&`l-o{TUs%%zuPHwugAUjE3=!u5ZTC@ z)}`GAmI0q@p~unvPy4#RSsF){L?neLeN2q8wCI~Wqu7Uwz z#id@UYUFdL2EhwqH>Kito*Ez6ShZWLj8>B2&W0N>IDL|>2CAz3CctBMMVGl^rqU7M zSK2Fxm7&shRLuB<5Q>k^z*rj#>9cYbdEFD)DyvjL5M}6!?s|i}e5TcY3tz7_yJ|=Z zmoby708zri1`~HfdxBd^=Vk=YBktw7YQf+eT-q-ONBor^jjLNLN~`CsiZpg~l2x|1 z$HrV5>^n8zrUaK8kReG&>F5}+rqJEs*NyCC0V=9Yyoh#)J= zepdfTi7fw(gDXW%?Sdo|B*S2&gnnUeiRNYV5WeG)rV4FbdU#;fFDq+ngFmEdyZT1_ z+|kQ1M(PNp0qzF&U=2l!B4Cf>m0I$sVB?@7QF-CfQ6ukf%rmr8Q7~4X9k}!o%=@fP zuYu3%meg|F+SYmJ?8Q%g(ScolQ0xC=^G#zrSgo;LYG159Ine`a2goy9rNjPC85!1m2o3PVp^@cGXSI;4&n0 z);A1H?_6M4Q)eGQ{!aguyy!b4Q$Q?GZJy`*low?MJsT`UmU{~Eo7J)wd*GG=|KQDy?ruRYPE&7K!Q?)5;cYM7 zF4H&ni$&)Asb+AYl#2tn=TN`lcC*z4e5h$&tDfbJf`;nvV-=I=(Q5lFl&8*G(Y<&E z*t=4B4WcpE|K}vd#o<+yWGFEGi7F=@+_!z|oF|3+vB}9-EgX6!G*A){6vW&u%E?)i z469dPnf~jsREUY%8t{m{^Fa_8X3k7*8qJest1Jq`tZ|FqGjh4&%yRv3^yg35heF?& z@ybP`_3~nOeh;8!71Qdeh32^o%hlRp7}_eW-bwX3uP@vnSyHMpIk`=JVykLI{x7q~ zO#lI;VV~87XJNf!kk;otLcDkc2;I)j>*8gz!j59^y)jTAWl!+1_G74BE8 zWvViA=OfT2pWk`Em6TL%mC;Zf=w_7={U_ivC+2laX~f! zL600Hn3O2LT|VBw74mh-#!GgQkSP1J%uT zJsEmV*xjVJxbFr0siW7ZINVVNvfd~vVPsyeoe5E4g;tg&m6w(>J73HvbxKH0gtbEu zdWi6oru|LYo;mZ;UO5q*g+wr8iu=yGB!wcqRg|HX9&JJ*1lR$I5S3R&n;Cm3RCxrY z&W}`GgGV=vp{{NZSJ)ra6j(0sDEYH?`eYZNvuif$i)Geh{nL00$i$YGtFuhv$Q04EGOz7DiiU6*9ZLdRbwaRxi#*5yr#XS z<+hW|vd9E-L?iEe53BhVAj5_q8=XgX@OeUNpfH?jXKjVJvDXX?aVL3FU#5!1VH)4w z%^)LPIq^h2+n80=Xc=ZpGegq9zNVAR7XcFT9zT4WwJtX}^oA;!&3({C?v0T1I5LD8 z7gu|WATc$rz>93_XDie1<$H=<7=SrpJ%;%Ta+uyQ!1sXMqyp%1Mn_mhU|*`t;UyQ3 zgvj(NlJkJVz0C;Z+yySubw>H3{Td$dTaKPZ+;ql?&$$mmJUef63=r~%a z^>%Nssp+10sKp#hS+#YYF^bqaHDNVvf#AuGUXSL|4T2s?~(G&en+=1TGdHIy#p?Tc3GaFM4~I zS2`GeR!sAf$2Ly%?dnO$Bl=amiKke&NKUM8o&QK3U3u~-famh6NX=*RYLaaK6&uDa z9Ay^KEC#9D^DV$JWhszu3;;}r^@{~aPG1#TdYlDIXiwrqBTeKVP>V~+(QTjvP`-xm zN9_x)Ib#4WxGqdP6Cl~IA481Jqcz&&#Bi8>bJg~J5tIdr8A{G zSwUS@q5X(kEpNp4lJAEU6CQ6L6y;^qQN`uIYf8MPAAFlOofg46Eh-I0|{NcU_k zwYt!8GAV>xk@aHBgj<`GxVKFSBu0mKl}t1DZ1|Xn(63aAuDKe;-ddB#xB&6=z81Ox z5xk)bB01&)iov?ST7-=ZXL)4su-Zjhk?k$f^ts=rjvzA~$f|QIs&C?n7>y1|rYlg{ zQ9(XxBKB)i@8ZXZYKnDGEK6S&;VbvV6URqNtIMn-kH*k*DmAIz>hKmstfRv}hf*Vm zAi3efwa&c}s)5fUcYrDMVxAUf&+ME}Xw@gdZ(tgUIr86-CNV=kMg+zwVp$(6-70$J zqEz!Gr}D=AD5rsY|2lgrtan7-s||B{-wlbdnV)Vh9?NM%R(~i z`QnzzQKz`#zvl~tl>XV8(WhY8~)t)GG0(S%zYBve`Q2_Bf~Y#LKf`!J6bhOB$viXYj2fq8izf z9Q78)-aTh$TL1wV?u`CHtT~3Ha0oMnqjmflA9#Gv4BSx9F&dbBB{4Sob0t!Zo7RXM zY1-uJtm>0d=8lU79}}F~i>qgJrFL%AZpGqTO8A@+YJ#x!9O(>|?YxZ$cf-wows_Ih z*KXV8vJ=L~gC*C2Hs*b%e#4I6{V|DFmR>zK$SsM9(zssSHaDI4m;ATqz_9}r_W=91Tl1uiu`;X_UUiOc{zhh_A#W9wPkohZhxy_;b?N7=bM5im z(ChEJYiySawi|BE0+x~xN3IZiTXIH6c#qd6vO-yJD+5ph_*Es;c`r({NgbV0ZRN5> ziLL(Xd*K~PdA@MDJ#pz)$v`}l_+Om5eJ#R1#ram%ZK+2XuR}GeyoJpDti{rz``v96 z+gH^eWGXy32yg+zF(!S=sYEfn8Nam&-1td~fHvIfDOk|Fia#tOsp`9no4oSN)h92S zz%2C?G?^lDSfJ~Ui@Bqa&qQ;*W6j%cDG54#Os|)p|6~2FF%w%kt&JhHr$0mz#P=C5+ zo(HAQie~(daKo6)8Vda_$1xz9hgGe`?zhf3VOZUIg2O?H*kUOyl>Yn2#|l-(Wo58! z1(!&(bm^WYB1Nf8>lg$ZKI#8!^jgz_KOGrwJ4P2*JhqJAhP+#8=ZF2L?%&NOeqlMV z0y8ycc3{5Q`r_ym>c?IR%q@$I^!LB*uo^Z6j_cMhtni5{T-^9&&c3Ju-BXKnKl2lZ z6^wDkv8+DQ9~Z2Rk_vQdqGsAm=LsnD;wA%nZisVMRHZpn;@lxRV@7UF1xjU&hY5E= ztt1-Z+cu<{$j_}lY>L`=+Br@NbU6v-An9Qa`AGeqa+BQCvSwBbE}Ai?DTMMCwuaOz zY}@c{`>*6!Vq`{?BOV-?s3yh~O+VODMO&qlCPlw-A%4I(56GY$*1`_4*mj{D{kHw4 z_l+1f@#e3bH`z1t!Ol8Gs`I}$Wt`oj0-9hH9GOFV-?6JfM6sGjMWe=%H8?yU*nJSRuT5lTz+X7wwKAB{z?Xn`Ti$YScG5rUpPKqKH$H3@bU5k p|65P^|B>Sp_-C?zCkuf1c>l-84-!uEkyO9{3S$BQ@)`=5{|8jV%Ci6f delta 8175 zcmZW}Wl)@fvTO+M?(P~`+#$HTLvVsS1cwiou;}70fgr(y2ZFnV5L^~m+}-7#dw;z; zZ+=a6b#?dD)J%WyaB%VkDi4nUw;(qUKYzoc$a`SPm7@J3xVxl~7&N)1MuTGE-vxJx z(~}%3hTxC#OSnFn$m5pwcVWlk@d2(K6R&t`v!OYg?gh)dsm;?1_34|y%T?yV%kUGR zVSc?g{FKkX@#8sX|E@Dw*4_W{^5>IC@LKSC@DOmYw~!C+db?+id=+g!NV>oKe!vCD zZ39VSACYA09Xw~$H98TxLH8_0tr%Caj2tqr%}-apv(w)N4rR}koAVDpDKp7bSbCzK z8!|4%=H1&zu&&2|bLYO^YqOn_db*d(i-~P{ac^|p#3nU|HY~}1Vji-hkfj2Eymlsg z((CceLf?wNNXt)!%iu+xrkmj6=N2)*QkEW9p z&#e}B%*FUnE*q`qQL7InsPfaI3)G2gXHBux%d2J-jAAoOSL|kj7{)2v3?6)wur*<% ztx$SpSp=Z-_@?#Sx>%nR>+R02IK8vHBkXc6 zw9-wqV;u7LDf^4P#TKzTMe6$fObdqv+b)`}1NOKZAuQRfx02M5BhZpmY%$EJOT^65 zm|6NWJS+lD;(QnFYPT_Q<8v@+T_Ar*1}+jVLvOObSE9Lng-p6>|qt>Js z?{`>Q40mjPqISWa1v7BJF@`alwS>#EQw;rcA+(e7B+j<3kY%~I`;CDW+wd;+lHy4I zyx_~ye^#dC-$V3)b-G~?b-lXxC-({)_dn-~v1)ckq<^_8hMPaqVg=lIqNdXE;AK?- z!}fK77pZgCT1)B4u4pCK=!ml!Fk#F?*8-?`0W`BqTFyOw9RrY={R80yV(J8l!(b)R zw1X)|6Z{z8%=**JrehEC^sSC~6P=cYz#aVWwjB@(`BFD`SL56%WH!}Sn{YOS&Xsci z_Fg@u*C{w}oLb(!BJ=fp?L}mJ&7peb4*O|y34_x!s((9gcmyl{8}3hGn?5;@giR?s7^kRKj4qiWvt_~*nD!3Hjz6W@m2d@khX7mX^fi*hLBdgWk ziRzag{Vr{*HVNALV8uhjbCml=Glcs`C~Kaz&Q-ud&PK^dbi8P&iqxwJDIE*bv27Z6 zJ^Cs1M+Uds9wD+!KcXNH%Xvbh1Z(7H`z{7NQ*x&|lxjP5HM0HV+tqlk;sK6m&EtW; z>DgABvvvT7=f=fOK#*`-GN-qfr!Ia6T)7@7Fzcmtx@Fk(gk3;ZWKmD7coOf|ehxKR@-p z)`X?9FB~r-mo+7DP9C+pPTu{yVfPZw*Bx?1 z1P&sS0@mw_85WG`G<$3MiPkNy%Dvl-mLQ{**r3wtjQU6x{kQGm7&PvXMTb@9*Kt-qPr;CUAfDxVmL%Wpl8zH18Y3Y z=f|VE7B~c>vGbv&=}{7LRh0g1OI%j(%mwC7Q@TGcPHa3nYIJ6Ga-(v{Gg)Vx_iVIS zoh-Pz`#Za@INaU99~&`JX5^9c|iQdz4XI z+T^v`v>Kzb>FTvhPO4c~S^hxPdn@Fvbzz5xqZXrltl~0CXlB2@i`LugYGvE~^vp)1G>5g=2Mlc)!>A2~opO<;gl_3x^?=yBu*Sg782*dvLu!3z2HiwR46KXpKro5G}rAU}OOj6c)C?20Yd&pTRi zK4s!qFOYTAn?^NUf%g0S-gL1L4() z;q$yjx>l+VdV+3jQJrVv^94^ox``C7t%qqh9)3hH&2Gj!M}BJ4ynL=S8O0of6AX=p z86ZP}5+ zpsX8P;no+WGWp%qX&-}TO7oB6LLKRUMm*&ec%c84AT#)+oA7qOiz@FtrEt03ceJz7h$rncUB}**--ljI@l|K>O@3;Ale{u(8 z1}>cz8Ul;E?Xzck6LV2mn?0>PW;KTtNSwVQlWFW)LSE3x;dzDlA>25Clw7 z;0=D`ed;?@92%+j)Cef5A5;%r2dJ?r^5AP_O2AoR|UuYu6t=Q5IV8%n23nAp$@3Uq#U z!_l6SE)+$gWF%ZB`6-F%qT~D_@UYB{6-)X_&t9@nF)CaE@YrXJ)D5xMs6*7KDYgBH za562OtAw;*INP>{dg4Z>8vw6W^7)yRL0<9NbOttn_R952m?I@v+^VapgNMrqlt86Q zM4MuT!I4RT9~49;y)To)*1;RyQQ>lZhaqi{@h-nY@mgdF6X&ZY0_|ZVLU%F&ZA@QL zeGhqY-ptCMKzzA@sa(l$%o(g7PalI&N8wsmV7Ed9@=>y5lA`35+cWXd*(}u$AM{Po zDIKWEO}pBqBunQ1=~ky#c{WZ1`M&!B7u6N-mp(?U!hF1|stG+S2k08I8fLASk{ZGm zDzvMrM`8Qd$z7`{O?J?SoAxHV>6gd+COf&`?CcBVdH*^5)_BXYjeZd4-F4cq!=KE| zIMBHiVs2IE+rM&P57K94EE)U0#VjwMfO)@F+73n=429?-SwQQfsoSF^)1L;KS7k~B z&&S($xc0C%e^K!KXAnNYFPvn72*Mw+2EN@)2nVQ_EL7P zD}T8)$!<@^l>JjY(_%idR;RbW%zS9=qpJ&oyq!Qm$oig}OIH9QfSH*-=lCz@aA#?$ zTLMzqUE8&`v;T{aTb=G4L;5EQon~Be?*|K>HjFAU4lz^5rpI6}ui4h`mGQ6bQ9Y6U zjGebbN9IqY^|Eb{u55Z3rZYfVFyCN<-dxu-7cy2m`t&3 z-5oExDGD*0BlpfE3h}0!?XU)|%vp=%F9!Ts#w(PZ3!^(by_Q3f;g+@)fP{7I)*C|2hd{hb%`b}_I@-S!d@4oX+;+BA)@@SPuXaUC0SlR4)*CB)HX4=4eeXq4@JfQEs3lE@>}GM zNE6^oTp}5Cu4zV%^!&Nn?gC^HrMMW-PR~=+_j!oDQxq&$sni(?Y=-5Xcfhq>UE{od zwgDYAdYo@&9!hF1PER8jy}ge94FqQ!sa7An?}0UAK;$lqRDel4-*?!LjnyHqM0K=eS%#)3lT+BUTO z2oOhY7IYA>o9)Ri)u->Sb0$0=QcBGi_dMs%Fcj#CC2%nkz&VrPkRss0;`V$oD+TSJ z1JEpzKg&;)^`{;jQMugt*!OB0b$5$=IXn3O58;T6POk~!j!l-CuZPGs=O{7 z-$qx61M_(|(mWOAd~9mUBL-Ch>onK3d;QO!H5Wb-@Y)(CCc;XX=HoVXw0X&mBmJ1VARoQ#kIR+q@FJ;_Rd1RYPQb<_;3)ot-Jx z4$ECNmFbU&VZLkc^u`b%MSdjS#d0DwHO<%7)73VvZZ;lHNC#T|U-`n+Wd;9VP<--R&6$d4~&pHs_{r%ozsdytJrJ0|Rc-EQe@xYzq zh};g>*bZTk^IsIJSxuZ=YU-eM*{#Z^Ct`}*L$=uZM$i29&8)wq7##r#<&jAsYuKOj z;(k;-8Fz!9%`DZY3B{{MheXGV;YeY2sDMfcg9>Yp0}{_i>0vF*${alBC9g2;2>w!Q zYzpXaK9I8`pTK?Ba8lu`uF$sR9pHY76}bPWz9G=^^_*P?za$_x_%!|so$L!_aOXIO zg3MWrwhoR9)Unx{Zk=Rn5N=&MNz_*Fs`h+ljK;owm^p`rc>5%w@(>^DL}B~ebKuCu zL5EGRDqw&Yd2p0QTc#9L=c(|1pWe)E0R%QPFwwEq6#aCS+`cU;A)tz_4Wt>qr}8&q zgN!O4nCw-Wt-T1>1g?;cPE zIe4J5R~sAuk{K?4d{S#h%b)uDZ`o{iRn>KS);)uX*~ECmcD7qrPajFKjw=C?Lfyqw zE_+Ma!K2}4YzEE%^M5|+3xLFPMF&V+O1W}(#711+RWbsOmqv>^ezXR_wdXF?mhCfa z!Oji?DKpU9dG++@*t4~Dp&t%JVzMII*R6FFIrMkY@}})+es9n8)cEAjM&s}%D3{++ z9Cj5&SLoyWWl29HN3v?Qp7#Q5$kjFQSz^z`E z5ue}dP6bZg+1P}111tUe-r#Ms3X zi2hO6UFs1=kLfw%vN22tH@3^XORDy_sSQ;Al*;ZfqY;vW4ya5Im&_*bIju^(EgnR@ zsJG_SRT4EW?L@o;2Lw+Ml29BHj*eY}$NA4%m#!ZhJ;5(#j@+%!XKtI-Ib^MY4hOUe zzxr&#a~y3QJT0froSX*LCTC|WA??tOOCFam&C0>NUI7Gcv{=J#;Dc7^bT zdbH>pRz3Scz$$93Ha_uAF>~FV*&`N#)p-Wczm4 zB!W2#3exO$oS|x>I0mzsNfbk#QKPG~qJq5J{Mv%mPJASS&0q~#tMAha*4A+GWy-|_ zZ@uool}*Dp7QEM~Ad88eNMl741)h<;&BT{bSNWTuUBS~G>jhji7U+D-=XH82zpm5iS-J%P-Gt15D5tSQEPY($0Ohp3+hjqIE_c%+}9aUpn+T1@1Vla-QFvKv3^r4J) zcNtK~!2^_FF0eq1gR{6R`QXArW1$@m+lET*L!yGYTT`C}-p&&mq=rpb2~ zhr{gSBPZ7|M!yda8XA*R^Q755i`MSq4+^=tc{$5uIx=<&8>55%9Jng+-v(2iJmnaH z$dc)bni_pQy{g0JFHB9d!Z*kN(&Xt^I1Ls&_Z}tpjXsv{S#1{Nb$%C$P&oV**cXup}N0CB&>n4|sTrK1b_pit?wSeGyD8bXf@#^X^e&+73?3h=|{=F=I5Ytd; ziWl}^2|jF+2>f9ZhCj0?Q#TAF8HUvX0B`r#3&&5fk;)!O95PwYyPbE^o#bRxzak4K zYesGO$(ky?eveo3%q1Zv{zyn{Zqe1>qU?BZROjDwUpTP&JXW>ErB_jP^wYGUy+dXl^Vpu0H> zF*5t3%WI!IA5jYNF7d8{+Kl1ChY9+7+f%&t5k0f}V=s;OM+-&k*dGz9gy%)k58tPM zeG7KFZNsFV<+|j$y_qB7KbhZD$af7ACSK}w&U%FPeRQj7Xqgnbt{6{0OK-FJ%(!4v zRu&dFt5CbX{Ehl)X7pch2LjPL08ixDONYytN;a7mJH~wZT!)K&vwrMI_srIrll5TN zJY(VT(-4fQW~*WyQJmpA_2P62c)q>No3x>^yORg<oTo#z4|XOUo97_cJ7xvRM4HJT}0I!Zfw{ zvXAFOp|O6YX+i&ZQqnDO-N&U0@$C3w!*KZn>I?ry$j2Eg_VVsXMwcn7x;(>aZ%CRZYsQ)1h*A2)2^;y z_>#E9l$rMShrx!Pf$b4R-&V$$9@5rNx83VuudW)oO@M`kg*)&r<&C+|#H;;rZvbaWd3LM9JxkJ_)-}gZBj}LA#hBVpc(P* zrQl9Yk3=xi{=+3F!zeGsDNXp7REm=`Sw(i?8#cNpYt;uO)J8CbHS)m9UcCQA-3Ei+ zQi`b9^IAo!yr?@!E%_i^*y>wKkV!Hl;*0im{Wpc=_+%`fjh(Ic?XqHDC2+R2x6__w zlRxJj%di4J6I(RN2DJzVHHo+@@W1qMafm8P5XdTJr9{r)jG*r4h6`KTAjXY+D~!6p z2#P7TgWm>?I3za}B}M&ynn7DAjB-Ot@O*3x)Q@TN_xZC7hmjoIxXOWa5}}X7F@9zu zltT?u2#{!;6|+wWPYX2~D8TvyMTEu!L$z92zmb3z#!%vD6BS$LB0ITc`o2{R<~?rw zXZF>cq`d@O_nMw(5<$GpM>^{91(D-yX=V!s1o6nbUoR=9@uR1tQxURvOxNFM*z5vR zS9r&35>FbKu}BuAtTwsE4^aEaiI3yG7Gu*r>=o|(GA2Il%x_<;L+zqkY%SMC6mdy5 zyC#9NY}R{(&M=S5rK`3o;bfjHWLUSMufWnCrX}oZQ?6E+oJn zEREqwbQF>pi@gf+c}<*Wqy^)8Sd#%^r~LMH?pnQ`PC66-Ifb2=4Cy{2(Zycx*D+1h zyItWC_i8^3U<^i09OrTRjln|QkJvZ->N8-b5#A&)W|@TMCEzp7bXNVmii~*7>N?aV z;EeJ*g2GJ0c>i`9ATfsb{!Ga=a$<9MYxP%`@rS&YFH_{GhWVR|u^##^o?W!AYVxsi z>#rQX>L}zKi>l7cZ1qVKi5~Ne2w)Doi?18ZTZ7NXzfL?XDKDgme5MM|#lAjywJ!j6 z9<<>j>p?{9;M*=c0qRUvb#vv|%$D%QSr%opSjS3^7iP1;zj)(I6Ll!RH#N@c+3l+e3?nGJiw@S za3wdI)RGe$vHe&2($1sCnxu+!&@RBMFVQ(H6m;ZHy|}ToO~wABEw^~y=L$b*YFDMk ztqe9}m~n7izd~vb%2pnd=|$j8$21|eWuvl!kP1vVGxR&>j1C#vzKzNAboPSFQ;kA| z26%j&VkEOh%2Ox0EkMfimui2*CXAtN_=M)r_Zq=CE=(|*?xSZ&gFlrRY9b- zjm|7XM{#vE%!~X2*_gJlBCZ0s^b4Cb@dpB%Zk`lqFS}mzIXUV2#eAXKc>d zF+aB}!#IxFkSWdB1UiBj!BfnK9#Wr?o|cY-&QnZqTuW&Edtn)3`KB?c3Ep?3ni`j(0 zkd-EawAc_$8vNb#oMV$G9b6uoDUevBmSL$;1Hmn!@8hi}Mc!t&VHo#>Lm-dQwjjEI z$ACWpY4*fhymwbek%d}C9DwyUqMSVi?_;|h1jwdsmiT6Jv7(onEduyueyj(EWQ1zq z88WO|FC7OYO}4bRJ79XjHOp_Iwlo#LA;0pW`9YTG$l>|8d7JL&DB<1G2^ujFNRY3|j|m`xpCC8ie+%;Q3h_X^CFD_gdC(Xc*0Ez`~Gz7wP){{ zW4_Fq^_z+HY4eG_Lf~d&W94M!X5p@W=7R)Qtn`Mjd^)xTzCJdUKBF3T-!JtTwV_(Au;lB!%Sp-k{fh9$tMT&z$?OUm_ea+G z@&y_<95)o-8~fD;x2|}Xz?u)QcV-8%5Q)&N()-(8j*XqrYf{dKJkMM3`y1EWtD7kB zPL5LNz{K+D@o1Fn?=DQ6=9F;>v{N8X5z4#E;|kjBMa*~&dU1lvnrN`fwY;!i28&3h z6C*1Y32{j}d!iPNGc>F;n-@Ii7#@8z49<3jBjV85e%e6>Xe3A~)e>*}=H1>YjW?l& z>v`w=p;tHQqeR!!?}R|`D$@2B`NvlvBs`o4k&X?k!yivJ%_MVKtK-6A55p{G8V=;& zg#WGc<;!XyYe&#u8^M4W2X;6>H3sMNjA)Zybd~NP(b4T28XUP9PAiiVtKUF|)EE~_ zA4gnESHb=TzluTBKt@AX9sakD6yBy#gFMzo;%>v$vF?pIFmI@kCZE(+~>Tyu9p8XVRBTy;t8#?Yliw>K+M4WJJ`ON zz_9UGLz@;Rd+_2v6L4hz!i_{5y&e&tP)**$A)wt48oh1`en`i-ZJq2E#8Z{ETKh{; zC0BW{X?I+`Evf^bQVRTsiP2X1s@(cHUiV8|LhGS@`vGjo(}3s)o&`MG4(q^ZG+$~g z3OL_t12Me>J*z2}z#jf_YWJEKQWo2*nfH!n_N5`{ToadF%1Fw*Z7dUihtPw28;Imy zag>NAM7d$Fja@N&CdeJs$+H!RGH=n{yn#arYkKJ(I8Eq#fM1}ov-9^%Tv_z(X|LiD zHilsZcyXPch|Xf7`_E~EtQ4}XtAEe^C_NDtk1F5(ru;Nf0~bglKeWOEIhUca_pe#G zUeKw0^I;}?u&EO>BL1tkdro*r&6mPD#Qy%H`NTGos;e)({3}>pq6Wv zuE3du^4q~5AaQ7<=d=|QpQ|6{pj8xSBXKB83(DE995YJIfm!T9qo13q=3y@>bYHE7 zCix$!*Q^=bi&|sA=ej6GZPlcIkC&y~H?JwIQze(_o&0vGOGUkWgy9{*|Bs4&p;UgB z^CXWw)e8TWfVcHa105I7MS)0(04H^YTWg>jHxH0OB2x1D9!dwj#1mk*Bj*(uovq+r z*r$yglJ{wM47YoEXo@w;33NJB8Lxmu;|yQp;#4i)^L$0bd5y+ZL^wTw^3{7)8%zw_st zgVrocK(YiQS%Hj+W6gT>gtFBh^gYQc!SO|Eay>nw9)&)6h=vLt!e7n;0hQN`OgMp< zz-((`M)F{%ef&!2J%mZFPlz^7ij1j8DD!e${Ze4^0(>>IgQER}GzHSyIQ@gvuJ5Uv zb2+rZmxlb4oaqNz(>oq%9tFlXUnZbrhl|6XGdx80B=^*Y`B6h`A$(1;(4%U8()GFI z_{!>e+3xyE#tPLks54b(0z3L?UU%}TMqw&&f=(;iFk$Slyoe+!$CHWSs6BAK#0~dp zC#Q}}A(HiiCC9&BC(&L6B()h&12Ek_J}}WVsjftnw+J!aU-#u-$yv)oPgKk4lf<<4 zVhd+{s3nYhEEC`pvsxqsr%n*2tn55$NQt}j@)!}4eS zS-V6g$WofX`5||-7$5Z%kGt-~@fV-XI)WM^1X&Kou{Wg2eoNItE980E>9dUfK=ATs zeVaA!eTsu>>cEsNq<2Q?)PzjUp!x()oR4e^pZrp;R(8Jg9l{r_Z>qnL(pceo zcOPV6x)^Y1s88%EPh5=N1^cNRMTPF~9M62m5#T52csO-N#AkMjvzH~A2k#TJW5W|u zWZv8<9+_XHOn!EDGor^Ia7%-4kc00;ulN15@|3a96BAVm;el1U`LEdi(c4db?aJ6( zvhW$-=_Ixk>4^Cx4D!Y8GxO}T;R5Xa9MAfzq{a(rl_BzJtrHi>!Yp z{rl4$tRq_T1!MRX8jT~>Seh|$a9=3x9fHqo>{{rO(G&AH3?tLe6*x!Pkzbh2*^HJ# zEgX*)mWDGKF1d$G?h|KaZ;u)L#DyRh9VPzZya{^QA`{4d|3h4PRU zycnUT41hR?2^Y6WZd8_?Bz*^3!L3IUg_W1rdvQGc(5&3E40s1)RH5jAr*Mz!6X=?p z%HvY3L$JU6#=1jS1asZxpIGHees77YR?9ge_DlYgwd%1c6bwnL0bd3JS@%Psms|rL zWQ;{wUSRG(ybC`xsk%0L%{Wy_PeIGWVQ{Mv4mjp1o;Ox{7pAy|U;je0u+J>Bu0e3u zLPV2fN4C_T9F%-OmEB9UDRa)P*cIA35H4?!`t4KOFI|&n5u?VTGsq+S7nx)bKl5>| z0P7$o@`wmlP{>YU^21EUx4Fh4RrlKo`w7Cn;HrBnJ;In}&Z2RzHB?Q}r*nHHr=~4i zCzd4ChgGa4Rjx;mXYa?atMzw=rnV+d&W@&rHi-X3c1Bi+tSqD~r2i4Haj@n+}GB3cA3_=`3ODA+H{RMLLGB)AoTnjE$;V$Zud zIq-kS5#`LnBSfyH8TddX^MJc;Hkwk__@f``!OhK5X|ivqukpBey#zS-RUOWQ{Vl_ z;g!FJZwB|lFPZXz@w4Ff!p=o5h_EsE&b>*v#8;}$#kM#pVcLJ#rmQf}j*4%;wzp@= zGXH%0HDX|4Q?I3aB;5+!-e$Ty*Qls#mL@U)^ut0ALOF!NmHG50FsLexqwB?GNizN9 zwL{iDsI}p%&jkWf!Ft+qwqAwlr+X24O_$x1%=%6CSLP&oO{9-55`Q!f?3G~k6hn&r zA`LStx_+kGrP@o1kJmK4vyzC;9k!~5dw$jh(m0PS(~Z-O%#<-u0!G1=pPF+!|4ORa%gGe5qr!nV5twswqZ4k`<6#$Ks!!>_Q|ZZ>@TJ;^x>H zPp&NRyOpX3YtN7BxQ{@)9)8nimPGy@cI z*+0|L`C1n|M_M;Y~ZFXPTt3s1o`c!A>Zz5DJY zT-+^Xlkbm8b4KWAp@MiBl!A_q;-g;wCGEs|5!MiFVoIk{=ma=O^rV1cb{g znfDVQtQ|^<45=_&k<}p#VCF0&P_>Y@C>Ux_BXW|T9cvNcyQUAjlQEWS;qJb!o$uR8 zwy)vS{8xn^KF9Ty>n-&P?lykG9Z0n2Qqn^&br357mWkUwO>4#}0j$NxlUc&RZEAh* z9$$yI@68g$yK@uO6CN6WMp7(6fw8evnOs$mXD()P`##X%F)s~KvT!H z5-yeH`;#1m8EHx`iAf+}AT{ou0&d5Yo{57}^B;&cl(2ox!^Oy4N}%1X|zukR5Hkigdw z#maW7>S$;JIX=6*Y~vA|r9yqnv@(5V@-RKaE$rmw z_DpeRCBibvmB$JbrQ^x*UPX6qoS;u?9<5H;g;2=jVJR+ecWG?lRY%4cSZ6;OCwSe~ zmF)TZO$eEiK||q!LA-3tSKvK%cDhOMOSImT77GWP6&owC?El`MzeLsfQz@FWXr3Ut z_lP9@O@l{;oF0eT1$g|Ur(w($^JF|NcVHA3e)ZQZY76;Ob437041!%RuR4_b?C9x! z!Rvls2c`Ap$o;)c>nCRZhXP$&PEHrM6Bj-oH#b$R>9e8spWlH`U>T(jc`4&PoFolE!H$X#YZhDEa2nAMzl{T1zEV; zA8nFpri66EzKMLSj>V@j?32Sa1QurF3by%A%)r_Pi~))gV@cA!s9RW{G~5q3Lpq3Q$r>Jz~thi7F ztnLG6r;hcF+yVG5&roMXh8IPqqNZG~TB{Wu^-J1?rTT&#O@|FD3e-s|qwejwLkSfX z%({i$YNpm{;ASo^SFTO+`aoy^BPFHygeiI2mgnV|%CxCk`6fV3pCSQrZOWkbMY2HE z|Huq1397$GlPAtjTXxfj8d-<%+Q97yLI#SEqPkCV=Ps6YHhwPzo`v^(w~cj10P8nw zu&IeJEFA^(t~~0?NrjfrTCo=s5)gD;oqIDnLN|82N(cynZ}e`32*H_WuIvOT#%{l! zVQQK5C&$L7joCxZ3I+z@Ldya&NszdAA*kA1_umeB48MJeboE8>P(ZmD8k23vb*+B z%o2DAw;yu5x>^;yU#vFtd00K20VQAsNS4~{Bh@<5o7OHJ9rE#TSO`#+2M!r>^ae7} zWDQk7zvVNT@x)&!zWQcHrykF|r z!HLLJ^o=Yhn>BhpKIRUe+eY6H7y1J3a~J1qjkKOj-3gQL?u*M63-j~E$G{yQ=w)hi zX61_3_WOx`ab;z1JfeE$u*n5iI%hOXzX{7SQU3eoilK%Ib$Lm$`fAz2(e=`k@R8+^ zfethOMP#&KF`jMpP6udplfiS@g5aKsi3W3YP*5mv+TzmVSHjWEM5fw1YLhXlysIgEzQi_ippbF;KYk#0Zs5 z7ATG2h?BjzdKDMin)9QdMMuHsN3f!$+k~ho{n~wvp=WGf5c!aPWds$b46n}vri-R} zDMVIwp!W}^F~0`*1Om{9e`k7zscoB|aHejObl4Ri8b1-DSUzz22pkuEh=5!;*Z(;( zcCp!AH3KD8$SUc4nq`$&a?Twm$1)1mXB=GHM{`3;r&zp`;Kzd_K0d)V+`tahKZUuR zzj%|;ATT{{#W)&X{n6rpC^X0%J-NwF=RdWlySZD^<7#!U>r^To=N*I%^@NE>WZH3_ zcrMc@Z^*+m&JInR1eo4mydFbJCiZl++~ujt+3<3N(sg)vxOZ+Eh`Pp^{6&uC&p$WS zi2l$m{Z5<-J~~+-B;bHs{-U_TZftDu4Fct^(;2Bc#}=qL=rF8mhh1r=lsHP{8(3Xk z6(!~=Nw@lNV8qrLUVD^5&A-^|Ac&G0Ty9xyUu$1;^-{7^0xDZe?~arN0sM{OAH65d z#|+s|r?qX9LP11?H`==$k*93R({71liav*eN$&TruWf6}r9t^-IUlMzM6-)ID#?Hp zLumyoo`6_nBtm!3L`(<2@K?W^U`+VpQA$Kx(Rxl;&WQNPfC=*7bl6WitGlj8#4}$n z#~<$IkJQhSfi0RZ%&#iUHPK5fcdgC->z+P7>86JWg|$-*jc@o{nJQ7$91UK2Kx-fy~YZ2;lOKlp_?-xu2Ei4&{C%-%@L?008x6vJ08LIlJ!CBXZ~$rTOdgD_I-Nq zw%Qo#Eeh8--_n_~&hcHAa(gKxLHKg!ii$A_UtX}CT~&-&(50|JG1$TBRgywG3;6*c;-l7 z$J?{6aA9WJBo+=eDoR}F?4~2~gU)rgXwaNPW~9XQIxQ^)|Ho{1pq;WEb}S{#xB^;9 zPFLWUrlu8rcrxRUp|HW(g_Ua|XvGhpYtvxzzM;G_)P!N@MZ-9||dF1Mx z=!>zOGL3JD;2GHQ2_!Hi^+6P&EL$hhJRQk`o1Y{NccTw|)If`uZ)wrlb+v@4HH~tO zj;qF~e26v9R3ca!%0FVoeZxlo zf%_)8%BYWR7yeP%r-sS+bP^BH+0Y7VJCtWZMY&4@#-;NS>TjVf#VXokE+-d+`Wf3Cq+ zlH*AeO@)ohQF3U-BIuP)Ercn;d`m2(D`HyTv~02XgG>?`qyyC*UmIzW_%82E;3W<^q*b=OX63EBmMD~(Pe%E=VvOQ6hQ6YYc zA{&%r2oy-)gQ(vaqs%t}qL3_?oL-Sa{|QK8Twk<&oC;wiJJ@K)*BUR4&?XPA&E-$H zq%S7T+Q@v+<)qRYi;eDeEXgECPeY2eU7Uz&kY*Sje15>^wu6r-y?hn`$3)KW2c9hx zIMXi+C+pXx6Z@ARQ{cnSo^p?-H9Y-FoK%t>NpiiPySeu|fr6^QA$C+yPUvDgDPW>$ zRO1zLL%P-e>CMtPEkSVj47{f?ct3;%N3`H)w3V{=2)z}4bKTFo7MAE>A@$&%JSH$+ zPIvfXkc~5%7VH5MkuadVID19KR~$gLIzSiyj`z)G)fQio23Eo0B)*Go(*JPWv8KXl zeF*yqe9$~nzrYKCuZ5x|_Ai6-g=FDC|9Y#E6a_47H#WVV8Ht%ST3&GEvtUhv)Kc4})N@ zz*eTJZQl@`wQ(hnv$FNMWivkFXjAY6YI^h)YywbhB7iN=lCV@2Y)HLB#sxO)9rI)x zD*#(ZnW9#f(bS%dST;%4wKzs47qGfHW(|*y zQ#S@d98CmD)@J5-*0b5R19l8IG)}E}wH?xXXnCOM3?t!g6u{KU6ia1>01Kry~D z!TsmyV@4i63S-h1(^O<+c4>})+l#Xv6Huy>r>$>k$fANY6}7~DH7KSnrKP|$5v5x+ ztlaLGjG_?>zhhbAkK5d*3>ZH2WI+@>0k?6=T;x}ISqZ9cLWo&v#VeL$F?92!GJdL| z0iSwe>ReezWm`?KfU4celVr;Kxxmp{0@%iE1`?au(J-~hFSP0FyN|43Ei0l_psY&X z9>#g3K$?4tIJ8=gvh~{+#Rl5=_yuIMAR{_It@YD3^Kd5BVGG35nE`E3py^^Q$Ry}8 zY?rAD18!V%NIH2B0-7*Xg%tM+3OR7eFlUIl4c@@X=u&|zbwbO%HCEv~FlH#-EdNSA zSplo#$RPCxN`aDj*qqmn`KMDE2|tNV;!(2&&$7SK(I|4MP;>O%Sk~qeA82yzkM94@ zQMvz{qjIuyasMw|9n{Y*e1INMp zPmYVL7KifY6E3?DsQ?QLm*js6H`{*+M*=!E9X!{64e`_}QPV&IXx4-a9>9e=r9?!H zxH2ZyNlZ+hv}}#|RgCmoinYvNV5Np>w1ROVZ-~MJQ-ZB6pQ>NZx=|xx(P_R9<}Yfu zM%_80wI!y3ZFO!q(pTCL>|zw;OTT4=8Pf6iPe*CY%`XE#i(3M`+k~^H)J7!k1v^A&q;{y!0-#dElYd0+k{M84aCl*;C z(*CP*>eN?FNke3`l1OG5hB&2L8Uy+JP@`}IzZdWw9LqcWK)IZM5@m^KK0MA`cWNYD z@?-W}x`qE0=@0-{oLb3VNy;fY#xQ0YAo@ONmy2_YKei7XRMVs68!c{-nt?DK3S%8n z&V`#u9N>K>O0FA1lv|JaJaIw*ew4qgt*P1QHU?yYJ@CcvI#9yWk+BOFtbCgYr8*Sp zEHC(orMkjiPz^aJ@YQyu*;2vqQ-*)_G<5RjwaU6q?QYVo>IurHPb_aaPeY?>z_E+;|D@vw1T(5qg!p+TeDFDJYcp_c$bv9FLUDjGgQ$MC&VQnoI4@ogx#fTUI;W#BBK9H>)W`&hAv}lrlWn zi@UVDSy)(GyB9sAr!fD31}WOKk1EzkDMKBL56%4pnIOMlNkBk57^G`=i=R?9Ds)?o z8v&U%Rs{IGKA!LGc6vQ{rI-6b=a+qdiYcVpP;l;|ZSAC_2J3?tFRS`TRyB@L_OJO$ zH$b&X7hI<*?EM=$QPIdtHjg9oV^T?8jCX}nTn-Lt!~}|U*4x|D@!Z5 zaCY*xO9-aWeuu;`0d~p2oj=pY+b`$hm{Ibp6q47xCLE3I@wBr`S^XgA-AGQR(Ux}tIv8t z`x#W=jnWsv<9qCsqL(!=Fl_R7pO5d(V_*Xu8C74uCOA6?6M>a?2Ah#YnQlYL3&`Zf zwqiSS5<2bh-On}YO;l!P+fa6t6OS4?1wP_)HGjN5N1zUd?lWBDQ|=` zR?uG`sKkCML2!ix8^%UQ=t0{=5Z9LERhPFn4on-2tO{LgZ96vCH&pz!D*w)V`vf~? z#X(qE%2nd3X@E0oRp-G+#XTWr3!HvqB5gD=hkZPibsX6qoh#4zOkbgPMd-C|#?K{D7{7b_P`3l>8yUS%&Fj|2BW+L!-N%kJUadGwR z>FeZ*zj7jpD&G5fCC7>%@GeJ@pTwmf;@(EnNO4^<~@Le#YLejnKTe9EFvOUG&D$d$nqC^=bW&TgDPvA*~8(N~Hj(pBgm_yOa`f77C2&a#xAmY#k>Sh`+O zY`2Q^yId`$(w|D~y&_;ckL@n0+dw)|gZQVGySD_USa)~n*Y?-r@pR#j=`$sv_girj zGV%;CAzms!1%$`;Y>aU8TYmON+tcyr*B`;OD0Xj!$38_x044`=v)uJ)%B=YKCh@H6 zPj~V1xDM<4dU`Hi?DW+3ag@7OxnpZi1uiL^VVsoGlOr&G=Z0Q`aOQiiy?0CNLXTmn z&CiYLe419BwA|saP-@g?qE^B$%!QSA%z^VHMRSala}_^u_8Q_wtmYHE?wy^9d2v_u z7&wwrBM1rM0JwmkXB(OqEVv16r9y{}MrGWIuQAEcdSaf3yMJ3tN)3LbSQEmOtlGH3 zv?mu7@UG-0wQ_(M>BwIrjWs~EH*?bFnm!bXSiX!;k(*;tlLr@Pg11a%)7WA(Zo$tF z{MHh|kEbJV=AC?+2ZHXWLq5j2r4=nREv+pj-P7x?z+q*FBj#tY{D-=pmLH7*OfXC< zB2wg;2FTdB)a}wsDn=ubPt8OVJzX zqo8lMG5ZGP(?0p~@bL8TOha?f(O$*lZh$tZ79qO38C2UmrS&vOF4jGFRhXTgF}48y zfHoHgRBs;LIpPJ$a(r_O!H!l5U(m{zj2g-kl3hLa6FckM7@Y>Uw5k?QlfWz1%G%)w z!p=M*;kK*fnTD<>g0Aor#LevJVj~SN1ipt_4|@c5bz7j9=PZk=ziFlEx)~3tfc5PY zUu%ok^4~lpv3#!9;FB{jFWvc#d)s2KR%I5DI$$L^e#*p!y&3HV8~CkMwUp?-I?iI3 zye_7C+EdCu7rFBS*6VHxXCSe{Koio=D6wo{-u-oR$L*(p6T!}`xqjQrW48nKZ7BCe zr~6a%BsbfInQv?L)2O-c>tDfGC_BH$ABRYn`qlw%)hA6~o#cG>YU>>7t@gVL%URrk z%|4>D3k(|8t@zNf71tMQ7Zf;V*E-S9r)NisF;NYt*;xe5?x#hAHuMEjx7PjZ`z1dZ z)0-1^JQ}3!rcPX@5I|N0I`j-A5sLn~i!kKecIX)t_MV-v2l%}0jT>*WOdV(M`?W>y z#TAuyCMG6jk<)f%ocGRXw+|O~laFcujrw#5RPSJcnG(t5Dqg0Lkk9L3+#5c5l2GCC z2ey#v;v2$~`{Q;JZ)Ni*)-LHgv3rx+Eam?=sDrFp=N!dQ(D{{VUiL z4q3VUWfwnBG2US7X#S7@ohoessO7Z}(~MJ~Q>Mqx$iLv9`7Sm{e1pun81wvq1?Fz- zor_j_FsI;YXN3paK$ttUrwIZdwB3quH&qjq)Ro&MNSSvSd&idJtvQ4vS;M+25uo-&kTZm}s6tRs;u6AOjVC9sR z$&_&J6hUI85?vkc*{l~f9~ur|1%+5XntL~fR(FD!8RL4At!x4HNBt55iUj|VwM<@6`Hw7n6!t}5~v{boyA0_y24%@gAj!q=A#VcZFsFg^d{E4GQyC=NQ z@2RIE^&8z_uJ4`@RNpbn^RO|$LrcU#Z&(rUirO~uYN6!t*!LN7!aE}a`_z6kK^Y<# zX=684%sqDSW-}t8eu|%%`~`^LWAZ)tzIJ~N4Ji_^96Tr8a|%@ZOz_*2a-=^ukOdK< zrfhw6{xq#^<_SjOtqUi=NKeg?UqJN(t$-}H3A)K>6ASead+%5GSes}lj(*&XwpVzv zN6W#e&j20QI24dr5p<*nJj(ebL1!Y=K`?wvB@>$5Mzf=!UX~ybB=^GKSG9;Uic!tP zTq9cZmx3Tn5V^XXROS8T4h@qnVnaa-gD2%Go@CEFBdF~~LR6_&hIvWlkJuaW#Zo&^ znl-{cAY82h;){Y>y0p#qlwr$P)OZtwKHDrKg;|R*Ue^(}ltUf`fOVKPN`--vO49I{ z1l7LJ!WkxlnGk;|C2}s!9N* zgztKNos3v8I#jHi2sSH3`PE}1;mUOwR$k&;GIk4pzLYXvX!qYk@44fN>4b+Csfmb& ze+0fcCii1^4jv(H0dWh^BaNyhfwFQl7JUYd((M?3ijt44W6v>?^b)V+>J-Dc-Mi#j z%J(-ZR+S@|3l@h|`)*`2q_JyPwNC?TV){fN$CnT%b*?Oao=1UmOwgy9+^SZsH?(V) z+T_1`AW;2Gb94lO&$p)$$5B0E>VE7s^H#|hFE;!!i4kXK23Gt{B4r9P)deUQ0^4*a zTxE*arS?V@zYck1jbEzkc+jP-@!wE^hV%J;{_Wi57WE-hHqmaQ+k~GM!p`xLTfM)_ z=J#^EZ2(CzLvA&?CXN(lA+*&!3^mr>5*7s~!6XK71|k+Qo-I@z3A(Jdk` z+t(cEFA{W`6lww;IB{C=F3#B3oN-oB914vBlN_{2|5^Gcei zMFdkMi!?x*j5v-d2{O_<<8Yi+E}6cZ`pF)`It0atl$k5iTNa+%!7}c1bFYk$5DcWyJL$?+wm2_zzo=7t-ReYis9qZRVcji)vLb#{^o?K|yxmMJ5ALNxZAG$xdj@Bz-EDPo=ye>5f zLXK`RUiNo*iUE-xY&Yh1M&hqt>DWBPQnB55WwK;+tl>lY#xFPl%8Jlm1H9=7VtL*f zvvvMl^RT8#2gZ72A&mtps07Gk9YK~+^~|s#@BqqjfhyI=JOR_tyD6uxR5g7m;qH{5 zd@b|Vb@q9Esbn<5qN+~)O+PVa(=cEvVZmd=VL?RpeM;^=tBT$E3s0;cd5~!tKB?beCyhH_j-PL+W8nt|3Y*-c-ouj ziTo}01^>R)M$v14e@Td_7g80%7{YiD`uy-zSWS=lB0i1*3+bBM(hDK_5*-F*2MUDM zu|uQ)c<{X&CA+<#Dn_F9DO3EUuE%z=w-CB`8%J4xG)AUbpvT9M4W5txPPt79Xo}vi zMz*hKqT&{awt&2HEMUuob8sHf$0i1gM)5~8FzTP7LSx>WGY12pd>+=@KO`m{KecTk zUOl{<&Gn*`vS`J#r_YSN@S}qw2LQpx{!}Ej^u$_Iy|a8t8d+E7M?dmKH!GF;BjFHl zc`5{1(D!swfky(z1Gw+wRx(OIf<}2AG%og{onLp_0w`3EYnCoxpb?sTCxqmZY8-5l zU6Kl4UZT+@xT$+#f=E6lIIr)l5z=z8Lrhj9A&hG?S8#8~tyrlOg$_Vj9OaLSjYsVb z))b94Rr;Dx8{kMFRe05yMZ{guG{XOv1#4%q2Ye2WeB3v^p5PJf926e0q3NJowioz;IFfLO~ z*}I5f-O5~JJN2`(nZ+gsXqv(0xG#H~v-?tV6>&FlBcq3X%?baFv!pC1LyR*U?58n| zwVHboBfQ27YY7geLvYUz&)C2wHL_-q=FSW&G`9)%6vI(`ophnJNJ0LCMX597b$(y$ ztkOx~lo5D#Wr~4D*s)NFlsMy1DQ8Z1lxd|oWDU9^t5ywSR0otTtJ6W=O%Y8pw5+Om z0PV!D+`wzqT#@54RJ>mnkE*0ftKY9i6#itT|HNq);L`Q5tLQhup*pM%J>S7gdGWCcl0!j>F6-`Kad!> z8DN!hv!@<&qetQHlS*D#;#z{dL1BOBzC(djlTuz&BCX73px#xl`7cbT&LS#YeW!dC zqUMa9xt!rM+>F{}UN#a=Ueyi?@hDY?rEDn_Q%MinBq=2yh zIe`sLhHCN|wDnR5AcQ2b_8@5I1S;Lj0$aoNYF#T0(&NcZ`- z-RS@#ms7F;J^AK^khQ+IsW^F`=8vgwtBt2q^r?S~DNg8YLAakn2L#^y>z|&_&eCfw z0%{i?7AU&G=W*%5<58fShQ}?vYp&uy5UMoPN}@6nw=IsIKZ}$5BxKv*)3^*x`ZfQ0 zsgcQv84^x-MkmLiH?8|S=8y8>Nj21=ED)(WBA`K`MGq$?f>uWpT@a&FAg&y7U&=0H z!|j`JU#1Tp6~&{^s~LNcTBBE_HuQ?S=2BJp^^Q|b|(vW`qOWiosw-o{mlJs#|aUs>q(`$3lNId4`p&t z>!lYngVKWXSyDjO{;Io;KJ{voUlQYn*y zLsbRs&_^Wgkfk;!a1MO!+ydO`Tx;@o zc^2~ISh1}2R|ZxC%@sB%7-F@0|wBp)2=YQ{V?tYH^ zOY>0n_oKc|uK`g-;L6k2S?4vC@ZO-DY_ygTwZme7y? z*yyJb$w3U*YW2U!V`{OKlh2bzmR1A>&VOqa2u4#*j88ioQmy7Ra6s^eA04m$d_BRKgDw!7ALff7a$r! z7mrVWDIMLeLeI`I?oaphDmjIe8&S$Vy3y}RwJHNl8z0)&e1B62o31-$2UkPvT6a5x z+?J>bUQyuqNwl|&-Y_fU{C*jZ|A@fa_~67%_uujilG^TjtjxE2Yt6n!@8YSMQ^#k2 zD~6!pO0$_i6+?SgA^RIshIX+!83uA+Ox|{4bj;Q`>Kp54i7)AA31)~i11`BADn%K> zF3hl_4E(Cp5}1ew@{*vD+}B5GT=i$g7PrNL+dRC=790;{`Z}My{o0alW$P~sV^Du0 z$}anQ_Ky3iu5#D=2qAe$+x|;MeTncae{GjLIZ*luU$(r~^z6%Uau{UhVFc=ezB-IY zdk}1@^!MTO^O={*r+Qin_$=T7w zzy|goWoKv!%LE_>5dR~fV42yNI1^^z4zA zD$A2Emg7x2-hCx*S)#WbP^oN5rPX6J{@_bi?iEPl3E`&I7ar6k3Z)AOB@3Ar!`1hJ zTQQrMv2a)S!B@vjR@Y}Dwn6mup3518Ak)5OdsX4D$Zl`8sDHgoaeloJZM}Rs1p$Og ze((nU3_$dz)pd%k{+6Bk4ZdKt30dm^yqL79W#R%Mu*N7DxJ z8O-~hXSqXB>36YWu}Nm0MASnu-x)uVSc5LXn?Ncu%BUz5d0WDHZ*!rX;eoUOcYS08 z;(MwznpS>)u9EcQE1bYe`rj^jq%-NpY}E>Zq(2lHrMH6$esE$y2VrFWI0(0ecwz_- z)o}ws!sXGYJmo&q#0St5Rt=r0U}K~Z|GJ0&WQytA2`+)7GPUc43jkImrWXC*Ot4bRj3yh_FWsjMzpeq zU+%6xc1P}xvfl^1j;11fwbd%wo7>S62-*7*djH^0*3k#SERAc)fjLVvpYJXt*gO#pzfD{zCc{dY|k&NY;9^2R1&+lKX@bi5)emZ4WKyow~p@`YCj zt76-caB`)Zlp@il#;b61Ceh23^YfK#h6x!rS6q0}f!bL|%^9n3t%|>+^ZHGkR3Iso^%64+9Z38z-?d)cJ%FMUJ z1NzGzom4WcT4wN=_fiv-9yODc{Nj^0Nu<~IN5a`Pv{Df_YRJca2PR6$w)XyBMwTce zBlF?=<3*b<0*D|vX~A+n?R4PeB#SViw6n5d;ljF$i%*QXS2NHY1$2%_Arzc>u?;M_ zHQgCeYNOxIPEB3UDq#3-dMGxOX}c2DwE6zJ#Q(87YgHwq<9ql}wb|JrYHag6#P{3J zOHm2BepaNlcB}bW-sX*i+v*cPx=B8Cr7z5b~8~m zQB?&UOS@uk?(JjU1Z{x(3t25NZI3X!{iQXh*bbcahu zxANPmGK1&J6jN>&O&%_zX?UnKG$|BP)HP*&fyRo-TK`Ndd8ql_wIJqdD_b!;#}BBF z2%!$o8+hL2BtP$z3d75T^}xLv8ObQa&=u`jTpMBNC$!vT-A>QAI0b6%-x^70^KZK@ z*dd6KC1?Ez1_cMxV~TApwYhV6IUDy&L@io0aAl71GIPCc*cV7B(aGU{K3f&$jam{A zgo!d{gozFgrQtCJTt>R*(CZ+4hFAJGc(1%w;> zHjR~7HXt=F6D$^K(GPa^=zCiJt&lDB2Y7HnL%+pb@^7C^Gc6mRpJk?V{xxxSagkD0 zl(eW=G{xiQ<5^X(;c~vl38xwCpirXzBlR~CI-h-ZS;9xX_|EMvXRjTgzL;> zS15bpH;Q)G(~YA(14Vr4Mi7GQ;!=wa2u_(WMvgHd&L^8&egh(rHQzThEs#Iiha8EP z7#~{lQvs5ujT(%6s>G$C$PebSNK%G?FX_hTWVN)9N*al44Azb)S%Z*gFeXb4+eL ziyOlaa5TNl8OuMkdjAD%b8l`EubOHRfBW7lTFcD4=Q;&_?%L5=j=%RiCT)uT^Nstt zwPuuqX4M*}`&j<|soq_|*V`z_{cecixs_G3>Url)3Y&dz`Rj`yi^lr4ZBK*n4~Xh?n~pQjoU zmJ{Uu;WIxXp7^2xIEDj28{UVZt<21zY;|JVnSCW6VpZ4vZCPQr_s(ltQYo80DUW*7 zvPw%EUU`I{U-@`TPv40w`A|~T#5pfngConAOKz;plX0l1Z`RNfk&Z=9l5z;%{)Q%h zuDUCj((Voh;%WlXBrKTI6+H&nCXcG{GkaRQxEt#^nNV!zrB@!Qu*k`0%BdBV)A%+B zsp=G8Tu+XdE7;*c_WOLhsR~Nk-cz%zS0JV7GPpgWVSMPhmm>9!(2X6KNNcthHF7i^XcU~Nm!1RWoQ z@^XqN{`7Ru6p9$0q%i6;r^|wEG0k$}V%Mi!2{3uNdYYQPu9UH`kRBw&9WT3+{n|5{ z8BRDdoVfwjP|^-A7S-ICpRcFia17o&r*DN<>9-4Yw%Hys%p}C3xykuvT!i;lZS@MH zWK-NR*@g)^J2qz(GjzH5w6jMvR0ZP>2+<() zwS4cv+uL(5D`~D(sJrb zVC|Xg4PPt04##!sipA8dF!P{m@p)0B-q;92WqQ9XE7GZ_(CKWjC`0g(xiqzk1vnVp zExUurT@Qs=fy|Z-YSf9lTX>gQG=I=Vd$%$P2prnBz0|eE=@R-hEl^IA9`ntYUygbZ zQf(CrUA6@US{h76;t*wTJgX0rYoVEALjkTGLjX5e@ zJ3QR1)YMEO9D*%=*7+5S36kY+PwUZHmz|q(b`fPwRaI48NUX%gxun%qDQ|8tv(O%! zIf!<}B4leIs?OJj^>_6qmVHLraej=sDW7w9(W$GEY($0G_f)Z4BQ;}9sPl6271 zM@gkz(DcU>1zJWy@0bi3dM;xg{X3$$Q(Qh{PeLxcBD}BqPRq9`%~vGzfXF!S-?p=M zxhWF<409F7fDhDq#ysU+(tBthg2P`z&{7jOhV{5OIbRghr<4yi==tr(6lu_#5z|OE zu};dy;!7ip$0Xl9*iT?~v6d|uni)YkPuJMKI3Qsa#@h(nP+JAjd7cN32YzRkkJc2- zp?y{%C!58nc*1Z;XI|)8h zR7j_{#VtYvB4Sn2Fw9}uB#6+=TlFKcN2G+n>8ZD+X9U6&b0QRioTYLi;EqA4GYBWj z;5y-!(n{d;d*-kPxB!2?feJZucwPfP%v{HNC%>X??}uQ4IVhuk39^@H0cqH0rTfGJ z>70mIM78acUGP>Bo=86QW2OE0caa%R#j{5vI zQfaYDd#Bq+J|5GcR#Ss@Tm_Wlo&1Ta*d6Eb95qBi$RL#Y-ikjv)`rvQ?2It+?lAqf zf96~=BgBfj<#Z2emUKZ!&bvm~d*#EhOyTyQ1_DTgI1X}c-p1~FmG+C}7{j_jkIW&k zf6~);-90f zlw+fK5YrjAS3-=c@A;np1+{IzF2Q1uyKx{vEb8u;K3`02;5O)qd`Wol+Q-3m-L_Os zZWR|R3UYkXelyfT%f@~knVpJEKW>SC>;i2U0n?e1%LemUTx^Kr0@Xi?uK1=FnF@8_ z{kZ+o!GJJK5L0dP>be~R>FMAyWdI5?uHl7FE%b523m7woPQ^&EU0C={8*iNsGxKn| zXKLi~{8k9w+8(50IHbf(HAcda?dKi=GfRlY(|`5d7Z~$cUhPE`oV=mC?T{t@Oxbid zi{I+DM`1V8$E>&6Wx+r+)bd>WD`JTqfvoozA*`bZZQb4(zd8sL()*A_jjwHp<83jA zaCv8Q+ZJ!!JvLX(?H0{0b0b@8O=c*+hHh^2&>rxq&kRb64Dp9CCBdb_+GZZ)_9*#K}^mLiFe-jvu5KKt)x)7ia=ovwjq% z0=320-U&7PdKTOb6JUxoDN*!--5{HBD23DzS;o@aT#WQ9On{g&A}J~b3RMlxr{s8} ztJtL3p&2yB+G~UbUwsZ$k1n9gCEBxe7E!LH=es zuvV(nb5B&Q8*3SC%L#y0jXP0sbcj+P+Ez)RVtsv86<|K{|9lDpPasIEb zkEs<=Y!a2<45T0op^%sckIHeIb_f;_;*=0;Cobpv+HSf4C{$s_J`ySL1w_yl6uSxK z^ocEVtY#_K#{s=JxLoVZ@LF>T89DN4&w~SN&tKz>G)UCb?89l#5M(*SAv6#LI7Ia` z`K0=yOf%qtzugj~IXoMum54&VgLMkZiT%3KKE{7VHw8t&Y9s|KGM!f;*Re%4D@(Kl zKM}3Ra0K!hsX}SzmngeHbinp?WkQ{$=#0mN0;^*MQ36#!6@EkoqQh1Iyz^@jm5UkK zln->#`HSpMFzsoCz~!ceseDw(V}RA)@}EnVTDA`Qh{V2ddPPm; zq(-pxnB|!uKL=ukozHMTD<3LMga5EuH3)Z9HtF8HOi8%7xSnsOF>vTqB5Md7RuVvMNswc_ z2#Fiiz9qw9u*-R=TT2GW)p7BNP1X3yu#A4!+`4?B`f?(wH?LRhth1-3W&hAECF|_N z2ipo37U-KhtS(!lJPaA|OJ$$*Sm8cJWnqFK^W(uagvsk@*l2`S^-u61bVQ++$r8p1 zQ`wAld*y1$hE9|!UD*sKI!%iM7|78G$r7UFfSaY;OgUZ|Q?JzadxwGpM)=k;oZ6Y+ zOwe|V6I>5OK9Jj$H7Xhsi=3$*;Mr|E)w#KVfzjI9))r{4j-~9Th)hXEU@t2N+dDuN zwA}CRgf=KUv4_UAGh!va-TF9TWIs}4c%i_(@I&(s1;>1vOJW+{bkX*ZGrI zduOL!rcO`eU=2jga3NyJDu_X^E#PELXh0PD9jr`gr*AIZt?tWfC$C2#L{X;{%*|zL zrOesW`{mY7%^!}eK#SNCDu}Bi%enC39JfuXrfHN@zjz~N-p+)<8L~o0GNOH60b$qA zN6*T(T4j+d)26FG)9cjBOWvEJV{7YVWYgh!&8zjzlbaE)_c&!@6qKlwo=L)4>(PaO z3(cJ!DKbQbk66BxUK?>*=GjqMEzq}1IkcQYeB|pI)l!Bd1|2V)BM-L?Unpg;qh3@r zx#e|opUP6K*XrhL84mOH^wH$|JU+$FZcksi_Iw^i%gE=RAi)_Edsy^Ja~dQ#Im5|4 z-U8#~`&7T*GxA>u@^}PS|@9V2a-fqM5;UKwEFj1`OQ~7~U1*F1>8?;XGaxi9%@`+f`m3ACBIQ8(foxEaKy__=cWW>+DxL|i$ zw%uU2zds(yYE(04-pwry@O`rl**Lgw*fOeqg-A*Z3S4a{YaQiMQ!e&&oXV=aBpVV+ zx1tzyG}3gs16?Z|mj%3~od+|=ySaSVk&ASBz5SYr|7|6Kl)34t?t)N$7H5+$kkr;! zl(RHD&w9XB@2I{XNg)~tave9caLK|wyR@(jcI=HQ^uO<7f8Vc~QNG^6IaZuLWN#n{>1m(f;zNz__Hng# zcF!3&BXIY$H_!R<`1%C<(*3%>?`^_L4n{iPNx@YNCCqSa{DW=zsqmLEi}Ul|X>Lw5 zsEEH82Q)Lw#fcMfDEFg8@7Q9neU*Gj*sC&S;;f)hCzboauIlgjX2TlRgqpVOBcisJ zrfq*VH-3%?yKTZGpzDE<8{8~r9Ve6|Y0U=#bgA)lfM-{|d-evMWv_uN<5FQW`8LiE zeDmJm?eHP6su_rLD4Q66c$&yWfAZkbJvX3R0?CaVvgMmT{yB-b8T9GUt)f>cyJ!rn z(YQygj|sb>^s4DZ?Ye^Ya+$`UOsv#b2DdX#EFW}nzun$@(&cf&-J3JhZGU?1k)(WY zV<&2NKZu$F)?S%{I%;0-%zU30ePSW(en0CR!(HoI2fEeZxf6S7`#j7=I?`BTb{Ag& zK<>x=1Q%B*R7^YZA>(VnHE$i>?+lGi!dT~5XA_Z8O&8gjIBm}7B||oJ`QrE951Wgt zI&|qB=|>)oD#c4Du(@c9OWdoLmV8*5hCZoqBDS0497Egpz6g^nj-Ga1Z>lLiYabJ4 zY9Gpb-QCN}%OXhmYZ_LUX9T$T>szT0pi;TNhS3oDL#BuFL{ppi*}QyS@5gZ;nxsj5 z#c7|<4J;HLL>&DDwKo5v% z(459T1dE3TvftnA%r^s=ND2K2HKP%G)*fT*IWK#e-jko%iULmzKEq#-RC8%6J-c0d z!=BvEujVlPjTM z1alW8s=S19*-9jm)y(Nvi|>9qgTQEJpwU|aF^f!FbCtBtD617-V!02AYCYoc-o`mc zC9Xn78Zfl15K3Dr<`}CXx@zW_s(IY76=JGs?C4qnG;I9;RJE4e&^m+t{f@w_lOldL zPj*Ze#2|E$rbk?QAAL^tXvI`$K_qKqbO*nB1K}p9vKS>CiX)lVsSWpuWfC# zmkSnPi*odc&}e^)#{4T=0CYG8Y$Sh^tc5gWm#;B3XYJ?VHc1_G24&=?>|+m>V8o;5 z|9C+9&aund3ND%)5qUmFVJS-^|HvE}z)I`h$}ahloXeNMOWsQ-NWSEchCxQ)_2cpU z%aT>QyGFUh7R6Gx-lyKpLH+0Zkt|y|qI<6-o@1l_s9WsXjvJVTerwEWtQI&%6Bq_-~IQyM!i>)}2 zljC77^@))wybefkdUCj%EC4u2P7G$nR)LxdZPFzE7;KhWG z1d1GNABHp(9aV8fiMqOl&bV~eGCT&d+jN;28r86DxHw1xE*Zrmjyq!)jitL= z^!az9WFPztOvad>2qp4&I3pn;@CecoR;=*vv;Or`kzk3^O3b1y$q9lalTNw&jx=N_ z0){^)K*Gow1FePxg2ch`IR?c$FLLOpx$cxQ&O>{NRD=>DEPg-7jYU?{jUVaENh9PU8sj;by?{KGau!NMTC4yA6=a`Bid1NbV;^WJIn20nA!QuKm=I=; z`aUbv(a`Jk-h!_A&*88At_E4nBcVo~MTz_qkpc`e41z9T&46Tz5f<{A)8UzhNFqXR zfKgVr{pHi~)vavBK3BxSq z5Mhy7l74y}nsMUmd%ZydG6xYDunxe{2?@c%&Y5t-BZtY#ObqysLTpP6`=11WlarMt zL6w&Rf`yGa!H1U<#KO+m=J-!O sj{j$JOsxM>tNte=EAU^~;{RX7KR#ym1RFk4SXOp+SPBYJc`?}k1JhXW761SM diff --git a/BookGPU/Chapters/chapter4/biblio4.bib b/BookGPU/Chapters/chapter4/biblio4.bib index 463e4e4..49063f2 100644 --- a/BookGPU/Chapters/chapter4/biblio4.bib +++ b/BookGPU/Chapters/chapter4/biblio4.bib @@ -1,8 +1,10 @@ -@unpublished{convolutionsoup, +@inproceedings{convolutionsoup, title = {Convolution Soup}, + booktitle = {GPU Technology Conference}, author = {Stam, J.}, abstract = {Graphics processors can be easily programmed to provide significant acceleration in many common parallel tasks. However, with additional architecture knowledge and understanding of optimization strategies, a savvy programmer can unleash the full potential of the GPU's massive memory bandwidth and ensure the processing resources are utilized to their fullest extent. In this talk, we'll explore several different approaches to a very simple but ubiquitous image processing algorithm, the convolution. A naive approach shows the detrimental impact of poorly written code, a simple approach achieves decent results with little effort or code complexity, and a few highly optimized techniques realize the GPUs full power for the most demanding tasks. The techniques explored in this simple but illustrative example will serve as a base for understanding the optimization strategies to apply towards more complex algorithms.}, year = {2010}, - month ={8}, + month ={Aug.}, pdf = {http://fr.slideshare.net/NVIDIA/1412-gtc09}, + url = {http://fr.slideshare.net/NVIDIA/1412-gtc09}, } \ No newline at end of file diff --git a/BookGPU/Chapters/chapter4/ch4.tex b/BookGPU/Chapters/chapter4/ch4.tex index 8788ab4..0a0d6cb 100644 --- a/BookGPU/Chapters/chapter4/ch4.tex +++ b/BookGPU/Chapters/chapter4/ch4.tex @@ -10,13 +10,13 @@ In this chapter, after dealing with GPU median filter implementations, we propose to explore how convolutions\index{Convolution} can be implemented on modern GPUs. Widely used in digital image processing filters, the \emph{convolution -operation} basically consists in taking the sum of products of elements -from two 2-D functions, letting one of the two functions move over +operation} basically consists of taking the sum of products of elements +from two 2D functions, letting one of the two functions move over every element of the other, producing a third function that is typically viewed as a modified version of one of the original functions. To -begin with, we shall examine non-separable or generic convolutions, -before adressing the matter of separable convolutions. We shall refer -to $I$ as an H x L pixel gray-level image, and to $I(x,y)$ as the gray-level +begin with, we shall examine non separable or generic convolutions, +before addressing the matter of separable convolutions. We shall refer +to $I$ as an $H\times L$ pixel gray-level image and to $I(x,y)$ as the gray-level value of each pixel of coordinates $(x,y)$. @@ -25,15 +25,15 @@ value of each pixel of coordinates $(x,y)$. Within a digital image $I$, the convolution operation is performed between image $I$ and convolution mask \emph{h} (To avoid confusion with other GPU functions referred to as kernels, we shall use\emph{ convolution -mask} instead of \emph{convolution kernel}) is defined by: +mask} instead of \emph{convolution kernel}) is defined by \begin{equation} -I'(x, y) = \left(I * h\right) = \sum_{(i < H)} \sum_{(j < L)}I(x-j, y-j).h(j,i) +I'(x, y) = \left(I * h\right) = \sum_{(i < H)} \sum_{(j < L)}I(x-j, y-j)h(j,i) \label{convoDef} \end{equation} While processing an image, function \emph{h} is often bounded by a square -window of size \emph{k = 2r + 1}, \textit{i.e} an uneven number, to ensure +window of size \emph{k = 2r + 1}, i.e., an uneven number, to ensure there is a center. We shall also point out that, as stated earlier, -the square shape is no limiting factor to the process, as any shape +the square shape is not a limiting factor to the process, as any shape can be inscribed into a square. In the case of a more complex shape, the remaining space is filled by null values (padding). @@ -41,7 +41,7 @@ the remaining space is filled by null values (padding). \section{Implementation} The basic principle of computing a convolution between one $I$ picture and one \emph{h} convolution mask defined on domain $\Omega$ is given -by algorithm \ref{algo_genconv} and illustrated by Figure \ref{fig:convoPrinciple}, which mainly shows how gray-level values of the center pixel's neighborhood are combined with the convolution mask values to compute the output value. +by Algorithm \ref{algo_genconv} and illustrated by Figure \ref{fig:convoPrinciple}, which mainly shows how gray-level values of the center pixel's neighborhood are combined with the convolution mask values to compute the output value. For more readability, only part of the connecting lines are shown. \begin{figure} \centering @@ -54,9 +54,9 @@ For more readability, only part of the connecting lines are shown. \label{algo_genconv} \ForEach{pixel at position $(x, y)$}{ Read all gray-level values $I(x, y)$ in the neighborhood\; - Compute the weighted sum \( I_\Omega = \sum_{(j,i) \in \Omega}I(x-j, y-j).h(j,i) \)\; + Compute the weighted sum \( I_\Omega = \sum_{(j,i) \in \Omega}I(x-j, y-j)h(j,i) \)\; Normalize $I'(x, y)$ value\; - Outputs the new gray-level value + Output the new gray-level value } \end{algorithm} @@ -68,7 +68,7 @@ brightness of the image will be altered and a normalization stage has to take place, as, for example, in the case of an 8-bit coded image: \begin{enumerate} -\item if $S \ge 0$ then $I' = I_\Omega / S$ +\item if $S > 0$ then $I' = I_\Omega / S$ \item if $S = 0$ then $I' = I_\Omega + 128$ \item if $S < 0$ then $I' = I_\Omega + 255$ \end{enumerate} @@ -78,69 +78,84 @@ each pixel, which will be quite time-costly when performed on a GPU. A simple wo \subsection{First test implementation} This first implementation consists of a rather naive application to -convolutions of the tuning recipes applied to median filters in the -previous chapter, as a reminder : texture memory used with incoming +convolutions of the techniques applied to median filters in the +previous chapter, as a reminder: texture memory used with incoming data, pinned memory with output data, optimized use of registers while processing data and multiple output per thread\index{Multiple output per thread}. One significant difference lies in the fact that the median filter uses only one parameter, the size of the window mask, -which can be hard-coded, while a convolution mask requires referring to several; hard-coding -its elements would lead to severe lack of flexibility (one function +which can be hard-coded, while a convolution mask requires referring to several parameters; hard-coding +the elements of the mask would lead to severe lack of flexibility (one function per filter, no external settings) so we will just use it as a starting point in our approach. Let us assume that we are planning to implement the convolution defined by the following $3\times 3$ mask (low-pass filter or averaging filter): $$h=\frac{1}{9}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}$$ -The kernel code presented in Listing \ref{lst:convoGene3Reg8} implements the convolution operation and applies all above optimizations except, for clarity reasons, multiple output per thread. -In the particular case of a generic convolution, it is important to note how mask coefficients are applied to image pixels in order to fit the definition of equation \ref{convoDef}: if the coordinates of the center pixel had been set to (0,0), then the pixel of coordinates $(i,j)$ would have been multiplied by the element $(-i,-j)$ of the mask, which, transposed in our kernel code, leads to multiply the $p^{th}$ pixel of the window by the $(n-p)^{th}$ element of the convolution mask. +The kernel code presented in Listing \ref{lst:convoGene3Reg8} implements the convolution operation and applies all above optimizations except, for clarity reasons, multiple outputs per thread. +In the particular case of a generic convolution, it is important to note how mask coefficients are applied to image pixels in order to fit the definition of equation \ref{convoDef}: if the coordinates of the center pixel had been set to (0,0), then the gray-level value of pixel of coordinates $(i,j)$ would have been multiplied by the element $(-i,-j)$ of the mask, which, transposed in our kernel code, leads to multiplying the $p^{th}$ pixel of the window by the $(n-p)^{th}$ element of the convolution mask. -\lstinputlisting[label={lst:convoGene3Reg8},caption=Generic CUDA kernel achieving a convolution operation with hard-coded mask values]{Chapters/chapter4/code/convoGene3Reg8.cu} +\lstinputlisting[label={lst:convoGene3Reg8},caption=generic CUDA kernel achieving a convolution operation with hard-coded mask values]{Chapters/chapter4/code/convoGene3Reg8.cu} Table \ref{tab:convoNonSepReg1} shows kernel timings and throughput values for such a low-pass filter extended to $5\times 5$ and $7\times 7$ masks applied on 8-bit coded gray-level -images of sizes $512\times 512$, $1024\times 1024$, $2048\times 2048$, $4096\times 4096$ and run on a C2070 card with $32\times 8$ thread blocks. -As a reminder, Table \ref{tab:memcpy1} details the data transfer costs that helped computing throughput values. +images of sizes $512\times 512$, $1024\times 1024$, $2048\times 2048$, and $4096\times 4096$ run on a C2070 card with $32\times 8$ thread blocks. -\begin{table}[h] +\begin{table}[htbp] \centering {\normalsize -\begin{tabular}{|c||r|r|r|r|r|r|} +\begin{tabular}{|c||r|r||r|r||r|r|} \hline -\textbf{Mask size$\rightarrow$}&\multicolumn{2}{|c|}{\textbf{3x3}}&\multicolumn{2}{|c|}{\textbf{5x5}}&\multicolumn{2}{|c|}{\textbf{7x7}}\\ -\textbf{Image size$\downarrow$}&time (ms)&TP&time (ms)&TP&time (ms)&TP\\\hline\hline +\textbf{Mask size}$\rightarrow$&\multicolumn{2}{c||}{$\mathbf{3\times 3}$}&\multicolumn{2}{c||}{$\mathbf{5\times 5}$}&\multicolumn{2}{c|}{$\mathbf{7\times 7}$}\\ +\textbf{Image size}$\downarrow$&time (ms)&TP&time (ms)&TP&time (ms)&TP\\\hline\hline $\mathbf{512\times 512}$ &0.077&1165 &0.209&559 &0.407 &472 \\\hline $\mathbf{1024\times 1024}$&0.297&1432 &0.820&836 &1.603 &515 \\\hline $\mathbf{2048\times 2048}$&1.178&1549 &\bf 3.265&\bf 875 &6.398&529 \\\hline $\mathbf{4096\times 4096}$&4.700&1585 &13.05&533 &25.56&533 \\\hline \end{tabular} } -\caption[Timings ($time$) and throughput values ($TP$ in Mpix/s) of one register-only non separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$ and $7\times 7$ pixels, on a C2070 card.]{Timings ($time$) and throughput values ($TP$ in Mpix/s) of one register-only non separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$ and $7\times 7$ pixels, on a C2070 card (fermi architecture). Data transfer duration are those of Table \ref{tab:memcpy1}.} +\caption[Timings (time) and throughput values (TP in MP/s) of one register-only non-separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$, and $7\times 7$ pixels, on a C2070 card.]{Timings (time) and throughput values (TP in MPx/s) of one register-only non-separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$, and $7\times 7$ pixels, on a C2070 card (fermi architecture). Data transfer duration are those of Table \ref{tab:memcpy1}. The bold value points out the result obtained in the reference situation.} \label{tab:convoNonSepReg1} \end{table} -\begin{table}[h] + + + + + + +Table \ref{tab:convoNonSepReg3} shows timings and global throughput values achieved by those convolution masks on an NVIDIA GT200 Tesla architecture (GTX280 card) with $16\times 8$ thread blocks. This measurement has been done in order to make a relevant comparison with a reference given by NVIDIA in \cite{convolutionsoup} in which they state that their fastest kernel achieves a $5\times 5$ convolution of an 8-bit $2048\times 2048$ pixel image in $1.4~ms$, leading to a throughput value of 945~MP/s. In all the result tables, the values associated to this reference will be presented in boldface. +Our current value of 802~MP/s, though not unsatisfactory, remains lower to the one reached by the manufacturer's own coding. +Tested in the same conditions, the newer Fermi architecture of +NVIDIA's GPUs proved slower (3.3 ms, see Table \ref{tab:convoNonSepReg1}) due to the lower maximum +register count allowed (63 as opposed to 128 for Tesla GT200). + +\begin{table}[htbp] \centering {\normalsize -\begin{tabular}{|c||r|r|r|r|r|r|} +\begin{tabular}{|c||r|r||r|r||r|r|} \hline -\textbf{Mask size$\rightarrow$}&\multicolumn{2}{|c|}{\textbf{3x3}}&\multicolumn{2}{|c|}{\textbf{5x5}}&\multicolumn{2}{|c|}{\textbf{7x7}}\\ -\textbf{Image size$\downarrow$}&time (ms)&TP&time (ms)&TP&time(ms)&TP\\\hline\hline +\textbf{Mask size}$\rightarrow$&\multicolumn{2}{c||}{$\mathbf{3\times 3}$}&\multicolumn{2}{c||}{$\mathbf{5\times 5}$}&\multicolumn{2}{c|}{$\mathbf{7\times 7}$}\\ +\textbf{Image size}$\downarrow$&time (ms)&TP&time (ms)&TP&time(ms)&TP\\\hline\hline $\mathbf{512\times 512}$ &0.060&1186 &0.148&848 &0.280&594 \\\hline $\mathbf{1024\times 1024}$&0.209&1407 &0.556&960 &1.080&649 \\\hline $\mathbf{2048\times 2048}$&0.801&1092 &\bf 2.189&\bf 802 &4.278&573 \\\hline $\mathbf{4096\times 4096}$&3.171&1075 &8.720&793 &17.076&569 \\\hline \end{tabular} } -\caption[Timings ($time$) and throughput values ($TP$ in Mpix/s) of one register-only non separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$ and $7\times 7$ pixels, on a GTX280.]{Timings ($time$) and throughput values ($TP$ in Mpix/s) of one register-only non separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$ and $7\times 7$ pixels, on a GTX280 (GT200 architecture). Data transfer duration are those of Table \ref{tab:memcpy1}.} +\caption[Timings (time) and throughput values (TP in MP/s) of one register-only non-separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$, and $7\times 7$ pixels, on a GTX280.]{Timings (time) and throughput values (TP in MP/s) of one register-only non-separable convolution kernel, for small mask sizes of $3\times 3$, $5\times 5$, and $7\times 7$ pixels, on a GTX280 (GT200 architecture). Data transfer duration are those of Table \ref{tab:memcpy1}. The bold value points out the result obtained in the reference situation.} \label{tab:convoNonSepReg3} \end{table} +It is interesting to note that, as long as each thread processes one single pixel, kernel execution time is ruled in proportion +with the number of pixels in the image multiplied by that of the mask. +The proportionality factor, that we call \textit{slope}, is $3.14.10^{-8}$~ms/pix on C2070 in this first implementation. +As a reminder, Table \ref{tab:memcpy1} details the data transfer costs that helped in computing throughput values. \begin{table}[h] \centering {\normalsize \begin{tabular}{|c||r|r|} \hline -\shortstack{\textbf{GPU card$\rightarrow$}\\\textbf{Image size$\downarrow$}}&\textbf{C2070}&\textbf{GTX280}\\\hline\hline +\shortstack{\textbf{GPU card}$\rightarrow$\\\textbf{Image size$\downarrow$}}&\textbf{C2070}&\textbf{GTX280}\\\hline\hline $\mathbf{512\times 512}$ &0.148 &0.161 \\\hline $\mathbf{1024\times 1024}$&0.435 &0.536 \\\hline $\mathbf{2048\times 2048}$&1.530 &3.039 \\\hline @@ -151,25 +166,14 @@ $\mathbf{4096\times 4096}$&5.882 &12.431 \\\hline \label{tab:memcpy1} \end{table} -Table \ref{tab:convoNonSepReg3} shows timings and global throughput values achieved by those convolution masks on an Nvidia GT200 Tesla architecture (GTX480 card) with $16x8$ thread blocks. This measurement has been done in order to make a relevant comparison with a reference given by Nvidia in \cite{convolutionsoup} where they state that their fastest kernel achieves a $5\times5$ convolution of an 8-bit $2048\times 2048$ pixelimage in $1.4~ms$, which lead to a throughput value of 945~Mpix/s. -Our current value of 802~Mpix/s, though not unsatisfactory, remains lower to the one reached by the manufacturer's own coding. -Tested in the same conditions, the newer Fermi architecture of -Nvidia's GPUs proved slower (3.3 ms, see Table \ref{tab:convoNonSepReg1}) due to the lower maximum -register count allowed (63, against 128 for Tesla GT200). - -It is interesting to note that, as long as each thread processes one single pixel, kernel execution time is ruled in proportion -with the number of pixels in the image multiplied by that of the mask. -The slope in this first implementaion is $3.14.10^{-8}~ms/pix$ on C2070. - \subsection{Using parameterizable masks} - To further improve the above implementation, it becomes necessary to free ourselves from the hard-coding constraint. To achieve this, as was the case with input image storing, several memory options are available, but, since the amount of data involved in processing a mask is quite small and constant, we considered it relevant to copy data -into \emph{symbol memory}. Listing \ref{lst:symbolmem} details the process, involving -the Cuda function \emph{CudaMemCopyToSymbol()}. +into \emph{symbol memory}. Listing \ref{lst:symbolmem} details this process, involving +the CUDA function \emph{cudaMemcpyToSymbol()}. \lstinputlisting[label={lst:symbolmem},caption=code snippet showing how to setup a mask in GPU symbol memory]{Chapters/chapter4/code/maskInSymbol.cu} @@ -179,10 +183,10 @@ a generic convolution kernel, whose code immediately appears both simple and concise. Its global time performance, however, is comparatively lower than the register-only process, due to the use of constant memory and of the \emph{r} parameter -(radius of the mask). The average slope amounts to $3.81~ms/pix$ on C2070, -which means a time-cost increase of around $20~\%$. +(radius of the mask). The average slope amounts to $3.81.10^{-8}$~ms/pix on C2070, +which means a time-cost increase of around 20~\%. -\lstinputlisting[label={lst:convoGene8r},caption=Generic CUDA kernel achieving a convolution operation with the mask in symbol memory and its radius passed as a parameter]{Chapters/chapter4/code/convoGene8r.cu} +\lstinputlisting[label={lst:convoGene8r},caption=generic CUDA kernel achieving a convolution operation with the mask in symbol memory and its radius passed as a parameter]{Chapters/chapter4/code/convoGene8r.cu} \subsection{Increasing the number of pixels processed by each thread} Much in the same way as we did with the Median Filter, we shall now @@ -193,87 +197,88 @@ of the size of the convolution mask, one can envisage processing 2 or more pixels per thread while keeping safely within the 63-per-thread rule. -However, when doing so, \textit{e.g} processing what we shall call a \textit{packet} of pixels, window mask overlapping has to be taken into account -to avoid multiple texture fetches of each pixel's gray-level value, while benefiting from the 2-D cache. +However, when doing so, e.g., processing what we shall call a \textit{packet} of pixels, window mask overlapping has to be taken into account +to avoid multiple texture fetches of each pixel's gray-level value, while benefiting from the 2D cache. In that case, both mask size and pixel packet shape determine the number of texture fetches to be performed for each pixel value. -Figure \ref{fig:convoOverlap1} illustrates two different situations: on top, a mask of radius 1 ($3\times 3$) applied to a packet of 8 pixels in row; at bottom, a mask of radius 2 ($5\times 5$). +Figure \ref{fig:convoOverlap1} illustrates two different situations: (a) a mask of radius 1 ($3\times 3$) applied to a packet of 8 pixels in a row; (b) a mask of radius 2 ($5\times 5$). The dark gray pixels are the center pixels (pixels of the packet), while light gray pixels belong to the halo around the packet. The number in each pixel box corresponds to the convolution count in which it is involved. -There would be little interest in using different \textit{packet} shapes, as the final global memory writes would not be coalescent; generating multiple latencies. - \begin{figure} +There would be little interest in using different \textit{packet} shapes, as the final global memory writes would not be coalescent, generating multiple latencies. + \begin{figure}[htbp] \centering - \subfigure[$3\times 3$ mask: there are 18 center pixels (out of 30) involved in 3 computations.]{ \includegraphics[width=5.8cm]{Chapters/chapter4/img/convoOverlap1.png}}\\ - \subfigure[$5\times 5$ mask: only 20 center pixels (out of 60), involved in 5 computations.]{ \includegraphics[width=7cm]{Chapters/chapter4/img/convoOverlap2.png}} - \caption{Mask window overlapping when processing 8 pixels per thread. Top: $3\times 3$ mask. Bottom: $5\times 5$ mask.} + \subfigure[$3\times 3$ mask: there are 18 pixels (out of 30) involved in 3 computations.]{ \includegraphics[width=5.8cm]{Chapters/chapter4/img/convoOverlap1.png}}\\ + \subfigure[$5\times 5$ mask: only 20 pixels (out of 60) are involved in 5 computations.]{ \includegraphics[width=7cm]{Chapters/chapter4/img/convoOverlap2.png}} + \caption[Mask window overlapping when processing a packet of 8 pixels per thread.]{Mask window overlapping when processing a packet of 8 pixels per thread. The dark gray pixels are the center pixels, while light gray pixels belong to the halo. The number in each pixel box is the convolution count in which it is involved. (a) $3\times 3$ mask; (b) $5\times 5$ mask.} \label{fig:convoOverlap1} \end{figure} -Altough we actually wrote GPU kernels able to process 2, 4, 8 and 16 pixels per thread, only the one that processes 8 pixels per thread is presented below, as it proved to be the fastest one. Listing \ref{lst:convoGene8x8pL3} reproduce the source code of the kernel for $3\times 3$ masks. -The bottom line is that each thread is associated with one base pixel of coordinates $(x,y)$ which is the first of the packet to be processed, the last one being $(x+7,y)$. -\lstinputlisting[label={lst:convoGene8x8pL3},caption=CUDA kernel achieving a $3\times 3$ convolution operation with the mask in symbol memory and direct data fetches in texture memory]{Chapters/chapter4/code/convoGene8x8pL3.cu} +Although we actually have written GPU kernels able to process 2, 4, 8, and 16 pixels per thread, only the one that processes 8 pixels per thread is presented below, as it proved to be the fastest one. Listing \ref{lst:convoGene8x8pL3} reproduces the source code of the kernel for $3\times 3$ masks. +The bottom line is that each thread is associated with one base pixel of coordinates $(x,y)$ which is the first, in the packet, to be processed, the last one being $(x+7,y)$. -In this particular case of a $3\times 3$ mask, each pixel value is used in 3 different convolution sums, except pixels located near both ends of the packet, whose values are used in fewer sums. -The general rule, when performing a $n\times n$ convolution (radius $k$) by 8-pixel packets is that each of the $(8-2k).(2k+1)$ \textit{center} pixels of the halo is used in $k$ sums, while the $4k.(2k+1)$ remaining pixels, located around the ends of the packet are used in fewer sums, from $k-1$ to $1$ ($2.(2k+1)$ pixels each). -\begin{table}[h] +In this particular case of a $3\times 3$ mask, each pixel value is used in 3 different convolution sums, except for pixels located near both ends of the packet, whose values are used in fewer sums. +The general rule, when performing an $n\times n$ convolution (radius $k$) by 8-pixel packets is that each of the $(8-2k).(2k+1)$ \textit{center} pixels of the halo is used in $k$ sums, while the $4k.(2k+1)$ remaining pixels, located around the ends of the packet, are used in fewer sums, from $k-1$ to $1$ ($2(2k+1)$ pixels each). +\begin{table}[htbp] \centering {\normalsize -\begin{tabular}{|c||r|r|r|r|r|r|} +\begin{tabular}{|c||r|r||r|r||r|r|} \hline -\textbf{Mask size$\rightarrow$}&\multicolumn{2}{|c|}{\textbf{3x3}}&\multicolumn{2}{|c|}{\textbf{5x5}}&\multicolumn{2}{|c|}{\textbf{7x7}}\\ -\textbf{Image size$\downarrow$}&time (ms)&TP&time (ms)&TP&time (ms)&TP\\\hline\hline +\textbf{Mask size}$\rightarrow$&\multicolumn{2}{c||}{$\mathbf{3\times 3}$}&\multicolumn{2}{c||}{$\mathbf{5\times 5}$}&\multicolumn{2}{c|}{$\mathbf{7\times 7}$}\\ +\textbf{Image size}$\downarrow$&time (ms)&TP&time (ms)&TP&time (ms)&TP\\\hline\hline $\mathbf{512\times 512}$ &0.036&1425 &0.069&1208 &0.110&1016 \\\hline $\mathbf{1024\times 1024}$&0.128&1862 &0.253&1524 &0.413&1237 \\\hline $\mathbf{2048\times 2048}$&0.495&2071 &\bf 0.987&1666 &1.615&1334 \\\hline $\mathbf{4096\times 4096}$&1.964&2138 &3.926&1711 &6.416&1364 \\\hline \end{tabular} } -\caption[Timings ($time$) and throughput values ($TP$ in Mpix/s) of our generic fixed mask size convolution kernel run on a C2070 card.]{Timings ($time$) and throughput values ($TP$ in Mpix/s) of our generic fixed mask size convolution kernel run on a C2070 card. Data transfer durations are those of Table \ref{tab:memcpy1}.} +\caption[Timings (time) and throughput values (TP in MP/s) of our generic fixed mask size convolution kernel run on a C2070 card.]{Timings (time) and throughput values (TP in MP/s) of our generic fixed mask size convolution kernel run on a C2070 card. Data transfer durations are those of Table \ref{tab:memcpy1}. The bold value points out the result obtained in the reference situation.} \label{tab:convoGene8x8p} \end{table} -Timing results and throughput values are shown in Table \ref{tab:convoGene8x8p}, and show that this solution now outperforms Nvidia references. +Timing results and throughput values are shown in Table \ref{tab:convoGene8x8p}, and show that this solution now outperforms NVIDIA references. It is important to remember that the above kernels have been optimized for the Fermi architecture, unlike those mentioned earlier, which were more efficient on the GT200 architecture. -However, our technique requires to write one kernel per mask size, which can be seen as a major constraint. To make it easier to use this method, we shall propose a kernel code generator that will be available in the near future. +However, our technique requires writing one kernel per mask size, which can be seen as a major constraint. To make it easier to use this method, we are working on a kernel code generator that is currently under development and will be made available in the near future. + +\lstinputlisting[label={lst:convoGene8x8pL3},caption=CUDA kernel achieving a $3\times 3$ convolution operation with the mask in symbol memory and direct data fetches in texture memory]{Chapters/chapter4/code/convoGene8x8pL3.cu} \subsection{Using shared memory to store prefetched data\index{Prefetching}.} \index{memory~hierarchy!shared~memory} A more convenient way of coding a convolution kernel is to use shared memory to perform a prefetching stage of the whole halo before computing the convolution sums. -This proves to be quite efficient and more versatile, but it obviously generates some overhead as: +This proves to be quite efficient and more versatile, but it obviously generates some overhead because \begin{itemize} \item Each pixel value has to be read at least twice, first from texture memory into shared memory and then one or several more times from shared memory to be used in convolution computations. \item Reducing the number of times a single pixel value is read from shared memory is bound to generate bank conflicts, hence once again performance loss. \end{itemize} - \begin{figure} + \begin{figure}[htbp] \centering \includegraphics[width=12cm]{Chapters/chapter4/img/convoShMem.png} - \caption[Organization of the prefetching stage of data, for a $5\times 5$ mask and a thread block size of $8\times 4$.]{Organization of the prefetching stage of data, for a $5\times 5$ mask and a thread block size of $8\times 4$. Threads in both top corners of the top figure are identified either by a circle or by a star symbol. The image tile, loaded into shared memory includes the pixels to be updated by the threads of the block, as well as its 2-pixel wide halo. Here, circle and star symbols in the image tile show which pixels are actually loaded into one shared memory vector by its corresponding thread. } + \caption[Organization of the prefetching stage of data, for a $5\times 5$ mask and a thread block size of $8\times 4$.]{Organization of the prefetching stage of data, for a $5\times 5$ mask and a thread block size of $8\times 4$. Threads in both top corners of the top figure are identified either by a circle or by a star symbol. The image tile, loaded into shared memory, includes the pixels to be updated by the threads of the block, as well as its 2-pixel wide halo. Here, circle and star symbols in the image tile show which pixels are actually loaded into one shared memory vector by its corresponding thread. } \label{fig:ShMem1} \end{figure} -Still, we also implemented this method, in a similar manner as Nvidia did in its SDK sample code. +Still, we also implemented this method, in a similar manner as NVIDIA did in its SDK sample code. Some improvement has been obtained by increasing the number of pixels processed by each thread, to an optimum 8 pixels per thread. The principle is to prefetch all pixel values involved in the computations performed by all threads of a block, including 8 pixels per thread plus the halo of radius $r$ (the radius of the convolution mask). As this obviously represents more values than the thread count in one block, some threads have to load more than one value. The general organization is reproduced in Figure \ref{fig:ShMem1} for $5\times 5$ mask and a $8\times 4$ thread block, while Listing \ref{lst:convoGeneSh1} gives the details of the implementation with its two distinct code blocks: preload in shared memory (Lines 20 to 42) and convolution computations (Lines 45 to 57). -Table \ref{tab:convoGeneSh1} details timing results of this implementation ($16\times 8$ threads/block), up to $13\times 13$ masks, that will serve as a reference in the next section, devoted to separable convolution. -\begin{table}[h] +Tables \ref{tab:convoGeneSh1} and \ref{tab:convoGeneSh2} detail timing results and throughput values of this implementation ($16\times 8$ threads/block), up to $13\times 13$ masks, that will serve as a reference in the next section, devoted to separable convolution. +\begin{table}[htbp] \centering {\normalsize \begin{tabular}{|c||r|r|r|r|r|r|} \hline -\shortstack{\textbf{Mask size$\rightarrow$}\\\textbf{Image size$\downarrow$}}&\textbf{3x3}&\textbf{5x5}&\textbf{7x7}&\textbf{9x9}&\textbf{11x11}&\textbf{13x13}\\\hline\hline +\shortstack{\textbf{Mask size}$\rightarrow$\\\textbf{Image size$\downarrow$}}&$\mathbf{3\times 3}$&$\mathbf{5\times 5}$&$\mathbf{7\times 7}$&$\mathbf{9\times 9}$&$\mathbf{11\times 11}$&$\mathbf{13\times 13}$\\\hline\hline $\mathbf{512\times 512}$ &0.040 &0.075 &0.141 &0.243&0.314&0.402\\\hline $\mathbf{1024\times 1024}$&0.141 &0.307 &0.524 &0.917&1.192&1.535\\\hline $\mathbf{2048\times 2048}$&0.543 &\bf 1.115&2.048 &3.598&4.678&6.037\\\hline $\mathbf{4096\times 4096}$&2.146 &4.364 &8.156 &14.341&18.652&24.020\\\hline \end{tabular} } -\caption{Performances, in milliseconds, of our generic 8 pixels per thread kernel using shared memory, run on a C2070 card.} +\caption{Performances, in milliseconds, of our generic 8 pixels per thread kernel using shared memory, run on a C2070 card. Data transfers duration are not included.} \label{tab:convoGeneSh1} \end{table} -\begin{table}[h] +\begin{table}[htbp] \centering {\normalsize \begin{tabular}{|c||r|r|r|r|r|r|} \hline -\shortstack{\textbf{Mask size$\rightarrow$}\\\textbf{Image size$\downarrow$}}&\textbf{3x3}&\textbf{5x5}&\textbf{7x7}&\textbf{9x9}&\textbf{11x11}&\textbf{13x13}\\\hline\hline +\shortstack{\textbf{Mask size}$\rightarrow$\\\textbf{Image size$\downarrow$}}&$\mathbf{3\times 3}$&$\mathbf{5\times 5}$&$\mathbf{7\times 7}$&$\mathbf{9\times 9}$&$\mathbf{11\times 11}$&$\mathbf{13\times 13}$\\\hline\hline $\mathbf{512\times 512}$ &1394 &1176 &907 &670&567&477\\\hline $\mathbf{1024\times 1024}$&1820 &1413 &1093 &776&644&532\\\hline $\mathbf{2048\times 2048}$&2023 &\bf 1586 &1172 &818&676&554\\\hline @@ -283,7 +288,7 @@ $\mathbf{4096\times 4096}$&2090 &1637 &1195 &830&684&561\\\hline \caption[Throughput values, in MegaPixel per second, of our generic 8 pixels per thread kernel using shared memory, run on a C2070 card.]{Throughput values, in MegaPixel per second, of our generic 8 pixels per thread kernel using shared memory, run on a C2070 card. Data transfer durations are those of Table \ref{tab:memcpy1}.} \label{tab:convoGeneSh2} \end{table} -\lstinputlisting[label={lst:convoGeneSh1},caption=CUDA kernel achieving a generic convolution operation after a preloading of data in shared memory.]{Chapters/chapter4/code/convoGeneSh1.cu} +\lstinputlisting[label={lst:convoGeneSh1},caption=CUDA kernel achieving a generic convolution operation after a preloading of data in shared memory]{Chapters/chapter4/code/convoGeneSh1.cu} \section{Separable convolution} A convolution operation is said separable when its masks $h$ is the product of 2 vectors $h_v$ and $h_h$, as is the case in the following example: @@ -292,45 +297,32 @@ $$h = h_v \times h_h = \begin{bmatrix}1\\2\\1\end{bmatrix} \times \begin{bmatrix -2&4&-2\\ -1&2&-1 \end{bmatrix}$$ -Such a mask allows to replace a generic 2-D convolution operation by two consecutive stages of a 1-D convolution operation: a vertical of mask $h_v$ and a horizontal of mask $h_h$. -This saves a lot of arithmetic operations, as a generic $n\times n$ convolution applied on a $H\times L$ image basically represents $H.L.n^2$ multiplications and as many additions, while two consecutive $n\times 1$ convolutions only represents $2.H.L.n$ of each, \textit{e.g} 60\% operations are saved per pixel of the image for a $5\times 5$ mask.\\ -However, beside reducing the operation count, performing a separable convolution also means writing an intermediate image into global memory. -CPU implementations of separable convolutions often use a single function to perform both 1-D convolution stages. To do so, this function reads the input image and actually ouputs the transposed filtered image. -Applying that principle to GPUs is not efficient, as outputting the transposed image means non-coalescent writes into global memory, generating severe performance loss. Hence the idea of developing two different kernels, one for each of both vertical and horizontal convolutions. - -Here, the use of Shared memory is the best choice, as there is no overlapping between neighbor windows and thus no possible optimization. -Moreover, to ensure efficiency, it is important to read the input image from texture memory, which implies an internal GPU data copy between both 1-D convolution stages. -Which, even if it is faster than CPU/GPU data transfer, makes separable convolutions slower than generic convolutions for small mask sizes. On C2070, the lower limit is $7\times 7$ pixels ($9\times 9$ for $512\times 512$ images). - -Both vertical and horizontal kernels feature similar runtimes: Table \ref{tab:convoSepSh1} only contains their average execution time, including the internal data copy stage, while Table \ref{tab:convoSepSh2} shows the achieved global throughput values. Timings of the data copy stage are given in Table \ref{tab:cpyToArray}. -Listings \ref{lst:convoSepShV} and \ref{lst:convoSepShH} detail the implementation of both 1-D kernels, while Listing \ref{lst:convoSepSh} shows how to use them in addition with the data copy function in order to achieve a whole separable convolution. The shared memory size is dynamically passed as a parameter at kernel call time. Its expression is given in the comment line before its declaration. -\begin{table}[h] -\centering -{\normalsize -\begin{tabular}{|c||r|} -\hline -\textbf{Image size}&\textbf{C2070}\\\hline\hline -$\mathbf{512\times 512}$ &0.029 \\\hline -$\mathbf{1024\times 1024}$&0.101 \\\hline -$\mathbf{2048\times 2048}$&0.387 \\\hline -$\mathbf{4096\times 4096}$&1.533 \\\hline -\end{tabular} -} -\caption{Time cost of data copy between the vertical and the horizontal 1-D convolution stages, on a C2070 cards (in milliseconds).} -\label{tab:cpyToArray} -\end{table} +Such a mask allows us to replace a generic 2D convolution operation by two consecutive stages of a 1D convolution operation: a vertical of mask $h_v$ and a horizontal of mask $h_h$. +This saves a lot of arithmetic operations, as a generic $n\times n$ convolution applied on an $H\times L$ image basically represents $HLn^2$ multiplications and as many additions, while two consecutive $n\times 1$ convolutions represents only $2HLn$ of each, e.g., 60\% operations are saved per pixel of the image for a $5\times 5$ mask. + +However, besides reducing the operation count, performing a separable convolution also means writing an intermediate image into global memory. +CPU implementations of separable convolutions often use a single function to perform both 1D convolution stages. To do so, this function reads the input image and actually ouputs the transposed filtered image. +Applying this principle to GPUs is not efficient, as outputting the transposed image means non coalescent writes into global memory, generating severe performance loss. Hence the idea of developing two different kernels, one for each of the vertical and horizontal convolutions. + +Here, the use of shared memory is the best choice, as there is no overlapping between neighbor windows and thus no possible optimization. +Moreover, to ensure efficiency, it is important to read the input image from texture memory, which implies an internal GPU data copy between both 1D convolution stages. +This, even if it is faster than CPU/GPU data transfer, makes separable convolutions slower than generic convolutions for small mask sizes. On C2070, the lower limit is $7\times 7$ pixels ($9\times 9$ for $512\times 512$ images). + +Both vertical and horizontal kernels feature similar runtimes: Table \ref{tab:convoSepSh1} contains only their average execution time, including the internal data copy stage, while Table \ref{tab:convoSepSh2} shows the achieved global throughput values. Timings of the data copy stage are given in Table \ref{tab:cpyToArray}. +Listings \ref{lst:convoSepShV} and \ref{lst:convoSepShH} detail the implementation of both 1D kernels, while Listing \ref{lst:convoSepSh} shows how to use them in addition with the data copy function in order to achieve a whole separable convolution. The shared memory size is dynamically passed as a parameter at kernel call time. Its expression is given in both Listings (\ref{lst:convoSepShV} and \ref{lst:convoSepShH}), in the comment lines before its declaration. + \begin{table}[h] \centering {\normalsize \begin{tabular}{|c||r|r|r|r|r|r|} \hline -\shortstack{\textbf{Mask size$\rightarrow$}\\\textbf{Image size$\downarrow$}}&\textbf{3x3}&\textbf{5x5}&\textbf{7x7}&\textbf{9x9}&\textbf{11x11}&\textbf{13x13}\\\hline\hline +\shortstack{\textbf{Mask size}$\rightarrow$\\\textbf{Image size$\downarrow$}}&$\mathbf{3\times 3}$&$\mathbf{5\times 5}$&$\mathbf{7\times 7}$&$\mathbf{9\times 9}$&$\mathbf{11\times 11}$&$\mathbf{13\times 13}$\\\hline\hline $\mathbf{512\times 512}$ &0.080 &0.087 &0.095 &\bf 0.108&\bf 0.115&\bf 0.126\\\hline $\mathbf{1024\times 1024}$&0.306 &0.333 &\bf 0.333 &\bf 0.378&\bf 0.404&\bf 0.468\\\hline $\mathbf{2048\times 2048}$&1.094 &1.191 &\bf 1.260 &\bf 1.444&\bf 1.545&\bf 1.722\\\hline $\mathbf{4096\times 4096}$&4.262 &4.631 &\bf 5.000 &\bf 5.676&\bf 6.105&\bf 6.736\\\hline \end{tabular}} -\caption[Performances, in milliseconds, of our generic 8 pixels per thread 1-D convolution kernels using shared memory, run on a C2070 card.]{Performances, in milliseconds, of our generic 8 pixels per thread 1-D convolution kernels using shared memory, run on a C2070 card. Timings include data copy. Bold values correspond to situations where separable-convolution kernels run faster than non separable ones.} +\caption[Performances, in milliseconds, of our generic 8 pixels per thread 1D convolution kernels using shared memory, run on a C2070 card.]{Performances, in milliseconds, of our generic 8 pixels per thread 1D convolution kernels using shared memory, run on a C2070 card. Timings include data copy. Bold values correspond to situations where separable-convolution kernels run faster than non separable ones.} \label{tab:convoSepSh1} \end{table} \begin{table}[h] @@ -338,28 +330,42 @@ $\mathbf{4096\times 4096}$&4.262 &4.631 &\bf 5.000 &\bf 5.676&\bf 6.105&\bf 6.73 {\normalsize \begin{tabular}{|c||r|r|r|r|r|r|} \hline -\shortstack{\textbf{Mask size$\rightarrow$}\\\textbf{Image size$\downarrow$}}&\textbf{3x3}&\textbf{5x5}&\textbf{7x7}&\textbf{9x9}&\textbf{11x11}&\textbf{13x13}\\\hline\hline +\shortstack{\textbf{Mask size}$\rightarrow$\\\textbf{Image size$\downarrow$}}&$\mathbf{3\times 3}$&$\mathbf{5\times 5}$&$\mathbf{7\times 7}$&$\mathbf{9\times 9}$&$\mathbf{11\times 11}$&$\mathbf{13\times 13}$\\\hline\hline $\mathbf{512\times 512}$ &1150 &1116 &1079 &\bf 1024&\bf 997 &\bf 957\\\hline $\mathbf{1024\times 1024}$&1415 &1365 &\bf 1365 &\bf 1290&\bf 1250&\bf 1169\\\hline $\mathbf{2048\times 2048}$&1598 &1541 &\bf 1503 &\bf 1410&\bf 1364&\bf 1290\\\hline $\mathbf{4096\times 4096}$&1654 &1596 &\bf 1542 &\bf 1452&\bf 1400&\bf 1330\\\hline \end{tabular} } -\caption[Throughput values, in MegaPixel per second, of our generic 8 pixels per thread 1-D convolution kernel using shared memory, run on a C2070 card.]{Throughput values, in MegaPixel per second, of our generic 8 pixels per thread 1-D convolution kernel using shared memory, run on a C2070 card. Data transfer durations are those of Table \ref{tab:memcpy1}.} +\caption[Throughput values, in megapixel per second, of our generic 8 pixels per thread 1D convolution kernel using shared memory, run on a C2070 card.]{Throughput values, in MegaPixel per second, of our generic 8 pixels per thread 1D convolution kernel using shared memory, run on a C2070 card. Bold values correspond to situations where separable-convolution kernels run faster than non separable ones (data transfer durations are those of Table \ref{tab:memcpy1}).} \label{tab:convoSepSh2} \end{table} - -\lstinputlisting[label={lst:convoSepSh},caption=data copy between the calls to 1-D convolution kernels achieving a 2-D separable convolution operation.]{Chapters/chapter4/code/convoSepSh.cu} -\lstinputlisting[label={lst:convoSepShV},caption=CUDA kernel achieving a horizontal 1-D convolution operation after a preloading \index{Prefetching} of data in shared memory.]{Chapters/chapter4/code/convoSepShV.cu} -\lstinputlisting[label={lst:convoSepShH},caption=CUDA kernel achieving a vertical 1-D convolution operation after a preloading of data in shared memory.]{Chapters/chapter4/code/convoSepShH.cu} +\begin{table}[h] +\centering +{\normalsize +\begin{tabular}{|c||r|} +\hline +\textbf{Image size}&\textbf{C2070}\\\hline\hline +$\mathbf{512\times 512}$ &0.029 \\\hline +$\mathbf{1024\times 1024}$&0.101 \\\hline +$\mathbf{2048\times 2048}$&0.387 \\\hline +$\mathbf{4096\times 4096}$&1.533 \\\hline +\end{tabular} +} +\caption{Time cost of data copy between the vertical and the horizontal 1D convolution stages, on a C2070 cards (in milliseconds).} +\label{tab:cpyToArray} +\end{table} +\lstinputlisting[label={lst:convoSepSh},caption=data copy between the calls to 1D convolution kernels achieving a 2D separable convolution operation]{Chapters/chapter4/code/convoSepSh.cu} +\lstinputlisting[label={lst:convoSepShV},caption=CUDA kernel achieving a horizontal 1D convolution operation after a preloading \index{Prefetching} of data into shared memory]{Chapters/chapter4/code/convoSepShV.cu} +\lstinputlisting[label={lst:convoSepShH},caption=CUDA kernel achieving a vertical 1D convolution operation after a preloading of data into shared memory]{Chapters/chapter4/code/convoSepShH.cu} \section{Conclusion} -Extensively detailing the various techniques that may be applied when designing a median or a convolution operation on GPU has enabled us determine that: +Extensively detailing the various techniques that may be applied when designing a median or a convolution operation on GPU has enabled us determine that \begin{itemize} -\item the use of registers with direct data fetching from texture often allows kernels to run faster than those which use the more conventionnal way of prefetching data from texture memory and storing them into shared memory. -\item increasing the pixel count processed by each thread brings important speedups. In this case, if neighboring windows overlap, optimized direct data fetching from texture will likely outperform the shared memory prefetching technique. That is the case for generic convolution kernels. -\item coding such optimized data fetching is not straightforward. Consequently, we are planning to provide a kernel code generator that will make our kernels more accessible by GPU users. +\item the use of registers with direct data fetching from texture often allows kernels to run faster than those which use the more conventionnal way of prefetching data from texture memory and storing them in shared memory. +\item increasing the pixel count processed by each thread brings important speedups. In this case, if neighboring windows overlap, optimized direct data fetching from texture will likely outperform the shared memory prefetching technique. This is the case for generic convolution kernels. +\item coding such optimized data fetching is not straightforward. Consequently, we are currently developing a kernel code generator that will make our kernels more accessible by GPU users. \end{itemize} -The presented kernels, optimized for a C2070 card, achieve up to 2138~Mpix/s including data transfers, which comes close to the absolute maximum throughput value allowed by the Fermi architecture. The next GPU generation (Kepler) may allow us not only to benefit from new dynamic parallelism capability to increase kernel paralelism level, but also to take advantage of an increase of the register count allowed per thread block which would allow us, for example, to extend our register-only median filter technique to larger mask sizes. +The presented kernels, optimized for a C2070 card, achieve up to 2138~MP/s including data transfers, which comes close to the absolute maximum throughput value allowed by the Fermi architecture. The next GPU generation (called Kepler) may allow us not only to benefit from new dynamic parallelism capability to increase kernel paralelism level, but also to take advantage of an increase in the register count allowed per thread block which would allow us, for example, to extend our register-only median filter technique to larger mask sizes. \putbib[Chapters/chapter4/biblio4] -- 2.39.5