Я намерен умножить 2 матрицы, используя метод, удобный для кеша (что приведет к меньшему количеству промахов)
Я узнал, что это можно сделать с помощью функции транспонирования кэша.
Но я не могу найти этот алгоритм. Могу ли я узнать, как этого добиться?
Слово, которое вы ищете, это thrashing. Поиск умножения матриц в 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;
}
}
}
c[i, j] = s;, но кажется, что j не объявлен в этой области.
- person Shihao Xu; 18.04.2017
a[i,j] вы всегда должны убедиться, что j всегда изменяется быстрее, чем i, если вы хотите максимизировать производительность.
- person Cesar; 13.02.2018
@ Ответ Цезаря неверен. Например, внутренний цикл
for (int k = 0; k < n; k++)
s += a[i,k] * Bcolj[k];
проходит через i-й столбец a.
Следующий код должен гарантировать, что мы всегда посещаем данные построчно.
void multiply(const double (&a)[I][K],
const double (&b)[K][J],
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;
}
}
}
}
