Скажем, у меня есть такая игрушечная петля
float x[N];
float y[N];
for (int i = 1; i < N-1; i++)
y[i] = a*(x[i-1] - x[i] + x[i+1])
И я предполагаю, что моя строка кэша 64 байта (то есть достаточно большой). Тогда у меня будет (на кадр) в основном 2 доступа к ОЗУ и 3 FLOP:
x[i-1], x[i], x[i+1]
y[i]
Операционная интенсивность
OI = 3 FLOP / (2 * 4 байт)
Что будет, если я сделаю что-то подобное
float x[N];
for (int i = 1; i < N-1; i++)
x[i] = a*(x[i-1] - x[i] + x[i+1])
Обратите внимание, что нет y
больше. Значит ли это, что теперь у меня есть один доступ к ОЗУ?
x[i-1], x[i], x[i+1]
, хранение x[i]
или еще 2 доступа к ОЗУ
x[i-1], x[i], x[i+1]
x[i]
Потому что эксплуатационная интенсивность О.И. будет отличаться в любом случае. Кто-нибудь может рассказать что-нибудь об этом? Или, может быть, уточнить некоторые вещи. Спасибо
Отказ от ответственности: я никогда не слышал о модели производительности крыши до сегодняшнего дня. Насколько я могу судить, он пытается вычислить теоретическую границу «арифметической интенсивности» алгоритма, которая представляет собой число FLOPS на байт данных, к которым осуществляется доступ. Такая мера может быть полезна для сравнения аналогичных алгоритмов, как размер N
становится большим, но не очень полезно для прогнозирования реальной производительности.
Как правило, современные процессоры могут выполнять инструкции гораздо быстрее, чем они могут извлекать / хранить данные (это становится значительно более выраженным, когда данные начинают расти больше, чем размер кэшей). Таким образом, вопреки тому, что можно ожидать, цикл с более высокой арифметической интенсивностью может работать намного быстрее, чем цикл с более низкой арифметической интенсивностью; что важнее всего как N
масштабирование — это общий объем данных, к которым было произведено прикосновение (это будет справедливо до тех пор, пока память остается значительно медленнее, чем процессор, что справедливо для современных настольных и серверных систем).
Короче говоря, процессоры x86, к сожалению, слишком сложны, чтобы их можно было точно описать с помощью такой простой модели. Доступ к памяти проходит через несколько уровней кэширования (обычно L1, L2 и L3), прежде чем попасть в оперативную память. Возможно, все ваши данные помещаются в L1 — при втором запуске цикла (циклов) доступ к ОЗУ может вообще не быть.
И там не только кеш данных. Не забывайте, что код также находится в памяти и должен быть загружен в кэш инструкций. Каждое чтение / запись также выполняется с / на виртуальный адрес, который поддерживается аппаратным TLB (который может в экстремальных случаях вызвать сбой страницы и, скажем, заставить ОС записать страницу на диск в середине вашего цикла ). Все это предполагает, что ваша программа использует все аппаратное обеспечение (в не-реальном времени это просто не так, поскольку другие процессы и потоки конкурируют за одни и те же ограниченные ресурсы).
Наконец, само выполнение (непосредственно) не выполняется с чтением и записью в память, а скорее данные сначала загружаются в регистры (затем результат сохраняется).
То, как компилятор распределяет регистры, если он пытается развернуть цикл, автоматически векторизовать, модель планирования команд (чередование команд, чтобы избежать зависимости данных между командами) и т. Д., Также будет влиять на фактическую пропускную способность алгоритма.
Итак, наконец, в зависимости от создаваемого кода, модели процессора, объема обрабатываемых данных и состояния различных кэшей, задержка алгоритма будет меняться на порядки. Таким образом, интенсивность работы цикла не может быть определена путем проверки только кода (или даже созданной сборки), поскольку в игре присутствует много других (нелинейных) факторов.
Чтобы ответить на ваш актуальный вопрос, насколько я могу судить по определение изложено здесь, второй цикл в среднем будет считаться одним дополнительным 4-байтовым доступом на каждую итерацию, поэтому его OI будет равен θ (3N FLOPS / 4N байтов). Интуитивно понятно, что это имеет смысл, потому что в кеш уже загружены данные, и запись может изменить кеш напрямую, а не возвращаться в основную память (однако данные в конечном итоге должны быть записаны обратно, но это требование не изменилось с первого раза петля).
Других решений пока нет …