ImprovedParallelMatricSearch.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <pthread.h>
   4 #include <time.h>
   5
   6 const int m_rows = 40000;
   7 const int m_cols = 40000;
   8 const int threads_to_use = 4;
   9
  10 _Atomic int hv = 0;
  11 int **matrix;
  12
  13 typedef struct{
  14   int start;
  15   int end;
  16 } thread_args;
  17
  18 void* parallel_populate_matrix(void *arg){
  19   thread_args *args = (thread_args *)arg;
  20   for(int r = 0; r < m_rows; r++){
  21       for(int c = args->start; c < args->end;c++){
  22           matrix[r][c] = r*m_cols+c;
  23       }
  24   }
  25   return NULL;
  26 }
  27
  28 void* parallel_search_cols(void *arg){
  29   thread_args *args = (thread_args *)arg;
  30   int local_hv = 0;
  31   for(int r = 0; r < m_rows; r++){
  32     for(int c = args->start; c < args->end; c++){
  33       if(matrix[r][c] > local_hv){
  34         local_hv = matrix[r][c];
  35       }
  36     }
  37   }
  38
  39   if(local_hv > hv){
  40     hv = local_hv;
  41   }
  42   return NULL;
  43 }
  44
  45 void run_parallel_search(int num_threads) {
  46     pthread_t *threads = malloc(num_threads * sizeof(pthread_t));
  47     thread_args *args = malloc(num_threads * sizeof(thread_args));
  48
  49     if (threads == NULL || args == NULL) {
  50         perror("Failed to allocate memory for threads");
  51         exit(1);
  52     }
  53
  54     int chunk_size = m_cols / num_threads;
  55
  56     for (int i = 0; i < num_threads; i++) {
  57         args[i].start = i * chunk_size;
  58         if (i == num_threads - 1) {
  59             args[i].end = m_cols;
  60         } else {
  61             args[i].end = (i + 1) * chunk_size;
  62         }
  63         if (pthread_create(&threads[i], NULL, &parallel_search_cols, &args[i]) != 0) {
  64             perror("Failed to create thread");
  65             exit(1);
  66         }
  67     }
  68
  69     for (int i = 0; i < num_threads; i++) {
  70         pthread_join(threads[i], NULL);
  71     }
  72     free(threads);
  73     free(args);
  74 }
  75
  76 void init_parallel_matrix(int *data,int num_threads){
  77     pthread_t *threads = malloc(num_threads * sizeof(pthread_t));
  78     thread_args *args = malloc(num_threads * sizeof(thread_args));
  79     if (threads == NULL || args == NULL) {
  80         perror("Failed to allocate memory for threads");
  81         exit(1);
  82     }
  83
  84     for(int r = 0; r<m_rows;r++){
  85       matrix[r] = data + r * m_cols;
  86     }
  87
  88     int chunk_size = m_cols / num_threads;
  89     for (int i = 0; i < num_threads; i++) {
  90           args[i].start = i * chunk_size;
  91           if (i == num_threads - 1) {
  92               args[i].end = m_cols;
  93           } else {
  94               args[i].end = (i + 1) * chunk_size;
  95           }
  96           if (pthread_create(&threads[i], NULL, &parallel_populate_matrix, &args[i]) != 0) {
  97               perror("Failed to create thread");
  98               exit(1);
  99           }
 100       }
 101
 102       for (int i = 0; i < num_threads; i++) {
 103           pthread_join(threads[i], NULL);
 104       }
 105       free(threads);
 106       free(args);
 107 }
 108
 109
 110 int main(void){
 111   printf("1st --> Allocate memory\n");
 112   clock_t t_t1; t_t1 = clock();
 113   size_t rows_size = m_rows * sizeof(int*);
 114   matrix = malloc(rows_size);
 115   if(matrix == NULL){
 116     perror("malloc failled");
 117     return 1;
 118   }
 119   size_t data_size = (size_t)m_rows * m_cols * sizeof(int);
 120   int *data;
 121   if(posix_memalign((void**)&data, 64, data_size) != 0){
 122     perror("not able to alocate memory");
 123     free(matrix);
 124     return 1;
 125   }
 126   t_t1 = clock() - t_t1;
 127   double t1_ttaken = ((double)t_t1)/CLOCKS_PER_SEC;
 128   printf(" %f sec\n",t1_ttaken);
 129
 130   printf("2nd --> Populate the matrix\n");
 131   clock_t t_t2; t_t2 = clock();
 132   init_parallel_matrix(data, threads_to_use);
 133   t_t2 = clock() - t_t2;
 134   double t2_ttaken = ((double)t_t2)/CLOCKS_PER_SEC;
 135   printf(" %f sec\n",t2_ttaken);
 136
 137   printf("3rd --> Search matrix\n");
 138   clock_t t_t3; t_t3 = clock();
 139   run_parallel_search(threads_to_use);
 140   t_t3 = clock() - t_t3;
 141   double t3_ttaken = ((double)t_t3)/CLOCKS_PER_SEC;
 142   printf(" %f sec\n",t3_ttaken);
 143
 144   printf("Done\n The biggest value found is  %d \n", hv);
 145   free(data);
 146   free(matrix);
 147   return 0;
 148 }