Какова требуемая сложность функции, не связанной с основной памятью?

Question

Я знаю, что доступ к основной памяти имеет высокую задержку, если данные не кэшируются. Этот вопрос о пропускной способности.

Какова необходимая сложность функции, которая никогда не должна быть связана основной памятью на обычном настольном ПК?

Я читал о современной ОЗУ с пропускной способностью 25-30 ГБ/с (DDR3 RAM, двухканальный режим). Насколько я могу судить, одно ядро ​​современного процессора Intel может хранить не более 32 байт на инструкцию с использованием современных наборов инструкций SIMD. и он может выполнять не более 4 * 10^9 инструкций. Так эффективно, он может выводить около 120 ГБ/с. Учитывая процессор с 8 потоками, максимальная сумма вывода составит около 960 ГБ/с в качестве наихудшей оценки.

Процессор может вывести не более ~ 36 раз данные, которые могут быть записаны в ОЗУ. Можно ли предположить, что любая функция, выполняющая операции без нагрузки и хранения более 36 циклов в одном SIMD-хранилище или загрузке (или более 9 циклов на обычное 8-байтовое хранилище или загрузка) никогда не будет связана с основной памятью? Может ли эта оценка быть значительно снижена или она слишком низкая по некоторым причинам?

Учитывая, что у меня есть:

X = (x_1, x_2, ..., x_n) // dataset, large enough to make good use of caches 
a(x), b(x), c(x, y), d(x) := c(a(x), b(x)) // functions that operate on elements 
A(x) := (a(x_1), a(x_2), ..., a(x_n)) // functions that operate on data sets 

Ищу руководящих принципов, когда это лучше (или не хуже) осуществлять

D(X) 

в

C(A(X), B(X)) 

учитывая, что первая реализация оказывает большее давление на тайники и регистры, а вторая реализация имеет больше операций загрузки/хранения.

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

Answer 1

Я думаю, что это очень зависит от того, написан ли код таким образом, что ЦП может предварительно выбрать следующий элемент данных в кеш. Если он предварительно задает неправильные данные, вы по-прежнему будете связаны с памятью независимо от того, сколько времени вы тратите на обработку текущих данных.

И если у вас есть несколько потоков, которые записываются на один и тот же адрес (их данные будут находиться в разных строках кэша), то даже если он был предварительно запрограммирован правильно, если другой поток был записан на этот адрес, тогда он должен быть сброшен и повторно -read из основной памяти.

В целом я думаю, что на этом уровне невозможно рассуждать об этих вещах, и это будет зависеть от точного сценария, который у вас есть.