Могут ли условия гонки снизить производительность кода?

Question

Я бег следующего кода для матричного умножения производительности которого я должен измерить:

for (int j = 0; j < COLUMNS; j++) 
#pragma omp for schedule(dynamic, 10) 
    for (int k = 0; k < COLUMNS; k++) 
     for (int i = 0; i < ROWS; i++) 
      matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j]; 

Да, я знаю, что это очень медленно, но это не главное - это исключительно для целей измерения производительности , Я запускаю 3 версии кода в зависимости от того, где я помещаю директиву #pragma omp, и, следовательно, в зависимости от того, где происходит распараллеливание. Код запускается в Microsoft Visual Studio 2012 в режиме выпуска и профилируется в CodeXL.

Одна вещь, которую я заметил из измерений, заключается в том, что опция в фрагменте кода (с распараллеливанием перед циклом k) является самой медленной, а затем версией с директивой перед j-циклом, а затем с ней перед цикл i. Представленная версия также является той, которая вычисляет неверный результат из-за условий гонки - одновременное использование нескольких потоков одним и тем же элементом матрицы результатов. Я понимаю, почему версия i цикла является самой быстрой - все конкретные потоки обрабатывают только часть диапазона i-переменной, увеличивая временную локальность. Тем не менее, я не понимаю, что приводит к тому, что версия цикла k является самой медленной - связано ли это с тем, что она производит неверный результат?

Answer 1

Конечно, условия гонки могут замедлить работу кода. Когда два или более потока обращаются к одной и той же части памяти (одна и та же строка кэша), эта часть должна быть загружена в кеш данных данных снова и снова, так как другой поток делает недействительным содержимое кеша, записывая в него. Они конкурируют за общий ресурс.

Когда две переменные, расположенные слишком близко в памяти, записываются и читаются больше потоков, это также приводит к замедлению. Это называется false sharing. В вашем случае это еще хуже, они не просто слишком близки, они даже совпадают.

Answer 2

Ваше предположение верно. Но если мы говорим о производительности, а не просто подтверждаем ваше предположение, то в истории больше.

• Порядок индексах является большой проблемой, многопоточный или нет. Учитывая, чем расстояние между mat[x][y] и mat[x][y+1] является один, в то время как расстояние между mat[x][y] и mat[x+1][y] является dim(mat[x]) Вы хотите x быть внешним индексом и y внутреннего иметь минимальное расстояние между итерацией. Учитывая __[i][j] += __[i][k] * __[k][j];, вы видите, что правильный порядок для пространственной локации i -> k -> j.

• Независимо от заказа, существует одно значение, которое можно сохранить для последующего. Учитывая ваш сниппет значение

  for (int j = 0; j < COLUMNS; j++) 
      for (int k = 0; k < COLUMNS; k++) 
       for (int i = 0; i < ROWS; i++) 
        matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j]; 
  

matrix_b[k][j] будет выбрано из памяти i раз.Вы могли бы начать с

for (int j = 0; j < COLUMNS; j++) 
     for (int k = 0; k < COLUMNS; k++) 
      int temp = matrix_b[k][j]; 
      for (int i = 0; i < ROWS; i++) 
       matrix_r[i][j] += matrix_a[i][k] * temp; 

Но учитывая, что вы пишете matrix_r[i][j], лучший доступ к оптимизации является matrix_r[i][j], учитывая, что запись происходит медленнее, чем чтение

Ненужные записи обращений к памяти

for (int i = 0; i < ROWS; i++) 
    matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j]; 

будет записывать в память matrix_r[i][j]ROWS раз. Использование временной переменной уменьшит доступ к ней.

for (int i = 0; i < ...; j++) 
     for (int j = 0; j < ...; k++) 
      int temp = 0; 
      for (int k = 0; k < ...; i++) 
       temp += matrix_a[i][k] * matrix_b[k][j]; 
      matrix_r[i][j] = temp; 

Это уменьшает доступ на запись от n^3 до n^2.

• Теперь вы используете потоки. Чтобы максимизировать эффективность многопоточности, вы должны изолировать столько же доступа к потоковой памяти от других. Один из способов сделать это - предоставить каждому потоку столбец и префикс этого столбца один раз. Один простой способ будет иметь транспонирование matrix_b таким образом, что

  matrix_r[i][j] += matrix_a[i][k] * matrix_b[k][j]; becomes 
  matrix_r[i][j] += matrix_a[i][k] * matrix_b_trans[j][k]; 
  

таким образом, что самый внутренний цикл по к всегда имеем дело с непрерывной памяти соответствующей к matrix_a и matrix_b_trans

for (int i = 0; i < ROWS; j++) 
     for (int j = 0; j < COLS; k++) 
      int temp = 0; 
      for (int k = 0; k < SAMEDIM; i++) 
       temp += matrix_a[i][k] * matrix_b_trans[j][k]; 
      matrix_r[i][j] = temp;