X-Git-Url: https://vgcfreebox.myrthtech.pt/gitweb/ue-pp-squarematrixparallelisation.git/blobdiff_plain/e1bc809d28992e9ab3b46078a6bd6de4618c1961..cb4d5357f1943a94fe71443c539d10553ebab83c:/MatrixParallelPrograming.tex?ds=sidebyside

diff --git a/MatrixParallelPrograming.tex b/MatrixParallelPrograming.tex
index 55dd9f5..ee3713d 100644
--- a/MatrixParallelPrograming.tex
+++ b/MatrixParallelPrograming.tex
@@ -44,7 +44,7 @@
 \fancyhf{} 
 
 \lhead{ProgramaÃ§Ã£o Paralela}
-\rhead{Matrix Search Parallelization}
+\rhead{Matrix Search Parallelisation}
 \fancypagestyle{noheadrule}{
   \fancyhf{}
   \renewcommand{\headrulewidth}{0pt}
@@ -53,7 +53,7 @@
 \rfoot{\thepage}
 
 
-\title{Matrix Search Parallelization}
+\title{Matrix Search Parallelisation}
 \author{Vitor GonÃ§alo Costa, m70323}
 \date{Universidade de Ãvora\\ \today}
 \begin{document}
@@ -114,7 +114,7 @@ With the current implementation of our program, the global variable hv, used to
 	\includegraphics[width=0.6\textwidth]{imagens/matrixsearchsequencial-02.png}  
 \end{figure}
 
-From the previous image we can be sure the 3rd task is the one to parallelise. We should also notice that the changes performed to the program actually increase it's time of execution, the view operation performed on this type of variable is more resource consuming than when performed on a variable of type integer. This can be proved by analysing the time for each task on the first version of our program, populating the matrix toke around 4.5 seconds while the search matrix task toke less than 4 seconds for 40k rows. The wall-clock time of the above figure is 18,931 seconds, this representes the real time a users waits for a program to finish,
+From the previous image we can be sure the 3rd task is the one to parallelise. We should also notice that the changes performed to the program actually increase it's time of execution, the view operation performed on this type of variable is more resource consuming than when performed on a variable of type integer. This can be proved by analysing the time for each task on the first version of our program, initialising the matrix toke around 4.5 seconds while the search matrix task toke less than 4 seconds for 40k rows. The wall-clock time of the above figure is 18,931 seconds, this representes the real time a users waits for a program to finish,
 
 \subsection*{Columns Split}
 Because the matrix in the spotlight is a square one, at first approach, one might think it doesn't really matter if a split is performed by columns or rows, but it does. Since C approaches 2D arrays per row, by the time the cpu access the 32 or 64 bytes of the matrix memory stored in ram to make it available closer, at LP2 or LP3, it brings the closest row values also, making it faster to loop though rows instead of columns. 
@@ -184,7 +184,7 @@ Finally, the \textbf{scalability} of a program measures how well a parallel prog
 \label{wall-cpu time of parallel strategies}
 \end{table}%
 
-Combining values from tables 1 and 2, and using the formulas presented before we can compute the performance metrics for both strategies:
+Combining values from tables 1 and 2, and using the formulas presented before, we can compute the performance metrics for both strategies:
 
 \begin{table}[htp]
 \begin{center}
@@ -207,26 +207,38 @@ The metric scalability can be divided in two: \underline{strong scaling}, when t
 
 \begin{figure}[h]
 	\centering
-	\includegraphics[width=0.6\textwidth]{imagens/matrixsearchsequencial-06.png}
+	\includegraphics[width=0.8\textwidth]{imagens/matrixsearchsequencial-06.png}
 	\caption{Weak scalability evaluation from 1 to 8 threads.}
 \end{figure}
 
 Since there wasn't a big gain when parallelising the search task we could either try to develop a new parallel strategy for the search task or parallelise the matrix initialisation instead. 
 
 \section*{Improving performance}
-tbd
+We start by updating the function parallel\_search\_cols() to have a local variable to store the highest value found by the thread and perform only one comparison to the atomic variable. This change alone makes the program finishes with a mean value of 8.192 seconds (using 8 threads for a 40k rows and columns matrix), comparing with the values on tables 1 and 2 we can validate the benefit of this change by computing $efficiency = \frac{1.1335}{8} = 14.16 \%$.
 
-\section*{Conclusions}
-Modern CPUs can spawn thousands of virtual threads to perform calculations.\\
+The second task, matrix initialisation, simulates the sequential section of a program in this study, but we could try to parallelise this operation has an extra exercise. The function init\_parallel\_matrix() was defined in order to populate segments of the matrix by different threads with a similar algorithm used for columns search. With this implementations,  the program now takes 4,821 seconds of wall-clock time with 4 threads. The following metrics were obtained:
+
+
+\begin{figure}[h]
+\begin{minipage}[c]{0.45\textwidth}
+	\begin{itemize}
+		\item speedup = 1,9262
+		\item efficiency = 48,15\%
+	\end{itemize}	
+\end{minipage}
+\begin{minipage}[c]{0.5\textwidth}
+\includegraphics[width=0.925\textwidth]{imagens/matrixsearchsequencial-07.png}
+\end{minipage}
+\end{figure}
 
-The action of populating the matrix could also update the value of global variable hv instead of the 3rd task. Search the matrix could have a local variable to store the highest value found and compare with the global var hv at the end.\\
+With the previous parallel implementations we finish this study with a parallel version of our initial sequential program that takes almost half of the time to be executed with four threads on the introduced machine. 
 
-The clock() function from time.h library is useless to compute wall-clock time and therefore should be ignored on metrics evaluations.
+\section*{Conclusions}
+This study revealed a few characteristics of modern cpu behaviours. Apart from being able to spawn thousands of virtual threads to perform calculations, way more than the expected, the framework they use can also predict and make computations easy. On the last experiment of parallelising both tasks, the program takes very similar total cpu time executing them, less than 9 seconds, or less than 2,25 seconds each thread, if we compare with values presented previously for the 2nd and 3rd task before parallelisation, considerably away from each other, we can almost argue that the search task benefits from the cache being 'warmed' by the preceding initialisation task.
 
+Parallelising a simple search algorithm is heavily influenced by memory access patterns and synchronisation overhead. While modern cpus can spawn multiple threads, the transition from sequential to parallel is not always linear. Our initial attempt using atomic variables showed that high contention can actually degrade performance. By implementing local thread variables, we achieved a speedup of 1.13x, and pre-parallelisation of matrix initialisation improved it to almost 2x using less resources.
 
-TODO:
-- strategy to split and continue threads;
-- evaluate strong/weak scalability with plot per number of threads 
+As a last conclusion from the study performed, although we focused on a column-based decomposition, performance data suggests that a row-wise partitioning strategy (horizontal striping) would likely yield superior results. Since C stores multi-dimensional arrays in row-major order, a thread processing a horizontal stripe accesses contiguous memory addresses. This maximizes spatial locality, allowing the CPU to effectively utilize its pre-fetchers and L1/L2 caches. By contrast, column-wise access frequently triggers 'cache misses,' as the CPU must jump across large memory strides to reach the next element in a column. Future iterations of this program should prioritize row-based decomposition to minimize memory latency and further improve the Speedup and Efficiency metrics
 
 
 \end{document}
\ No newline at end of file
