Convolution in the spatial domain is calculated per pixel by multiplying corresponding values in the filter and the data set and adding them together, then dividing by the number of elements in the filter. See Figure \ref{convolute} for an illustration. This is done per point in the data set. It is a way to calculate how all neighboring pixels effect the pixel one is looking at now given a mathematical distribution. One cannot perform convolution in place because this would effect the results for the neighboring pixel when calculated later. Therefore a result table must be used to contain the updated values. 

\begin{figure}[H]
	\centering
	\includegraphics[width=15cm]{report/method/convolute.PNG}
	\caption{Image illustrating the different pieces used in convolution}
	\label{convolute}
\end{figure}

Having a result table is an issue for large data sets because this means that one can only use half the memory available to read from disk and the other half for the result table. Another limitation as to how much data that can be read at a time is that the operating system usually uses some of the memory and it may even vary depending on the processes running on the machine. The memory available in this implementation is 8 GB. Where 1.5 GB is used for the operating system, that is why only a maximum of 3GB  data is read at a time, which correspond to 6 GB allocated in memory because of the duplication of the table to calculate results. 

When reading several blocks of data to be convoluted it is crucial that one accounts for the border values that should be read as well to avoid border effects between the blocks read. The size of the border is dependent on the size of the filter since when the outer most point is to be filtered then half the filter, in all dimensions, will be outside the frame of the data. This is why one must have a boarder along the whole data set as well as between all the blocks of data. This means that there is a boarder along all edges of the data set and between each block, and that the border size is regulated by the filters size. 

In the case where the filter to be convoluted is separable, then there is no need to optimize memory if the filter is kept constantly in the L1 cache then just normal traversal through each dimension would be optimal with few cache misses. When it comes to non-separable filters in two or three dimensions then one must jump in memory to reach the next row of data, which means that the pre-fetcher of the controller, using the SSE4a instructions \cite{amd}, should retrieve the next row into the cache to perform the calculations. The pre-fetcher is able to get the next row as long as the stride is constant for each read from memory because it will be able to understand the pattern. In this case it is always constant, meaning that the rows needed are able to be pre-fetched without any problem. Cache misses can be checked using a computation profiler \cite{amd}, which will be shown later in the result chapter. The filter size also regulates the amount of computation performed per pixel. Since as mentioned one is to traverse the filter size and perform calculations using all the values in the filter array. This means given that one has a 5x5x5 filter one would perform 125 multiplications and additions per pixel to in the cube. A 3x3x3 filter would give 27 multiplication and additions, and so on.

\begin{figure}[H]
	\centering
	\includegraphics[width=15cm]{report/method/overlap.PNG}
	\caption{image illustrating overlap in memory between calculations of neighboring pixels}
	\label{memory}
\end{figure}

If one is to optimize for this type of data then one should do as many calculations as possible while data is in the cache. See Figure \ref{memory} to see how data from one pixel overlap with data for the calculation to the next pixel. This means that a lot of the values needed in the next calculation are already in the cache, but once one traverses to the end in the x direction then the data that will be needed for the next calculations have no overlap from the previous. Such that all the values in the cache need to be changed. Since all data is aligned and all jumps in memory have similar strides, this should result in the pre-fetcher being able to optimize against cache misses because the strides are constant. This can be shown in the profiler where this resulted in a cache miss percentage close to 0 \%. This shows that there is no more a need to optimize for memory and cache misses beyond this point.
\newline

\lstset{frame=single,tabsize=2, language=Java, basicstyle=\footnotesize, numberstyle=\footnotesize, numbers=left, captionpos=b, breaklines=true, title={C code for three dimentional convolution}}
\begin{lstlisting}
float counter = len*len*len;
float imagevalue;
//performing convolution
for (int i = 0; i < z; i++) {
	for (int j = 0; j < y; j++) {
		for (int k = 0; k < x; k++) {
			imagevalue = 0;
			for (int l = 0; l < len; l++) {
				for (int m = 0; m < len; m++) {
					for (int n = 0; n < len; n++) {
						imagevalue += token[(len+x)*(len+y)*(i+l) + (len+x)*(j+m) + (k + n)] * filter[(len*len)*l + (len)*m + n];
					}
				}
			}
			data[y*x*i+ x*j + k] = imagevalue / counter;
		}
	}
}
\end{lstlisting}
