title: parallel 2D convolution using openMP
body: <p>I'm attempting to implement 2D convolution in C. I have 2 implementations: first one is sequential and the second one is a parallel implementation using openMP.
  The problem is that the runtime for parallel code is always more than the runtime for the sequential code. The original algorithm was implemented in C++ using std::vector and It works fine, but I'm trying to implement It in C using pointers and dynamic memory allocation.</p>
  
  <p>Here's the steps taken in the algorithm:</p>
  
  <p>1- read input_matrix and kernel from separate files.</p>
  
  <p>2- compute convolution</p>
  
  <p>3- write the result to a file.</p>
  
  <p>I use dynamic memory allocation for the input_matrix, kernel, and output_matrix. Border columns and border rows are assumed to be neighbors, and kernels are assumed to have odd number of rows and columns.</p>
  
  <p>Here's the sequential convolution:</p>
  
  <pre><code>int index1, index2, a, b;
  
      for(int z = 0; z&lt;rows*columns;++z)
          *(output_matrix + z) = 0;
  
      clock_t begin = clock();
  
      for(int x=0;x&lt;rows;++x){
          for(int y=0;y&lt;columns;++y){
              for(int i=0;i&lt;krows;++i){
                  for(int j=0;j&lt;kcolumns;++j){
                      a=x+i-krows/2;  
                      b=y+j-kcolumns/2;                   
                      if(a&lt;0)
                          index1=rows+a;
                      else if(a&gt;rows-1)
                          index1=a-rows;
                      else 
                          index1=a;
  
                      if(b&lt;0)
                          index2=columns+b;
                      else if(b&gt;columns-1)
                          index2=b-columns;
                      else 
                          index2=b;
  
                      output_matrix[x*columns+y]+=input_matrix[index1*columns+index2]*kernel_matrix[i*kcolumns+j];
  
                  }
              }
  
          }
      }
  
      clock_t end = clock();
  
      printf("Sequential runtime = %f\n", (double)(end - begin) / CLOCKS_PER_SEC);
  </code></pre>
  
  <p>And here is the parallel code for convolution:</p>
  
  <pre><code>int index1, index2, a, b,x,y;
  
  for(int z = 0; z&lt;rows*columns;++z)
      *(output_matrix + z) = 0;
  
  clock_t begin = clock();
  #pragma omp parallel
  # pragma omp for private(x,y,a, b, index1, index2) 
  for(int z=0;z&lt;rows*columns;++z){
      x=z/columns;
      y=z%columns;
      for(int i=0;i&lt;krows;++i){
          for(int j=0;j&lt;kcolumns;++j){
              a=x+i-krows/2;  
              b=y+j-kcolumns/2;                   
              if(a&lt;0)
                  index1=rows+a;
              else if(a&gt;rows-1)
                  index1=a-rows;
              else 
                  index1=a;
  
              if(b&lt;0)
                  index2=columns+b;
              else if(b&gt;columns-1)
                  index2=b-columns;
              else 
                  index2=b;
  
              output_matrix[x*columns+y]+=input_matrix[index1*columns+index2]*kernel_matrix[i*kcolumns+j];
  
          }
      }
  }
  
  clock_t end = clock();
  printf("Parallel runtime using OMP= %f\n", (double)(end - begin) / CLOCKS_PER_SEC);
  </code></pre>