Увеличение производительности за счет кэш-памяти и конвейерности процессора

@wlmn · Регистрация: 05.02.2017

Студворк — интернет-сервис помощи студентам

Читаю тут одну книгу и не понимаю.
Перемножают матрицы. И говорят. Ну вот, если будем перемножать как обычно большие матрицы С=AB, то т.к. матрица представлена в памяти в виде строки ее элементов, эти А и В в кэш-память не влезет, поэтому удобно представить их в виде блоков матриц. (блок - минор меньшей размерности, для простоты NxN и будем считать, что А,В nxn, n делится на N)
И значит будем эти самые блоки и перемножать. Тогда
С_im = A_ij B_jm (тут подразумевается соглашение Эйнштейна - т.е. суммируем по j, а D_ab - это миноры матрицы D NxN)
Ну и так как мы перемножаем эти самые миноры, у нас они все влазят в кэш-память, и процесс перемножения ускоряется, для разных процессоров во-разному, но вот взяли они какой-то пример и на третьем пентиуме получилось, аж в 7,6 раз быстрее.

А дальше вообще какая-то жесть. Пишут: Вспомним, что все современные процессоры имеют конвейер инструкций, причем весьма глубокий (может доходить до полутора десятков стадий). Для его заполнения длина линейного участка программы (т.е. не содержащих перехода) должна быть как минимум больше глубины конвейера (желательно - в несколько раз больше). В предыдущем варианте в самом внутреннем цикле находится 1 оператор языка С.

C

for(int i = 0; i<N; i++)
{
     for(int j = 0; i<N; i++)
     {
     /*тот самый оператор*/
     }
}

который, в зависимости от целевого процессора, транслируется компилятором в 7-12 инструкций (включая операторы обслуживания цикла).
Для увеличения длины линейного участка программы "развернем" цикл в предыдущем варианте: за один виток по j будем вычислять сразу по 4 элемента матрицы С.
c_i,m, c_i+1,m, c_i,m+1, c_i+1,m+1. Поскольку при их вычислении используются повторяющиеся элементы матриц А,В, то также появляются дополнительные резервы для ускорения работы за счет оптимизации компилятора и кэш-памяти.

И таким образом, они ускоряют программу умножения матриц, по сравнению с самым естественным вариантом (строка*столбец) в 13,8 раз.
Скажите, правильно ли я понимаю, что для того, чтобы ускорить программу за счет конвейерности, мне нужно знать длину этого конвейера? Как узнать эту длину на моем компьютере, и как вообще узнать во сколько инструкций транслируются те или иные команды? Что такое длина линейного участка я так и не понял.

А если попроще, могу ли я ускорить вот так вот что-либо напихав внутрь цикла побольше операций?

@nmcf · 03.03.2017, 10:02

Документацию на процессор читать, наверное.

@wlmn · 03.03.2017, 16:57 **[ТС]**

Ну а что такое линейный участок и чем это вообще отличается от раскрытия цикла?
Если на пальцах, то кажется, что было:
...-> i++ -> проверка цикла -> оператор -> i++ -> проверка цикла -> оператор -> и т.д.
Стало:
i++ -> проверка цикла -> оператор -> оператор -> оператор -> оператор -> i++ -> проверка цикла -> оператор -> оператор -> оператор -> оператор ->...
Т.е. процессор затрачивает меньше времени на цикл for.
Но они там говорят, что этот оператор транслируется компилятором с учетом обслуживания цикла, и почему-то кажется, что имеется в виду, цикл здесь ни при чем. И еще кажется, что компилятор такие штуки сам должен оптимизировать, потому что в обратном случае это как-то странно, можно сделать вывод, что лучше от циклов вообще отказаться: чем больше операторов внутри, тем меньше времени затрачивается на обслуживание цикла. - Я не знаю, эта книга какая-то сложная для понимания.
И если так, то при чем здесь тогда вообще конвейерность?

@nmcf 7529 / 6394 / 2914 Регистрация: 14.04.2014 Сообщений: 27,855
	03.03.2017, 10:02	2
	Документацию на процессор читать, наверное. 0

@wlmn 23 / 23 / 3 Регистрация: 05.02.2017 Сообщений: 207
	03.03.2017, 16:57 [ТС]	3
	Ну а что такое линейный участок и чем это вообще отличается от раскрытия цикла? Если на пальцах, то кажется, что было: ...-> i++ -> проверка цикла -> оператор -> i++ -> проверка цикла -> оператор -> и т.д. Стало: i++ -> проверка цикла -> оператор -> оператор -> оператор -> оператор -> i++ -> проверка цикла -> оператор -> оператор -> оператор -> оператор ->... Т.е. процессор затрачивает меньше времени на цикл for. Но они там говорят, что этот оператор транслируется компилятором с учетом обслуживания цикла, и почему-то кажется, что имеется в виду, цикл здесь ни при чем. И еще кажется, что компилятор такие штуки сам должен оптимизировать, потому что в обратном случае это как-то странно, можно сделать вывод, что лучше от циклов вообще отказаться: чем больше операторов внутри, тем меньше времени затрачивается на обслуживание цикла. - Я не знаю, эта книга какая-то сложная для понимания. И если так, то при чем здесь тогда вообще конвейерность? 0

Опции темы