title: Eigen & OpenMP : No parallelisation due to false sharing and thread overhead
body: <p><strong>System Specification:</strong></p>
  
  <ol>
  <li>Intel Xeon E7-v3 Processor(4 sockets, 16 cores/sockets, 2
  threads/core)</li>
  <li>Use of Eigen family and C++</li>
  </ol>
  
  <p>Following is serial implementation of code snippet:</p>
  
  <pre><code>Eigen::VectorXd get_Row(const int j, const int nColStart, const int nCols) {
  
      Eigen::VectorXd row(nCols);
      for (int k=0; k&lt;nCols; ++k) {
          row(k) = get_Matrix_Entry(j,k+nColStart);
      }
  
  } 
  
  double get_Matrix_Entry(int x , int y){
      return exp(-(x-y)*(x-y));
  } 
  </code></pre>
  
  <p>I need to parallelise the get_Row part as nCols can be as large as 10^6, therefore, I tried certain techniques as:</p>
  
  <ol>
  <li><p><strong>Naive parallelisation:</strong></p>
  
  <pre><code>Eigen::VectorXd get_Row(const int j, const int nColStart, const int nCols) {  
      Eigen::VectorXd row(nCols);
  
       #pragma omp parallel for schedule(static,8)    
       for (int k=0; k&lt;nCols; ++k) {
            row(k)    =   get_Matrix_Entry(j,k+nColStart);
  
       return row;
  }
  </code></pre></li>
  <li><p><strong>Strip Mining:</strong></p>
  
  <pre><code>Eigen::VectorXd get_Row(const int j, const int nColStart, const int nCols) { 
      int vec_len = 8;
      Eigen::VectorXd row(nCols) ;
      int i,cols;
      cols=nCols;
      int rem = cols%vec_len;
      if(rem!=0)
          cols-=rem;
  
      #pragma omp parallel for    
      for(int ii=0;ii&lt;cols; ii+=vec_len){
           for(i=ii;i&lt;ii+vec_len;i++){
               row(i) = get_Matrix_Entry(j,i+nColStart);
           }
      }
  
      for(int jj=i; jj&lt;nCols;jj++)
          row(jj) = get_Matrix_Entry(j,jj+nColStart);
  
      return row;
  }
  </code></pre></li>
  <li><p><strong>Somewhere from internet to avoid false sharing:</strong></p>
  
  <pre><code>Eigen::VectorXd get_Row(const int j, const int nColStart, const int nCols) {
      int cache_line_size=8;
      Eigen::MatrixXd row_m(nCols,cache_line_size);
  
      #pragma omp parallel for schedule(static,1)
      for (int k=0; k&lt;nCols; ++k) 
          row_m(k,0)  =   get_Matrix_Entry(j,k+nColStart);
  
      Eigen::VectorXd row(nCols); 
      row = row_m.block(0,0,nCols,1);
  
     return row;
  
  }
  </code></pre></li>
  </ol>
  
  <p><strong>OUTPUT:</strong></p>
  
  <p>None of the above techniques helped in reducing the time taken to execute get_row for large nCols implying naice parallelisation worked similar to the other techniques(although better from serial), any suggestions or method that can help to improve the time?</p>
  
  <p>As mentioned by user Avi Ginsburg, I am mentioning some other system details:</p>
  
  <ul>
  <li>g++(GCC) is compiler with version 4.4.7</li>
  <li>Eigen Library Version is 3.3.2</li>
  <li>Compiler flags used: "-c -fopenmp -Wall  -march=native -O3 -funroll-all-loops -ffast-math -ffinite-math-only -I header" , here header is folder containing Eigen.</li>
  <li><p>Output of gcc -march=native -Q --help=target->(Description of some flags are mentioned only):</p>
  
  <p>-mavx                             [enabled]</p>
  
  <p>-mfancy-math-387                  [enabled]</p>
  
  <p>-mfma                             [disabled]</p>
  
  <p>-march=                           core2</p></li>
  </ul>
  
  <p>For full desciption of flags please see <a href="https://drive.google.com/file/d/0B4tReu45goapb2xpSFpxbUlEMjQ/view?usp=sharing" rel="nofollow noreferrer">this</a>.</p>