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

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

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

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

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

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

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

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

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