Алгоритм распараллеливания OpenMP C

Question

в книге «Использование OpenMP» является примером плохого доступа к памяти в C, и я думаю, что это главная проблема в моей попытке распараллелить алгоритм Гаусса.

Пример выглядит примерно так:

k= 0 ;    
for( int j=0; j<n ; j++)
  for(int i = 0; i<n; i++)
       a[i][j] = a[i][j] - a[i][k]*a[k][j] ;

Итак, я понимаю, почему это вызывает плохой доступ к памяти. В C массив 2d хранится в строках, и здесь на каждом шаге i новая строка будет копироваться из памяти в кэш.

Я пытаюсь найти решение для этого, но я не получаю хорошую скорость. Последствия моих попыток незначительны.

Может кто-нибудь подсказать мне, что я могу сделать?

Самый простой способ - поменять местами циклы for, но я хочу сделать это по столбцам.

Вторая попытка:

for( int j=0; j<n-1 ; j+=2)
  for(int i = 0; i<n; i++)
  {
     a[i][j] = a[i][j] - a[i][k]*a[k][j] ;
     a[i][j+1] = a[i][j+1] - a[i][k]*a[k][j+1] ;
  }

вообще ничего не изменило.

Третья попытка:

for( int j=0; j<n ; j++)
{  
  d= a[k][j] ;
  for(int i = 0; i<n; i++)
  {
    e = a[i][k] ;
    a[i][j] = a[i][j] - e*d ;
  }
}

Thx много

Привет, Степп

Answer 1

Ваш порядок зацикливания приведет к потере кэша на каждую итерацию , как вы указали. Так что просто поменяйте местами операторы цикла:

for (int i = 0; i < n; i++)       // now "i" is first
  for (int j = 0; j < n; j++)
       a[i][j] = a[i][j] - a[i][k]*a[k][j];

Это исправит строку в a и изменит только столбцы, что означает, что ваш доступ к памяти будет непрерывным.

Answer 2

Эта проблема доступа к памяти связана только с использованием CACHE, а не Openmp. Чтобы использовать кеш в целом, вы должны иметь доступ к смежным областям памяти. Помните также, что если два или более потоков обращаются к одной и той же области памяти, то вы можете столкнуться с проблемой «ложного сдвига», которая приводит к ненужной перезагрузке кэша. См. Например:
http://software.intel.com/en-us/articles/avoiding-and-identifying-false-sharing-among-threads/

Answer 3

вместо этого используйте плоский массив, например:

#define A(i,j) A[i+j*ldA]

for( int j=0; j<n ; j++)
{  
  d= A(k,j) ;
  ...
}