- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
void MultipleSquareMatrix(Matrix*rres, Matrix*mul1, Matrix* mul2)
{
int N = mul1->height();
Matrix rmul1(N,N);
Matrix rmul2(N,N);
#define SM (CLS / sizeof (double))
for (i = 0; i < N; i += SM)
for (j = 0; j < N; j += SM)
for (k = 0; k < N; k += SM)
for (i2 = 0, rres = &res[i][j],
rmul1 = &mul1[i][k]; i2 < SM;
++i2, rres += N, rmul1 += N)
for (k2 = 0, rmul2 = &mul2[k][j];
k2 < SM; ++k2, rmul2 += N)
for (j2 = 0; j2 < SM; ++j2)
rres[j2] += rmul1[k2] * rmul2[j2];
}
Follow us!
Автор, откликнитесь, каким мегаоптимизированным алгоритмом пользовались? Предлагаю закопирайтить эту интелектуальную собственность под своим именем "Метод ***(фамилия)".
upd: они и ещё и глобальные?! 0_о
С++?
Вот:
- класс или структура с конструктором и перегруженым оператором operator[].
#define CLS 64
#define N 1000
double res[N][N];
double mul1[N][N];
double mul2[N][N];
int main()
{
#define SM (CLS / sizeof (double))
double *rmul1;
double *rmul2;
double *rres;
int i,j,k,i2,j2,k2;
for (i = 0; i < N; i += SM)
for (j = 0; j < N; j += SM)
for (k = 0; k < N; k += SM)
for (i2 = 0, rres = &res[i][j],
rmul1 = &mul1[i][k]; i2 < SM;
++i2, rres += N, rmul1 += N)
for (k2 = 0, rmul2 = &mul2[k][j];
k2 < SM; ++k2, rmul2 += N)
for (j2 = 0; j2 < SM; ++j2)
rres[j2] += rmul1[k2] * rmul2[j2];
return 0;
}
в данном случае длина строка кеша выставлена в 64 байта, такая длина сейчас на большинстве современных Intel Core 2 и Quad.
в линейке процов AMD придется посмотреть в спецификации Cashe line size )
Это часть оптимизации?
Большой прирост хоть?
Так что, Вам в любом случае придется уменьшать количество промахов при обращении в кеш, конечно мы не можем напрямую влиять на кеш, однако можем подстроится под внутреннюю оптимизацию процессора и использовать её в своих целях.
>перемножаем строку на столбец
не так, золотце, вторая матрица транспонируется, не знал? ну вот поэтому я и говорю - байтоебство без знания алгоритмов - как минимум смешно.
проверь матрицы не 10х10, а 50000х50000 и удивись
а раз этот алгоритм здесь, то какой вывод?
lwn.net/Articles/250967
на PS3 уже давно проще матрицу из кеша перемножить еще раз, чем читать ее из памяти (линия 128 байт)... поищи инфу в блоге Micke Aston...
в твоих
задумайся когда нибудь, что тормозит в твоих программах, и в 99% случаем это будет память... доступ в память мимо кеша это несколько сотен тактов процессора, что равно сотне команд работающих в пределах кеша...
Еще К.К. в "оптимизации программ по памяти" писал про этов 2003м году.
К примеру, иногда можно это сделать на сопроцессорах, например на видюхе.
google://кластеры из PS3
Прямо связь поколений.
минусуйте меня
big O определяется исходя из предпосылки, что время умножения и сложения плавающих петухов константно
Я скорее всего уже безнадёжно отстал от этой области, поэтому не спорю, но:
Где ассемблерные комманды процессора по упреждающему чтению данных в кэш?
Коли так, то это перемножение матриц оптимизированное под кэш конкретного размера.
Процессор сам сделает упреждающую выборку, если сможет. И это заслуга процессора, а не алгоритма.
Как говорится проще перечислить, когда упреждающая выборка работает хорошо, чем когда она работает плохо. Наша цель сделать так, чтобы она работала на нас, а не против нас.
пожалуй лучше ссылки не придумать, здесь довольно подробно все рассмотрено.
Но!
Стиль ужасен. Нет комментариев. Ничего не говорящие имена переменных. #define посреди кода. Какая-то чушь с C++. Наконец, всё это работает только если N кратно SM (восьми).
Итого -- таки говнокод.