- 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
зачот
Про южный не знаю. Возможно, и сейчас встречается в неинтегрированном виде под другими названиями.
Кстати, я застал технику без Super I/O («южного моста») на материнке. Ещё на 486 обычно Super I/O выполняли в виде отдельной карточки для шины ISA (даже не PCI и не VLB, ибо скорости ISA для контроллеров тех лет хватало).
Южный переименовался в IO Hub, и из него рос корень PCI (не экспресс!), USB хост адаптер, и вероятно (S)ATA.
А всякую мелочевку типа биоса, FDC и прочих 16550 UART и i8042 (PS/2) выселили в Super IO, который связали с IO хабом через LPC
Топология менялась несметное число раз: от прямой "системной шины" в 5150 (просто никаких мостов: все на одной шине сидят от памяти до LPT) впоследствии неазванной ISA, до уезда всего вклюая рут комплекс PCI-Express в проц. Когда мы используем nvme, мы реально включаем его в проц, лол.
вот относительно новая хуйня (чипсет зачем-то сверху, хотя он какбы южный)
PCI-E два: четвертые в чипсете, пятые в проце.
На "юге" осталась USB, сеть, звук, TPM для битлокера, и всякие SMBus, нужные чтобы там скоростю вентиляторов и температурными зонами рулить через ACPI
А SMBus вроде поверх I2C работает?
Интересно, в какой момент появился термин "north bridge".
Вот еще пара схемок из книжки про PCI:
https://postimg.cc/FYthyYL1
https://postimg.cc/SnWkDm6r
тут видно, что PCI уже сразу назывался host bridge, и уже сразу в память надо было ходить через него (это логично, так как на этой шине всякое уйстройство -- басмастер, и все могут срать в память без CPU, каждый сам себе DMA), а PCI-ISA bridge всего лишь адаптер на шине PCI, и там еще в BIOS setup хостбриджу надо было рассказывать, какие адреса не трогать, чтб они достались ISA.
Отдельная ебля с прерываниями (они были свои в PCI и они шарились) и их надо было мапить на прервания x86. Когда в PCI-Express завезли MSI, все выдохнули
хахаха, да ведь это же ХУЙ вместе с яйцами!
Прямо связь поколений.
минусуйте меня
big O определяется исходя из предпосылки, что время умножения и сложения плавающих петухов константно
Я скорее всего уже безнадёжно отстал от этой области, поэтому не спорю, но:
Где ассемблерные комманды процессора по упреждающему чтению данных в кэш?
Коли так, то это перемножение матриц оптимизированное под кэш конкретного размера.
Процессор сам сделает упреждающую выборку, если сможет. И это заслуга процессора, а не алгоритма.
Как говорится проще перечислить, когда упреждающая выборка работает хорошо, чем когда она работает плохо. Наша цель сделать так, чтобы она работала на нас, а не против нас.
там немного двадцатый век (EDO, BEDO, все прелести асинхронной DRAM), но много и годноты вроде борьбы с переменной на границе кеш линеек
Я, кстати, ставил планки PC-100 и PC-133 на машину с частотой шины 66 МГц.
Оверклокеры остались, но теперь у них есть SPD, XMP и пр
пожалуй лучше ссылки не придумать, здесь довольно подробно все рассмотрено.
Но!
Стиль ужасен. Нет комментариев. Ничего не говорящие имена переменных. #define посреди кода. Какая-то чушь с C++. Наконец, всё это работает только если N кратно SM (восьми).
Итого -- таки говнокод.