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

в книге «Использование 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 ;
  }
}

Большое спасибо

Приветствует Степп


openmp memory-access
person Stepp    schedule 24.02.2011    source источник
comment
Вы пробовали поменять порядок ваших for петель?   -  person ire_and_curses    schedule 24.02.2011
comment
да, я думал об этом, но это не было бы решением для намерения. кстати спасибо всем за быстрые ответы!   -  person Stepp    schedule 24.02.2011

Ответы (3)


arrow_upward
0
arrow_downward

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

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

for( int j=0; j<n ; j++)
{  
  d= A(k,j) ;
  ...
}
person Anycorn    schedule 24.02.2011
comment
какая разница? 2d-массивы на самом деле представляют собой длинные плоские массивы. - person Andrey; 24.02.2011
comment
@ Андрей, это значительно упрощает создание основного макета столбца. 2d-массивы уродливы на многих уровнях. - person Anycorn; 24.02.2011
comment
весь код составляет около 200 строк и полон незакомментированных попыток... я постараюсь сделать его презентабельным завтра, потому что в данный момент моя голова взрывается... - person Stepp; 24.02.2011

arrow_upward
0
arrow_downward

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

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 и изменит только столбцы, что означает, что ваши обращения к памяти будут непрерывными.

person chrisaycock    schedule 24.02.2011
comment
Спасибо, это был бы самый простой способ решить эту проблему, но я хочу, чтобы он работал по столбцам. - person Stepp; 24.02.2011

arrow_upward
0
arrow_downward

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

person GBBL    schedule 24.02.2011