Итеративное умножение матриц с разбиением на на блоки
Я хотел написать умножение матриц с учётом кэша. Нашёл алгоритм на wiki
Алгоритм:
Ввод: матрица A(n x m) и B(m x p)
Пусть С будет новой матрицей (n x p)
Выбираем часть размера T = Θ( sqrt(M) )
int I,J,K,i,j,k,sum;
for(I = 1; I <= n; I += T)
for(J = 1; J <= p; J += T)
for(K = 1; K <= m; K += T)
for(i = I; i <= min(I + T, n); i++)
for(j = J; j <= min(J + T, p); j++) {
sum = 0;
for(k = K; k <= min(K + T, m); k++)
sum += A[i][k] * B[k][j]
C[i][j] += sum;
}
M - это вроде размер кэша, но мне совсем не понятна эта нотация с тетой от корня: T = Θ( sqrt(M) ). Как её вычеслить?
Ответы (1 шт):
Автор решения: AlexGlebe
→ Ссылка
Допустим у вас размер кеша 2 Мегабайта
$ lscpu
L3 cache: 2048K
Например матрица у вас будет с элементами типа double. У него размер 8 байт.
Тогда максимальный вариант размеров матрицы, влазящая в кеш будет sqrt(2048 * 1024 / 8) == 512. То-есть размер матрицы sizeof(double[512][512]) равен размеру кеша.
О большое Θ - написали, потому, что неизвестно с каким типом вы будете работать.