Матричное умножение строк и основных столбцов

В настоящее время я работаю над программой C, пытаясь вычислить умножение матриц. Я подошел к этой задаче, перебирая каждый столбец второй матрицы, как показано ниже.

Я установил размер 1000.

for(i=0;i<size;i++)
{
  for(j=0;j<size;j++)
  {
    for(k=0;k<size;k++)
    {
      matC[i][j]+=matA[i][k]*matB[k][j];
    }
  }
}

Я хотел знать, какой проблемный шаблон доступа в этой реализации. Что делает доступ к строке/столбцу более эффективным, чем другой? Я пытаюсь понять это с точки зрения логики использования кешей. Пожалуйста, помогите мне понять это. Ваша помощь очень ценится :)


c row matrix matrix-multiplication
person WoLv3rine    schedule 11.10.2012    source источник

Ответы (1)


arrow_upward
9
arrow_downward

Если вы говорите об использовании кешей, вы можете захотеть сделать что-то, называемое мозаикой цикла. Вы разбиваете цикл на плитки, так что внутренняя часть цикла сохраняется в кеше (который в наши дни довольно велик). Таким образом, ваш цикл превратится во что-то вроде (если вы передаете матрицы в функцию с помощью указателей)

for(j=0;j<size;j+=t)
    for(k=0;k<size;k+=t)
       for(i=0;i<size;i+=t)
          for(ii=i;ii<MIN(i+t,size);ii++)
             for(jj=j;jj<MIN(j+t,size);jj++)
        {       
          var=*(c+ii * size+jj);    //Var is a scalar variable                     
          for(kk=k;kk<MIN(k+t,size);kk++)
              {                      
         var = var + *(a+ii *size +kk) * *(bt +jj * size+ kk);          
              }
          *(c+ii *size +jj) = var;
        }

Значение t варьируется в зависимости от полученного ускорения. Может быть t = 64 128 256 и так далее. Есть много других методов, которые вы можете использовать здесь. Мозаика цикла — это всего лишь один из методов эффективного использования кэша. Кроме того, вы можете транспонировать матрицу B перед отправкой в ​​​​функцию умножения. Таким образом, вы получите линейный доступ к элементам матрицы B. Чтобы объяснить вам больше, рассмотрим

          A  --------   and B | | | |
             --------         | | | |
             --------         | | | | 
             --------         | | | |

Здесь вы всегда будете учитывать, чтобы умножить первую строку A на первый столбец B. И, поскольку вы используете C, я полагаю, ЦП требует дополнительных усилий для чтения всех столбцов матрицы B один за другим внутри памяти. Чтобы облегчить эти усилия, вы можете транспонировать матрицу и получить строки матрицы B' (которые, по сути, являются не чем иным, как столбцами B) и использовать мозаику цикла для кэширования максимального количества элементов для умножения. Надеюсь, это поможет.

person Recker    schedule 11.10.2012
comment
Большое спасибо! это объяснение помогло мне понять, как они работают, и их различия. - person WoLv3rine; 20.10.2012