Удобный для кеширования метод умножения двух матриц

Question

Я намереваюсь умножить 2 матрицы с использованием метода кэширования (это приведет к уменьшению числа пропусков)

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

Но я не могу найти этот алгоритм. Могу ли я узнать, как этого добиться?

Answer 1

Слово, которое вы ищете, поражает. Поиск умножающей матрицы в Google дает больше результатов.

Стандартный алгоритм умножения для c = a*b будет выглядеть так

void multiply(double[,] a, double[,] b, double[,] c)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                C[i, j] += a[i, k] * b[k, j]; 
}

По сути, быстрое перемещение по памяти большими шагами отрицательно сказывается на производительности. Шаблон доступа для k в B [k, j] делает именно это. Таким образом, вместо того, чтобы прыгать в памяти, мы можем переставить операции так, чтобы большинство внутренних циклов работало только со вторым индексом доступа матриц:

void multiply(double[,] a, double[,] B, double[,] c)
{  
   for (i = 0; i < n; i++)
   {  
      double t = a[i, 0];
      for (int j = 0; j < n; j++)
         c[i, j] = t * b[0, j];

      for (int k = 1; k < n; k++)
      {
         double s = 0;
         for (int j = 0; j < n; j++ )
            s += a[i, k] * b[k, j];
         c[i, j] = s;
      }
   }
}

Это был пример, приведенный на этой странице. Однако другой вариант - заранее скопировать содержимое B[k, *] в массив и использовать этот массив в вычислениях внутреннего цикла. Этот подход обычно намного быстрее, чем альтернативы, даже если он включает в себя копирование данных. Даже если это может показаться нелогичным, пожалуйста, попробуйте сами.

void multiply(double[,] a, double[,] b, double[,] c)
{
    double[] Bcolj = new double[n];
    for (int j = 0; j < n; j++)
    {
        for (int k = 0; k < n; k++)
            Bcolj[k] = b[k, j];

        for (int i = 0; i < n; i++)
        {
            double s = 0;
            for (int k = 0; k < n; k++)
                s += a[i,k] * Bcolj[k];
            c[j, i] = s;
        }
   }
}

Answer 2

@ Цезарь не верный ответ. Например, внутренний цикл

for (int k = 0; k < n; k++)
   s += a[i,k] * Bcolj[k];

проходит через i-й столбец

Следующий код должен гарантировать, что мы всегда посещаем данные построчно.

void multiply(const double (&a)[I][K], 
              const double (&b)[K][J], 
              const double (&c)[I][J]) 
{
    for (int j=0; j<J; ++j) {
       // iterates the j-th row of c
       for (int i=0; i<I; ++i) {
         c[i][j] = 0;
       } 

       // iterates the j-th row of b
       for (int k=0; k<K; ++k) {
          double t = b[k][j];
          // iterates the j-th row of c
          // iterates the k-th row of a
          for (int i=0; i<I; ++i) {
            c[i][j] += a[i][k] * t;
          } 
       }
    }
}