best speedup and efficiency achieved

diff --git a/ImprovedParallelMatricSearch.c b/ImprovedParallelMatricSearch.c
index 0df0ba1a6021e876f7e99027d1b109f04f4ffbcd..b3853841200067c140aafebbe438e504158dbb55 100644 (file)
--- a/ImprovedParallelMatricSearch.c
+++ b/ImprovedParallelMatricSearch.c
@@ -5,7 +5,7 @@
 
 const int m_rows = 40000;
 const int m_cols = 40000;
 
 const int m_rows = 40000;
 const int m_cols = 40000;

-const int threads_to_use = 8;
+const int threads_to_use = 4;

 
 _Atomic int hv = 0;
 int **matrix;
 
 _Atomic int hv = 0;
 int **matrix;


@@ -15,6 +15,16 @@ typedef struct{
   int end;
 } thread_args;
 
   int end;
 } thread_args;
 

+void* parallel_populate_matrix(void *arg){
+  thread_args *args = (thread_args *)arg;
+  for(int r = 0; r < m_rows; r++){
+      for(int c = args->start; c < args->end;c++){
+          matrix[r][c] = r*m_cols+c;
+      }
+  }
+  return NULL;
+}
+

 void* parallel_search_cols(void *arg){
   thread_args *args = (thread_args *)arg;
   int local_hv = 0;
 void* parallel_search_cols(void *arg){
   thread_args *args = (thread_args *)arg;
   int local_hv = 0;


@@ -63,14 +73,40 @@ void run_parallel_search(int num_threads) {
     free(args);
 }
 
     free(args);
 }
 

-void init_parallel_matrix(int num_threads){
-  for(int r = 0; r < m_rows; r++){  
-    for(int c = 0; c < m_cols; c++){
-      matrix[r][c] = r*m_cols+c;
+void init_parallel_matrix(int *data,int num_threads){
+    pthread_t *threads = malloc(num_threads * sizeof(pthread_t));
+    thread_args *args = malloc(num_threads * sizeof(thread_args));
+    if (threads == NULL || args == NULL) {
+        perror("Failed to allocate memory for threads");
+        exit(1);

     }
     }

-  }
+    
+    for(int r = 0; r<m_rows;r++){
+      matrix[r] = data + r * m_cols;
+    }
+
+    int chunk_size = m_cols / num_threads;
+    for (int i = 0; i < num_threads; i++) {
+          args[i].start = i * chunk_size;
+          if (i == num_threads - 1) {
+              args[i].end = m_cols;
+          } else {
+              args[i].end = (i + 1) * chunk_size;
+          }
+          if (pthread_create(&threads[i], NULL, &parallel_populate_matrix, &args[i]) != 0) {
+              perror("Failed to create thread");
+              exit(1);
+          }
+      }
+    
+      for (int i = 0; i < num_threads; i++) {
+          pthread_join(threads[i], NULL);
+      }
+      free(threads);
+      free(args);

 }
 
 }
 

+

 int main(void){
   printf("1st --> Allocate memory\n");
   clock_t t_t1; t_t1 = clock();
 int main(void){
   printf("1st --> Allocate memory\n");
   clock_t t_t1; t_t1 = clock();


@@ -93,10 +129,7 @@ int main(void){
 
   printf("2nd --> Populate the matrix\n");
   clock_t t_t2; t_t2 = clock();
 
   printf("2nd --> Populate the matrix\n");
   clock_t t_t2; t_t2 = clock();

-  for(int r = 0; r<m_rows;r++){
-    matrix[r] = data + r * m_cols;
-  }
-  init_parallel_matrix(threads_to_use);
+  init_parallel_matrix(data, threads_to_use);

   t_t2 = clock() - t_t2;
   double t2_ttaken = ((double)t_t2)/CLOCKS_PER_SEC; 
   printf(" %f sec\n",t2_ttaken);  
   t_t2 = clock() - t_t2;
   double t2_ttaken = ((double)t_t2)/CLOCKS_PER_SEC; 
   printf(" %f sec\n",t2_ttaken);  

diff --git a/MatrixParallelPrograming.pdf b/MatrixParallelPrograming.pdf
index 0ef406a97af05499b3c394eb8cda9971b219444f..ba56ecbeb152b795277470db6f30b3e74449e60c 100644 (file)
Binary files a/MatrixParallelPrograming.pdf and b/MatrixParallelPrograming.pdf differ

diff --git a/MatrixParallelPrograming.tex b/MatrixParallelPrograming.tex
index 55dd9f506e069b9f495ce853a470a2003f959f40..aca5c5ea3347a6ff7137a7bf2fd85771b7b8184e 100644 (file)
--- a/MatrixParallelPrograming.tex
+++ b/MatrixParallelPrograming.tex
@@ -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}%
 
 \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}
 
 \begin{table}[htp]
 \begin{center}


@@ -207,26 +207,36 @@ The metric scalability can be divided in two: \underline{strong scaling}, when t
 
 \begin{figure}[h]
        \centering
 
 \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}
        \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 all configurations out of the way,  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.\\

 
 

-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 cpu still "remembers" the matrix while searching it.

 
 

+Parallelising a simple search algorithm is heavily influenced by memory access patterns and synchronization 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 

 
 
 \end{document}
\ No newline at end of file
 
 
 \end{document}
\ No newline at end of file