Модель линии крыши: расчет эксплуатационной интенсивности

Скажем, у меня есть такая игрушечная петля

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:

  • 1 (кэшированный) доступ для чтения: загрузка всех 3 x[i-1], x[i], x[i+1]
  • 1 доступ для записи: хранение y[i]
  • 3 FLOP (1 мул, 1 сложение, 1 саб)

Операционная интенсивность

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 больше. Значит ли это, что теперь у меня есть один доступ к ОЗУ?

  • 1 (кэшировано) чтение / запись: загрузка x[i-1], x[i], x[i+1], хранение x[i]

или еще 2 доступа к ОЗУ

  • 1 (кэшировано) прочитано: загрузка x[i-1], x[i], x[i+1]
  • 1 (кэшированный) запись: хранение x[i]

Потому что эксплуатационная интенсивность О.И. будет отличаться в любом случае. Кто-нибудь может рассказать что-нибудь об этом? Или, может быть, уточнить некоторые вещи. Спасибо

7

Решение

Отказ от ответственности: я никогда не слышал о модели производительности крыши до сегодняшнего дня. Насколько я могу судить, он пытается вычислить теоретическую границу «арифметической интенсивности» алгоритма, которая представляет собой число FLOPS на байт данных, к которым осуществляется доступ. Такая мера может быть полезна для сравнения аналогичных алгоритмов, как размер N становится большим, но не очень полезно для прогнозирования реальной производительности.

Как правило, современные процессоры могут выполнять инструкции гораздо быстрее, чем они могут извлекать / хранить данные (это становится значительно более выраженным, когда данные начинают расти больше, чем размер кэшей). Таким образом, вопреки тому, что можно ожидать, цикл с более высокой арифметической интенсивностью может работать намного быстрее, чем цикл с более низкой арифметической интенсивностью; что важнее всего как N масштабирование — это общий объем данных, к которым было произведено прикосновение (это будет справедливо до тех пор, пока память остается значительно медленнее, чем процессор, что справедливо для современных настольных и серверных систем).

Короче говоря, процессоры x86, к сожалению, слишком сложны, чтобы их можно было точно описать с помощью такой простой модели. Доступ к памяти проходит через несколько уровней кэширования (обычно L1, L2 и L3), прежде чем попасть в оперативную память. Возможно, все ваши данные помещаются в L1 — при втором запуске цикла (циклов) доступ к ОЗУ может вообще не быть.

И там не только кеш данных. Не забывайте, что код также находится в памяти и должен быть загружен в кэш инструкций. Каждое чтение / запись также выполняется с / на виртуальный адрес, который поддерживается аппаратным TLB (который может в экстремальных случаях вызвать сбой страницы и, скажем, заставить ОС записать страницу на диск в середине вашего цикла ). Все это предполагает, что ваша программа использует все аппаратное обеспечение (в не-реальном времени это просто не так, поскольку другие процессы и потоки конкурируют за одни и те же ограниченные ресурсы).

Наконец, само выполнение (непосредственно) не выполняется с чтением и записью в память, а скорее данные сначала загружаются в регистры (затем результат сохраняется).

То, как компилятор распределяет регистры, если он пытается развернуть цикл, автоматически векторизовать, модель планирования команд (чередование команд, чтобы избежать зависимости данных между командами) и т. Д., Также будет влиять на фактическую пропускную способность алгоритма.

Итак, наконец, в зависимости от создаваемого кода, модели процессора, объема обрабатываемых данных и состояния различных кэшей, задержка алгоритма будет меняться на порядки. Таким образом, интенсивность работы цикла не может быть определена путем проверки только кода (или даже созданной сборки), поскольку в игре присутствует много других (нелинейных) факторов.


Чтобы ответить на ваш актуальный вопрос, насколько я могу судить по определение изложено здесь, второй цикл в среднем будет считаться одним дополнительным 4-байтовым доступом на каждую итерацию, поэтому его OI будет равен θ (3N FLOPS / 4N байтов). Интуитивно понятно, что это имеет смысл, потому что в кеш уже загружены данные, и запись может изменить кеш напрямую, а не возвращаться в основную память (однако данные в конечном итоге должны быть записаны обратно, но это требование не изменилось с первого раза петля).

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]