\documentclass[12pt,a4paper,twoside]{report}

\usepackage[latin1]{inputenc}
\usepackage[inner=2.5cm,outer=3.5cm,bottom=3cm,top=2.5cm,pdftex]{geometry}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage{rotating}
\usepackage{varioref}
\usepackage{fancyhdr}
\usepackage[page]{appendix}
\usepackage[colorlinks=true,linkcolor=black,citecolor=black,urlcolor=black]{hyperref}
%\usepackage[pdfborder=0 0 0]{hyperref}
\usepackage{paralist}
\usepackage{float}
\usepackage{subfigure}
\usepackage{titlesec}
\usepackage[style=super,header=plain,]{glossary}
\usepackage{tocbibind}     % for bibliography in TOC
\usepackage{url}           % for URL formatting in references
\usepackage{enumitem}
\usepackage{longtable}
\usepackage{listings}
\usepackage[all]{xy}
\usepackage{parskip}
\usepackage{listings}
\usepackage{pdfpages}

% Fix for twoside vertical stretch problem
% See http://www.latex-community.org/viewtopic.php?t=1547
\raggedbottom


% Style our chapter headings.
\titlespacing{\chapter}{0pt}{0pt}{40pt}
\titleformat{\chapter}[display]
 {\bfseries\Large}
 {\filleft\MakeUppercase{\chaptertitlename} \Huge\thechapter}
 {4ex}
 {\titlerule
  \vspace{2ex}%
  \filright}
 [\vspace{2ex}%
 \titlerule]

%make glossary
\makeglossary
% compile report.tex, run the cmd below, compile again. 
% makeindex report.glo -s report.ist -t report.glg -o report.gls

\vrefwarning

\begin{document}


% Plain, roman numbering with no fancy headers.

%\title{Tekna 2.0 Portal}
%\author{Group 8}

%\maketitle

\pagenumbering{roman}
\includepdf{frontpage.pdf}
\cleardoublepage
\pagestyle{plain}


\setcounter{tocdepth}{2}
\pagebreak

% TODO Introduction
\chapter*{Problem Description}
\addcontentsline{toc}{chapter}{Problem Description}

In Petrel, Schlumberger's seismic software, one often comes across large seismic cubes that need to be filtered in order to generate clearer images. The seismic cubes are viewed from three dimensions, implying that one must filter in all three dimensions as well. However, this filtering is very computationally demanding and thus uses a lot of computational resources. This project's goal is to implement a Gaussian filter on a large three dimensional data set on the GPU using NVIDIA CUDA to off-load the CPU. A CPU version will also be developed for comparison and analysis. Since the size of the data to be transferred to the GPU memory is quite large, the calculations need to be performed on sub cubes. This implies that one must account for border data between cubes to avoid an edge effect. The implementations developed will be benchmarked and compared to evaluate performance gains. 

\cleardoublepage
\chapter*{Abstract}
\addcontentsline{toc}{chapter}{Abstract}

In the petroleum and gas industry, one of the main foci is using seismic processing to find new oil and gas reservoirs. Recordings of seismic waves can be used to create images representing the surface of the earth. To do so one has to filter the data collected. One of the methods for filtering this data is convolution in the spatial domain. Which is done in three dimensions (3D) because of the 3D nature of the data collected. The data collected can be of surfaces over several kilometers in length and are therefore very large is size.

This project focuses on implementing a 3D convolution algorithm on modern CPUs and GPUs with non-separable filters for large data sets, in the spatial domain. Our results demonstrate that the filtering mask should be placed in constant memory rather than shared memory because there is an overhead assosiated with the use of shared memory per kernel launch. The data in constant memory must be read coalecsed for it to be efficient. Shared memory should not to be used for the filtered data either due to the lack of communication between the threads in the convolution kernel. Again, the overhead of reading into shared memory only slows down the process. To compare our results, implementations on the CPU were performed in C. The platforms tested on are both a uni-core CPU and a quad-core CPU, as well as a single GPU and a system with up to 4 GPUs. The CPU used is a AMD phenom x4, whereas the GPUs used are the NVIDIA Tesla c1060 and NVIDIA Tesla s1070. Our work includes figuring out how to process large amounts of data most efficiently on both the CPU and GPU with the use of different blocking methods when accessing the disk.

Our results also show that the I/O time, which one would expect to be a bottleneck, is only 1-2\% of the total execution time on a single CPU. This means that convolution is a computationally demanding task, but fortunatly a very parallelizable one. Our results indicate that compared to a single core a speedup of 3.57 is achieved on the Phenom x4 , a speedup of 17 is achieved on the Tesla c1060 (single GPU)  and a speedup of 62 is achieved on the Tesla s1070 (4 GPUs). This led to the computation percentage being reduced by 5\%, 25\% and 90\%, respectively for the three platforms. Further work regarding optimizations should hence focus on I/O.

\cleardoublepage
\chapter*{Acknowledgement}
\addcontentsline{toc}{chapter}{Acknowledgement}
\input{report/ack}

\pagebreak


\tableofcontents
\listoftables
\listoffigures


% Fancy headers, chapter on the left of even pages, section on the right
% of odd pages.
\pagestyle{fancy}
\fancyhead{}
\fancyhead[LE]{\leftmark}
\fancyhead[RO]{\rightmark}

\fancyhead[RE]{\includegraphics[width=2.0cm]{report/fig-headerlogo2}}
%\fancyhead[LO]{\includegraphics[width=2.5cm]{report/fig-headerlogo}}



% Parts
\cleardoublepage
\ 
\newpage
\ 
\newpage

\pagenumbering{arabic}
\setcounter{page}{1}
\chapter{Introduction}
	
		\input{report/Intro/motivation}
	\section{Project Goals}
		\input{report/Intro/projectgoal}
	\section{Project Contributions}
		\input{report/Intro/projectcontribution}
	\section{Outline}
		\input{report/Intro/outline}


\cleardoublepage

\chapter{Background and Related Work}
\input{report/background/intro}
	\section{Related Work}
		\input{report/related/related}
	\newpage
	\section{Spatial Filtering}
		\input{report/background/spatial}
	\section{Spatial Filter Masks and The Gaussian Filter}
		\input{report/background/gaussian}
	\section{Gaussian Smoothing in Seismic Processing}
		\input{report/background/seismic}
	\section{Parallel Computing}
	\label{parallelsection} 
		\input{report/background/parallel}
	\section{OpenMP and Multithreading}
		\input{report/background/openmp}
	\section{GPU and CPU Architectural Features}
		\input{report/background/GPU}
	\section{CUDA Programming Model}
		\input{report/background/CUDA}
%	\section{3D-Dataset and Sub-Cubing}
%		\input{report/background/3dData}

\cleardoublepage

\chapter{3D Filter Implementations}
\input{report/method/intro}
	
	\section{Hardware and Software Used}
		\input{report/results/hardsoft}
	\section{Programming Framework}
		\input{report/method/framework}	
	\section{3D Gaussian Filter Implementation}
		\input{report/method/filter}
	\section{Reading from and Writing to Disk}
		\input{report/method/io}
	\section{Convolution Implementation on Uni-Core CPU}
		\input{report/method/single}
	\section{Convolution Implementation on Quad-Core CPU}
		\input{report/method/quad}
	\section{GPU Implementation in CUDA}
		\input{report/method/gpu}
	\section{Multi-GPU Implementation in CUDA}
		\input{report/method/multigpu}
	\section{Testing and Benchmarking implementation}
	\label{testing}
		\input{report/method/test}
		

\cleardoublepage

\chapter{Results and Discussion of Benchmarkes }
\input{report/results/intro}
\input{report/discussion/intro}

	\section{I/O and Blocking Results}
		\input{report/results/block}
	\section{I/O and Blocking Discussion}
		\input{report/discussion/IO}
	\section{Visual results of Convolution}
		\input{report/results/visual}
	\section{AMD and CUDA profiler Results}
		\input{report/results/profiler}
	\section{Benchmarked Convolution Results}
		\input{report/results/single}
	\newpage
	\section{Convolution and Optimization Discussion}
		\input{report/discussion/parallel}
	
\cleardoublepage

\chapter{Conclusions and Future Work}

In the case of processing large seismic data sets, there is always a concern of how to efficiently transfer the data in sub blocks from disk to buffer and back. However when running on a single CPU core, our results showed that I/O time was limited to only 1\% of the execution time.  This means that 3D convolution studied here in this report are computationally demanding. However, convolution is very parallelizable since the calculations in neighboring pixels are very independent. Our results showed that a speedup of 3.57 was gained when running on a quad-core platform, which is close to the theoretical speedup of 4. 

Our results showed that the GPU could accelerate the task significantly. The results showed that running the application on a GPU resulted in a speedup of about 17. The main limitations were the bottleneck of having to transfer the data from system buffer to the global memory of the GPU and the fact that the convolution kernel used 22 registers for computations and thereby only a maximum of 63\% occupancy was possible. Nevertheless, by having used the GPU we showed that it was possible to reduce the execution time from hours to minutes even for larger sets. We discovered that this was achieved by using constant memory for the filtering mask and global memory for the dataset, and both were accessed coalecsed. Shared memory was not used because it introduced an overhead per kernel launch, which was avoided by using constant memory.

Our results also showed that convolution was easy to distribute across several platforms. When using the Tesla s1070, which is similar to using 4 seperate GPUs, the problem scaled nearly perfectly. Comparing our results of running on a single GPU to running on four achieved a speedup of 3.7, which is very close to the theoretical four times speedup. This was accomplished by pipelining the executions on the GPUs such that they hide each others computation and I/O time. The speedup gained from this compared to the uni-core implementation is 62 with a computation time of only 10\%. Hence the major bottleneck now has become the time used reading from disk.

\newpage
\section{Future Work}

In this project, the focus has been on using non separable filters such that one must filter in all three dimensions per pixel. A suggestion for further work in this field is to explore what effects a separable filter would  have on speedup and performance.

Another focus in this project has been at looking into filtering in the spatial domain. Therefore an improvement of further work could look into using the fourier domain

When maximizing performance on the GPU the use of constant memory was used in this implementation, for reasons given in the discussion. An interesting aspect for further work would be using the shared memory instead and compare performance between the two. Or even the use of NVIDIAs new GPU architecture Fermi where one can use caches.

As the performance is optimized the computation time is decreased and I/O is dominant again. This is seen when using the Tesla s1070 on large data sets where the computation time is only 10\%, which means that 90\% of the time is used on I/O. Further work here would involve further optimization of I/O maybe even experimenting with parallel I/O.

All code for the GPU is written in CUDA. Another option would be using OpenCL. This way one could compare using NVIDIA hardware to the use of AMD hardware. One can also compare the performance obtaind by simply changing the programming platform to OpenCL as well.


\renewcommand{\bibname}{Bibliography and References}
\bibliographystyle{plain}
\bibliography{references}
\nocite{*}


\cleardoublepage

%Appendices
\appendix
\addcontentsline{toc}{chapter}{\appendixtocname}
\chapter{Benchmarking Tables}
\label{resulttables}
\includepdf[pages=1-8]{results.pdf}



%glossary
%\printglossary
%\addcontentsline{toc}{chapter}{Glossary}

\end{document}